Machine Learning Techniques Lecture 11: Gradient Boosted Decision Tree | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 11: Gradient Boosted Decision Tree


 
 

内容:

Gradient Boosted Decision Tree,一开始现讲怎么把adaboost和decision tree搭配起来,需要引进sampling 和pruning才能搭配得很好;然后讲了怎么从优化的角度来看adaboost,找到好的 hypothesis 就是找一个好的方向,找到alpha其实就是走一个适当的步长,对应到adaboost里面的exponential error这样的函数就是优化问题;我们可以把优化观点下的adaboost延伸到其他不同种的错误衡量,映入了gradientboost,他做的事情就是residual fitting,根据余数还剩多少来更新regression的问题,看看能不能做得更好;最后总结了一下aggregation的方法。

 
 


 
 

上一讲:

Random forest模型,就是一堆的decision tree,利用bagging的方式做出一些不一样的decision tree,再把他们合起来。除了基本的bagging和decision tree之外,再加上一些额外的random机制,做到了自动的validation和特征选择。

 
 

这里:

Gradient boosted decision tree

 
 


 
 

上一次讲的random forest,外层是个bagging,里面是decision tree。这里把decision tree结合到adaboost一起的话,就是 Adaboost-Dtree:

  1. 每一轮给我们的资料一群新的weight;
  2. 通过这些weight来使用decision tree学一个g;
  3. 使用linear的方式把g合起来成为G

 
 

要把decision tree搭配adaboost的话,需要把decision tree改造成可以接受权重的形式。

 
 


 
 

带权重的decision tree算法应该要根据权重来最佳化Ein。

 
 

做法:

  1. 打开演算法看看到底哪些地方涉及到权重带来的影响,然后在这些地方代入权重来计算结果。
  2. 但是像decision tree这样的演算法包含很多作者的优化和特殊处理,对于做法一很难做到,因此考虑的做法是原来的演算法不动,而是考虑外面送进演算法的资料做些手脚,把权重的影响用资料来代替。

 
 

比如bagging里面权重为n,则复制资料n份,在此基础上再抽样。因此这里也可以通过已考虑权重的资料来做sampling,这样就可以得到一组可以表达权重信息的资料。

 
 

所以Adaboost-DTree:Adaboost + sampling(通过权重来抽样) + Dtree;这就是其典型做法。

 
 


 
 

当我们通过adaboost得到g以后是怎么决定g票数的:先算一下g的错误率,然后根据上面公式得到g的票数,这是adaboost做的事情。

 
 

问题是:对于完全长成的树,把所有的资料用于训练,Ein为0,加权中后Ein应该也是0,alpha_t则会是无限大,也就是说得到一个跟强很强的权重是无限大,也就是说只要这棵树决定就好了,其他的都是无用的。

问题在于你把所有的资料都用于训练,且让树完全长成。

 
 

改进:砍树不让完全长成;不用所有的资料来训练;… 简单地说就是需要弱一点的树。

做法:我们用的是sampling后的资料,也就是说是部分的资料而不是全部的资料;不让完全长成的方法则是和前面讲的一样,那些方法都可以拿来用。

 
 


 
 

什么样的是最弱的树?

一层高的树,C&RT里面做的事情就是切一刀,想办法让两边加权的纯度越低越好,这样的再结合decision tree就是adaboost-stump。

 
 

也就是说 Adaboost -stump 是 adaboost-Dtree的一个特例。当树的层数那么小的时候,一般都不会出现Ein=0,也就不用担心上面出现权重为无穷大的情况了,这时候就不见得要做sampleing。

 
 


 
 

练习

 
 


 
 

前面复习了一下Adaboost,以及讨论了一下怎么搭配decision tree,现在进一步来看看adaboost算法的奥妙,然后再据此延伸成今天要讲的griendent boosted decision tree模型。

 
 

