AdaBoost原理

## 1 简介

**Boosting**，也称为**增强学习**或**提升法**，是一种重要的学习技术，能够预测精度比随机精度略高的**弱学习器**增强为预测精度高的**强学习器**，这在直接构造**强学习器**非常困难的情况下，为学习算法的设计提供了一种有效的新思路和新方法。其中，最为成功的应用是 $Yoav \space Freund$ 和 $Robert \space Schapire$ 在 1995 年提出的 $AdaBoost$ 算法。

$AdaBoost$ 是英文 $Adaptive \space Boosting$（自适应增强）的缩写，他的自适应在于：**前一个基本分类器被错误分类的样本的均值会增大，而正确分类的样本的均值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中，加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数才确定最终的强分类器**。

## 2 算法步骤

1. 首先，是初始化训练数据的权值分布 $D_1$。假设有 $N$ 个训练样本数据，则每一个训练样本最开始时，都被赋予相同的权值：$\omega=\frac1N$。
2. 然后，训练弱分类器 $h_i$。具体训练过程是：
   1. 如果某个训练样本点被弱分类器 $h_i$**准确地分类**，那么在构造下一个训练集中，它对应的**权值要减小**。
   2. 相反，如果某个训练样本点被弱分类器 $h_i$**错误地分类**，那么他的**权值就应该增大**。
   3. 权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
3. 最后，将各个训练得到的弱分类器组合成一个强分类器。**各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用**。

## 3 算法过程

给定训练数据集：$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$，其中 $y_i$ 属于 $\{1,-1\}$ 用于表示训练样本的类别标签，$i=1,2,...,N$。$AdaBoost$ 的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些分类器组合成一个强分类器。

**相关符号定义：**

* $D_t(i)$：训练样本集的权值分布。
* $\omega_i$：每个训练样本的权值大小。
* $h$：弱分类器。
* $H$ 基本分类器。
* $H_{final}$：最终的强分类器。
* $e$：误差率。
* $\alpha_t$：弱分类器的权重。

**具体流程如下：**

1. 首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值：$\omega_i=\frac1N$，这样训练样本集的初始权值分布 $D_1(i)$：

$$
D_1(i)=(\omega_1,\omega_2,...,\omega_N)=（\frac1N,\frac1N,...,\frac1N）
$$

2. 进行迭代 $t=1,2,...,T$：
   1. 选取一个当前误差率最低的弱分类器 $h$ 作为第 $t$ 个基本分类器 $H_t$，并计算弱分类器 $h_t:X\rightarrow \{-1,1\}$，该弱分类器在分布 $D_t$ 上的误差为

$$
      e_t=P(H_t(x_i) \ne y_i)=\sum_{i=1}^N\omega_{ti}I(H_t(x_i) \ne y_i)
      $$

> 由上述式子可知，$H_t(x)$ 在训练集上的误差率 $e_t$ 就是被 $H_t(x)$ 误分类样本的权值之和。
      >
   2. 计算该弱分类器在最终分类器中所占的权重（弱分类器权重用 $\alpha$ 表示）：

$$
      \alpha_t=\frac12\ln\left(\frac{1-e_t}{e_t}\right)
      $$
   3. 更新训练样本的权值分布 $D_{t+1}$：

$$
      D_{t+1}=\frac{D_t(i)exp(-\alpha_ty_iH_t(x_i))}{Z_t}
      $$

其中 $Z_t$ 为归一化常数 $Z_t=2\sqrt{e_t(1-e_t)}$
   4. 最后，按弱分类器权重 $\alpha_t$ 组合各个弱分类器，即：

$$
      f(x)=\sum_{t=1}^T\alpha_tH(x)
      $$

通过符号函数 $sign$ 的作用，得到一个强分类器为：

$$
      H_{final}=sign(f(x))=sign(\sum_{t=1}^T\alpha_tH(x))
      $$

**相关说明：** 因为权重更新依赖于 $\alpha$，而 $\alpha$ 又依赖于误差率 $e$，所以我们可以直接将权重更新公式用 $e$ 表示。样本权重更新公式：$D_{t+1}=\frac{D_t(i)exp(-\alpha_ty_iH_t(x_i))}{Z_t}$，其中 $Z_t=2\sqrt{e_t(1-e_t)}$：

