標(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方法基于這樣一種思想：對于一個復(fù)雜任務(wù)來說，將多個專家的判斷進(jìn)行適當(dāng)?shù)木C合所得出的判斷，要比其中任何一個專家單獨(dú)的判斷要好。通俗地說，就是“三個臭皮匠頂個諸葛亮”的道理。梯度提升同其他boosting方法一樣，通過集成（ensemble）多個弱學(xué)習(xí)器，通常是決策樹，來構(gòu)建最終的預(yù)測模型。
Boosting、bagging和stacking是集成學(xué)習(xí)的三種主要方法。不同于bagging方法，boosting方法通過分步迭代（stage-wise）的方式來構(gòu)建模型，在迭代的每一步構(gòu)建的弱學(xué)習(xí)器都是為了彌補(bǔ)已有模型的不足。Boosting族算法的著名代表是AdaBoost，AdaBoost算法通過給已有模型預(yù)測錯誤的樣本更高的權(quán)重，使得先前的學(xué)習(xí)器做錯的訓(xùn)練樣本在后續(xù)受到更多的關(guān)注的方式來彌補(bǔ)已有模型的不足。與AdaBoost算法不同，梯度提升方法在迭代的每一步構(gòu)建一個能夠沿著梯度最陡的方向降低損失（steepest-descent）的學(xué)習(xí)器來彌補(bǔ)已有模型的不足。經(jīng)典的AdaBoost算法只能處理采用指數(shù)損失函數(shù)的二分類學(xué)習(xí)任務(wù)，而梯度提升方法通過設(shè)置不同的可微損失函數(shù)可以處理各類學(xué)習(xí)任務(wù)（多分類、回歸、Ranking等），應(yīng)用范圍大大擴(kuò)展。另一方面，AdaBoost算法對異常點(diǎn)（outlier）比較敏感，而梯度提升算法通過引入bagging思想、加入正則項(xiàng)等方法能夠有效地抵御訓(xùn)練數(shù)據(jù)中的噪音，具有更好的健壯性。這也是為什么梯度提升算法（尤其是采用決策樹作為弱學(xué)習(xí)器的GBDT算法）如此流行的原因，有種觀點(diǎn)認(rèn)為GBDT是性能最好的機(jī)器學(xué)習(xí)算法，這當(dāng)然有點(diǎn)過于激進(jìn)又固步自封的味道，但通常各類機(jī)器學(xué)習(xí)算法比賽的贏家們都非常青睞GBDT算法，由此可見該算法的實(shí)力不可小覷。
基于梯度提升算法的學(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ù)測速度快。同時，決策樹算法相比于其他的算法需要更少的特征工程，比如可以不用做特征標(biāo)準(zhǔn)化，可以很好的處理字段缺失的數(shù)據(jù)，也可以不用關(guān)心特征間是否相互依賴等。決策樹能夠自動組合多個特征，它可以毫無壓力地處理特征間的交互關(guān)系并且是非參數(shù)化的，因此你不必?fù)?dān)心異常值或者數(shù)據(jù)是否線性可分（舉個例子，決策樹能輕松處理好類別A在某個特征維度x的末端，類別B在中間，然后類別A又出現(xiàn)在特征維度x前端的情況）。不過，單獨(dú)使用決策樹算法時，有容易過擬合缺點(diǎn)。所幸的是，通過各種方法，抑制決策樹的復(fù)雜性，降低單顆決策樹的擬合能力，再通過梯度提升的方法集成多個決策樹，最終能夠很好的解決過擬合的問題。由此可見，梯度提升方法和決策樹學(xué)習(xí)算法可以互相取長補(bǔ)短，是一對完美的搭檔。至于抑制單顆決策樹的復(fù)雜度的方法有很多，比如限制樹的最大深度、限制葉子節(jié)點(diǎn)的最少樣本數(shù)量、限制節(jié)點(diǎn)分裂時的最少樣本數(shù)量、吸收bagging的思想對訓(xùn)練樣本采樣（subsample），在學(xué)習(xí)單顆決策樹時只使用一部分訓(xùn)練樣本、借鑒隨機(jī)森林的思路在學(xué)習(xí)單顆決策樹時只采樣一部分特征、在目標(biāo)函數(shù)中添加正則項(xiàng)懲罰復(fù)雜的樹結(jié)構(gòu)等?，F(xiàn)在主流的GBDT算法實(shí)現(xiàn)中這些方法基本上都有實(shí)現(xiàn)，因此GBDT算法的超參數(shù)還是比較多的，應(yīng)用過程中需要精心調(diào)參，并用交叉驗(yàn)證的方法選擇最佳參數(shù)。
本文對GBDT算法原理進(jìn)行介紹，從機(jī)器學(xué)習(xí)的關(guān)鍵元素出發(fā)，一步一步推導(dǎo)出GBDT算法背后的理論基礎(chǔ)，讀者可以從這個過程中了解到GBDT算法的來龍去脈。對于該算法的工程實(shí)現(xiàn)，本文也有較好的指導(dǎo)意義，實(shí)際上對機(jī)器學(xué)習(xí)關(guān)鍵概念元素的區(qū)分對應(yīng)了軟件工程中的“開放封閉原則”的思想，基于此思想的實(shí)現(xiàn)將會具有很好的模塊獨(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\)時如何預(yù)測出目標(biāo)\(y\)。定義\(x_i \in R^d\) 為訓(xùn)練集中的第\(i\)個訓(xùn)練樣本，則線性模型（linear model）可以表示為：\(\hat{y}_i = \sum_j{w_j x_{ij}}\)。模型預(yù)測的分?jǐn)?shù)\(\hat{y}_i\)在不同的任務(wù)中有不同的解釋。例如在邏輯回歸任務(wù)中，\(1/(1+exp(-\hat{y}_i))\)表示模型預(yù)測為正例的概率；而在排序?qū)W習(xí)任務(wù)中，\(\hat{y}_i\)表示排序分。
參數(shù)就是我們要從數(shù)據(jù)中學(xué)習(xí)得到的內(nèi)容。模型通常是由一個參數(shù)向量決定的函數(shù)。例如，線性模型的參數(shù)可以表示為：\(\Theta=\{w_j|j=1,\cdots,d\}\)。
目標(biāo)函數(shù)通常定義為如下形式：\[ Obj(\Theta)=L(\Theta)+\Omega(\Theta)\] 其中，\(L(\Theta)\)是損失函數(shù)，用來衡量模型擬合訓(xùn)練數(shù)據(jù)的好壞程度；\(\Omega(\Theta)\)稱之為正則項(xiàng)，用來衡量學(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ù)和正則項(xiàng)，損失函數(shù)最小化表明模型能夠較好的擬合訓(xùn)練數(shù)據(jù)，一般也預(yù)示著模型能夠較好地?cái)M合真實(shí)數(shù)據(jù)（groud true）；另一方面，對正則項(xiàng)的優(yōu)化鼓勵算法學(xué)習(xí)到較簡單的模型，簡單模型一般在測試樣本上的預(yù)測結(jié)果比較穩(wěn)定、方差較?。▕W坎姆剃刀原則）。也就是說，優(yōu)化損失函數(shù)盡量使模型走出欠擬合的狀態(tài)，優(yōu)化正則項(xiàng)盡量使模型避免過擬合。
從概念上區(qū)分模型、參數(shù)和目標(biāo)函數(shù)給學(xué)習(xí)算法的工程實(shí)現(xiàn)帶來了益處，使得機(jī)器學(xué)習(xí)的各個組成部分之間耦合盡量松散。
加法模型（additive model）
GBDT算法可以看成是由K棵樹組成的加法模型：\[\hat{y}_i=\sum_{k=1}^K f_k(x_i), f_k \in F \tag 0\] 其中\(zhòng)(F\)為所有樹組成的函數(shù)空間，以回歸任務(wù)為例，回歸樹可以看作為一個把特征向量映射為某個score的函數(shù)。該模型的參數(shù)為：\(\Theta=\{f_1,f_2, \cdots, f_K \}\)。于一般的機(jī)器學(xué)習(xí)算法不同的是，加法模型不是學(xué)習(xí)d維空間中的權(quán)重，而是直接學(xué)習(xí)函數(shù)（決策樹）集合。
上述加法模型的目標(biāo)函數(shù)定義為：\(Obj=\sum_{i=1}^n l(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega(f_k)\)，其中\(zhòng)(\Omega\)表示決策樹的復(fù)雜度，那么該如何定義樹的復(fù)雜度呢？比如，可以考慮樹的節(jié)點(diǎn)數(shù)量、樹的深度或者葉子節(jié)點(diǎn)所對應(yīng)的分?jǐn)?shù)的L2范數(shù)等等。
如何來學(xué)習(xí)加法模型呢？
解這一優(yōu)化問題，可以用前向分布算法（forward stagewise algorithm）。因?yàn)閷W(xué)習(xí)的是加法模型，如果能夠從前往后，每一步只學(xué)習(xí)一個基函數(shù)及其系數(shù)（結(jié)構(gòu)），逐步逼近優(yōu)化目標(biāo)函數(shù)，那么就可以簡化復(fù)雜度。這一學(xué)習(xí)過程稱之為Boosting。具體地，我們從一個常量預(yù)測開始，每次學(xué)習(xí)一個新的函數(shù)，過程如下：\[ \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} \]
那么，在每一步如何決定哪一個函數(shù)\(f\)被加入呢？指導(dǎo)原則還是最小化目標(biāo)函數(shù)。
在第\(t\)步，模型對\(x_i\)的預(yù)測為：\(\hat{y}_i^t= \hat{y}_i^{t-1} + f_t(x_i)\)，其中\(zhòng)(f_t(x_i)\)為這一輪我們要學(xué)習(xí)的函數(shù)（決策樹）。這個時候目標(biāo)函數(shù)可以寫為：
\[ \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} \]
舉例說明，假設(shè)損失函數(shù)為平方損失（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)\)稱之為殘差（residual）。因此，使用平方損失函數(shù)時，GBDT算法的每一步在生成決策樹時只需要擬合前面的模型的殘差。
泰勒公式：設(shè)\(n\)是一個正整數(shù)，如果定義在一個包含\(a\)的區(qū)間上的函數(shù)\(f\)在\(a\)點(diǎn)處\(n+1\)次可導(dǎo)，那么對于這個區(qū)間上的任意\(x\)都有：\(\displaystyle f(x)=\sum _{n=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^ n+R_ n(x)\)，其中的多項(xiàng)式稱為函數(shù)在\(a\)處的泰勒展開式，\(R_ n(x)\)是泰勒公式的余項(xiàng)且是\((x-a)^ n\)的高階無窮小。
----維基百科
根據(jù)泰勒公式把函數(shù)\(f(x+\Delta x)\)在點(diǎn)\(x\)處二階展開，可得到如下等式：
\[f(x+\Delta x) \approx f(x) + f'(x)\Delta x + \frac12 f''(x)\Delta x^2 \tag 3\]
由等式(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}^{t-1}}l(y_i,\hat{y}^{t-1})\)；\(h_i\)定義為損失函數(shù)的二階導(dǎo)數(shù)，即\(h_i=\partial_{\hat{y}^{t-1}}^2l(y_i,\hat{y}^{t-1})\)。
假設(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ù)最小化的過程中不起作用，因此我們可以從等式(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ù)僅僅依賴于目標(biāo)函數(shù)，從等式(5)可以看出只需為學(xué)習(xí)任務(wù)定義好損失函數(shù)，并為每個訓(xùn)練樣本計(jì)算出損失函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)，通過在訓(xùn)練樣本集上最小化等式(5)即可求得每步要學(xué)習(xí)的函數(shù)\(f(x)\)，從而根據(jù)加法模型等式(0)可得最終要學(xué)習(xí)的模型。
GBDT算法
一顆生成好的決策樹，假設(shè)其葉子節(jié)點(diǎn)個數(shù)為\(T\)，該決策樹是由所有葉子節(jié)點(diǎn)對應(yīng)的值組成的向量\(w \in R^T\)，以及一個把特征向量映射到葉子節(jié)點(diǎn)索引（Index）的函數(shù)\(q:R^d \to \{1,2,\cdots,T\}\)組成的。因此，策樹可以定義為\(f_t(x)=w_{q(x)}\)。
決策樹的復(fù)雜度可以由正則項(xiàng)\(\Omega(f_t)=\gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2\)來定義，即決策樹模型的復(fù)雜度由生成的樹的葉子節(jié)點(diǎn)數(shù)量和葉子節(jié)點(diǎn)對應(yīng)的值向量的L2范數(shù)決定。
定義集合\(I_j=\{ i \vert q(x_i)=j \}\)為所有被劃分到葉子節(jié)點(diǎn)\(j\)的訓(xùn)練樣本的集合。等式(5)可以根據(jù)樹的葉子節(jié)點(diǎn)重新組織為T個獨(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)可寫為：
\[Obj^{(t)} = \sum_{j=1}^T \left[G_iw_j + \frac12(H_i + \lambda)w_j^2 \right] + \gamma T\]
假設(shè)樹的結(jié)構(gòu)是固定的，即函數(shù)\(q(x)\)確定，令函數(shù)\(Obj^{(t)}\)的一階導(dǎo)數(shù)等于0，即可求得葉子節(jié)點(diǎn)\(j\)對應(yīng)的值為：\[w_j^*=-\frac{G_j}{H_j+\lambda} \tag 7\] 此時，目標(biāo)函數(shù)的值為\[Obj = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T \tag 8\]
綜上，為了便于理解，單顆決策樹的學(xué)習(xí)過程可以大致描述為：
然而，可能的樹結(jié)構(gòu)數(shù)量是無窮的，所以實(shí)際上我們不可能枚舉所有可能的樹結(jié)構(gòu)。通常情況下，我們采用貪心策略來生成決策樹的每個節(jié)點(diǎn)。
在上述算法的第二步，樣本排序的時間復(fù)雜度為\(O(n \log n)\)，假設(shè)公用K個特征，那么生成一顆深度為K的樹的時間復(fù)雜度為\(O(dKn\log n)\)。具體實(shí)現(xiàn)可以進(jìn)一步優(yōu)化計(jì)算復(fù)雜度，比如可以緩存每個特征的排序結(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ù)值減去左右兩個孩子節(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)樵黾恿藰涞膹?fù)雜性（該分裂增加了一個葉子節(jié)點(diǎn)）帶來的懲罰。
最后，總結(jié)一下GBDT的學(xué)習(xí)算法：
通常在第四步，我們把模型更新公式替換為：\(\hat{y}_i^t = \hat{y}_i^{t-1} + \epsilon f_t(x_i)\)，其中\(zhòng)(\epsilon\)稱之為步長或者學(xué)習(xí)率。增加\(\epsilon\)因子的目的是為了避免模型過擬合。
參考資料
[2] [XGBoost 是一個優(yōu)秀的GBDT開源軟件庫，有多種語言接口](http://xgboost.readthedocs.io/en/latest/)
[3] [Pyramid 是一個基于Java語言的機(jī)器學(xué)習(xí)庫，里面也有GBDT算法的介紹和實(shí)現(xiàn)](https://github.com/cheng-li/pyramid)
[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的一個通俗易懂的解釋，比較適合初學(xué)者或者是已經(jīng)對GBDT算法原理印象不深的從業(yè)者
[6] 關(guān)于GBDT算法調(diào)參的經(jīng)驗(yàn)和技巧可以參考這兩篇博文：《GBM調(diào)參指南》、
《XGBoost調(diào)參指南》，作者使用的算法實(shí)現(xiàn)工具來自于著名的Python機(jī)器學(xué)習(xí)工具scikit-learn
[7] GBDT算法在搜索引擎排序中的應(yīng)用可以查看這篇論文《Web-Search Ranking with Initialized Gradient Boosted Regression Trees》，這篇論文提出了一個非常有意思的方法，用一個已經(jīng)訓(xùn)練好的隨機(jī)森林模型作為GBDT算法的初始化，再用GBDT算法優(yōu)化最終的模型，取得了很好的效果
聯(lián)系客服