Adaboost 里面的权重是根据前一轮的权重乘(正确:y_n = g_t(X_n))或者除(错误:y_n != g_t(X_n))方块t,我们简化一下上面的公式变成一行,用符号来控制正负;再化简一下就变成了一个递归推进的式子,也就是U^t+1与U^t相关。根据递推来算Un就是一个连乘的形式,再化为连加的形式。

 
 

橘色的部分:voting score,是小g做投票的结果,是G的分数。

 
 


 
 

Linear model可以看作是两步,第一步是使用hypothesis做特征转换,再用线性模型组合起来,这个线性模型会告诉我们每个g是几票(灰色的条件是说投票权重不能为负的条件),

 
 

我们把g_t(Xn)看作是phine,alpha看作是每个转换过的特征的权重,voting score就是w*phine。我们在SVM里面讲过,w*phine/abs(w) 就是到分割线的距离(SVM里面的常数项b不影响理解)。所以voting score可以看作是某个空间里面还没有正规化的点到分隔线的距离。

 
 

所以 y_n(voting score) 就是 unnormalized margin,所以同样我们希望margin 越大越好,所以我们希望 exp(-y_n(voting score)) 越小越好,所以希望每一个点的权重越小越好。Adaboost 一轮一轮的进行下去,就会使得这个值越来越小,这是Adaboost的一个重要性质。也就是说Adaboost可以达到large margin的效果。

 
 


 
 

Adaboost 可以让公示里面紫色的部分越来越小,也就可以看作是其可以让上面等式的右半部分越来越小,也就是说在最后一轮括号内的部分红色和蓝色相乘是很大的,也就是达到了large margin的效果。

 
 

我们特别的来看看蓝色红色相乘的结果:

  1. 01错误的时候,如图黑色线所示,同号错误为0,异号错误为1;
  2. adaboost错误(紫色部分)的时候,如紫色线所示,是01错误的上限函数。因为是上限函数,类似以前讲过的SVM,logistic regression等等,可以大概的用它来把0/1问题做的比较好。

 
 


 
 

证明:

基本工具是 gradient descent(梯度下降法):如果你要最小化一个函数的话,你做的事情是从你当前的点出发,选择一个方向使得最靠近目标。数学上就是做泰勒展开,梯度描述的就是方向,求一个最好的方向,最终的结果就是负梯度的方向走上n大小的一步。

 
 

这里我们把g_t这个函数当作是方向(原来是向量,向量的ab相互对应,这里是函数,函数的xy相互对应),同样目标是向h(x_n)方向走n远,加入公式后就如上面所示,然后目标是变成最上面的相似公式。首先整理一下公式就出现了U_n^t,式子就简洁多了,再做泰勒展开,原来的公式就可以拆分为两部分,前半部分就是现在的Ein,那么后面一项就应该越小越好,这样就最佳化了Err。

 
 

所以目标就是找到一个好的h让后面这一项越小越好。

 
 


 
 

对于后面那一项,如果做的是binary classification,y,h都是正负1,那么就只有两种情况,yh同号和异号,结果如上面所示。然后再平移出一个项,然后就可以化简为如上所示的结果,所以结论就是要Ein^u越小越好。

 
 

Adaboost 里面的 A 做的事情就是找到一个好的g_t=h,就是好的方向,这个方向代表函数。

 
 


 
 

Adaboost 通过上面所示的式子的最佳化找出g_t,但是每次走一小步代价比较大,能不能走大步一点,或者说干脆找一个最好的n(也就是g固定的时候,n越大步越好)。

 
 

也就是说这里不再和以前gradient descent一样每次步长是一样的,每次一小步,而是一次就走一大步到离目标最近,这是greedily(贪心的)faster(快速的)的n。

这个叫做: steepest descent

 
 

运用 steepest descent 则可以把原来的式子改写成灰色框最后一行所示的结果。绿色表示所有的 正确的U_n^t/所有U_N^t,红色表示的是所有的 错误的U_N^t/所有的U_N^t(epthon_t)。

