GBDT梯度提升樹

前言

GBDT的全稱是Gradient Boosting Decision Tree，Gradient Boosting和Decision Tree是兩個獨立的概念。

GBDT算法

Boosting講解

Boosting的概念很好了解，意思是用一些弱分類器的組合來構造一個強分類器。是以，它不是某個具體的算法，它說的是一種理念。和這個理念相對應的是一次性構造一個強分類器。像支援向量機，邏輯回歸等都屬于後者。通常，我們通過相加來組合分類器，形式如下：

F m ( x ) = f 0 + a 1 f 1 ( x ) + a 2 f 2 ( x ) + . . . + a m f m ( x ) F_m(x)=f_0+a_1f_1(x)+a_2f_2(x)+...+a_mf_m(x) Fm​(x)=f0​+a1​f1​(x)+a2​f2​(x)+...+am​fm​(x)

其中每一個 f i ( x ) f_i(x) fi​(x)就是一個分類器，強分類器是由多個弱分類器線性相加而成，具體如何做呢？

Boosting，疊代，即通過疊代多棵樹來共同決策。這怎麼實作呢？難道是每棵樹獨立訓練一遍，比如年齡預測，訓練三棵樹，針對A這個樣本，第一棵樹認為是10歲，第二棵樹認為是0歲，第三棵樹認為是20歲，我們就取平均值10歲做最終結論？–當然不是！且不說這是投票方法并不是GBDT，隻要訓練集不變，獨立訓練三次的三棵樹必定完全相同，這樣做完全沒有意義。之前說過，GBDT是把所有樹的結論累加起來做最終結論的，是以可以想到每棵樹的結論并不是年齡本身，而是年齡的一個累加量。GBDT的核心就在于，每一棵樹學的是之前所有樹結論和的殘差，這個殘差加上一棵樹的預測值後能得真實值。比如A的真實年齡是18歲：

• 第一棵樹的預測年齡是12歲，差了6歲，即殘差為6歲。
• 那麼在第二棵樹裡我們把A的年齡設為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子節點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹裡A的年齡就變成1歲，繼續學。

這就是Gradient Boosting在GBDT中的意義。

Decision Tree

Decision Tree是決策樹算法，一種強分類器，決策樹分為兩大類，回歸樹和分類樹。前者用于預測實數值，如明天的溫度、使用者的年齡、網頁的相關程度；後者用于分類标簽值，如晴天/陰天/霧/雨、使用者性别、網頁是否是垃圾頁面。這裡要強調的是，前者的結果加減是有意義的，如10歲+5歲-3歲=12歲，後者則無意義，如男+男+女=到底是男是女？ GBDT的核心在于累加所有樹的結果作為最終結果，就像前面對年齡的累加（-3是加負3），GBDT中一般使用回歸樹，回歸樹不同于分類樹，它原理在下一節會突出。

多子產品累加算法的目标函數

由上述兩個部分我們可以知道梯度提升樹是一個多個提升樹模型混合後的一個模型，形式化如下所示：

y i ^ = ∑ k = 1 K f k ( x i ) \widehat{y_i}=\sum_{k=1}^{K}{f_k(x_i)} yi​

​=k=1∑K​fk​(xi​)

我們定義一個誤差函數 l ( y i , y i ^ ) l(y_i,\widehat{y_i}) l(yi​,yi​

​)，來表示誤差情況，如下所示：

O b j = ∑ i = 1 n l ( y i , y i ^ ) + ∑ k = 1 K Ω ( f k ) Obj = \sum_{i=1}^{n}{l(y_i,\widehat{y_i})}+\sum_{k=1}^{K}{\Omega(f_k)} Obj=i=1∑n​l(yi​,yi​

​)+k=1∑K​Ω(fk​)

• l ( y i , y i ^ ) l(y_i,\widehat{y_i}) l(yi​,yi​

  ​) 表示誤差函數，一般可以為平方損失函數 ( y − y i ^ ) 2 (y-\widehat{y_i})^2 (y−yi​

  ​)2或者Huber loss 損失函數。

• ∑ k = 1 K Ω ( f k ) \sum_{k=1}^{K}{\Omega(f_k)} ∑k=1K​Ω(fk​)代表了基模型的複雜度，用來抑制模型複雜度的正則項，若基模型是樹模型，則樹的深度、葉子節點數等名額可以反應樹的複雜程度。

我們接下來分析 y i ^ \widehat{y_{i}} yi​

​，因為它是有多個模型結果累加起來的，是以我們用另一種方式表示為：

y i t ^ = y i t − 1 ^ + f t ( x i ) \widehat{y_{i}^{t}} = \widehat{y_{i}^{t-1}}+f_t(x_i) yit​

​=yit−1​

​+ft​(xi​)

其中 y ^ i t − 1 \widehat{y}_{i}^{t-1} y

​it−1​為前 t − 1 t-1 t−1次模型結果累加的值，于是在t個模型的時候，他的目标函數為：

O b j t = ∑ i = 1 n l ( y i , y ^ i t − 1 + f t ( x i ) ) + Ω ( f t ) + C Obj^t= \sum_{i=1}^{n}{l(y_i, \widehat{y}_{i}^{t-1}+f_t(x_i))}+\Omega(f_t)+C Objt=i=1∑n​l(yi​,y

​it−1​+ft​(xi​))+Ω(ft​)+C

• 因為是第t個模型，則 ∑ k = 1 K Ω ( f k ) = Ω ( f t ) + C \sum_{k=1}^{K}{\Omega(f_k)} =\Omega(f_t)+C ∑k=1K​Ω(fk​)=Ω(ft​)+C，前t-1個模型都是常量
• 即此時最優化目标函數，就相當于求 f t ( x i ) f_t(x_i) ft​(xi​)，其他都是已知的。

利用二階泰勒展開式來表述該問題：

f ( x + Δ x ) ≈ f ( x ) + f ′ ( x ) Δ x + 1 2 f ′ ′ ( x ) Δ x 2 f(x+\Delta{x}) \approx f(x)+f^{'}(x)\Delta{x}+\frac{1}{2}f^{''}(x)\Delta{x}^2 f(x+Δx)≈f(x)+f′(x)Δx+21​f′′(x)Δx2

我們令 y ^ i t − 1 \widehat{y}_{i}^{t-1} y

​it−1​表示上述公式中的 x x x， f t ( x i ) ) f_t(x_i)) ft​(xi​))表示為公式中的 Δ x \Delta{x} Δx，于是等式就改寫為：

O b j t = ∑ i = 1 n l ( y i , y ^ i t − 1 + f t ( x i ) ) + Ω ( f t ) + C = ∑ i = 1 n [ l ( y i , y ^ i t − 1 ) + g i f t ( x ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) + C \begin{aligned} Obj^t &= \sum_{i=1}^{n}{l(y_i, \widehat{y}_{i}^{t-1}+f_t(x_i))}+\Omega(f_t)+C \\ &=\sum_{i=1}^{n} \bigg[l(y_i,\widehat{y}_{i}^{t-1})+g_if_t(x)+\frac{1}{2}h_if_t^2(x_i) \bigg] +\Omega(f_t)+C \end{aligned} Objt​=i=1∑n​l(yi​,y

​it−1​+ft​(xi​))+Ω(ft​)+C=i=1∑n​[l(yi​,y

​it−1​)+gi​ft​(x)+21​hi​ft2​(xi​)]+Ω(ft​)+C​

• g i g_i gi​表示誤差函數的一階導，也就是 l 函 數 l函數 l函數的一階導數
• h i h_i hi​表示誤差函數的二階導，也就是 l 函 數 l函數 l函數的二階導數

公式是怎麼得來的呢 ？把 y i y_i yi​作為一個常量，不過它本身也是常量，然後對另一個變量使用泰勒展開式，

其實這裡我還有一個疑問，為什麼令 y ^ i t − 1 \widehat{y}_{i}^{t-1} y

​it−1​表示上述公式中的 x x x， f t ( x i ) ) f_t(x_i)) ft​(xi​))表示為公式中的 Δ x \Delta{x} Δx？這個疑惑還不清楚，

但是我們針對第t個模型，我可以可以知道 y ^ i t − 1 \widehat{y}_{i}^{t-1} y

​it−1​是前t-1個模型的輸出累加， y i y_i yi​是樣本的标簽值，都是常量，去掉這些常量，得到如下形式：

O b j t ≈ ∑ i = 1 n [ g i f t ( x ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) Obj^t \approx \sum_{i=1}^{n} \bigg[g_if_t(x)+\frac{1}{2}h_if_t^2(x_i) \bigg] +\Omega(f_t) Objt≈i=1∑n​[gi​ft​(x)+21​hi​ft2​(xi​)]+Ω(ft​)

這就是多個模型累加的目标函數，如果應用在決策樹中，我們來看看會有什麼結果。

應用在回歸樹

一顆生成好的決策樹，其葉子節點個數為T，将所有葉子節點對應值組成的向量 w ∈ R T w∈R^T w∈RT，還有一個把輸入特征向量映射到葉子節點索引（Index）的函數 q : R d → 1 , 2 , ⋯ , T q:R^d→{1,2,⋯,T} q:Rd→1,2,⋯,T組成的。是以，決策樹可以定義為 f t ( x ) = w q ( x ) f_t(x)=w_{q(x)} ft​(x)=wq(x)​。還有一個，決策樹的複雜度如何定義？

Ω ( f t ) = γ T + 1 2 λ ∑ i = 1 T w i 2 \Omega(f_t)=\gamma T+\frac{1}{2}\lambda \sum_{i=1}^{T}{w_{i}^{2}} Ω(ft​)=γT+21​λi=1∑T​wi2​

• 一部分是葉子結點數量
• 另一部分是葉子節點對應的值向量的L2範式

同時假設第 j j jg個樣本上有多個樣本，集合為 I j = { i ∣ q ( x i ) = j } I_j=\{i|q(x_i)=j\} Ij​={i∣q(xi​)=j}，上述公式變為：

O b j t ≈ ∑ i = 1 n [ g i f t ( x ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) = ∑ i = 1 n [ g i w q ( x ) + 1 2 h i w q ( x i ) 2 ] + γ T + 1 2 λ ∑ i = 1 T w i 2 = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w q ( x j ) 2 ] + γ T \begin{aligned} Obj^t &\approx \sum_{i=1}^{n} \bigg[g_if_t(x)+\frac{1}{2}h_if_t^2(x_i) \bigg] +\Omega(f_t) \\ &= \sum_{i=1}^{n} \bigg[g_iw_{q(x)}+\frac{1}{2}h_iw_{q(x_i)}^2 \bigg] +\gamma T+\frac{1}{2}\lambda \sum_{i=1}^{T}{w_{i}^{2}} \\ &= \sum_{j=1}^{T} \bigg[ (\sum_{i\in I_j}{g_i})w_j + \frac{1}{2}(\sum_{i\in I_j}{h_i}+\lambda)w_{q(x_j)}^2 \bigg]+\gamma T \end{aligned} Objt​≈i=1∑n​[gi​ft​(x)+21​hi​ft2​(xi​)]+Ω(ft​)=i=1∑n​[gi​wq(x)​+21​hi​wq(xi​)2​]+γT+21​λi=1∑T​wi2​=j=1∑T​[(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​+λ)wq(xj​)2​]+γT​

G j = ∑ i ∈ I j g i ， H j = ∑ i ∈ I j h i + λ G_j=\sum_{i\in I_j}{g_i}， H_j=\sum_{i\in I_j}{h_i}+\lambda Gj​=∑i∈Ij​​gi​，Hj​=∑i∈Ij​​hi​+λ，等式改寫為：

O b j t = ∑ j = 1 T [ G j w j + 1 2 H i w q ( x j ) 2 ] + γ T Obj^t = \sum_{j=1}^{T} \bigg[ G_jw_j + \frac{1}{2}H_{i}w_{q(x_j)}^2 \bigg]+\gamma T Objt=j=1∑T​[Gj​wj​+21​Hi​wq(xj​)2​]+γT

假設樹的結構是固定的，即函數 q ( x ) q(x) q(x)确定，令函數 O b j ( t ) Obj(t) Obj(t)的一階導數等于0，即可求得葉子節點 j j j對應的值為：

w j = − G j H j + λ w_j=-\frac{G_j}{H_j+\lambda} wj​=−Hj​+λGj​​

此時目标函數變為：

O b j = − 1 2 ∑ j = 1 T G j 2 H j + λ + γ T Obj = -\frac{1}{2}\sum_{j=1}^{T}{\frac{G_j^2}{H_j+\lambda}}+\gamma T Obj=−21​j=1∑T​Hj​+λGj2​​+γT

綜上，為了便于了解，單顆決策樹的學習過程可以大緻描述為：

• 枚舉所有可能的樹結構q
• 用最終的目标函數為每個q計算其對應的分數Obj，分數越小說明對應的樹結構越好
• 根據上一步的結果，找到最佳的樹結構，為樹的每個葉子節點計算預測值 w j w_j wj​

然而，可能的樹結構數量是無窮的，是以實際上我們不可能枚舉所有可能的樹結構。通常情況下，我們采用貪心政策來生成決策樹的每個節點。

• 從深度為0的樹開始，對每個葉節點枚舉所有的可用特征
• 針對每個特征，把屬于該節點的訓練樣本根據該特征值升序排列，通過線性掃描的方式來決定該特征的最佳分裂點，并記錄該特征的最大收益（采用最佳分裂點時的收益）
• 選擇收益最大的特征作為分裂特征，用該特征的最佳分裂點作為分裂位置，把該節點生長出左右兩個新的葉節點，并為每個新節點關聯對應的樣本集
• 回到第1步，遞歸執行到滿足特定條件為止

在上述算法的第二步，樣本排序的時間複雜度為 O ( n l o g n ) O(n logn) O(nlogn)，假設一共有K個特征，那麼生成一顆深度為K的樹的時間複雜度為 O ( d K ∗ n ∗ l o g n ) O(d_K*n*logn) O(dK​∗n∗logn)。具體實作可以進一步優化計算複雜度，比如可以緩存每個特征的排序結果等。

這裡的問題是怎麼求得最大收益？

• 假設樹要分裂成左子樹( L L L)和右子樹( R R R)

• 分裂前的目标函數是：

  O b j a = − 1 2 ( G L + G R ) 2 H L + H R + λ + γ T Obj_a = -\frac{1}{2}{\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}}+\gamma T Obja​=−21​HL​+HR​+λ(GL​+GR​)2​+γT

• 分裂後的目标函數則是：

  O b j b = − 1 2 [ ( G L ) 2 H L + λ + ( G R ) 2 H R + λ ] + 2 γ T Obj_b = -\frac{1}{2}\bigg[ {\frac{(G_L)^2}{H_L+\lambda}}+\frac{(G_R)^2}{H_R+\lambda}\bigg]+2\gamma T Objb​=−21​[HL​+λ(GL​)2​+HR​+λ(GR​)2​]+2γT

• 兩個損失相減 O b j b − O b j a Obj_b-Obj_a Objb​−Obja​這個就是選擇某一個特征之後的收益：

  G a i n = O b j b − O b j a = − 1 2 [ ( G L ) 2 H L + λ + ( G R ) 2 H R + λ − ( G L + G R ) 2 H L + H R + λ ] + γ T \begin{aligned} Gain &=Obj_b-Obj_a \\ &= -\frac{1}{2}\bigg[ {\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} \bigg]+\gamma T \end{aligned} Gain​=Objb​−Obja​=−21​[HL​+λ(GL​)2​+HR​+λ(GR​)2​−HL​+HR​+λ(GL​+GR​)2​]+γT​

  當然這裡很多博文裡選擇 O b j a − O b j b Obj_a - Obj_b Obja​−Objb​，利用分裂前的目标函數減去分裂後的目标函數：

  G a i n = O b j a − O b j b = 1 2 [ ( G L ) 2 H L + λ + ( G R ) 2 H R + λ − ( G L + G R ) 2 H L + H R + λ ] − γ T \begin{aligned} Gain &=Obj_a-Obj_b \\ &= \frac{1}{2}\bigg[ {\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} \bigg]-\gamma T \end{aligned} Gain​=Obja​−Objb​=21​[HL​+λ(GL​)2​+HR​+λ(GR​)2​−HL​+HR​+λ(GL​+GR​)2​]−γT​

  其實不管那種計算方式，隻需要這兩個內插補點的絕對值最大就是收益的最大。

• 針對每個特征計算最大收益之後，比較每個特征的最大收益，選擇收益最大值的特征作為下一個節點，但是這裡好像并沒有說特征的最佳分裂點是如何計算的？

最後，總結一下GBDT的學習算法：

1. 算法每次疊代生成一顆新的決策樹
2. 在每次疊代開始之前，計算損失函數在每個訓練樣本點的一階導數 g i g_i gi​和二階導數 h i h_i hi​

3. 通過貪心政策生成新的決策樹，通過等式(7)計算每個葉節點對應的預測值 f t ( x ) f_t(x) ft​(x)

   f t ( x ) = w j = − G j H j + λ f_t(x)=w_j=-\frac{G_j}{H_j+\lambda} ft​(x)=wj​=−Hj​+λGj​​

4. 把新生成的決策樹 f t ( x ) f_t(x) ft​(x)添加到模型中： y i t = y i t − 1 + f t ( x i ) y^t_i=y^{t−1}_i+f_t(x_i) yit​=yit−1​+ft​(xi​)

通常在第四步，我們把模型更新公式替換為： y i t = y i t − 1 + ϵ f t ( x i ) y^t_i=y^{t−1}_i+\epsilon f_t(x_i) yit​=yit−1​+ϵft​(xi​)，其中 ϵ \epsilon ϵ稱之為步長或者學習率。增加 ϵ \epsilon ϵ因子的目的是為了避免模型過拟合。雖然大家這樣似乎沒有什麼問題，但是依舊有一些問題：

• 模型的個數問題？似乎從上述看，每一個特征就對應一個模型，因為分裂是通過特征值分裂得來的
• 如果前兩個特征就确定了所有樣本，也就終止了，那麼終止條件到底是什麼？

作用範圍

該版本GBDT幾乎可用于所有回歸問題（線性/非線性），相對logistic regression僅能用于線性回歸，GBDT的适用面非常廣。亦可用于二分類問題（設定門檻值，大于門檻值為正例，反之為負例）。

參考部落格

GBDT（MART） 疊代決策樹入門教程 | 簡介

機器學習-一文了解GBDT的原理-20171001