开发者俱乐部

标题: Adaboost 算法的原理与推导 [打印本页]
作者: xman    时间: 2016-10-8 21:10
标题: Adaboost 算法的原理与推导
0 引言

        一直想写Adaboost来着，但迟迟未能动笔。其算法思想虽然简单“听取多人意见，最后综合决策”，但一般书上对其算法的流程描述实在是过于晦涩。昨日11月1日下午，邹博在我组织的机器学习班第8次课上讲决策树与Adaboost，其中，Adaboost讲得酣畅淋漓，讲完后，我知道，可以写本篇博客了。
        无心啰嗦，本文结合邹博之决策树与Adaboost的PPT跟《统计学习方法》等参考资料写就，可以定义为一篇课程笔记、读书笔记或学习心得，有何问题或意见，欢迎于本文评论下随时不吝指出，thanks。


1 Adaboost的原理
1.1 Adaboost是什么
       AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。
        AdaBoost是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。
        在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器。整个训练过程如此迭代地进行下去。


1.2 Adaboost算法流程
       给定一个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)}，其中实例 ，而实例空间 ，yi属于标记集合{-1,+1}，Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。
        Adaboost的算法流程如下：
        接下来，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。具体说来，则是：
        a.使用具有权值分布Dm的训练数据集学习，得到基本二元分类器：
        b.计算Gm(x)在训练数据集上的分类误差率
        c. 计算Gm(x)的系数，am表示Gm(x)在最终分类器中的重要程度：
        由上述式子可知，em <= 1/2时，am >= 0，且am随着em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。
        d. 更新训练数据集的权值分布
       使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。
        其中，Zm是规范化因子，使得Dm+1成为一个概率分布：

        从而得到最终分类器，如下：
1.3 Adaboost的一个例子


       下面，给定下列训练样本，请用AdaBoost算法学习一个强分类器。
        求解过程：初始化训练数据的权值分布，令每个权值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分别对于m = 1,2,3, ...等值进行迭代。
        迭代过程1：对于m=1，在权值分布为D1的训练数据上，阈值v取2.5时误差率最低，故基本分类器为：
        从而可得G1(x)在训练数据集上的误差率e1=P(G1(xi)≠yi) = 0.3
        然后计算G1的系数：
        接着更新训练数据的权值分布：
        最后得到各个数据的权值分布D2=(0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)，分类函数f1(x)=0.4236G1(x)，故最终得到的分类器sign(f1(x))在训练数据集上有3个误分类点。
        迭代过程2：对于m=2，在权值分布为D2的训练数据上，阈值v取8.5时误差率最低，故基本分类器为：
        G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.2143
        计算G2的系数：
        更新训练数据的权值分布：
        D3=(0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)
        f2(x)=0.4236G1(x) + 0.6496G2(x)
        分类器sign(f2(x))在训练数据集上有3个误分类点。
        迭代过程3：对于m=3，在权值分布为D3的训练数据上，阈值v取5.5时误差率最低，故基本分类器为：
        G3(x)在训练数据集上的误差率e3=P(G3(xi)≠yi) = 0.1820
        计算G3的系数：
        更新训练数据的权值分布：
        D4=(0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)，f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)，分类器sign(f3(x))在训练数据集上有0个误分类点。


2 Adaboost的误差界


       通过上面的例子可知，Adaboost在学习的过程中不断减少训练误差e，那这个误差界到底是多少呢？
        事实上，adaboost 的训练误差的上界为：
        下面，咱们来通过推导来证明下上述式子。
        当G(xi)≠yi时，yi*f(xi)<0，因而exp(-yi*f(xi))≥1，因此前半部分得证。
        关于后半部分，别忘了：
        整个的推导过程如下：
        这个结果说明，可以在每一轮选取适当的Gm使得Zm最小，从而使训练误差下降最快。接着，咱们来继续求上述结果的上界。
        对于二分类而言，有如下结果：
        其中， 。
        继续证明下这个结论。
        由之前Zm的定义式跟本节最开始得到的结论可知：
        而这个不等式 可先由e^x和1-x的开根号，在点x的泰勒展开式推出。
        值得一提的是，如果取γ1, γ2… 的最大值，记做γ（显然，γ≥γi>0，i=1,2,...m），则对于所有m，有：
        这个结论表明，AdaBoost的训练误差是以指数速率下降的。另外，AdaBoost算法不需要事先知道下界γ，AdaBoost具有自适应性，它能适应弱分类器各自的训练误差率 。

        最后，Adaboost 还有另外一种理解，即可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法，有机会再推导下，然后更新此文。而在此之前，有兴趣的可以参看《统计学习方法》第8.3节或其它相关资料。

3 参考文献与推荐阅读
















欢迎光临 开发者俱乐部 (http://xodn.com/) Powered by Discuz! X3.2