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

02-10

現在網上介紹gbdt演算法的文章並不算少，但總體看下來，千篇一律的多，能直達精髓的少，有條理性的就更稀少了。我希望通過此篇文章，能抽絲剝繭般的向初學者介紹清楚這個演算法的原理所在。如果仍不清楚可以在文後留言。

1、如何在不改變原有模型的結構上提升模型的擬合能力

假設現在你有樣本集 $(x_{1},y_{1}),(x_{2},y_{2}),...(x_{n},y_{n})$ ，然後你用一個模型，如 $F(x)$ 去擬合這些數據，使得這批樣本的平方損失函數（即 $frac{1}{2}sum_{0}^{n}{}(y_{i}-F(x_{i}))^{2}$ ）最小。但是你發現雖然模型的擬合效果很好，但仍然有一些差距，比如預測值 $F(x_{1})$ =0.8，而真實值 $y_{1}$ =0.9， $F(x_{2})$ =1.4， $y_{2}$ =1.3等等。另外你不允許更改原來模型 $F(x)$ 的參數，那麼你有什麼辦法進一步來提高模型的擬合能力呢。

既然不能更改原來模型的參數，那麼意味著必須在原來模型的基礎之上做改善，那麼直觀的做法就是建立一個新的模型 $f(x)$ 來擬合 $F(x)$ 未完全擬合真實樣本的殘差，即 $y-F(X)$ 。所以對於每個樣本來說，擬合的樣本集就變成了： $(x_{1},y_{1}-F(x_{1})),(x_{2},y_{2}-F(x_{2})),...(x_{n},y_{n}-F(x_{n}))$ .

2、基於殘差的gbdt

在第一部分， $y_{i}-F(x_{i})$ 被稱為殘差，這一部分也就是前一模型（ $F(x_{i})$ ）未能完全擬合的部分，所以交給新的模型來完成。

我們知道gbdt的全稱是Gradient Boosting Decision Tree，其中gradient被稱為梯度，更一般的理解，可以認為是一階導，那麼這裡的殘差與梯度是什麼關係呢。在第一部分，我們提到了一個叫做平方損失函數的東西，具體形式可以寫成 $frac{1}{2}sum_{0}^{n}{}(y_{i}-F(x_{i}))^{2}$ ，熟悉其他演算法的原理應該知道，這個損失函數主要針對回歸類型的問題，分類則是用熵值類的損失函數。具體到平方損失函數的式子，你可能已經發現它的一階導其實就是殘差的形式，所以基於殘差的gbdt是一種特殊的gbdt模型，它的損失函數是平方損失函數，只能處理回歸類的問題。具體形式可以如下表示：

$損失函數：L(y,F(x)) = frac{1}{2}(y-F(X))^{2}$

$所以我們想最小化J = frac{1}{2}sum_{0}^{n}{}(y_{i}-F(x_{i}))^{2}$

損失函數的一階導：

正好殘差就是負梯度：

3、為什麼基於殘差的gbdt不是一個好的選擇

首先基於殘差的gbdt只能處理回歸類的問題，不能處理分類問題，這是損失函數所限制的，所以更一般化的gbdt是基於梯度的演算法，這也就意味著只要我給出的損失函數是可導的，那麼我就能用gbdt的思想去解決問題。具體解決的問題就不會僅僅限於回歸了。

另外，基於殘差的gbdt在解決回歸問題上也不算是一個好的選擇，一個比較明顯的缺點就是對異常值過於敏感。我們來看一個例子：

很明顯後續的模型會對第4個值關注過多，這不是一種好的現象，所以一般回歸類的損失函數會用絕對損失或者huber損失函數來代替平方損失函數：

4、Boosting的加法模型

如前面所述，gbdt模型可以認為是是由k個基模型組成的一個加法運算式：

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

其中F是指所有基模型組成的函數空間。

那麼一般化的損失函數是預測值 $hat{y}$ 與真實值 $y$ 之間的關係，如我們前面的平方損失函數，那麼對於n個樣本來說，則可以寫成：

$L=sum_{i=1}^n l(y_i, hat{y}_i)$

