在內建學習之Adaboost算法原理小結中，我們對Boosting家族的Adaboost算法做了總結，本文就對Boosting家族中另一個重要的算法梯度提升樹(Gradient Boosting Decison Tree, 以下簡稱GBDT)做一個總結。GBDT有很多簡稱，有GBT(Gradient Boosting Tree), GTB(Gradient Tree Boosting )， GBRT(Gradient Boosting Regression Tree), MART(Multiple Additive Regression Tree)，其實都是指的同一種算法，本文統一簡稱GBDT。GBDT在BAT大廠中也有廣泛的應用，假如要選擇3個最重要的機器學習算法的話，個人認為GBDT應該占一席之地。
1. GBDT概述
GBDT也是內建學習Boosting家族的成員，但是卻和傳統的Adaboost有很大的不同。回顧下Adaboost，我們是利用前一輪疊代弱學習器的誤差率來更新訓練集的權重，這樣一輪輪的疊代下去。GBDT也是疊代，使用了前向分布算法，但是弱學習器限定了隻能使用CART回歸樹模型，同時疊代思路和Adaboost也有所不同。
在GBDT的疊代中，假設我們前一輪疊代得到的強學習器是$f_{t-1}(x)$, 損失函數是$L(y, f_{t-1}(x))$, 我們本輪疊代的目标是找到一個CART回歸樹模型的弱學習器$h_t(x)$，讓本輪的損失函數$L(y, f_{t}(x)) =L(y, f_{t-1}(x)+ h_t(x))$最小。也就是說，本輪疊代找到決策樹，要讓樣本的損失盡量變得更小。
GBDT的思想可以用一個通俗的例子解釋，假如有個人30歲，我們首先用20歲去拟合，發現損失有10歲，這時我們用6歲去拟合剩下的損失，發現差距還有4歲，第三輪我們用3歲拟合剩下的差距，差距就隻有一歲了。如果我們的疊代輪數還沒有完，可以繼續疊代下面，每一輪疊代，拟合的歲數誤差都會減小。
從上面的例子看這個思想還是蠻簡單的，但是有個問題是這個損失的拟合不好度量，損失函數各種各樣，怎麼找到一種通用的拟合方法呢？
2. GBDT的負梯度拟合
在上一節中，我們介紹了GBDT的基本思路，但是沒有解決損失函數拟合方法的問題。針對這個問題，大牛Freidman提出了用損失函數的負梯度來拟合本輪損失的近似值，進而拟合一個CART回歸樹。第t輪的第i個樣本的損失函數的負梯度表示為$$r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)}$$
利用$(x_i,r_{ti})\;\; (i=1,2,..m)$,我們可以拟合一顆CART回歸樹，得到了第t顆回歸樹，其對應的葉節點區域$R_{tj}, j =1,2,..., J$。其中J為葉子節點的個數。
針對每一個葉子節點裡的樣本，我們求出使損失函數最小，也就是拟合葉子節點最好的的輸出值$c_{tj}$如下：$$c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c)$$
這樣我們就得到了本輪的決策樹拟合函數如下：$$h_t(x) = \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})$$
進而本輪最終得到的強學習器的表達式如下：$$f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj}) $$
通過損失函數的負梯度來拟合，我們找到了一種通用的拟合損失誤差的辦法，這樣無輪是分類問題還是回歸問題，我們通過其損失函數的負梯度的拟合，就可以用GBDT來解決我們的分類回歸問題。差別僅僅在于損失函數不同導緻的負梯度不同而已。
3. GBDT回歸算法
好了，有了上面的思路，下面我們總結下GBDT的回歸算法。為什麼沒有加上分類算法一起？那是因為分類算法的輸出是不連續的類别值，需要一些處理才能使用負梯度，我們在下一節講。
輸入是訓練集樣本$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$， 最大疊代次數T, 損失函數L。
輸出是強學習器f(x)
1) 初始化弱學習器$$f_0(x) = \underbrace{arg\; min}_{c}\sum\limits_{i=1}^{m}L(y_i, c)$$
2) 對疊代輪數t=1,2,...T有：
a)對樣本i=1,2，...m，計算負梯度$$r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)}$$
b)利用$(x_i,r_{ti})\;\; (i=1,2,..m)$, 拟合一顆CART回歸樹,得到第t顆回歸樹，其對應的葉子節點區域為$R_{tj}, j =1,2,..., J$。其中J為回歸樹t的葉子節點的個數。
c) 對葉子區域j =1,2,..J,計算最佳拟合值$$c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c)$$
d) 更新強學習器$$f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj}) $$
3) 得到強學習器f(x)的表達式$$f(x) = f_T(x) =f_0(x) + \sum\limits_{t=1}^{T}\sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})$$
4. GBDT分類算法
這裡我們再看看GBDT分類算法，GBDT的分類算法從思想上和GBDT的回歸算法沒有差別，但是由于樣本輸出不是連續的值，而是離散的類别，導緻我們無法直接從輸出類别去拟合類别輸出的誤差。
為了解決這個問題，主要有兩個方法，一個是用指數損失函數，此時GBDT退化為Adaboost算法。另一種方法是用類似于邏輯回歸的對數似然損失函數的方法。也就是說，我們用的是類别的預測機率值和真實機率值的差來拟合損失。本文僅讨論用對數似然損失函數的GBDT分類。而對于對數似然損失函數，我們又有二進制分類和多元分類的差別。
4.1 二進制GBDT分類算法
對于二進制GBDT，如果用類似于邏輯回歸的對數似然損失函數，則損失函數為：$$L(y, f(x)) = log(1+ exp(-yf(x)))$$
其中$y \in\{-1, +1\}$。則此時的負梯度誤差為$$r_{ti} = -\bigg[\frac{\partial L(y, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)} = y_i/(1+exp(y_if(x_i)))$$
對于生成的決策樹，我們各個葉子節點的最佳負梯度拟合值為$$c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} log(1+exp(-y_i(f_{t-1}(x_i) +c)))$$
由于上式比較難優化，我們一般使用近似值代替$$c_{tj} = \sum\limits_{x_i \in R_{tj}}r_{ti}\bigg / \sum\limits_{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|)$$
除了負梯度計算和葉子節點的最佳負梯度拟合的線性搜尋，二進制GBDT分類和GBDT回歸算法過程相同。
4.2 多元GBDT分類算法
多元GBDT要比二進制GBDT複雜一些，對應的是多元邏輯回歸和二進制邏輯回歸的複雜度差别。假設類别數為K，則此時我們的對數似然損失函數為：$$L(y, f(x)) = - \sum\limits_{k=1}^{K}y_klog\;p_k(x) $$
其中如果樣本輸出類别為k，則$y_k=1$。第k類的機率$p_k(x) $的表達式為：$$p_k(x) = exp(f_k(x)) \bigg / \sum\limits_{l=1}^{K} exp(f_l(x)) $$
集合上兩式，我們可以計算出第$t$輪的第$i$個樣本對應類别$l$的負梯度誤差為$$r_{til} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f_k(x) = f_{l, t-1}\;\; (x)} = y_{il} - p_{l, t-1}(x_i)$$
觀察上式可以看出，其實這裡的誤差就是樣本$i$對應類别$l$的真實機率和$t-1$輪預測機率的內插補點。
對于生成的決策樹，我們各個葉子節點的最佳負梯度拟合值為$$c_{tjl} = \underbrace{arg\; min}_{c_{jl}}\sum\limits_{i=0}^{m}\sum\limits_{k=1}^{K} L(y_k, f_{t-1, l}(x) + \sum\limits_{j=0}^{J}c_{jl} I(x_i \in R_{tjl}))$$
由于上式比較難優化，我們一般使用近似值代替$$c_{tjl} = \frac{K-1}{K} \; \frac{\sum\limits_{x_i \in R_{tjl}}r_{til}}{\sum\limits_{x_i \in R_{til}}|r_{til}|(1-|r_{til}|)}$$
除了負梯度計算和葉子節點的最佳負梯度拟合的線性搜尋，多元GBDT分類和二進制GBDT分類以及GBDT回歸算法過程相同。
5. GBDT常用損失函數
這裡我們再對常用的GBDT損失函數做一個總結。
對于分類算法，其損失函數一般有對數損失函數和指數損失函數兩種:
a) 如果是指數損失函數，則損失函數表達式為$$L(y, f(x)) = exp(-yf(x))$$
其負梯度計算和葉子節點的最佳負梯度拟合參見Adaboost原理篇。
b) 如果是對數損失函數，分為二進制分類和多元分類兩種，參見4.1節和4.2節。
對于回歸算法，常用損失函數有如下4種:
a)均方差，這個是最常見的回歸損失函數了$$L(y, f(x)) =(y-f(x))^2$$
b)絕對損失，這個損失函數也很常見$$L(y, f(x)) =|y-f(x)|$$
對應負梯度誤差為：$$sign(y_i-f(x_i))$$
c)Huber損失，它是均方差和絕對損失的折衷産物，對于遠離中心的異常點，采用絕對損失，而中心附近的點采用均方差。這個界限一般用分位數點度量。損失函數如下：
$$L(y, f(x))=
\begin{cases}
\frac{1}{2}(y-f(x))^2& {|y-f(x)| \leq \delta}\\
\delta(|y-f(x)| - \frac{\delta}{2})& {|y-f(x)| > \delta}
\end{cases}$$
對應的負梯度誤差為：
$$r(y_i, f(x_i))=
\begin{cases}
y_i-f(x_i)& {|y_i-f(x_i)| \leq \delta}\\
\delta sign(y_i-f(x_i))& {|y_i-f(x_i)| > \delta}
\end{cases}$$
d) 分位數損失。它對應的是分位數回歸的損失函數，表達式為$$L(y, f(x)) =\sum\limits_{y \geq f(x)}\theta|y - f(x)| + \sum\limits_{y < f(x)}(1-\theta)|y - f(x)| $$
其中$\theta$為分位數，需要我們在回歸前指定。對應的負梯度誤差為：
$$r(y_i, f(x_i))=
\begin{cases}
\theta& { y_i \geq f(x_i)}\\
\theta - 1 & {y_i < f(x_i) }
\end{cases}$$
對于Huber損失和分位數損失，主要用于健壯回歸，也就是減少異常點對損失函數的影響。
6. GBDT的正則化
和Adaboost一樣，我們也需要對GBDT進行正則化，防止過拟合。GBDT的正則化主要有三種方式。
第一種是和Adaboost類似的正則化項，即步長(learning rate)。定義為$\nu$,對于前面的弱學習器的疊代$$f_{k}(x) = f_{k-1}(x) + h_k(x) $$
如果我們加上了正則化項，則有$$f_{k}(x) = f_{k-1}(x) + \nu h_k(x) $$
$\nu$的取值範圍為$0 < \nu \leq 1 $。對于同樣的訓練集學習效果，較小的$\nu$意味着我們需要更多的弱學習器的疊代次數。通常我們用步長和疊代最大次數一起來決定算法的拟合效果。
第二種正則化的方式是通過子采樣比例(subsample)。取值為(0,1]。注意這裡的子采樣和随機森林不一樣，随機森林使用的是放回抽樣，而這裡是不放回抽樣。如果取值為1，則全部樣本都使用，等于沒有使用子采樣。如果取值小于1，則隻有一部分樣本會去做GBDT的決策樹拟合。選擇小于1的比例可以減少方差，即防止過拟合，但是會增加樣本拟合的偏差，是以取值不能太低。推薦在[0.5, 0.8]之間。
使用了子采樣的GBDT有時也稱作随機梯度提升樹(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采樣，程式可以通過采樣分發到不同的任務去做boosting的疊代過程，最後形成新樹，進而減少弱學習器難以并行學習的弱點。
第三種是對于弱學習器即CART回歸樹進行正則化剪枝。在決策樹原理篇裡我們已經講過，這裡就不重複了。
7. GBDT小結
GBDT終于講完了，GDBT本身并不複雜，不過要吃透的話需要對內建學習的原理，決策樹原理和各種損失函樹有一定的了解。由于GBDT的卓越性能，隻要是研究機器學習都應該掌握這個算法，包括背後的原理和應用調參方法。目前GBDT的算法比較好的庫是xgboost。當然scikit-learn也可以。
最後總結下GBDT的優缺點。
GBDT主要的優點有：
1) 可以靈活處理各種類型的資料，包括連續值和離散值。
2) 在相對少的調參時間情況下，預測的準确率也可以比較高。這個是相對SVM來說的。
3)使用一些健壯的損失函數，對異常值的魯棒性非常強。比如 Huber損失函數和Quantile損失函數。
GBDT的主要缺點有：
1)由于弱學習器之間存在依賴關系，難以并行訓練資料。不過可以通過自采樣的SGBT來達到部分并行。
以上就是GBDT的原理總結，後面會講GBDT的scikit-learn調參，敬請期待。
(歡迎轉載，轉載請注明出處。歡迎溝通交流： [email protected])