Lecture 10: Boosting（AdaBoost）

目录 · ← l9 · l11 →

Lecture 10: Boosting（AdaBoost）

概述

本讲介绍与 Bagging 思路相反的集成方法——Boosting。Bagging 并行训练独立模型取平均（降方差）；Boosting 串行训练一系列“弱学习器”，每个新学习器聚焦上一个犯错的样本，最终加权组合（降偏差）。代表算法 AdaBoost：用带权重的样本训练弱分类器，按错误率分配话语权，逐步把弱学习器提升为强学习器。

核心概念与数学直觉

• 集成学习的两种哲学：
  • Bagging（并行，如随机森林）：独立训练、投票平均 → 降方差。适合高方差模型（深树）。
  • Boosting（串行，如 AdaBoost/GBDT）：逐步修正错误 → 降偏差。适合高偏差模型（浅树/弱分类器）。
  • 直觉：Bagging 像“多个独立专家投票”（每人独立判断，抵消随机错误）；Boosting 像“师徒相传”——每个新徒弟专攻师父的短板。
• AdaBoost 的核心机制：
  • 样本权重：每个训练样本有权重 $D^{(i)}$，初始均匀 $1/m$。每轮训练后，被分错的样本权重增大、分对的减小——下一轮的弱分类器被迫“重视”难样本。
  • 分类器权重：每轮弱分类器 $h_t$ 的话语权 $\alpha_t$ 由其加权错误率 $\epsilon_t$ 决定： $\epsilon_t = \sum_{i: h_t(x^{(i)}) \ne y^{(i)}} D^{(i)}_t, \qquad \alpha_t = \frac{1}{2} \ln\left(\frac{1 - \epsilon_t}{\epsilon_t}\right)$
    • $\epsilon_t$：第 $t$ 轮弱分类器的加权错误率。
    • $\alpha_t$：话语权——错误率越低（$\epsilon_t \to 0$）话语权越大；随机猜（$\epsilon_t = 0.5$）时 $\alpha_t = 0$；差于随机（$\epsilon_t > 0.5$）时 $\alpha_t < 0$（反转预测）。
  • 权重更新： $D^{(i)}_{t+1} = \frac{D^{(i)}_t \exp(-\alpha_t y^{(i)} h_t(x^{(i)}))}{Z_t}$
    • $y^{(i)} h_t(x^{(i)})$：正确分类时 $= +1$（权重乘 $e^{-\alpha_t} < 1$，减小）；错误时 $= -1$（权重乘 $e^{\alpha_t} > 1$，增大）。
    • $Z_t$：归一化因子，保证 $\sum_i D^{(i)}_{t+1} = 1$。
  • 最终预测：加权投票： $H(x) = \text{sign}\left( \sum_{t=1}^{T} \alpha_t h_t(x) \right)$
  • 理论保证：若每轮 $\epsilon_t < 0.5$（略好于随机），AdaBoost 的训练误差指数级下降： $\hat{\epsilon} \le \exp\left(-2 \sum_{t=1}^{T} \left(\frac{1}{2} - \epsilon_t\right)^2\right) \to 0$（当 $T$ 增长且每轮略好于随机）
  • 为什么 Boosting 能降偏差：弱学习器（如深度 1 的决策树桩）单个偏差大；串行叠加使最终模型能表达复杂边界——偏差逐步降低。若弱学习器已很强，Boosting 收益有限（甚至过拟合）。
  • 与梯度下降的联系：AdaBoost 可看作在指数损失 $L(y, f(x)) = e^{-y f(x)}$ 上的前向分步加法建模 (forward stagewise additive modeling)——每轮沿损失下降最快的方向加一个弱学习器。这为 GBDT（用梯度替代）铺路。

算法伪代码与逻辑解说：AdaBoost

伪代码

输入:
    - 训练集 (X, y)，y ∈ {-1, +1}
    - 弱学习器算法 WeakLearner（如深度 1 决策树桩）
    - 轮数 T

输出:
    - 强分类器 H(x) = sign( Σ_t α_t h_t(x) )

1. 初始化样本权重 D^(i) = 1/m（i = 1..m）
2. 对 t = 1..T:
    2.1 用权重 D 训练弱学习器 h_t（最小化加权错误率）
    2.2 计算加权错误率: ε_t = Σ_{i: h_t(x^(i)) ≠ y^(i)} D^(i)
    2.3 若 ε_t >= 0.5: 令 h_t 反转（或终止/重启权重）
    2.4 计算话语权: α_t = 0.5 * ln((1 - ε_t) / ε_t)
    2.5 更新权重: D^(i) = D^(i) * exp(-α_t * y^(i) * h_t(x^(i))), 再除以 Z_t 归一化
