自适应增强（Adaptive Boosting, AdaBoost）算法的权重更新与误分类样本重加权过程
字数 4007 2025-12-08 22:48:14

自适应增强（Adaptive Boosting, AdaBoost）算法的权重更新与误分类样本重加权过程

1. 题目描述

我们已经讨论过AdaBoost的基本原理与构建过程，这里将聚焦于其核心机制：如何在每一轮迭代中自适应地更新弱分类器的权重，并重点计算与更新训练样本的权重，以强调被前一轮误分类的样本。这个过程是“自适应”（Adaptive）的关键体现，它使算法能够逐步聚焦于难以分类的样本，最终将这些弱分类器集成为一个强分类器。我们将详细推导样本权重和分类器权重的更新公式，并解释其背后的数学原理。

2. 背景与符号定义

假设我们有一个二分类训练数据集：

  • 输入空间：\(\mathcal{X}\)（例如特征向量）
  • 输出空间：\(\mathcal{Y} = \{-1, +1\}\)（二分类标签）
  • 训练集：\(D = \{ (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) \}\)，共 \(N\) 个样本。
  • 弱分类器集合：\(\{ h_t(x) \}\)，其中 \(h_t: \mathcal{X} \to \{-1, +1\}\) 是第 \(t\) 轮迭代中训练得到的弱分类器。
  • 目标：通过迭代 \(T\) 轮，得到一个强分类器 \(H(x) = \text{sign}\left( \sum_{t=1}^{T} \alpha_t h_t(x) \right)\)，其中 \(\alpha_t\) 是第 \(t\) 个弱分类器的权重。

3. 核心过程逐步推导

步骤1：初始化样本权重

首先，在算法开始时，所有训练样本的权重是均匀分布的，即每个样本的初始权重为：

\[w_1^{(i)} = \frac{1}{N}, \quad i = 1, 2, ..., N \]

这表示在第一轮训练中，所有样本同等重要。

步骤2：迭代训练弱分类器

对于每一轮迭代 \(t = 1, 2, ..., T\)：

(a) 用当前样本权重训练弱分类器
基于当前样本权重分布 \(w_t^{(i)}\) 训练一个弱分类器 \(h_t(x)\)。这里的“基于权重”通常意味着在训练时，将样本权重作为损失函数的权重，或者在采样时根据权重进行有放回抽样（例如在决策树桩中）。

(b) 计算当前弱分类器的加权误差率
定义加权误差率 \(\epsilon_t\) 为当前弱分类器在加权样本上的错误率：

\[\epsilon_t = \sum_{i=1}^{N} w_t^{(i)} \cdot \mathbb{I}(h_t(x_i) \ne y_i) \]

其中 \(\mathbb{I}(\cdot)\) 是指示函数（若括号内条件为真则取1，否则取0）。
注意：误差率 \(\epsilon_t\) 是加权和，权重是样本权重 \(w_t^{(i)}\)。因此，被错误分类的样本如果权重较大，会对误差率贡献更大。

(c) 计算当前弱分类器的权重
根据误差率 \(\epsilon_t\)，计算该弱分类器在最终强分类器中的权重 \(\alpha_t\)：

\[\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right) \]

推导解释：

  • 这个公式来源于指数损失函数（Exponential Loss）的优化。直观上：
    • 如果 \(\epsilon_t < 0.5\)（即弱分类器略好于随机猜测），则 \(\alpha_t > 0\)，且 \(\epsilon_t\) 越小，\(\alpha_t\) 越大，表示这个弱分类器在最终投票中话语权越重。
    • 如果 \(\epsilon_t = 0.5\)，则 \(\alpha_t = 0\)，该弱分类器无贡献。
    • 如果 \(\epsilon_t > 0.5\)（弱于随机猜测），则 \(\alpha_t < 0\)，意味着其预测取反后可能更有用（AdaBoost通常要求基分类器至少略好于随机，所以这种情况不常见）。
  • 从优化角度看，这个 \(\alpha_t\) 使得在当前样本权重下，加权指数损失最小。

(d) 更新样本权重
这是自适应重加权的核心步骤。更新公式为：

\[w_{t+1}^{(i)} = w_t^{(i)} \cdot \exp\left( -\alpha_t \cdot y_i \cdot h_t(x_i) \right) \cdot Z_t^{-1} \]

其中 \(Z_t\) 是归一化因子，确保更新后的权重之和为1：

