基础 · 09

提升方法：AdaBoost 与 GBDT

一个弱分类器只比瞎猜好一点，但按正确的方式把很多弱分类器加起来就能逼近任意强分类器。从 AdaBoost 的权重游戏到 GBDT 的残差追逐。

14 min read

弱学习器 → 强学习器

上一篇我们看到，单棵决策树很容易过拟合，而 Bagging 通过"独立训练 + 投票"来降低方差。提升方法（Boosting） 走了另一条路：

串行地训练弱分类器，每一轮把上一轮做错的样本"加重"，最后把所有弱分类器加权求和。

"弱分类器"指的是正确率只比随机猜稍好——比如一个决策树桩（stump），只做一次分裂。单独看它几乎没用，但 Schapire (1990) 证明了一个惊人的理论：

只要每个弱分类器的准确率 > 50%，用提升方法组合足够多轮后，训练误差可以指数级降到零。

这就是 PAC 学习框架下的"强可学习 ⇔ 弱可学习"等价定理。Boosting 给出了具体的构造性证明。

AdaBoost 算法

AdaBoost（Adaptive Boosting, Freund & Schapire 1997）是最经典的提升算法。给定训练集 {(xi,yi)}i=1N\{(\mathbf{x}_i, y_i)\}_{i=1}^N，yi∈{−1,+1}y_i \in \{-1, +1\}：

初始化： 所有样本等权 wi(1)=1/Nw_i^{(1)} = 1/N。

第 mm 轮：

  1. 用权重分布 w(m)\mathbf{w}^{(m)} 训练弱分类器 Gm(x)G_m(\mathbf{x})。
  2. 计算加权错误率：
em=∑i=1Nwi(m)⋅1[Gm(xi)≠yi]e_m = \sum_{i=1}^{N} w_i^{(m)} \cdot \mathbb{1}[G_m(\mathbf{x}_i) \neq y_i]
  1. 计算弱分类器权重：
αm=12ln⁡1−emem\alpha_m = \frac{1}{2} \ln \frac{1 - e_m}{e_m}

当 em<0.5e_m < 0.5 时 αm>0\alpha_m > 0；错误率越低，权重越大。

  1. 更新样本权重：
wi(m+1)=wi(m)Zm⋅exp⁡ ⁣(−αm yi Gm(xi))w_i^{(m+1)} = \frac{w_i^{(m)}}{Z_m} \cdot \exp\!\bigl(-\alpha_m \, y_i \, G_m(\mathbf{x}_i)\bigr)

其中 ZmZ_m 是归一化常数。分对的样本 yiGm(xi)=+1y_i G_m(\mathbf{x}_i) = +1，权重乘以 e−αme^{-\alpha_m}（变小）；分错的样本乘以 e+αme^{+\alpha_m}（变大）。

最终分类器：

H(x)=sign ⁣(∑m=1Mαm Gm(x))H(\mathbf{x}) = \text{sign}\!\left( \sum_{m=1}^{M} \alpha_m \, G_m(\mathbf{x}) \right)

关键直觉：错分样本权重增大 → 下一轮弱分类器被迫"关注"这些难例 → 新分类器专门修补旧的错误。

交互演示

下面的可视化展示 AdaBoost 的迭代过程。每点击一次 "Add Stump"，算法就找到当前权重下最优的决策树桩，并更新样本权重。注意观察：被错分的样本变得更大（权重更高），而正确分类的样本缩小。

轮次 0 / 8
点击 "Add Stump" 逐轮添加弱分类器。圆圈大小反映样本权重——被错分的样本权重更大。 黄色虚线是当前弱分类器，背景色是组合分类器的决策区域。

训练误差的指数下降

AdaBoost 最漂亮的理论结果是它的训练误差上界。设最终分类器的训练误差为 R^(H)\hat{R}(H)，则：

R^(H)≤∏m=1M2em(1−em)=∏m=1M1−4γm2\hat{R}(H) \leq \prod_{m=1}^{M} 2\sqrt{e_m(1 - e_m)} = \prod_{m=1}^{M} \sqrt{1 - 4\gamma_m^2}

其中 γm=12−em\gamma_m = \frac{1}{2} - e_m 是第 mm 轮比随机猜好多少。如果每轮 γm≥γ>0\gamma_m \geq \gamma > 0，则：

R^(H)≤(1−4γ2)M≤e−2γ2M\hat{R}(H) \leq \left(\sqrt{1 - 4\gamma^2}\right)^M \leq e^{-2\gamma^2 M}

