AdaBoost (Adaptive Boosting)

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

历史上，Kearns 和 Valiant 首先提出了“强可学习(strongly learnable)”和“弱可学习(weakly learnable)”的概念。指出：在概率近似正确(probably approximately correct，PAC)学习框架中，一个概念(一个类)，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习的。非常有趣的是 Schapire 后来证明 强可学习与弱可学习是等价的 ，也就是说，在 PAC 学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
这样一来，问题便成为，在学习中，如果已经发现了“弱学习算法”，那么能否将它提升(boost)为“强学习算法”。大家知道， 发现弱学习算法通常要比发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升方法时所要解决的问题。 关于提升方法的研究很多，有很多算法被提出。最具代表性的是 AdaBoost 算法(AdaBoost algorithm)。

AdaBoost 算法描述如下：
输入：训练数据集 $T=({\mathit{x}}_{\mathbf{1}},y_1),({\mathit{x}}_{\mathbf{2}},y_2),\cdots ({\mathit{x}}_{\mathit{N}},y_N)$ ，其中 ${\mathit{x}}_{\mathit{i}}\in \mathcal{X}\subseteq {\mathbb{R}}^n,y_i\in \mathcal{Y}=\{-1,+1\},i=1,2,\cdots ,N$ ，其中 $y_i$ 是 ${\mathit{x}}_{\mathit{i}}$ 的类标记；弱学习算法。
输出：最终分类器 $G(x)$ 。
第 1 步，初始化训练数据的权值分布：
$$D_1=\{w_{1,1},w_{1,2},\cdots ,w_{1,i},\cdots ,w_{1,N}\},w_{1,i}=\frac{1}{N},i=1,2,\cdots ,N$$
第 2 步，对 $m=1,2,\cdots ,M$ （ $M$ 表示迭代的次数，即基本分类器个数）依次执行下面过程：
(a) 使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器：
$$G_m:\mathcal{X}\mapsto \{-1,+1\}$$
(b) 计算 $G_m(\mathit{x})$ 在训练数据集上的分类误差率：
$$e_m=P(G_m({\mathit{x}}_{\mathit{i}})\ne y_i)=\sum _{i=1}^N{w}_{m,i}I(G_m({\mathit{x}}_{\mathit{i}})\ne y_i)$$
注：上式中 $I(G_m({\mathit{x}}_{\mathit{i}})\ne y_i)$ 是指示函数，当参数为真（即不等号成立）时其值为 1，否则为 0。
(c) 计算基本分类器 $G_m(\mathit{x})$ 的系数：
$${\alpha }_m=\frac{1}{2}\ln \frac{1-e_m}{e_m}$$
(d) 更新训练数据集的权值分布：
$$D_{m+1}=\{w_{m+1,1},w_{m+1,2},\cdots ,w_{m+1,i},\cdots ,w_{m+1,N}\}$$
其中：
$$w_{m+1,i}=\{\begin{array}{ll}{\displaystyle \frac{w_{m,i}}{Z_m}}{e}^{-{\alpha }_m},& G_m({\mathit{x}}_{\mathit{i}})=y_i\text{注：即当该样本被正确分类时}\\ {\displaystyle \frac{w_{m,i}}{Z_m}}{e}^{{\alpha }_m},& G_m({\mathit{x}}_{\mathit{i}})\ne y_i\text{注：即当该样本被错误分类时}\end{array}$$
利用 $y_i\in \{-1,+1\}$ ，上式还可以写为：
$$w_{m+1,i}={\displaystyle \frac{w_{m,i}}{Z_m}}{e}^{-{\alpha }_m{y}_i{G}_m({\mathit{x}}_{\mathit{i}})},i=1,2,\cdots ,N$$
这里， $Z_m$ 是规范化因子，为：
$$Z_m=\sum _{i=1}^N{w}_{w,i}{e}^{-{\alpha }_m{y}_i{G}_m({\mathit{x}}_{\mathit{i}})}$$
它使 $D_{m+1}$ 成为一个概率分布。
第 3 步，构建基本分类器的线性组合：
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(\mathit{x})$$
得到最终分类器：
$$G(x)=sign(f(x))=sign(\sum _{m=1}^M{\alpha }_m{G}_m(\mathit{x}))$$
算法完。

说明 1：上面算法中， $w_{m+1,i}=\{\begin{array}{ll}{\displaystyle \frac{w_{m,i}}{Z_m}}{e}^{-{\alpha }_m},& G_m({\mathit{x}}_{\mathit{i}})=y_i\\ {\displaystyle \frac{w_{m,i}}{Z_m}}{e}^{{\alpha }_m},& G_m({\mathit{x}}_{\mathit{i}})\ne y_i\end{array}$ 使得被基本分类器 $G_m(\mathit{x})$ 误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较， 误分类样本的权值被放大 $e^{2{\alpha }_m}=\frac{e_m}{1-e_m}$ 倍 。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的样本数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是 AdaBoost 的一个特点。
说明 2：线性组合 $f(x)$ 实现 $M$ 个基本分类器的 加权表决 。系数 ${\alpha }_m$ 表示了基本分类器 $G_m(\mathit{x})$ 的重要性，这里，所有 ${\alpha }_m$ 之和并不为 1。 $f(x)$ 的符号决定实例 $\mathit{x}$ 的类别， $f(x)$ 的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是 AdaBoost 的另一特点。

AdaBoost 算法的实践过程可以形象地用图 1 （图片摘自“The Elements of Statistical Learning(2nd), Chapter 10 Boosting and Additive Trees”）展示。

给定如表 1 所示训练数据。假设弱分类器由 $x<v$ 或 $x>v$ 产生，其阈值 $v$ 使该分类器在训练数据集上分类误差率最低。试用 AdaBoost 算法学习一个强分类器。

解：初始化数据权值分布：
$$D_1=(w_{1,1},w_{1,2},\cdots ,w_{1,10})$$
其中， $w_{1,i}=0.1,i=1,2,\cdots ,10$
迭代过程 1，对 $m=1$ ，有
(a) 在权值分布为 $D_1$ 的训练数据上，容易求得阈值 $v$ 取 2.5 时的分类误差率最低（这时误差点为 $x=6,7,8$ ），故第 1 个基本分类器为：
$$G_1(x)=\{\begin{array}{ll}1,& x<2.5\\ -1,& x>2.5\end{array}$$
(b) $G_1(x)$ 在训练数据集上的误差率： $e_1=P(G_1(x_i)\ne y_i)=0.3$
(c) 计算 $G_1(x)$ 的系数：
$${\alpha }_1=\frac{1}{2}\ln \frac{1-e_1}{e_1}=0.4236$$
(d) 更新训练数据的权值分布：
$$\begin{array}{rl}{w}_{2,i}& =\frac{w_{1,i}}{Z_1}{e}^{-{\alpha }_1{y}_i{G}_1(x)},i=1,2,\cdots ,10\\ D_2& =(w_{2,1},w_{2,2},\cdots ,w_{2,10})\\ & =(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)\end{array}$$
分类器 $sign[f_1(x)]$ 在训练数据集上有 3 个误分类点。
迭代过程 2，对 $m=2$ ，有
(a) 在权值分布为 $D_2$ 的训练数据上，容易求得阈值 $v$ 取 8.5 时的分类误差率最低，故第 2 个基本分类器为：
$$G_2(x)=\{\begin{array}{ll}1,& x<8.5\\ -1,& x>8.5\end{array}$$
(b) $G_2(x)$ 在训练数据集上的误差率： $e_2=P(G_2(x_i)\ne y_i)=0.2143$
(c) 计算 $G_2(x)$ 的系数：
$${\alpha }_2=\frac{1}{2}\ln \frac{1-e_2}{e_2}=0.6496$$
(d) 更新训练数据的权值分布：
$$\begin{array}{rl}{D}_3& =(0.0455,0.0455,0.0455,0.1667,0.1667,0.01667,0.1060,0.1060,0.1060,0.0455)\\ f_2(x)& =0.4236G_1(x)+0.6496G_2(x)\end{array}$$
分类器 $sign[f_2(x)]$ 在训练数据集上有 3 个误分类点。
迭代过程 3，对 $m=3$ ，有
(a) 在权值分布为 $D_3$ 的训练数据上，容易求得阈值 $v$ 取 5.5 时的分类误差率最低，故第 2 个基本分类器为：
$$G_3(x)=\{\begin{array}{ll}1,& x<5.5\\ -1,& x>5.5\end{array}$$
(b) $G_3(x)$ 在训练数据集上的误差率： $e_3=0.1820$
(c) 计算 $G_3(x)$ 的系数：
$${\alpha }_3=0.7514$$
(d) 更新训练数据的权值分布：
$$\begin{array}{rl}{D}_4& =(0.125,0.125,0.125,0.102,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)\end{array}$$
分类器 $sign[f_3(x)]$ 在训练数据集上误分类点个数为 0。
于是，最终分类器为：
$$G(x)=sign[f_3(x)]=sign[0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)]$$

AdaBoost 算法缺点：对异常点非常敏感。 它不断增加误分类样本的权重（指数上升），但如果数据样本是异常点(outlier)，则可能极大的干扰后面基本分类器的学习。

考虑加法模型(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)$ 就是损失函数极小化问题：
$$\underset{{\beta }_m,{\gamma }_m}{min}\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))$$
通常这是一个复杂的优化问题。前向分布算法(forward stagewise algorithm)求解这一优化问题的想法是：因为学习的是加法模型，那如果能够从前向后，每一步只学习一个基函数及其系数，然后逐步逼近上面的优化目标式，那么就可以简化优化的复杂度。具体的，每步只需优化如下损失函数：
$$\underset{\beta ,\gamma }{min}\sum _{i=1}^{N}L(y_i,\beta b(x_i;\gamma ))$$
这样， 前向分布算法将同时求解从 $m=1$ 到 $M$ 的所有参数 ${\beta }_m,{\gamma }_m$ 的优化问题简化为逐次求解各个 ${\beta }_m,{\gamma }_m$ 的优化问题。

AdaBoost 算法可以看作是损失函数为指数损失时的前向分布算法。关于它的推导可参考：
(1) 《统计学习方法，李航著》 8.3.2 前向分步算法与 AdaBoost
(2) The Elements of Statistical Learning(2nd), 10.4 Exponential Loss and AdaBoost

按照损失函数的不同，表 2 给出了 4 种不同的 Boost 方法。

参考：Machine Learning - A Probabilistic Perspective, 16.4 Boosting