集成學習之Boosting —— Gradient Boosting原理

08-17

來自專欄數據科學の雜談5 人贊了文章

集成學習之Boosting —— AdaBoost原理

集成學習之Boosting —— AdaBoost實現

集成學習之Boosting —— Gradient Boosting原理

集成學習之Boosting —— Gradient Boosting實現

上一篇介紹了AdaBoost演算法，在AdaBoost中每一輪基學習器訓練過後都會更新樣本權重，再訓練下一個學習器，最後將所有的基學習器加權組合。AdaBoost使用的是指數損失，這個損失函數的缺點是對於異常點非常敏感，（關於各種損失函數可見之前的文章：常見回歸和分類損失函數比較），因而通常在噪音比較多的數據集上表現不佳。Gradient Boosting在這方面進行了改進，使得可以使用任何損失函數 (只要損失函數是連續可導的)，這樣一些比較robust的損失函數就能得以應用，使模型抗噪音能力更強。

Boosting的基本思想是通過某種方式使得每一輪基學習器在訓練過程中更加關註上一輪學習錯誤的樣本，區別在於是採用何種方式？AdaBoost採用的是增加上一輪學習錯誤樣本的權重的策略，而在Gradient Boosting中則將負梯度作為上一輪基學習器犯錯的衡量指標，在下一輪學習中通過擬合負梯度來糾正上一輪犯的錯誤。這裡的關鍵問題是：為什麼通過擬合負梯度就能糾正上一輪的錯誤了？Gradient Boosting的發明者給出的答案是：函數空間的梯度下降。

函數空間的的梯度下降

首先回顧一下梯度下降 (Gradient Descend)。機器學習的一大主要步驟是通過優化方法最小化損失函數 $L( heta)$ ，進而求出對應的參數 $heta$ 。梯度下降是經典的數值優化方法，其參數更新公式：

$heta = heta - alpha cdot frac{partial}{partial heta}L( heta) ag{1.1}$

Gradient Boosting 採用和AdaBoost同樣的加法模型，在第m次迭代中，前m-1個基學習器都是固定的，即 $f_m(x) = f_{m-1}(x) + ho_m h_m(x) ag{1.2}$

因而在第m步我們的目標是最小化損失函數 $L(f) = sumlimits_{i=1}^NL(y_i,f_m(x_i))$ ，進而求得相應的基學習器。若將 $f(x)$ 當成參數，則同樣可以使用梯度下降法：

$f_m(x) = f_{m-1}(x) - ho_m cdot frac{partial}{partial f_{m-1}(x)}L(y,f_{m-1}(x)) ag{1.3}$

對比式 (1.2)和 (1.3)，可以發現若將 $h_m(x) approx -frac{partial L(y,f_{m-1}(x))}{partial f_{m-1}(x)}$ ，即用基學習器 $h_m(x)$ 擬合前一輪模型損失函數的負梯度，就是通過梯度下降法最小化 $L(f)$ 。由於 $f(x)$ 實際為函數，所以該方法被認為是函數空間的梯度下降。

負梯度也被稱為「響應 (response)」或「偽殘差 (pseudo residual)」，從名字可以看出是一個與殘差接近的概念。直覺上來看，殘差 $r = y-f(x)$ 越大，表明前一輪學習器 $f(x)$ 的結果與真實值 $y$ 相差較大，那麼下一輪學習器通過擬合殘差或負梯度，就能糾正之前的學習器犯錯較大的地方。

Gradient Boosting演算法流程

1. 初始化： $f_0(x) = mathop{argmin}limits_gamma sumlimits_{i=1}^N L(y_i, gamma)$
2. for m=1 to M:
(a) 計算負梯度： $ilde{y}i = -frac{partial L(y_i,f{m-1}(x_i))}{partial f_{m-1}(x_i)}, qquad i = 1,2 cdots N$
(b) 通過最小化平方誤差，用基學習器 $h_m(x)$ 擬合 $ilde{y_i}$ ，
$qquad w_m = mathop{argmin}limits_w sumlimits_{i=1}^{N} left[ ilde{y}_i - h_m(x_i,;,w) ight]^2$
(c) 使用line search確定步長 $ho_m$ ，以使 $L$ 最小，
$qquad ho_m = mathop{argmin}limits_{ ho} sumlimits_{i=1}^{N} L(y_i,f_{m-1}(x_i) + ho h_m(x_i,;,w_m))$
(d) $f_m(x) = f_{m-1}(x) + ho_m h_m(x,;,w_m)$
3. 輸出 $f_M(x)$

回歸提升樹

在Gradient Boosting框架中，最常用的基學習器是決策樹 (一般是CART)，二者結合就成了著名的梯度提升樹 (Gradient Boosting Decision Tree, GBDT)演算法。下面先敘述回歸問題，再敘述分類問題。注意GBDT不論是用於回歸還是分類，其基學習器 (即單顆決策樹) 都是回歸樹，即使是分類問題也是將最後的預測值映射為概率。

