Boosting Part I: AdaBoost

约 3985 个字 1 张图片 预计阅读时间 13 分钟 总阅读量 次

前置内容：【待补充】 https://www.youtube.com/watch?v=LsK-xG1cLYA

AdaBoost 是集成学习（Ensemble Learning）中 Boosting 家族的代表性算法，理解其思想对后续理解 GBDT、XGBoost 等更复杂的算法有很大帮助。

AdaBoost 的全称是 Adaptive Boosting（自适应增强），其核心思想是三点：

1. 通过迭代地训练一系列的弱学习器（Weak Learner），
2. 并将它们通过其分类效果加权组合成一个强学习器（Strong Learner），进行==分类任务==。
3. “自适应”体现在：后续的模型会从前面模型分错的样本中进行学习（残差学习），也就是更关注之前模型分错的样本。

1. 使用场景

AdaBoost 主要用于解决分类问题，尤其是二分类问题。

• 二分类问题：这是 AdaBoost 最经典和最直接的应用，例如判断邮件是否为垃圾邮件、用户是否会流失等。
• 多分类问题：可以通过推广形式（如 AdaBoost.M1, SAMME, SAMME.R 算法）来解决多分类任务。
• 回归问题：也有对应的回归版本（如 AdaBoost.R），但它在回归领域的流行度较低。

它的核心价值在于==能将一些性能仅仅比随机猜测好一点的弱学习器（比如层数很低的决策树，即“决策树桩” Decision Stump），通过多个学习器的加权组合（“众人的智慧”）==，显著提升其性能，达到很高的精度。

2. 核心思想

AdaBoost 的思想可以概括为三个步骤的循环：

1. 提高被错分样本的权重：算法开始时，为每个训练样本分配相同的权重。在每一轮迭代中，训练一个弱学习器。然后，提高那些被这个弱学习器错分的样本的权重，降低正确分类的样本的权重。这样一来，后续的弱学习器就会更加关注那些“难啃的骨头”。

2. 加权组合弱学习器：在每一轮迭代结束后，根据当前弱学习器的分类错误率，为其分配一个权重 \(\alpha\)。 (Amount of say)，错误率越低的弱学习器，会被赋予越大的权重**。这意味着在最终的“投票”决策中，表现好的学习器有更大的发言权。

而不是像随机森林一样，最终投票时候每一棵树的权重都是相等的，取 majority。

1. 迭代与组合：重复以上两个步骤，直到达到预设的迭代次数或满足某个终止条件。最终的强分类器是所有弱学习器根据其各自的权重进行加权投票（或加权求和）的结果。

从另一个角度看，AdaBoost 算法可以被看作是一个前向分步加法模型（Forward Stagewise Additive Model），其损失函数为指数损失函数（Exponential Loss）。

3. 算法流程

假设我们有一个二分类的训练数据集 \(T = \{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}\)，其中 \(x_i \in \mathcal{X}\) 是样本实例，\(y_i \in \{-1, +1\}\) 是样本标签。算法的迭代次数为 \(M\)。

算法步骤如下：

1. 初始化样本权重

   为每个样本初始化一个相等的权重。如果总共有 \(N\) 个样本, 则每个样本的初始权重为：

   \[
   D_1 = (w_{11}, w_{12}, ..., w_{1N}), \quad w_{1i} = \frac{1}{N}, \quad i=1, 2, ..., N
   \]

