最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 自适应提升算法AdaBoost

    Adaptive Boosting(AdaBoost)是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个最强的最终分类器(强分类器)。

    1

    Motivation of Boosting

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

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

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

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

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

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

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

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

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

    所以,上个苹果的例子中,不同的学生代表不同的hypotheses gt;最终得到的苹果总体定义就代表hypothesis G;而老师就代表演算法A,指导学生的注意力集中到关键的例子中(错误样本),从而得到更好的苹果定义。其中的数学原理,我们下一部分详细介绍。

    2

    Diversity by Re-weighting

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

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

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

    其实这种example-weighted learning,我们在机器学习基石课程第8次笔记中就介绍过class-weighted的思想。二者道理是相通的。

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

    为了得到不同的gt,我们先来看看gtg(t+1)是怎么得到的:

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

    3

    Adaptive Boosting Algorithm

    值得注意的是上述的结论是建立在ϵt≤1/2的基础上,如果ϵt≥1/2,那么就做相反的推论即可。关于ϵt≥1/2的情况,我们稍后会进行说明。

    但是,上述步骤还有两个问题没有解决,第一个问题是初始的u应为多少呢?一般来说,为了保证第一次Ein最小的话,设u=1/N即可。这样最开始的g就能由此推导。第二个问题,最终的G(x)应该怎么求?是将所有的g(t)合并uniform在一起吗?一般来说并不是这样直接uniform求解,因为g(t+1)是通过gt得来的,二者在Ein上的表现差别比较大。所以,一般是对所有的g(t)进行linear或者non-linear组合来得到G(t)

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

    如何在每次迭代的时候计算αt呢?我们知道αtϵt是相关的:ϵt越小,对应的αt应该越大,ϵt越大,对应的αt应该越小。又因为tϵt是正相关的,所以,αt应该是t的单调函数。我们构造αt为:

    αt这样取值是有物理意义的,例如当ϵt=1/2时,error很大,跟掷骰子这样的随机过程没什么两样,此时对应的t=1,αt=0,即此gtG没有什么贡献,权重应该设为零。而当ϵt=0时,没有error,表示该gt预测非常准,此时对应的t=∞,αt=∞,即此gtG贡献非常大,权重应该设为无穷大。

    这种算法被称为Adaptive Boosting。它由三部分构成:base learning algorithm A,re-weighting factor t和linear aggregation αt。这三部分分别对应于我们在本节课开始介绍的例子中的Student,Teacher和Class。

    综上所述,完整的adaptive boosting(AdaBoost)Algorithm流程如下:

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

    对这个VC bound中的第一项Ein(G)来说,有一个很好的性质:如果满足ϵtϵ<1/2,则经过T=O(log N)次迭代之后,Ein(G)能减小到等于零的程度。而当N很大的时候,其中第二项也能变得很小。因为这两项都能变得很小,那么整个Eout(G)就能被限定在一个有限的上界中。

    其实,这种性质也正是AdaBoost算法的精髓所在。只要每次的ϵtϵ<1/2,即所选择的矩g比乱猜的表现好一点点,那么经过每次迭代之后,矩g的表现都会比原来更好一些,逐渐变强,最终得到Ein=0且Eout很小。

    4

    Adaptive Boosting in Action

    上一小节我们已经介绍了选择一个“弱弱”的算法A(ϵtϵ<1/2,比乱猜好就行),就能经过多次迭代得到Ein=0。我们称这种形式为decision stump模型。下面介绍一个例子,来看看AdaBoost是如何使用decision stump解决实际问题的。

    如下图所示,二维平面上分布一些正负样本点,利用decision stump来做切割。

    第一步:

    第二步:

    第三步:

    第四步:

    第五步:

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

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

    可以看出,AdaBoost-Stump这种非线性模型得到的分界线对正负样本有较好的分离效果。

    课程中还介绍了一个AdaBoost-Stump在人脸识别方面的应用:

    5

    Summary

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

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 自适应提升算法AdaBoost

    发表评论

    • 53会员总数(位)
    • 321资源总数(个)
    • 19本周发布(个)
    • 2 今日发布(个)
    • 334稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情