Compiled scikit-learn decision trees for faster evaluation
Project description
In some use cases, predicting given a model is in the hot-path, so speeding up decision tree evaluation is very useful.
An effective way of speeding up evaluation of decision trees can be to generate code representing the evaluation of the tree, compile that to optimized object code, and dynamically load that file via dlopen/dlsym or equivalent.
See https://courses.cs.washington.edu/courses/cse501/10au/compile-machlearn.pdf for a detailed discussion, and http://tullo.ch/articles/decision-tree-evaluation/ for a more pedagogical explanation and more benchmarks in C++.
It’s fairly trivial to implement this for regression trees due to the simpler predict() method, but in theory is possible do to it for arbitrary multi-class, multi-output trees.
This package implements the simple case of single-output regression trees. There are a few changes that need to be made to allow it to work on Linux (change the CXX compiler invocation flags), and Windows (use the appropriate equivalents of dlopen, etc).
Benchmarks
For random forests, we see 5x to 8x speedup in evaluation. For gradient boosted ensembles, it’s between a 1.5x and 3x speedup in evaluation. This is due to the fact that gradient boosted trees already have an optimized prediction implementation.
There is a benchmark script attached that allows us to examine the performance of evaluation across a range of ensemble configurations and datasets.
In the graphs attached, GB is Gradient Boosted, RF is Random Forest, D1, etc correspond to setting max-depth=1, and B10 corresponds to setting max_leaf_nodes=10.
Graphs
for dataset in friedman1 friedman2 friedman3 uniform hastie; do
python ../benchmarks/bench_compiled_tree.py \
--iterations=10 \
--num_examples=1000 \
--num_features=50 \
--dataset=$dataset \
--max_estimators=300 \
--num_estimator_values=6
done
