Boosting：自适应提升算法

小象实战讲义 · 机器学习算法精讲

在上一节我们学习了Bagging（装袋法）和随机森林，它们通过并行训练多个模型并投票来提升性能。本节我们将深入探讨另一种强大的集成学习范式——Boosting（提升法）。Boosting的核心思想是顺序地训练一系列“弱”分类器，每个新分类器都专注于纠正前一个分类器犯下的错误，最终将这些弱分类器加权组合成一个强大的“强”分类器。学完本节，你将掌握Boosting（特别是AdaBoost）的工作原理、数学推导，并能亲手实现其核心步骤。

💡 核心导读

• 串行与并行的本质区别：理解Boosting（顺序、自适应）与Bagging（并行、独立）的根本差异。
• 双重权重更新机制：掌握如何根据分类误差更新弱分类器的权重，以及如何根据分类结果更新每个样本的权重。
• AdaBoost算法全流程：从初始化、迭代训练到最终预测，一步步拆解算法的数学公式和实现逻辑。
• 从直觉到公式：通过可视化示例，直观理解为什么调整样本权重能有效提升模型性能。

Boosting vs. Bagging：哲学与流程对比

Boosting与Bagging虽然同属集成学习，但设计哲学和训练流程截然不同。

• Bagging (Bootstrap Aggregating)：

  • 并行化：从原始数据集中通过有放回抽样生成多个不同的训练子集，每个子集独立训练一个基学习器（如决策树）。这些学习器之间没有依赖关系，可以并行训练。
  • 降低方差：通过平均多个模型的预测，有效减少模型因数据扰动而产生的方差，对过拟合有一定的抑制作用。随机森林是Bagging的典型代表。

• Boosting (提升法)：

  • 序列化：按顺序训练一系列弱学习器。每一个新学习器的训练都依赖于前一个学习器的结果。
  • 聚焦错误：核心机制是样本权重。在每一轮迭代后，算法会增加被前一个弱分类器分错的样本的权重，减少分对样本的权重。这样，下一个弱分类器就会更“关注”那些难以分类的样本。
  • 加权组合：每个弱分类器在最终投票中的话语权（权重） 不同，分类误差越小的弱分类器，其权重越大。
  • 降低偏差：通过不断修正错误，Boosting能够生成一个偏差很低的强学习器。AdaBoost是Boosting家族中最著名的算法之一。

简而言之，讲师用”臭皮匠”给两种集成法画了像：Bagging 的三个臭皮匠人人平等，谁也不比谁好；Boosting 的臭皮匠则分了等级——有厉害点的、有差一点的，最后按本事加权发言；而误差等于瞎猜（$e_k=0.5$）的”傻子”，连臭皮匠的资格都没有，直接被开除（权重为 0）。

AdaBoost算法详解

AdaBoost（Adaptive Boosting，自适应提升）由Yoav Freund和Robert Schapire于1995年提出。下面我们逐步解析其算法流程、关键公式及背后的动机。

1. 问题设定与初始化

假设我们有一个二分类数据集，包含 $N$ 个样本：$\lbrace (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) \rbrace$，其中 $y_i \in \lbrace -1, +1\rbrace$。 我们计划顺序训练 $K$ 个弱分类器，记为 $g_1(x), g_2(x), ..., g_K(x)$。

第一步：初始化样本权重。 为每个样本分配初始权重，通常假设所有样本同等重要，即均匀分布： $$w_{1,i} = \frac{1}{N}, \quad \text{对于 } i = 1, 2, ..., N$$ 这里 $w_{k,i}$ 表示在第 $k$ 轮迭代时，第 $i$ 个样本的权重。

2. 迭代训练：第 $k$ 轮

对于 $k = 1, 2, ..., K$，执行以下步骤：

a) 训练弱分类器 $g_k(x)$ 使用当前样本权重分布 $w_{k}$ 训练一个弱分类器。这意味着在训练过程中，分类器会更重视权重大的样本。弱分类器可以是任何算法，如深度很小的决策树（Decision Stump）、朴素贝叶斯等。

