Source-linked AI summary
A Random Forest Guided Tour
Gérard Biau, Erwan Scornet
TL;DR
Random forests remain difficult to analyze despite strong practical performance, leaving a gap between theoretical understanding and observed behavior. This review surveys the theory and methodology behind the algorithm, including parameter selection, resampling, and variable importance, and concludes that existing results do not yet explain its behavior in full generality.
Problem
Random forests’ complex, data-dependent mechanisms leave their mathematical properties insufficiently understood despite widespread practical use.
Method
The paper provides a guided theoretical survey of random forests, emphasizing their mathematical foundations, resampling mechanism, parameter selection, and variable importance.
Results
The review synthesizes recent theoretical and methodological results on random forests, including variable-importance decompositions based on conditional information.
Takeaways & Limitations
Current theory offers insights into random forests but does not yet fully explain their remarkable behavior across general settings.
Takeaways & Limitations
Existing results remain insufficient to explain random forests’ behavior in full generality, including patterns beyond standard sparsity or smoothness conditions.
Abstract
from arXiv · showhide
The random forest algorithm, proposed by L. Breiman in 2001, has been extremely successful as a general-purpose classification and regression method. The approach, which combines several randomized decision trees and aggregates their predictions by averaging, has shown excellent performance in settings where the number of variables is much larger than the number of observations. Moreover, it is versatile enough to be applied to large-scale problems, is easily adapted to various ad-hoc learning tasks, and returns measures of variable importance. The present article reviews the most recent theoretical and methodological developments for random forests. Emphasis is placed on the mathematical forces driving the algorithm, with special attention given to the selection of parameters, the resampling mechanism, and variable importance measures. This review is intended to provide non-experts easy access to the main ideas.
1 Introduction
Random forests combine randomized tree predictors through a divide-and-conquer aggregation strategy and are widely valued for accurate, flexible, scalable prediction. This survey introduces the algorithm and reviews the theoretical and methodological challenges underlying its practical success.
- Method: Random forests sample fractions of the data, grow randomized tree predictors, and aggregate their predictions.This divide-and-conquer procedure was devised by Breiman in the early 2000s, building on earlier work by Amit and Geman, Ho, and Dietterich.
- Strengths: Their popularity reflects broad applicability, few tuning parameters, accuracy, high-dimensional capability, and parallelizability.The method is also recognized for handling small sample sizes and potentially large real-life systems.
- Applications: Random forests have been successfully applied to air quality prediction, chemoinformatics, ecology, 3D object recognition, and bioinformatics.These examples illustrate the method’s involvement in varied practical prediction problems.
- Theory: Theoretical understanding remains less conclusive, with Breiman’s upper bound relating forest generalization error to tree correlation and strength.Subsequent work analyzes more elaborate models and moves closer to practical random forests.
- Theory: Rigorous analysis is difficult because random forests combine bagging and CART splitting, so theory often studies simplified procedures.The survey provides a guided tour of major theoretical approaches while discussing their inherent pros and cons.
2 The random forest estimate
This section defines Breiman’s random forest as an ensemble of randomized regression trees, focusing on nonparametric regression and the mechanisms that generate and aggregate the trees. It explains finite and infinite forests, randomized resampling and splitting, CART-based predictions, and the principal construction parameters.
- Scope and definition: The survey uses “random forests” to mean Breiman’s (2001) original algorithm rather than generic aggregation of randomized decision trees.The introduction focuses on regression, while noting that forests also handle supervised classification.
- Forest estimate: A random forest averages predictions from M randomized regression trees whose random parameters are independent and identically distributed and independent of the training data.Randomness resamples training observations and selects directions for successive splits.
- Forest estimate: M = 500 is the randomForest package default, while the infinite forest replaces finite averaging with expectation over the random parameter Θ.The M →∞ operation is justified conditionally on the training data by the law of large numbers.
- Tree construction: Each tree resamples observations, then repeatedly splits hyperrectangular cells by maximizing the CART criterion over mtry uniformly selected coordinates, stopping at the specified cell-size rule.The terminal cells partition the input space, and each tree predicts by averaging responses in the query point’s terminal cell.
- Tree construction: The three construction parameters are an, mtry, and nodesize; regression defaults are an = n, mtry = ⌈p/3⌉, and nodesize = 5.They control the number of sampled observations, candidate split directions, and the minimum cell size for splitting.
- Forest estimate: As M grows, the forest’s variance decreases, and choosing a large number of trees does not lead to overfitting.The passage links larger forests to more accurate predictions.
3 Simplified models and local averaging estimates
Because standard random forests are difficult to analyze, theory often studies simplified, non-adaptive models. These models establish consistency, sparse-dimension adaptation, error reduction through averaging, and connections to local-neighbor methods.
- Simplified models: Theoretical work often replaces the data-dependent random forest with simplified or stylized models whose mathematical analysis is more tractable.This reflects a gap between theoretical understanding and the practical performance of standard forests.
- Purely random forests: Centered forests are consistent for classification and regression when k →∞ and n/2^k →∞.For uniformly distributed X, terminal nodes contain on average about n/2^k data points; k ≈ log n is a natural choice discussed in the analysis.
- Sparse models: The convergence rate depends on the number |S| of strong variables rather than the ambient dimension p, and is strictly faster than n^-2/(p+2) when |S| ≤⌊0.54p⌋.Thus, under the sparse representation assumption, the forest estimate adapts to the intrinsic dimension |S|.
- Averaging and error: Tree averaging can make estimation error vanish at the slow rate 1/log n even when each centered-forest tree is fully grown.However, k ≈ log n is too large for consistency because the corresponding forest’s approximation error remains constant.
- Local averaging: For trees without resampling and with one observation per leaf, the forest estimate is a weighted average of responses whose predictors are layered nearest neighbors of x.The weights are nonnegative and sum to one, linking simplified forests to local averaging, although the original forest’s exact weights remain unknown.
4 Theory for Breiman’s forests
Theory for Breiman’s forests analyzes resampling and splitting separately because the full algorithm depends on the entire sample. Results establish consistency, optimal convergence, sparsity adaptation, and asymptotic normality under varying assumptions, while leaving bootstrap and unpruned CART behavior incompletely understood.
- Resampling: Breiman’s forests use bootstrap resampling—n draws with replacement from n observations—and average predictors through bagging.The bootstrap sample can differ structurally from the original sample because observations may be duplicated.
- Resampling: The bootstrap’s role remains poorly understood because most theoretical analyses replace it with subsampling without replacement, excluding the bootstrap regime.These analyses typically assume the subsampling rate a_n/n tends to zero at a prescribed rate.
- Resampling: Subbagging makes 1-nearest-neighbor regression universally mean squared consistent when a_n →∞ and a_n/n →0.The subbagged estimator is a local averaging estimate with resampling-based nearest-neighbor weights.
- Resampling: Subbagged nearest-neighbor estimation achieves optimal convergence rates over Lipschitz smoothness classes whether resampling uses replacement or not.This connects bagging theory to nearest-neighbor estimation beyond the specific bootstrap mechanism.
- Splitting: Random forests asymptotically split with high probability along the S informative variables, explaining their adaptation to sparse settings.The result makes the procedure behave as if data were projected onto the space spanned by informative variables.
- Whole-algorithm theory: Consistency and asymptotic normality have been proved for simplified forests using subsampling, while finite-forest normality requires a_n = o(√n) and n/M_n → 0.The infinitesimal jackknife consistently estimates the variance of Breiman’s infinite forests, whereas unpruned consistency relies on a difficult CART conjecture.
5 Variable importance
Random forests assess variable importance mainly through impurity reduction and out-of-bag accuracy changes. Theoretical results clarify how these measures relate to conditional information, irrelevant variables, and correlated features, while empirical studies identify correlation as a limitation for MDA.
- Core importance measures: MDI averages each variable’s weighted impurity decrease over all trees, whereas MDA averages the change in out-of-bag error after permuting that variable.MDI is based on splits using the variable; MDA compares out-of-bag performance before and after permutation.
- Theoretical interpretation: For totally randomized, fully developed trees, the total information I(X(1), . . . , X(p); Y ) decomposes into the importances of individual variables.Each importance can be expressed using conditional mutual information between a variable and the output given subsets of the other variables.
- Theoretical interpretation: A variable is irrelevant with respect to V exactly when its theoretical MDI⋆ equals 0, and adding an irrelevant variable does not change other single-tree importances.Irrelevance is defined by zero conditional mutual information with the output given the relevant variable set.
- Correlation effects: In the Gaussian correlated-feature setting, variable importance decreases as the inverse of the square of p as the number of correlated variables increases.The result assumes equal feature-output covariances and an equicorrelated feature covariance matrix.
- Correlation effects: Empirical studies report that increasing correlation among features makes MDA less able to detect the most relevant variables.Multiple studies have emphasized the negative effect of correlated variables on MDA performance.
6 Extensions
Random forests have been extended beyond standard offline prediction to weighted, online, survival, ranking, clustering, quantile, missing-data, one-class, and imbalanced-data settings. These extensions modify aggregation, training, or outputs to address specialized data structures and learning tasks.
- Weighted forests: Weighted forests assign tree-level weights to emphasize more accurate trees, while related methods guide tree construction so trees complement one another.These approaches alter prediction aggregation or resampling and randomization during tree building.
- Online forests: Online forests incorporate data generated over time without requiring the entire training set to be accessible at once.They adapt random forests to streaming settings where observations must be incorporated quickly.
- Survival forests: Random forests have been extended to survival analysis, where incomplete and right-censored duration data and nonlinear effects are important.Ishwaran et al. (2008) proved consistency for a survival-forest extension.
- Ranking forests: Ranking Forests address ranking problems using nonparametric scoring and ROC-curve optimization under the AUC criterion.The method is based on ranking trees.
- Clustering forests: Cluster Forests probe high-dimensional data clouds for local clusterings and aggregate them with spectral clustering to assign clusters across the data set.A cluster-quality measure guides the search, and local clusterings are progressively improved in a tree-growth-like fashion.
- Additional extensions: Other extensions use random forests for quantile estimation, missing-value imputation, one-class classification, medical-image segmentation, and unbalanced data through majority-class down-sampling.Quantile forests estimate the full conditional response distribution; missing values can be estimated from the proximity matrix.
7 Conclusion and perspectives
The review argues that forests’ core principles can support efficient learning for massive, high-dimensional data, while important theoretical questions about their behavior and tuning remain unresolved. It also suggests that tree aggregation may represent highly complex patterns through exponentially many leaf-region intersections.
- The review provides an overview of recent random-forest literature and considers how new and emerging fields are impacting the method.The authors present the article as an accessible overview for non-experts.
- Forest principles—divide and conquer, resampling, aggregation, and random feature-space search—may support computationally efficient algorithms for massive, high-dimensional data.The authors view these principles as simple but fundamental ideas that could leverage state-of-the-art algorithms.
- Existing results do not fully explain random forests’ remarkable behavior or the complex patterns they estimate beyond standard sparsity and smoothness conditions.The authors argue that these patterns remain to be discovered, quantified, and mathematically described.
- Random forests can discriminate among a very large number of regions because leaf-region intersections may be exponential in the number of trees.The tuple of leaf identities across trees can represent a considerable quantity of possible patterns.
- Bootstrap resampling with an = n points selected with replacement performs well empirically, but no theory currently supports this default choice.The preliminary resampling size remains a critical tuning issue.