在集成学习原理小结中,我们讲到了集成学习按照个体学习器之间是否存在依赖关系可以分为两类,第一个是个体学习器之间存在强依赖关系,另一类是个体学习器之间不存在强依赖关系。前者的代表算法就是是boosting系列算法。在boosting系列算法中, Adaboost是最著名的算法之一。Adaboost既可以用作分类,也可以用作回归。本文就对Adaboost算法做一个总结。

1. 回顾boosting算法的基本原理

  在集成学习原理小结中,我们已经讲到了boosting算法系列的基本思想,如下图:

 从图中可以看出,Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1,根据弱学习的学习误差率表现来更新训练样本的权重,使得之前弱学习器1学习误差率高的训练样本点的权重变高,使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.,如此重复进行,直到弱学习器数达到事先指定的数目T,最终将这T个弱学习器通过集合策略进行整合,得到最终的强学习器。  

不过有几个具体的问题Boosting算法没有详细说明。

    1)如何计算学习误差率e?

    2) 如何得到弱学习器权重系数α?

    3)如何更新样本权重D?

    4) 使用何种结合策略?

    只要是boosting大家族的算法,都要解决这4个问题。那么Adaboost是怎么解决的呢?

2. Adaboost算法的基本思路

我们这里讲解Adaboost是如何解决上一节这4个问题的。

    假设我们的训练集样本是

T={(x,y1),(x2,y2),...(xm,ym)}

 训练集的在第k个弱学习器的输出权重为

D(k)=(wk1,wk2,...wkm);w1i=1m;i=1,2...m

 首先我们看看Adaboost的分类问题。

    分类问题的误差率很好理解和计算。由于多元分类是二元分类的推广,这里假设我们是二元分类问题,输出为{-1,1},则第k个弱分类器在训练集上的加权误差率为

接着我们看弱学习器权重系数,对于二元分类问题,第k个弱分类器的权重系数为

3. AdaBoost分类问题的损失函数优化

 刚才上一节我们讲到了分类Adaboost的弱学习器权重系数公式和样本权重更新公式。但是没有解释选择这个公式的原因,让人觉得是魔法公式一样。其实它可以从Adaboost的损失函数推导出来。

    从另一个角度讲, Adaboost是模型为加法模型,学习算法为前向分步学习算法,损失函数为指数函数的分类问题。

    模型为加法模型好理解,我们的最终的强分类器是若干个弱分类器加权平均而得到的。

    前向分步学习算法也好理解,我们的算法是通过一轮轮的弱学习器学习,利用前一个强学习器的结果和当前弱学习器来更新当前的强学习器的模型。也就是说,第k-1轮的强学习器为

4. AdaBoost二元分类问题算法流程

 这里我们对AdaBoost二元分类问题算法流程做一个总结。

 输入为样本集,输出为{-1, +1},弱分类器算法, 弱分类器迭代次数K。

输出为最终的强分类器

 1) 初始化样本集权重为

  其中R为类别数。从上式可以看出,如果是二元分类,R=2,则上式和我们的二元分类算法中的弱分类器的系数一致。

5. Adaboost回归问题的算法流程

这里我们对AdaBoost回归问题算法流程做一个总结。AdaBoost回归算法变种很多,下面的算法为Adaboost R2回归算法过程。

  输入为样本集,,弱学习器算法, 弱学习器迭代次数K。

  输出为最终的强学习器

f(x)=Gk(x)

 其中,是所有k对应的弱学习器。  

6. Adaboost算法的正则化

为了防止Adaboost过拟合,我们通常也会加入正则化项,这个正则化项我们通常称为步长(learning rate)。定义为,对于前面的弱学习器的迭代

fk(x)=fk1(x)+αkGk(x)

如果我们加上了正则化项,则有

fk(x)=fk1(x)+ναkGk(x)

 的取值范围为0<ν1。对于同样的训练集学习效果,较小的意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

7. Adaboost小结

到这里Adaboost就写完了,前面有一个没有提到,就是弱学习器的类型。理论上任何学习器都可以用于Adaboost.但一般来说,使用最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树,Adaboost分类用了CART分类树,而Adaboost回归用了CART回归树。

    这里对Adaboost算法的优缺点做一个总结。

    Adaboost的主要优点有:

    1)Adaboost作为分类器时,分类精度很高

    2)在Adaboost的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活。

    3)作为简单的二元分类器时,构造简单,结果可理解。

    4)不容易发生过拟合

    Adaboost的主要缺点有:

    1)对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

 

(欢迎转载,转载请注明出处。欢迎沟通交流: liujianping-ok@163.com)