AdaBoost 算法手推

AdaBoost 是加法模型 $f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)$ 在指数损失 $L_{\exp}(f) = \sum_{i=1}^{n} e^{-y_i f(x_i)}$ 下的前向分步加性建模 (Forward Stagewise Additive Modeling)。第 $m$ 轮固定 $f_{m-1}$, 记权重 $w_i^{(m)} = e^{-y_i f_{m-1}(x_i)}$, 只需极小化 $\sum_{i=1}^{n} w_i^{(m)} e^{-\alpha_m y_i G_m(x_i)}$。把样本按对错拆分: 分对 ($y_i G_m(x_i) = +1$) 贡献 $e^{-\alpha_m} w_i$, 分错 ($y_i G_m(x_i) = -1$) 贡献 $e^{\alpha_m} w_i$, 目标化为 $e^{-\alpha_m}\left(W_m - \text{err}_m\right) + e^{\alpha_m} \text{err}_m$, 其中 $W_m = \sum_{i=1}^{n} w_i^{(m)}$ 为权重总和, $\text{err}_m = \sum_{y_i \neq G_m(x_i)} w_i^{(m)}$ 为加权错分样本权重和。对 $\alpha_m$ 求导置零: $-e^{-\alpha_m}\left(W_m - \text{err}_m\right) + e^{\alpha_m} \text{err}_m = 0$, 即 $e^{2\alpha_m} = \frac{W_m - \text{err}_m}{\text{err}_m}$; 定义加权错误率 $e_m = \frac{\text{err}_m}{W_m}$, 得 $\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$ — 弱分类器越准 ($e_m \to 0$) 权重越大, 随机猜测 ($e_m = 0.5$) 权重为 0, 差于随机 ($e_m > 0.5$) 权重为负 (实践中翻转预测即可)。固定 $\alpha_m > 0$ 时, 目标关于 $G_m$ 等价于 $\sum_{i=1}^{n} w_i^{(m)} \mathbb{1}\left[y_i \neq G_m(x_i)\right]$ — 带权分类错误率, 这正是每轮用加权数据训练弱分类器的依据。权重更新: $w_i^{(m+1)} = w_i^{(m)} e^{-\alpha_m y_i G_m(x_i)}$, 即分对乘 $e^{-\alpha_m} = \sqrt{\frac{e_m}{1 - e_m}} < 1$(权重下降), 分错乘 $e^{\alpha_m} = \sqrt{\frac{1 - e_m}{e_m}} > 1$(权重放大), 再除以 $W_{m+1}$ 归一化。最终分类器 $G(x) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)$。指数损失是 0-1 损失的凸上界 ($e^{-yf} \geq \mathbb{1}[yf < 0]$, 且光滑可微), 使加权训练与函数空间梯度下降严格对齐。

“推导 AdaBoost 权重”是 ML 面试白板题的高频天花板 — 常追问: 目标函数怎么来、为什么对 $\alpha_m$ 求导、权重为什么乘性更新、为什么必须归一化、与 GBDT 的关系。

单个弱分类器 (如深度 1 的 stump) 精度仅略好于随机 — AdaBoost 迭代重加权把训练注意力集中到错分样本, 训练误差以 $\prod_{m=1}^{M} 2\sqrt{e_m(1 - e_m)}$ 为界: 只要每轮 $e_m < 0.5$(弱学习器条件), 误差随 $M$ 指数趋于 0, 将“略优于随机”的弱学习器提升为任意精度的强分类器; 代价是指数损失对噪声/离群点过度敏感 (错分样本权重爆炸式增长), 因此 LogitBoost 改用对数似然损失、GBDT 用负梯度框架做了推广。

白板推导 AdaBoost 权重: 从指数损失出发, 固定 $G_m$ 把样本拆成“分对/分错”两组, 对 $\alpha_m$ 求导得 $\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}$

推导样本权重乘性更新 $w_i \leftarrow w_i e^{-\alpha_m y_i G_m(x_i)}$: 分对乘 $e^{-\alpha_m}$、分错乘 $e^{\alpha_m}$, 为什么必须归一化? 两个乘子之比是多少?

为什么每轮用“带权数据”训练弱分类器? 固定 $\alpha_m$ 后目标为什么退化为加权错误率?

为什么用指数损失? 它与 0-1 损失、对数损失 (LogitBoost) 的代理关系与各自优劣?

训练误差上界 $\prod_m 2\sqrt{e_m(1 - e_m)}$ 的含义; AdaBoost 与加法模型/GBDT 的关系