您好、欢迎来到现金彩票网!
当前位置:刘伯温高手心水论坛1 > 推导树 >

Adaboost 算法的原理与推导

发布时间:2019-06-19 06:57 来源:未知 编辑:admin

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

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

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

  初始化训练数据的权值分布。如果有N个样本,则每一个训练样本最开始时都被赋予相同的权值:1/N。

  训练弱分类器。具体训练过程中,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它的权值就被降低;相反,如果某个样本点没有被准确地分类,那么它的权值就得到提高。然后,权值更新过的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。

  将 各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,使其在最终的分类函数中起着较大的决定作用, 而降低分类误差率大的弱分类器的权重,使其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的权重较大,否则较小。

  给定一个训练数据集T={(x1,y1), (x2,y2)(xN,yN)},其中实例

  ,yi属于标记集合{-1,+1},Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器,然后将这些弱分类器组合成一个强分类器。

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

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

  拿到这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 将那几类数据分成两类。当然,这只是主观臆测,下面实际计算下这个具体过程。

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

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

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

  0 1 2对应的类(Y)是1,因它们本身都小于2.5,所以被G1(x)分在了相应的类“1”中,分对了。

  3 4 5本身对应的类(Y)是-1,因它们本身都大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。

  但6 7 8本身对应类(Y)是1,却因它们本身大于2.5而被G1(x)分在了类-1中,所以这3个样本被分错了。

  9本身对应的类(Y)是-1,因它本身大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。

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

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

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

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

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

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

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

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

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

  通过上面的例子可知,Adaboost在学习的过程中不断减少训练误差e,直到各个弱分类器组合成最终分类器,那这个最终分类器的误差界到底是多少呢?

  这个结果说明,可以在每一轮选取适当的Gm使得Zm最小,从而使训练误差下降最快。接着,咱们来继续求上述结果的上界。

  这个结论表明,AdaBoost的训练误差是以指数速率下降的。另外,AdaBoost算法不需要事先知道下界,AdaBoost具有自适应性,它能适应弱分类器各自的训练误差率 。

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

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

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

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

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

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

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

http://ivansolano.com/tuidaoshu/230.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有