1.1 单棵决策树的困境

在上一篇文章中，我们详细讨论了决策树的构建与剪枝。单棵完全生长的决策树具有以下特点：

• 低偏差：能够完美拟合训练数据
• 高方差：训练数据的微小变化会导致完全不同的树

这就是决策树容易过拟合的根本原因。如果我们直接用一棵完整的决策树去做分类，在训练集上可能表现完美，但在测试集上往往“原形毕露”。

1.2 两个集成方向：并行 vs 串行

如何克服单棵决策树的不稳定性？集成学习给出了两个不同的答案：

Bagging（随机森林） ：让多棵树并行生长，每棵树都是“独立的专家”，最后平等投票。就像专家会诊 —— 多位专家独立诊断后投票决定。

Boosting（AdaBoost） ：让多棵树串行生长，后一棵树专门用来修正前一棵树的错误。就像渐进式诊疗 —— 先做初步诊断，发现错误后针对性复查，不断修正。

AdaBoost属于后者——串行集成。它的核心思想是：用一系列弱分类器（每棵树的深度都很浅，分类能力仅比随机猜测稍好一点点），通过串行地调整样本权重，让每个新的弱分类器都重点关注前一轮被分错的样本，最终将这些弱分类器加权组合成一个强分类器。

1.3 “错题本”的直觉

AdaBoost最直观的理解方式就是 “错题本”机制。

想象你在准备一场考试：

• 第一轮：你做完一套模拟卷（训练一个弱分类器），发现某些题做错了
• 第二轮：你翻开错题本，重点复习那些做错的题（提高错题的权重），再做一套新卷子
• 第三轮：又产生了新的错题，继续重点复习……
• 最终：你把所有做过的卷子的经验综合起来（加权组合），形成一套完整的知识体系

AdaBoost的每一轮迭代都在做同样的事情 —— 增加前一个基学习器在训练过程中预测错误样本的权重，使得后续基学习器更加关注这些被错误标注的训练样本，尽可能纠正这些错误。

但需要注意的是，AdaBoost并不是只关注错题。它只是更偏向错题，而不是只看错题。就像复习时不能只看错题，也得看看做对的题 —— 只是错题的权重大一些。

2.1 符号约定

在正式进入算法之前，首先需要约定符号：

• 训练集：$\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}$，其中 $y_i \in \{-1, +1\}$
• $T$：迭代次数（弱分类器的数量）
• $D_t(i)$：第 $t$ 轮中第 $i$ 个样本的权重
• $h_t(x)$：第 $t$ 轮训练出的弱分类器
• $\alpha_t$：第 $t$ 个弱分类器在最终集成模型中的权重
• $\epsilon_t$：第 $t$ 个弱分类器的加权错误率

2.2 完整算法步骤

步骤1：初始化样本权重

将所有样本的权重设为相等：$D_1(i) = \frac{1}{N}, \quad i = 1, 2, ..., N$

步骤2：对 $t = 1, 2, ..., T$ 迭代

(a) 训练弱分类器：在当前样本权重分布 $D_t$ 下，训练一个弱分类器 $h_t(x)$。

(b) 计算加权错误率：

其中 $\mathbb{I}(\cdot)$ 是指示函数，条件成立时为1，否则为0。

(c) 计算弱分类器的权重：

(d) 更新样本权重：

其中 $Z_t = \sum_{i=1}^{N} D_t(i) \cdot \exp(-\alpha_t y_i h_t(x_i))$ 是归一化因子，保证 $\sum_i D_{t+1}(i) = 1$。

步骤3：输出最终强分类器：

代码实现：

1
import numpy as np
2
from sklearn.tree import DecisionTreeClassifier
3

4
class AdaBoost:
5
    """从零实现AdaBoost算法"""
6

7
    def __init__(self, n_estimators=50):
8
        self.n_estimators = n_estimators
9
        self.alphas = []
10
        self.weak_classifiers = []
11

12
    def fit(self, X, y):
13
        """
14
        X: shape (n_samples, n_features)
15
        y: shape (n_samples,), 取值 {-1, +1}
16
        """
17
        n_samples = X.shape[0]
18

19
        # 步骤1：初始化样本权重
20
        D = np.ones(n_samples) / n_samples
21

22
        for t in range(self.n_estimators):
23
            # 步骤2(a)：训练弱分类器（决策树桩，深度为1）
24
            weak_clf = DecisionTreeClassifier(max_depth=1)
25
            weak_clf.fit(X, y, sample_weight=D)
