The Unreasonable Effectiveness of Random Forests
medium.com
medium.com
A cool trick for speeding up trained random forests/gradient boosted decision trees is to dump the tree to C/ASM, compile it, and dlopen it as a function pointer. Depending on the model and the architecture, you can get an 8x speedup relative to an optimized C implementation that walks the tree.
There's an implementation for scikit-learn with benchmarks at https://github.com/ajtulloch/sklearn-compiledtrees if you're interested in this technique.
I did something similar a few years ago when using a random forest as a heuristic to speed-up some minimax game tree search code. I don't think I still have the python scripts used to generate the compiled code (no great loss, they would have been terrible throwaway code) but amusingly enough I still have an example of a compiled random forest:
(warning: link #2 is a ~44k line cpp file of gotos encoding 50 compiled decision trees)
1. https://raw.githubusercontent.com/fcostin/hangman_cpp/master/forest.h
2. https://raw.githubusercontent.com/fcostin/hangman_cpp/master/forest.cpp
(II) On a different note, the article states "Another point that some might find a concern is that random forest models are black boxes that are very hard to interpret.". Well, yes and no. Decision trees are pretty easy to interpret -- you can always pick out one of the decision trees and look at it.
If one is interested in learning more about random forests I'd recommend taking a look at these notes from Breiman and Cutler (the folks responsible for the algorithm!): https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home...
E.g. they discuss "variable importance" measures, as featured in the original R version of randomForest. There are a bunch of tools built around random forests for extracting some insight beyond the raw predictions, to aid interpretation! Use them! https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home...
(III) Final comment: the article doesn't mention the Bayesian interpretation of ensembling a bunch of statistical models together. That's another potentially insightful way of thinking about why the method might be effective, and isn't limited to decision trees.
A library like Cereal should be able to do this almost trivially simply by serializing the data, unserializing it to a flat buffer, then pointing to the start of that buffer.
Also I should say that a random forest created by pointer hopping to each new level is a very naive implementation and will take a long time to create due to heap allocation and a long time to traverse due to cache misses.
Fundamentally I can't think of any reason compiling a tree would be a good approach in a general sense.
Another optimization is to put make splits multiple levels instead of just one. How many might depend on how many you can squeeze into a cache line. If you split position is a float and the dimension is a byte, each split would be 5 bytes. You can squeeze 12 of these into a cache line. You can go 3 level down instead of one by packing 7 of them into a chunk (1 split + 2 splits + 4 splits). This still leaves room for a 32 bit index or pointer for each of the 4 leaves.
Yeah, as I understand it, the enthusiasm for deep learning comes because it scales well to truly huge data sets where most other machine learning algorithms tend to create artifacts of a similar size to the data in question.
That is to say that deep learning, random trees and SVMs all do approximately the same thing - non-linear regression, equivalently regression on a feature space, roughly drawing curves between two sets on huge dimensional space and using these curves for distinguishing objects.
Also - the linked paper giving all the actual details of the algorithm seems unresponsive.
This link worked for me:
The main trick is in storing the tree as a binary heap in the rows of a texture, with the left and right subtrees at 2i and 2i+1, respectively, and where the attribute index and split value are encoded in the color channels. Your texture width is your tree depth^2-1, and your texture height the number of trees in your forest. The texture ends up looking something like this (scaled up x10) http://i.imgur.com/afH5iFl.png
With a GPU shader, you can navigate these trees very quickly to classify an entire input image at once.
Now we have The Unreasonable Effectiveness of Random Forests and The Unreasonable Effectiveness of Recurrent Neural Networks. We just need The Unreasonable Effectiveness of XGBoost (for winning Kaggle competitions) and we'll have the whole set.
[1] http://on-demand.gputechconf.com/gtc/2014/webinar/gtc-expres...
https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65....
Here's what this means visually:
http://i.imgur.com/IjfXFkm.png
There is just one of the 100 data sets generated shown.
> Another point that some might find a concern is that random forest models are black boxes that are very hard to interpret.
I generally agree that random forests are more difficult to interpret than linear models such as logistic regression, but I think they're still far more interpretable than more comparable non-linear models such as neural networks or SVMs with non-linear kernels. At the end of the day, a random forest is just a bunch of decision trees, each of which are very straightforward for humans to understand. Additionally, there are a number of straightforward methods available for assessing the importance of each individual feature in a random forest in aggregate ([1], section 15.4). Neural networks, on the other hand, result in models that are too cryptic to be meaningfully inspected by a human, and have more complex variable importance measures [2].
The relative interpretability of these non-linear models played a large factor in our decision to add random forests to our modeling stack at Sift Science, which you can read more about here: http://blog.siftscience.com/blog/2015/large-scale-decision-f...
[1]: http://statweb.stanford.edu/~tibs/ElemStatLearn/
[2]: http://www.massey.ac.nz/~mkjoy/pdf/Olden,Joy&DeathEM.pdf
Maybe I'm not the target audience, though.
Usually the SciKit-learn algorithm cheat sheet[1] is a good guide for this, but it doesn't include random forest (or any kind of decision tree).
[1] http://scikit-learn.org/stable/tutorial/machine_learning_map...
This is largely because they are a randomized ensemble of weaker models. Individual decision trees are quite prone to overfitting and other issues but in an rf you grow a bunch of them on diffrent bootstrap samples of the data and let them vote and it turns out the combined performance is much better and much less error prone then a single model.
Specific examples where they work well include genetic data (many more noisy variables then observations) and customer/consumer data. They also get used in image data and signal processing but deep neural networks are recently tending to beat them here and in similar less heterogenous data sets.
Many times I ended up using linear regression (with properly engineered variables), or something as simple, because it gave almost as good results as RF, but I could interpret the results, inputs, etc. (And may task was academic or business analytics, so CV score was not the only figure of merit.)
Moreover, not-so-obviously strange rules learned by more complex models were exposed as strange by the information-dense pictorial representation of linear regression.
The abstract:
In this paper we perform an empirical evaluation of supervised learning on high-dimensional data. We evaluate performance on three metrics: accuracy, AUC, and squared loss and study the effect of increasing dimensionality on the performance of the learning algorithms. Our findings are consistent with previous studies for problems of relatively low dimension, but suggest that as dimensionality increases the relative performance of the learning algorithms changes. To our surprise, the method that performs consistently well across all dimensions is random forests, followed by neural nets, boosted trees, and SVMs.
This Monday I'm publishing a post on [1] that gives some rigorous explanation for this, which essentially covers the results of this paper [2] whose main theorem is a claim about majority voting schemes.
[2]: http://cseweb.ucsd.edu/~yfreund/papers/BoostingtheMargin.pdf
> Some like SVMs for the elegance of their formulation or the quality of the available implementations, some like decision rules for their simplicity and interpretability, and some are crazy about neural networks for their flexibility.
Nowadays it seems that ANN (and related algorithms) get all the credit. It's refreshing to see someone point out why some people actually prefer other methods.