全網(wǎng)最淺顯易懂的GBDT(xgboost)算法原理深入剖析

梯度提升（Gradient boosting）是一種用于回歸、分類(lèi)和排序任務(wù)的技術(shù)，屬于Boosting算法族的一部分。Boosting是一族可將弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的算法，屬于集成學(xué)習(xí)（ensemble learning）的范疇。Boosting方法基于這樣一種思想：對(duì)于一個(gè)復(fù)雜任務(wù)來(lái)說(shuō)，將多個(gè)專(zhuān)家的判斷進(jìn)行適當(dāng)?shù)木C合所得出的判斷，要比其中任何一個(gè)專(zhuān)家單獨(dú)的判斷要好。通俗地說(shuō)，就是“三個(gè)臭皮匠頂個(gè)諸葛亮”的道理。梯度提升同其他boosting方法一樣，通過(guò)集成（ensemble）多個(gè)弱學(xué)習(xí)器，通常是決策樹(shù)，來(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è)能夠沿著梯度最陡的方向降低損失（steepest-descent）的學(xué)習(xí)器來(lái)彌補(bǔ)已有模型的不足。經(jīng)典的AdaBoost算法只能處理采用指數(shù)損失函數(shù)的二分類(lèi)學(xué)習(xí)任務(wù)，而梯度提升方法通過(guò)設(shè)置不同的可微損失函數(shù)可以處理各類(lèi)學(xué)習(xí)任務(wù)（多分類(lèi)、回歸、Ranking等），應(yīng)用范圍大大擴(kuò)展。另一方面，AdaBoost算法對(duì)異常點(diǎn)（outlier）比較敏感，而梯度提升算法通過(guò)引入bagging思想、加入正則項(xiàng)等方法能夠有效地抵御訓(xùn)練數(shù)據(jù)中的噪音，具有更好的健壯性。這也是為什么梯度提升算法（尤其是采用 決策樹(shù) 作為弱學(xué)習(xí)器的GBDT算法）如此流行的原因。之前有種觀點(diǎn)認(rèn)為GBDT是性能最好的 機(jī)器學(xué)習(xí) 算法，這當(dāng)然有點(diǎn)過(guò)于激進(jìn)又固步自封的味道，但通常各類(lèi)機(jī)器學(xué)習(xí)算法比賽的贏家們都非常青睞GBDT算法，由此可見(jiàn)該算法的實(shí)力不可小覷。