b) 计算分类误差率 $e_k$ 误差率不是简单统计错分样本数，而是所有错分样本的权重之和。 $$e_k = \sum_{i=1}^{N} w_{k,i} \cdot \mathbb{I}(g_k(x_i) \ne y_i)$$ 其中 $\mathbb{I}(\cdot)$ 是指示函数，当括号内条件为真时值为1，否则为0。 因为 $\sum_{i=1}^N w_{k,i} = 1$，所以 $e_k$ 可以理解为在當前权重分布下，弱分类器犯错的加权概率。

c) 计算弱分类器权重 $\alpha_k$ 这是AdaBoost的精髓：为当前弱分类器 $g_k(x)$ 分配一个在最终集成模型中的权重 $\alpha_k$。 $$\alpha_k = \frac{1}{2} \ln\left(\frac{1 - e_k}{e_k}\right)$$

• 公式含义：$\alpha_k$ 是 $e_k$ 的单调递减函数。分类器误差 $e_k$ 越小，其权重 $\alpha_k$ 越大。

讲师带着大家代入几个数来”感受”这条曲线：

• $e_k = 0.5$（瞎猜水平）：分子分母都是 0.5，$\alpha_k = \frac{1}{2}\ln 1 = 0$。二分类问题瞎蒙都能蒙对一半，所以 $e_k=0.5$ 的分类器”简直是个傻子”——傻子没有投票权，权重归零。
• $e_k = 0.2$（不错的弱分类器）：$\frac{1-0.2}{0.2} = 4$，$\alpha_k = \frac{1}{2}\ln 4$。以 2 为底的话 $\log_2 4 = 2$，而 $\ln 4$ 比 2 还大——“一个比二大的、很好的结果”。
• $e_k = 0.1$：$\frac{1-0.1}{0.1} = 9$，$\alpha_k = \frac{1}{2}\ln 9$，更大。
• $e_k \to 0$（完美分类）：$\alpha_k \to +\infty$——分得越好，话语权越大。实践中需加平滑项避免除零。
• 如果 $e_k > 0.5$（比瞎猜还差），则 $\alpha_k < 0$：可以把它的预测反转（用 $-g_k(x)$）再加入集成。通常我们要求弱分类器至少略好于瞎猜（$e_k < 0.5$）。

d) 更新样本权重 $w_{k+1,i}$ 根据当前弱分类器的表现，调整每个样本的权重，为下一轮训练做准备。 $$w_{k+1,i} = \frac{w_{k,i}}{Z_k} \cdot \exp\left(-\alpha_k \cdot y_i \cdot g_k(x_i)\right)$$ 其中 $Z_k = \sum_{i=1}^{N} w_{k,i} \cdot \exp\left(-\alpha_k \cdot y_i \cdot g_k(x_i)\right)$ 是归一化因子，确保更新后的权重之和为1。

• 更新规则解读：
  • 对于分类正确的样本：$y_i \cdot g_k(x_i) = +1$，则 $\exp(-\alpha_k)$ 是一个小于1的数（因为 $\alpha_k > 0$）。这意味着该样本的权重被减小。
  • 对于分类错误的样本：$y_i \cdot g_k(x_i) = -1$，则 $\exp(\alpha_k)$ 是一个大于1的数。这意味着该样本的权重被增大。
  • 归一化因子 $Z_k$ 保证了所有权重更新后仍然构成一个概率分布。讲师举了个小例子：若某两个样本更新后分别是 0.3 和 0.2，除以 $Z_k = 0.5$ 后就是 $0.6$ 和 $0.4$——每一步的权重和恒为 1。

3. 组合最终强分类器

