GBDT算法原理深入解析

1、GBDT 算法原理深入解析標(biāo)簽： 機(jī)器學(xué)習(xí)集成學(xué)習(xí)GBM GBDT XGBoost 梯度提升( Gradient boosting )是一種用于回歸、分類和排序任務(wù)的機(jī)器學(xué)習(xí)技術(shù)，屬于Boosting 算法族的一部分。Boosting 是一族可將弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的算法，屬于集成學(xué)習(xí)(ensemble learning )的范疇。Boosting 方法基于這樣一種思想：對(duì)于一個(gè)復(fù)雜任務(wù)來(lái)說(shuō)，將多個(gè)專家的判斷進(jìn)行適當(dāng)?shù)木C合所得出的判斷，要比其中任何一個(gè)專家單獨(dú)的判斷要好。通俗地說(shuō)，就是“三個(gè)臭皮匠頂個(gè)諸葛亮”的道理。 梯度提升同其他boosting 方法一樣，通過(guò)集成 ( ensemble

2、)多個(gè)弱學(xué)習(xí)器，通常是決策樹，來(lái)構(gòu)建最終的預(yù)測(cè)模型。Boosting 、 bagging 和 stacking 是集成學(xué)習(xí)的三種主要方法。不同于 bagging 方法， boosting 方法通過(guò)分步迭代( stage-wise )的方式來(lái)構(gòu)建模型，在迭代的每一步構(gòu)建的弱學(xué)習(xí)器都是為了彌補(bǔ)已有模型的不足。Boosting 族算法的著名代表是AdaBoost ， AdaBoost 算法通過(guò)給已有模型預(yù)測(cè)錯(cuò)誤的樣本更高的權(quán)重，使得先前的學(xué)習(xí)器做錯(cuò)的訓(xùn)練樣本在后續(xù)受到更多的關(guān)注的方式來(lái)彌補(bǔ)已有模型的不足。與AdaBoost 算法不同，梯度提升方法在迭代的每一步構(gòu)建一個(gè)能夠沿著梯度最陡的方向降低損失(

3、steepest-descent )的學(xué)習(xí)器來(lái)彌補(bǔ)已有模型的不足。經(jīng)典的AdaBoost 算法只能處理采用指數(shù)損失函數(shù)的二分類學(xué)習(xí)任務(wù)，而梯度提升方 法通過(guò)設(shè)置不同的可微損失函數(shù)可以處理各類學(xué)習(xí)任務(wù)（多分類、回歸、Ranking 等） ，應(yīng)用范圍大大擴(kuò)展。另一方面，AdaBoost 算法對(duì)異常點(diǎn)（outlier ）比較敏感，而梯度提升算法通過(guò)引入bagging 思想、加入正則項(xiàng)等方法能夠有效地抵御訓(xùn)練數(shù)據(jù)中的噪音，具有更好的健壯性。這也是為什么梯度提升算法（尤其是采用決策樹作為弱學(xué)習(xí)器的GBDT 算法）如此流行的原因，有種觀點(diǎn)認(rèn)為GBDT 是性能最好的機(jī)器學(xué)習(xí)算法，這當(dāng)然有點(diǎn)過(guò)于激進(jìn)又固步自封

4、的味道，但通常各類機(jī)器學(xué)習(xí)算法比賽的贏家們都非常青睞GBDT 算法， 由此可見該算法的實(shí)力不可小覷?；谔荻忍嵘惴ǖ膶W(xué)習(xí)器叫做 GBM（Gradient Boosting Machine） 。理論上，GBM 可以選擇各種不同的學(xué)習(xí)算法作為基學(xué)習(xí)器?，F(xiàn)實(shí)中，用得最多的基學(xué)習(xí)器是決策樹。為什么梯度提升方法傾向于選擇決策樹 （通常是CART 樹） 作為基學(xué)習(xí)器呢？這與決策樹算法自身的優(yōu)點(diǎn)有很大的關(guān)系。決策樹可以認(rèn)為是if-then 規(guī)則的集合，易于理解，可解釋性強(qiáng)，預(yù)測(cè)速度快。同時(shí)，決策樹算法相比于其他的算法需要更少的特征工程，比如可以不用做特征標(biāo)準(zhǔn)化，可以很好的處理字段缺失的數(shù)據(jù)，也可以不用關(guān)心