2. 进行 M 轮迭代

   对 \(m = 1, 2, ..., M\)：

   a. 训练弱学习器：使用带有权重分布 \(D_m\) 的训练数据集进行学习，得到一个弱学习器 \(G_m(x)\)。这个学习器的目标是最小化加权错误率。

   这里的弱学习器，可以认为是==利用样本的某一个特征的数据，建立的一个对样本进行分类的决策树（只分叉一次！），又被叫做 Stump==。

   很明显这个分类相对粗糙，虽然我们对每个特征都找一个当前数据下最优的参数构造Stump，但是毫无疑问它不够深，因此是粗糙的。

   b. 计算弱学习器的错误率：计算 \(G_m(x)\) 在训练数据集上的加权错误率 \(\epsilon_m\)。

   \[
   \epsilon_m = \sum_{i=1}^{N} w_{mi} I(G_m(x_i) \neq y_i)
   \]

   其中 \(I(\cdot)\) 是指示函数（Indicator Function），当括号内条件为真时取1，否则取0。

   其实就是，把预测错误的数据的权重加起来就行了。

   c. 计算弱学习器的权重 \(\alpha_m\)：根据错误率 \(\epsilon_m\) 来计算该学习器在最终模型中的“发言权”。

   \[
   \alpha_m = \frac{1}{2} \ln\left(\frac{1 - \epsilon_m}{\epsilon_m}\right)
   \]

   这个公式表明，错误率 \(\epsilon_m\) 越小，\(\alpha_m\) 的值越大。当 \(\epsilon_m=0.5\)（相当于随机猜测）时，\(\alpha_m=0\)。

   d. 更新样本权重：为下一轮迭代更新样本的权重分布 \(D_{m+1} = (w_{m+1,1}, ..., w_{m+1,N})\)。

   说人话版本：对于样本 \(x_i\)，如果它被正确分类，则

   \[
   w_{m+1, i} = w_{m,i} \times \exp(-\alpha_m )
   \]

   如果被错误分类，则：

   \[
   w_{m+1, i} = w_{m,i} \times \exp(\alpha_m )
   \]

   对所有样本的权重作归一化，确保权重和为 1.

   \(w_{m + 1, i} = \dfrac{w_{m + 1, i}}{ \sum_{i \in N} w_{m + 1, i}}\)

3. 组合成强学习器

   将 \(M\) 个弱学习器通过各自的权重 \(\alpha_m\) 加权组合起来，得到最终的强分类器 \(G(x)\)。

   \[
   f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)
   \]

   \[
   G(x) = \text{sign}(f(x)) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right)
   \]

   其中 \(\text{sign}(\cdot)\) 是符号函数，大于0取+1，小于0取-1。

如何训练这个弱学习器？

主流的一般是两种方式：

• “加权 Gini 系数法”
• “根据权重进行重采样 (Resampling)”

首先要明确我们的目标：在第 \(m\) 轮迭代中，我们手上有一份加权的数据集，其权重分布为 \(D_m\)。我们需要在这份加权数据上训练一个弱学习器 \(G_m(x)\)，使其加权错误率 \(\epsilon_m\) 尽可能小。

以最常用的弱学习器—— 决策树桩（Decision Stump） 为例。决策树桩就是一个只有一个分裂节点的决策树，它会选择一个特征和一个阈值，将数据分成两部分。

方法一：直接使用权重进行学习（加权度量法）

这是更高效、更常用、也是诸如 Scikit-learn 等主流库中的实现方式。它的核心思想是修改弱学习器（决策树桩）的构建算法，使其在选择最佳分裂点时，能够将样本权重考虑进去。

标准的决策树在选择分裂点时，会使用信息增益（基于信息熵）或基尼增益（基于基尼不纯度）等指标。在 AdaBoost 中，我们只需要将这些指标进行“加权”即可。

1. 回顾标准基尼不纯度： 对于一个叶子节点（数据集）\(D\)，假设有 \(K\) 个类别，第 \(k\) 类的样本比例为 \(p_k\)，则该节点的基尼不纯度定义为：

   \[
   \text{Gini}(D) = \sum_{k=1}^{K} p_k (1-p_k) = 1 - \sum_{k=1}^{K} p_k^2
   \]

   其中，\(p_k = \frac{\text{Count}(C_k)}{\text{Count}(D)}\)，即类别 \(k\) 的样本数除以总样本数。

   严谨地说，这个Stump 的分类效果就是每个叶子节点的 Gini Impurity 的加权平均和（按照叶子结点的样本数量为权重）。

