Sharp Analysis of a Simple Model for Random Forests
This provides theoretical guarantees for random forests, addressing a long-standing problem in machine learning theory, but it is incremental as it builds on prior models.
The paper tackles the problem of analyzing a simple random forest model's prediction error, showing that with Lipschitz regression functions depending on a small feature subset, the mean-squared error is O((n(log n)^(S-1)/2)^{-1/(S log2+1)}), answering an open question and proving this rate is optimal.
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\log2+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.