Gradient Boosting Decision Tree 梯度提升決策樹

Gradient Boosting Decision Tree 梯度提升決策樹 #

Gradient boosting decision tree，是用 gradient 做 boosting 的 decision tree。

令我們的資料 \( D = \{\bold{x_n},y_n\}_{n=1}^N, where\;\bold{x_n}\in\R^p,y_n \in\R \) ，為一個有 N 筆資料，p 維特徵，一維實數 label 的迴歸問題資料集。

我們訓練了一棵決策樹 f，對資料 \( \bold{x_n} \) 的預測值為 \( f(\bold{x_n}) \) ，Loss 總合為 \( \Sigma_{n=1}^N L(y_n, f(\bold{x_n})) \) 。這時候我們訓練第二棵決策樹 \( f_2 \) ，希望 \( \Sigma_{n=1}^N L(y_n, \Sigma_{i=1}^2 \eta_i f_i(\bold{x_n})) \) 可以變小，其中 \( \eta_i \) 為一個 scalar，對不同的 f 做加權。以此類推，我們可以訓練很多棵決策樹，讓我們的 Loss 足夠小，假設為 T 棵，則我們要解的式子為：

\[L(y, \bold{f}) = \Sigma_{n=1}^N L(y_n, \Sigma_{i=1}^T\eta_i f_i(\bold{x_n}))\newline \bold{f} = f_1, f_2, ..., f_T\]

Gradient Boosting #

我們在 Gradient descent 的時候做的事情是，找到最好的 weight w 使 Loss 最小，每一步 w 往 \( -\frac{dL}{dw} \) 的地方走一小段距離 ( \( \eta_i \) )，希望最後可以走到足夠接近極小值的地方，最後的 weight 就是 \( \Sigma_{i=0}^T \eta_i w_i \) 。同理，我們這邊每一步往 \( -\frac{\partial L}{\partial f} \) 的方向走，每步走 \( \eta_i \) 這麼遠。走了 T 步以後， \( \Sigma_{i=1}^T \eta_i f_i(\bold{x}) \) 可以讓我們的 Loss 足夠小，於是我們稱這個方法為 gradient boosting。如果 f 為決策樹，就稱為 gradient boosting decision tree。

因此，當我們在訓練第 m 棵決策樹，我們不去動已經訓練好的前 m - 1 棵樹，而且我們的 Loss function 必須是對於 f 可微分的。Steepest descent 會選擇 \( \eta_m f_i(\bold{x}) \) ，其中 \( \eta_m \) 為純量 (scalar)， \( f_m(\bold{x}) \) 為 \( L(y, \bold{f}) \) 在 m - 1 時的負的 gradient。

考慮 Loss 為 mean square error 的情況：

\[L(y, \bold{f}) = \Sigma_{n=1}^N \frac{1}{2}(y_n - \bold{f}(\bold{x_n}))^2 \newline -\frac{\partial L(y, \bold{f})}{\partial \bold{f}} = \Sigma_{n=1}^N (y_n - \bold{f}(\bold{x_n}))\]

負的 gradient 正好就是答案跟目前預測值的差 (residual)。

LightGBM 的優化 #

LightGBM 為微軟於 2017 年發表於 NeurIPS 的論文：LightGBM: A Highly Efficient Gradient Boosting Decision Tree，提出一個高效率且成效好的 GBDT 方法，並且有實作 Python package。在演算法上提出 Gradient-based One-Side Sampling 以及 Exclusive Feature Bundle 做為資料太多或是特徵太多的優化。

Gradient-based One-Side Sampling #

給定 a 為 large gradient data 的抽樣比例，b 為 small gradient data 的抽樣比例。在訓練第 m 棵決策樹時，算出每一筆資料的 gradient，並且對 gradient 排序，前 \( a \times length(data) \) 筆資料為 topSet。剩下的資料隨機抽出 \( b \times length(data) \) 筆為 randSet。使用 topSet + randSet 做為下一棵樹的訓練資料，其中 randSet 給 \(\frac{1-a}{b} \) 的 instance weight 還原原本的權重比例。

對於模型來說，小 gradient 的資料已經訓練得很好了，也對權重影響較小，一個直覺的做法就是將他們丟掉。但是這樣會改變訓練資料的分佈，所以這邊丟掉一部份並且將權重還原，在資料分佈接近的情況下減少資料量來加速訓練。

Exclusive Feature Bundle #

在特徵很稀疏(sparse)的情況下，一筆 instance 在兩個稀疏特徵都不為 0 的機率很低，所以我們可以「bundle」這兩個 feature 「exclusive」，因為 #bundle « #feature，所以計算量大幅減少了。我們想要知道：

  1. 哪些 feature 可以綁在一起
  2. 要怎麼做出 bundle