2. 推广到加权基尼不纯度： 现在，每个样本 \(i\) 都有一个权重 \(w_{mi}\)。我们重新定义 \(p_k\)：它不再是样本数量的比例，而是样本权重的比例。

   \[
   p_k = \frac{\sum_{i \in D, y_i=k} w_{mi}}{\sum_{i \in D} w_{mi}}
   \]

   即节点 \(D\) 中属于类别 \(k\) 的所有样本的权重之和，除以节点 \(D\) 中所有样本的权重之和。

   那么，加权基尼不纯度 (Weighted Gini Impurity) 就变成了：

   \[
   \text{Gini}_{\text{weighted}}(D) = 1 - \sum_{k=1}^{K} \left( \frac{\sum_{i \in D, y_i=k} w_{mi}}{\sum_{i \in D} w_{mi}} \right)^2
   \]

3. 寻找最佳分裂点： 构建决策树桩的过程，就是遍历每一个特征的每一个可能的分裂阈值，计算分裂后的加权基尼增益 (Weighted Gini Gain)，然后选择使该增益最大的那个特征和阈值。

   假设一个分裂将节点 \(D\) 分成了左节点 \(D_{left}\) 和右节点 \(D_{right}\)，则分裂后的加权基尼不纯度为：

   \[
   \text{Gini}_{\text{split}} = \frac{W_{left}}{W_{total}} \text{Gini}_{\text{weighted}}(D_{left}) + \frac{W_{right}}{W_{total}} \text{Gini}_{\text{weighted}}(D_{right})
   \]

   其中，\(W_{left}, W_{right}, W_{total}\) 分别是左节点、右节点和父节点的总权重。

   我们的目标就是在所有的特征中，找到一个分裂，使得这个 \(\text{Gini}_{\text{split}}\) 最小。

总结一下这个方法的流程：

对于第 \(m\) 轮迭代： | Step | 操作 | | :---: | :------------------------------------------------------------------------------------------------- | | 1 | 遍历所有特征 \(j=1, ..., d\)。 | | 2 | 对于每个特征 \(j\)，遍历所有可能的切分点 \(v\)。 | | 3 | 对于每个 \((j, v)\) 构成的切分，根据上述加权公式计算分裂后的加权基尼不纯度（或最小化加权分类误差）。 | | 4 | 选择使加权度量最优（如加权基尼不纯度最低）的那个 \((j, v)\) 作为本次迭代的弱分类器 \(G_m(x)\)。 |

这种方法没有改变数据的数量，只是在算法的评判标准里加入了权重，非常直接且高效。

---

方法二：根据权重进行重采样（Resampling）

这是一种在概念上更简单的方法，最早的 AdaBoost 论文中就是这样描述的。它的核心思想是不改变弱学习器算法本身，而是通过改变提供给算法的训练数据来体现“关注”。

细节展开：

1. 构建概率分布： 在第 \(m\) 轮迭代开始时，我们有权重分布 \(D_m = (w_{m1}, w_{m2}, ..., w_{mN})\)，且 \(\sum_{i=1}^{N} w_{mi} = 1\)。我们可以把这个权重分布看作一个离散的概率分布。

