Sharp Analysis of a Simple Model for Random Forests
Sharp Analysis of a Simple Model for Random Forests
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Jason M. Klusowski
中科院分区：
文献类型：
--
作者：
Jason M. Klusowski
自Leo Breiman于2001年创立以来，随机森林已经成为提高回归和分类问题准确性的重要工具。在本文中，我们重新审视了一个历史上重要的随机森林模型，最初由Breiman在2004年提出，后来由G\'erard Biau在2012年研究，其中一个功能是随机选择的，分裂发生在节点的中点沿着所选择的功能。如果回归函数是Lipschitz，并且只依赖于$ d $特征中的一小部分S $，我们证明了，给定$ n $个观测值和适当调整的分裂概率，均方预测误差为$ O（（n（\log n）^{（S-1）/2}）^{-\frac{1}{S\log2+1}}）$。这肯定地回答了一个悬而未决的问题Biau的收敛速度是否可以提高这个随机森林模型。此外，通过对线性模型的近似和估计误差的精细分析，我们表明，这个速度一般不能提高。最后，我们推广我们的分析，并提高现有的预测误差界的另一个随机森林模型，其中每棵树是从二次采样数据和分裂进行经验中位数沿着选定的功能。
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\'erard 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.