基于梯度提升算法的學(xué)習(xí)器叫做GBM(Gradient Boosting Machine)。理論上，GBM可以選擇各種不同的學(xué)習(xí)算法作為基學(xué)習(xí)器?，F(xiàn)實(shí)中，用得最多的基學(xué)習(xí)器是決策樹(shù)。為什么梯度提升方法傾向于選擇決策樹(shù)（通常是CART樹(shù)）作為基學(xué)習(xí)器呢？這與決策樹(shù)算法自身的優(yōu)點(diǎn)有很大的關(guān)系。決策樹(shù)可以認(rèn)為是if-then規(guī)則的集合，易于理解，可解釋性強(qiáng)，預(yù)測(cè)速度快。同時(shí)，決策樹(shù)算法相比于其他的算法需要更少的特征工程，比如可以不用做特征標(biāo)準(zhǔn)化，可以很好的處理字段缺失的數(shù)據(jù)，也可以不用關(guān)心特征間是否相互依賴(lài)等。決策樹(shù)能夠自動(dòng)組合多個(gè)特征，它可以毫無(wú)壓力地處理特征間的交互關(guān)系并且是非參數(shù)化的，因此你不必?fù)?dān)心異常值或者數(shù)據(jù)是否線性可分（舉個(gè)例子，決策樹(shù)能輕松處理好類(lèi)別A在某個(gè)特征維度x的末端，類(lèi)別B在中間，然后類(lèi)別A又出現(xiàn)在特征維度x前端的情況）。不過(guò)，單獨(dú)使用決策樹(shù)算法時(shí)，有容易過(guò)擬合的缺點(diǎn)。所幸的是，通過(guò)各種方法，抑制決策樹(shù)的復(fù)雜性，降低單顆決策樹(shù)的擬合能力，再通過(guò)梯度提升的方法集成多個(gè)決策樹(shù)，最終能夠很好的解決過(guò)擬合的問(wèn)題。由此可見(jiàn)，梯度提升方法和決策樹(shù)學(xué)習(xí)算法可以互相取長(zhǎng)補(bǔ)短，是一對(duì)完美的搭檔。至于抑制單顆決策樹(shù)的復(fù)雜度的方法有很多，比如限制樹(shù)的最大深度、限制葉子節(jié)點(diǎn)的最少樣本數(shù)量、限制節(jié)點(diǎn)分裂時(shí)的最少樣本數(shù)量、吸收bagging的思想對(duì)訓(xùn)練樣本采樣（subsample），在學(xué)習(xí)單顆決策樹(shù)時(shí)只使用一部分訓(xùn)練樣本、借鑒隨機(jī)森林的思路在學(xué)習(xí)單顆決策樹(shù)時(shí)只采樣一部分特征、在目標(biāo)函數(shù)中添加正則項(xiàng)懲罰復(fù)雜的樹(shù)結(jié)構(gòu)等?，F(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)，本文也有較好的指導(dǎo)意義，實(shí)際上對(duì) 機(jī)器學(xué)習(xí)關(guān)鍵概念元素的區(qū)分對(duì)應(yīng)了軟件工程中的“開(kāi)放封閉原則”的思想，基于此思想的實(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。定義 x_i \in R^d 為訓(xùn)練集中的第i個(gè)訓(xùn)練樣本，則線性模型（linear model）可以表示為：\hat{y}_i = \sum_j{w_j x_{ij}}。模型預(yù)測(cè)的分?jǐn)?shù)\hat{y}_i在不同的任務(wù)中有不同的解釋。例如在邏輯回歸任務(wù)中，1/(1+exp(-\hat{y}_i))表示模型預(yù)測(cè)為正例的概率；而在排序?qū)W習(xí)任務(wù)中，\hat{y}_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)稱(chēng)之為正則項(xiàng)，用來(lái)衡量學(xué)習(xí)到的模型的復(fù)雜度。訓(xùn)練集上的損失（Loss）定義為：L=\sum_{i=1}^n l(y_i, \hat{y}_i)。

常用的損失函數(shù)有:

  • 平方損失（square loss）： l(y_i, \hat{y}_i)=(y_i - \hat{y}_i)^2；
  • Logistic損失： l(y_i, \hat{y}_i)=y_i ln(1+e^{y_i}) + (1-y_i)ln(1+e^{\hat{y}_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就是指使用平方損失和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)定、方差較?。▕W坎姆剃刀原則）。也就是說(shuō)，優(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è)組成部分之間耦合盡量松散。

加法模型（additive model）

GBDT算法可以看成是由K棵樹(shù)組成的加法模型。一般我們使用CART（classification and regression tree）樹(shù)作為集成學(xué)習(xí)的基礎(chǔ)模塊，下圖是一顆用來(lái)預(yù)測(cè)某用戶(hù)是否喜歡電腦游戲X的例子，該例子中人群被劃分到不同的葉子節(jié)點(diǎn)，每個(gè)葉子節(jié)點(diǎn)被賦予一個(gè)分?jǐn)?shù)來(lái)表示其與目標(biāo)的關(guān)聯(lián)度。

cart.png

通常，一棵樹(shù)并不足以強(qiáng)大到能夠解決問(wèn)題，我們使用基于多棵樹(shù)的集成模型來(lái)建模。在GBDT算法中，該集成模型即加法模型，它的形式化如下：