2. 进行重采样： 我们从原始的 \(N\) 个训练样本中，进行有放回的（with replacement） 抽样，共抽取 \(N\) 次，形成一个新的训练集 \(T'_m\)。 在每一次抽样时，样本 \((x_i, y_i)\) 被抽中的概率恰好是它的权重 \(w_{mi}\)。

3. 结果： 经过这个重采样过程后，我们会得到一个新的、大小同样为 \(N\) 的训练集 \(T'_m\)。在这个新数据集中：

   • 初始权重高的样本（即之前被分错的），很可能会多次出现。
   • 初始权重低的样本（即之前被分对的），可能一次都不会出现。

4. 训练标准弱学习器： 现在，我们可以把这个新的数据集 \(T'_m\) 当作一个普通的、无权重的数据集，直接喂给一个标准的、不需要支持权重的弱学习器算法（比如一个标准的、采用非加权基尼系数进行决策树桩构建的算法）进行训练。

   因为高权重的样本在新数据集中物理上就出现了更多次，所以学习器在训练时自然而然就会更“关注”它们，想办法把它们分对，以降低整体的（未加权的）分类错误。

---

特性	方法一 (加权度量)	方法二 (重采样)
实现方式	修改弱学习器内部的度量函数（如Gini）	对训练数据进行有放回的重采样
对学习器的要求	弱学习器算法必须能处理带权重的样本	可以使用任何"off-the-shelf"的标准弱学习器
效率	更高。利用了所有样本信息。	较低。采样过程有额外开销，且引入了随机性。
确定性	确定性的。每次运行结果一致。	随机性的。每次采样结果不同，训练出的模型也可能略有差异。
信息利用率	充分利用了所有样本。	可能会丢失一些低权重样本的信息（如果它们没被抽到）。
实际应用	主流方法。Scikit-learn AdaBoostClassifier 使用此法。	理论上清晰，但在实践中因效率和随机性问题较少使用。

加权度量法是目前工业界和学术界实现 AdaBoost 的标准做法。而重采样法则为我们理解 AdaBoost 如何将“权重”转化为模型的“偏好”提供了一个非常直观的视角。

3.1 推理

推理时候，对输入的特征，计算每个 Stump 输出的类别，对每个可能的分类，按照这个 Stump 的权重 \(\alpha_m\) 加和，也就得到了“预测为某类别”的总权重。选权重最高的那个即可。复杂度 \(O(M)\)，也就是 Stump 的数量。

4. 算法复杂度

AdaBoost 的算法复杂度主要由两部分构成：

1. 弱学习器的训练复杂度：假设训练一个弱学习器的平均时间复杂度为 \(T_{weak}\)。
2. 迭代过程的复杂度：算法需要进行 \(M\) 轮迭代。在每一轮中，除了训练模型，还需要计算错误率和更新样本权重，这部分的时间复杂度大约是 \(O(N)\)，其中 \(N\) 是样本数量。

因此，AdaBoost 的总时间复杂度大致为：\(O(M \cdot (T_{weak} + N))\)。

通常，弱学习器的训练复杂度是主导因素。例如，如果使用决策树桩（Decision Stump, 即单层决策树）作为弱学习器，其训练复杂度通常为 \(O(N \cdot d)\)，其中 \(d\) 是特征维度。在这种情况下，AdaBoost 的总复杂度就是 \(O(M \cdot N \cdot d)\)。

5. 优缺点总结

优点: * 高精度：通常能获得比单一学习器高很多的分类精度。 * 不易过拟合：由于弱学习器通常结构简单（高偏差，低方差），AdaBoost 算法被证明在理论上具有较低的泛化误差，抗过拟合能力比单一复杂模型（如决策树）要强。 * 实现简单：算法框架清晰，容易编程实现。 * 灵活性高：可以选用各种不同的算法作为弱学习器。 * 无需调参：除了弱学习器本身的参数和迭代次数 \(M\) 外，几乎没有其他需要调整的超参数。

缺点: * 对异常值（Outliers）和噪声敏感：由于 AdaBoost 会持续关注并提升错分样本的权重，这会导致模型在训练过程中过多地关注那些难以区分的噪声点和异常值，可能会牺牲整体性能来拟合这些“坏”数据。 * 串行执行，难以并行：AdaBoost 的迭代过程是串行的，后一轮的训练必须依赖前一轮的结果（权重分布），这使得它难以通过并行计算来缩短训练时间。这一点与 Bagging（如随机森林）有显著不同。

6. 面试常见追问

• AdaBoost 和 GBDT 的区别是什么？
  • 损失函数：AdaBoost 主要使用指数损失函数；GBDT 可以使用更广泛的损失函数（如均方误差、对数损失等）。
  • 优化方式：AdaBoost 通过调整样本权重来关注上一轮的错误；GBDT 通过拟合上一轮的残差（或负梯度）来修正模型。GBDT 是在函数空间中进行梯度下降。
• AdaBoost 为什么对异常值敏感？
  • 直接回到它的核心思想：算法会给错分的样本越来越大的权重。如果一个异常值总是被分错，它的权重会指数级增长，导致模型在后期迭代中花费大量“精力”去拟合这个异常值，从而影响整体模型的泛化能力。
• AdaBoost 会过拟合吗？
  • 会的。尽管它有较好的抗过拟合能力，但如果迭代次数 \(M\) 过多，或者弱学习器选择得过于复杂，模型同样会过拟合训练数据。通常可以通过交叉验证来选择一个合适的 \(M\)。