26
            predictions = weak_clf.predict(X)
27

28
            # 步骤2(b)：计算加权错误率
29
            misclassified = (predictions != y)
30
            epsilon = np.sum(D * misclassified)
31

32
            # 防止除零或数值不稳定
33
            if epsilon == 0:
34
                epsilon = 1e-10
35
            if epsilon == 1:
36
                epsilon = 1 - 1e-10
37

38
            # 步骤2(c)：计算弱分类器的权重
39
            alpha = 0.5 * np.log((1 - epsilon) / epsilon)
40

41
            # 步骤2(d)：更新样本权重
42
            # 正确分类: 权重乘以 exp(-alpha)，错误分类: 权重乘以 exp(alpha)
43
            D = D * np.exp(-alpha * y * predictions)
44
            D = D / np.sum(D)  # 归一化
45

46
            # 保存结果
47
            self.alphas.append(alpha)
48
            self.weak_classifiers.append(weak_clf)
49

50
        return self
51

52
    def predict(self, X):
53
        """预测：加权投票"""
54
        # 计算所有弱分类器的加权预测之和
55
        weighted_sum = np.zeros(X.shape[0])
56
        for alpha, clf in zip(self.alphas, self.weak_classifiers):
57
            weighted_sum += alpha * clf.predict(X)
58
        return np.sign(weighted_sum)

3.1 加法模型

AdaBoost最终得到的模型是一个加法模型（Additive Model）—— 多个基学习器的线性组合：

其中 $h_t(x)$ 是第 $t$ 个弱分类器，$\alpha_t$ 是其权重。

这个形式看起来简单，但问题在于如何确定每一轮的 $\alpha_t$ 和 $h_t$？

3.2 前向分步算法

前向分步算法（Forward Stagewise Algorithm） 是解决这个问题的核心策略。此算法的核心思想是：从前向后，每一步只优化当前这一个基分类器，固定之前已经选好的所有基分类器不变。

具体来说：

1. 初始化 $H_0(x) = 0$
2. 对 $t = 1, 2, ..., T$：
   • 固定 $H_{t-1}(x)$ 不变
   • 选择 $(\alpha_t, h_t)$ 使得损失函数最小：$(\alpha_t, h_t) = \arg\min_{\alpha, h} \sum_{i=1}^{N} L(y_i, H_{t-1}(x_i) + \alpha h(x_i))$
   • 更新：$H_t(x) = H_{t-1}(x) + \alpha_t h_t(x)$

由此可见：前向分步算法将一个复杂的全局优化问题（同时优化所有 $\alpha_t$ 和 $h_t$）转化为 $T$ 个相对简单的局部优化问题（每一步只优化一个 $\alpha_t$ 和 $h_t$）。

3.3 指数损失函数

AdaBoost使用的损失函数 —— 指数损失函数（Exponential Loss） ：

其中 $y \in \{-1, +1\}$，$H(x)$ 是模型的预测值（实数，不一定是 ±1）。

使用指数损失的原因：

1. 数学性质好：指数函数连续可微，便于优化
2. 与0-1损失一致：最小化指数损失等价于最小化分类错误率
3. 推导简洁：指数损失天然导出了AdaBoost的权重更新公式

定理：AdaBoost算法是前向分步加法算法在以指数函数为损失函数时的特例。

4.1 推导弱分类器的权重 $\alpha_t$

假设在第 $t$ 轮，我们已经有了前 $t-1$ 轮的集成模型 $H_{t-1}(x)$。现在要选择新的弱分类器 $h_t(x)$ 和权重 $\alpha_t$，使得指数损失最小：

令 $w_i^{(t)} = \exp(-y_i H_{t-1}(x_i))$（上一轮更新后的样本权重，未归一化），则目标函数变为：

对于固定的 $\alpha$，最小化上式等价于最小化加权错误率：

现在推导 $\alpha_t$ 的表达式：

将样本分为两类：被 $h$ 正确分类的（$y_i h(x_i) = 1$）和错误分类的（$y_i h(x_i) = -1$）。

目标函数可以写成：

（这里假设权重已经归一化，即 $\sum w_i^{(t)} = 1$）

对 $\alpha$ 求导并令其为零：

解得：

这就是AdaBoost中弱分类器权重的计算公式。

4.2 推导样本权重的更新公式

下列推导样本权重 $w_i^{(t)} = \exp(-y_i H_{t-1}(x_i))$ 的更新规律

在得到 $h_t$ 和 $\alpha_t$ 后：

