原理

自适应算法（AdaBoost）是 Boosting 族算法最著名的代表。

核心步骤

AdaBoot 算法的两个核心步骤：

每一轮中如何改变训练数据的权值？
AdaBoost 算法提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。于是那些没有得到正确分类的数据由于权值的加大而受到后一轮的弱分类器的更大关注。
最后如何将一系列弱分类器组合成一个强分类器？AdaBoost 采用加权多数表决的方法：

加大分类误差率较小的弱分类器的权值，使得它在表决中起较大作用。
减小分类误差率较大的弱分类器的权值，使得它在表决中起较小的作用。

特点

AdaBoost算法有两个特点：

不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同作用。

因此 AdaBoost 要求基本学习器能够对特定的数据分布进行学习，这一般是在学习的时候为每个训练样本赋予一个权重。
对于无法接受带权样本的基本学习算法，则可以通过“重采样法”来处理：即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样的样本集对基本学习器进行训练。
一般而言这两者没有显著的优劣差别。

利用基本分类器的线性组合构成最终分类器。

自适应性

AdaBoost 算法具有自适应性，即它能够自动适应弱分类器各自的训练误差率，这也是它的名字（适应的提升）的由来。

算法

输入与输出

输入

训练数据集 AdaBoost - 图1 ，其中 AdaBoost - 图2
弱学习器

输出

最终分类器 AdaBoost - 图3

1 初始化训练集的权值分布

AdaBoost - 图4

2 训练模型与更新系数

对于第 AdaBoost - 图5 次训练与系数更新， AdaBoost - 图6

(a) 使用具有权值分布的训练数据集学习，得到基本分类器：

AdaBoost - 图8

(b) 计算

AdaBoost - 图10 **

它就是所有误分类点的权重之和。
这里应该有一个判断准则：若 AdaBoost - 图11 ，算法终止，构建失败；当 AdaBoost - 图12 时，算法继续。

(c) 计算的系数：

这里的对数是自然对数。

(d) 更新训练集的权值分布：

AdaBoost - 图15 **

其中， AdaBoost - 图16 是规范化因子，它使 AdaBoost - 图17 成为一个概率分布，即训练集各权值和为 1。

3 构建基本分类器的线性组合

AdaBoost - 图18

算法说明

首先给出公式中（2）和（4）的函数图像，其中自变量均为分类误差率 AdaBoost - 图19 ：

（1）分类误差率要求

首先，为什么在（1）中我们要求分类误差率 AdaBoost - 图21 呢？这是因为：
第一，一个随机分类器的误差率均值即为 AdaBoost - 图22 ，如果一个分类器误差率比 AdaBoost - 图23 还大，这就说明这个分类器不仅毫无作用，反而有副作用，这时候一定是基学习器或数据集哪里出问题了，算法停止，重新审视。

第二，从另一个角度，构建的基本分类器的线性组合 AdaBoost - 图24 的系数应该为正，即基本分类器起作用。那么根据（2）公式，即图中的绿色图像可以看出， AdaBoost - 图25 。

（2）基本分类器权重系数

还是据（2）公式，即图中的绿色图像在 AdaBoost - 图26 部分，基本分类器的权重系数 AdaBoost - 图27 会随着分类误差率 AdaBoost - 图28 的变小而增大，即 AdaBoost - 图29 越小，对应 AdaBoost - 图30 的权重 AdaBoost - 图31 越大。

由于 AdaBoost - 图32 是分类误差率 AdaBoost - 图33 的单调递减函数，因此：

AdaBoost 加大分类误差率较小的弱分类器的权值，使得它在表决中起较大作用。
AdaBoost 减小分类误差率较大的弱分类器的权值，使得它在表决中起较小的作用。

（4）训练集权重更新

对于（4），当 AdaBoost - 图34 对训练集中的第 AdaBoost - 图35 个样本预测正确时：

AdaBoost - 图36 ，即图中红色图像，是 AdaBoost - 图37 的单增函数。由于我们之前就提到过，对于正确分类的样本，下一次学习时其样本权重是要（相对）降低的。但此时，分类错误率 AdaBoost - 图38 越高，模型就不能对正确样本权重降得过低。

当 AdaBoost - 图39 对训练集中的第 AdaBoost - 图40 个样本预测错误时：
AdaBoost - 图41 ，即图中橙色图像，是 AdaBoost - 图42 的单减函数。对于错误分类的样本，下一次学习时其样本权重是要（相对）提高的。此时，分类错误率 AdaBoost - 图43 越高，模型就不能对错误样本权重定得过高。

两者比较，误分类样本的权重是正确分类样本的权重的 AdaBoost - 图44 倍。于是误分类样本在下一轮学习中权重更大（相对的）。

（6）过拟合

为防止过拟合，AdaBoost 通常会加入正则化项。该正则化项称作步长或者学习率，定义为 AdaBoost - 图45 。考虑正则化项之后，模型的更新方式为：

AdaBoost - 图46

误差分析

AdaBoost 最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率，也就是选取合适 AdaBoost - 图47 后，随着 AdaBoost - 图48 增大，训练误差 AdaBoost - 图49

证明以上结论，需要以下几个定理：

定理1：AdaBoost 的训练误差界。AdaBoost 算法最终分类器的训练误差界为：

AdaBoost - 图50

定理2：二类分类问题 AdaBoost 的训练误差界

AdaBoost - 图51 **

这里， AdaBoost - 图52 。

推论1：如果存在 AdaBoost - 图53 ，对所有 AdaBoost - 图54 有 AdaBoost - 图55 ，则

AdaBoost - 图56

这表明在此条件下 AdaBoost的训练误差是以指数速率下降的。这一性质当然是很有吸引力的。

注意，AdaBoost 算法不需要知道下届 AdaBoost - 图57 。与早期的提升方法不同，AdaBoost 具有自适应性，即它能适应弱分类器各自的训练误差率。这也是它的名称的由来。

上述定理都只是关于训练误差的分析，实际应用中更关系测试集的误差。AdaBoost 算法也会出现过拟合，此时训练误差为 0 但是测试集的误差较大。

当 AdaBoost 的基础分类器比较复杂时，AdaBoost 很容易陷入过拟合。但是当 AdaBoost 的基础分类器比较简单时，AdaBoost 反而难以陷入过拟合。这也是为什么 AdaBoost 的基础分类器经常选择使用树桩的原因。

References

[1] http://www.huaxiaozhuan.com/统计学习/chapters/6_ensemble_learning.html [2] https://heshenghuan.github.io/2016/01/17/AdaBoost%E7%AC%94%E8%AE%B0/ [3] https://zhuanlan.zhihu.com/p/42018105 [4] https://zhuanlan.zhihu.com/p/27126737 [5] 《统计学习方法》李航