Consistency of Random Forests

By Erwan Scornet, Gérard Biau, Jean-Philippe Vert. 2014

619 citations recorded by the source corpus.

Random forests are a learning algorithm proposed by Breiman [Mach. Learn. 45 (2001) 5–32] that combines several randomized decision trees and aggregates their predictions by averaging. Despite its wide usage and outstanding practical performance, little is known about the mathematical properties of the procedure. This disparity between theory and practice originates in the difficulty to simultaneously analyze both the randomization process and the highly data-dependent tree structure. In the present paper, we take a step forward in forest exploration by proving a consistency result for Breiman's [Mach. Learn. 45 (2001) 5–32] original algorithm in the context of additive regression models. Our analysis also sheds an interesting light on how random forests can nicely adapt to sparsity. 1. Introduction. Random forests are an ensemble learning method for classification and regression that constructs a number of randomized decision trees during the training phase and predicts by averaging the results. Since its publication in the seminal paper of Breiman (2001), the procedure has become a major data analysis tool, that performs well in practice in comparison with many standard methods. What has greatly contributed to the popularity of forests is the fact that they can be applied to a wide range of prediction problems and have few parameters to tune. Aside from being simple to use, the method is generally recognized for its accuracy and its ability to deal with small sample sizes, high-dimensional feature spaces and complex data structures. The random forest methodology has been successfully involved in many practical problems, including air quality prediction (winning code of the EMC data science global hackathon in 2012, see http://www.kaggle.com/c/dsg-hackathon), chemoinformatics [Svetnik et al. (2003)], ecology [Prasad, Iverson and Liaw (2006), Cutler et al. (2007)], 3D

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Local Linear Forests (2018, background): “Bühlmann and Yu (2002) showed how bagging makes forests smoother than single trees, while Biau (2012) and Scornet, Biau, and Vert (2015) established asymptotic risk consistency of random forests under specific assumptions.”
Metalearners for estimating heterogeneous treatment effects using machine learning (2017, background): “[17] Scornet E, Biau G, Vert JP (2015) Consistency of random forests.”
Generalized random forests (2016, methodology): “Following Sexton and Laake (2009), however, we can efficiently approximate ĤHS n (x) at almost no computational cost if we are willing to slightly modify our subsampling scheme.”
Uniform Convergence of Random Forests via Adaptive Concentration (2015, background): “In particular, Scornet et al. [36] prove that Breiman’s original forests are L 2 consistent assuming that the conditional mean surface E [ Y | X = x ] is an additive function, while Biau [4] and Denil et al. [16] discuss the properties of some random forests where trees are grown using only a…”
Forecasting Inflation in a Data-Rich Environment: The Benefits of Machine Learning Methods (2019, positive): “This late success is partly due to the new theoretical results developed by Scornet, Biau, and Vert (2015) and Wagner and Athey (2018).”
On the asymptotics of random forests (2014, background): “Recent attempts to bridge the gap between theoretical forest models and Breiman’s (2001) forests have been made by Wager (2014) and Scornet et al. (2014) who establish consistency of the original algorithm under suitable assumptions.”
The Rhetoric and Reality of Anthropomorphism in Artificial Intelligence (2019, background): “, observations drawn randomly without replacement—which are more theoretically tractable (Mentch and Hooker 2016; Scornet et al. 2015; Wager and Athey 2018).”
Random Forests for Big Data (2015, background): “Key words: Random Forest, Big Data, Parallel Computing, Bag of Little Bootstraps, On-line Learning”
Getting Better from Worse: Augmented Bagging and a Cautionary Tale of Variable Importance (2020, background): “…their inception, numerous studies have sought to establish their important statistical properties including consistency (Biau and Devroye, 2010; Scornet et al., 2015; Klusowski, 2019), asymptotic normality (Mentch and Hooker, 2016; Wager and Athey, 2018), and rates of convergence (Peng et al.,…”
A review on machine learning principles for multi-view biological data integration (2016, background): “Recent studies also prove that not all random forest models are universally consistent [55, 56].”
Reliable ABC model choice via random forests (2014, background): “A first step addressing this issue is to obtain error rates conditional on the data as in Stoehr et al. (2015). However, the statistical methodology considered therein suffers from the curse of dimensionality and we here consider a different approach to precisely estimate this error.”
Adaptive Concentration of Regression Trees, with Application to Random Forests (2015, background): “[38] to ensure that trees can eventually accumulate evidence enabling them to split along signal coordinates.”
Boulevard: Regularized Stochastic Gradient Boosted Trees and Their Limiting Distribution (2018, neutral): “In particular, the consistency of methods related to Random Forests (RFs: Breiman, 2001) has been demonstrated in Biau (2012); Scornet et al. (2015) while Wager et al. (2014); Mentch and Hooker (2016); Wager and Athey (2017) and Athey et al. (2016) prove central limit theorems for RF predictions.”
: "Statistical Modeling: The Two Cultures" (Statistical Science, 2001, 16(3), 199-231) (neutral): “It has made strides in understanding theoretical aspects of random forests, (Scornet et al., 2015; Wager and Walther, 2015; Athey et al., 2019) and boosting (B¨uhlmann and Yu, 2003; Zhang and Yu, 2005), in understanding prediction accuracy from scratch by establishing non-asymptotic prediction…”