1. 当样本分错时，$y_iH_t(x_i)=-1$

$$
         D_{t+1}=\frac{D_t(i)exp(\alpha_t)}{Z_t}=\frac{D_t(i)}{Z_t}exp(\frac12\ln(\frac{1-e_t}{e_t}))=\frac{D_t(i)}{X_t}\sqrt{\frac{1-e_t}{e_t}}=\frac{D_t(i)}{2\sqrt{e_t(1-e_t)}}\sqrt{\frac{1-e_t}{e_t}}=\frac{D_t(i)}{2e_t}
         $$
      2. 当样本分对时，$y_iH_t(x_i)=1$

$$
         D_{t+1}=\frac{D_t(i)exp(-\alpha_t)}{Z_t}=\frac{D_t(i)}{Z_t}exp(-\frac12\ln(\frac{1-e_t}{e_t}))=\frac{D_t(i)}{X_t}\sqrt{\frac{e_t}{1-e_t}}=\frac{D_t(i)}{2\sqrt{e_t(1-e_t)}}\sqrt{\frac{e_t}{1-e_t}}=\frac{D_t(i)}{2(1-e_t)}
         $$

综合上面的推导，可得样本分错与分对时，其权值更新的公式为：

1. 错误分类样本，权值更新：$D_{t+1}(i)=\frac{D_t(i)}{2\varepsilon_t}$
      2. 正确分类样本，权值更新：$D_{t+1}(i)=\frac{D_t(i)}{2(1-\varepsilon_t)}$

## 4 实例讲解

**例：给定如图所示的训练样本，弱分类器采用平行于坐标轴的直线，用 $AdaBoost$ 算法实现强分类。**

![](/media/202104/2021-04-07_093917.png)

### 4.1 数据分析

将这 10 个样本作为训练数据，根据 $X$ 和 $Y$ 的对应关系，可以把这 10 个数据分为两类，图中用“+”表示类别 1，用“O”表示类别-1。本例使用水平或者垂直的直线作为分类器，图中已经给出了三个弱分类器，即

