Dark Dwarf Blog background

Boosting 算法

1633 words • 9 min read views
#Ma-Le

Boosting 算法

1. AdaBoost 简介

AdaBoost (Adaptive Boosting) 是一种用于分类或回归的集成方法。它具有如下的特点：

  • 它通过不断关注之前被错分的样本来提升模型的拟合能力，从而降低偏差。这一点与随机森林等主要减少方差的集成方法不同。
  • 与 Bagging 类似，它也对训练样本进行加权，但权重在每次迭代中都会动态调整。
  • 每个弱学习器训练时样本的权重都是不同的。
  • 增加被错误分类的训练点的权重：这是 AdaBoost 的核心机制。如果一个样本被当前的学习器搞错了，那么在训练下一个学习器时，这个样本的权重就会变大，让下一个学习器更加关注这个难点。
  • 在最终做决策时，表现好的（错误率低的）学习器有更大的发言权。

它的核心流程如下：

  1. 训练 TT 个分类器：AdaBoost 依次训练出一系列的弱分类器 G1,G2,...,GTG_1, G_2, ..., G_T。（这里的 TT 通常代表 “Trees”，因为决策树是 AdaBoost 最常用的弱学习器）。
  2. 动态调整样本权重：训练第 tt 个分类器 GtG_t 时，训练样本 XiX_i 的权重取决于它被前面 t−1t-1 个分类器 G1,...,Gt−1G_1, ..., G_{t-1} 错分了多少次。如果一个样本 XiX_i 被一个非常准确的弱学习器错分了，它的权重会增加得更多；反之则会减少。
  3. 训练弱学习器 GtG_t：GtG_t 的训练目标是，在当前样本权重分布下，尽可能地把样本（尤其是权重大的样本）分类正确。

最终我们获得强分类器 M(z)M(z) 是所有弱学习器的加权线性组合。对于一个测试点 zz，最终的预测结果由 M(z)=∑βtGt(z)M(z) = \sum \beta _t G_t(z) 的符号决定，其中 Gt(z)G_t(z) 的输出是 +1 或 -1，βtβ_t 是第 tt 个弱学习器的权重（投票权）。M(z)M(z) 是一个连续值，最终的分类结果是 sign(M(z))\text{sign}(M(z))。

我们经常使用决策树来作为弱分类器的理由如下：

  • 可靠地减少偏差：Boosting 能稳定地降低偏差。使用“不纯”的短决策树（即只有一层分裂的决策树，或深度很浅的树）可以防止过拟合，从而控制方差。同时短决策树的训练和预测都非常快。
  • 无需超参数搜索：与 SVM、神经网络等需要精细调参的模型相比，AdaBoost+决策树几乎是“开箱即用”的，效果通常都很好。UC Berkeley 的 Leo Breiman 称之为“世界上最好的现成（off-the-shelf）分类器”。
  • 隐式特征选择：AdaBoost+短决策树是一种特征选择的形式。如果一个特征对提升整体预测能力贡献不大，它可能根本不会被任何一个短决策树选中。
  • 非线性边界更有效：对于线性分类器，Boosting 效果不佳，因为需要很多次迭代才能拟合复杂的非线性边界。而决策树本身就是非线性的，Boosting 可以更快地减少其偏差。

2. 损失函数与公式推导

AdaBoost 使用了一个特殊的指数损失函数：

