Adaboost

简述一下 Adaboost 的权值更新方法

对提升方法来说，有两个问题需要回答：

1. 在每一轮如果改变训练数据的权值或概率分布；
2. 如何将弱分类器组合成一个强分类器。

对于第一个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，于是，分类问题就被一系列的弱分类器“分而治之”。

至于第二个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率较大的弱分类器的权值，使其在表决中起较小的作用。

AdaboostBoost的算法的框架如下图所示 具体来说，整个AdaBoost算法包括以下三个步骤：

• 1）初始化训练样本的权值分布。 如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：。
• 2）训练弱分类器。具体训练过程中，如果某个样本已经被准确地分类，那么在构造下一个训练集中，它的权值就会被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本被用于训练下一个分类器，整个训练过程如果迭代地进行下去，使得分类器在迭代过程中逐步改进。
• 3）将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中权重较大，否则较小。得到最终分类器。

推导一下Adaboost的样本权重更新公式

假定给定一个二类分类的训练数据集

其中，AdaBoost从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成一个强分类器。

步骤一：首先，初始化训练数据的权值分布。

步骤二：在每一轮顺次执行下列操作：

• 1）使用当前权值分布为的训练数据集，学习得到基分类

• 2）计算上一步得到的基分类器在训练数据集上的分类误差率为
  这里表示第轮中第个实例的权值，。这表明，在加权的训练数据集上的分类误差率是被误分类样本的权值之和，由此可以看出数据权值分布与基本分类器的分类误差率的关系。
• 3）计算前面的权重系数，该系数表示在最终分类器中的重要程度，目的在于使我们得到基分类器在最终分类器中所占的权值，系数计算公式如下： $$ a_m=\frac{1}{2}\log\frac{1-e_m}{e_m} $$ 这里的对数是自然对数，由表达式可知，当时，，并且随着的减小而增大，意味着分类误差越小的基本分类器在最终分类器的作用越大，而则刚好相反，这正好验证了集成学习中每个个体分类器的分类精度必须大于0.5的前提条件。
• 4）更新训练数据集的权值分布为下一轮作准备
  其中
  我们也可以写成：

$$w_{m+1,i} = \left{\begin{matrix} \frac{w_{mi}}{Z_m}e^{-a_m}\ , & G_m\left(x_i\right)=y_i\ \frac{w_{mi}}{Z_m}e^{a_m}\ , & G_m\left(xi\right)\ne y_i\ \end{matrix}\right. $$

由此可知，被基本分类器误分类样本的权值得以扩大，而被正确分类样本的权值得以缩小。两两比较，误分类样本的权值倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作业，这是AdaBoost的一个特点。 这里我们还引入了一个规范化因子，它的作用在于使成为一个概率分布。具体公式为

重复步骤二中的1至4步骤，得到一系列的权重参数和基分类器。

步骤三：将上一步得到的基分类器根据权重参数线性组合

得到最终分类器

线性组合实现了个基本分类器的加权表决。系数表示了基本分类器的重要性，这里，所有的之和并不为1。的符号决定实例的类，的绝对值表示分类的确信度，利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。

训练过程中，为何每轮训练一直存在分类错误的问题，整个Adaboost却能快速收敛？

每轮训练结束后，AdaBoost 会对样本的权重进行调整，调整的结果是越到后面被错误分类的样本权重会越高。而后面的分类器为了达到较低的带权分类误差，会把样本权重高的样本分类正确。这样造成的结果是，虽然每个弱分类器可能都有分错的样本，然而整个 AdaBoost 却能保证对每个样本进行正确分类，从而实现快速收敛。

Adaboost 的优缺点？

优点：

• 能够基于泛化性能相当弱的的学习器构建出很强的集成，不容易发生过拟合。

缺点：

• 对异常样本比较敏感，异常样本在迭代过程中会获得较高的权值，影响最终学习器的性能表现。

AdaBoost 与 GBDT 对比有什么异同？

相同：

• 都是 Boosting 家族成员，使用弱分类器；
• 都使用前向分布算法；

不同：

• 迭代思路不同：Adaboost 是通过提升错分数据点的权重来弥补模型的不足（利用错分样本），而 GBDT 是通过算梯度来弥补模型的不足（利用残差）；
• 损失函数不同：AdaBoost 采用的是指数损失，GBDT 使用的是绝对损失或者 Huber 损失函数；