Adaboost总结

一、简介

　　Boosting 是一类算法的总称，这类算法的特点是通过训练若干弱分类器，然后将弱分类器组合成强分类器进行分类。为什么要这样做呢？因为弱分类器训练起来很容易，将弱分类器集成起来，往往可以得到很好的效果。俗话说，"三个臭皮匠，顶个诸葛亮"，就是这个道理。这类 boosting 算法的特点是各个弱分类器之间是串行训练的，当前弱分类器的训练依赖于上一轮弱分类器的训练结果。各个弱分类器的权重是不同的，效果好的弱分类器的权重大，效果差的弱分类器的权重小。值得注意的是，AdaBoost 不止适用于分类模型，也可以用来训练回归模型。这需要将弱分类器替换成回归模型，并改动损失函数。

进入正题之前，先来看Adaboost的两个核心问题：

1. 在每一轮学习之前，如何改变训练数据的权值分布？
2. 如何将一组弱分类器组合成一个强分类器？

针对第一个问题，Adaboost算法的做法是：

提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。如此，那些没有得到正确分类的样本，由于其权值加大而受到后一轮的弱分类器的更大关注。

第二个问题，弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地：

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

AdaBoost算法的巧妙之处就在于它将这些学习思路自然并且有效地在一个算法里面实现。

几个误区：

• Adaboost算法基本原理就是将多个弱分类器（弱分类器一般选用单层决策树）进行合理的结合，使其成为一个强分类器。
• 弱学习器：在二分情况下弱分类器的错误率会低于50%。其实任意的分类器都可以做为弱分类器，比如之前介绍的KNN、决策树、Naive Bayes、logiostic回归和SVM都可以。

1. Adaboost 的算法的流程？

重点关注以下4个问题

• 如何计算学习误差率e?
• 如何得到弱学习器权重系数α?
• 如何更新样本权重D?
• 使用何种结合策略？

　　本节主要介绍Adaptive Boosting。首先通过讲一个老师教小学生识别苹果的例子，来引入Boosting的思想，即把许多“弱弱”的hypotheses合并起来，变成很强的预测模型。然后重点介绍这种算法如何实现，关键在于每次迭代时，给予样本不同的系数u，宗旨是放大错误样本，缩小正确样本，得到不同的小矩g。并且在每次迭代时根据错误ϵ值的大小，给予不同gt不同的权重。最终由不同的gt进行组合得到整体的预测模型G。实际证明，Adaptive Boosting能够得到有效的预测模型。

（1）引入

　　我们先来看一个简单的识别苹果的例子，老师展示20张图片，让6岁孩子们通过观察，判断其中哪些图片的内容是苹果。从判断的过程中推导如何解决二元分类问题的方法。

　　显然这是一个监督式学习，20张图片包括它的标签都是已知的。首先，学生Michael回答说：所有的苹果应该是圆形的。根据Michael的判断，对应到20张图片中去，大部分苹果能被识别出来，但也有错误。其中错误包括有的苹果不是圆形，而且圆形的水果也不一定是苹果。如下图所示：

　　上图中蓝色区域的图片代表分类错误。显然，只用“苹果是圆形的”这一个条件不能保证分类效果很好。我们把蓝色区域（分类错误的图片）放大，分类正确的图片缩小，这样在接下来的分类中就会更加注重这些错误样本。

　　然后，学生Tina观察被放大的错误样本和上一轮被缩小的正确样本，回答说：苹果应该是红色的。根据Tina的判断，得到的结果如下图所示：

　　上图中蓝色区域的图片一样代表分类错误，即根据这个苹果是红色的条件，使得青苹果和草莓、西红柿都出现了判断错误。那么结果就是把这些分类错误的样本放大化，其它正确的样本缩小化。同样，这样在接下来的分类中就会更加注重这些错误样本。

　　接着，学生Joey经过观察又说：苹果也可能是绿色的。根据Joey的判断，得到的结果如下图所示：

　　上图中蓝色区域的图片一样代表分类错误，根据苹果是绿色的条件，使得图中蓝色区域都出现了判断错误。同样把这些分类错误的样本放大化，其它正确的样本缩小化，在下一轮判断继续对其修正。

　　后来，学生Jessica又发现：上面有梗的才是苹果。得到如下结果：