\hat{y}_i=\sum_{k=1}^K f_k(x_i), f_k \in F \tag 0

其中F為所有樹(shù)組成的函數(shù)空間，以回歸任務(wù)為例，回歸樹(shù)可以看作為一個(gè)把特征向量映射為某個(gè)score的函數(shù)。該模型的參數(shù)為：\Theta={f_1,f_2, \cdots, f_K }。與一般的機(jī)器學(xué)習(xí)算法不同的是，加法模型不是學(xué)習(xí)d維空間中的權(quán)重，而是直接學(xué)習(xí)函數(shù)（決策樹(shù)）集合。

twocart.png

如上圖所示，每個(gè)樣本的最終得分是由每顆子樹(shù)的得分相加得到的。

上述加法模型的目標(biāo)函數(shù)定義為：

Obj=\sum_{i=1}^n l(y_i, \hat{y}i) + \sum_{k=1}^K \Omega(f_k)，

其中\Omega(\cdot)是正則項(xiàng)，表示決策樹(shù)的復(fù)雜度，那么該如何定義樹(shù)的復(fù)雜度呢？比如，可以考慮樹(shù)的節(jié)點(diǎn)數(shù)量、樹(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ù)（在GBDT算法中即為樹(shù)的結(jié)構(gòu)和葉子節(jié)點(diǎn)的分?jǐn)?shù)），逐步逼近優(yōu)化目標(biāo)函數(shù)，那么就可以簡(jiǎn)化復(fù)雜度。這一學(xué)習(xí)過(guò)程稱(chēng)之為Boosting。具體地，我們從一個(gè)常量預(yù)測(cè)開(kāi)始，每次學(xué)習(xí)一個(gè)新的函數(shù)，過(guò)程如下：

\begin{split} \hat{y}_i^0 &= 0 \\ \hat{y}_i^1 &= f_1(x_i) = \hat{y}_i^0 + f_1(x_i) \\ \hat{y}_i^2 &= f_1(x_i) + f_2(x_i) = \hat{y}_i^1 + f_2(x_i) \\ & \cdots \\ \hat{y}_i^t &= \sum_{k=1}^t f_k(x_i) = \hat{y}_i^{t-1} + f_t(x_i) \ \end{split}

那么，在每一步如何決定哪一個(gè)函數(shù)f被加入呢？指導(dǎo)原則還是最小化目標(biāo)函數(shù)。 在第t步，模型對(duì)x_i的預(yù)測(cè)為：\hat{y}_i^t= \hat{y}_i^{t-1} + f_t(x_i)，其中f_t(x_i)為這一輪我們要學(xué)習(xí)的函數(shù)（決策樹(shù)）。這個(gè)時(shí)候目標(biāo)函數(shù)可以寫(xiě)為：

\begin{split} Obj^{(t)} &= \sum_{i=1}^nl(y_i, \hat{y}_i^t) + \sum_{i=i}^t \Omega(f_i) \\ &= \sum_{i=1}^n l\left(y_i, \hat{y}_i^{t-1} + f_t(x_i) \right) + \Omega(f_t) + constant \end{split}\tag{1}

舉例說(shuō)明，假設(shè)損失函數(shù)為平均平方損失（mean square loss），則目標(biāo)函數(shù)為：

\begin{split} Obj^{(t)} &= \sum_{i=1}^n \left(y_i - (\hat{y}_i^{t-1} + f_t(x_i)) \right)^2 + \Omega(f_t) + constant \\ &= \sum_{i=1}^n \left[2(\hat{y}_i^{t-1} - y_i)f_t(x_i) + f_t(x_i)^2 \right] + \Omega(f_t) + constant \end{split}\tag{2}

其中，(\hat{y}_i^{t-1} - y_i)稱(chēng)之為殘差（residual）。因此，在使用平方損失函數(shù)時(shí)，GBDT算法的每一步在生成決策樹(shù)時(shí)只需要擬合前面的模型的殘差。