決策樹可以看作是一個分段函數，將特徵空間劃分為多個獨立區域，在每個區域預測一個常數，如下圖所示：

因此單棵決策樹可表示為 $h(x,;,left {R_j,b_j ight }_1^J) = sum limits_{j=1}^J b_j I(x in R_j)$ ，其中 $left {R_j ight }_1^J$ 為劃分出來的獨立區域 (即各個葉結點)， $left { b_j ight }_1^J$ 為各區域上的輸出值。為了求出這兩個參數，於是上面Gradient Boosting中的2.b步變為：

? $qquadqquadqquad left { R_{jm} ight}_1^J = mathop{argmin}limits_{left { R_{jm} ight}_1^J}sumlimits_{i=1}^N left [ ilde{y}_i - h_m(x_i,;,left {R_{jm},b_{jm} ight}_1^J) ight]^2$

即先求出樹劃分出的區域，而相應的 $b_{jm} = mathop{mean} limits_{x in R_{jm}} ilde{y}_{im}$ 為該區域的平均值。

接下來注意到2.c步中求出的 $ho_m$ 對於整棵樹中所有區域都是一樣的，這樣可能並不會使損失最小，因此Friedman提出可以對每個區域 $R_j$ 分別求一個最優的值 $gamma_{jm} = ho_m b_{jm}$ ，則2.c步變為：

$qquad qquad qquad qquad gamma_{jm} = mathop{argmin}limits_gamma sumlimits_{x_i in R_{jm}}L(y_i,f_{m-1}(x_i)+gamma)$

GBDT回歸演算法流程

1. 初始化： $f_0(x) = mathop{argmin}limits_gamma sumlimits_{i=1}^N L(y_i, gamma)$
2. for m=1 to M:
(a) 計算負梯度： $ilde{y}_i = -frac{partial L(y_i,f{m-1}(x_i))}{partial f_{m-1}(x_i)}, qquad i = 1,2 cdots N$

(b) $left { R_{jm} ight}_1^J = mathop{argmin}limits_{left { R_{jm} ight}_1^J}sumlimits_{i=1}^N left [ ilde{y}_i - h_m(x_i,;,left {R_{jm},b_{jm} ight}_1^J) ight]^2$
(c) $gamma_{jm} = mathop{argmin}limits_gamma sumlimits_{x_i in R_{jm}}L(y_i,f_{m-1}(x_i)+gamma)$
(d) $f_m(x) = f_{m-1}(x) + sumlimits_{j=1}^J gamma_{jm}I(x in R_{jm})$
3. 輸出 $f_M(x)$

回歸問題損失函數的選擇

常用的損失函數為平方損失 (squared loss)，絕對值損失 (absolute loss)，Huber損失 (huber loss)，下面給出各自的負梯度 (來自ESL 360頁)：

分類提升樹

將GBDT由回歸拓展到分類，關鍵是損失函數的選擇。如果選用了指數損失 (exponential loss)，則退化為AdaBoost演算法。另一種常用的分類損失函數為logistic loss，形式為 $L(y,f(x)) = log(1+e^{-2yf(x)})$ 。

要將其最小化，則對於 $f(x)?$ 求導並令其為0：

$frac{partial,log(1+e^{-2yf(x)})}{partial f(x)} = P(y=1|x) frac{-2e^{-2f(x)}}{1+e^{-2f(x)}} + P(y=-1|x) frac{2e^{2f(x)}}{1+e^{2f(x)}} = 0 quad Longrightarrow quad f(x) = frac12 logfrac{P(y=1|x)}{P(y=-1|x)}$

可以看到這與指數損失的目標函數一樣，都是對數幾率，見下圖 (來自MLAPP 566頁)：

區別在於指數損失容易受異常點的影響，不夠robust，且只能用於二分類問題。所以像scikit-learn中GradientBoostingClassifier的默認損失函數就是deviance。

與回歸提升樹的流程類似，求logistic loss的負梯度為：

$ilde{y} = -frac{partial , log(1+e^{-2yf(x)})}{partial f(x)} = -frac{-2y e^{-2yf(x)}}{1+e^{-2yf(x)}} = frac{2y}{1+e^{2yf(x)}}$

對於每個區域 $R_j$ 的最優值為：

$gamma_j = mathop{argmin}limits_gamma sumlimits_{x in R_j} L(y,f_{m-1}(x)+gamma) = mathop{argmin}limits_gamma sum limits_{x in R_j} log(1+e^{-2y(f_{m-1}(x)+gamma)})$

上式難以直接求出，因此常用近似值代替： $gamma_j = frac{sumlimits_{x in R_j} ilde{y}}{sumlimits_{x in R_j}| ilde{y}|(2-| ilde{y}|)}$

因為是分類問題，最後輸出 $f_M(x)$ 後要進行概率估計：設 $P = P(y=1|x)$ ，

$f(x) = frac12 logfrac{P(y=1|x)}{P(y=-1|x)} = frac12log frac{P}{1-P} quad color{Blue}{Longrightarrow}quad P = P(y=1|x) = frac{1}{1+e^{-2f(x)}} ;in left{0,1 ight}$

