AdaBoost 训练误差界

结论 ​

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

$${\epsilon }_t={\text{Pr}}_{i\sim D_t}[h_t(x_i)\ne y_i]<\frac{1}{2},$$

并取

$${\alpha }_t=\frac{1}{2}\log \frac{1-{\epsilon }_t}{{\epsilon }_t},F_T(x)=\sum _{t=1}^T{\alpha }_t{h}_t(x).$$

则最终分类器 $\mathrm{sign}{F}_T$ 的训练错误率满足

$${\hat{R}}_S^{0\text{-}1}(F_T)\le \prod _{t=1}^T{Z}_t=\prod _{t=1}^{T}2\sqrt{{\epsilon }_t(1-{\epsilon }_t)}.$$

若写 ${\epsilon }_t=\frac{1}{2}-{\gamma }_t$，则

$${\hat{R}}_S^{0\text{-}1}(F_T)\le \exp (-2\sum _{t=1}^T{\gamma }_t^2).$$

特别地，每轮优势至少 $\gamma >0$ 时，$T\ge \log \left(1/\epsilon \right)/(2{\gamma }^2)$ 足以把训练错误压到 $\epsilon$ 以下。

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

AdaBoost 更新为

$$D_{t+1}(i)=\frac{D_t(i)e^{-{\alpha }_t{y}_i{h}_t(x_i)}}{Z_t},Z_t=\sum _i{D}_t(i)e^{-{\alpha }_t{y}_i{h}_t(x_i)}.$$

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

$$D_{T+1}(i)=\frac{m^{-1}{e}^{-y_i{F}_T(x_i)}}{\prod _t{Z}_t}.$$

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

$$\frac{1}{m}\sum _{i=1}^m{e}^{-y_i{F}_T(x_i)}=\prod _{t=1}^T{Z}_t.$$

误分类时 $y_i{F}_T(x_i)\le 0$，于是 $\mathbf{1}[y_i{F}_T(x_i)\le 0]\le e^{-y_i{F}_T(x_i)}$；训练零一错误便被指数损失控制。

每轮最优系数与弱优势 ​

由于 $y_i{h}_t(x_i)$ 只取 $\pm 1$，

$$Z_t=(1-{\epsilon }_t)e^{-{\alpha }_t}+{\epsilon }_t{e}^{{\alpha }_t}.$$

对 ${\alpha }_t$ 求极小，得到所用的 $\frac{1}{2}\log ((1-{\epsilon }_t)/{\epsilon }_t)$，并有 $Z_t=2\sqrt{{\epsilon }_t(1-{\epsilon }_t)}$。代入 ${\epsilon }_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 归约为何只需对目标误差取对数轮数。

适用边界 ​

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

本定理只控制给定训练集。训练错误为零不意味着测试风险为零，噪声和异常点还可能让权重集中到少数不可拟合样本。训练后继续迭代的泛化现象需要 Boosting 的间隔理论公理库Boosting 的间隔理论Boosting margin theory · Boosting margin bound用加权投票的归一化训练间隔分布和基分类器复杂度控制总体分类错误，而不直接依赖 boosting 轮数。或其他复杂度分析，不能把上式直接称为 PAC 界。

参考资料

• 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.