在使用其他損失函數(shù)時(shí)，如logistic loss，就很難得到如MSE損失那樣簡(jiǎn)潔的解析表達(dá)式。因此，Xgboost使用泰勒公式的二階展開(kāi)式來(lái)近似目標(biāo)函數(shù)，詳細(xì)過(guò)程如下：

泰勒公式：設(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=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^ n+R_n(x)，其中的多項(xiàng)式稱(chēng)為函數(shù)在 a 處的泰勒展開(kāi)式，R_n(x)是泰勒公式的余項(xiàng)且是(x-a)^ n的高階無(wú)窮小。
其中，零階導(dǎo)數(shù)理解為本身，常數(shù)0階導(dǎo)數(shù)仍為本身，函數(shù)的0階導(dǎo)數(shù)為函數(shù)本身；并且規(guī)定0!=1。

根據(jù)泰勒公式把函數(shù)f(x+\Delta x)在點(diǎn)x處二階展開(kāi)，可得到如下等式： f(x+\Delta x) \approx f(x) + f'(x)\Delta x + \frac12 f''(x)\Delta x^2 \tag 3
（即用x+\Delta x代替泰勒公式中的x，并且用x代替泰勒公式中的a）

由等式(1)可知，目標(biāo)函數(shù)是關(guān)于變量 \hat{y}_i^{t-1} + f_t(x_i) 的函數(shù)，若把變量\hat{y}_i^{t-1}看成是等式(3)中的x，把變量f_t(x_i)看成是等式(3)中的\Delta x，則等式(1)可轉(zhuǎn)化為：

Obj^{(t)} = \sum_{i=1}^n \left[ l(y_i, \hat{y}_i^{t-1}) + g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) + constant \tag 4

其中，g_i定義為損失函數(shù)的一階導(dǎo)數(shù)，即g_i=\partial_{\hat{y}_i^{t-1}}l(y_i,\hat{y}_i^{t-1})；h_i定義為損失函數(shù)的二階導(dǎo)數(shù)，即h_i=\partial_{\hat{y}_i^{t-1}}^2l(y_i,\hat{y}_i^{t-1})。 這里需要注意的是，損失函數(shù)是對(duì)前一步的預(yù)測(cè)結(jié)果\hat{y}_i^{t-1}求導(dǎo)。

假設(shè)損失函數(shù)為平方損失函數(shù)，則g_i=\partial_{\hat{y}^{t-1}}(\hat{y}^{t-1} - y_i)^2 = 2(\hat{y}^{t-1} - y_i)，h_i=\partial_{\hat{y}^{t-1}}^2(\hat{y}^{t-1} - y_i)^2 = 2，把g_i和h_i代入等式(4)即得等式(2)。

由于函數(shù)中的常量在函數(shù)最小化的過(guò)程中不起作用，因此我們可以從等式(4)中移除掉常量項(xiàng)，得：
Obj^{(t)} \approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \tag 5

由于要學(xué)習(xí)的函數(shù)僅僅依賴(lài)于目標(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ù)，假設(shè)其葉子節(jié)點(diǎn)個(gè)數(shù)為T，該決策樹(shù)是由所有葉子節(jié)點(diǎn)對(duì)應(yīng)的值組成的向量w \in R^T，以及一個(gè)把特征向量映射到葉子節(jié)點(diǎn)索引（Index）的函數(shù)q:R^d \to {1,2,\cdots,T}組成的。因此，策樹(shù)可以定義為f_t(x)=w_{q(x)}。

決策樹(shù)的復(fù)雜度可以由正則項(xiàng) \Omega(f_t)=\gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 來(lái)定義，即 決策樹(shù)模型的復(fù)雜度由生成的樹(shù)的葉子節(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ù)樹(shù)的葉子節(jié)點(diǎn)重新組織為T個(gè)獨(dú)立的二次函數(shù)的和：
\begin{split} Obj^{(t)} &\approx \sum_{i=1}^n \left[ g_if_t(x_i) + \frac12h_if_t^2(x_i) \right] + \Omega(f_t) \\ &= \sum_{i=1}^n \left[ g_iw_{q(x_i)} + \frac12h_iw_{q(x_i)}^2 \right] + \gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=1}^T \left[(\sum_{i \in I_j}g_i)w_j + \frac12(\sum_{i \in I_j}h_i + \lambda)w_j^2 \right] + \gamma T \end{split}\tag 6