训练误差以指数速度衰减到零。只要每个弱分类器比随机好那么一点点（γ>0\gamma > 0），堆够多轮就够了。

证明的关键在于：Zm=2em(1−em)Z_m = 2\sqrt{e_m(1-e_m)} 正好等于每轮的归一化因子，而训练误差 ≤∏Zm\leq \prod Z_m。

前向分步算法

AdaBoost 的 αm\alpha_m 和权重更新规则看起来像"凑出来的"——背后有更深的统一解释。

前向分步加法模型（Forward Stagewise Additive Modeling） 考虑如下优化：

min⁡f∑i=1NL(yi,  f(xi)),f(x)=∑m=1Mαm b(x; γm)\min_{f} \sum_{i=1}^{N} L\bigl(y_i,\; f(\mathbf{x}_i)\bigr), \quad f(\mathbf{x}) = \sum_{m=1}^{M} \alpha_m \, b(\mathbf{x};\, \gamma_m)

其中 b(x;γm)b(\mathbf{x}; \gamma_m) 是基函数（弱学习器），LL 是损失函数。直接优化所有 MM 个 (αm,γm)(\alpha_m, \gamma_m) 太难，前向分步的策略是：每轮只优化当前这一个 (αm,γm)(\alpha_m, \gamma_m)，固定已有的不动。

(αm,γm)=arg⁡min⁡α,γ∑i=1NL ⁣(yi,  fm−1(xi)+α b(xi; γ))(\alpha_m, \gamma_m) = \arg\min_{\alpha, \gamma} \sum_{i=1}^{N} L\!\left(y_i,\; f_{m-1}(\mathbf{x}_i) + \alpha \, b(\mathbf{x}_i;\, \gamma)\right)

当 LL 取指数损失 L(y,f)=e−yfL(y, f) = e^{-yf} 时，前向分步恰好推出 AdaBoost 的所有公式。

具体地：第 mm 步要最小化 ∑iwi(m)exp⁡(−yiαGm(xi))\sum_i w_i^{(m)} \exp(-y_i \alpha G_m(\mathbf{x}_i))，其中 wi(m)=e−yifm−1(xi)w_i^{(m)} = e^{-y_i f_{m-1}(\mathbf{x}_i)}。对 α\alpha 求导令其为零，得到的正是 αm=12ln⁡1−emem\alpha_m = \frac{1}{2}\ln\frac{1-e_m}{e_m}。

这揭示了 AdaBoost 的本质：它是指数损失函数下的前向分步加法模型的特例。

梯度提升 GBDT

把前向分步的思路推广：如果损失函数不是指数损失（比如平方损失做回归、对数损失做分类），怎么办？

梯度提升（Gradient Boosting, Friedman 2001） 的核心想法：

每一轮不直接对样本加权，而是让新的弱学习器去拟合当前损失函数的负梯度。

设已有模型 fm−1f_{m-1}，定义第 ii 个样本的伪残差：

ri(m)=−∂L(yi,f(xi))∂f(xi)∣f=fm−1r_i^{(m)} = -\frac{\partial L(y_i, f(\mathbf{x}_i))}{\partial f(\mathbf{x}_i)}\bigg|_{f = f_{m-1}}
  • 平方损失：L=12(y−f)2L = \frac{1}{2}(y - f)^2，负梯度 =yi−fm−1(xi)= y_i - f_{m-1}(\mathbf{x}_i)——就是普通残差。
  • 对数损失：负梯度是概率残差 yi−σ(fm−1(xi))y_i - \sigma(f_{m-1}(\mathbf{x}_i))。

第 mm 轮：用一棵回归树 TmT_m 拟合伪残差 {ri(m)}\{r_i^{(m)}\}，然后更新：

fm(x)=fm−1(x)+η⋅Tm(x)f_m(\mathbf{x}) = f_{m-1}(\mathbf{x}) + \eta \cdot T_m(\mathbf{x})

其中 η∈(0,1]\eta \in (0, 1] 是学习率（shrinkage），用来控制每步的步长防止过拟合。

GBDT 与 AdaBoost 的联系：

AdaBoostGBDT
损失函数指数损失任意可微损失
每轮拟合目标加权分类负梯度（伪残差）
基学习器分类器回归树
更新方式加权投票加法模型

GBDT 是更一般的框架：把损失函数换成指数损失就退化回 AdaBoost。实际中 XGBoost、LightGBM、CatBoost 都是 GBDT 的高效工程实现，加了二阶近似（Newton step）、直方图加速、正则化等优化。

这个想法在前沿里