5、特征間是否相互依賴等。決策樹能夠自動(dòng)組合多個(gè)特征，它可以毫無(wú)壓力地處理特征間的交互關(guān)系并且是非參數(shù)化的，因此你不必?fù)?dān)心異常值或者數(shù)據(jù)是否線性可分（舉個(gè)例子，決策樹能輕松處理好類別A 在某個(gè)特征維度x 的末端，類別B在中間，然后類別A又由現(xiàn)在特征維度 x前端的情況)不過(guò)，單獨(dú)使用決策樹算法時(shí)，有容易過(guò)擬合缺點(diǎn)。所幸的是，通過(guò)各種方法，抑制決策樹的復(fù)雜性，降低單顆決策樹的擬合能力，再通過(guò)梯度提升的方法集成多個(gè)決策樹，最終能夠很好的解決過(guò)擬合的問(wèn)題。由此可見，梯度提升方法和決策樹學(xué)習(xí)算法可以互相取長(zhǎng)補(bǔ)短，是一對(duì)完美的搭檔。至于抑制單顆決策樹的復(fù)雜度的方法有很多，比如限制樹的最大深度、限制葉子節(jié)點(diǎn)的最

6、少樣本數(shù)量、限制節(jié)點(diǎn)分裂時(shí)的最少樣本數(shù)量、吸收bagging 的思想對(duì)訓(xùn)練樣本采樣( subsample ) ， 在學(xué)習(xí)單顆決策樹時(shí)只使用一部分訓(xùn)練樣本、借鑒隨機(jī)森林的思路在學(xué)習(xí)單顆決策樹時(shí)只采樣一部分特征、在目標(biāo)函數(shù)中添加正則項(xiàng)懲罰復(fù)雜的樹結(jié)構(gòu)等。現(xiàn)在主流的 GBDT 算法實(shí)現(xiàn)中這些方法基本上都有實(shí)現(xiàn)，因此GBDT 算法的超參數(shù)還是比較多的，應(yīng)用過(guò)程中需要精心調(diào)參， 并用交叉驗(yàn)證的方法選擇最佳參數(shù)。本文對(duì) GBDT 算法原理進(jìn)行介紹，從機(jī)器學(xué)習(xí)的關(guān)鍵元素出發(fā)，一步一步推導(dǎo)出 GBDT 算法背后的理論基礎(chǔ)，讀者可以從這個(gè)過(guò)程中了解到 GBDT 算法的來(lái)龍去脈。對(duì)于該算法的工程實(shí)現(xiàn)，本文也有較好

7、的指導(dǎo)意義，實(shí)際上對(duì)機(jī)器學(xué)習(xí)關(guān)鍵概念元素的區(qū)分對(duì)應(yīng)了軟件工程中的“開放封閉原則”的思想，基于此思想的實(shí)現(xiàn)將會(huì)具有很好的模塊獨(dú)立性和擴(kuò)展性。機(jī)器學(xué)習(xí)的關(guān)鍵元素先復(fù)習(xí)下監(jiān)督學(xué)習(xí)的關(guān)鍵概念：模型(model ) 、參數(shù)( parameters ) 、目標(biāo)函數(shù)(objective function )模型就是所要學(xué)習(xí)的條件概率分布或者決策函數(shù)，它決定了在給定特征向量(x)時(shí)如何預(yù)測(cè)由目標(biāo)(y) o定義(x_i in RAd)為訓(xùn)練集中的第(i) 個(gè)訓(xùn)練樣本，則線性模型(linearmodel)可以表示為：(haty_i = sum_jw_jx_ij)。模型預(yù)測(cè)的分?jǐn)?shù)(haty_i) 在不同的任務(wù)中有不

