AdaBoost 算法

算法 ​

训练集为 $(x_i,y_i{)}_{i=1}^m$，标签 $y_i\in \{-1,+1\}$。初始化 $D_1(i)=1/m$。第 $t$ 轮用分布 $D_t$ 训练弱分类器 $h_t:\mathcal{X}\to \{-1,+1\}$，计算

$${\epsilon }_t=\sum _i{D}_t(i)\mathbf{1}[h_t(x_i)\ne y_i],{\alpha }_t=\frac{1}{2}\log \frac{1-{\epsilon }_t}{{\epsilon }_t},$$

并更新

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

其中 $Z_t$ 是使权重和为 $1$ 的归一化常数。最终输出

$$H(x)=\mathrm{sign}\sum _{t=1}^T{\alpha }_t{h}_t(x).$$

权重变化的含义 ​

正确分类时 $y_i{h}_t(x_i)=1$，权重乘 $e^{-{\alpha }_t}$；误分类时该乘积为 $-1$，权重乘 $e^{{\alpha }_t}$。归一化后，下一轮更重视当前组合的困难点。若 ${\epsilon }_t<1/2$，则 ${\alpha }_t>0$；当 ${\epsilon }_t=1/2$ 时该分类器没有贡献；大于 $1/2$ 时弱学习条件失效，通常应翻转分类器或停止，而不是照搬正系数解释。

指数损失推导 ​

令加法 score $F_T(x)=\sum _t{\alpha }_t{h}_t(x)$。经验指数损失为

$$\frac{1}{m}\sum _i{e}^{-y_i{F}_T(x_i)}.$$

按上述更新展开可得它等于 $\prod _{t=1}^T{Z}_t$。对固定 $h_t$，最小化 $Z_t=(1-{\epsilon }_t)e^{-\alpha }+{\epsilon }_t{e}^{\alpha }$ 得到给定的 ${\alpha }_t$，且最小值 $2\sqrt{{\epsilon }_t(1-{\epsilon }_t)}$。又因为误分类时 $e^{-y_i{F}_T(x_i)}\ge 1$，训练错误率不超过这组归一化常数的乘积。

具体过程与边界 ​

在含少量几何上困难点的二维样本中，第一棵决策桩会分对大多数点；误分点权重上升后，第二棵桩沿另一坐标切分，最终加权 score 综合两条边界。若困难点实际是错标异常值，权重也会持续集中到它们上面，导致对噪声敏感；这不是算法必然“自动忽略异常”的场景。

指数训练损失下降不等于总体误差必然下降，仍需 margin 或复杂度泛化分析。AdaBoost 优化的代理是 exponential loss，与分类代理损失公理库分类代理损失与校准classification calibration · classification surrogate loss说明可优化代理风险在什么条件下能够控制二分类的零一超额风险。相关；它不是交叉熵算法，也不是单纯多数概率放大。

参考资料

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