> 本篇文章先介绍了提升放法和AdaBoost算法。已经了解的可以直接跳过。后面给出了AdaBoost算法的两个例子，附有详细计算过程。
## 1、提升方法（来源于统计学习方法）
提升方法是一种常用的统计学习方法，应用十分广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。提升算法基于这样一种思路：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上，就是“三个臭皮匠顶个诸葛亮”的道理。
历史上，Kearns和Valiant首先提出了“强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。指出：在概率近似正确（probably approximately correct，PAC）学习框架中，一个概念（一个分类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。非常有趣的是Schapire后来证明强可学习与弱可学习是等价的，也就是说，在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
这样一来，问题便成为，在学习中，如果已经发现了“弱学习算法”，那么能否将它提升（boost）为“强学习算法”。大家知道，发现弱学习算法通常要比发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升方法时所要解决的问题。关于提升方法的研究很多，有很多算法被提出。最具代表性的是AdaBoost算法（AdaBoost algorithm）。
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合这些分类器，构成一个强分类器。
这样。对于提升算法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值分布；二是如何将弱分类器组合成为一个强分类器。
## 2、AdaBoost算法
对于上一小节末尾提出的提升方法的两个问题，AdaBoost算法的做法是：1、提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。2、采用加权多数表决的方法。具体的，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差大的弱分类器的权值，使其在表决中起较小的作用。
下面给出AdaBoost算法的公式：
> 输入：训练数据集T={（x1,y1）,（x2,y2）,...（xN,yN）},其中xi∈X⊆Rn,yi∈Y={−1,+1};弱学习算法。
> 输出：最终分类器G(x)。
> （1）初始化训练数据的权值分布
>
>
> D1=(w11,...,w1i,...,w1N),w1i=1N,i=1,2,...,N
>
> 注：第一次训练弱分类器时各个样本的权值是相等的。
> （2）对m=1,2，…,M 注：这里是个循环
> （a）使用具有权值分布Dm的训练数据集学习，得到基本分类器
>
> Gm:X→{−1,+1}
>
> （b）计算Gm(x)在训练集上的分类误差率
>
> em=P(Gm(xi)≠yi)=∑i=1nwmiI(Gm(xi)≠yi)
>
> 注：I(Gm(xi)≠yi)：不等函数I值为1.相等函数值为0。
> （c）计算Gm(x)的系数
>
> αm=12log1−emem
>
> 这里的对数是自然对数。注：显然αm是em的调单减函数，这里就解释了为什么对于没有正确分类的数据要加大权值。
> （d）更新训练数据集的权值分布
>
>
> Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N)
>
>
>
> wm+1,i=wmiZmexp(−αmyiGm(xi))i=1,2,...,N
>
> 这里，Zm是规范化因子
>
>
> Zm=∑i=1Nwmiexp(−αmyiGm(xi))
>
> 它使Dm+1成为一个概率分布。
> 注：自已比较Zm与wm+1,i的表达式，会发现这里的Zm就是在对wm+1,i进行归一化工作。
> （3）构建基本分类器的线性组合
>
> f(x)=∑m=1MαmGm(x)
>
> 得到最终分类器
>
> G(x)=sign(f(x))=sign(∑m=1MαmGm(x))
注：对于增大分类错误数据的权值和分类误差计算的说明：
> 1、Gm(x)的系数
>
> αm=12log1−emem
>
> αm表示Gm(x)在最终分类器中的重要性。由αm的表达式可知，当em⩽12时，αm⩾0 ,并且αm随着em的减小而增大，所以分类误差越小的基本分类器在最终分类器中的作用越大。
> 2、计算基本分类器Gm(x)在加权训练数据集上的分类误差率：
>
> em=P(Gm(xi)≠yi)=∑Gm(xi)≠yiwmi
>
> ,这里，wmi表示第m轮中第i个实例的权值，∑Ni=1=1（因为权值利用Zm进行了归一化）。这表明，Gm(x)在加权的训练数据集上的分类误差是被Gm(x)误分类杨蓓的权值之和，由此可以看出数据权值分布Dm与基本分类器Gm(x)的分类误差率的关系。
## 3、AdaBoost算法实例
下面提供一个例子帮助大家理解上面的概念。
给定如下表所示的训练数据。假设弱分类器由xv或x>v产生，其阈值使该分类器在 训练数据集上分类误差率最低。试用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 |
解：初始化数据权值分布
D1=(w11,w12,...,w110)
w1i=0.1,i=1,2,...,10
对m=1，
（a）在权值分布为D1的训练数据上，阈值v取2.5时分类误差率最低，故基本分类器为
G1(x)={1,x2.5−1,x>2.5
（b）显然序号为7、8、9数据产生了错误。G1(x)在训练数据集上的误差率等于将这3个数据的权值相加，即
e1=P(G1(xi)≠yi)=∑i=1nw1iI(G1(xi)≠yi)=0.3
注：I(G1(xi)≠yi)表示当G1(xi)不等于yi时 函数I()的值为1，等于时值为0。这里只有i=7,8,9时函数I值为1，其余为0。
（c）计算G1(x)的系数
α1=12log1−e1e1=12log1−e1e1=0.4236
（d）更新训练数据的权值分布：
D2=(w21,...,w2i,...,w210)
w2i=w1iZ1exp(−α1yiG1(xi)),i=1,2,...,10
Z1=∑i=1Nw1iexp(−α1yiG1(xi))=∑i=11−6,10110exp(−0.4236∗1)+∑i=79110exp(−0.4236∗−1)=0.4583+0.4582=0.9165
w2i=w1iZ1exp(−α1yiG1(xi))=1100.9165exp(−0.4236∗1)=0.07143,i=1,2,...,6,10
w2i=w1iZ1exp(−α1yiG1(xi))=1100.9165exp(−0.4236∗−1)=0.16667,i=7,8,9
D2=(w21,...,w2i,...,w210)=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143,)
f1(x)=α1G1(x)=0.4236G1(x)
分类器sign[f1(x)]在训练数据集上有3个误分点。
对m=2，
（a）在权值分布为D2的训练数据上，阈值v取8.5时分类误差率最低，故基本分类器为
G2(x)={1,x8.5−1,x>8.5
（b）显然序号为4、5、6数据产生了错误。G2(x)在训练数据集上的误差率等于将这3个数据的权值相加，即
e2=P(G2(xi)≠yi)=∑i=1nw2iI(G2(xi)≠yi)=0.07143∗3=0.2143
注：I(G2(xi)≠yi)表示当G2(xi)不等于yi时 函数I()的值为1，等于时值为0。这里只有i=4,5,6时函数I值为1，其余为0。
（c）计算G2(x)的系数
α2=12log1−e2e2=12log1−e2e2=0.6496
（d）更新训练数据的权值分布：
D3=(w31,...,w3i,...,w310)
w3i=w2iZ2exp(−α2yiG2(xi)),i=1,2,...,10
Z2=∑i=1Nw2iexp(−α2yiG2(xi))=∑i=11−3,100.07143exp(−0.6496∗1)+∑i=790.16667exp(−0.4236∗1)+∑i=460.07143exp(−0.4236∗−1)=0.14922+0.26113+0.41032=0.82067
w3i=w2iZ2exp(−α2yiG2(xi))=0.071430.82067exp(−0.6496∗1)=0.0455,i=1,2,3,10
w3i=w2iZ2exp(−α2yiG2(xi))=0.071430.82067exp(−0.6496∗−1)=0.1667,i=4,5,6
w3i=w2iZ2exp(−α2yiG2(xi))=0.166670.82067exp(−0.6496∗1)=0.1060,i=7，8，9
D3=(w31,...,w3i,...,w310)=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)
f2(x)=α1G1(x)+α2G2(x)=0.4236G1(x)+0.6496G2(x)
分类器sign[f2(x)]在训练数据集上有3个误分点。
对m=3，
（a）在权值分布为D3的训练数据上，阈值v取5.5时分类误差率最低，故基本分类器为
G3(x)={1,x>5.5−1,x5.5
（b）显然序号为1、2、3、10的数据产生了错误。G3(x)在训练数据集上的误差率等于将这4个数据的权值相加，即
e3=P(G3(xi)≠yi)=∑i=1nw3iI(G2(xi)≠yi)=0.0445∗4=0.1820
注：I(G3(xi)≠yi)表示当G3(xi)不等于yi时 函数I()的值为1，等于时值为0。这里只有i=1,2,3,10时函数I值为1，其余为0。
（c）计算G3(x)的系数
α3=12log1−e3e3=12log1−e3e3=0.7514
（d）更新训练数据的权值分布：
D4=(w41,...,w4i,...,w410)
w4i=w3iZ3exp(−α3yiG3(xi)),i=1,2,...,10
Z3=∑i=1Nw3iexp(−α3yiG3(xi))=∑i=11−3,100.0455exp(−0.7514∗−1)+∑i=790.1060exp(−0.7514∗1)+∑i=460.1667exp(−0.7514∗1)=0.38593+0.15000+0.23590=0.77183
w4i=w3iZ3exp(−α3yiG3(xi))=0.04550.77183exp(−0.7514∗−1)=0.125,i=1,2,3,10
w4i=w3iZ3exp(−α3yiG3(xi))=0.16670.77183exp(−0.7514∗1)=0.102,i=4,5,6
w4i=w3iZ3exp(−α3yiG3(xi))=0.10600.77183exp(−0.7514∗1)=0.065,i=7，8，9
D4=(w41,...,w4i,...,w410)=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)
f3(x)=α1G1(x)+α2G2(x)+α3G3(x)=0.4236G1(x)+0.6496G2(x)+0.7514G3(x)
分类器sign[f3(x)]在训练数据集上有0个误分点。
于是最终分类器为：