找出最好的 feature bundle 其實就是圖的著色問題。給定圖 G(V, E)，要在每個點上著色但相鄰的點不能同色。特徵就是點，兩個特徵如果有任何一筆資料同時不為零就是相鄰的特徵，相鄰的特徵不能是同一個 bundle (顏色)。這是一個 NP-hard 的問題，所以必須使用貪心的近似演算法。因為有時候可能幾十萬或是百萬筆資料中，只有一兩筆資料在兩個特徵不為零，我們會給一個最大的 conflict \( \gamma \) ，只要衝突的資料筆數小於 \( \gamma \) ，我們還是可以把它們放在同一個 bundle，可以大幅減少計算量。

根據上面的討論，就可以設計做出 feature bundle 的演算法。將特徵照非零值的個數排序，逐一檢查，如果此特徵跟任何一個現有的 bundle conflict 小於等於 \( \gamma \) ，就將跟特徵加入 bundle，否則就自成一個 bundle。

LightGBM 套件 #

官方有提供 Python 套件可以直接使用。

安裝：

pip install lightgbm

使用：

from lightgbm import LGBMClassifier, LGBMRegressor
# classification tree
X = [[0, 0], [2, 2]]
y = [1, 0]
clf = LGBMClassifier()
clf.fit(X, y)
print(clf.predict([[1, 1]]))

# regression tree
X = [[0, 0], [2, 2]]
y = [0.5, 2.5]
clf = LGBMRegressor()
clf.fit(X, y)
print(clf.predict([[1, 1]]))

其中建議至少搜尋一下 max_depth 參數(樹的最大深度)，如果處理 imbalance data 的話建議調整一下 scale_pos_weight 或是 is_unbalance。

其他參數調整可以參考官網建議。

LightGBM Custom Loss Function #

有時候我們想要使用自定義的 Loss，我們只要自己算好對 y_pred 的一次微分 (gradient) 跟二次微分 (hessian) 便可以使用。

以 Scikit Learn 內建的 california_housing 資料集為例，他的 label 是加州區域的房價。如果我們寧願房價低估也不要高估，所以給高估的部分兩倍的 MSE penalty 如下：

\[L(y, p) = \begin{cases} 2(y - p)^2 &\text{if } p >= y \\ (y - p)^2 &\text{else} \end{cases}\]
import numpy as np

from lightgbm import LGBMRegressor
from sklearn.datasets import fetch_california_housing

def my_mse(y_true, y_pred, alpha):
    gt = np.where(y_true <= y_pred)[0]
    lt = np.where(y_true > y_pred)[0]
    my_mse = (np.power(y_pred[gt] - y_true[gt], 2).sum() * alpha + np.power(y_pred[lt] - y_true[lt], 2).sum()) / y_true.shape[0]
    return my_mse

def objective_my_mse(y_true, y_pred):
    # 高估部分的 index
    gt = np.where(y_true <= y_pred)[0]
    # 低估部分的 index
    lt = np.where(y_true > y_pred)[0]
    grad = np.zeros_like(y_true)
    hess = np.zeros_like(y_true)
    # 2 * (y_pred - y_true)^2 對 y_pred 微分
    grad[gt] = (y_pred[gt] - y_true[gt]) * 4
    # (y_pred - y_true)^2 對 y_pred 微分
    grad[lt] = (y_pred[lt] - y_true[lt]) * 2
    # 2 * (y_pred - y_true)^2 對 y_pred 二次微分
    hess[gt] = 4
    # (y_pred - y_true)^2 對 y_pred 二次微分
    hess[lt] = 2
    return grad, hess

data = fetch_california_housing()
feature = data['data']
label = data['target']

clf = LGBMRegressor(objective='mse')
clf.fit(feature, label)
predict = clf.predict(feature)
print('my_mse(1) = ', my_mse(label, predict), 'my_mse(2) = ', my_mse(label, predict, 2))
# my_mse(1) =  0.16185924439865307 my_mse(2) =  0.22466035755190344

clf = LGBMRegressor(objective=obj_my_mse)
clf.fit(feature, label)
predict = clf.predict(feature)
print('my_mse(1) = ', my_mse(label, predict), 'my_mse(2) = ', my_mse(label, predict, 2))
# my_mse(1) =  0.17455908215254148 my_mse(2) =  0.20977227751451513

my_mse(1) 為原本的 MSE，my_mse(2) 為高估部分給予兩倍 panelty 的 MSE。使用跟 metric 一致的 objective 可以取得比較好的訓練分數。

參考資料：

XGBoost paper

LightGBM paper

comments powered by Disqus