至此公式只有n是变数,其他都是已知的,单变数做最佳化的问题,微分=0就可以得到结果。

 
 

结果 steepest n = alpha_t。

所以Adaboost:把函数当作是向量一样在gradient上面走了最大的一步。

 
 


 
 

练习

 
 


 
 

上面部分对Adaboost的解释是:Adaboost就是在Err_ada上面每一步都在做最佳化,每一步的时候找出一个h,把它当作g_t,然后决定在这个g_t上面走多长的距离,最终变成这个g_t的票数就是alpha_t。

所以对于公式来说就包含两个部分,一个部分是对h做最佳化,一个部分是对n做最佳化。

 
 

根据这个概念做延伸,拿来对不同的error function做最佳化,扩展为 GradientBoost,做法思想和上面一致,只是把里面计算err的部分换成任何你想要的平滑的error function,这就是adaboost的延伸。

在这架构下你就可以使用不一样的hypothesis,而不再必须是binary classification,最常见的是使用real-output hypothesis,就是实数输出的hypotheris。同样在这里有两个步骤,第一步决定一个最佳化的h,再决定一个最佳化的n。

 
 


 
 

例如说通过GradientBoost方式来做regression:

 
 

regression里面用的err就是平方错误;把紫色部分命名为S_n表示的是当前已经算出来的err,然后再向某个方向的移动(红色蓝色乘积);

灰色框第一步:将红色蓝色部分提出到sum外面的时候做的是 err对s 的偏微分,在s_n的位置取值,这是对于每一个点。

灰色框第二步:微分后的结果。

因为前面一项可以看作是常数,我们要做的是最小化,因此就是后面那一项越小越好。后面这一项只要保证两个乘数的符号不同,结果就是负的就是在减小。我们关注的是正负,对于大小要做限制,不然无限大就是最佳解了。

 
 



上面讲到我们要对h的大小做限制,因为其大小对于我们来说不重要,大小的解决是靠后面计算中的n来解决的。

 
 

如果我们直接限制n=1这样来做限制的话,我们求解的就是有条件的最佳化问题,比较难求解;这边类似以前解决有条件最佳化问题的方法,把条件当作是最佳化问题的一个惩罚项直接加入到式子里面去。就是上面蓝色框内的红色括号部分,一个平方项。然后再可以凑出平方来化简,用来凑数的常数项这里都可以随便加,不影响结果。

 
 

常数对于最佳化都没有影响,只有最后的平方项才会影响最佳化,上面式子里面剩下的部分的意思是:我想要找一个最好的h,那么他就是要和y减掉s的平方误差上尽可能的接近,那就是做regression。因此上面问题的最佳解就是拿 (x, y-s) 来做regression,y-s就是余数。

 
 


 
 

上一步说明的是怎么找出一个好的g_t,就是求解一个(x_n, y_n – s_n)的regression问题,下一步就是怎么得到权重n,意思就是在g_t这个方向上面我们要走做大一步。

 
 

这个问题公式化就是蓝色所示,包括分数s部分,y部分,n*g_t部分,其中g_t是固定的。同样我们可以把这个式子化简为一个平方式:里面包含g_t*n,y-s两项。也就是说g_t和余数y-s越靠近越好,通过调节n使得两个越靠近越好的最佳化问题。这就是一个单变数的linear regression的问题。

 
 

这样就得到了每个g的权重n。

 
 


 
 

把上面的概念都合在一起,就得到了 Gradient Boosted Decision Tree(GBDT) 算法:
 

算法经过T轮之后回传一堆g和alpha,然后直接加权就会得到一个比较好的G。

每一轮:首先想办法求解一个regression问题,使用某一个A(base learn method,这里用的就是decision tree)求解从x_n到余数y_n-s_n得到一个g_t;然后通过一个单变数的linear regression就可以得到对应的alpha_t;然后跟新分数s_n。

 
 

