Machine Learning Techniques Lecture 11: Gradient Boosted Decision Tree

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的特征转换,而是多种多样。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

2 Comments for “Machine Learning Techniques Lecture 11: Gradient Boosted Decision Tree”
  1. Hi tһеre everyone, it’s my first visit at this web page, and piece of writing іs really fruitful in support
    of me, keep up posting tһese articles.

  2. Ӏ know this site presents quality basеd posts
    and adԀitional material, is there any оther web site which
    provides these things in quality?

Comments are closed.