Source-linked AI summary
Consistency of random forests
Erwan Scornet, Gérard Biau, Jean-Philippe Vert
TL;DR
Random forests are widely used, yet their mathematical properties are difficult to establish because randomization and data-dependent tree structure must be analyzed together. This paper develops an analysis of Breiman’s original procedure for additive regression and proves consistency under stated regimes, while identifying sparsity adaptation and important scope boundaries.
Problem
The paper addresses limited mathematical understanding of widely used random forests, whose randomization and data-dependent tree structure are difficult to analyze simultaneously.
Method
The paper analyzes Breiman’s original random-forest procedure through the behavior of CART-generated cells and parameter regimes controlling leaves or subsampling.
Results
The paper proves L2 consistency for Breiman’s original procedure and shows that rough individual trees can aggregate into a provably consistent forest architecture.
Takeaways & Limitations
The analysis supports consistency for random forests in additive regression and indicates adaptation to sparse settings with many ambient coordinates but fewer informative ones.
Takeaways & Limitations
Pointwise consistency is not guaranteed everywhere, especially near edges, and Theorem 2 relies on assumption (H2), whose general validity is unknown.
Abstract
from arXiv · showhide
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
1. Introduction.
Random forests are widely used and practically successful, but their mathematical properties remain difficult to analyze because randomization interacts with data-dependent tree construction. This paper studies Breiman’s original procedure for additive regression and proves a consistency result while examining sparsity adaptation.
- Random forests combine randomized decision trees and average their predictions for classification and regression.
- Despite broad practical use and strong performance, theoretical understanding of random forests remains limited.
- Bagging and CART splitting are essential components whose complexity has led many theoretical studies to analyze simplified, data-independent procedures.
- The paper proves L2 consistency for Breiman’s original algorithm in additive regression models, presenting what the authors identify as its first consistency result.
- The analysis indicates that random forests can adapt to sparse settings when the ambient dimension is large but only a smaller number of coordinates carry information.
2. Random forests.
The method builds randomized regression trees from sampled data, CART-selected axis-aligned splits, and a chosen number of leaves, then averages tree predictions. The analysis considers finite and infinite forests and allows tuning of sampling and leaf-growth parameters.
- An L2 regression forest estimates m(x) = E[Y | X = x] from independent training pairs by averaging randomized tree predictions.
- The infinite-forest estimate is obtained by taking the number of trees M to infinity and replacing the randomization average with conditional expectation.
- The algorithm uses mtry candidate directions, an sampled observations, and tn leaves as its three principal parameters.
- Each tree samples an data points, selects candidate split directions, optimizes the CART criterion, and stops when it reaches tn leaves.
- The analysis studies both partially grown trees, tn < an, and fully grown trees, tn = an, with parameter choices differing from the original bootstrap defaults.
- The CART criterion chooses axis-perpendicular cuts by optimizing prediction squared error over possible coordinate cuts.
3. Main results.
The paper proves consistency for Breiman’s original random forest algorithm in additive regression models and analyzes its behavior under sparsity. The results cover two tree-growth regimes and identify conditions governing consistency and informative splitting.
- Model and assumptions: The analysis studies additive regression models, where the regression function is decomposed into univariate components under assumptions including continuous components and Gaussian noise.The covariates are uniformly distributed on [0,1]^p, and the noise is independent, centered Gaussian with finite variance.
- Consistency results: Theorem 1 proves random-forest consistency when an →∞, tn →∞, and tn(log an)^9/an →0 under the additive-model assumption (H1).The result applies when the number of leaves grows more slowly than the number of selected data points.
- Consistency results: Theorem 1 remains valid with an = n, so subsampling is unnecessary for consistency when tree depth is controlled by tn.The paper also notes that CART is consistent under the same assumptions.
- Proof strategy and scope: The consistency proofs rely on controlling variation of the regression function within random-tree cells and on analyzing CART-generated cells as sample size increases.For fully grown trees, the required condition (H2) is automatic in some settings, including partitions independent of the responses and the noiseless case, but is unknown generally.
- Consistency results: For fully grown trees with tn = an, Theorem 2 proves consistency when an →∞, tn →∞, and an log n/n →0, assuming (H1) and (H2).The second regime requires the additional assumption (H2), concerning dependence between noise and random-tree cell connections.
- Sparsity adaptation: Proposition 1 shows that, with high probability, the first k splits asymptotically occur along the S informative variables when the model is sparse and mtry = p.Here S < p denotes the unknown number of informative variables, while the remaining variables are assumed uninformative.
4. Discussion.
The discussion explains how the analysis controls approximation and estimation errors for data-dependent random-forest trees, establishing consistency in two regimes while identifying scope limitations.
- The analysis is difficult because random-forest partitions depend on both predictors and responses, unlike Y-independent partitioning analyses.This dependence complicates direct use of standard local-averaging consistency arguments.
- Small regression-function variation within random-tree cells provides control of the forest’s approximation error.Proposition 2 supplies this control as the sample size grows.
- The estimation error requires separate treatment: tree depth controls regime 1, whereas subsampling controls connection probabilities and tree diversity in fully grown regime 2.In regime 2, the condition a_n log n/n → 0 limits repeated connections between a query point and individual observations.
- The fully grown-tree result relies on assumption (H2), whose validity is not known in complete generality.The theorem nevertheless closely mimics the algorithm used in practice.
- Despite inconsistent individual trees with one observation per leaf, aggregating their rough predictions yields a provably consistent architecture.The discussion contrasts this with standard tree-consistency conditions requiring terminal-node counts to grow.
- The results establish L2 consistency but do not directly imply pointwise consistency, especially near domain edges where cell diameters lack local control.The paper notes that forests may be inconsistent at some fixed points while remaining L2 consistent.
5. Proof of Theorems 1 and 2.
The proofs introduce theoretical and empirical random-forest constructions, establish that their cuts and cellwise behavior are close, and then verify partition-complexity conditions for consistency.
- Proof setup: The analysis defines possible cut sequences and cells containing x, then measures proximity between alternative sequences of cuts.The theoretical and empirical cells are constructed from consecutive cuts, with notation distinguishing their cut tuples and resulting regions.
- Theoretical forest: The empirical split criterion is compared with a sample-independent theoretical criterion, whose optimizer defines the theoretical random forest.The empirical criterion converges almost surely to its theoretical counterpart for every cut, motivating the comparison.
- Proposition 2: The resulting cellwise approximation error tends to zero, completing the proof of Proposition 2.The argument combines the bounds for theoretical-cell variation and the distance between corresponding cut sequences.
- Theorem 1: For the consistency theorem, the proof uses achievable partitions, their terminal-node complexity, partitioning numbers, truncation, and piecewise-constant tree estimates.The truncated estimate belongs to the class of functions piecewise constant on the data-dependent partition, allowing the auxiliary theorem to control approximation and estimation errors.
- Theorem 1: The auxiliary theorem separates approximation and estimation control for the truncated random-forest estimate under its stated conditions.The proof checks the theorem’s statements (i)–(iii), with statements (ii) and (iii) controlling approximation and estimation error, respectively.
approximation error.
The approximation-error argument bounds the target function by a cellwise constant approximation and invokes Proposition 2 to obtain convergence.
- approximation error: The proof fixes ξ > 0 and sets the truncation level using the boundedness of m and the noise scale.The truncation level is chosen as βn = ∥m∥∞ plus a term involving σ and log an.
- approximation error: The approximation is formed by assigning each cell A the value m(zA) at an arbitrary point zA ∈ A, and Proposition 2 then supplies the convergence bound.The resulting approximation-error control is stated for all sufficiently large n.
- approximation error: Because m is bounded, βn eventually exceeds ∥m∥∞, so truncation does not alter the relevant bounded target values.This condition is used for all sufficiently large n.
Estimation error.
The estimation-error proof verifies the auxiliary theorem’s complexity and tail conditions for the truncated estimate using the fixed number of terminal nodes per tree.
- Estimation error: The proof begins by fixing L > 0 and establishing statement (iii) for all sufficiently large n satisfying L < βn.This is one of the conditions required by the auxiliary consistency theorem.
- Estimation error: Each tree has exactly tn terminal nodes, so the maximal terminal-node count of the achievable partition class equals tn.This identity is used in the complexity calculations.
- Estimation error: The remaining bounds follow from the stated assumptions and yield the required estimation-error condition for sufficiently large n.The passage sequence records the assumption-based conclusion and its use with Theorem 3.
Untruncated estimate.
The proof controls the nontruncated estimate by decomposing its error into approximation and estimation terms, using Gaussian-noise bounds and a layered-nearest-neighbor argument.
- Untruncated estimate: After establishing consistency for the truncated estimate, the proof reduces completion of Theorem 1 to consistency of the nontruncated random-forest estimate.The subsequent argument separately bounds approximation and estimation contributions.
- Untruncated estimate: The approximation and estimation bounds converge to zero under the assumptions, completing the proof of Theorem 1.The estimation argument uses Gaussian tail control for the maximum of n χ2-squared random variables.
- Untruncated estimate: The estimation error is decomposed into terms In and Jn, with Jn treated as approximation error and In as estimation error.The decomposition is written as 2In + 2Jn.
- Untruncated estimate: A data point connects to a random point when it is selected by subsampling and no other data point lies in the hyperrectangle between them; such points are layered nearest neighbors.This geometric characterization is the key argument for the (H2.1) case.
Supplement to “Consistency of random forests”
This supplement contains proofs of the paper’s technical results.
- The supplement provides proofs for the paper’s technical results.
- The material is presented as a PDF supplement identified by DOI 10.1214/15-AOS1321SUPP.
- Its content is supplementary rather than a standalone statement of the paper’s results.