AdaBoost 训练误差界 | Codeboy's Blog

形式陈述

以下结论沿用AdaBoost的加权分布、系数与 score 定义。

设 $m\ge1$ ，训练集为 $(x_i,y_i)_{i=1}^m$ ， $y_i\in\{-1,+1\}$ 。AdaBoost 第 $t$ 轮在分布 $D_t$ 下选择弱分类器 $h_t\in\{-1,+1\}^{\mathcal X}$ ，加权错误率

0<\varepsilon_t=\Pr_{i\sim D_t}[h_t(x_i)\ne y_i]<\frac12,

并取

\alpha_t=\frac12\log\frac{1-\varepsilon_t}{\varepsilon_t}, \qquad F_T(x)=\sum_{t=1}^T\alpha_th_t(x).

则最终分类器 $\operatorname{sign}F_T$ 的训练错误率满足

\widehat R_S^{0\text{-}1}(F_T) \le\prod_{t=1}^TZ_t =\prod_{t=1}^T2\sqrt{\varepsilon_t(1-\varepsilon_t)}.

若写 $\varepsilon_t=\frac12-\gamma_t$ ，则

\widehat R_S^{0\text{-}1}(F_T) \le\exp\!\left(-2\sum_{t=1}^T\gamma_t^2\right).

这些公式针对 $T\ge1$ 个有限系数的有效轮；若某轮错误为零，按算法返回该完美规则，训练错误直接为零。特别地，每轮优势至少 $0<\gamma<1/2$ 时，对目标 $0<\varepsilon<1$ ，取整数 $T\ge\lceil\log(1/\varepsilon)/(2\gamma^2)\rceil$ 足以把训练错误控制到至多 $\varepsilon$ 。

归一化常数为何连成指数损失

AdaBoost 更新为

D_{t+1}(i)=\frac{D_t(i)e^{-\alpha_ty_ih_t(x_i)}}{Z_t}, \qquad Z_t=\sum_iD_t(i)e^{-\alpha_ty_ih_t(x_i)}.

从 $D_1(i)=1/m$ 迭代展开，

D_{T+1}(i) =\frac{m^{-1}e^{-y_iF_T(x_i)}}{\prod_tZ_t}.

对 $i$ 求和并用 $\sum_iD_{T+1}(i)=1$ ，得到经验指数损失的精确分解

\frac1m\sum_{i=1}^me^{-y_iF_T(x_i)}=\prod_{t=1}^TZ_t.

固定 $\operatorname{sign}(0)=+1$ 。误分类时 $y_iF_T(x_i)\le0$ ；将所有零 margin 也计入只会增大错误上界，于是 $\mathbf 1[y_iF_T(x_i)\le0]\le e^{-y_iF_T(x_i)}$ ；训练零一错误便被指数损失控制。

每轮最优系数与弱优势

由于 $y_ih_t(x_i)$ 只取 $\pm1$ ，

Z_t=(1-\varepsilon_t)e^{-\alpha_t}+\varepsilon_te^{\alpha_t}.

对 $\alpha_t$ 求极小，得到所用的 $\frac12\log((1-\varepsilon_t)/\varepsilon_t)$ ，并有 $Z_t=2\sqrt{\varepsilon_t(1-\varepsilon_t)}$ 。代入 $\varepsilon_t=1/2-\gamma_t$ ，

Z_t=\sqrt{1-4\gamma_t^2}\le e^{-2\gamma_t^2},

最后一步来自 $\log(1-x)\le-x$ 。因此指数下降不是一句“弱分类器叠加会变强”的口号，而是每轮对同一个指数势函数取得固定乘法收缩。

直觉

每轮弱优势不是被简单相加，而是让同一个指数势函数乘上小于一的归一化因子。连续相乘转成优势平方和的指数衰减，因此目标训练错误只需对数轮数；若某轮没有正优势，势函数便不再收缩。

例子与边界

固定弱优势的轮数

若弱学习器无论样本权重怎样重排都能保持优势 $\gamma$ ，每轮让训练指数损失最多乘 $e^{-2\gamma^2}$ 。要再减少一个十进制数量级，只需追加 $\log 10/(2\gamma^2)$ 轮，与当前已迭代多少轮无关。这种几何衰减解释了 weak-to-strong 归约为何只需对目标误差取对数轮数。

适用边界

$\varepsilon_t$ 必须按当前 $D_t$ 计算；普通未加权训练错误不能代替它。若 $\varepsilon_t=1/2$ ，则 $\alpha_t=0$ ，这一轮没有进展；若大于 $1/2$ ，二元分类时可翻转弱分类器，若假设类或输出协议不允许翻转，则弱学习条件已经失败。

本定理只控制给定训练集。训练错误为零不意味着测试风险为零，噪声和异常点还可能让权重集中到少数不可拟合样本。训练后继续迭代的泛化现象需要 Boosting 的间隔理论或其他复杂度分析，不能把上式直接称为 PAC 界。

推论与应用

固定优势 $\gamma$ 给出 $O(\gamma^{-2}\log(1/\varepsilon))$ 的 boosting 轮数，这正是弱到强归约的定量核心。优势随轮次变化时，真正累积的是 $\sum_t\gamma_t^2$ ，少数很强的轮次与许多微弱轮次可以产生不同收缩轨迹。

间隔理论进一步研究 score 的归一化分布，而非仅问训练符号是否正确；噪声数据上则需把异常点权重集中与早停策略单独分析。训练错误界本身不提供这些样本外保证。

参考资料

Yoav Freund and Robert Schapire, “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting,” 1997.
Robert E. Schapire and Yoav Freund, Boosting: Foundations and Algorithms, MIT Press, 2012, Chapter 2.

形式陈述 ​

归一化常数为何连成指数损失 ​

每轮最优系数与弱优势 ​

固定弱优势的轮数 ​

适用边界 ​

反向链接

形式陈述

归一化常数为何连成指数损失

每轮最优系数与弱优势

固定弱优势的轮数

适用边界