原理

提升（boosting）方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

Boosting的基本思路

提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是“三个臭皮匠订个诸葛亮”的道理。

历史上，Kearns和Valiant首先提出了“强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。指出：在概率近似正确（probably approximately correct，PAC）学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。非常有趣的是Schapire后来证明强可学习与弱可学习是等价的，也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

这样一来，问题便成为，在学习中，如果已经发行了“弱学习算法”，那么能否将它提升（boosting）为“强学习算法”。大家知道，发现弱学习算法通常要比发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升方法时所要解决的问题。关于提升方法的研究很多，有很多算法被提出。最具代表性的是AdaBoost算法。

对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

这样，对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

AdaBoost的巧妙之处就在于它将这些想法自然且有效地实现在一种算法里。

AdaBoost

现在叙述AdaBoost算法。假设给定一个二分类的训练数据集

\[T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}\]

其中，每个样本点由实例与标记组成。实例\(x_i \in X \in R^N\)，标记\(y_i \in Y ={-1, +1}\)，X是实例空间，Y是标记集合。AdaBoost利用一下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。

输入：训练数据集\(T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}\)，其中\(x_i \in X \in R^N, y_i \in Y ={-1, +1}\)；弱学习算法； 输出：最终分类器G(x).

(1) 初始化训练数据的权值分布

\[D_1=(w_11,...,w_1i,...,w_1N), w_1i=\frac{1}{N}, i=1,2,...,N\]

(2) 对m=1,2,…,M

(a) 使用具有权值分布\(D_m\)的训练数据集学习，得到基本分类器

\[G_m(x): X \to {-1,+1}\]

(b) 计算\(G_m(x)\)在训练数据集上的分类误差率

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

(c) 计算\(G_m(x)\)的系数

\[\alpha_m = \frac{1}{2} ln \frac{1-e_m}{e_m}\]

(d) 更新训练数据集的权值分布

\[D_{m+1}=(w_{m+1,1}, ..., w_{m+1,i},..., w_{m+1,N})\] \[w_{m+1,i} = \frac{w_{mi}}{Z_m} exp(-\alpha_m y_i G_m(x_i)), i=1,2,...,N\]

这里，\(Z_m\)是规范化因子

\[Z_m = \sum_{i=1}{N} w_{mi} exp(-\alpha_m y_i G_m(x_i))\]

它使\(D_{m+1}\)成为一个概率分布。

(3) 构建分布分类器的线性组合

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

得到最终分类器

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

对AdaBoost算法作如下说明：

步骤（1）假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器\(G_1(x)\)

步骤（2）AdaBoost反复学习基本分类器，在每一轮m=1,2,…,M顺次执行下列操作：

（a）使用当前分布\(D_m\)加权的训练数据集，学习基本分类器\(G_m(x)\)

（b）计算基本分类器\(G_m(x)\)在加权训练数据集上的分类误差率：

\[e_m=P(G_m(x_i) \neq y_i) = \sum_{G_m(x_i)\neq y_i} w_{mi}\]

这里，\(w_{mi}\)表示第m轮中第i个实例的权值，\(\sum_{i=1}^N w_{mi}=1\)。这表明\(G_m(x)\)在加权的训练数据集上的分类误差率是被\(G_m(x)\)误分类样本的权值之和，由此可以看出数据权值分布\(D_m\)与基本分类器\(G_m(x)\)的分类误差率的关系。

（c）计算基本分类器\(G_m(x)\)的系数\(\alpha_m\)。\(\alpha_m\)表示\(G_m(x)\)在最终分类器中的重要性。由式（8.2）可知，当\(e_m \leq \frac{1}{2}\)时，\(\alpha_m \geq 0\)，并且\(\alpha_m\)随着\(e_m\)的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。

（d）更新训练数据的权值分布为下一轮做准备。

\[w_{m+1,i}= \left\{ \begin{align} \frac{w_{mi}}{Z_m} e^{-\alpha_m} &,& G_m(x_i) = y_i \\ \frac{w_{mi}}{Z_m} e^{\alpha_m} &,& G_m(x_i) \neq y_i \end{align} \right\]

由此可知，被基分类器\(G_m(x)\)误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，五分类样本的权值被放大\(e^{2\alpha_m}=\frac{e_m}{1-e_m}\)倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。

步骤（3）线性组合f(x)实现M个基本分类器的加权表决。系数\(\alpha_m\)表示了基本分类器\(G_m(x)\)的重要性，这里，所有\(\alpha_m\)之和并不为1。f(x)的符号决定实例x的类，f(x)的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是AdaBoost的另一个特点。

AdaBoost算法的训练误差分析

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。

AdaBoost算法最终分类器的训练误差界为

\[\frac{1}{N} \sum_{i=1}^N I(G(x_i) \neq y_i) \leq \frac{1}{N} \sum_i exp(-y_i f(x_i)) = \prod_m Z_m\]

这一定理说明，可以在每一轮选取适当的\(G_m\)使得\(Z_m\)最小，从而使训练误差下降最快。

AdaBoost的训练误差是以指数速率下降的。这一性质很有吸引力。

Ada是Adaptive的缩写。

AdaBoost算法的解释

AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二分类学习方法。

考虑加法模型（additive model）

\[f(x) = \sum_{m=1}^M \beta_m b(x; \gamma_m)\]

其中，\(b(x; \gamma_m)\)为基函数，\(\gamma_m\)为基函数的参数，\(\beta_m\)为基函数的系数。显然，AdaBoost是一个加法模型。

在给定训练数据及损失函数\(L(y, f(x))\)的条件下，学习加法模型\(f(x)\)成为经验风险极小化即损失函数极小化问题：

\[\min_{\beta_m,\gamma_m} \sum_{i=1}^N L(y_i, \sum_{m=1}^M \beta_m b(x; \gamma_m))\]

通常这是一个复杂的优化问题。前向分布算法（forward stagewise algorithm）求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：

\[\min_{\beta,\gamma} \sum_{i=1}^N L(y_i, \beta b(x_i; \gamma))\]

给定训练数据集 \(T={(x_1, y_1),(x_2, y_2),...,(x_N, y_N)}, x_i \in X \subseteq R^n, y_i \in Y = {-1,+1}\)。损失函数\(L(y,f(x))\)和基函数的集合\({b(x;\gamma)}\)，学习加法模型\(f(x)\)的前向分布算法如下：

输入：训练数据集\(T={(x_1, y_1),(x_2, y_2),...,(x_N, y_N)}\)，损失函数$L(y,f(x))\(，基函数的集合\){b(x;\gamma)}$$；

输出：加法模型\(f(x)\)

(1) 初始化\(f_0(x)=0\) (2) 对m=1,2,…,M (a) 极小化损失函数

\[(\beta_m, \gamma_m) = arg \min_{\beta,\gamma} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + \beta b(x_i; \gamma))\]

得到参数\(\beta_m, \gamma_m\)。

(b) 更新

\[f_m(x) = f_{m-1}(x_i) + \beta_m b(x_i; \gamma_m)\]

(3) 得到加法模型

$$f(x) = f_M(x) = \sum_{m=1}^M \beta_m b(x_i; \gamma_m)

这样，前向分布算法将同时求解从m=1到M所有参数\(\beta_m, \gamma_m\)优化问题简化为逐次求解各个\(\beta_m, \gamma_m\)的优化问题。

参考材料

  • 统计学习方法 李航 第8章 提升方法