前言

集成学习(Ensemble Learning)是利用多个学习器来实现学习任务的一种机器学习模型，集成学习目前已经涉及到各个领域，并有不错的学习效果。AdaBoost是集成学习与提升方法中的代表，本文将介绍AdaBoost的算法原理

一、AdaBoost基本思想

1.弱分类器和强分类器

弱分类器：比较粗糙的分类规则，分类的正确率仅比随机分类略好
强分类器：精确的分类规则，分类的正确率非常高

2.核心思想

提升方法的基本思想很简单，就是“三个臭皮匠顶一个诸葛亮”。因为求弱分类器比求强分类器要容易的多，从弱学习算法出发，得到一系列的弱分类器，然后将这些弱分类器组合起来构成一个强分类器，达到分类效果。
在这里插入图片描述
给定一个数据集，如图，按层进行学习（每条虚线上均为一层弱分类器）。对于每一层来说，数据集是不变的，改变的是权重w(i)（AdaBoost根据样本分类对错改变权重，也即前一层分类对的下一层没必要过多关注，在下一层所占权重变小，前一层分类错误的在下一层被重点关注，所占权重大）。每一层弱分类器学习完成后，根据分类误差率得到相应的权值（分类误差率小的占最后总表决权值大，分类误差率大的占最后总表决权小）。最终，将得到的所有弱分类器按权重线性组合输出。

二、算法实现

1. 引入数据集

假设给定一个二类分类的训练数据集T = {( $x_1, y_1), (x_2, y_2),...,(x_N, y_N)$ }，其中，每个样本点由实例和标签组成。实例 $x_i \in$ X $\subseteq$ $R^n$ ，标签 $y_i$ $\in$ Y = {-1, +1}，X是实例空间，Y是标签集合。

2. 输出最终分类器

2.1 初始化训练数据的权值

$D_1$ = （ $w_{11},...,w_{1i},...,w_{1N}$ ）， $w_{1i}$ = $\frac{1}{N}$ ，i = 1, 2, 3,…,N

2.2 对m = 1,2,…,M

（a）使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器 $G_m(x)$ ：X $\rightarrow$ {-1, +1}

（b）计算 $G_m(x)$ 在训练数据集上的分类误差率

$e_m$ = $\displaystyle\sum_{i=1}^{N} P(G_m(x_i) \neq y_i) = \displaystyle\sum_{i=1}^{N}w_{mi}I(G_m(x_i) \neq y_i)$ ①

其中，I 表示 $G_m(x_i) \neq y_i$ 的实例个数， $e_m$ = $\displaystyle\sum_{i=1}^{N} P(G_m(x_i) \neq y_i) = \displaystyle\sum_{G_m(x_i) \neq y_i}w_{mi}$ 这里， $w_{mi}$ 表示第 m 轮中第 i 个实例的权值，所有的权值之和为1（ $\displaystyle\sum_{i=1}^{N} w_{mi}= 1$ ）。 $G_m(x)$ 在加权的训练数据集上的分类误差率是被 $G_m(x)$ 误分类样本的权值之和，所以数据权值分布 $D_m$ 在每一轮随基本分类器 $G_m(x)$ 分类误差率的改变而更新

（c）计算 $G_m(x)$ 系数

$\alpha_m$ = $\frac{1}{2}ln\frac{1-e_m}{e_m}$ ②

$\alpha_m$ 是所有基本分类器在最终分类器中的权重，由②可知，当 $e_m\le\frac{1}{2}$ 时， $\alpha_m \geq 0$ , $e_m \in (0, 1)$ ，该函数为单减函数，所以分类误差率 $e_m$ 越小，最终所占权重 $\alpha_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 = \displaystyle\sum_{i=1}^{N} w_{mi}\exp(-\alpha_my_iG_m(x_i))$ ⑤
它使 $D_{m+1}$ 成为一个概率分布。

上式④可以写为： $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{1-e_m}{e_m}$ 倍。因此，误分类的样本在下一轮将更多的被关注，而正确分类的在下一轮被关注更少。

2.3 构建基本分类器（弱分类器）的线性组合

$\displaystyle\sum_{m=1}^{M} \alpha_mG_m(x_i)$ ⑥
得到最终的分类器
$sign(\displaystyle\sum_{m=1}^{M}\alpha_mG_m(x))$ ⑦

三、AdaBoost训练误差分析

AdaBoost最终分类器的训练误差

$\frac{1}{N}\displaystyle\sum_{i=1}^{N}I(G(x_i) \neq y_i) \le \frac{1}{N}\displaystyle\sum_{i}\exp(-y_if(x_i)) = \displaystyle\prod_{m}Z_m$

该定理说明，可以在每一轮选取适当的 $G_m$ 使得 $Z_m$ 最小，从而使训练误差下降最快。

$\displaystyle\prod_{m}Z_m = \displaystyle\prod_{m=1}^{M}[2\sqrt{e_m(1-e_m)}] = \displaystyle\prod_{m=1}^{M}\sqrt{(1-4\gamma_m^{2})} \le \exp(-2\displaystyle\sum_{m=1}^{M}\gamma_m^{2})$ ，其中 $\gamma_m = \frac{1}{2} - e_m$