　　经过这几个同学的推论，苹果被定义为：圆的，红色的，也可能是绿色的，上面有梗。从一个一个的推导过程中，我们似乎得到一个较为准确的苹果的定义。虽然可能不是非常准确，但是要比单一的条件要好得多。也就是说把所有学生对苹果的定义融合起来，最终得到一个比较好的对苹果的总体定义。这种做法就是我们本节课将要讨论的演算法。这些学生代表的就是简单的hypotheses gt,将所有gt融合，得到很好的预测模型G。例如，二维平面上简单的hypotheses (水平线和垂直线)，这些简单gt最终组成的较复杂的分类线能够较好地将正负样本完全分开，即得到了好的预测模型。

　　

　　所以，上个苹果的例子中，不同的学生代表不同的hypotheses gt​；最终得到的苹果总体定义就代表hypothesis G；而老师就代表演算法A，指导学生的注意力集中到关键的例子中（错误样本），从而得到更好的苹果定义。

（2）Diversity by Re-weighting

　　Bagging的核心是bootstrapping，通过对原始数据集D不断进行bootstrap的抽样动作，得到与D类似的数据集D^{^}_t ，每组D^{^}_t 都能得到相应的gt，从而进行aggregation的操作。现在，假如包含四个样本的D经过bootstrap，得到新的D^{^}_t , 如下：

　　参数u相当于是权重因子，当D^{^}t 中第i个样本出现的次数越多的时候，那么对应的ui越大，表示在error function中对该样本的惩罚越多。所以，从另外一个角度来看bagging，它其实就是通过bootstrap的方式，来得到这些ui 值，作为犯错样本的权重因子，再用base algorithn最小化包含ui 的error function，得到不同的gt。这个error function被称为bootstrap weighted error。

　　这种算法叫做Weightd Base Algorithm，目的就是最小化bootstrap-weighted error。

 　　其实，这种weightd base algorithm我们之前就见过类似的算法形式。例如在soft-margin SVM中，我们引入允许犯错的项，同样可以将每个点的error乘以权重因子un 。加上该项前的参数C，经过QP，最终得到0≤α_n≤C_un，有别于之前介绍的0≤α≤C。这里的un 相当于每个犯错的样本的惩罚因子，并会反映到αn 的范围限定上。

　　同样在logistic regression中，同样可以对每个犯错误的样本乘以相应的un ，作为惩罚因子。un表示该错误点出现的次数，un越大，则对应的惩罚因子越大，则在最小化error时就应该更加重视这些点。

　　知道了u的概念后，我们知道不同的u组合经过base algorithm得到不同的gt 。那么如何选取u，使得到的gt之间有很大的不同呢？之所以要让所有的gt差别很大，是因为上节课aggregation中，我们介绍过gt越不一样，其aggregation的效果越好，即每个人的意见越不相同，越能运用集体的智慧，得到好的预测模型。

　　为了得到不同的g_t，我们先来看看g_t和g_t+1是怎么得到的：

　　乍看上面这个式子，似乎不好求解。但是，我们对它做一些等价处理，其中分式中分子可以看成gt作用下犯错误的点，而分母可以看成犯错的点和没有犯错误的点的集合，即所有样本点。其中犯错误的点和没有犯错误的点分别用橘色方块和绿色圆圈表示：

（3）Adaptive Boosting Algorithm

　　接下来的内容，我们将对上面的第二个问题进行探讨，研究一种算法，将所有的g(t)进行linear组合。方法是计算g(t)的同时，就能计算得到其线性组合系数α_t ，即aggregate linearly on the fly。这种算法使最终求得g_t+1 的时候，所有gt的线性组合系数α也求得了，不用再重新计算α了。这种Linear Aggregation on the Fly算法流程为：

　　综上所述，完整的adaptive boosting（AdaBoost）Algorithm流程如下：

　　从我们之前介绍过的VC bound角度来看，AdaBoost算法理论上满足：

（4）举例：

【例1】

　　上一小节我们已经介绍了选择一个“弱弱”的算法A（ϵt​≤ϵ<21​，比乱猜好就行），就能经过多次迭代得到E_in​=0。我们称这种形式为decision stump模型。下面介绍一个例子，来看看AdaBoost是如何使用decision stump解决实际问题的。如下图所示，二维平面上分布一些正负样本点，利用decision stump来做切割。