$$
h_1=\left\{\begin{array}{l}1\;,\;X_1<2.5\\-1\;,\;X_1>2.5\end{array},\;\right.h_2=\left\{\begin{array}{l}1\;,\;X_1<8.5\\-1\;,\;X_1>8.5\end{array},\;h_3=\right.\left\{\begin{array}{l}1\;,\;X_1>6.5\\-1\;,\;X_1<6.5\end{array}\right.
$$

### 4.2 初始化

首先需要初始化训练样本数据的权值分布，每一个训练样本最开始时都被赋予相同的权值：$\omega_i=\frac1N$，这样训练样本集的初始权值分布 $D_1(i)$：

令每个权值 $\omega_1(i)=\frac1N=0.1$，其中，$N=10,i=1,2,...,10$，然后分别对于 $t=1,2,3,...$ 等值进行迭代（$t$ 表示迭代次数，表示第 $t$ 轮），下表已经给出训练样本的权值分布情况：

![](/media/202104/2021-04-07_100342.png)

### 4.3 进行迭代

#### 4.3.1 第一次迭代 $t=1$

初始的权值分布 $D_1$ 为 $\frac1N$（10 个数据，每个数据的权值皆初始化为 0.1）：

$$
D_1=[0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1]
$$

在权值分布 $D_1$ 的情况下，取已知的三个弱分类器 $h_1,h_2$ 和 $h_3$ 中误差率最小的分类器作为第一个基本分类器 $H_1(x)$（三个弱分类器的误差率都是 0.3，那就取第 1 个吧）：

$$
H_1=\left\{\begin{array}{l}1\;,\;X_1<2.5\\-1\;,\;X_1>2.5\end{array}\right.
$$

> 某个分类器的误差率等于该分类器的被**错分样本的权值之和**。

在分类器 $H_1(x)=h_1$ 情况下，样本点 `5、7、8` 被错分，因此基本分类器 $H_1(x)$ 的误差率为：

$$
e_1=(0.1+0.1+0.1)=0.3
$$

根据误差率 $e_1$ 计算 $H_1$ 的权重：

$$
\alpha_1=\frac12\ln(\frac{1-e_1}{e_1})=\frac12\ln(\frac{1-0.3}{0.3})=0.4236
$$

**这个 $\alpha_1$ 代表 $H_1(x)$ 在最终的分类函数中所占的权重为 0.4236。**

可见，**被误分类样本的权值之和影响误差率 $e$，误差率 $e$ 影响基本分类器在最终分类器中所占的权重 $\alpha$。
![](/media/202104/2021-04-07_102036.png)**

然后，更新训练样本数据的权值分布，用于下一轮的迭代：

1. 对于正确分类的训练样本 `1、2、3、4、6、9、10`（共 7 个）的权值更新为：

$$
   D_2=\frac{D_1}{2(1-\varepsilon_1)}=\frac1{10}\times\frac1{x\times(1-0.3)}=\frac1{14}
   $$

> 可见，**正确分类**的样本的权值由原来的 $\frac1{10}$ 减小到 $\frac1{14}$。
   >
2. 对于所有错误分类的训练样本 `5、7、8`（共 3 个）的权值更新为：

$$
   D_2(i)=\frac{D_1(i)}{2\varepsilon_1}=\frac1{10}\times\frac1{2\times0.3}=\frac16
   $$

> 可见，**错误分类**的样本的权值由原来的 $\frac1{10}$ 增大到 $\frac16$。
   >

这样，第一轮迭代后，最后得到的各个样本数据新的权值分布为：

$$
D_2=[\frac1{14},\frac1{14},\frac1{14},\frac1{14},\frac16,\frac1{14},\frac16,\frac16,\frac1{14},\frac1{14}]
$$

由于样本数据 `5、7、8` 被 $H_1(x)$ 分错了，所以他们的权值由之前的 0.1 增大到 $\frac16$；反之，其他数据皆被分正确，所以他们的权值皆由之前的 0.1 减小到 $\frac1{14}$，下表给出了权值分布的变换情况：

![](/media/202104/2021-04-07_103828.png)

> 用浅绿色底纹标记出来的表格，是被 $H_1(x)$ 分错的样本 `5、7、8`；没有底纹（白色的）是正确分类的样本 `1、2、3、4、6、9、10`。

可得**分类函数**为：

$$
f_1(x)=\alpha_1H_1(x)=0.4236H_1(x)
$$

此时，组合一个基本分类器 $sign(f_1(x))$ 作为强分类器在训练集上有 3 个误分类点 `5、7、8`，此时强分类器的训练错误率为：0.3。

#### 4.3.2 第二次迭代 $t=2$

在权值分布 $D_2$ 的情况下，再取 3 个弱分类器 $h_1、h_2$ 和 $h_3$ 中误差率最小的分类器作为第二个基本分类器 $H_2(x)$：

1. 当取弱分类器 $h_1=X_1=2.5$ 时，此时被错分的样本点为 `5、7、8`，误差率为：

$$
   e=\frac16+\frac16+\frac16=\frac12
   $$
2. 当取弱分类器 $h_2=X_1=8.5$ 时，此时被错分的样点为 `3、4、6`，误差率为：

$$
   e=\frac1{14}+\frac1{14}+\frac1{14}=\frac3{14}
   $$
3. 当取弱分类器 $h_3=X_1=6.5$ 时，此时被错分的样点为 `1、2、9`，误差率为：

$$
   e=\frac1{14}+\frac1{14}+\frac1{14}=\frac3{14}
   $$

![](/media/202104/2021-04-07_105812.png)

因此，取当前最小的分类器 $h_2$ 作为第 2 个分类器 $H_2(x)$：

$$
H_1=\left\{\begin{array}{l}1\;,\;X_1<8.5\\-1\;,\;X_1>8.5\end{array}\right.
$$

显然，$H_2(x)$ 把样本 `3、4、6` 分错了，根据 $D_2$ 可知他们的权值为：

$$
D_2(3)=\frac1{14},D_2(4)=\frac1{14},D_2(6)=\frac1{14}
$$

所以 $H_2(x)$ 在训练数据集上的误差率为：

$$
e_2=P(H_2(x_i) \ne y_i)=3\times\frac1{14}=\frac3{14}（即权值之和）
$$

根据误差率 $e_2$ 计算 $H_2$ 的权重为：

$$
\alpha_2=\frac12=\ln(\frac{1-e_2}{e_2})=0.6496
$$

更新训练样本数据的权值分布：

1. 对于**正确分类**的样本权值更新为：

$$
   D_3(i)=\frac{D_2(i)}{2(1-e_2)}=\frac7{11}D_2(i)
   $$
2. 对于**错误分类**的权值更新为：

$$
   D_3(i)=\frac{D_2(i)}{2e_2}=\frac73D_2(i)
   $$

这样，第 2 轮迭代后，最后得到各个样本数据新的权值分布为：

$$
D_3=[\frac1{22},\frac1{22},\frac16,\frac16,\frac7{66},\frac7{66},\frac1{22},\frac1{22}]
$$

下表给出了权值分布的变换情况：

![](/media/202104/2021-04-07_112606.png)

可得**分类函数**：

$$
f_2(x)=0.4236H_1(x)+0.6496H_2(x)
$$

此时，组合两个基本分类器 $sign(f_2(x))$ 作为强分类器在训练数据集上有 3 个误分类点 `3、4、6`，此时强分类器的训练错误率为：0.3。

#### 4.3.3 第三次迭代 $t=3$

按照第二次迭代的方法再次进行迭代，最终得到 $H_3(x)$ 在训练数据集上的误差率为：

$$
e_3=P(H_3(x_i) \ne y_i)=3\times\frac1{22}=\frac3{22}（即权值之和）
$$

根据误差率 $e_3$ 计算 $H_3$ 的权重为：

$$
\alpha_3=\frac12\ln(\frac{1-e_3}{e_3})=0.9229
$$

更新训练样本数据的权值分布：

1. 对于**正确分类**的样本权值更新为：

$$
   D_4(i)=\frac{D_3(i)}{2(1-e_3)}=\frac{11}{19}D_3(i)
   $$
2. 对于**错误分类**的权值更新为：

$$
   D_4(i)=\frac{D_3(i)}{2e_3}=\frac{11}{3}D_3(i)
   $$

这样，第 3 轮迭代后，得到各个样本数据新的权值分布为：

$$
D_4=[\frac16,\frac16,\frac{11}{114},\frac{11}{114},\frac{7}{114},\frac{11}{114},\frac{7}{114},\frac{7}{114},\frac16,\frac{1}{38}]
$$

下表给出了权值分布的变换情况：

![](/media/202104/2021-04-07_115605.png)

可得**分类函数**：

$$
f_3(x)=0.4236H_1(x)+0.6496H_2(x)+0.9229H_3(x)
$$

此时，组合三个基本分类器 $sign(f_3(x))$ 作为强分类器，在训练数据集上有 0 个误分类点。至此，整个训练结束。

整合所有分类器，可得最终的强分类器为：

$$
H_{final}=sign(\sum_{t=1}^{T}\alpha_tH_t(x))=sign(0.4236H_1(x)+0.6496H_2(x)+0.9229H_3(x))
$$

**这个强分类器 $H_{final}$ 对训练样本的错误率为 0。**

## 5 优缺点

### 5.1 优点

1. **很好的利用了弱分类器进行级联。**
2. **可以将不同的分类算法作为弱分类器。**
3. 具有**很高的精度**。
4. 相对于 $Bagging$ 和 $Random \space Forest$ 算法，$AdaBoost$**充分考虑了每个分类器的权重**。

### 5.2 缺点

1. **迭代次数也就是弱分类器数目不太好设定，可以使用交叉验证来进行确定。**
2. 在训练过程中，$AdaBoost$**会使得难于分类样本的权值呈指数增长，训练将会过于偏向这类困难的样本，导致 $AdaBoost$ 算法易受噪声干扰。**
3. $AdaBoost$**依赖于弱分类器，而弱分类器的训练时间往往很长。**

## **6 参考文献**

1. [（十三）通俗易懂理解——Adaboost 算法原理](https://zhuanlan.zhihu.com/p/41536315)。
2. [机器学习常用算法优点及缺点总结](https://blog.csdn.net/u012422446/article/details/53034260)。