更一般的，我們知道一個好的模型，在偏差和方差上有一個較好的平衡，而演算法的損失函數正是代表了模型的偏差面，最小化損失函數，就相當於最小化模型的偏差，但同時我們也需要兼顧模型的方差，所以目標函數還包括抑制模型複雜度的正則項，因此目標函數可以寫成：

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

其中 $Omega$ 代表了基模型的複雜度，若基模型是樹模型，則樹的深度、葉子節點數等指標可以反應樹的複雜程度。

對於Boosting來說，它採用的是前向優化演算法，即從前往後，逐漸建立基模型來優化逼近目標函數，具體過程如下：

$egin{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}$

那麼，在每一步，如何學習一個新的模型呢，答案的關鍵還是在於gbdt的目標函數上，即新模型的加入總是以優化目標函數為目的的。

我們以第t步的模型擬合為例，在這一步，模型對第 $i$ 個樣本 $x_{i}$ 的預測為：

$hat{y}_i^t= hat{y}_i^{t-1} + f_t(x_i)$

其中 $f_t(x_i)$ 就是我們這次需要加入的新模型，即需要擬合的模型，此時，目標函數就可以寫成：

$egin{split} Obj^{(t)} &= sum_{i=1}^nl(y_i, hat{y}_i^t) + sum_{i=i}^t Omega(f_i) \ &= sum_{i=1}^n lleft(y_i, hat{y}_i^{t-1} + f_t(x_i) ight) + Omega(f_t) + constant end{split} ag{1}$

即此時最優化目標函數，就相當於求得了 $f_t(x_i)$ 。

5、什麼是gbdt的目標函數

我們知道泰勒公式中，若 $Delta x$ 很小時，我們只保留二階導是合理的（gbdt是一階導，xgboost是二階導，我們以二階導為例，一階導可以自己去推，因為更簡單），即：

$f(x+Delta x) approx f(x) + f(x)Delta x + frac12 f(x)Delta x^2 ag 2$

那麼在等式（1）中，我們把 $hat{y}_i^{t-1}$ 看成是等式（2）中的x， $f_t(x_i)$ 看成是 $Delta x$ ，因此等式（1）可以寫成：

$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) ight] + Omega(f_t) + constant ag 3$

其中 $g_{i}$ 為損失函數的一階導， $h_{i}$ 為損失函數的二階導，注意這裡的導是對 $hat{y}_i^{t-1}$ 求導。我們以平方損失函數為例 $sum_{i=1}^n left(y_i - (hat{y}_i^{t-1} + f_t(x_i)) ight)^2$ ，則 $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$ 。

由於在第t步 $hat{y}_i^{t-1}$ 其實是一個已知的值，所以 $l(y_i, hat{y}_i^{t-1})$ 是一個常數，其對函數優化不會產生影響，因此，等式（3）可以寫成：

$Obj^{(t)} approx sum_{i=1}^n left[ g_if_t(x_i) + frac12h_if_t^2(x_i) ight] + Omega(f_t) ag 4$

所以我么只要求出每一步損失函數的一階和二階導的值（由於前一步的 $hat{y}^{t-1}$ 是已知的，所以這兩個值就是常數）代入等式4，然後最優化目標函數，就可以得到每一步的 $f(x)$ ，最後根據加法模型得到一個整體模型。

6、如何用決策樹來表示上一步的目標函數

假設我們boosting的基模型用決策樹來實現，則一顆生成好的決策樹，即結構確定，也就是說樹的葉子結點其實是確定了的。假設這棵樹的葉子結點有 $T$ 片葉子，而每片葉子對應的值 $w in R^T$ 。熟悉決策樹的同學應該清楚，每一片葉子結點中樣本的預測值都會是一樣的，在分類問題中，是某一類，在回歸問題中，是某一個值，那麼肯定存在這樣一個函數 $q:R^d o {1,2,cdots,T}$ ，即將 $f_{t}(x)$ 中的每個樣本映射到每一個葉子結點上，當然 $f_{t}(x)$ 和 $q$ 我們都是不知道的，但我們也不關心，這裡只是說明一下決策樹表達數據結構的方法是怎麼樣的，不理解也沒有問題。