经过 $K$ 轮迭代后，我们得到了 $K$ 个弱分类器及其权重 $\lbrace g_k(x), \alpha_k\rbrace _{k=1}^K$。最终的强分类器 $G(x)$ 是它们的加权投票结果： $$G(x) = \text{sign}\left( \sum_{k=1}^{K} \alpha_k g_k(x) \right)$$ 即，将所有弱分类器的预测结果乘以其权重后求和，然后取符号。结果为正则预测为 $+1$，为负则预测为 $-1$。

AdaBoost工作机制可视化与代码实现

为了直观理解样本权重调整如何工作，我们设想一个简单的二维分类问题。下图（概念示意）展示了AdaBoost的三轮迭代过程：

1. 第一轮：初始权重均匀（所有点大小相同）。弱分类器1（一条分割线）将一些红点和蓝点分错。算法增加这些错分点的权重（图中点变大）。
2. 第二轮：由于错分点权重变大，弱分类器2会努力去正确分类这些“重点关注”的点，从而产生一条不同的分割线。它纠正了部分第一轮的错分点，但又可能分错其他点。算法再次更新权重，增大新一轮的错分点权重。
3. 第三轮：弱分类器3继续聚焦于当前权重大的（即之前难以分类的）点。
4. 最终组合：将三个弱分类器的决策边界（及其权重）结合起来，通过加权投票，形成了一个复杂且分类能力更强的边界，能够很好地分离所有点。

关键洞察：Boosting不是选择最后一个最好的分类器，而是将所有弱分类器的智慧（以不同权重）结合起来。每个分类器只擅长处理一部分问题，但通过聚焦错误和加权组合，它们共同解决了整个难题。

下面，我们通过一个极简化的数值例子，用代码实现AdaBoost的一轮核心计算，以验证公式。

import math

# ===== AdaBoost 单轮核心计算示例 =====
# 注意：这是一个自包含的演示块，展示公式计算，并非完整训练循环。

# 1. 模拟数据：4个样本，真实标签为+1或-1
y_true = [1, 1, -1, -1]  # 真实标签

# 2. 模拟第k轮的状态
# 假设当前样本权重 w_k (已经归一化，和为1)
w_k = [0.25, 0.25, 0.25, 0.25]
# 假设弱分类器 g_k 对4个样本的预测结果
g_pred = [1, -1, -1, 1]  # 第二个和第四个样本预测错误

# 3. 计算误差率 e_k: 错分样本的权重和
e_k = 0.0
for i in range(len(y_true)):
    if g_pred[i] != y_true[i]:
        e_k += w_k[i]
print(f"当前样本权重: {w_k}")
print(f"弱分类器预测: {g_pred}")
print(f"误差率 e_k = {e_k:.4f}")

# 4. 计算弱分类器权重 alpha_k (加入平滑防止除零或log(0))
def compute_alpha(epsilon, eps=1e-10):
    epsilon = max(min(epsilon, 1 - eps), eps)  # 限制在[eps, 1-eps]区间
    return 0.5 * math.log((1 - epsilon) / epsilon)

alpha_k = compute_alpha(e_k)
print(f"弱分类器权重 alpha_k = {alpha_k:.4f}")

# 5. 更新样本权重 w_{k+1,i}
w_new_numerator = []  # 更新权重的分子部分
for i in range(len(y_true)):
    # 计算 y_i * g_k(x_i)
    product = y_true[i] * g_pred[i]  # 正确时为+1，错误时为-1
    # 计算分子: w_k[i] * exp(-alpha_k * product)
    # 对指数项进行限幅，防止数值溢出(虽然本例很小，但养成好习惯)
    exponent = -alpha_k * product
    exponent = max(min(exponent, 500), -500)  # 限制在[-500, 500]区间
    w_new_numerator.append(w_k[i] * math.exp(exponent))

# 6. 计算归一化因子 Z_k
Z_k = sum(w_new_numerator)
print(f"归一化因子 Z_k = {Z_k:.4f}")