这算法可以看作是 Adaboost Decision Tree 的 regression 版本,这算法在资讯检索领域应用广泛。

 
 


 
 

练习

 
 


 
 

至此介绍了这课里面要提到的所有aggregation model,我们来复习一下。

 
 

首先讲的是blending model,就是如果今天我们手上已经有了一些g,我们希望把他们合起来。

 
 

我们讲了三个基本的blending方法:第一个是uniform blending,每一个g地位一样,直接就是民主投票;第二个是non-uniform blending,就是加权投票,这里通过拿g做特征转换,然后再做一个阶段的linear model就可以得到这个权重应该是多少;第三种是conditional blending,就是在不同的时候使用不同的g,这个其实也可以看作是第二种方式的扩展,只是使用的不是linear model,而是non-linear model来得到权重。

特点:越uniform,越是追求的是稳定性,通过不同的g来修正彼此之间的错误;越non-uniform(conditional),越追求的是能力的强大,但同时带来的就是需要非常的小心避免overfitting。

 
 


 
 

然后讲的是learning model,就是手上还没有g,我们需要边学习g边决定怎么把他们混合起来。

 
 

同样讲了三种learning的面向:第一个是uniform的时候:代表性的是bagging方法,通过bootstripping的方法去学到不一样的g,最后直接就是平均就得到G;第二个是non-uniform的时候,就是linear的时候:Adaboost通过改变资料的权重的方式来得到不一样的g,边得到不一样的g边依据他们的表现来决定他们的最终的权重,从最佳化的角度就是要走最大的一步来决定这个g的票数;第三种是conditional,在不同的时候使用不同的g,有一个代表性的方法是decision tree,透过branching,在树里面通过分叉条件去使用不同的g。

 
 

在这一讲里面还把Adaboost延伸到GradientBoost,同样是需要找到一些不一样的g,不同的是不像adaboost一样重新改变权重,而是在regression的设定里面,透过看看剩下多少余数,在余数上面做learning,做完以后同样看能走多大步的方式来得到权重。

 
 

这四个就是aggregation learning model,都非常实用。

 
 


 
 

至此我们有了这些 aggregation model,我们还能进一步融合他们做一些不一样的事。

 
 

  1. Bagging + Decision Tree = Random Forest:使用的是完全长成的decision tree,还透过投影到不同的方向上让decision tree更为强大。

 
 

  1. Adaboost + Decision Tree = Adaboost D-Tree:使用的则是比较弱的decision tree,因为adaboost就是要把很多弱弱的东西合起来把它变强,一开始用太强的没意义。

 
 

  1. Gradientboost _ Decision Tree = Gradient D-Tree:同样使用的也是比较弱的decisiontree。

 
 


 
 

Aggregation 这个把g合起来变成G的概念为什么会做的好?

 
 

  1. 解决的是underfitting:一对弱弱的合起来会变强,原因是aggregation代表的就是feature transform。
  2. 解决的是overfitting:把很多个合起来以后会找到一个比较中庸的选择,原因是aggregation存在regularization的性质。

 
 

适合的使用会得到比较好的结果。

 
 


 
 

练习

 
 


 
 

总结:

Gradient Boosted Decision Tree,一开始现讲怎么把adaboost和decision tree搭配起来,需要引进sampling 和pruning才能搭配得很好;然后讲了怎么从优化的角度来看adaboost,找到好的 hypothesis 就是找一个好的方向,找到alpha其实就是走一个适当的步长,对应到adaboost里面的exponential error这样的函数就是优化问题;我们可以把优化观点下的adaboost延伸到其他不同种的错误衡量,映入了gradientboost,他做的事情就是residual fitting,根据余数还剩多少来更新regression的问题,看看能不能做得更好;最后总结了一下aggregation的方法。

 
 

下一讲:

至此讲完了aggregation,下面开始探讨说如何让机器自动的学到更多更复杂更不一样的特征,不见得是hypothesis的特征转换,而是多种多样。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

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

  • Categories

  • Tags