Machine Learning Techniques Lecture 8: Adaptive Boosting | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 8: Adaptive Boosting


 
 

内容:

介绍了 Adaboost 演算法,一开始先给大家一个小学生课堂的例子来告诉大家这个演算法想像上是长什么样子的。这算法的关键是每一轮的时候透过重新的给每一个example不一样的权重,提高错误的权重,降低正确的权重来得到不一样的g,最后再把g整合成G。最后给了一个adaboost配合decision stump以后的实例,可以工作的很好。

 
 


 
 

上一讲:开始讲aggregation model,就是想办法把很多的小g合起来变成一个更符合你需求的大G。然后讲到blending,就是如果你已经有很多小g在手上的时候,你可以让他们求平均或者加权投票或者更复杂的非线性组合它们。那如果手上只有一堆已有的资料,那么可以通过bootstrap的方式得到一堆资料集,然后得到一堆小g求大G,这样的演算法叫做bagging。

 
 

今天从这系概念出发,讲一个有趣的演算法。

 
 


 
 

举例:老师交学生辨识图中有没有苹果做法

 
 

首先去网络上手机苹果图片。

 
 


 
 

收集了10张苹果图片,10张不是苹果的图片。老师就是想通过这些数据来学到怎样区分图中有没有苹果的二元分类。

 
 


 
 

放到一起,前十张是苹果,后十张不是苹果。(对应到机器学习里面的supervised learning,告诉x,y)

 
 

第一个学生觉得:苹果是圆形的,不是苹果的很多不是圆形。

根据是不是圆形分类,有些是对的,有些是错的(蓝色的就是错的部分)。

 
 


 
 

为了让学生更认识到这种分类方式的缺陷,老师就把已经作对了的图片缩小,没做对的放大,突出错误的地方。

 
 

然后再问学生还有没有其他的规则来分类?

 
 

第二个学生觉得:苹果是红色的,不是苹果很多都不是红色的。

根据颜色分类,有些是对的,有些是错的。(蓝色标出了错误的)

 
 

同样老师标出了错误的,让后放大缩小来突出错误的。

 
 


 
 

然后再问怎样的才是苹果?

 
 

第三个学生说苹果也可能是绿色的,也是有对有错。

然后老师同样的去放大缩小,然后再以此类推。

 
 


 
 

经过这样的反复,最后会得到的分类结果一般来说总比第一个学生说的单一的分类方法效果好。

 
 


 
 

学生就是小gt,就是上图的水平垂直线;整个班级就是大G,就是把小g融合起来,就是上面弯弯曲曲的黑色边界,很顺利的分开了圈圈叉叉;老师的作用是每一次都强调一下犯错误的地方。

 
 

这就是今天讲的演算法的基本思路。

 
 


 
 

练习

 
 


 
 

我们先从Bagging开始讲起:其核心就是bootstraping抽样动作。如果我们假设得到上面所示的一笔资料四个数据,那接下来做的就是在这个数据的基础上让Ein最小。那么从原始的数据库来看,资料可以标示为资料+U(表示当前这个取出的新的data包含这个数据的个数)。这时候Ein如何方便的标识:算一笔资料的错误率,然后乘上系数U,如上图绿色框所示。

 
 

所以Bagging做的事可以看作是透过bootstrap的方式产生一组U,然后去最小化Ein^u。

 
 


 
 

上面就是一种 Weighted Base Algorithm,就是演算法带有权重参数,可以应用在已有的各种算法里面,譬如SVM(上限发生变化),Logistic regression(抽样的时候U是抽中的权重),蓝色的部分就是原来的公式会变化的部分。

 
 


 
 

如果我们的 weighted base algorithm 会根据这些u来决定,那么我们应该怎么去改变u让得到的g越不一样越好?(上一讲提到过,如果g越不一样,aggregation做的结果越好)
 

g_t 是由 u_t 来当weight,g_t+1 由 U_t+1 来得到的。如果g_t在使用u_t+1的时候非常的不好,后续的过程中就会选到和g_t很不一样的g_t+1。比如对于binary classification,我们的期望是让g_t在u_t+1的时候分类结果最差,就是1/2,和丢铜板一样。

 
 


 
 

怎么做,如红色的部分公式,方块代表犯错误的点的u加起来是多少;圆圈代表的是没犯错的点的u加起来是多少,然后我们想做的就是让犯错的u和没犯错的u调到一样。

举个例子见上面的表格,我们先看现在t时刻的犯错的u=1126,没犯错的6211,目前不相等。然后用放大缩小的方式让两边相等,就是左边的乘6211权重,右边乘1126权重,就等了(或者可以乘以相应的对方的比例)。【简单地说就是配上系数使两边相等,这样下一轮得到的数据用这一轮的分类结果表现就应该会非常差】

 
 


 
 

练习

 
 


 
 

上一小结说的就是 optimal re-weighting:为了让g_t 和 g_t+1 很不一样,对犯错误的点放大。按照上面的求解策略,这里可以定义一个方块t参数,对于错误的和正确的点做如上蓝色框所示的参数相乘。

 
 

