提升方法
提升(boosting)方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。
提升方法的基本思路
提升方法基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是"三个臭皮匠顶个诸葛亮"的道理。
历史上，Kearns和Valiant首先提出了"强可学习(strongly learnable)"和"弱可学习(weakly learnable)"的概念。指出：
- 在概率近似正确(probably approximately correct, PAC)学习的框架中，一个概念（一个类），如果存在一个多项式学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；
- 一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测好，那么就称这个概念是弱可学习的。
Schapire后来证明强可学习与弱可学习是等价的。也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
由于，发现弱学习算法通常要比发现强学习算法容易得多。通过将已经发现的"弱学习算法"提升(boost)为"强学习算法"，就是我们所说的提升方法。
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据集的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
这样，对提升方法来说，有两个问题需要回答：
- 一是在每一轮如何改变训练数据的权值或概率分布；
- 二是如何将弱分类器组合成一个强分类器。
关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器"分而治之"。
至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
AdaBoost算法
假设给定一个二分类的训练数据集：
$$T=\{(x_1, y_1),(x_2, y_2),...,(x_N,y_N)\}$$
其中，每个样本点由实例与标记组成。实例$x_i \in X \subset 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 \subset 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 -> {-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}log\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_my_iG_m(x_i)), i=1,2,...,N$$
这里，$Z_m$是规范化因子：
$$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$
它使$D_m+1$成为一个概率分布。
(3) 构建基本分类器的线性组合：
$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$
得到最终分类器：
$$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_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}^Nw_{mi}=1$。这表明，$G_m(x)$在加权的训练数据集上的分类误差率是被$G_m(x)$误分类样本的权值之和，由此可以看出数据权值分布$D_m$与基本分类器$G_m(x)$的分类误差率的关系。
- (c) 计算基本分类器$G_m(x)$的系数$\alpha_m·\alpha_m$表示$G_m(x)$在最终分类器中的重要性。由式$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$可知，当$e_m \leq \frac{1}{2}$时，$\alpha_m \geq 0$，并且$\alpha_m$随着$e_m$的减小而增大 ，所以分类误差率越小的基本分类器在最终的分类器中的作用越大。
- (d) 更新训练数据的权值分布作为下一轮作准备。
$$w_{m_1,i} = \begin{cases} \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{cases}$$
由此可知，被基本分类器$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)$的绝对值表示分类的确信度。利用基本分类器b的线性组合构建最终分类器是AdaBoost的另一特点。
AdaBoost实例
给定如下表所示训练数据。假设弱分类器由$x<v$或$x>v$产生，其阈值v使该分类器在训练数据集上分类误差率最低。试用AdaBoost算法学习一个强分类器。
$$AdaBoost实例 训练数据表$$
| 序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| y | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1 |
解 初始化数据权值分布：
$$D_1 = (w_{11},w_{12},...,w_{110})$$
$$w_{1i}=0.1, i=1,2,...,10$$
对$m=1$
(a) 在权值分布为$D_1$的训练数据上，阈值v取2.5时分类误差率最低，故基本分类器为:
$$G_1(x) = \begin{cases} 1,& x<2.5\\ -1,& x>2.5 \end{cases}$$
(b) $G_1(x)$在训练数据集上的误差率$e_1=P(G_1(x_i) \neq y_i) = 0.3$
(c) 计算$G_1(x)$的系数：$\alpha_1=\frac{1}{2}log\frac{1-e_1}{e_1}=0.4236$
(d) 更新训练数据的权值分布：
$$D_2=(w_{21},...,w_{2i},...,w_{210})$$
$$w_{2i}=\frac{w_{1i}}{Z_1}exp(-\alpha_1y_iG_1(x_i)), i=1,2,...10$$
$$D_2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)$$
$$f_1(x)=0.4236G_1(x)$$
分类器$sign[f_1(x)]$在训练数据集上有3个误分类点。
对$m=2$，
(a) 在权值分布为$D_2$的训练数据集上，阈值v是8.5时分类误差率最低，基本分类器为:
$$G_1(x) = \begin{cases} 1,& x<8.5\\ -1,& x>8.5 \end{cases}$$
(b) $G_2(x)$在训练数据集上的误差率$e_2=0.2143$。
(c) 计算$\alpha_2=0.6496$。
(d) 更新训练数据权值分布:
$$D_3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)$$
$$f_2(x)=0.4236G_1(x) + 0.6496G_2(x)$$
分类器$sign[f_2(x)]$在训练数据集上有3个误分类点。
对m=3，
(a) 在权值分布为$D_3$的训练数据上，阈值v是5.5时分类误差率最低，基本分类器为：
$$G_1(x) = \begin{cases} 1,& x>5.5\\ -1,& x<5.5 \end{cases}$$
(b) $G_3(x)$在训练样本集上的误差率$e_3=0.1820$。
(c) 计算$\alpha_3=0.7514$。
(d) 更新训练数据的权值分布:
$$D_4=(0.125,0.125,0.125,0.102,0.102,0.065,0.065,0.065,0.125)$$
于是得到：
$$f_3(x)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)$$
AdaBoost算法的训练误差分析
AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。关于这个问题有下面的定理：
AdaBoost的训练误差界 AdaBoost算法最终分类器的训练误差界为：
$$\frac{1}{N}\sum_{i=1}^NI(G(x_i) \neq y_i) \leq \frac{1}{N}\sum_iexp(-y_if(x_i))=\prod_mZ_m$$
$$G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))$$
$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$
$$Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))$$
证明 当$G(x_i) \neq y_i$时，$y_if(x_i) < 0$，因而$exp(-y_if(x_i)) \geq 1$。由此直接推导出前半部分。
后半部分的推导要用到$Z_m$的定义式及变形：
$$w_{mi}exp(-\alpha_my_iG_m(x_i))=Z_mw_{m+1,i}$$
现推导如下：
$$\frac{1}{N}\sum_iexp(-y_if(x_i)) \\ = \frac{1}{N}\sum_iexp(-\sum_{m=1}^M)\alpha_my_iG_m(x_i) \\ = \sum_iw_{1i}\prod_{m=1}^Mexp(-\alpha_my_iG_m(x_i)) \\ = Z_1\sum_iw_{2i}\prod_{m=2}^Mexp(-\alpha_my_iG_m(x_i)) \\ = Z_1Z_2\sum_iw_{3i}\prod_{m=3}^Mexp(-\alpha_my_iG_m(x_i)) \\ = ... \\ = Z_1Z_2...Z_{M-1}\sum_iw_{Mi}exp(-\alpha_My_iG_M(x_i)) \\ = \prod_{m=1}^MZ_m$$
这一定理说明，可以在每一轮选取适当的$G_m$使得$Z_m$最小，从而使训练误差下降最快。对二分类问题，有如下结果：
二分类问题 AdaBoost的训练误差界
$$\prod_{m=1}^MZ_m = \prod_{m=1}^M[2\sqrt{e_m(1-e_m)}] = \prod_{m=1}^M\sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M\gamma_m^2)$$
这里，$\gamma_m = \frac{1}{2} - e_m$。
证明 由Z_m的定义式得：
$$Z_m = \sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i)) \\ = \sum_{yi=G_m(x_i)}w_{mi}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)}w_{mi}e^{\alpha_m} \\ = (1-e_m)e^{-\alpha_m} + e_me^{\alpha_m} \\ = 2\sqrt{e_m(1-e_m)} = \sqrt{1-4\gamma_m^2}$$
至于不等式：
$$\prod_{m=1}^M\sqrt{1-4\gamma_m^2} \leq exp(-2\sum_{m=1}^M\gamma_m^2)$$
则可先由$e^x$和$\sqrt{1-x}$在点x=0的泰勒展开式推出不等式$\sqrt{1-4\gamma_m^2} \leq exp(-2\gamma_m^2)$，进而得到。
推论 如果存在$\gamma > 0$，对所有m有$\gamma_m \geq \gamma$，则：
$$\frac{1}{N}\sum_{i=1}{N}I(G(x_i) \neq y_i) \leq exp(-2M\gamma^2)$$
这表明在此条件下AdaBoost的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。
注意，AdaBoost算法不需要知道下界$\gamma$。这正是Freund与Schapire设计AdaBoost时所考虑的。与一些早期的提升方法不同，AdaBoost具有适应性，即它能适应弱分类器各自的训练误差率。这也是它的名称(适应的提升)的由来，Ada是Adaptive的简写。
AdaBoost算法的解释
AdaBoost算法还有另一个解释，即可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二分类学习方法。
前向分布算法
考虑加法模型(additive model)：
$$f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$$
其中，$b(x;\gamma_m)$为基函数，$\gamma_m$为基函数的参数，$\beta_m$为基函数的系数。
在给定训练数据及损失函数$L(x,f(x))$的条件下，学习加法模型$f(x)$成为经验风险最小化即损失函数极小化问题：
$$min_{\beta_m,\gamma_m}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))$$
通常这是一个复杂的优化问题。前向分布算法(forward stagewise algorithm)求解这一优化问题的想法是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数：
$$min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\beta b(x_i;\gamma))$$
给定训练数据集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}, x_i \in X \subset 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)=argmin_{\beta,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma))$$
得到参数$\beta_m,\gamma_m$
(b) 更新
$$f_m(x)=f_{m-1}(x) + \beta_mb(x;\gamma_m)$$
(3) 得到加法模型
$$f(x)=f_M(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$$
这样，前向分布算法将同时求解从m=1到M所有参数$\beta_m,\gamma_m$的优化问题简化为逐次求解各个$\beta_m,\gamma_m$的优化问题。
前向分布算法与AdaBoost
由前向分布算法可以推导出AdaBoost，用定理叙述这一关系。
定理 AdaBoost算法是前向分布加法算法的特例，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器：
$$f(x)=\sum_{m=1}^M\alpha_mG_m(x)$$
由基本分类器$G_m(x)$及其系数$\alpha_m$组成，$m=1,2,...,M$。前向分布算法逐一学习基函数，这一过程与AdaBoost算法逐一学习基本分类器的过程一致。下面证明前向分布算法的损失函数是指数损失函数(exponential loss function)
$$L(y, f(x))=exp[-yf(x)]$$
时，其学习的具体操作等价于AdaBoost算法学习的具体操作。
假设经过m-1轮迭代前向分布算法已经得到$f_{m-1}(x)$：
$$f_{m-1}(x) = f_{m-2}(x)+\alpha_{m-1}G_{m-1}(x) \\ = \alpha_1G_1(x) + ... + \alpha_{m-1}G_{m-1}(x)$$
在第m轮迭代得到$\alpha_m, G_m(x)$和$f_m(x)$。
$$f_m(x)=f_{m-1}(x) + \alpha_mG_m(x)$$
目标是使前向分布算法得到的$\alpha_m$和$G_m(x)$使$f_m(x)$在训练数据集T上的指数损失最小，即：
$$(\alpha_m,G_m(x))=argmin_{\alpha,G}\sum_{i=1}^Nexp[-y_i(f_{m-1}(x_i) + \alpha G(x_i))]$$
也即：
$$目标式：(\alpha_m,G_m(x))=argmin_{\alpha,G}\sum_{i=1}^Nw_{mi}exp[-y_i\alpha G(x_i)]$$
其中，$w_{mi}=exp[-y_if_{m-1}(x_i)]$。因为$w_{mi}$既不依赖$\alpha$也不依赖$G$，所以与最小化无关。但$w_{mi}$依赖于$f_{m-1}(x)$，随着每一轮迭代而发生改变。
现证使上式达到最小的$\alpha_m^*$和$G_m^*(x)$就是AdaBoost算法所得到的的$\alpha_m$和$G_m(x)$。求解可分为两步：
首先，求$G_m^*(x)$。对任意$\alpha > 0$，使目标式最小的G(x)由下式得到：
$$G_m^*(x)=argmin_G\sum_{i=1}^Nw_{mi}I(y_i \neq G(x_i))$$
其中，$w_{mi}=exp[-y_if_{m-1}(x_i)]$。
此分类器$G_m^*(x)$即为AdaBoost算法的基本分类器$G_m(x)$，因为它是使第m轮加权训练数据分类误差率最小的基本分类器。
之后，求$\alpha_m^*$。目标式中：
$$\sum_{i=1}^Nw_{mi}exp[-y_i\alpha G(x_i)] \\ = \sum_{y_i=G_m(x_i)}w_{mi}e^{-\alpha} + \sum_{y_i \neq G_m(x_i)}w_{mi}e^{\alpha} \\ = (e^{\alpha} - e^{-\alpha})\sum_{i=1}^Nw_{mi}I(y_i \neq G(x_i)) + e^{-\alpha}\sum_{i=1}^Nw_{mi}$$
将以求得的$G_m^*(x)$带入上式，对$\alpha$求导并使导数为0，即得到使目标式最小的$\alpha$。
$$\alpha_m^*=\frac{1}{2}log\frac{1-e_m}{e_m}$$
其中，$e_m$是分类误差率：
$$e_m=\frac{\sum_{i=1}^Nw_{mi}I(y_i \neq G_m(x_i))}{\sum_{i=1}^Nw_{mi}}=\sum_{i=1}^Nw_{miI(y_i \neq G_m(x_i))}$$
这里的$\alpha_m^*$与AdaBoost算法第2(c)步的$\alpha_m$完全一致。
最后看来每一轮样本权值的更新。由
$$f_m(x)=f_{m-1}(x) + \alpha_mG_m(x)$$
以及$w_{mi}=exp[-y_if_{m-1}(x_i)]$，可得
$$w_{m+1,i}=w_{m,i}exp[-y_i\alpha_mG_m(x)]$$
这与AdaBoost算法第2(d)步的样本权值的更新，只相差规范化因子，因而等价。
]]>
