Loading repository data…
Loading repository data…
szilard / repository
A minimal benchmark for scalability, speed and accuracy of commonly used open source implementations (R packages, Python scikit-learn, H2O, xgboost, Spark MLlib etc.) of the top machine learning algorithms for binary classification (random forests, gradient boosted trees, deep neural networks etc.).
All benchmarks are wrong, but some are useful
This project aims at a minimal benchmark for scalability, speed and accuracy of commonly used implementations of a few machine learning algorithms. The target of this study is binary classification with numeric and categorical inputs (of limited cardinality i.e. not very sparse) and no missing data, perhaps the most common problem in business applications (e.g. credit scoring, fraud detection or churn prediction). If the input matrix is of n x p, n is varied as 10K, 100K, 1M, 10M, while p is ~1K (after expanding the categoricals into dummy variables/one-hot encoding). This particular type of data structure/size (the largest) stems from this author's interest in some particular business applications.
A large part of this benchmark was done in 2015, with a number of updates later on as things have changed. Make sure you read at the end of this repo a summary of how the focus has changed over time, and why instead of updating this benchmark I started a new one (and where to find it).
The algorithms studied are
in various commonly used open source implementations like
Update (June 2015): It turns out these are the most popular tools used for machine learning indeed. If your software tool of choice is not here, you can do a minimal benchmark with little work with the following instructions.
Random forest, boosting and more recently deep neural networks are the algos expected to perform the best on the structure/sizes described above (e.g. vs alternatives such as k-nearest neighbors, naive-Bayes, decision trees, linear models etc). Non-linear SVMs are also among the best in accuracy in general, but become slow/cannot scale for the larger n sizes we want to deal with. The linear models are less accurate in general and are used here only as a baseline (but they can scale better and some of them can deal with very sparse features, so they are great in other use cases).
By scalability we mean here that the algos are able to complete (in decent time) for the given data sizes with the main constraint being RAM (a given algo/implementation will crash if running out of memory). Some of the algos/implementations can work in a distributed setting, although the largest dataset in this study n = 10M is less than 1GB, so scaling out to multiple machines should not be necessary and is not the focus of this current study. (Also, some of the algos perform relatively poorly speedwise in the multi-node setting, where communication is over the network rather than via updating shared memory.) Speed (in the single node setting) is determined by computational complexity but also if the algo/implementation can use multiple processor cores. Accuracy is measured by AUC. The interpretability of models is not of concern in this project.
In summary, we are focusing on which algos/implementations can be used to train relatively accurate binary classifiers for data with millions of observations and thousands of features processed on commodity hardware (mainly one machine with decent RAM and several cores).
Training datasets of sizes 10K, 100K, 1M, 10M are generated from the well-known airline dataset (using years 2005 and 2006). A test set of size 100K is generated from the same (using year 2007). The task is to predict whether a flight will be delayed by more than 15 minutes. While we study primarily the scalability of algos/implementations, it is also interesting to see how much more information and consequently accuracy the same model can obtain with more data (more observations).
The tests have been carried out on a Amazon EC2 c3.8xlarge instance (32 cores, 60GB RAM). The tools are freely available and their installation is trivial (version information here). For some of the models that ran out of memory for the larger data sizes a r3.8xlarge instance (32 cores, 250GB RAM) has been used occasionally. For deep learning on GPUs, p2.xlarge (1 GPU with 12GB video memory, 4 CPU cores, 60GB RAM) instance has been used.
Update (January 2018): A more modern approach would use docker for fully automated installing of all ML software and automated timing/running of tests (which would make it more easy to rerun the tests on new versions of the tools, would make them more reproducible etc). This approach has been actually used in a successor of this benchmark focusing on the top performing GBM implementations only, see here.
For each algo/tool and each size n we observe the following: training time, maximum memory usage during training, CPU usage on the cores, and AUC as a measure for predictive accuracy. Times to read the data, pre-process the data, score the test data are also observed but not reported (not the bottleneck).
The linear models are not the primary focus of this study because of their not so great accuracy vs the more complex models (on this type of data). They are analyzed here only to get some sort of baseline.
The R glm function (the basic R tool for logistic regression) is very slow, 500 seconds on n = 0.1M (AUC 70.6). Therefore, for R the glmnet package is used. For Python/scikit-learn LogisticRegression (based on the LIBLINEAR C++ library) has been used.
| Tool | n | Time (sec) | RAM (GB) | AUC |
|---|---|---|---|---|
| R | 10K | 0.1 | 1 | 66.7 |
| . | 100K | 0.5 | 1 | 70.3 |
| . | 1M | 5 | 1 | 71.1 |
| . | 10M | 90 | 5 | 71.1 |
| Python | 10K | 0.2 | 2 | 67.6 |
| . | 100K | 2 | 3 | 70.6 |
| . | 1M | 25 | 12 | 71.1 |
| . | 10M | crash/360 | 71.1 | |
| VW | 10K | 0.3 (/10) | 66.6 | |
| . | 100K | 3 (/10) | 70.3 | |
| . | 1M | 10 (/10) | 71.0 | |
| . | 10M | 15 | 71.0 | |
| H2O | 10K | 1 | 1 | 69.6 |
| . | 100K | 1 | 1 | 70.3 |
| . | 1M | 2 | 2 | 70.8 |
| . | 10M | 5 | 3 | 71.0 |
| Spark | 10K | 1 | 1 | 66.6 |
| . | 100K | 2 | 1 | 70.2 |
| . | 1M | 5 | 2 | 70.9 |
| . | 10M | 35 | 10 | 70.9 |
Python crashes on the 60GB machine, but completes when RAM is increased to 250GB (using a sparse format would help with memory footprint and likely runtime as well). The Vowpal Wabbit (VW) running times are reported in the table for 10 passes (online learning) over the data for the smaller sizes. While VW can be run on multiple cores (as multiple processes communicating with each other), it has been run here in the simplest possible way (1 core). Also keep in mind that VW reads the data on the fly while for the other tools the times reported exclude reading the data into memory.
One can play with various parameters (such as regularization) and even do some search in the parameter space with cross-validation to get better accuracy. However, very quick experimentation shows that at least for the larger sizes regularization does not increase accuracy significantly (which is expected since n >> p).
The main conclusion here is that it is trivial to train linear models even for n = 10M rows virtually in any of these tools on a single machine in a matter of seconds. H2O and VW are the most memory efficient (VW needs only 1 observation in memory at a time therefore is the ultimately scalable solution). H2O and VW are also the fastest (for VW the time reported includes the time to read the data as it is read on the fly). Again, the differences in memory efficiency and speed will start to really matter only for larger sizes and beyond the scope of this study.
For this dataset the accuracy of the linear model tops-off at moderate sizes while the accuracy of non-linear models (e.g. random forest) continues to increase with increasing data size. This is because a simple linear structure can be extracted already from a smaller dataset and having more data points will not change the classification boundary significantly. On the other hand, more complex models such as random forests can improve further with increasing data size by adjusting further the classification boundary.
This means that having more data ("big data") does not improve further the accuracy of the linear model (at least for this dataset).
Note also that the random forest model is more accurate than the linear one for any size, and contrary to the conventional wisdom of "more data beats better algorithms", the random forest model on 1% of the data (100K records) beats the linear model on all the data (10M records).
Similar behavior can be observed in other non-sparse datasets, e.g. the Higgs dataset. Contact me (e.g. submit a github issue) if you have learning curves for linear vs non-linear models on other datasets (dense or sparse).
On the other hand, there is certainly a price for higher accuracy in terms of larger required training (CPU) time.
Ultimately, there is a data size - algo (complexity) - cost (CPU time) - accuracy tradeoff (to be studied in more details later). Some quick results for H2O:
| n | Model | Time (sec) | AUC |
|---|---|---|---|
| 10M | Linear | 5 | 71.0 |
| 0.1M | RF | 150 | 72.5 |
| 10M | RF | 4000 | 77.8 |
Note: The random forests results have been published in a more organized and self-contained form in this blog post.
Random forests with 500 trees have been trained in each tool choosing the default of square root of p as the number of variables to split on.
| Tool | n | Time (sec) | RAM (GB) | AUC |
|---|---|---|---|---|
| R | 10K | 50 | 10 | 68.2 |
| . | 100K | 1200 | 35 | 71.2 |
| . | 1M | crash | ||
| Python | 10K | 2 | 2 | 68.4 |
| . | 100K | 50 | 5 | 71.4 |
| . | 1M | 900 | 20 | 73.2 |
| . | 10M | crash | ||
| H2O | 10K | 15 | 2 | 69.8 |
| . | 100K | 150 | 4 | 72.5 |
| . | 1M | 600 | 5 | 75.5 |
| . | 10M | 4000 | 25 | 77.8 |
| Spark | 10K | 50 | 10 | 69.1 |
| . | 100K | 270 | 30 | 71.3 |
| . | 1M | crash/2000 | 71.4 | |
| xgboost | 10K | 4 | 1 | 69.9 |
| . | 100K | 20 | 1 | 73.2 |
| . | 1M | 170 | 2 | 75.3 |
| . | 10M | 3000 | 9 | 76.3 |
The R implementation (randomForest package) is slow and inefficient in memory use. It cannot cope by default with a large number of categories, therefore the data had to be one-hot encode