定義G_j=\sum_{i \in I_j}g_i，H_j=\sum_{i \in I_j}h_i，則等式(6)可寫(xiě)為：
Obj^{(t)} = \sum_{j=1}^T \left[G_iw_j + \frac12(H_i + \lambda)w_j^2 \right] + \gamma T

假設(shè)樹(shù)的結(jié)構(gòu)是固定的，即由函數(shù)q(x)確定，令函數(shù)Obj^{(t)}對(duì)參數(shù) w_j 的一階導(dǎo)數(shù)等于0，即可求得葉子節(jié)點(diǎn) j 對(duì)應(yīng)的值為：w_j^*=-\frac{G_j}{H_j+\lambda} \tag 7

此時(shí)，目標(biāo)函數(shù)的值為
Obj^* = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T \tag 8
該函數(shù)度量了一顆樹(shù)結(jié)構(gòu)的好壞程度，其類(lèi)似于決策樹(shù)算法中的不純度度量（impurity measure），只是額外考慮了正則項(xiàng)。

struct_score.png

綜上，為了便于理解，單顆決策樹(shù)的學(xué)習(xí)過(guò)程可以大致描述為：

  1. 枚舉所有可能的樹(shù)結(jié)構(gòu) q
  2. 用等式(8)為每個(gè) q 計(jì)算其對(duì)應(yīng)的分?jǐn)?shù)Obj，分?jǐn)?shù)越小說(shuō)明對(duì)應(yīng)的樹(shù)結(jié)構(gòu)越好
  3. 根據(jù)上一步的結(jié)果，找到最佳的樹(shù)結(jié)構(gòu)，用等式(7)為樹(shù)的每個(gè)葉子節(jié)點(diǎn)計(jì)算預(yù)測(cè)值

然而，可能的樹(shù)結(jié)構(gòu)數(shù)量是無(wú)窮的，所以實(shí)際上我們不可能枚舉所有可能的樹(shù)結(jié)構(gòu)。通常情況下，我們采用貪心策略來(lái)生成決策樹(shù)的每個(gè)節(jié)點(diǎn)。

  1. 從深度為0的樹(shù)開(kāi)始，對(duì)每個(gè)葉節(jié)點(diǎn)枚舉所有的可用特征
  2. 針對(duì)每個(gè)特征，把屬于該節(jié)點(diǎn)的訓(xùn)練樣本根據(jù)該特征值升序排列，通過(guò)線性掃描的方式來(lái)決定該特征的最佳分裂點(diǎn)，并記錄該特征的最大收益（采用最佳分裂點(diǎn)時(shí)的收益）；這里假設(shè)類(lèi)別型特征已經(jīng)做了one-hot編碼
  3. 選擇收益最大的特征作為分裂特征，用該特征的最佳分裂點(diǎn)作為分裂位置，把該節(jié)點(diǎn)生長(zhǎng)出左右兩個(gè)新的葉節(jié)點(diǎn)，并為每個(gè)新節(jié)點(diǎn)關(guān)聯(lián)對(duì)應(yīng)的樣本集
  4. 回到第1步，遞歸執(zhí)行到滿足特定條件為止