\[Z_t = \sum_{i=1}^{N} w_t^{(i)} \cdot \exp\left( -\alpha_t \cdot y_i \cdot h_t(x_i) \right) \]

逐项解释：

  • 指数项 \(\exp\left( -\alpha_t \cdot y_i \cdot h_t(x_i) \right)\) 是关键：
    • 如果样本被正确分类，即 \(y_i \cdot h_t(x_i) = +1\)（因为 \(y_i\) 和 \(h_t(x_i)\) 同号），则指数为 \(-\alpha_t\)（因为 \(-\alpha_t \times 1\)）。由于 \(\alpha_t > 0\)（通常），所以 \(-\alpha_t < 0\)，那么 \(\exp(-\alpha_t) < 1\)，这意味着正确分类样本的权重会被减小。
    • 如果样本被错误分类，即 \(y_i \cdot h_t(x_i) = -1\)，则指数为 \(+\alpha_t\)，那么 \(\exp(+\alpha_t) > 1\)，误分类样本的权重会被增大。
  • 因此，误分类样本的权重增加，正确分类样本的权重减少，使得下一轮训练时，弱分类器会“更关注”之前分错的样本。
  • 归一化因子 \(Z_t\) 的作用是保持权重总和为1，使其成为一个概率分布。注意，\(Z_t\) 实际上就是当前轮的加权指数损失（乘以2后与误差率有关）。

(e) 归一化权重
由于每一步都除以 \(Z_t\)，所以更新后的权重自动满足：

\[\sum_{i=1}^{N} w_{t+1}^{(i)} = 1 \]

这保证了权重始终构成一个有效的概率分布，可以用于下一轮的加权训练。

步骤3：组合弱分类器形成强分类器

经过 \(T\) 轮迭代后，得到 \(T\) 个弱分类器及其权重 \(\alpha_t\)。最终的强分类器为加权投票：

\[H(x) = \text{sign}\left( \sum_{t=1}^{T} \alpha_t h_t(x) \right) \]

符号函数 \(\text{sign}(\cdot)\) 将加权和转换为 ±1 的预测结果。

4. 权重更新的直观解释与示例

假设在第 \(t\) 轮：

  • 当前弱分类器 \(h_t\) 的误差率 \(\epsilon_t = 0.2\)，则其权重 \(\alpha_t = \frac{1}{2} \ln\left( \frac{1-0.2}{0.2} \right) = \frac{1}{2} \ln(4) \approx 0.6931\)。
  • 对于一个被正确分类的样本（\(y_i h_t(x_i) = +1\)），其权重更新因子为 \(\exp(-0.6931) \approx 0.5\)，即权重减半。
  • 对于一个被错误分类的样本（\(y_i h_t(x_i) = -1\)），其权重更新因子为 \(\exp(0.6931) \approx 2.0\)，即权重加倍。

这样，误分类样本在下一轮训练时被抽中（或重视）的概率增大，使得下一轮的弱分类器不得不更努力地纠正这些错误。

5. 算法总结与特性

  1. 自适应性：样本权重的动态更新使得算法能逐步聚焦于难分类样本。
  2. 误差率上界：AdaBoost的训练误差上界以指数速度下降，这是其理论保证。
  3. 实际应用：通常使用决策树桩（深度为1的决策树）作为弱分类器，因其简单且快速。
  4. 防止过拟合：虽然AdaBoost在训练集上误差可以降到很低，但通过控制迭代轮数 \(T\) 和弱分类器复杂度，可以在测试集上获得良好泛化。

6. 补充：权重更新公式的另一种写法

有时权重更新公式写为：

\[w_{t+1}^{(i)} = \frac{w_t^{(i)}}{Z_t} \times \begin{cases} e^{-\alpha_t}, & \text{if } h_t(x_i) = y_i \quad \text{(正确分类)} \\ e^{+\alpha_t}, & \text{if } h_t(x_i) \ne y_i \quad \text{(错误分类)} \end{cases} \]

这与之前的指数形式等价，但更直观地显示了正确/错误分类时的缩放因子。

通过以上步骤，AdaBoost实现了“自适应”增强：每一轮都根据当前弱分类器的表现，重新调整样本权重，使后续的弱分类器能专注于之前分错的样本，最终将这些弱分类器的加权投票组合成一个高精度的强分类器。

自适应增强（Adaptive Boosting, AdaBoost）算法的权重更新与误分类样本重加权过程 1. 题目描述 我们已经讨论过AdaBoost的基本原理与构建过程，这里将聚焦于其 核心机制 ： 如何在每一轮迭代中自适应地更新弱分类器的权重，并重点计算与更新训练样本的权重，以强调被前一轮误分类的样本 。这个过程是“自适应”（Adaptive）的关键体现，它使算法能够逐步聚焦于难以分类的样本，最终将这些弱分类器集成为一个强分类器。我们将详细推导样本权重和分类器权重的更新公式，并解释其背后的数学原理。 2. 背景与符号定义 假设我们有一个二分类训练数据集： 输入空间：\( \mathcal{X} \)（例如特征向量） 输出空间：\( \mathcal{Y} = \{-1, +1\} \)（二分类标签） 训练集：\( D = \{ (x_ 1, y_ 1), (x_ 2, y_ 2), ..., (x_ N, y_ N) \} \)，共 \( N \) 个样本。 弱分类器集合：\( \{ h_ t(x) \} \)，其中 \( h_ t: \mathcal{X} \to \{-1, +1\} \) 是第 \( t \) 轮迭代中训练得到的弱分类器。 目标：通过迭代 \( T \) 轮，得到一个强分类器 \( H(x) = \text{sign}\left( \sum_ {t=1}^{T} \alpha_ t h_ t(x) \right) \)，其中 \( \alpha_ t \) 是第 \( t \) 个弱分类器的权重。 3. 核心过程逐步推导 步骤1：初始化样本权重 首先，在算法开始时，所有训练样本的权重是均匀分布的，即每个样本的初始权重为： \[ w_ 1^{(i)} = \frac{1}{N}, \quad i = 1, 2, ..., N \] 这表示在第一轮训练中，所有样本同等重要。 步骤2：迭代训练弱分类器 对于每一轮迭代 \( t = 1, 2, ..., T \)： (a) 用当前样本权重训练弱分类器 基于当前样本权重分布 \( w_ t^{(i)} \) 训练一个弱分类器 \( h_ t(x) \)。这里的“基于权重”通常意味着在训练时，将样本权重作为损失函数的权重，或者在采样时根据权重进行有放回抽样（例如在决策树桩中）。 (b) 计算当前弱分类器的加权误差率 定义加权误差率 \( \epsilon_ t \) 为当前弱分类器在加权样本上的错误率： \[ \epsilon_ t = \sum_ {i=1}^{N} w_ t^{(i)} \cdot \mathbb{I}(h_ t(x_ i) \ne y_ i) \] 其中 \( \mathbb{I}(\cdot) \) 是指示函数（若括号内条件为真则取1，否则取0）。 注意 ：误差率 \( \epsilon_ t \) 是加权和，权重是样本权重 \( w_ t^{(i)} \)。因此，被错误分类的样本如果权重较大，会对误差率贡献更大。 (c) 计算当前弱分类器的权重 根据误差率 \( \epsilon_ t \)，计算该弱分类器在最终强分类器中的权重 \( \alpha_ t \)： \[ \alpha_ t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_ t}{\epsilon_ t} \right) \] 推导解释 ： 这个公式来源于指数损失函数（Exponential Loss）的优化。直观上： 如果 \( \epsilon_ t < 0.5 \)（即弱分类器略好于随机猜测），则 \( \alpha_ t > 0 \)，且 \( \epsilon_ t \) 越小，\( \alpha_ t \) 越大，表示这个弱分类器在最终投票中话语权越重。 如果 \( \epsilon_ t = 0.5 \)，则 \( \alpha_ t = 0 \)，该弱分类器无贡献。 如果 \( \epsilon_ t > 0.5 \)（弱于随机猜测），则 \( \alpha_ t < 0 \)，意味着其预测取反后可能更有用（AdaBoost通常要求基分类器至少略好于随机，所以这种情况不常见）。 从优化角度看，这个 \( \alpha_ t \) 使得在当前样本权重下，加权指数损失最小。 (d) 更新样本权重 这是自适应重加权的核心步骤 。更新公式为： \[ w_ {t+1}^{(i)} = w_ t^{(i)} \cdot \exp\left( -\alpha_ t \cdot y_ i \cdot h_ t(x_ i) \right) \cdot Z_ t^{-1} \] 其中 \( Z_ t \) 是归一化因子，确保更新后的权重之和为1： \[ Z_ t = \sum_ {i=1}^{N} w_ t^{(i)} \cdot \exp\left( -\alpha_ t \cdot y_ i \cdot h_ t(x_ i) \right) \] 逐项解释 ： 指数项 \( \exp\left( -\alpha_ t \cdot y_ i \cdot h_ t(x_ i) \right) \) 是关键： 如果样本被正确分类，即 \( y_ i \cdot h_ t(x_ i) = +1 \)（因为 \( y_ i \) 和 \( h_ t(x_ i) \) 同号），则指数为 \( -\alpha_ t \)（因为 \( -\alpha_ t \times 1 \)）。由于 \( \alpha_ t > 0 \)（通常），所以 \( -\alpha_ t < 0 \)，那么 \( \exp(-\alpha_ t) < 1 \)，这意味着 正确分类样本的权重会被减小 。 如果样本被错误分类，即 \( y_ i \cdot h_ t(x_ i) = -1 \)，则指数为 \( +\alpha_ t \)，那么 \( \exp(+\alpha_ t) > 1 \)， 误分类样本的权重会被增大 。 因此， 误分类样本的权重增加，正确分类样本的权重减少 ，使得下一轮训练时，弱分类器会“更关注”之前分错的样本。 归一化因子 \( Z_ t \) 的作用是保持权重总和为1，使其成为一个概率分布。注意，\( Z_ t \) 实际上就是当前轮的加权指数损失（乘以2后与误差率有关）。 (e) 归一化权重 由于每一步都除以 \( Z_ t \)，所以更新后的权重自动满足： \[ \sum_ {i=1}^{N} w_ {t+1}^{(i)} = 1 \] 这保证了权重始终构成一个有效的概率分布，可以用于下一轮的加权训练。 步骤3：组合弱分类器形成强分类器 经过 \( T \) 轮迭代后，得到 \( T \) 个弱分类器及其权重 \( \alpha_ t \)。最终的强分类器为加权投票： \[ H(x) = \text{sign}\left( \sum_ {t=1}^{T} \alpha_ t h_ t(x) \right) \] 符号函数 \( \text{sign}(\cdot) \) 将加权和转换为 ±1 的预测结果。 4. 权重更新的直观解释与示例 假设在第 \( t \) 轮： 当前弱分类器 \( h_ t \) 的误差率 \( \epsilon_ t = 0.2 \)，则其权重 \( \alpha_ t = \frac{1}{2} \ln\left( \frac{1-0.2}{0.2} \right) = \frac{1}{2} \ln(4) \approx 0.6931 \)。 对于一个被正确分类的样本（\( y_ i h_ t(x_ i) = +1 \)），其权重更新因子为 \( \exp(-0.6931) \approx 0.5 \)，即权重减半。 对于一个被错误分类的样本（\( y_ i h_ t(x_ i) = -1 \)），其权重更新因子为 \( \exp(0.6931) \approx 2.0 \)，即权重加倍。 这样，误分类样本在下一轮训练时被抽中（或重视）的概率增大，使得下一轮的弱分类器不得不更努力地纠正这些错误。 5. 算法总结与特性 自适应性 ：样本权重的动态更新使得算法能逐步聚焦于难分类样本。 误差率上界 ：AdaBoost的训练误差上界以指数速度下降，这是其理论保证。 实际应用 ：通常使用决策树桩（深度为1的决策树）作为弱分类器，因其简单且快速。 防止过拟合 ：虽然AdaBoost在训练集上误差可以降到很低，但通过控制迭代轮数 \( T \) 和弱分类器复杂度，可以在测试集上获得良好泛化。 6. 补充：权重更新公式的另一种写法 有时权重更新公式写为： \[ w_ {t+1}^{(i)} = \frac{w_ t^{(i)}}{Z_ t} \times \begin{cases} e^{-\alpha_ t}, & \text{if } h_ t(x_ i) = y_ i \quad \text{(正确分类)} \\ e^{+\alpha_ t}, & \text{if } h_ t(x_ i) \ne y_ i \quad \text{(错误分类)} \end{cases} \] 这与之前的指数形式等价，但更直观地显示了正确/错误分类时的缩放因子。 通过以上步骤，AdaBoost实现了“自适应”增强：每一轮都根据当前弱分类器的表现，重新调整样本权重，使后续的弱分类器能专注于之前分错的样本，最终将这些弱分类器的加权投票组合成一个高精度的强分类器。