L(λ,λ^)  =  e−λλ^  =  {e−λ^,λ=+1,eλ^,λ=−1.L(\lambda,\hat{\lambda}) \;=\; e^{-\lambda\hat{\lambda}} \;=\; \begin{cases} e^{-\hat{\lambda}}, & \lambda=+1,\\[6pt] e^{\hat{\lambda}}, & \lambda=-1. \end{cases}

其中： λ\lambda 是真实标签 (+1 或 -1)，λ^\hat{\lambda} 是元学习器的连续输出值 M(Xi)M(X_i)。

于是总风险可以表示为：

Risk=1n∑i=1nL(M(Xi),yi)=1n∑i=1ne−yiM(Xi)\text{Risk} = \frac{1}{n} \sum_{i=1}^{n} L(M(X_i), y_i) = \frac{1}{n} \sum_{i=1}^{n} e^{-y_i M(X_i)}

将模型展开并分离，有：

Risk=1n∑i=1ne−yi∑t=1TβtGt(Xi)=1n∑i=1n∏t=1Te−βtyiGt(Xi)=1n∑i=1n(∏t=1T−1e−βtyiGt(Xi))e−βTyiGT(Xi)\begin{aligned} \text{Risk} &= \frac{1}{n} \sum_{i=1}^{n} e^{-y_i \sum_{t=1}^{T} \beta_t G_t(X_i)} \\ &= \frac{1}{n} \sum_{i=1}^{n} \prod_{t=1}^{T} e^{-\beta_t y_i G_t(X_i)} \\ &= \frac{1}{n} \sum_{i=1}^{n} \left( \prod_{t=1}^{T-1} e^{-\beta_t y_i G_t(X_i)} \right) e^{-\beta_T y_i G_T(X_i)} \end{aligned}

我们定义第 TT 轮开始时的样本权重 wi(T)w_i^{(T)}：

wi(T)=∏t=1T−1e−βtyiGt(Xi)w_i^{(T)} = \prod_{t=1}^{T-1} e^{-\beta_t y_i G_t(X_i)}

于是总风险可以写成关于第T轮的形式：

RiskT=∑i=1nwi(T)e−βTyiGT(Xi)=∑yi=GT(Xi)wi(T)e−βT+∑yi≠GT(Xi)wi(T)eβT=e−βT∑i=1nwi(T)+(eβT−e−βT)∑yi≠GT(Xi)wi(T)\begin{aligned} \text{Risk}_T &= \sum_{i=1}^{n} w_i^{(T)} e^{-\beta_T y_i G_T(X_i)} \\ &= \sum_{y_i = G_T(X_i)} w_i^{(T)} e^{-\beta_T} + \sum_{y_i \neq G_T(X_i)} w_i^{(T)} e^{\beta_T} \\ &= e^{-\beta_T} \sum_{i=1}^{n} w_i^{(T)} + (e^{\beta_T} - e^{-\beta_T}) \sum_{y_i \neq G_T(X_i)} w_i^{(T)} \end{aligned}

由这个式子，我们讨论两个问题：

  • GTG_T 的选择：可以看出最优的弱分类器 GTG_T 的选择依据如下：
GT=arg⁡min⁡G∑i=1nwi(T)I(yi≠G(Xi))G_T = \underset{G}{\arg\min} \sum_{i=1}^{n} w_i^{(T)} \mathbb{I}(y_i \neq G(X_i))

这正是我们训练弱分类器的目标：我们希望让被错分的点的权重之和最小。

  • 权重的递归定义：可以得到如下的样本权重更新规则：
wi(T+1)=wi(T)e−βTyiGT(Xi)={wi(T)e−βT,if yi=GT(Xi)(correct)wi(T)eβT,if yi≠GT(Xi)(incorrect)w_i^{(T+1)} = w_i^{(T)} e^{-\beta_T y_i G_T(X_i)} = \begin{cases} w_i^{(T)} e^{-\beta_T}, & \text{if } y_i = G_T(X_i) \quad (\text{correct}) \\ w_i^{(T)} e^{\beta_T}, & \text{if } y_i \neq G_T(X_i) \quad (\text{incorrect}) \end{cases}

然后我们推导分类器权重 βT\beta_T 的选择。令风险函数为 J(βT)J(\beta_T)：

J(βT)=∑yi=GT(Xi)wi(T)e−βT+∑yi≠GT(Xi)wi(T)eβTJ(\beta_T) = \sum_{y_i = G_T(X_i)} w_i^{(T)} e^{-\beta_T} + \sum_{y_i \neq G_T(X_i)} w_i^{(T)} e^{\beta_T}

对 βT\beta_T 求偏导并令其为零：

∂J(βT)∂βT=−∑yi=GT(Xi)wi(T)e−βT+∑yi≠GT(Xi)wi(T)eβT=0eβT∑yi≠GT(Xi)wi(T)=e−βT∑yi=GT(Xi)wi(T)e2βT=∑yi=GT(Xi)wi(T)∑yi≠GT(Xi)wi(T)e2βT=∑i=1nwi(T)−∑yi≠GT(Xi)wi(T)∑yi≠GT(Xi)wi(T)e2βT=1−∑yi≠GT(Xi)wi(T)∑i=1nwi(T)∑yi≠GT(Xi)wi(T)∑i=1nwi(T) \begin{aligned} \frac{\partial J(\beta_T)}{\partial \beta_T} &= -\sum_{y_i = G_T(X_i)} w_i^{(T)} e^{-\beta_T} + \sum_{y_i \neq G_T(X_i)} w_i^{(T)} e^{\beta_T} = 0 \\ e^{\beta_T} \sum_{y_i \neq G_T(X_i)} w_i^{(T)} &= e^{-\beta_T} \sum_{y_i = G_T(X_i)} w_i^{(T)} \\ e^{2\beta_T} &= \frac{\sum_{y_i = G_T(X_i)} w_i^{(T)}}{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}} \\ e^{2\beta_T} &= \frac{\sum_{i=1}^n w_i^{(T)} - \sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}} \\ e^{2\beta_T} &= \frac{1 - \frac{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{i=1}^n w_i^{(T)}}}{\frac{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{i=1}^n w_i^{(T)}}} \\ \end{aligned}