• 当 $h_t(x_i) = y_i$（分类正确）时：$w_i^{(t+1)} = w_i^{(t)} \cdot e^{-\alpha_t}$

• 当 $h_t(x_i) \neq y_i$（分类错误）时：$w_i^{(t+1)} = w_i^{(t)} \cdot e^{\alpha_t}$

由于 $\alpha_t > 0$（因为 $\epsilon_t < 0.5$），所以分类正确的样本权重减小（乘以 $e^{-\alpha_t} < 1$），分类错误的样本权重增大（乘以 $e^{\alpha_t} > 1$）。

这正是AdaBoost “错题本”机制的数学本质 —— 被分错的样本在下一轮获得更高的权重。

统一写成：

加上归一化因子 $Z_t$ 后：

其中 $Z_t = \sum_{i=1}^{N} D_t(i) \exp(-\alpha_t y_i h_t(x_i))$。

代码实现：

1
# 验证权重更新公式的正确性
2
def verify_weight_update():
3
    np.random.seed(42)
4
    N = 10
5
    y = np.random.choice([-1, 1], N)
6
    h = np.random.choice([-1, 1], N)
7
    epsilon = 0.3
8
    alpha = 0.5 * np.log((1 - epsilon) / epsilon)
9

10
    D = np.ones(N) / N
11

12
    # 更新权重
13
    D_new_raw = D * np.exp(-alpha * y * h)
14
    D_new = D_new_raw / np.sum(D_new_raw)
15

16
    # 检查：错误分类的样本权重是否增大
17
    misclassified = (h != y)
18
    correct = (h == y)
19

20
    print(f"错误分类样本的平均权重变化: {np.mean(D_new[misclassified] / D[misclassified]):.4f}")
21
    print(f"正确分类样本的平均权重变化: {np.mean(D_new[correct] / D[correct]):.4f}")
22
    # 错误分类的权重变化 > 1，正确分类的权重变化 < 1
23

24
verify_weight_update()

4.3 指数损失与0-1损失的一致性

考虑期望指数损失 $\mathbb{E}[e^{-y H(x)}]$，对其关于 $H(x)$ 求偏导：

展开期望公式得：

整理得：

因此：

这意味着：最小化指数损失得到的分类器，恰好是贝叶斯最优分类器。指数损失是0-1损失的一个一致的替代损失函数（Surrogate Loss Function） 。

5.1 GBM是AdaBoost的泛化

在后续文章中，我们会详细讨论了梯度提升机（GBM） 。GBM的核心思想是每一轮用基学习器去拟合损失函数的负梯度。

AdaBoost和GBM之间有着深刻的联系 —— AdaBoost可以被视为GBM在“指数损失函数 + 特定的坐标下降优化”下的一个特例。更准确地说，如果GBM选择了指数损失函数 $L(y, f(x)) = e^{-y f(x)}$，那么GBM就退化成了AdaBoost算法。

这个联系可以从两个角度理解：

• 角度一：损失函数。GBM允许使用任意可微的损失函数，而AdaBoost固定使用指数损失函数。从这个意义上说，GBM是AdaBoost在损失函数维度上的泛化——它把AdaBoost的指数损失替换成了任意可微损失。

• 角度二：优化算法。AdaBoost使用前向分步加法模型（每一步解析地求解最优的 $\alpha_t$ 和 $h_t$），而GBM使用函数空间中的梯度下降（每一步用基学习器拟合负梯度）。从这个意义上说，GBM是AdaBoost在优化算法维度上的泛化——它把解析求解替换成了梯度下降。

5.2 指数损失的优缺点

优点：

• 数学性质好，推导简洁
• 与0-1损失一致
• 天然导出AdaBoost的权重更新公式

缺点：

• 对异常点非常敏感。指数损失对大误差的惩罚是指数级的——如果一个样本被严重分错（$y H(x)$ 是一个很大的负数），它的损失会爆炸式增长。
• 这也是为什么AdaBoost在噪声较多的数据集上表现可能不如GBM。

5.3 从AdaBoost到GBM：一条清晰的脉络

我们可以把从AdaBoost到GBM的演进看作一条清晰的脉络：

AdaBoost 证明了“串行纠错”这个思路是有效的，并用指数损失给出了一个优雅的数学框架。

GBM 则把这个框架泛化了 —— 把“指数损失”换成“任意可微损失”，把“解析求解”换成“梯度下降”，从而把AdaBoost从一个具体的算法变成了一个通用的算法框架。