1. Boosting

Boosting（提升方法）是将弱学习器算法提升为强学习算法的统计学习方法。在分类问题中，提升方法通过反复修改训练数据的权值分布，构建一系列基本分类器（也称为弱分类器），并将这些基本分类器线性组合，构成一个强分类器。AdaBoost就是Boosting中的代表性算法。Boosting原理可由下面这张图所示：

Boosting.png

2. AdaBoost

2.1 AdaBoost算法过程

输入：训练数据集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ ，其中 $x_i\in \chi \subseteq R^n$ ；弱学习器算法；
输出：最终分类器 $G(x)$
(1)初始化训练数据的权值分布
$D_i=(W_{11},...,W_{1i},...,W_{1N}), \quad W_{1i}=\frac{1}{N},\quad i=1,2,...,N$

(2)对 $m$ 个基本分类器 $m=1,2,...,M$
(a)使用具有权值分布 $D_m$ 的训练数据集，学习得到基本分类器 $G_m(x):\chi \to \{-1,+1 \}$

(b)计算 $G_m(x)$ 在训练数据集上的分类误差率 $e_m=\sum_{i=1}^{N}P(G_m(x)\not=y_i)=\sum_{i=1}^{N}W_{mi}I(G_m(x)\not=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_my_iG_m(x_i)),\quad i=1,2,...,N$

其中， $Z_m$ 是规范化因子 $Z_m=\sum_{i=1}^{N}W_{mi}exp(-\alpha_my_iG_m(x_i))$

(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))$

其中， $sign(x)$ 是符号函数，取某个数的符号(正或负)。

对上述过程的说明：
步骤(1)：假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设可以保证第1步能够在原始数据集上学习得到基本分类器 $G_1(x)$
步骤(2)：AdaBoost反复学习基本分类器，在每一轮 $m=1,2,...,M$ 依次执行下列操作：
(a)使用当前权值分布为 $D_m$ 的训练数据集，学习得到基本分类器 $G_m(x)$
(b)计算基本分类器 $G_m(x)$ 在加权训练数据集上的分类误差率： $e_m=\sum_{i=1}^{N}P(G_m(x_i)\not=y_i)=\sum_{G_m(x)\not=y_i}W_{mi}$

其中， $W_{mi}$ 表示第 $m$ 轮迭代中第 $i$ 个样本的权值，即 $G_m(x)$ 在加权训练数据集上的分类误差率就是被 $G_m(x)$ 误分类样本的权值之和。
(c)计算基本分类器 $G_m(x)$ 的权重，即 $G_m(x)$ 在最终分类器中的重要性。由上面(c)中公式可知，当分类误差率 $e_m\le\frac{1}{2}$ 时， $\alpha_m\ge0$ ，且 $\alpha_m$ 随着 $e_m$ 的减小而增大，因此分类误差率越小的基本分类器在最终分类器中的作用越大。
(d)更新训练集的权值分布为学习下一个基本分类器作准备。当 $G_m(x)\not=y_i$ 时， $W_{m+1,i}=\frac{W_{mi}}{Z_{m}}e^{\alpha_m}$ ；当 $G_m(x)=y_i$ 时， $W_{m+1,i}=\frac{W_{mi}}{Z_{m}}e^{-\alpha_m}$ ；由此可知，被基本分类器 $G_m(x)$ 误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。比较两者的权值，发现误分类样本的权值被放大了 $e^{2\alpha_m}=\frac{1-e_m}{e_m}$ 倍。
步骤(3)：线性组合 $f(x)$ 实现 $M$ 个基本分类器的加权表决。系数 $\alpha_m$ 表示基本分类器 $G_m(x)$ 的重要性， $\alpha_m$ 的和并不为1。 $f(x)$ 的符号决定了实例x的类别， $f(x)$ 的绝对值表示分类的确信度。

2.2 AdaBoost算法的训练误差分析

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即不断减少在训练数据集上的分类误差率。对此，《统计学习方法》中给出了如下定理：
定理1（AdaBoost的训练误差界）AdaBoost算法的训练误差界为 $\frac{1}{N}\sum_{i=1}^{N}I(G_m(x)\not=y_i)\le\frac{1}{N}\sum_{i=1}exp(-y_if(x_i))=\prod_mZ_m$
证明过程如下：

定理1证明.png

该定理说明，可以在每一轮选取适当的 $G_m$ 使得 $Z_m$ 最小，从而使训练误差下降最快。对于二分类问题，给出了如下定理：

定理2（二分类问题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^2_m)}\le exp(-2\sum_{m=1}^{M}\gamma^2_m)$ 其中， $\gamma_m=\frac{1}{2}-e_m$
证明过程如下：

定理2证明.png

推论：结合定理1与定理2，如果存在 $\gamma>0$ ，对所有的m有 $\gamma_m\ge\gamma$ ，则 $\frac{1}{N}\sum_{i=1}^{N}I(G_m(x)\not=y_i)\le exp(-2M\gamma^2)$
这表明在此条件下AdaBoost的训练误差是以指数速率下降的。

2.3 AdaBoost算法的解释

AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法的二分类学习算法。
加法模型可理解为，最终的强分类器是由基本分类器加权平均得到的。
前向分布算法可理解为，在AdaBoost算法中我们利用前一个基本分类器的结果来更新后一个基本分类器的训练集数据权值。假设经过m-1轮的迭代，已经得到强分类器 $f_{m-1}(x)=f_{m-2}(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_{m}G_{m}(x)$

由此可见强分类器是通过前向分布学习算法一步步得到的。

下面介绍AdaBoost的损失函数
2.1节中的基本分类器权重计算公式和样本权值更新公式都可从AdaBoost的损失函数中推导出来。

alpha与w的推导.png

2.4 AdaBoost算法的正则化

为了防止AdaBoost过拟合，通常也会加入正则化项，这个正则化项被称为步长(learning rate)。记为v，对于前面的基本分类器的迭代 $f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)$
如果加上了正则化项，则有 $f_m(x)=f_{m-1}(x)+v\alpha_mG_m(x)$

$v$ 的取值范围为 $0<v\le1$ 。对于同样的训练集学习效果，较小的 $v$ 意味着需要更多的基本分类器的迭代次数。通常用步长和迭代最大次数来一起决定算法的拟合效果。

3. 总结

AdaBoost算法的两大特点：

特点1：通过迭代，每次学习一个基本分类器；每次迭代中，提高那些被前一轮分类器错误分类的数据的权值，同时降低那些被正确分类的数据的权值；使得误分类样本在下一轮学习中起更大的作用。即不改变所给的训练数据，而是通过不断改变训练数据的权值分布，使得训练数据在基本分类器的学习中起不同的作用。
特点2：利用基本分类器的线性组合构建最终分类器。对分类误差率小的基本分类器赋予大的权值，使其在最终的模型中起较大的作用，对分类误差率大的基本分类器赋予小的权值，使其在最终的模型中起较小的作用。

参考

1.《统计学习方法》-李航著

https://www.cnblogs.com/pinard/p/6133937.html

AdaBoost算法介绍