我们定义加权错误率 errT\text{err}_T：

errT=∑yi≠GT(Xi)wi(T)∑i=1nwi(T)\text{err}_T = \frac{\sum_{y_i \neq G_T(X_i)} w_i^{(T)}}{\sum_{i=1}^{n} w_i^{(T)}}

则：

e2βT=1−errTerrT2βT=ln⁡(1−errTerrT)βT=12ln⁡(1−errTerrT)\begin{aligned} e^{2\beta_T} &= \frac{1 - \text{err}_T}{\text{err}_T} \\ 2\beta_T &= \ln\left(\frac{1 - \text{err}_T}{\text{err}_T}\right) \\ \beta_T &= \frac{1}{2} \ln\left(\frac{1 - \text{err}_T}{\text{err}_T}\right) \end{aligned}
  • 如果 errT=0err_T = 0 (完美分类)，βT=∞\beta_T = \infty (获得无限大的投票权)。
  • 如果 errT=0.5err_T = 0.5 (相当于随机猜测)，βT=0\beta_T = 0 (没有投票权)。
  • 如果 errT>0.5err_T > 0.5 (比随机猜还差)，βT\beta_T 会是负数。这意味着这个学习器“坏到恰到好处”，我们可以把它预测的结果反过来用，它就变成了一个好的学习器。

于是，AdaBoost 经过整理后的完整流程如下：

  1. 初始化权重：所有训练样本的权重 wiw_i 初始化为 1n\frac{1}{n}。
  2. 循环 TT 次，对于第 tt 次：
    1. 使用当前的权重 wiw_i 训练一个弱学习器 GtG_t。
    2. 计算 GtG_t 的加权错误率 errterr_t，并根据 errterr_t 计算该学习器的投票权重 βt\beta_t。
    3. 更新所有样本的权重 wiw_i：错分的样本权重乘以 e(βt)e^{(\beta_t)}，正确的样本权重乘以 e(−βt)e^{(-\beta _t)}。（然后通常会进行归一化，使所有权重之和为1）。
  3. 返回最终模型：元学习器 h(z)=sign(∑t=1TβtGt(z))h(z) = \text{sign}(\sum _{t=1} ^T β_t G_t(z))。

需要说明：指数损失函数对噪声和异常值非常敏感，一个离群点可能会获得极大的权重，从而影响后续学习器的训练。如果数据质量不高，可以考虑使用其他更鲁棒的损失函数。