Consistency of random forests

Abstract

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

References in corpus (5)

• Random survival forests
• Analysis of a Random Forests Model
• Consistency of Online Random Forests
• Asymptotic Theory for Random Forests
• On the asymptotics of random forests

Cited by in corpus (79)

• Correlation and variable importance in random forests
• Meta-learners for Estimating Heterogeneous Treatment Effects using Machine Learning
• Unbiased split variable selection for random survival forests using maximally selected rank statistics
• Adaptive Concentration of Regression Trees, with Application to Random Forests
• High-dimensional regression adjustments in randomized experiments
• A Debiased MDI Feature Importance Measure for Random Forests
• Interpretable Random Forests via Rule Extraction
• Flexible domain prediction using mixed effects random forests
• Combining Static and Dynamic Features for Multivariate Sequence Classification
• Optimized ensemble deep learning framework for scalable forecasting of dynamics containing extreme events
• Selective inference for effect modification via the lasso
• Trees, forests, and impurity-based variable importance
• A novel distribution-free hybrid regression model for manufacturing process efficiency improvement
• Making Sense of Random Forest Probabilities: a Kernel Perspective
• Randomization as Regularization: A Degrees of Freedom Explanation for Random Forest Success
• Fast Linear Model Trees by PILOT
• Scalable and Efficient Hypothesis Testing with Random Forests
• Estimation and Inference with Trees and Forests in High Dimensions
• Getting Better from Worse: Augmented Bagging and a Cautionary Tale of Variable Importance
• Unbiased Measurement of Feature Importance in Tree-Based Methods
• SHAFF: Fast and consistent SHApley eFfect estimates via random Forests
• Provable Boolean Interaction Recovery from Tree Ensemble obtained via Random Forests
• The Implicit Regularization of Ordinary Least Squares Ensembles
• Consistency of survival tree and forest models: splitting bias and correction
• CyPhERS: A Cyber-Physical Event Reasoning System providing real-time situational awareness for attack and fault response
• Imputation procedures in surveys using nonparametric and machine learning methods: an empirical comparison
• One Class Splitting Criteria for Random Forests
• Asymptotic Distributions and Rates of Convergence for Random Forests via Generalized U-statistics
• Stochastic tree ensembles for regularized nonlinear regression
• Regression-Enhanced Random Forests
• A Unified Framework for Random Forest Prediction Error Estimation
• Sharp Analysis of a Simple Model for Random Forests
• Transformation Forests
• Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
• Impact of subsampling and pruning on random forests
• Asymptotic Properties of High-Dimensional Random Forests
• Extrapolated cross-validation for randomized ensembles
• On the asymptotics of random forests
• Interpretable Classification of Bacterial Raman Spectra with Knockoff Wavelets
• $V$-statistics and Variance Estimation
• Random Forests for dependent data
• A Practically Competitive and Provably Consistent Algorithm for Uplift Modeling
• GrCAN: Gradient Boost Convolutional Autoencoder with Neural Decision Forest
• Model-assisted estimation through random forests in finite population sampling
• Achieving Reliable Causal Inference with Data-Mined Variables: A Random Forest Approach to the Measurement Error Problem
• Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
• A Numerical Transform of Random Forest Regressors corrects Systematically-Biased Predictions
• A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds
• Semi-Supervised Off Policy Reinforcement Learning
• Subsampling Winner Algorithm for Feature Selection in Large Regression Data
• On the use of Harrell's C for clinical risk prediction via random survival forests
• Random forests and kernel methods
• Reliable ABC model choice via random forests
• Causal survival embeddings: non-parametric counterfactual inference under censoring
• Ensemble Learning with Statistical and Structural Models
• Best-scored Random Forest Classification
• Estimating the Algorithmic Variance of Randomized Ensembles via the Bootstrap
• Adaptive Conformal Prediction by Reweighting Nonconformity Score
• WildWood: a new Random Forest algorithm
• Nonparametric Variable Screening with Optimal Decision Stumps
• Classification Trees for Imbalanced and Sparse Data: Surface-to-Volume Regularization
• Building Trees for Probabilistic Prediction via Scoring Rules
• On the Consistency of a Random Forest Algorithm in the Presence of Missing Entries
• Random Planted Forest: a directly interpretable tree ensemble
• Two-stage Best-scored Random Forest for Large-scale Regression
• Consistent Sufficient Explanations and Minimal Local Rules for explaining regression and classification models
• Computing Affine Combinations, Distances, and Correlations for Recursive Partition Functions
• MMD-based Variable Importance for Distributional Random Forest
• Wasserstein Random Forests and Applications in Heterogeneous Treatment Effects
• Censored Quantile Regression Forests
• Bridging Breiman's Brook: From Algorithmic Modeling to Statistical Learning
• Comments on Leo Breiman's paper 'Statistical Modeling: The Two Cultures' (Statistical Science, 2001, 16(3), 199-231)
• Estimating a sharp convergence bound for randomized ensembles
• Robust Similarity and Distance Learning via Decision Forests
• Modelling and Analysing Behaviours and Emotions via Complex User Interactions
• Prospective Learning in Retrospect
• Asymptotic Unbiasedness of the Permutation Importance Measure in Random Forest Models
• Sparse nearest neighbor Cholesky matrices in spatial statistics
• Modelling hetegeneous treatment effects by quantitle local polynomial decision tree and forest