# 7. 得到归一化后的新权重 w_{k+1}
w_kplus1 = [num / Z_k for num in w_new_numerator]
print(f"更新后样本权重 w_{{k+1}}: {[round(w, 4) for w in w_kplus1]}")
print(f"验证权重和: {sum(w_kplus1):.4f}")

当前样本权重: [0.25, 0.25, 0.25, 0.25]
弱分类器预测: [1, -1, -1, 1]
误差率 e_k = 0.5000
弱分类器权重 alpha_k = 0.0000
归一化因子 Z_k = 1.0000
更新后样本权重 w_{k+1}: [0.25, 0.25, 0.25, 0.25]
验证权重和: 1.0000

在这个特例中，误差率 $e_k=0.5$（随机猜测），因此计算出的 $\alpha_k=0$。根据更新公式，$exp(-0 * \pm1) = 1$，所以样本权重没有发生变化。这符合预期：一个表现不优于随机猜测的分类器，不应该影响样本的权重分布，也不会在最终投票中拥有话语权。

Boosting的优势、局限与变种

优势：

1. 精度高：通过聚焦错误，能构建出非常强大的模型。
2. 灵活：几乎可以集成任何类型的弱学习器——决策树、朴素贝叶斯都可以（本课程聚焦的弱学习器是决策树）。

局限与注意事项：

1. 对噪声数据和异常值敏感：Bagging 的放回式采样天然会”稀释”极端噪声点的影响，而 Boosting 反其道而行——它持续加大错分样本的权重，如果这些样本本身是噪声，后续的学习器就会被”带偏”。这也是 Bagging 降方差、Boosting 降偏差的根源之一。
2. 训练速度慢：因为必须一个分类器接一个分类器地顺序训练，无法像 Bagging 那样把各棵树扔到不同机器上并行。
3. 要求弱学习器：弱学习器需要至少比瞎猜略好（$e_k < 0.5$），否则会被”开除”。

变种：本节的算法叫 AdaBoost——Adaptive Boosting，“自适应”指的就是样本权重随每轮错误动态调整。Boosting 家族还有更通用的 Gradient Boosting（把提升看作函数空间的梯度下降），它与决策树结合就是 GBDT——这正是下一节的主角。

📝 动手练一练

1. 概念辨析：假设在一个二分类AdaBoost的中期迭代中，某个弱分类器 $g_t(x)$ 在当前样本权重分布下的误差率 $e_t = 0.1$。请计算它的权重 $\alpha_t$。如果下一个弱分类器 $g_{t+1}(x)$ 的误差率 $e_{t+1} = 0.4$，谁的“话语权”更大？这说明了Boosting的什么倾向？

2. 代码思考：观察上面代码演示的输出，当 $e_k=0.5$ 时，$\alpha_k=0$，样本权重未更新。请你想一想，如果我们要修改代码，模拟一个 $e_k=0.2$ 的情况（即弱分类器较好），应该改变哪个变量？改变后，被分错的样本权重是会增大还是减小？请尝试在脑海中或草稿上推算一下。

本章小结

本节我们深入探讨了集成学习的另一大支柱——Boosting，并重点剖析了其代表算法AdaBoost。我们理解了其与Bagging在并行/串行、聚焦方差/偏差上的根本区别。通过拆解AdaBoost的算法步骤，我们掌握了其双重权重（样本权重、分类器权重）的自适应更新机制，并理解了这种机制如何通过让后续分类器不断修正前序错误，从而组合成一个强大的模型。

📋 行动清单

• 理清流程：尝试在不看讲义的情况下，在白板上画出AdaBoost一轮迭代的计算流程图，包括输入、输出和关键公式。
• 手动计算：找一个小数据集（3-4个样本），手动模拟AdaBoost的前两轮迭代，计算每一步的 $e_k$, $\alpha_k$ 和更新后的样本权重，加深对公式的理解。
• 拓展阅读：了解Boosting家族的其他成员，如Gradient Boosting的核心思想（用梯度下降的角度理解提升过程），为学习GBDT、XGBoost等高级主题打下基础。

—— 小象教研组