那麼 $f_{t}(x)$ 就可以轉成 $w_{q(x)}$ ，這裡的 $q(x)$ 代表了每個樣本在哪個葉子結點上，而 $w_{q}$ 則代表了哪個葉子結點取什麼 $w$ 值，所以 $w_{q(x)}$ 就代表了每個樣本的取值 $w$ （即預測值）。

如果決策樹的複雜度可以由正則項來定義 $Omega(f_t)=gamma T + frac12 lambda sum_{j=1}^T w_j^2$ ，即決策樹模型的複雜度由生成的樹的葉子節點數量和葉子節點對應的值向量的L2範數決定。

我們假設 $I_j={ i vert q(x_i)=j }$ 為第 $j$ 個葉子節點的樣本集合，則等式4根據上面的一些變換可以寫成：

$egin{split} Obj^{(t)} &approx sum_{i=1}^n left[ g_if_t(x_i) + frac12h_if_t^2(x_i) ight] + Omega(f_t) \ &= sum_{i=1}^n left[ g_iw_{q(x_i)} + frac12h_iw_{q(x_i)}^2 ight] + 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 ight] + gamma T end{split} ag 5$

即我們之前樣本的集合，現在都改寫成葉子結點的集合，由於一個葉子結點有多個樣本存在，因此才有了 $sum_{i in I_j}g_i$ 和 $sum_{i in I_j}h_i$ 這兩項。

定義 $G_j=sum_{i in I_j}g_i$ ， $H_j=sum_{i in I_j}h_i$ ，則等式5可以寫成：

$Obj^{(t)} = sum_{j=1}^T left[G_jw_j + frac12(H_j + lambda)w_j^2 ight] + gamma T$

如果樹的結構是固定的，即 $q$ 是確定的，或者說我們已經知道了每個葉子結點有哪些樣本，所以 $G_j$ 和 $H_j$ 是確定的，但 $w$ 不確定（ $w$ 其實就是我們需要預測的值），那麼令目標函數一階導為0，則可以求得葉子結點 $j$ 對應的值：

$w_j^*=-frac{G_j}{H_j+lambda} ag 6$

目標函數的值可以化簡為：

$Obj = -frac12 sum_{j=1}^T frac{G_j^2}{H_j+lambda} + gamma T ag 7$

7、如何最優化目標函數

那麼對於單棵決策樹，一種理想的優化狀態就是枚舉所有可能的樹結構，因此過程如下：

a、首先枚舉所有可能的樹結構，即 $q$ ；

b、計算每種樹結構下的目標函數值，即等式7的值；

c、取目標函數最小（大）值為最佳的數結構，根據等式6求得每個葉子節點的 $w$ 取值，即樣本的預測值。

但上面的方法肯定是不可行的，因為樹的結構千千萬，所以一般用貪心策略來優化：

a、從深度為0的樹開始，對每個葉節點枚舉所有的可用特徵

b、針對每個特徵，把屬於該節點的訓練樣本根據該特徵值升序排列，通過線性掃描的方式來決定該特徵的最佳分裂點，並記錄該特徵的最大收益（採用最佳分裂點時的收益）

c、選擇收益最大的特徵作為分裂特徵，用該特徵的最佳分裂點作為分裂位置，把該節點生長出左右兩個新的葉節點，並為每個新節點關聯對應的樣本集

d、回到第1步，遞歸執行到滿足特定條件為止

那麼如何計算上面的收益呢，很簡單，仍然緊扣目標函數就可以了。假設我們在某一節點上二分裂成兩個節點，分別是左（L）右（R），則分列前的目標函數是 $-frac12 [frac{(G_L+G_R)^2}{H_L+H_R+lambda}] + gamma$ ，分裂後則是 $-frac12 [ frac{G_L^2}{H_L+lambda} + frac{G_R^2}{H_R+lambda}] +2gamma$ ，則對於目標函數來說，分裂後的收益是（這裡假設是最小化目標函數，所以用分裂前-分裂後）：