5 ms·

The article mentions that "The main drawback of Random Forests is the model size. You could easily end up with a forest that takes hundreds of megabytes of memo

The article mentions that "The main drawback of Random Forests is the model size. You could easily end up with a forest that takes hundreds of megabytes of memory and is slow to evaluate." 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 https://github.com/ajtulloch/sklearn-compiledtrees if you're interested in this technique.

shoo 11y ago
(I) Indeed, it is a pretty good trick, and is simple to implement, given that the algorithm for evaluating a random forest is simple. Good on you for implementing it nicely for scikit-learn, benchmarking it, and making the code available. 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 This probably isn't the fastest possible encoding of a bunch of decision trees, but it was pretty quick. (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.htm 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.htm#varimp 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.
ching_wow_ka 11y ago
Is this often done? Can you provide a reference explaining this further? Possibly specific to ML models.
CyberDildonics 11y ago
Why go through all that though? The fundamental principle is that it is flattening the buffer to one linear section of memory, making the pointers jump to a location that is likely already prefetched and possibly in the same cache line. Dumping to C seems like it is missing the point. 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.
- ajtulloch 11y ago
  That's actually not the case - that's one effect, sure, but when you compared the compiled trees to the flattened trees (the strategy just described), the compiled trees are substantially faster across a range of parameters. See http://tullo.ch/articles/decision-tree-evaluation/ http://tullo.ch/articles/decision-tree-evaluation/ for a detailed evaluation.
  - CyberDildonics 11y ago
    That's really awesome that you put that together, but I have to think that 200 points and a depth < 2 would basically be a linear search over about 100 elements right? 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.
joe_the_user 11y ago
Mmmm, 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: https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf

shoo 11y ago

(I) Indeed, it is a pretty good trick, and is simple to implement, given that the algorithm for evaluating a random forest is simple. Good on you for implementing it nicely for scikit-learn, benchmarking it, and making the code available. 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 This probably isn't the fastest possible encoding of a bunch of decision trees, but it was pretty quick. (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.htm 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.htm#varimp 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.

ching_wow_ka 11y ago

Is this often done? Can you provide a reference explaining this further? Possibly specific to ML models.

CyberDildonics 11y ago

Why go through all that though? The fundamental principle is that it is flattening the buffer to one linear section of memory, making the pointers jump to a location that is likely already prefetched and possibly in the same cache line. Dumping to C seems like it is missing the point. 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.

ajtulloch 11y ago
That's actually not the case - that's one effect, sure, but when you compared the compiled trees to the flattened trees (the strategy just described), the compiled trees are substantially faster across a range of parameters. See http://tullo.ch/articles/decision-tree-evaluation/ http://tullo.ch/articles/decision-tree-evaluation/ for a detailed evaluation.
- CyberDildonics 11y ago
  That's really awesome that you put that together, but I have to think that 200 points and a depth < 2 would basically be a linear search over about 100 elements right? 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.

joe_the_user 11y ago

Mmmm, 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: https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf https://www.stat.berkeley.edu/~breiman/randomforest2001.pdf