当错误率必定是大于1/2的时候,方块t一定大于1,也就是说错误的一定是放大,正确的一定会是缩小操作。(对应到了分苹果的例子的老师的操作)

 
 

这个就是adaboost里面得到不一样的g的方法的理论依据。

 
 


 
 

至此就有了一个初步的演算法的长相:

  1. 参数化原来的bootstrap操作,则可以看作是我们在每一轮里面得到g都是透过u得来的,u就是每个example的权重。
  2. 在每一轮的时候,透过方块t来更新u,目的是让现在的g在下一轮的分类中变的很烂,选出的g就会很不一样。
  3. 透过这些不一样的g来合成大G。

 
 

但是还存在一些问题要解决:

  1. 一开始的u是多少,就是1/N,每个点都一样,让一开始的结果和Ein最小。
  2. 合成G的时候怎么弄,g1对Ein是最好的,g2对Ein就很差了,也就是说各个的权重不一样,不要uniform。

 
 

下面要讲的算法就是在产生g的过程中顺便决定了怎么样把这些g合起来(aggregate linearily on the fly)。

 
 


 
 

算法:

一开始u = 1/N;然后对于每一步有三件事情做,

  1. 生成由u表示的dataset来得到g;
  2. 由u的当前结果来更新u为下一轮做准备;
  3. 计算合成的时候的参数alpha;

最后合成的时候直接每个g乘以自己对应的alpha得到G

 
 

我们希望每个g都很好,很好的概念是方块t应该要很大,所以alpha可以看作是方块出来的某一个单调函数的结果,方块越大,alpha越大。

Alpha = ln(方块t),这是设计这个演算法的人做的选择。物理意义会是 1/2的错误率的时候权重为0,错误率为0的时候权重为无穷大,还是很合理的。

 
 

Adaptive Boosting 包含三个元素:

  1. 通过产生的数据集得到的g(Student)
  2. 用方块t对资料放缩重要性(teacher)
  3. 由g合成成G(Class)

 
 


 
 

Adaptive Boosting (Adaboost) Algorithm 算法:

一开始u = 1/N表示所有的点重要性都一样;然后对于每一步有三件事情做,

  1. 得到一个g;
  2. 把错误的乘以方块t,正确的乘以方块t;
  3. 决定alpha;

最后合成的时候直接每个g乘以自己对应的alpha得到G

 
 


 
 

Adaboost的理论特性,我们来看看把VC bound 用在这里的话会得到什么样的保证。

 
 

Eout(G) <= Ein(G)(已经看过的资料上的表现) + 模型复杂度付出的代价(绿色部分,Dvc(h)表示的是g付出的代价,还要合上T,蓝色部分是标准的Dvc告诉我们的事)

 
 

这个演算法得很好的性质:我们可以在相对很短的时间内把第一项(红色部分)做的很小,大概只要花log(n)轮就能做到Ein(G)为0,也就会把第二项做到很小。

 
 

boosting的意思是:我们的任意g只要比乱猜好一点,那么我们就可以让整个演算法越变越强,强到Ein是0,Eout也是很小。

 
 


 
 

练习

 
 


 
 

上面讲到我们弱弱的演算法g需要比乱猜好一点,什么样的演算法可以做到这件事情呢?

 
 

回头看ML foundations作业里面有一个特殊的模型 decision stump,如上所示公式。

包含三个参数:特征是什么,你要切在那里,正方向是哪面;通过搜寻有限多的组合得到最好的decision stump。这是少数真的能把Ein做到最好的hypothesis,对于weighted Ein也可以搜寻所有的组合想办法做到最好。

物理意义就是二维平面上支持切垂直和水平刀。复杂度是 资料的数量乘以feature的数量。

 
 

Decision stump 单独用能力就是太弱了,因为只能切垂直水平刀,那么我们来配合使用adaboost。

 
 


 
 

资料

 
 


 
 

切一刀,放大的三个圈圈就是犯错误的,没犯错误的缩小。

 
 


 
 

再切,以此类推

 
 


 
 

已经得到了非线性边界

 
 


 
 


 
 


 
 

切完了

 
 


 
 

复杂的例子

 
 


 
 

Adaboost + decision stump 实际上确实也蛮好用的,用于实时人脸辨识。

 
 


 
 

练习

 
 


 
 

总结:

介绍了 Adaboost 演算法,一开始先给大家一个小学生课堂的例子来告诉大家这个演算法想像上是长什么样子的。这算法的关键是每一轮的时候透过重新的给每一个example不一样的权重,提高错误的权重,降低正确的权重来得到不一样的g,最后再把g整合成G。最后给了一个adaboost配合decision stump以后的实例,可以工作的很好。

 
 

下一讲:

Bagging 是 uniform aggregation;Adaboost 是 linear aggregation;下一讲给大家介绍 conditional aggregation 的方法。

 
 

 
 


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags