NO IMAGE

GBDT演算法原理深入解析

標籤(空格分隔): 機器學習 整合學習 GBM GBDT XGBoost


梯度提升(Gradient boosting)是一種用於迴歸、分類和排序任務的機器學習技術1,屬於Boosting演算法族的一部分。Boosting是一族可將弱學習器提升為強學習器的演算法,屬於整合學習(ensemble learning)的範疇。Boosting方法基於這樣一種思想:對於一個複雜任務來說,將多個專家的判斷進行適當的綜合所得出的判斷,要比其中任何一個專家單獨的判斷要好。通俗地說,就是“三個臭皮匠頂個諸葛亮”的道理。梯度提升同其他boosting方法一樣,通過整合(ensemble)多個弱學習器,通常是決策樹,來構建最終的預測模型。

Boosting、bagging和stacking是整合學習的三種主要方法。不同於bagging方法,boosting方法通過分步迭代(stage-wise)的方式來構建模型,在迭代的每一步構建的弱學習器都是為了彌補已有模型的不足。Boosting族演算法的著名代表是AdaBoost,AdaBoost演算法通過給已有模型預測錯誤的樣本更高的權重,使得先前的學習器做錯的訓練樣本在後續受到更多的關注的方式來彌補已有模型的不足。與AdaBoost演算法不同,梯度提升方法在迭代的每一步構建一個能夠沿著梯度最陡的方向降低損失(steepest-descent)的學習器來彌補已有模型的不足。經典的AdaBoost演算法只能處理採用指數損失函式的二分類學習任務2,而梯度提升方法通過設定不同的可微損失函式可以處理各類學習任務(多分類、迴歸、Ranking等),應用範圍大大擴充套件。另一方面,AdaBoost演算法對異常點(outlier)比較敏感,而梯度提升演算法通過引入bagging思想、加入正則項等方法能夠有效地抵禦訓練資料中的噪音,具有更好的健壯性。這也是為什麼梯度提升演算法(尤其是採用決策樹作為弱學習器的GBDT演算法)如此流行的原因,有種觀點認為GBDT是效能最好的機器學習演算法,這當然有點過於激進又固步自封的味道,但通常各類機器學習演算法比賽的贏家們都非常青睞GBDT演算法,由此可見該演算法的實力不可小覷。

基於梯度提升演算法的學習器叫做GBM(Gradient Boosting Machine)。理論上,GBM可以選擇各種不同的學習演算法作為基學習器。現實中,用得最多的基學習器是決策樹。為什麼梯度提升方法傾向於選擇決策樹(通常是CART樹)作為基學習器呢?這與決策樹演算法自身的優點有很大的關係。決策樹可以認為是if-then規則的集合,易於理解,可解釋性強,預測速度快。同時,決策樹演算法相比於其他的演算法需要更少的特徵工程,比如可以不用做特徵標準化,可以很好的處理欄位缺失的資料,也可以不用關心特徵間是否相互依賴等。決策樹能夠自動組合多個特徵,它可以毫無壓力地處理特徵間的互動關係並且是非引數化的,因此你不必擔心異常值或者資料是否線性可分(舉個例子,決策樹能輕鬆處理好類別A在某個特徵維度x的末端,類別B在中間,然後類別A又出現在特徵維度x前端的情況)。不過,單獨使用決策樹演算法時,有容易過擬合缺點。所幸的是,通過各種方法,抑制決策樹的複雜性,降低單顆決策樹的擬合能力,再通過梯度提升的方法整合多個決策樹,最終能夠很好的解決過擬合的問題。由此可見,梯度提升方法和決策樹學習演算法可以互相取長補短,是一對完美的搭檔。至於抑制單顆決策樹的複雜度的方法有很多,比如限制樹的最大深度、限制葉子節點的最少樣本數量、限制節點分裂時的最少樣本數量、吸收bagging的思想對訓練樣本取樣(subsample),在學習單顆決策樹時只使用一部分訓練樣本、借鑑隨機森林的思路在學習單顆決策樹時只取樣一部分特徵、在目標函式中新增正則項懲罰複雜的樹結構等。現在主流的GBDT演算法實現中這些方法基本上都有實現,因此GBDT演算法的超引數還是比較多的,應用過程中需要精心調參,並用交叉驗證的方法選擇最佳引數。

本文對GBDT演算法原理進行介紹,從機器學習的關鍵元素出發,一步一步推匯出GBDT演算法背後的理論基礎,讀者可以從這個過程中瞭解到GBDT演算法的來龍去脈。對於該演算法的工程實現,本文也有較好的指導意義,實際上對機器學習關鍵概念元素的區分對應了軟體工程中的“開放封閉原則”的思想,基於此思想的實現將會具有很好的模組獨立性和擴充套件性。

機器學習的關鍵元素

先複習下監督學習的關鍵概念:模型(model)、引數(parameters)、目標函式(objective function)

模型就是所要學習的條件概率分佈或者決策函式,它決定了在給定特徵向量xx時如何預測出目標yy。定義xi∈Rdx_i \in R^d 為訓練集中的第ii個訓練樣本,則線性模型(linear model)可以表示為:y^i=∑jwjxij\hat{y}_i = \sum_j{w_j x_{ij}}。模型預測的分數y^i\hat{y}_i在不同的任務中有不同的解釋。例如在邏輯迴歸任務中,1/(1 exp(−y^i))1/(1 exp(-\hat{y}_i))表示模型預測為正例的概率;而在排序學習任務中,y^i\hat{y}_i表示排序分。

引數就是我們要從資料中學習得到的內容。模型通常是由一個引數向量決定的函式。例如,線性模型的引數可以表示為:Θ={wj|j=1,⋯,d}\Theta=\{w_j|j=1,\cdots,d\}。

目標函式通常定義為如下形式:

Obj(Θ)=L(Θ) Ω(Θ)

Obj(\Theta)=L(\Theta) \Omega(\Theta)
其中,L(Θ)L(\Theta)是損失函式,用來衡量模型擬合訓練資料的好壞程度;Ω(Θ)\Omega(\Theta)稱之為正則項,用來衡量學習到的模型的複雜度。訓練集上的損失(Loss)定義為:L=∑ni=1l(yi,y^i)L=\sum_{i=1}^n l(y_i, \hat{y}_i)。常用的損失函式有平方損失(square loss): l(yi,y^i)=(yi−y^i)2l(y_i, \hat{y}_i)=(y_i – \hat{y}_i)^2;Logistic損失: l(yi,y^i)=yiln(1 eyi) (1−yi)ln(1 ey^i)l(y_i, \hat{y}_i)=y_i ln(1 e^{y_i}) (1-y_i)ln(1 e^{\hat{y}_i})。常用的正則項有L1範數Ω(w)=λ∥w∥1\Omega(w)=\lambda \Vert w \Vert_1和L2範數Ω(w)=λ∥w∥2\Omega(w)=\lambda \Vert w \Vert_2。Ridge regression就是指使用平方損失和L2範數正則項的線性迴歸模型;Lasso regression就是指使用平方損失和L1範數正則項的線性迴歸模型;邏輯迴歸(Logistic regression)指使用logistic損失和L2範數或L1範數正則項的線性模型。

目標函式之所以定義為損失函式和正則項兩部分,是為了儘可能平衡模型的偏差和方差(Bias Variance Trade-off)。最小化目標函式意味著同時最小化損失函式和正則項,損失函式最小化表明模型能夠較好的擬合訓練資料,一般也預示著模型能夠較好地擬合真實資料(groud true);另一方面,對正則項的優化鼓勵演算法學習到較簡單的模型,簡單模型一般在測試樣本上的預測結果比較穩定、方差較小(奧坎姆剃刀原則)。也就是說,優化損失函式儘量使模型走出欠擬合的狀態,優化正則項儘量使模型避免過擬合。

從概念上區分模型、引數和目標函式給學習演算法的工程實現帶來了益處,使得機器學習的各個組成部分之間耦合儘量鬆散。

加法模型(additive model)

GBDT演算法可以看成是由K棵樹組成的加法模型:

y^i=∑k=1Kfk(xi),fk∈F(0)

\hat{y}_i=\sum_{k=1}^K f_k(x_i), f_k \in F \tag 0
其中FF為所有樹組成的函式空間,以迴歸任務為例,迴歸樹可以看作為一個把特徵向量對映為某個score的函式。該模型的引數為:Θ={f1,f2,⋯,fK}\Theta=\{f_1,f_2, \cdots, f_K \}。於一般的機器學習演算法不同的是,加法模型不是學習d維空間中的權重,而是直接學習函式(決策樹)集合。

上述加法模型的目標函式定義為:Obj=∑ni=1l(yi,y^i) ∑Kk=1Ω(fk)Obj=\sum_{i=1}^n l(y_i, \hat{y}_i) \sum_{k=1}^K \Omega(f_k),其中Ω\Omega表示決策樹的複雜度,那麼該如何定義樹的複雜度呢?比如,可以考慮樹的節點數量、樹的深度或者葉子節點所對應的分數的L2範數等等。

如何來學習加法模型呢?

解這一優化問題,可以用前向分佈演算法(forward stagewise algorithm)。因為學習的是加法模型,如果能夠從前往後,每一步只學習一個基函式及其係數(結構),逐步逼近優化目標函式,那麼就可以簡化複雜度。這一學習過程稱之為Boosting。具體地,我們從一個常量預測開始,每次學習一個新的函式,過程如下:

y^0iy^1iy^2iy^ti=0=f1(xi)=y^0i f1(xi)=f1(xi) f2(xi)=y^1i f2(xi)⋯=∑k=1tfk(xi)=y^t−1i ft(xi)

\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}

那麼,在每一步如何決定哪一個函式ff被加入呢?指導原則還是最小化目標函式。
在第tt步,模型對xix_i的預測為:y^ti=y^t−1i ft(xi) \hat{y}_i^t= \hat{y}_i^{t-1} f_t(x_i),其中ft(xi)f_t(x_i)為這一輪我們要學習的函式(決策樹)。這個時候目標函式可以寫為:

Obj(t)=∑i=1nl(yi,y^ti) ∑i=itΩ(fi)=∑i=1nl(yi,y^t−1i ft(xi)) Ω(ft) constant(1)

\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}

舉例說明,假設損失函式為平方損失(square loss),則目標函式為:

Obj(t)=∑i=1n(yi−(y^t−1i ft(xi)))2 Ω(ft) constant=∑i=1n[2(y^t−1i−yi)ft(xi) ft(xi)2] Ω(ft) constant(2)

\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}

其中,(y^t−1i−yi)(\hat{y}_i^{t-1} – y_i)稱之為殘差(residual)。因此,使用平方損失函式時,GBDT演算法的每一步在生成決策樹時只需要擬合前面的模型的殘差。

泰勒公式:設nn是一個正整數,如果定義在一個包含aa的區間上的函式ff在aa點處n 1n 1次可導,那麼對於這個區間上的任意xx都有:f(x)=∑n=0Nf(n)(a)n!(x−a)n Rn(x)\displaystyle f(x)=\sum _{n=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^ n R_ n(x),其中的多項式稱為函式在aa處的泰勒展開式,Rn(x)R_ n(x)是泰勒公式的餘項且是(x−a)n(x-a)^ n的高階無窮小。

—-維基百科

根據泰勒公式把函式f(x Δx)f(x \Delta x)在點xx處二階展開,可得到如下等式:

f(x Δx)≈f(x) f′(x)Δx 12f′′(x)Δx2(3)

f(x \Delta x) \approx f(x) f'(x)\Delta x \frac12 f”(x)\Delta x^2 \tag 3
由等式(1)可知,目標函式是關於變數y^t−1i ft(xi)\hat{y}_i^{t-1} f_t(x_i)的函式,若把變數y^t−1i\hat{y}_i^{t-1}看成是等式(3)中的xx,把變數ft(xi)f_t(x_i)看成是等式(3)中的Δx\Delta x,則等式(1)可轉化為:

Obj(t)=∑i=1n[l(yi,y^t−1i) gift(xi) 12hif2t(xi)] Ω(ft) constant(4)

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
其中,gig_i定義為損失函式的一階導數,即gi=∂y^t−1l(yi,y^t−1)g_i=\partial_{\hat{y}^{t-1}}l(y_i,\hat{y}^{t-1});hih_i定義為損失函式的二階導數,即hi=∂2y^t−1l(yi,y^t−1)h_i=\partial_{\hat{y}^{t-1}}^2l(y_i,\hat{y}^{t-1})。
假設損失函式為平方損失函式,則gi=∂y^t−1(y^t−1−yi)2=2(y^t−1−yi)g_i=\partial_{\hat{y}^{t-1}}(\hat{y}^{t-1} – y_i)^2 = 2(\hat{y}^{t-1} – y_i),hi=∂2y^t−1(y^t−1−yi)2=2h_i=\partial_{\hat{y}^{t-1}}^2(\hat{y}^{t-1} – y_i)^2 = 2,把gig_i和hih_i代入等式(4)即得等式(2)。

由於函式中的常量在函式最小化的過程中不起作用,因此我們可以從等式(4)中移除掉常量項,得:

Obj(t)≈∑i=1n[gift(xi) 12hif2t(xi)] Ω(ft)(5)

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

由於要學習的函式僅僅依賴於目標函式,從等式(5)可以看出只需為學習任務定義好損失函式,併為每個訓練樣本計算出損失函式的一階導數和二階導數,通過在訓練樣本集上最小化等式(5)即可求得每步要學習的函式f(x)f(x),從而根據加法模型等式(0)可得最終要學習的模型。

GBDT演算法

一顆生成好的決策樹,假設其葉子節點個數為TT,該決策樹是由所有葉子節點對應的值組成的向量w∈RTw \in R^T ,以及一個把特徵向量對映到葉子節點索引(Index)的函式q:Rd→{1,2,⋯,T}q:R^d \to \{1,2,\cdots,T\}組成的。因此,策樹可以定義為ft(x)=wq(x)f_t(x)=w_{q(x)}。

決策樹的複雜度可以由正則項Ω(ft)=γT 12λ∑Tj=1w2j\Omega(f_t)=\gamma T \frac12 \lambda \sum_{j=1}^T w_j^2 來定義,即決策樹模型的複雜度由生成的樹的葉子節點數量和葉子節點對應的值向量的L2範數決定。

定義集合Ij={i|q(xi)=j}I_j=\{ i \vert q(x_i)=j \}為所有被劃分到葉子節點jj的訓練樣本的集合。等式(5)可以根據樹的葉子節點重新組織為T個獨立的二次函式的和:

Obj(t)≈∑i=1n[gift(xi) 12hif2t(xi)] Ω(ft)=∑i=1n[giwq(xi) 12hiw2q(xi)] γT 12λ∑j=1Tw2j=∑j=1T⎡⎣(∑i∈Ijgi)wj 12(∑i∈Ijhi λ)w2j⎤⎦ γT(6)

\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

定義Gj=∑i∈IjgiG_j=\sum_{i \in I_j}g_i,Hj=∑i∈IjhiH_j=\sum_{i \in I_j}h_i,則等式(6)可寫為:

Obj(t)=∑j=1T[Giwj 12(Hi λ)w2j] γT

Obj^{(t)} = \sum_{j=1}^T \left[G_iw_j \frac12(H_i \lambda)w_j^2 \right] \gamma T
假設樹的結構是固定的,即函式q(x)q(x)確定,令函式Obj(t) Obj^{(t)}的一階導數等於0,即可求得葉子節點jj對應的值為:

w∗j=−GjHj λ(7)

w_j^*=-\frac{G_j}{H_j \lambda} \tag 7 此時,目標函式的值為

Obj=−12∑j=1TG2jHj λ γT(8)

Obj = -\frac12 \sum_{j=1}^T \frac{G_j^2}{H_j \lambda} \gamma T \tag 8

綜上,為了便於理解,單顆決策樹的學習過程可以大致描述為:
1. 列舉所有可能的樹結構qq
2. 用等式(8)為每個qq計算其對應的分數ObjObj,分數越小說明對應的樹結構越好
3. 根據上一步的結果,找到最佳的樹結構,用等式(7)為樹的每個葉子節點計算預測值

然而,可能的樹結構數量是無窮的,所以實際上我們不可能列舉所有可能的樹結構。通常情況下,我們採用貪心策略來生成決策樹的每個節點。
1. 從深度為0的樹開始,對每個葉節點列舉所有的可用特徵
2. 針對每個特徵,把屬於該節點的訓練樣本根據該特徵值升序排列,通過線性掃描的方式來決定該特徵的最佳分裂點,並記錄該特徵的最大收益(採用最佳分裂點時的收益)
3. 選擇收益最大的特徵作為分裂特徵,用該特徵的最佳分裂點作為分裂位置,把該節點生長出左右兩個新的葉節點,併為每個新節點關聯對應的樣本集
4. 回到第1步,遞迴執行到滿足特定條件為止

在上述演算法的第二步,樣本排序的時間複雜度為O(nlogn)O(n \log n),假設公用K個特徵,那麼生成一顆深度為K的樹的時間複雜度為O(dKnlogn)O(dKn\log n)。具體實現可以進一步優化計算複雜度,比如可以快取每個特徵的排序結果等。

如何計算每次分裂的收益呢?假設當前節點記為CC,分裂之後左孩子節點記為LL,右孩子節點記為RR,則該分裂獲得的收益定義為當前節點的目標函式值減去左右兩個孩子節點的目標函式值之和:Gain=ObjC−ObjL−ObjRGain=Obj_C-Obj_L-Obj_R,具體地,根據等式(8)可得:

Gain=12[G2LHL λ G2RHR λ−(GL GR)2HL HR λ]−γ

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項表示因為增加了樹的複雜性(該分裂增加了一個葉子節點)帶來的懲罰。

最後,總結一下GBDT的學習演算法:
1. 演算法每次迭代生成一顆新的決策樹
2. 在每次迭代開始之前,計算損失函式在每個訓練樣本點的一階導數gig_i和二階導數hih_i
3. 通過貪心策略生成新的決策樹,通過等式(7)計算每個葉節點對應的預測值
4. 把新生成的決策樹ft(x)f_t(x)新增到模型中:y^ti=y^t−1i ft(xi)\hat{y}_i^t = \hat{y}_i^{t-1} f_t(x_i)

通常在第四步,我們把模型更新公式替換為:y^ti=y^t−1i ϵft(xi)\hat{y}_i^t = \hat{y}_i^{t-1} \epsilon f_t(x_i),其中ϵ\epsilon稱之為步長或者學習率。增加ϵ\epsilon因子的目的是為了避免模型過擬合。

參考資料

[1] Gradient Boosting 的更多內容
[2] XGBoost是一個優秀的GBDT開源軟體庫,有多種語言介面
[3] Pyramid是一個基於Java語言的機器學習庫,裡面也有GBDT演算法的介紹和實現
[4] Friedman的論文《Greedy function approximation: a gradient boosting machine》是比較早的GBDT演算法文獻,但是比較晦澀難懂,不適合初學者,高階選手可以進一步學習
[5] “A Gentle Introduction to Gradient Boosting“是關於Gradient Boosting的一個通俗易懂的解釋,比較適合初學者或者是已經對GBDT演算法原理印象不深的從業者
[6] 關於GBDT演算法調參的經驗和技巧可以參考這兩篇博文:《GBM調參指南》、
XGBoost調參指南》,作者使用的演算法實現工具來自於著名的Python機器學習工具scikit-learn
[7] GBDT演算法在搜尋引擎排序中的應用可以檢視這篇論文《Web-Search Ranking with Initialized Gradient Boosted Regression Trees 》,這篇論文提出了一個非常有意思的方法,用一個已經訓練好的隨機森林模型作為GBDT演算法的初始化,再用GBDT演算法優化最終的模型,取得了很好的效果

備註:CSDN對公式的渲染總有一個豎線在後面,影響了美觀。本文最初發布在作業部落,原文連結:https://www.zybuluo.com/yxd/note/611571


  1. https://en.wikipedia.org/wiki/Gradient_boosting
  2. 當然,現在已經有能夠處理多分類或迴歸任務的AdaBoost演算法變種