AI有道
一个有情怀的公众号
Adaptive Boosting(AdaBoost)是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个最强的最终分类器(强分类器)。
1
Motivation of Boosting
我们先来看一个简单的识别苹果的例子,老师展示20张图片,让6岁孩子们通过观察,判断其中哪些图片的内容是苹果。从判断的过程中推导如何解决二元分类问题的方法。
显然这是一个监督式学习,20张图片包括它的标签都是已知的。首先,学生Michael回答说:所有的苹果应该是圆形的。根据Michael的判断,对应到20张图片中去,大部分苹果能被识别出来,但也有错误。其中错误包括有的苹果不是圆形,而且圆形的水果也不一定是苹果。如下图所示:
上图中蓝色区域的图片代表分类错误。显然,只用“苹果是圆形的”这一个条件不能保证分类效果很好。我们把蓝色区域(分类错误的图片)放大,分类正确的图片缩小,这样在接下来的分类中就会更加注重这些错误样本。
然后,学生Tina观察被放大的错误样本和上一轮被缩小的正确样本,回答说:苹果应该是红色的。根据Tina的判断,得到的结果如下图所示:
上图中蓝色区域的图片一样代表分类错误,即根据这个苹果是红色的条件,使得青苹果和草莓、西红柿都出现了判断错误。那么结果就是把这些分类错误的样本放大化,其它正确的样本缩小化。同样,这样在接下来的分类中就会更加注重这些错误样本。
接着,学生Joey经过观察又说:苹果也可能是绿色的。根据Joey的判断,得到的结果如下图所示:
上图中蓝色区域的图片一样代表分类错误,根据苹果是绿色的条件,使得图中蓝色区域都出现了判断错误。同样把这些分类错误的样本放大化,其它正确的样本缩小化,在下一轮判断继续对其修正。
后来,学生Jessica又发现:上面有梗的才是苹果。得到如下结果:
经过这几个同学的推论,苹果被定义为:圆的,红色的,也可能是绿色的,上面有梗。从一个一个的推导过程中,我们似乎得到一个较为准确的苹果的定义。虽然可能不是非常准确,但是要比单一的条件要好得多。也就是说把所有学生对苹果的定义融合起来,最终得到一个比较好的对苹果的总体定义。这种做法就是我们本节课将要讨论的演算法。这些学生代表的就是简单的hypothesesgtgt,将所有gtgt融合,得到很好的预测模型G。例如,二维平面上简单的hypotheses(水平线和垂直线),这些简单gtgt最终组成的较复杂的分类线能够较好地将正负样本完全分开,即得到了好的预测模型。
所以,上个苹果的例子中,不同的学生代表不同的hypothesesgt;最终得到的苹果总体定义就代表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,我们先来看看gt和g(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,即此gt对G没有什么贡献,权重应该设为零。而当ϵt=0时,没有error,表示该gt预测非常准,此时对应的⋄t=∞,αt=∞,即此gt对G贡献非常大,权重应该设为无穷大。
这种算法被称为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(logN)次迭代之后,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能够得到有效的预测模型。
往期回顾
【1】一文详解Blending和Bagging
【2】深度学习概述
【3】
【4】
【5】卷积神经网络CNN基础
【6】循环神经网络RNN
【7】干货 | 吴恩达deeplearning.ai专项课程历史文章汇总
【8】简单的梯度下降算法,你真的懂了吗?
【9】力荐 | 台大林轩田《机器学习基石》资源汇总
长按二维码
扫描关注
如果喜欢我的文章,就请点赞或转发吧!