正則化 (Regularization)

1、Shrinkage

對每個基學習器乘以一個係數 $, u, (0 < u <1)$ ，使其對最終模型的貢獻減小，從而防止學的太快產生過擬合。 $u$ 又稱學習率，即scikit-learn中的learning rate。於是上文的加法模型就從：

? $f_m(x) = f_{m-1}(x) + ho_m h_m(x,;,w_m) ag{1.4}$

變為：

? $f_m(x) = f_{m-1}(x) + u ho_m h_m(x,;,w_m) ag{1.5}$

一般 $u$ 要和迭代次數M結合起來使用，較小的 $u$ 意味著需要較大的M。ESL中推薦的策略是先將 $u$ 設得很小 ( $u$ < 0.1)，再通過early stopping選擇M，不過現實中也常用cross-validation進行選擇。

2、Early stopping

將數據集劃分為訓練集和測試集，在訓練過程中不斷檢查在測試集上的表現，如果測試集上的準確率下降到一定閾值之下，則停止訓練，選用當前的迭代次數M，這同樣是防止過擬合的手段。

3、限制樹的複雜度

不加限制完全生成的樹同樣可能會學的太快導致過擬合，因而通常對其進行預剪枝。常用的方法是限制樹的深度(scikit-learn中的max_depth)等。

4、Subsampling

借用bootstrap的思想，每一輪訓練時只使用一部分樣本，不同點是這裡的採樣是無放回抽樣，這個方法被稱為Stochastic Gradient Boosting。對於單棵樹來說，只使用一部分樣本擬合會增加單棵樹的偏差和方差，然而subsampling會使樹與樹之間的相關性減少，從而降低模型的整體方差，很多時候會提高準確性。

subsampling的另一個好處是因為只使用一部分樣本進行訓練，所以能顯著降低計算開銷。

特徵重要性

單棵決策樹的可解釋性很強，GBDT則繼承了這個優點。

對於單棵樹T，用下式來衡量每個特徵 $X_l$ 的重要性：

$mathcal{I}_{l}^2(T) = sumlimits_{t=1}^{J-1}hat{i}_t^2I(v(t) = l) ag{1.6}$

其中 $J$ 表示葉結點 (leaf node) 數量， $J-1$ 表示內部結點 (internal node) 數量， $X_{v(t)}$ 是與內部結點t相關聯的分裂特徵。對於每個內部結點t，用特徵 $X_{v(t)}$ 來模擬劃分特徵空間，得到一個分裂後的平方誤差減少量，即 $hat{i}^2_t$ ，最後將所有內部節點上的誤差減少量加起來，就是特徵 $X_l$ 的重要性。總誤差減少地越多，該特徵就越重要。

對於M棵樹的集成而言，特徵重要性就是各棵樹相應值的平均：

$mathcal{I}_{l}^2 = frac1Msumlimits_{m=1}^Mmathcal{I}_l^2(T_m) ag{1.7}$

終末 —— 決策樹和GBDT

Gradient Boosting演算法理論上可以選擇多種不同的學習演算法作為基學習器，但實際使用地最多的無疑是決策樹，這並非偶然。決策樹有很多優良的特性，比如能靈活處理各種類型的數據，包括連續值和離散值；對缺失值不敏感；不需要做特徵標準化/歸一化；可解釋性好等等，但其致命缺點是不穩定，導致容易過擬合，因而很多時候準確率不如其他演算法。

決策樹是非參數模型，這並不意味著其沒有參數，而是在訓練之前參數數量是不確定的，因此完全生長的決策樹有著較大的自由度，能最大化地擬合訓練數據。然而單顆決策樹是不穩定的，樣本數相同的訓練集產生微小變動就能導致最終模型的較大差異，即模型的方差大，泛化性能不好。集成學習的另一代表Bagging是對付這個問題的一大利器 (詳見前一篇文章Bagging與方差) 。而Bagging的拓展演算法 —— 隨機森林，通過在樹內部結點的分裂過程中，隨機選取固定數量的特徵納入分裂的候選項，這樣就進一步降低了單模型之間的相關性，總體模型的方差也比Bagging更低。

另一方面，決策樹和Gradient Boosting結合誕生了GBDT，GBDT繼承了決策樹的諸多優點，同時也改進了其缺點。由於GBDT採用的樹都是複雜度低的樹，所以方差很小，通過梯度提升的方法集成多個決策樹，最終能夠很好的解決過擬合的問題。然而Boosting共有的缺點為訓練是按順序的，難以並行，這樣在大規模數據上可能導致速度過慢，所幸近年來XGBoost和LightGBM的出現都極大緩解了這個問題，後文詳述。

Reference:

1. Friedman, J.

Greedy Function Approximation: A Gradient Boosting Machine?

www-stat.stanford.edu

2. Friedman, J.

Stochastic Gradient Boosting?

statweb.stanford.edu

3. Friedman, J., Hastie, T. and Tibshirani, R. The Elements of Staistical Learning