精华内容
下载资源
问答
  • Adaboost 算法的原理与推导

    万次阅读 多人点赞 2014-11-02 23:31:07
    Adaboost 算法的原理与推导 0 引言 一直想写Adaboost来着,但迟迟未能动笔。其算法思想虽然简单:听取多人意见,最后综合决策,但一般书上对其算法的流程描述实在是过于晦涩。昨日11月1日下午,在我组织的...

        Adaboost 算法的原理与推导

    0 引言

        一直想写Adaboost来着,但迟迟未能动笔。其算法思想虽然简单:听取多人意见,最后综合决策,但一般书上对其算法的流程描述实在是过于晦涩。昨日11月1日下午,在我组织的机器学习班 第8次课上讲决策树与Adaboost,其中,Adaboost讲得酣畅淋漓,讲完后,我知道,可以写本篇博客了。

        无心啰嗦,本文结合机器学习班决策树与Adaboost 的PPT,跟邹讲Adaboost指数损失函数推导的PPT(第85~第98页)、以及李航的《统计学习方法》等参考资料写就,可以定义为一篇课程笔记、读书笔记或学习心得,有何问题或意见,欢迎于本文评论下随时不吝指出,thanks。

    1 Adaboost的原理

    1.1 Adaboost是什么    

        AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个基本分类器分错的样本会得到加强,加权后的全体样本再次被用来训练下一个基本分类器。同时,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

        具体说来,整个Adaboost 迭代算法就3步:

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

    1.2 Adaboost算法流程

        给定一个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)},其中实例x \in \mathcal{X},而实例空间\mathcal{X} \subset \mathbb{R}^n,yi属于标记集合{-1,+1},Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器,然后将这些弱分类器组合成一个强分类器。

        Adaboost的算法流程如下:

    • 步骤1. 首先,初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值:1/N。

    • 步骤2. 进行多轮迭代,用m = 1,2, ..., M表示迭代的第多少轮

    a. 使用具有权值分布Dm的训练数据集学习,得到基本分类器(选取让误差率最低的阈值来设计基本分类器):

    b. 计算Gm(x)在训练数据集上的分类误差率

    由上述式子可知,Gm(x)在训练数据集上的 误差率em就是被Gm(x)误分类样本的权值之和。

    c. 计算Gm(x)的系数,am表示Gm(x)在最终分类器中的重要程度(目的:得到基本分类器在最终分类器中所占的权重。注:这个公式写成am=1/2ln((1-em)/em) 更准确,因为底数是自然对数e,故用In,写成log容易让人误以为底数是2或别的底数,下同):

    由上述式子可知,em <= 1/2时,am >= 0,且am随着em的减小而增大,意味着分类误差率越小的基本分类器在最终分类器中的作用越大。

    d. 更新训练数据集的权值分布(目的:得到样本的新的权值分布),用于下一轮迭代

    使得被基本分类器Gm(x)误分类样本的权值增大,而被正确分类样本的权值减小。就这样,通过这样的方式,AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。

        其中,Zm是规范化因子,使得Dm+1成为一个概率分布:

    • 步骤3. 组合各个弱分类器

    从而得到最终分类器,如下:

    1.3 Adaboost的一个例子

        下面,给定下列训练样本,请用AdaBoost算法学习一个强分类器。

        

        求解过程:初始化训练数据的权值分布,令每个权值W1i = 1/N = 0.1,其中,N = 10,i = 1,2, ..., 10,然后分别对于m = 1,2,3, ...等值进行迭代。

        拿到这10个数据的训练样本后,根据 X 和 Y 的对应关系,要把这10个数据分为两类,一类是“1”,一类是“-1”,根据数据的特点发现:“0 1 2”这3个数据对应的类是“1”,“3 4 5”这3个数据对应的类是“-1”,“6 7 8”这3个数据对应的类是“1”,9是比较孤独的,对应类“-1”。抛开孤独的9不讲,“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据,分别对应的类是1、-1、1,直观上推测可知,可以找到对应的数据分界点,比如2.5、5.5、8.5 将那几类数据分成两类。当然,这只是主观臆测,下面实际计算下这个具体过程。

    迭代过程1

    对于m=1,在权值分布为D1(10个数据,每个数据的权值皆初始化为0.1)的训练数据上,经过计算可得:

      1. 阈值v取2.5时误差率为0.3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.3),
      2. 阈值v取5.5时误差率最低为0.4(x < 5.5时取1,x > 5.5时取-1,则3 4 5 6 7 8皆分错,误差率0.6大于0.5,不可取。故令x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.4),
      3. 阈值v取8.5时误差率为0.3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.3)。

    可以看到,无论阈值v取2.5,还是8.5,总得分错3个样本,故可任取其中任意一个如2.5,弄成第一个基本分类器为:

    上面说阈值v取2.5时则6 7 8分错,所以误差率为0.3,更加详细的解释是:因为样本集中

      1. 0 1 2对应的类(Y)是1,因它们本身都小于2.5,所以被G1(x)分在了相应的类“1”中,分对了。
      2. 3 4 5本身对应的类(Y)是-1,因它们本身都大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。
      3. 但6 7 8本身对应类(Y)是1,却因它们本身大于2.5而被G1(x)分在了类"-1"中,所以这3个样本被分错了。
      4. 9本身对应的类(Y)是-1,因它本身大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。

    从而得到G1(x)在训练数据集上的误差率(被G1(x)误分类样本“6 7 8”的权值之和)e1=P(G1(xi)≠yi) = 3*0.1 = 0.3

    然后根据误差率e1计算G1的系数:

    这个a1代表G1(x)在最终的分类函数中所占的权重,为0.4236。
    接着更新训练数据的权值分布,用于下一轮迭代:

    值得一提的是,由权值更新的公式可知,每个样本的新权值是变大还是变小,取决于它是被分错还是被分正确。

    即如果某个样本被分错了,则yi * Gm(xi)为负,负负得正,结果使得整个式子变大(样本权值变大),否则变小。

    第一轮迭代后,最后得到各个数据的权值分布D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出,因为样本中是数据“6 7 8”被G1(x)分错了,所以它们的权值由之前的0.1增大到0.1666,反之,其它数据皆被分正确,所以它们的权值皆由之前的0.1减小到0.0715。

    分类函数f1(x)= a1*G1(x) = 0.4236G1(x)。

    此时,得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点(即6 7 8)。

        从上述第一轮的整个迭代过程可以看出:被误分类样本的权值之和影响误差率,误差率影响基本分类器在最终分类器中所占的权重

      迭代过程2

    对于m=2,在权值分布为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上,经过计算可得:

      1. 阈值v取2.5时误差率为0.1666*3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.1666*3),
      2. 阈值v取5.5时误差率最低为0.0715*4(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.0715*3 + 0.0715),
      3. 阈值v取8.5时误差率为0.0715*3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.0715*3)。

    所以,阈值v取8.5时误差率最低,故第二个基本分类器为:

    面对的还是下述样本:

    很明显,G2(x)把样本“3 4 5”分错了,根据D2可知它们的权值为0.0715, 0.0715,  0.0715,所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。

    计算G2的系数:

    更新训练数据的权值分布:

    D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分错的样本“3 4 5”的权值变大,其它被分对的样本的权值变小。
    f2(x)=0.4236G1(x) + 0.6496G2(x)

    此时,得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点(即3 4 5)。

      迭代过程3

    对于m=3,在权值分布为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上,经过计算可得:

      1. 阈值v取2.5时误差率为0.1060*3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.1060*3),
      2. 阈值v取5.5时误差率最低为0.0455*4(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.0455*3 + 0.0715),
      3. 阈值v取8.5时误差率为0.1667*3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.1667*3)。

    所以阈值v取5.5时误差率最低,故第三个基本分类器为:

    依然还是原样本:

    此时,被误分类的样本是:0 1 2 9,这4个样本所对应的权值皆为0.0455,

    所以G3(x)在训练数据集上的误差率e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820。

    计算G3的系数:

    更新训练数据的权值分布:

    D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。被分错的样本“0 1 2 9”的权值变大,其它被分对的样本的权值变小。

    f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)

    此时,得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此,整个训练过程结束。

        现在,咱们来总结下3轮迭代下来,各个样本权值和误差率的变化,如下所示(其中,样本权值D中加了下划线的表示在上一轮中被分错的样本的新权值):

    1. 训练之前,各个样本的权值被初始化为D1 = (0.1, 0.1,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1);
    2. 第一轮迭代中,样本“6 7 8”被分错,对应的误差率为e1=P(G1(xi)≠yi) = 3*0.1 = 0.3,此第一个基本分类器在最终的分类器中所占的权重为a1 = 0.4236。第一轮迭代过后,样本新的权值为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715);
    3. 第二轮迭代中,样本“3 4 5”被分错,对应的误差率为e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143,此第二个基本分类器在最终的分类器中所占的权重为a2 = 0.6496。第二轮迭代过后,样本新的权值为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455);
    4. 第三轮迭代中,样本“0 1 2 9”被分错,对应的误差率为e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820,此第三个基本分类器在最终的分类器中所占的权重为a3 = 0.7514。第三轮迭代过后,样本新的权值为D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。

        从上述过程中可以发现,如果某些个样本被分错,它们在下一轮迭代中的权值将被增大,同时,其它被分对的样本在下一轮迭代中的权值将被减小。就这样,分错样本权值增大,分对样本权值变小,而在下一轮迭代中,总是选取让误差率最低的阈值来设计基本分类器,所以误差率e(所有被Gm(x)误分类样本的权值之和)不断降低。

        综上,将上面计算得到的a1、a2、a3各值代入G(x)中,G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ],得到最终的分类器为:

    G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。

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

    3 Adaboost 指数损失函数推导

        事实上,在上文1.2节Adaboost的算法流程的步骤3中,我们构造的各个基本分类器的线性组合

        是一个加法模型,而Adaboost算法其实是前向分步算法的特例。那么问题来了,什么是加法模型,什么又是前向分步算法呢?

    3.1 加法模型和前向分步算法

        如下图所示的便是一个加法模型

        其中,称为基函数,称为基函数的参数,称为基函数的系数。

        在给定训练数据及损失函数的条件下,学习加法模型成为经验风险极小化问题,即损失函数极小化问题:

        随后,该问题可以作如此简化:从前向后,每一步只学习一个基函数及其系数,逐步逼近上式,即:每步只优化如下损失函数:

        这个优化方法便就是所谓的前向分步算法。

        下面,咱们来具体看下前向分步算法的算法流程:

    • 输入:训练数据集
    • 损失函数:
    • 基函数集:
    • 输出:加法模型
    • 算法步骤:
      • 1. 初始化
      • 2. 对于m=1,2,..M
    • a)极小化损失函数

    得到参数

    • b)更新

      • 3. 最终得到加法模型

        就这样,前向分步算法将同时求解从m=1到M的所有参数()的优化问题简化为逐次求解各个(1≤m≤M)的优化问题。

    3.2 前向分步算法与Adaboost的关系

        在上文第2节最后,我们说Adaboost 还有另外一种理解,即可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。其实,Adaboost算法就是前向分步算法的一个特例,Adaboost 中,各个基本分类器就相当于加法模型中的基函数,且其损失函数为指数函数。

        换句话说,当前向分步算法中的基函数为Adaboost中的基本分类器时,加法模型等价于Adaboost的最终分类器

        你甚至可以说,这个最终分类器其实就是一个加法模型。只是这个加法模型由基本分类器及其系数组成,m = 1, 2, ..., M。前向分步算法逐一学习基函数的过程,与Adaboost算法逐一学习各个基本分类器的过程一致。

        下面,咱们便来证明:当前向分步算法的损失函数是指数损失函数

        时,其学习的具体操作等价于Adaboost算法的学习过程

         假设经过m-1轮迭代,前向分步算法已经得到

        而后在第m轮迭代得到。其中,为:

        而未知。所以,现在咱们的目标便是根据前向分步算法训练,使得最终在训练数据集T上的指数损失最小,即

        针对这种需要求解多个参数的情况,可以先固定其它参数,求解其中一两个参数,然后逐一求解剩下的参数。例如我们可以固定,只针对做优化。

        换言之,在面对 这2m个参数都未知的情况下,可以:

    1. 先假定已知,求解出
    2. 然后再逐一求解其它未知参数。

        且考虑到上式中的既不依赖也不依赖G,所以是个与最小化无关的固定值,记为,即,则上式可以表示为(后面要多次用到这个式子,简记为):

        值得一提的是,虽然与最小化无关,但依赖于,随着每一轮迭代而发生变化。

        接下来,便是要证使得上式达到最小的就是Adaboost算法所求解得到的

        为求解上式,咱们先求再求

        首先求。对于任意,使上式最小的G(x)由下式得到:

        别忘了,

        跟1.2节所述的误差率的计算公式对比下:

        可知,上面得到的便是Adaboost算法的基本分类器,因为它是在第m轮加权训练数据时,使分类误差率最小的基本分类器。换言之,这个便是Adaboost算法所要求的,别忘了,在Adaboost算法的每一轮迭代中,都是选取让误差率最低的阈值来设计基本分类器

        然后求。还是回到之前的这个式子上:

        这个式子的后半部分可以进一步化简,得:

        接着将上面求得的

        代入上式中,且对求导,令其求导结果为0,即得到使得一式最小的,即为:

        这里的跟上文1.2节中的计算公式完全一致。

        此外,毫无疑问,上式中的便是误差率:

        即就是被Gm(x)误分类样本的权值之和。

       就这样,结合模型,跟,可以推出

       从而有:

        与上文1.2节介绍的权值更新公式

        相比,只相差一个规范化因子,即后者多了一个

        所以,整个过程下来,我们可以看到,前向分步算法逐一学习基函数的过程,确实是与Adaboost算法逐一学习各个基本分类器的过程一致,两者完全等价。

        综上,本节不但提供了Adaboost的另一种理解:加法模型,损失函数为指数函数,学习算法为前向分步算法,而且也解释了最开始1.2节中基本分类器及其系数的由来,以及对权值更新公式的解释,你甚至可以认为本节就是对上文整个1.2节的解释。

    4 参考文献与推荐阅读

    1. wikipedia上关于Adaboost的介绍:http://zh.wikipedia.org/zh-cn/AdaBoost
    2. 邹之决策树与Adaboost PPT:http://pan.baidu.com/s/1hqePkdY
    3. 邹讲Adaboost指数损失函数推导的PPT:http://pan.baidu.com/s/1kTkkepD(第85页~第98页);
    4. 《统计学习方法 李航著》第8章;
    5. 关于adaboost的一些浅见:http://blog.sina.com.cn/s/blog_6ae183910101chcg.html
    6. A Short Introduction to Boosting:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.5148&rep=rep1&type=pdf
    7. 南大周志华教授做的关于boosting 25年的报告PPT:http://vdisk.weibo.com/s/FcILTUAi9m111
    8. 《数据挖掘十大算法》第7章 Adaboost;
    9. http://summerbell.iteye.com/blog/532376
    10. 统计学习那些事:http://cos.name/2011/12/stories-about-statistical-learning/
    11. 统计学习基础学习笔记:http://www.loyhome.com/%E2%89%AA%E7%BB%9F%E8%AE%A1%E5%AD%A6%E4%B9%A0%E7%B2%BE%E8%A6%81the-elements-of-statistical-learning%E2%89%AB%E8%AF%BE%E5%A0%82%E7%AC%94%E8%AE%B0%EF%BC%88%E5%8D%81%E5%9B%9B%EF%BC%89/
    12. PRML第十四章组合模型读书笔记:http://vdisk.weibo.com/s/DmxNcM5_IaUD
    13. 顺便推荐一个非常实用的在线编辑LaTeX 公式的网页:http://private.codecogs.com/latex/eqneditor.php?lang=zh-cn
    展开全文
  • Adaboost算法

    2017-10-07 14:46:42
    1、AdaBoost算法介绍 AdaBoost是Boosting方法中最优代表性的提升算法。该方法通过在每轮降低分对样例的权重,增加分错样例的权重,...2、AdaBoost算法过程: 1)初始化每个训练样例的权值,共N个训练样例。 2)...

    1、AdaBoost算法介绍

    AdaBoost是Boosting方法中最优代表性的提升算法。该方法通过在每轮降低分对样例的权重,增加分错样例的权重,使得分类器在迭代过程中逐步改进,最终将所有分类器线性组合得到最终分类器,Boost算法框架如下图所示:

    图1.1 Boost分类框架(来自PRML)

    2、AdaBoost算法过程:

    1)初始化每个训练样例的权值,共N个训练样例。

    2)共进行M轮学习,第m轮学习过程如下:

    A)使用权值分布为Wm的训练样例学习得到基分类器Gm。

    B)计算上一步得到的基分类器的误差率:(此公式参考PRML,其余的来自统计学习方法)

    C)计算Gm前面的权重系数:

    D)更新训练样例的权重系数,

    E)重复A)到D)。得到一系列的权重参数am和基分类器Gm

    4)将上一步得到的基分类器根据权重参数线性组合,得到最终分类器:

     

    3、算法中的两个权重分析:

    1)关于基分类器权重的分析

    上面计算的am表示基分类器在最终的分类器中所占的权重,am的计算根据em而得到,由于每个基分类器的分类性能要好于随机分类器,故而误差率em<0.5.(对二分类问题)

    当em<0.5时,am>0且am随着em的减小而增大,所以,分类误差率越小的基分类器在最终的分类器中所占的权重越大。

    注:此处的所有am之后并不为1。

    2)训练样例的权重分析

    根据公式可知,样例分对和分错,权重相差倍(统计学习方法上此公式有误)。

    由于am>0,故而exp(-am)<1,当样例被基本分类器正确分类时,其权重在减小,反之权重在增大。

    通过增大错分样例的权重,让此样例在下一轮的分类器中被重点关注,通过这种方式,慢慢减小了分错样例数目,使得基分类器性能逐步改善。

     

    4、训练误差分析

             关于误差上界有以下不等式,此不等式说明了Adaboost的训练误差是以指数的速度下降的,

    推导过程用到的公式有:

    具体推导过程请看统计学习方法课本!

     

    5、AdaBoost算法推导过程

    AdaBoost算法使用加法模型,损失函数为指数函数,学习算法使用前向分步算法。

    其中加法模型为:

    损失函数为指数函数:

    我们的目标是要最小化损失函数,通过最小化损失函数来得到模型中所需的参数。而在Adaboost算法中,每一轮都需要更新样例的权重参数,故而在每一轮的迭代中需要将损失函数极小化,然后据此得到每个样例的权重更新参数。这样在每轮的迭代过程中只需要将当前基函数在训练集上的损失函数最小即可。

    现在我们需要通过极小化上面的损失函数,得到a,G。

    设:

    于是有:

    为了方便下面推导,我们将:

    这样,我们就有:

    正式推导过程如下:

    设:

    对g(a)求导得:

    ,得到:

    其中,在计算过程中用到的em为:

    由于,所以得到新的损失为:

    最终的wmi通过规范化得到:

    其中规范化因子为:

    展开全文
  • AdaBoost是一种特殊的Boosting族算法,它与众多的Boosting一族的算法的工作机制一致:先从初始训练样本中训练一个基学习器(也称弱学习器),再根据基学习器的表现对训练样本的分布进行调整,使得先前基学习器分类...

    一.算法思想

    \quad\quad AdaBoost是一种特殊的Boosting族算法,它与众多的Boosting一族的算法的工作机制一致:先从初始训练样本中训练一个基学习器(也称弱学习器),再根据基学习器的表现对训练样本的分布进行调整,使得先前基学习器分类错误的样本在后续中受到更多的关注(即加大权重),然后基于调整后的样本分布来训练下一个基学习器,如此重复进行,直至基学习器的数量达到事先指定的值T,最终将这T个基学习器进行加权结合。

    二.算法过程

    给定训练集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\} D={(x1,y1),(x2,y2),...,(xm,ym)}
    其中 x i ∈ X , y i ∈ { − 1 , + 1 } x_i\in{X},y_i\in{\{-1,+1\}} xiX,yi{1,+1}
    初始化训练样本权重 D 1 ( i ) = 1 m ( i = 1 , 2 , . . . , m ) D_1(i)=\frac{1}{m}(i=1,2,...,m) D1(i)=m1(i=1,2,...,m)
    for t = 1,2,…,T:
    \quad 训练弱分类器 h t = ζ ( D , D t ) h_t=\zeta(D,D_t) ht=ζ(D,Dt)
    \quad 计算错误率 ϵ t = P r i ∼ D t ( h t ( x i ) ≠ y i ) \epsilon_t=P_{r_i\sim{D_t}}(h_t(x_i)\neq{y_i}) ϵt=PriDt(ht(xi)=yi)
    \quad 计算弱分类器的权重 α t = 1 2 l n ( 1 − ϵ t ϵ t ) \alpha_t=\frac{1}{2}ln(\frac{1-\epsilon_t}{\epsilon_t}) αt=21ln(ϵt1ϵt)
    \quad 更新训练样本的权重:
    D t + 1 = D t ( i ) Z t × { e − α t , h t ( x i ) = y i e α t , h t ( x i ) ≠ y i = D t ( i ) Z t e − α t y i h t ( x i ) D_{t+1}=\frac{D_t(i)}{Z_t}\times\left\{ \begin{aligned} e^{-\alpha t},\quad h_t(x_i)=y_i\\ e^{\alpha t},\quad h_t(x_i)\neq{y_i} \end{aligned} \quad =\frac{D_t(i)}{Z_t}e^{-\alpha t y_i h_t(x_i)} \right. Dt+1=ZtDt(i)×{eαt,ht(xi)=yieαt,ht(xi)=yi=ZtDt(i)eαtyiht(xi)
    输出结果 H f i n a l ( x i ) = s i g n ( ∑ t = 1 T α t h t ( x i ) ) H_{final}(x_i)=sign(\sum_{t=1}^{T}\alpha_th_t(x_i)) Hfinal(xi)=sign(t=1Tαtht(xi))

    展开全文
  • 提取Haar特征 生成弱分类器 采用AdaBoost算法选取优化的弱分类器
  • AdaBoost算法

    2018-11-26 19:05:40
    数据挖掘领域十大经典算法之—AdaBoost算法(超详细附代码) 简介 Adaboost算法是一种提升方法,将多个弱分类器,组合成强分类器。 AdaBoost,是英文”Adaptive Boosting“(自适应增强)的缩写,由Yoav Freund和...
     本文转载自:https://blog.csdn.net/fuqiuai/article/details/79482487  
    

    数据挖掘领域十大经典算法之—AdaBoost算法(超详细附代码)

    简介

    Adaboost算法是一种提升方法,将多个弱分类器,组合成强分类器。
    AdaBoost,是英文”Adaptive Boosting“(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。
    它的自适应在于:前一个弱分类器分错的样本的权值(样本对应的权值)会得到加强,权值更新后的样本再次被用来训练下一个新的弱分类器。在每轮训练中,用总体(样本总体)训练新的弱分类器,产生新的样本权值、该弱分类器的话语权,一直迭代直到达到预定的错误率或达到指定的最大迭代次数。
    总体——样本——个体三者间的关系需要搞清除
    总体N。样本:{ni}i从1到M。个体:如n1=(1,2),样本n1中有两个个体。

    算法原理

    (1)初始化训练数据(每个样本)的权值分布:如果有N个样本,则每一个训练的样本点最开始时都被赋予相同的权重:1/N。
    (2)训练弱分类器。具体训练过程中,如果某个样本已经被准确地分类,那么在构造下一个训练集中,它的权重就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。同时,得到弱分类器对应的话语权。然后,更新权值后的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。
    (3)将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,分类误差率小的弱分类器的话语权较大,其在最终的分类函数中起着较大的决定作用,而分类误差率大的弱分类器的话语权较小,其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的比例较大,反之较小。

    算法流程

    第一步:
    初始化训练数据(每个样本)的权值分布。每一个训练样本,初始化时赋予同样的权值w=1/N。N为样本总数。
    这里写图片描述
    D1表示,第一次迭代每个样本的权值。w11表示,第1次迭代时的第一个样本的权值。
    N为样本总数。
    第二步:进行多次迭代,m=1,2….M。m表示迭代次数。
    a)使用具有权值分布Dm(m=1,2,3…N)的训练样本集进行学习,得到弱的分类器。
    这里写图片描述
    该式子表示,第m次迭代时的弱分类器,将样本x要么分类成-1,要么分类成1.那么根据什么准则得到弱分类器?
    准则:该弱分类器的误差函数最小,也就是分错的样本对应的 权值之和,最小。
    这里写图片描述
    b)计算弱分类器Gm(x)的话语权,话语权am表示Gm(x)在最终分类器中的重要程度。其中em,为上步中的εm(误差函数的值)
    这里写图片描述
    该式是随em减小而增大。即误差率小的分类器,在最终分类器的 重要程度大。
    c)更新训练样本集的权值分布。用于下一轮迭代。其中,被误分的样本的权值会增大,被正确分的权值减小。
    这里写图片描述
    Dm+1是用于下次迭代时样本的权值,Wm+1,i是下一次迭代时,第i个样本的权值。
    其中,yi代表第i个样本对应的类别(1或-1),Gm(xi)表示弱分类器对样本xi的分类(1或-1)。若果分对,yi*Gm(xi)的值为1,反之为-1。其中Zm是归一化因子,使得所有样本对应的权值之和为1.
    这里写图片描述
    该公式并不难,仔细看看、想想。
    第三步迭代完成后,组合弱分类器。
    首先,这里写图片描述
    然后,加个sign函数,该函数用于求数值的正负。数值大于0,为1。小于0,为-1.等于0,为0.得到最终的强分类器G(x)
    这里写图片描述

    *额外(关于权值、话语权、弱分类器准则的公式,想深入了解的可以看看。使用的话,知道上面的内容已经足够)
    利用前向分布加法模型(简单说,就是把一起求n个问题,转化为每次求1个问题,再其基础上,求下一个问题,如此迭代n次),adaboost算法可以看成,求式子的最小。tn时样本n对应的正确分类,fm是前m个分类器的结合(这里乘了1/2,因为博主看的文章的am是1/2*log(~~),这个无所谓,无非是多个1/2少个1/2。
    这里写图片描述
    这里写图片描述
    然后,假设前m-1个相关的参数已经确定。通过化简E这个式子,我们可以得到:
    这里写图片描述
    其中,是一个常量。
    这里写图片描述
    然后,
    这里写图片描述
    其中,Tm是分类正确的样本的权值,Mm是分类错误的样本的权值。式子不算难,自己多看几遍就能理解了。
    到现在,可以看出,最小化E,其实就是最小化
    这里写图片描述
    这个式子是什么?看看前面,这个就是找弱分类器时的准则!
    然后得到了弱分类器ym后,我们可以进推导出am和样本的权值。这里给出am的推导过程(手写的,字很烂)其中,ε是这里写图片描述
    该图中,最右边的是“+exp(-am/2)*1”,写得太乱(—_—)
    这里写图片描述
    最后求出来的am没有1/2,这个无所谓。因为这里定义fm是多乘了个1/2。

    优点

    (1)精度很高的分类器
    (2)提供的是框架,可以使用各种方法构建弱分类器
    (3)简单,不需要做特征筛选
    (4)不用担心过度拟合

    实际应用

    (1)用于二分类或多分类
    (2)特征选择
    (3)分类人物的baseline

    代码

    代码已在github上实现,这里也贴出来

    # encoding=utf-8
    
    import pandas as pd
    import time
    
    from sklearn.cross_validation import train_test_split
    from sklearn.metrics import accuracy_score
    
    from sklearn.ensemble import AdaBoostClassifier
    
    if __name__ == '__main__':
    
        print("Start read data...")
        time_1 = time.time()
    
        raw_data = pd.read_csv('../data/train_binary.csv', header=0) 
        data = raw_data.values
    
        features = data[::, 1::]
        labels = data[::, 0]
    
        # 随机选取33%数据作为测试集,剩余为训练集
        train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
    
        time_2 = time.time()
        print('read data cost %f seconds' % (time_2 - time_1))
    
    
        print('Start training...') 
        # n_estimators表示要组合的弱分类器个数;
        # algorithm可选{‘SAMME’, ‘SAMME.R’},默认为‘SAMME.R’,表示使用的是real boosting算法,‘SAMME’表示使用的是discrete boosting算法
        clf = AdaBoostClassifier(n_estimators=100,algorithm='SAMME.R')
        clf.fit(train_features,train_labels)
        time_3 = time.time()
        print('training cost %f seconds' % (time_3 - time_2))
    
    
        print('Start predicting...')
        test_predict = clf.predict(test_features)
        time_4 = time.time()
        print('predicting cost %f seconds' % (time_4 - time_3))
    
    
        score = accuracy_score(test_labels, test_predict)
    print("The accruacy score is %f" % score)
    

    测试数据集为经过二分类处理后的MNIST数据集,获取地址train_binary.csv

    运行结果

    这里写图片描述

    更多案例请关注“思享会Club”公众号或者关注思享会博客:http://gkhelp.cn/ 本文转载自:https://blog.csdn.net/qq_37331184/article/details/84554163

    在这里插入图片描述

    展开全文
  • 本文档是本人在学习Adaboost算法过程中的心得体会,是学习中的重点提取,可以帮助初学者理解。
  • adaboost算法

    2010-05-01 19:09:38
    讲解adaboost算法过程,个人觉得很经典,英文的,但是很好懂
  • AdaBoost 算法

    2020-02-06 19:30:38
    AdaBoost 算法 是一种经典的集成学习算法,它将多个弱分类器集成起来,以达到较高的分类准确率,广泛应用于数据分类、人脸检测等应用中。尤其在人脸检测方面,AdaBoost 是非常经典、成功的一个算法。弱分类器被线性...
  • Adaboost 算法

    千次阅读 2017-06-09 20:16:30
    Adaboost 算法? 什么是集成学习集成学习就是将多个弱的学习器结合起来组成一个强的学习器。这就涉及到,先产生一组‘个体学习器’,再用一个策略将它们结合起来。个体学习器可以选择:决策树,神经网络。 集成时...
  • AdaBoost算法实例详解

    千次阅读 2020-05-23 14:15:10
    抛开这些理论性的推导不谈(其实是因为能力有限),通过例子直观的了解AdaBoost算法的计算过程。 简要叙述一下AdaBoost算法的主要过程: AdaBoost为每个数据样本分配权重,权重符合概率分布,初始权重符合均匀分布...
  • 提升方法AdaBoost算法

    2018-06-15 19:06:38
    本文尝试对AdaBoost算法过程进行解释,希望能对大家理解AdaBoost算法有所帮助。 注:1.文中出现的一些数学结论,只提供了简单、便于理解的证明,并非严谨、详细的证明。 2.文中对AdaBoost算法的解释方式,...
  • 原文地址:AdaBoost算法的训练过程作者:charming 每个Haar特征对应看一个弱分类器,但并不是任伺一个Haar特征都能较好的描述人脸灰度分布的某一特点,如何从大量的Haar特征中挑选出最优的Haar特征并制作成分类器...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,912
精华内容 6,364
关键字:

adaboost算法的过程