以下的内容是我在根据《统计学习方法》一书第8章所撰写的总结笔记。原书中提到的公式大多在此推导了一遍，以便日后温习所需。
关键字：多个基本分类器线性组合
提升方法
常用的统计学习方法中有一种叫做提升（boosting）方法，应用十分广泛。在分类问题中，提升方法利用样本学习出多个分类器，并将这些分类器进行线性组合，提高分类性能。
这其实是基于这样一种思想：对于一个复杂任务来说，讲多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独做出的判断好。实际上，就是俗话所说的“三个臭皮匠顶个诸葛亮”的道理。
AdaBoost算法
基本思路
Kearns和Valiant提出了“强可学习（strongly learnable）”和“弱可学习（weakly learnable）”的概念。指出：在概率近似正确（probably approximately correct, PAC）学习的框架中，
- 一个概念（一个类）如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；
- 一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略高，那么就称这个概念是弱可学习的。
有趣的是，Schapire后来证明强可学习与弱可学习是等价，他使用构造的方法证明：一个概念弱可学习的充要条件是这个概念强可学习。这个结论的证明我之后会学习，补上这里的空缺。
既然强可学习与弱可学习是等价的，那么在实际问题中如果已经发现了“弱学习算法”，那么将它提升(boost)为“强学习算法”将是可行的。并且，发现弱学习算法通常要比发现强学习算法容易得多。这么一种看似偷懒的思路，却收获了相当不错的效果。基于这一思路，AdaBoost算法（Adaptive Boosting）是可行算法中的一个代表。
对于提升方法，有两个问题需要回答：（1）每一轮如何改变训练数据的权值或概率分布；（2）如何将弱分类器组合成一个强分类器。
问题（1），AdaBoost的做法是，提高被前一轮错分类的样本的权值，而降低那些被正确分类的样本的权值。对于问题（2），即弱分类器的组合，Adaboost采取的是加权线性组合的方式。
算法原理
假定给定一个二类分类的训练数据集
$$ T=\lbrace (x_1,y_1),(x_2,y_2),…,(x_N,y_N) \rbrace $$
其中，每个样本点由实例与标记组成。实例$ x_i \in X \subseteq R^n $，$X$是实例空间，标记$y_i \in \lbrace -1, +1\rbrace$。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成一个强分类器。
AdaBoost算法
输入：训练数据集T，弱学习算法；
输出：最终分类器$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 \lbrace -1,+1 \rbrace$$
(b)计算$G_m$在训练数据集上的分类误差率
$$e_m=P(G_m(x_i) \ne y_i) = \sum_{i=1}^{N}{w_{mi}I(G_m(x_i) \ne 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,1N})$$
$$w_{m+1,i} = \frac{w_{m,i}}{Z_m}exp(-\alpha_m y_i G_m(x_i))$$
这里的$Z_m$是规范化因子：
$$Z_m = \sum_{i=1}^{N}w_{m,i}exp( -\alpha_m y_i G_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算法分析
AdaBoost是一个迭代算法。
(1)在最初假设中，每个训练数据集的样本具有相同的权重$w_{1i}=\frac{1}{N}$。以此为基础，算法在第一轮是在原始数据上学习基本分类器$G_1(x)$。
(2)AdaBoost算法的迭代过程，对m=1,2,…,M：
(a)使用当前$D_m$学习基本分类器$G_m(x)$
(b)需要注意的是，分类误差率$e_m$是一个十分重要的指标，因为学习基本分类器的优化准则是最小化当前的$e_m$。而分类误差率和当前的权值分布有关
$$e_m = P(G_m(x_i) \ne y_i) = \sum_{G_m(x_i) \ne y_i} w_{m,i}$$
因为每一轮迭代中，(d)会更新权值分布，这保证了每一轮迭代中学习的基本分类器$G_m$与上一轮的分类器$G_{m-1}$是不同的。
(c)这一步计算的系数$\alpha_m$是基本分类器$G_m(x)$在最终分类器$G(x)$中的权重：
$\alpha_m$趋势图
上图是$\alpha_m = \frac{1}{2} log \frac{1-e_m}{e_m}$的函数图像，横轴是$e_m$，纵轴是$\alpha_m$。可以看到看到，当分类误差率越小时函数值越大，也即表示分类误差率小的基本分类器在最终分类器中的权重越大。
(d)依据现有组合分类器的分类结果，更新训练数据集的权值分布，这与(c)一起保证了每次迭代得到与上一轮不一样的分类器。
更新权值的公式也可以写成：
- 如果$G_m(x_i) = y_i$，$w_{m+1,i}=\frac{w_{m,i}}{Z_m}e^{-\alpha_m}$
- 如果$G_m(x_i) \ne y_i$，$w_{m+1,i}=\frac{w_{m,i}}{Z_m}e^{\alpha_m}$
简便的计算规范化因子的方法：
$$Z_m = 2 \sqrt{e_m(1-e_m)}$$
AdaBoost算法的训练误差分析
先上结论，书中定理8.1给出：AdaBoost算法最终分类器的训练误差上界为
$$\frac{1}{N}\sum_{i=1}^{N} I(G(x_i)\ne y_i)\le \frac{1}{N}\sum_i exp(-y_if(x_i))=\prod_m Z_m$$
这个不等式的证明过程也十分明了，主要的难点在于后半部分的推导。需要使用到$Z_m$的定义式及变形：
- $w_{m,i}exp(-\alpha_m y_i G_m(x_i))=Z_m w_{m+1,i}$
- $Z_m = \sum_i w_{m,i} exp(-\alpha_m y_i G_m(x_i))$
推导过程如下：
$\frac{1}{N}\sum_i exp(-y_if(x_i)) = \frac{1}{N}\sum_i exp ( -\sum_{m=1}^M\alpha_m y_i G_m(x_i) )$# 利用$\frac{1}{N}=w_{1,i}$
$=\sum_iw_{1,i}\prod_{m=1}^M exp(-\alpha_m y_i G_m(x_i))$
$=Z_1\sum_iw_{2,i}\prod_{m=2}^M exp(-\alpha_m y_i G_m(x_i))$# 利用1式
$= …$
$=Z_1Z_2…Z_{M-1}\sum_iw_{M,i}exp(-\alpha_M y_i G_M(x_i))$# $Z_M$是利用2式得到的
$=\prod_{m=1}^MZ_m$
利用这个上界，我们可以得到一个性质：不断增加弱分类器，AdaBoost的训练误差上界会不断降低。下图是$Z_m$的图像，横轴为分类误差率$e_m$，纵轴是规范化因子$Z_m$
如图，可以看到$Z_m$的图像是一个开口朝下的抛物线，且在$e_m=0.5$处取得最大值1，故可得$0<Z_m\le1.0$。由此易得：
$$\prod_{m=1}^{M+1}Z_m = Z_{M+1}\prod_{m=1}^MZ_m\le \prod_{m=1}^MZ_m$$
也即AdaBoost的训练误差界会随着m的增加而不断降低。
第二部分，定理8.2部分，目前还没有太深入的理解，只是知道了一个非常好用的计算规范化因子的简便公式：$Z_m = 2\sqrt{e_m(1-e_m)}$。