8、同的解釋。例如在邏輯回歸任務(wù)中，(1/(1+exp(-haty_i)表示模型預(yù)測(cè)為正例的概率；而在排序?qū)W習(xí)任務(wù)中，(haty_i) 表示排序分。參數(shù)就是我們要從數(shù)據(jù)中學(xué)習(xí)得到的內(nèi)容。模型通常是由一個(gè)參數(shù)向量決定的函數(shù)。例如，線性模型的參數(shù)可以表示為：(Theta=w_j|j=1,cdots,d) 。目標(biāo)函數(shù)通常定義為如下形式： Obj(Theta)=L(Theta)+Omega(Theta) 其中，(L(Theta) 是損失函數(shù)，用來(lái)衡量模型擬合訓(xùn)練數(shù)據(jù)的好壞程度； (Omega(Theta) 稱之為正則項(xiàng)，用來(lái)衡量學(xué)習(xí)到的模型的復(fù)雜度。訓(xùn)練集上的損失(Loss )定義為：(L=sum_i=1

9、An l(y_i, haty_i) 。常用的損失函數(shù)有平方損失 ( square loss ) ： (l(y_i, haty_i)=(y_i - haty_i)A2)；Logistic 損失： (l(y_i, haty_i)=y_i ln(1+eAy_i) + (1-y_i)ln(1+eAhaty_i) 。常用的正則項(xiàng)有L1 范數(shù)(Omega(w)=lambda Vert w Vert_1) 和 L2 范數(shù) (Omega(w)=lambda Vert w Vert_2)。 Ridge regression就是指使用平方損失和L2 范數(shù)正則項(xiàng)的線性回歸模型；Lasso regression 就是

10、指使用平方損失和L1 范數(shù)正則項(xiàng)的線性回歸模型；邏輯回歸(Logistic regression )指使用logistic 損失和 L2 范數(shù)或 L1 范數(shù)正則項(xiàng)的線性模型。目標(biāo)函數(shù)之所以定義為損失函數(shù)和正則項(xiàng)兩部分，是為了盡可能平衡模型的偏差和方差(Bias Variance Trade-off ) 。最小化目標(biāo)函數(shù)意味著同時(shí)最小化損失函數(shù)和正則項(xiàng)，損失函數(shù)最小化表明模型能夠較好的擬合訓(xùn)練數(shù)據(jù)，一般也預(yù)示著模型能夠較好地?cái)M合真實(shí)數(shù)據(jù)(groud true ) ；另一方面，對(duì)正則項(xiàng)的優(yōu)化鼓勵(lì)算法學(xué)習(xí)到較簡(jiǎn)單的模型，簡(jiǎn)單模型一般在測(cè)試樣本上的預(yù)測(cè)結(jié)果比較穩(wěn)定、方差較小 (奧坎姆剃刀原則)也就是說(shuō)

11、，優(yōu)化損失函數(shù)盡量使模型走出欠擬合的狀態(tài)，優(yōu)化正則項(xiàng)盡量使模型避免過(guò)擬合。從概念上區(qū)分模型、參數(shù)和目標(biāo)函數(shù)給學(xué)習(xí)算法的工程實(shí)現(xiàn)帶來(lái)了益處，使得機(jī)器學(xué)習(xí)的各個(gè)組成部分之間耦合盡量松散。加法模型(additivemodel ) GBDT 算法可以看成是由K 棵樹組成的加法模型：haty_i=sum_k=1AK f_k(x_i), f_k in F tag 0 其中 (F)為所有樹組成的函數(shù)空間，以回歸任務(wù)為例，回歸樹可以看作為一個(gè)把特征向量映射為某個(gè)score 的函數(shù)。該模型的參數(shù)為： (Theta=f_1,f_2, cdots, f_K )。 于一般的機(jī)器學(xué)習(xí)算法不同的是，加法模型不是學(xué)習(xí)d 維

12、空間中的權(quán)重，而是直接學(xué)習(xí)函數(shù)(決策樹)集合。上述加法模型的目標(biāo)函數(shù)定義為：(Obj=sum_i=1An l(y_i, haty_i) + sum_k=1AKOmega(f_k) ，其中 (Omega) 表示決策樹的復(fù)雜度，那么該如何定義樹的復(fù)雜度呢？比如，可以考慮樹的節(jié)點(diǎn)數(shù)量、樹的深度或者葉子節(jié)點(diǎn)所對(duì)應(yīng)的分?jǐn)?shù)的L2 范數(shù)等等。如何來(lái)學(xué)習(xí)加法模型呢？解這一優(yōu)化問(wèn)題，可以用前向分布算法( forward stagewise algorithm ) 。因?yàn)閷W(xué)習(xí)的是加法模型，如果能夠從前往后，每一步只學(xué)習(xí)一個(gè)基函數(shù)及其系數(shù)(結(jié)構(gòu)) ，逐步逼近優(yōu)化目標(biāo)函數(shù)，那么就可以簡(jiǎn)化復(fù)雜度。這一學(xué)習(xí)過(guò)程稱之為Bo

13、osting 。具體地，我們從一個(gè)常量預(yù)測(cè)開始，每次學(xué)習(xí)一個(gè)新的函數(shù)，過(guò)程如下： beginsplithaty_iA0 &= 0 haty_iA1 &= f_1(x_i) = haty_iA0 +f_1(x_i) haty_iA2 &= f_1(x_i) + f_2(x_i) = haty_iA1 +f_2(x_i) & cdots haty_iAt &= sum_k=1At f_k(x_i) = haty_iAt-1 + f_t(x_i) endsplit 那么， 在每一步如何決 定哪一個(gè)函數(shù)(f) 被加入呢？指導(dǎo)原則還是最小化目標(biāo)函數(shù)。在第'

14、(t)步，模型對(duì)(x_i)的預(yù)測(cè)為：(haty_iAt=haty_iAt-1 + f_t(x_i) ，其中 (f_t(x_i) 為這一輪我們要學(xué)習(xí)的函數(shù)(決策樹)。這個(gè)時(shí)候目標(biāo)函數(shù)可以寫為： beginsplit ObjA(t) &= sum_i=1Anl(y_i, haty_iAt) + sum_i=iAt Omega(f_i) &= sum_i=1An lleft(y_i, haty_iAt-1 + f_t(x_i) right) + Omega(f_t) + constant endsplittag1 舉例說(shuō)明，假設(shè)損失函數(shù)為平方損失(square loss )，貝U 目

15、標(biāo)函數(shù)為： beginsplit ObjA(t) &= sum_i=1An left(y_i - (haty_iAt-1 + f_t(x_i) right)A2 +Omega(f_t) + constant &= sum_i=1Anleft2(haty_iAt-1 - y_i)f_t(x_i) + f_t(x_i)A2 right + Omega(f_t) + constant endsplittag2 其中， (haty_iAt-1 - y_i) 稱之為殘差(residual ) 。因此，使用平方損失函數(shù)時(shí)，GBDT 算法的每一步在生成決策樹時(shí)只需要擬合前面的模型的殘差。泰勒

16、公式：設(shè)(n)是一個(gè)正整數(shù)，如果定義在一個(gè)包含(a) 的區(qū)間上的函數(shù)(f) 在 (a) 點(diǎn)處(n+1)次可導(dǎo)，那么對(duì)于這個(gè)區(qū)間上的任意(x)都有：(displaystyle f(x)=sum_n=0ANfracfA(n)(a)n!(x-a)A n+R_ n(x) ，其中的多項(xiàng)式稱為函數(shù)在(a) 處的泰勒展開式，(R_ n(x) 是泰勒公式的余項(xiàng)且是(x-a)A n) 的高階無(wú)窮小。維基百科根據(jù)泰勒公式把函數(shù)(f(x+Delta x) 在點(diǎn) (x) 處二階展開，可得到如下等式： f(x+Delta x) approx f(x) + f'(x)Delta x + frac12 f'

17、'(x)Delta xA2 tag 3 由等式 (1)可知，目標(biāo)函數(shù)是關(guān)于變量 (haty_iAt-1 + f_t(x_i) 的函數(shù)， 若把變量(haty_iAt-1)看成是等式(3)中的 (x)， 把變量 (f_t(x_i) 看成是等式(3)中的(Delta x) ，則等式(1)可轉(zhuǎn)化為： ObjA(t) = sum_i=1Anleft l(y_i, haty_iAt-1) + g_if_t(x_i) + frac12h_if_tA2(x_i) right + Omega(f_t) + constant tag 4 其中， (g_i) 定義為損失函數(shù)的一階導(dǎo)數(shù)，即(g_i=parti

18、al_hatyAt-1l(y_i,hatyAt-1); (h_i)定義為損失函數(shù)的二階導(dǎo)數(shù)，即(h_i=partial_hatyAt-1A2l(y_i,hatyAt-1) 。假設(shè)損失函數(shù)為平方損失函數(shù)，則(g_i=partial_hatyAt-1(hatyAt-1 - y_i)A2 =2(hatyAt-1 - y_i) ，(h_i=partial_hatyAt-1A2(hatyAt-1 - y_i)A2 = 2) ，把(g_i) 和 (h_i) 代入等式(4)即得等式(2)。 由于函數(shù)中的常量在函數(shù)最小化的過(guò)程中不起作用，因此我們可以從等式(4)中移除掉常量項(xiàng)，得： ObjA(t) appro

19、x sum_i=1Anleft g_if_t(x_i) + frac12h_if_tA2(x_i) right + Omega(f_t)tag 5 由于要學(xué)習(xí)的函數(shù)僅僅依賴于目標(biāo)函數(shù)，從等式(5)可以看出只需為學(xué)習(xí)任務(wù)定義好損失函數(shù)，并為每個(gè)訓(xùn)練樣本計(jì)算出損失函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，通過(guò)在訓(xùn)練樣本集上最小化等式(5)即可求得每步要學(xué)習(xí)的函數(shù)(f(x) ，從而根據(jù)加法模型等式(0)可得最終要學(xué)習(xí)的模型。GBDT 算法一顆生成好的決策樹，假設(shè)其葉子節(jié)點(diǎn)個(gè)數(shù)為(T) ，該決策樹是由所有葉子節(jié)點(diǎn)對(duì)應(yīng)的值組成的向量(w in RAT) ， 以及一個(gè)把特征向量映射到葉子節(jié)點(diǎn)索引(Index )的函數(shù)(q

20、:RAdto 1,2,cdots,T) 組成的。因此，策樹可以定義為(f_t(x)=w_q(x) 。決策樹的復(fù)雜度可以由正則項(xiàng)(Omega(f_t)=gamma T + frac12 lambda sum_j=1ATw_jA2)來(lái)定義，即決策樹模型的復(fù)雜度由生成的樹的葉子節(jié)點(diǎn)數(shù)量和葉子節(jié)點(diǎn)對(duì)應(yīng)的值向量的L2 范數(shù)決定。定義集合(I_j= i vert q(x_i尸j )為所有被劃分到葉子節(jié)點(diǎn)(j)的訓(xùn)練樣本的集合。等式 (5)可以根據(jù)樹的葉子節(jié)點(diǎn)重新組織為T 個(gè)獨(dú)立的二次函數(shù)的和： beginsplit ObjA(t) &approxsum_i=1An left g_if_t(x_i)

21、 + frac12h_if_tA2(x_i) right +Omega(f_t) &= sum_i=1An left g_iw_q(x_i) + frac12h_iw_q(x_i)A2 right + gamma T + frac12 lambda sum_j=1AT w_jA2 &= sum_j=1AT left(sum_i in I_jg_i)w_j + frac12(sum_i in I_jh_i + lambda)w_jA2right + gamma T endsplittag 6 定義 (G_j=sum_i in I_jg_i)， (H_j=sum_i in I_jh

22、_i) ，則等式(6)可寫為：ObjA(t) = sum_j=1AT leftG_iw_j + frac12(H_i + lambda)w_jA2 right + gamma T 假設(shè)樹的結(jié)構(gòu)是固定的，即函數(shù) (q(x) 確定，令函數(shù)(ObjA(t) 的一階導(dǎo)數(shù)等于0，即可求得葉子節(jié)點(diǎn)(j) 對(duì)應(yīng)的值為：w_jA*=-fracG_jH_j+lambda tag 7 此時(shí)，目標(biāo)函數(shù)的值為 Obj = -frac12 sum_j=1AT fracG_jA2H_j+lambda+ gamma T tag 8 綜上，為了便于理解，單顆決策樹的學(xué)習(xí)過(guò)程可以大致描述為：枚舉所有可能的樹結(jié)構(gòu)(q) 用等式(

23、8)為每個(gè)'(q)計(jì)算其對(duì)應(yīng)的分?jǐn)?shù)(Obj),分?jǐn)?shù)越小說(shuō)明對(duì)應(yīng)的樹結(jié)構(gòu)越好根據(jù)上一步的結(jié)果，找到最佳的樹結(jié)構(gòu)，用等式 (7) 為樹的每個(gè)葉子節(jié)點(diǎn)計(jì)算預(yù)測(cè)值然而，可能的樹結(jié)構(gòu)數(shù)量是無(wú)窮的，所以實(shí)際上我們不可能枚舉所有可能的樹結(jié)構(gòu)。通常情況下，我們采用貪心策略來(lái)生成決策樹的每個(gè)節(jié)點(diǎn)。從深度為0 的樹開始，對(duì)每個(gè)葉節(jié)點(diǎn)枚舉所有的可用特征針對(duì)每個(gè)特征，把屬于該節(jié)點(diǎn)的訓(xùn)練樣本根據(jù)該特征值升序排列，通過(guò)線性掃描的方式來(lái)決定該特征的最佳分裂點(diǎn)，并記錄該特征的最大收益(采用最佳分裂點(diǎn)時(shí)的收益)選擇收益最大的特征作為分裂特征，用該特征的最佳分裂點(diǎn)作為分裂位置，把該節(jié)點(diǎn)生長(zhǎng)出左右兩個(gè)新的葉節(jié)點(diǎn)，并為每個(gè)新

24、節(jié)點(diǎn)關(guān)聯(lián)對(duì)應(yīng)的樣本集回到第1 步，遞歸執(zhí)行到滿足特定條件為止在上述算法的第二步，樣本排序的時(shí)間復(fù)雜度為(O(nlog n) ，假設(shè)公用K 個(gè)特征，那么生成一顆深度為K 的樹的時(shí)間復(fù)雜度為(O(dKnlog n) 。具體實(shí)現(xiàn)可以進(jìn)一步優(yōu)化計(jì)算復(fù)雜度，比如可以緩存每個(gè)特征的排序結(jié)果等。如何計(jì)算每次分裂的收益呢？假設(shè)當(dāng)前節(jié)點(diǎn)記為(C), 分裂之后左孩子節(jié)點(diǎn)記為(L) ，右孩子節(jié)點(diǎn)記為(R) ，則該分裂獲得的收益定義為當(dāng)前節(jié)點(diǎn)的目標(biāo)函數(shù)值減去左右兩個(gè)孩子節(jié)點(diǎn)的目標(biāo)函數(shù)值之和：(Gain=Obj_C-Obj_L-Obj_R) ， 具體地，根據(jù)等式(8)可得：Gain=frac12left fracG_LA2H_L+lambda +fracG_RA2H_R+lambda-frac(G_L+G_R)A2H_L+H_R+lambdaright - gamma其中， (-gamma) 項(xiàng)表示因?yàn)樵黾恿藰涞膹?fù)雜性(該分裂增加了一個(gè)葉子節(jié)點(diǎn))帶來(lái)的懲罰。最后，總結(jié)一下GBDT 的學(xué)習(xí)算法：算法每次迭代生成一顆新的決策樹在每次迭代開始之前，計(jì)算損失函數(shù)在每個(gè)訓(xùn)練樣本點(diǎn)的一階導(dǎo)數(shù)(g_i)和二階導(dǎo)數(shù)(h_i) 通過(guò)貪心策略生成新的決策樹，通過(guò)等式(7)計(jì)算每個(gè)葉