Ensemble methods; mixing predictions from many weak learners to get strong learners.
The rule of thumb seems to be “Fast to train, fast to use. Gets you results. May not get you answers.” So, like neural networks but from the previous hype cycle.
Questions
In a different context, I’ve run into the general ensemble method model averaging; How does that relate to boosting/bagging algorithms? How does random tree methods relate to dropout? To boostrap?
Random trees, forests, jungles
- Awesome Random Forests
- how to do machine vision using random forests brought to you by the folks behind Kinect.
- generalized random forests [Athey, Tibshirani, and Wager (2019)} (implementationa) are a mild generalisation.
Self-regularising properties
Jeremy Kun: Why Boosting Doesn’t Overfit:
Boosting, which we covered in gruesome detail previously, has a natural measure of complexity represented by the number of rounds you run the algorithm for. Each round adds one additional “weak learner” weighted vote. So running for a thousand rounds gives a vote of a thousand weak learners. Despite this, boosting doesn’t over-fit on many datasets. In fact, and this is a shocking fact, researchers observed that Boosting would hit zero training error, they kept running it for more rounds, and the generalization error kept going down! It seemed like the complexity could grow arbitrarily without penalty. […] this phenomenon is a fact about voting schemes, not boosting in particular.
🏗
Gradient boosting
The idea of gradient boosting originated in the observation by Leo Breiman that boosting can be interpreted as an optimization algorithm on a suitable cost function Breiman (1997). Explicit regression gradient boosting algorithms were subsequently developed by Jerome H. Friedman, (Friedman 2001, 2002) simultaneously with the more general functional gradient boosting perspective of Llew Mason, Jonathan Baxter, Peter Bartlett and Marcus Frean (Mason et al. 1999). The later two papers introduced the view of boosting algorithms as iterative functional gradient descent algorithms. That is, algorithms that optimize a cost function over function space by iteratively choosing a function (weak hypothesis) that points in the negative gradient direction. This functional gradient view of boosting has led to the development of boosting algorithms in many areas of machine learning and statistics beyond regression and classification.
Bayes
The Bayesian Additive Regression Trees Chipman, George, and McCulloch (2010), are wildly popular and successful in machine learning competitions. Kenneth Tay does a good intro.
Implementations
xgboost
XGBoost is an optimized distributed gradient boosting library designed to be highly efficient, flexible and portable. It implements machine learning algorithms under the Gradient Boosting framework. XGBoost provides a parallel tree boosting (also known as GBDT, GBM) that solve many data science problems in a fast and accurate way. The same code runs on major distributed environment (Hadoop, SGE, MPI) and can solve problems beyond billions of examples.
catboost
bartmachine
We present a new package in R implementing Bayesian additive regression trees (BART). The package introduces many new features for data analysis using BART such as variable selection, interaction detection, model diagnostic plots, incorporation of missing data and the ability to save trees for future prediction It is significantly faster than the current R implementation, parallelized, and capable of handling both large sample sizes and high-dimensional data.
Athey, Susan, Julie Tibshirani, and Stefan Wager. 2019. “Generalized Random Forests.” Annals of Statistics 47 (2): 1148–78. https://doi.org/10.1214/18-AOS1709.
Balog, Matej, Balaji Lakshminarayanan, Zoubin Ghahramani, Daniel M. Roy, and Yee Whye Teh. 2016. “The Mondrian Kernel.” June 16, 2016. http://arxiv.org/abs/1606.05241.
Balog, Matej, and Yee Whye Teh. 2015. “The Mondrian Process for Machine Learning.” July 18, 2015. http://arxiv.org/abs/1507.05181.
Bickel, Peter J., Bo Li, Alexandre B. Tsybakov, Sara A. van de Geer, Bin Yu, Teófilo Valdés, Carlos Rivero, Jianqing Fan, and Aad van der Vaart. 2006. “Regularization in Statistics.” Test 15 (2): 271–344. https://doi.org/10.1007/BF02607055.
Breiman, Leo. 1997. “Arcing the Edge.” Statistics Department, University of California, Berkeley. https://statistics.berkeley.edu/sites/default/files/tech-reports/486.pdf.
———. 1996. “Bagging Predictors.” Machine Learning 24 (2): 123–40. https://doi.org/10.1007/BF00058655.
Bühlmann, Peter, and Sara van de Geer. 2011. Statistics for High-Dimensional Data: Methods, Theory and Applications. 2011 edition. Heidelberg ; New York: Springer.
Chipman, Hugh A., Edward I. George, and Robert E. McCulloch. 2010. “BART: Bayesian Additive Regression Trees.” The Annals of Applied Statistics 4 (1): 266–98. https://doi.org/10.1214/09-AOAS285.
Criminisi, Antonio, Jamie Shotton, and Ender Konukoglu. 2012. Decision Forests: A Unified Framework for Classification, Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning. Vol. 7. https://doi.org/10.1561/0600000035.
Díaz-Avalos, Carlos, P. Juan, and J. Mateu. 2012. “Similarity Measures of Conditional Intensity Functions to Test Separability in Multidimensional Point Processes.” Stochastic Environmental Research and Risk Assessment 27 (5): 1193–1205. https://doi.org/10.1007/s00477-012-0654-1.
Fernández-Delgado, Manuel, Eva Cernadas, Senén Barro, and Dinani Amorim. 2014. “Do We Need Hundreds of Classifiers to Solve Real World Classification Problems?” Journal of Machine Learning Research 15 (1): 3133–81. http://jmlr.org/papers/v15/delgado14a.html.
Friedman, Jerome H. 2001. “Greedy Function Approximation: A Gradient Boosting Machine.” The Annals of Statistics 29 (5): 1189–1232. https://doi.org/10.1214/aos/1013203451.
———. 2002. “Stochastic Gradient Boosting.” Computational Statistics & Data Analysis, Nonlinear Methods and Data Mining, 38 (4): 367–78. https://doi.org/10.1016/S0167-9473(01)00065-2.
Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. 2000. “Additive Logistic Regression: A Statistical View of Boosting (with Discussion and a Rejoinder by the Authors).” The Annals of Statistics 28 (2): 337–407. https://doi.org/10.1214/aos/1016218223.
Gall, J., and V. Lempitsky. 2013. “Class-Specific Hough Forests for Object Detection.” In Decision Forests for Computer Vision and Medical Image Analysis, edited by A. Criminisi and J. Shotton, 143–57. Advances in Computer Vision and Pattern Recognition. Springer London. http://www.iai.uni-bonn.de/~gall/download/jgall_houghforest_cvpr09.pdf.
Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. 2015. “Distilling the Knowledge in a Neural Network.” March 9, 2015. http://arxiv.org/abs/1503.02531.
Johnson, R., and Tong Zhang. 2014. “Learning Nonlinear Functions Using Regularized Greedy Forest.” IEEE Transactions on Pattern Analysis and Machine Intelligence 36 (5): 942–54. https://doi.org/10.1109/TPAMI.2013.159.
Kapelner, Adam, and Justin Bleich. 2016. “bartMachine: Machine Learning with Bayesian Additive Regression Trees.” Journal of Statistical Software 70 (4). https://doi.org/10.18637/jss.v070.i04.
Lakshminarayanan, Balaji, Daniel M Roy, and Yee Whye Teh. 2014. “Mondrian Forests: Efficient Online Random Forests.” In Advances in Neural Information Processing Systems 27, edited by Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, 3140–8. Curran Associates, Inc. http://papers.nips.cc/paper/5234-mondrian-forests-efficient-online-random-forests.pdf.
Mason, Llew, Jonathan Baxter, Peter Bartlett, and Marcus Frean. 1999. “Boosting Algorithms as Gradient Descent.” In Proceedings of the 12th International Conference on Neural Information Processing Systems, 512–18. NIPS’99. Denver, CO: MIT Press.
Mentch, Lucas, and Siyu Zhou. 2020. “Randomization as Regularization: A Degrees of Freedom Explanation for Random Forest Success.” Journal of Machine Learning Research 21 (171): 1–36. http://jmlr.org/papers/v21/19-905.html.
Nock, Richard, and Wilko Henecka. 2020. “Boosted and Differentially Private Ensembles of Decision Trees.” February 3, 2020. http://arxiv.org/abs/2001.09384.
Rahimi, Ali, and Benjamin Recht. 2009. “Weighted Sums of Random Kitchen Sinks: Replacing Minimization with Randomization in Learning.” In Advances in Neural Information Processing Systems, 1313–20. Curran Associates, Inc. http://papers.nips.cc/paper/3495-weighted-sums-of-random-kitchen-sinks-replacing-minimization-with-randomization-in-learning.
Schapire, Robert E., Yoav Freund, Peter Bartlett, and Wee Sun Lee. 1998. “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods.” The Annals of Statistics 26 (5): 1651–86. https://doi.org/10.1214/aos/1024691352.
Scornet, Erwan. 2014. “On the Asymptotics of Random Forests.” September 7, 2014. http://arxiv.org/abs/1409.2090.
Scornet, Erwan, Gérard Biau, and Jean-Philippe Vert. 2014. “Consistency of Random Forests.” May 12, 2014. http://arxiv.org/abs/1405.2881.
Shotton, Jamie, Toby Sharp, Pushmeet Kohli, Sebastian Nowozin, John Winn, and Antonio Criminisi. 2013. “Decision Jungles: Compact and Rich Models for Classification.” In NIPS. http://research.microsoft.com/apps/pubs/default.aspx?id=205439.