初始：

迭代五次：

 可以看到，经过5次迭代之后，所有的正负点已经被完全分开了，则最终得到的分类线为：

【例2】

　　另外一个例子，对于一个相对比较复杂的数据集，如下图所示。它的分界线从视觉上看应该是一个sin波的形式。如果我们再使用AdaBoost算法，通过decision stump来做切割。在迭代切割100次后，得到的分界线如下所示。

 　　可以看出，AdaBoost-Stump这种非线性模型得到的分界线对正负样本有较好的分离效果。课程中还介绍了一个AdaBoost-Stump在人脸识别方面的应用：

【例3】

2.Adaboost 如何选择特征 ？

3.Adaboost 如何构建特征 ？

4.Adaboost 如何用于分类？

5.Adaboost 如何用于回归？

【拓展】为什么每个样本最终的结果取分类器得到所有值排序之后的中位数作为最终的结果？

答：因为中位数的值能够使得误差最小，具体证明见下图

6.Adaboost 通过什么方式减少误差 ？

7.Adaboost 的效果相比于传统的LR，SVM效果为什么好一些 ？

8.Adaboost 如何加速训练？

9.Adaboost 的参数有哪些，如何调参 ？

 （1）框架参数

base_estimator:A理论上可以选择任何一个分类或者回归学习器，不过需要支持样本权重。我们常用的一般是CART决策树或者神经网络MLP。默认是决策树.另外有一个要注意的点是，如果我们选择的AdaBoostClassifier算法是SAMME.R，则我们的弱分类学习器还需要支持概率预测，也就是在scikit-learn中弱分类学习器对应的预测方法除了predict还需要有predict_proba。

algorithm:这个参数只有AdaBoostClassifier有。主要原因是scikit-learn实现了两种Adaboost分类算法，SAMME和SAMME.R。两者的主要区别是弱学习器权重的度量，SAMME使用了和我们的原理篇里二元分类Adaboost算法的扩展，即用对样本集分类效果作为弱学习器权重，而SAMME.R使用了对样本集分类的预测概率大小来作为弱学习器权重。由于SAMME.R使用了概率度量的连续值，迭代一般比SAMME快，因此AdaBoostClassifier的默认算法algorithm的值也是SAMME.R。我们一般使用默认的SAMME.R就够了，但是要注意的是使用了SAMME.R， 则弱分类学习器参数base_estimator必须限制使用支持概率预测的分类器。SAMME算法则没有这个限制。

loss:这个参数只有AdaBoostRegressor有，Adaboost.R2算法需要用到。有线性‘linear’, 平方‘square’和指数 ‘exponential’三种选择, 默认是线性，一般使用线性就足够了，除非你怀疑这个参数导致拟合程度不好。

n_estimators:太小容易欠拟合，太大容易过拟合，默认50

learning_rate:fk(x)=fk−1(x)+ναkGk(x)，v就是学习率，较小的v意味着需要更多的弱学习器的迭代次数。通常我们用步长和迭代次数一起来决定算法的拟合效果，可以从一个小一点的v开始调参，默认是1.

（2）弱学习器参数

max_features:划分时考虑的最大特征数。默认是“None”，可以使用很多种类型的值，默认是"None",意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑log2N个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑N−−√个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的"None"就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。

max_depth:默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。

min_samples_split:内部节点再划分所需最小样本数。这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。

min_samples_leaf:叶子节点最少样本数。 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。

min_weight_fraction_leaf:叶子节点最小的样本权重和。这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。 默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。

max_leaf_nodes:通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。

10.Adaboost 的优缺点 ？

优点：

• Adaboost作为分类器时，分类精度很高
• 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
• 作为简单的二元分类器时，构造简单，结果可理解。
• 不容易发生过拟合

缺点：

• 在Adaboost训练过程中，Adaboost会使得难于分类样本的权值呈指数增长，训练将会过于偏向这类困难的样本，导致Adaboost算法易受噪声干扰。此外，Adaboost依赖于弱分类器，而弱分类器的训练时间往往很长。

参考文献：

【1】手把手教你实现一个 AdaBoost

【2】AdaBoost原理详解

【3】第06章：深入浅出ML之Boosting家族

【4】集成学习之Adaboost算法原理小结