Sparse Policy Tree 
An R / Rust Package to implement an exhaustive tree search for
policy-learning. Aims to extend and speed up work done with the
policytree package.
Usage
There’s just one function, sparse_policy_tree(). Use it just as you
would the policy_tree() function from the policytree package.
Trees aren’t guaranteed to be exactly the same as those produced by
policytree in that some leaves may be left unpruned (working on this),
but they should give the same predictions.
n <- 400
p <- 4
d <- 3
depth <- 2
# Classification task taken from policytree tests
# Continuous X
X <- round(matrix(rnorm(n * p), n, p),2)
colnames(X) <- letters[1:ncol(X)]
Y <- matrix(0, n, d)
best.tree <- policytree:::make_tree(X, depth = depth, d = d)
best.action <- policytree:::predict_test_tree(best.tree, X)
Y[cbind(1:n, best.action)] <- 100 * runif(n)
best.reward <- sum(Y[cbind(1:n, best.action)])
tree <- sparse_policy_tree(X,Y,2)
tree
#> policy_tree object
#> Tree depth: 2
#> Actions: 1 2 3
#> Variable splits:
#> (1) split_variable: b split_value: -0.73
#> (2) split_variable: a split_value: -3.36
#> (4) * action: 3
#> (5) * action: 3
#> (3) split_variable: a split_value: 0.57
#> (6) * action: 3
#> (7) * action: 2Installation:
Installing Rust:
You must have Rust installed to compile this package. The rust website provides an excellent installation script that has never caused me any issues.
On Linux, you can install Rust with:
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | shOn Windows, I use the rust installation wizard, found here.
Installing Package from Github:
Once you install rust, you should be able to install the package with:
devtools::install_github("Yale-Medicaid/sparsepolicytree")Benchmarks:
Below are the results from a series of benchmarks to gauge the speed of the package. These were run on an old 4-core, 8-thread server that I have access to, and I think should be pretty representative of the speed a user can expect to see if they run the algorithm on all cores of a modern data-science laptop.
| Number of Observations | Number of Distinct Predictor Values | Number of Predictors | Number of Treatments | Time |
|---|---|---|---|---|
| 10^2 | 2 | 30 | 20 | 0.003s |
| 10^3 | 2 | 30 | 20 | 0.015s |
| 10^4 | 2 | 30 | 20 | 0.15s |
| 10^5 | 2 | 30 | 20 | 1.57s |
| 10^6 | 2 | 30 | 20 | 17s |
| 10^2 | 30 | 30 | 20 | 0.052s |
| 10^3 | 30 | 30 | 20 | 0.240s |
| 10^4 | 30 | 30 | 20 | 3.041s |
| 10^5 | 30 | 30 | 20 | 100s |
| 10^6 | 30 | 30 | 20 | 21 min |
| 10^2 | 10^2 | 30 | 20 | 0.41s |
| 10^3 | 10^3 | 30 | 20 | 40s |
| 10^4 | 10^4 | 30 | 20 | 70 min |
sparse_policy_tree is dominant when the number of values a variable can take is small (say, under 200), but performs poorly when the number of unique values is large. For dense variables, you are generally better off using the policytree package, which is more developed,and will return faster while running on a only single core.
Limiting the Number of Threads:
To constrain the number of cores the program uses, you can set the
RAYON_NUM_THREADS variable before running the search. At present, this
variable is read at the construction of the multithreading thread pool,
and so must be set once each R session. In a future version, I’ll work
to include a fix so that the number of threads can be included in an
argument to the sparse_policy_tree function.
Here’s an example of how to set the function to run on an single core in R:
Sys.setenv(RAYON_NUM_THREADS=1)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent