提升方法¶

概览¶

提升方法 (Boosting) 是一种集成学习策略，其核心思想源于一个朴素的观察：

对于一个复杂的任务，将多个“专家”（弱学习器）的判断进行适当的综合，得出的判断往往要比其中任何一个专家单独的判断更好。

历史上，Kearns 和 Valiant在机器学习的PAC (Probably Approximately Correct, 概率近似正确) 学习框架下，提出了以下概念： * 强可学习：一个概念，如果存在一个多项式时间的学习算法能够学习它，并且学习的正确率很高（接近1） * 弱可学习：一个概念，如果存在一个多项式时间的学习算法能够学习它，但学习的正确率仅仅比随机猜测好一点

Schapire 证明：强可学习与弱可学习是等价的。

通常来说，找到弱学习算法通常比找到强学习算法要容易得多，那么，如果已经发现了“弱学习算法”，那么能否将它提升 (boost) 为“强学习算法”？也即是，提升方法需要解决的两个核心问题：

在每一轮如何改变训练数据的权重或概率分布？
如何将各个弱分类器组合成一个强分类器？

AdaBoost¶

AdaBoost (Adaptive Boosting) 巧妙地解决了上述提升方法的两个核心问题。它的其核心机制为自适应地调整样本权重和模型权重。

AdaBoost 如何解决核心问题：

改变数据权重：

AdaBoost 的做法是，提高那些被前一轮弱分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。
组合弱分类器：

AdaBoost 采取加权多数表决 的方法。具体来说，加大分类误差率小的弱分类器的权重，使其在表决中起较大的作用；减小分类误差率大的弱分类器的权重，使其在表决中起较小的作用。

算法步骤¶

初始化样本权重：
- 假设有 $N$ 个训练样本，初始时，每个样本的权重 $w_i$ 都被设置为 $1/N$。这意味着在开始时，所有样本被同等对待。
- $D_1 = (w_{11}, w_{12}, ..., w_{1N})$, $w_{1i} = 1/N$ for $i=1, 2, ..., N$.
迭代训练弱学习器 (共 M 轮)： 对于 $m = 1, 2, ..., M$:
- (a) 训练弱学习器** $G_m(x)$：** 使用当前带有权重分布 $D_m$ 的训练数据集训练一个弱学习器 $G_m(x)$。
- (b) 计算弱学习器 $G_m(x)$ 的误差率 $\epsilon_m$：
  
  \[ \epsilon_m = P(G_m(x_i) \neq y_i) = \sum_{i=1}^{N} w_{mi} I(G_m(x_i) \neq y_i) \]
  
  其中 $I(\cdot)$ 是指示函数。 * © 计算弱学习器 $G_m(x)$ 的权重 $\alpha_m$：
  
  \[ \alpha_m = \frac{1}{2} \ln\left(\frac{1 - \epsilon_m}{\epsilon_m}\right) \]
  
  误差率 $\epsilon_m$ 越小，$\alpha_m$ 越大。 * (d) 更新样-本权重 $D_{m+1}$：
  
  \[ \begin{aligned} Z_m &= \sum_{i=1}^{N} w_{mi} \exp(-\alpha_m y_i G_m(x_i)) \\ w_{m+1, i} &= \frac{w_{mi}}{Z_m} \exp(-\alpha_m y_i G_m(x_i)) \end{aligned} \]
  
  其中 $y_i \in \{-1, +1\}$，$G_m(x_i)$ 也输出 -1 或 +1。$Z_m$ 是规范化因子，确保 $\sum_{i=1}^{N} w_{m+1, i} = 1$。如果样本 $x_i$ 被 $G_m(x)$ 错误分类 ($y_i G_m(x_i) = -1$)，其权重会被增大。如果被正确分类 ($y_i G_m(x_i) = 1$)，其权重会被减小。
组合弱学习器：

最终的强分类器 $G(x)$ 是所有弱学习器的加权线性组合：

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

训练误差分析¶

AdaBoost 算法的一个显著特点是它能够持续降低在训练数据上的分类误差率。

设 AdaBoost 算法经过 $M$ 轮迭代后得到的最终分类器为 $G(x) = \text{sign}(f(x))$，

其中 $f(x) = \sum_{m=1}^{M} \alpha_m G_m(x)$ 是弱分类器 $G_m(x)$ 的加权和。AdaBoost 算法最终分类器的训练误差满足以下不等式： $$ \frac{1}{N}\sum_{i=1}^{N}I(G(x_i) \neq y_i) \le \frac{1}{N}\sum_{i=1}^{N}\exp(-y_i f(x_i)) = \prod_{m=1}^{M}Z_m $$

$I(\cdot)$为指示函数，当条件为真时取值为1，否则为0。

这个定理表明，AdaBoost 的训练误差率有一个明确的上界，这个上界是每一轮迭代中规范化因子 $Z_m$ 的连乘积。

如果每个弱分类器 $G_m(x)$ 的加权错误率 $\epsilon_m < 0.5$（即比随机猜测要好），那么 $Z_m < 1$。在这种情况下，随着迭代次数 $M$ 的增加，$\prod_{m=1}^{M}Z_m$ 会以指数速率下降，趋向于0。这意味着 AdaBoost 算法能够快速降低训练误差，并且在理论上可以达到非常低的训练误差。

AdaBoost的前向分步算法解释¶

除了直接的算法步骤描述，AdaBoost 还可以从另一个角度进行理解，即将其视为一个加法模型，使用指数损失函数，并通过前向分步算法进行优化的过程。这样看，AdaBoost 实际上是前向分布加法算法的特例。

核心概念:

