Sharp Analysis of a Simple Model for Random Forests

Abstract

Random forests have become an important tool for improving accuracy in regression and classification problems since their inception by Leo Breiman in 2001. In this paper, we revisit a historically important random forest model originally proposed by Breiman in 2004 and later studied by Gérard Biau in 2012, where a feature is selected at random and the splits occurs at the midpoint of the node along the chosen feature. If the regression function is Lipschitz and depends only on a small subset of $S$ out of $d$ features, we show that, given access to $n$ observations and properly tuned split probabilities, the mean-squared prediction error is $O((n(\log n{)}^{(S-1)/2}{)}^{-\frac{1}{S\log 2+1}})$. This positively answers an outstanding question of Biau about whether the rate of convergence for this random forest model could be improved. Furthermore, by a refined analysis of the approximation and estimation errors for linear models, we show that this rate cannot be improved in general. Finally, we generalize our analysis and improve extant prediction error bounds for another random forest model in which each tree is constructed from subsampled data and the splits are performed at the empirical median along a chosen feature.

References in corpus (3)

• A Debiased MDI Feature Importance Measure for Random Forests
• Analysis of purely random forests bias
• Risk bounds for purely uniformly random forests

Cited by in corpus (6)

• The ASAS-SN Catalog of Variable Stars II: Uniform Classification of 412,000 Known Variables
• Randomization as Regularization: A Degrees of Freedom Explanation for Random Forest Success
• Getting Better from Worse: Augmented Bagging and a Cautionary Tale of Variable Importance
• Asymptotic Properties of High-Dimensional Random Forests
• On Ensembling vs Merging: Least Squares and Random Forests under Covariate Shift
• Is interpolation benign for random forest regression?