3. 返回 H(x) = sign( Σ_t α_t h_t(x) )

【算法逻辑解说】

1. Step 1：所有样本一视同仁（均匀权重）。
2. Step 2.1：弱学习器必须能处理样本权重——决策树桩按权重计算 Gini/误差，即“重样本犯错代价更高”。
3. Step 2.3 关键保障：若 $\epsilon_t \ge 0.5$（不优于随机），翻转 $h_t$（预测取反）使其错误率 $\le 0.5$；否则 $\alpha_t \le 0$ 无意义。
4. Step 2.4：$\alpha_t$ 是“信任度”。注意 $\epsilon_t \to 0$ 时 $\alpha_t \to +\infty$——完美分类器话语权极大（但此时权重更新 $Z_t$ 会异常，实践中加小 $\epsilon$ 或直接用强学习器）。
5. Step 2.5：错误样本权重乘 $e^{\alpha_t}$、正确样本乘 $e^{-\alpha_t}$——下一轮弱学习器被迫聚焦难样本。$Z_t = \sum_i D^{(i)} \exp(-\alpha_t y^{(i)} h_t(x^{(i)}))$ 保证概率归一。
6. Step 3 投票：强分类器 = 带权投票。只取 $\text{sign}$ 得硬标签；去掉 sign 的实数值 $f(x) = \sum_t \alpha_t h_t(x)$ 可当置信分数用（校准需额外处理）。

关键要点

1. Boosting 串行纠错降偏差；Bagging 并行平均降方差——适用场景不同。
2. AdaBoost 三要素：样本权重（聚焦难样本）、话语权 $\alpha_t$（信任度）、加权投票（组合）。
3. 弱学习器“略好于随机”即可，理论保证训练误差指数下降。
4. AdaBoost ≈ 指数损失上的前向分步加法建模——与梯度下降同源的优化视角。
5. 现代实战中 GBDT/XGBoost/LightGBM 是 Boosting 的主流形态（回归树 + 二阶梯度近似 + 正则化）。

常见误区与注意事项

• 对噪声数据用 AdaBoost：AdaBoost 会把权重集中到异常点，最终被噪声带偏（过拟合噪声）。实践：限制 $T$、用早停（监控验证误差）。
• 弱学习器太强：若 $h_t$ 每轮都近乎完美，$\epsilon_t \approx 0$，$\alpha_t$ 爆炸且后续轮次权重失衡——Boosting 的意义在于“弱”学习器的叠加。
• 忽略样本权重：决策树实现必须支持加权分裂；朴素实现（忽略权重）的 AdaBoost 完全失效。
• 把 $\alpha_t$ 直接当概率：$\alpha_t$ 是话语权不是概率；$H$ 的实数值输出需 Platt 校准才能解释为概率。
• 混淆 AdaBoost 与 Bagging 的适用模型：AdaBoost 配弱模型（树桩）；随机森林配强模型（深树）——用反了效果差。

思考题

1. 问题：若第 $t$ 轮弱分类器错误率 $\epsilon_t = 0.4$，计算 $\alpha_t$，并说明其含义。
   • 答案：$\alpha_t = \frac{1}{2}\ln\frac{0.6}{0.4} \approx 0.203$——比随机（0.5）好，话语权为正；下一轮错误样本权重乘 $e^{0.203} \approx 1.225$，正确样本乘 $e^{-0.203} \approx 0.816$——难样本被放大约 1.5 倍。
2. 问题：为什么 AdaBoost 对噪声敏感？如何缓解？
   • 答案：错误样本权重每轮指数放大，噪声点（本就不可能被正确分类）权重会主导后续训练，弱学习器被迫拟合噪声 ⇒ 过拟合。缓解：限制轮数 $T$（早停）、在验证集上监控、使用带“噪声鲁棒”损失的变体（如修改损失为截断形式）。
3. 问题：AdaBoost 与梯度下降有什么深层联系？
   • 答案：把强分类器看成函数 $f(x) = \sum_t \alpha_t h_t(x)$ 的逐步构造：每轮选择 $(\alpha_t, h_t)$ 使指数损失 $L = \sum_i e^{-y^{(i)} f(x^{(i)})}$ 下降最快——这正是函数空间中的坐标下降/前向分步加法建模。GBDT 把“指数损失”推广到任意可微损失，用负梯度作为拟合目标，即“任意损失的 Boosting”。