加法模型 (Additive Model): AdaBoost 的最终分类器 $f(x)$ 是由一系列基学习器（即弱分类器 $G_m(x)$）及其对应的权重 $\alpha_m$ 线性组合而成的：

\[ f(x) = \sum_{m=1}^{M} \alpha_m G_m(x) \]
指数损失函数 (Exponential Loss Function): AdaBoost 算法在学习过程中，可以看作是在最小化一个特定的损失函数，即指数损失函数：

\[ L_{\text{exp}}(y_i, f(x_i)) = \exp(-y_i f(x_i)) \]
前向分步算法 (Forward Stagewise Algorithm): 这是一种贪心算法策略，用于拟合加法模型。在算法的每一步（第 $m$ 步），我们并不改变已经学习到的模型部分 $f_{m-1}(x) = \sum_{k=1}^{m-1} \alpha_k G_k(x)$，而是通过最小化当前总损失来确定新的基学习器 $G_m(x)$ 及其权重 $\alpha_m$。具体来说，在第 $m$ 步，我们求解： $$ (\alpha_m, G_m) = \arg\min_{\alpha, G} \sum_{i=1}^{N} \exp\left[-y_i \left(f_{m-1}(x_i) + \alpha G(x_i)\right)\right] $$ 这个优化问题可以分解为两步：
1. 首先固定 $\alpha$，找到使损失最小的 $G(x)$。
2. 然后固定 $G(x)$，找到使损失最小的 $\alpha$。
可以证明，AdaBoost 算法中更新样本权重 $w_{mi}$ 和计算弱分类器权重 $\alpha_m$ 的步骤相同。 * 样本权重 $w_{m+1,i} \propto \exp(-y_i f_m(x_i))$，这与最小化指数损失有关。 * $\alpha_m = \frac{1}{2} \ln\left(\frac{1 - \epsilon_m}{\epsilon_m}\right)$ 的推导也源于对上述优化问题的求解。

将 AdaBoost 解释为前向分步算法和指数损失函数的优化过程，有助于将 AdaBoost 纳入更一般的统计学习框架，并且为 AdaBoost 的性能和行为提供了更深刻的理解。（例如，指数损失函数对错误分类的样本赋予很高的权重，这解释了 AdaBoost 对噪声和异常值比较敏感的原因。）

SAMME¶

SAMME (Stagewise Additive Modeling using a Multi-class Exponential loss function) 算法，是 AdaBoost 算法向多分类问题领域的一个重要扩展。原始的 AdaBoost 算法主要针对二分类问题设计，虽然可以通过“一对余”(One-vs-Rest) 或“一对一”(One-vs-One) 等策略间接应用于多分类任务，但 SAMME 提供了一种更为直接和统一的多分类提升框架。

顾名思义，SAMME 采用的是一种分阶段的加法模型，并使用了一个为多分类场景定制的指数损失函数。在此基础上，SAMME.R 通过利用弱学习器输出的类别概率信息，进一步提升了算法的性能。

直接多分类提升¶

SAMME 继承了 AdaBoost 的核心思想，其针对多分类场景的关键调整如下：

计算弱学习器 $G_m(x)$ 的权重 $\alpha_m$: $$ \alpha_m = \ln\left(\frac{1 - \epsilon_m}{\epsilon_m}\right) + \ln(K-1) $$ 为了确保 $\alpha_m > 0$ （即学习器表现优于随机猜测），算法加入了 $ln(K-1)$的一项。

更新样本权重 $D_{m+1}$:

如果样本 $x_i$ 被 $G_m(x)$ 正确分类 ($I(G_m(x_i) \neq y_i) = 0$)，其权重 $w_{mi}$ 会乘以因子 $\exp(0)=1$，即保持不变（在规范化之前）。

而相对应的，原先的算法乘以$-1$，相对来说惩罚较为严苛

加权投票: 经过 M 轮迭代后，最终的强分类器 $G(x)$ 通过对所有弱学习器的预测进行加权投票来产生： $$ G(x) = \arg\max_{k \in {1, 2, \dots, K}} \sum_{m=1}^{M} \alpha_m I(G_m(x) = k) $$

SAMME.R¶

SAMME.R (R 代表 "Real") 是 SAMME 的一个重要变种。与 SAMME 不同，SAMME.R 要求其弱学习器能够输出类别概率估计 $p_m(k|x_i) = P(y_i=k|x_i, D_m)$，而不仅仅是离散的类别标签。

核心思想: SAMME.R 利用这些概率信息来更精细地调整样本权重和组合弱学习器，通常能够比 SAMME 收敛更快，并且在许多数据集上表现出更好的性能。对每个样本 $x_i$，将其类别概率 $p_m(k|x_i)$ 转换为对数几率的形式：

\[ h_{mk}(x_i) = (K-1) \left( \ln p_{mk}(x_i) - \frac{1}{K} \sum_{j=1}^K \ln p_{mj}(x_i) \right) \]

更新样本权重： $$ w_{m+1, i} = \frac{w_{mi} \exp\left( -\frac{K-1}{K} y_{ik}^* h_{mk}(x_i) \right)}{Z_m} $$ （其中 $y_{ik}^*$ 是经过编码的目标变量，通常是 $y_{ik}^* = 1$ 如果 $y_i=k$，否则是 $-1/(K-1)$，具体形式可能因推导略有差异）。权重更新同样涉及到规范化。这里的权重更新更为复杂，直接源于对多分类指数损失函数的最小化。

SAMME.R 中不直接计算单个弱分类器的权重 $\alpha_m$ 用于投票，而是直接更新总的分类器 $f_m(x)$。