在上述算法的第二步，樣本排序的時(shí)間復(fù)雜度為O(n \log n)，假設(shè)共有 K 個(gè)特征，那么生成一顆深度為 d 的樹(shù)的時(shí)間復(fù)雜度為O(dKn\log 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=\frac12 \left[ \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma 其中，-\gamma 項(xiàng)表示因?yàn)樵黾恿藰?shù)的復(fù)雜性（該分裂增加了一個(gè)葉子節(jié)點(diǎn)）帶來(lái)的懲罰。當(dāng)節(jié)點(diǎn)的最佳分裂收益小于0時(shí)（也就是不考慮增加樹(shù)的復(fù)雜性懲罰時(shí)的收益小于\gamma時(shí)），意味著此時(shí)最好不要分裂該節(jié)點(diǎn)。這也就是決策樹(shù)剪枝算法的原理。搜索某特征最佳分裂點(diǎn)的過(guò)程可參考下面的例子。

split_find.png

A left to right scan is sufficient to calculate the structure score of all possible split solutions, and we can find the best split efficiently.

關(guān)于如何計(jì)算特征的重要度，請(qǐng)參考《Tree ensemble算法的特征重要度計(jì)算》。

最后，總結(jié)一下GBDT的學(xué)習(xí)算法：

  1. 算法每次迭代生成一顆新的 決策樹(shù)
  2. 在每次迭代開(kāi)始之前，計(jì)算損失函數(shù)在每個(gè)訓(xùn)練樣本點(diǎn)的一階導(dǎo)數(shù)g_i和二階導(dǎo)數(shù)h_i
  3. 通過(guò)貪心策略生成新的 決策樹(shù)，通過(guò)等式(7)計(jì)算每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)的預(yù)測(cè)值
  4. 把新生成的 決策樹(shù)f_t(x)添加到模型中：\hat{y}_i^t = \hat{y}_i^{t-1} + f_t(x_i)

通常在第四步，我們把模型更新公式替換為：\hat{y}_i^t = \hat{y}_i^{t-1} + \epsilon f_t(x_i)，其中\epsilon稱(chēng)之為步長(zhǎng)或者學(xué)習(xí)率。增加\epsilon因子的目的是為了避免模型過(guò)擬合。

參考資料

  • [1] Gradient Boosting 的更多內(nèi)容
  • [2] XGBoost 是一個(gè)優(yōu)秀的GBDT開(kāi)源軟件庫(kù)，有多種語(yǔ)言接口
  • [3] Pyramid 是一個(gè)基于Java語(yǔ)言的機(jī)器學(xué)習(xí)庫(kù)，里面也有GBDT算法的介紹和實(shí)現(xiàn)
  • [4] Friedman的論文《Greedy function approximation: a gradient boosting machine》是比較早的GBDT算法文獻(xiàn)，但是比較晦澀難懂，不適合初學(xué)者，高階選手可以進(jìn)一步學(xué)習(xí)
  • [5] "A Gentle Introduction to Gradient Boosting"是關(guān)于Gradient Boosting的一個(gè)通俗易懂的解釋?zhuān)容^適合初學(xué)者或者是已經(jīng)對(duì)GBDT算法原理印象不深的從業(yè)者
  • [6] 關(guān)于GBDT算法調(diào)參的經(jīng)驗(yàn)和技巧可以參考這兩篇博文：《GBM調(diào)參指南》、 《XGBoost調(diào)參指南》，作者使用的算法實(shí)現(xiàn)工具來(lái)自于著名的Python機(jī)器學(xué)習(xí)工具scikit-learn
  • [7] GBDT算法在搜索引擎排序中的應(yīng)用可以查看這篇論文《Web-Search Ranking with Initialized Gradient Boosted Regression Trees 》，這篇論文提出了一個(gè)非常有意思的方法，用一個(gè)已經(jīng)訓(xùn)練好的隨機(jī)森林模型作為GBDT算法的初始化，再用GBDT算法優(yōu)化最終的模型，取得了很好的效果
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容