Estimating the algorithmic variance of randomized ensembles via the bootstrap

研究问题: 在训练数据固定时，如何量化分类集成方法自身随机性造成的预测误差波动，并判断集成规模是否足以使该波动可忽略？
方法与思路: 作者对 bagging、随机森林等分类集成提出 bootstrap 算法方差估计，在一阶模型下分析误差中心化分布，并通过外推降低计算成本。
材料陈述的贡献: 摘要称，随着集成规模增大，所提方法可一致近似预测误差的中心化分布，并为判断算法波动何时可忽略提供实践指引。
阅读关注点: 应核对随机集成的一阶模型、重抽样单位、外推的有效条件，以及算法方差与训练样本不确定性、整体预测误差的区别。
阅读边界: 仅据版本未注明的 OpenAlex 索引摘要；结论条件于固定训练集，且限于所述分类模型，不能据此判断总体泛化误差或收益预测表现。

GPT-6.1 Sol · 高 · 2026-10-05

原文摘要

Although the methods of bagging and random forests are some of the most widely used prediction methods, relatively little is known about their algorithmic convergence. In particular, there are not many theoretical guarantees for deciding when an ensemble is “large enough”—so that its accuracy is close to that of an ideal infinite ensemble. Due to the fact that bagging and random forests are randomized algorithms, the choice of ensemble size is closely related to the notion of “algorithmic variance” (i.e., the variance of prediction error due only to the training algorithm). In the present work, we propose a bootstrap method to estimate this variance for bagging, random forests and related methods in the context of classification. To be specific, suppose the training dataset is fixed, and let the random variable $\mathrm{ERR}_{t}$ denote the prediction error of a randomized ensemble of size $t$ . Working under a “first-order model” for randomized ensembles, we prove that the centered law of $\mathrm{ERR}_{t}$ can be consistently approximated via the proposed method as $t\to\infty$ . Meanwhile, the computational cost of the method is quite modest, by virtue of an extrapolation technique. As a consequence, the method offers a practical guideline for deciding when the algorithmic fluctuations of $\mathrm{ERR}_{t}$ are negligible.Although the methods of bagging and random forests are some of the most widely used prediction methods, relatively little is known about their algorithmic convergence. In particular, there are not many theoretical guarantees for deciding when an ensemble is “large enough”—so that its accuracy is close to that of an ideal infinite ensemble. Due to the fact that bagging and random forests are randomized algorithms, the choice of ensemble size is closely related to the notion of “algorithmic variance” (i.e., the variance of prediction error due only to the training algorithm). In the present work, we propose a bootstrap method to estimate this variance for bagging, random forests and related methods in the context of classification. To be specific, suppose the training dataset is fixed, and let the random variable $\mathrm{ERR}_{t}$ denote the prediction error of a randomized ensemble of size $t$. Working under a “first-order model” for randomized ensembles, we prove that the centered law of $\mathrm{ERR}_{t}$ can be consistently approximated via the proposed method as $t\to\infty$. Meanwhile, the computational cost of the method is quite modest, by virtue of an extrapolation technique. As a consequence, the method offers a practical guideline for deciding when the algorithmic fluctuations of $\mathrm{ERR}_{t}$ are negligible.

摘要来源：OpenAlex 索引摘要（稿件版本未注明）

笔记与分组

分类依据与纠错

Estimating the algorithmic variance of randomized ensembles via the bootstrap

代码、数据与补充材料

用 Bootstrap 估计随机集成方法的算法方差

原文摘要

同方向的基础文献

同方向的基础文献