透視 XGBoost(1) 圖解 Regression
Introduction
XGboost 是 gradient boosting machine 的一種實作方式,xgboost 也是建一顆新樹 去擬合上一步模型輸出 F_{m-1}(x) 的 \text{residual}
不同的是,Xgboost 做了大量運算和擬合的優化,這讓他比起傳統 GBDT 更為高效率與有效
跟擬合目標有關的有
- Second Order Tayler Approximation
- Approximate Greedy Algorithm
- Weighted Quantile Sketch
- Sparsity-Aware Split Finding
跟工程優化有關的有
- Cache - Aware Access
- Block for Out-of-Core Computation
- Parallel Learning
以下章節主要分兩大塊
- XGBoost for Regression: 藉由 regression 介紹 XGBoost 如何 train 一棵 XGB tree,以圖文方式說明 XGB tree 如何擬合目標到剪枝。此章節不涉及公式證明,只有少量運算,適合快速理解 XGB 訓練流程
- XGBoost Regression Math Background:此章節深入討論在前一章節中用到的公式原理,並給予證明,適合深入理解 XGBoost 為何 work
篇幅關係 XGBoost 的優化手段放在 透視 XGBoost(4) 神奇 optimization 在哪裡?
XGBoost for Regression
從 gradient boosting 說起
XGBoost 跟 gradient boosting algorithm 框架一樣,皆是依序建立多棵樹 f_1(x), f_2(x), ….,f_M(x) 組成模型
- 其中第 m 步的 tree f_m(x) 是擬合模型 F_{m-1}(x) 預測值 \text{predicted } 與 真實值 \text{observed} 的 \text{residual}
- \nu 為 learning rate
算法差別主要體現在
- objective function 的設計
- Step 2 (B) (C) 建樹,GBDT 是建一顆傳統 regression tree f_m(x) 去擬合 \text{residual}; XGBoost 有自己衡量分裂 gain 的方式去擬合 residual 建立 XGB tree f_m(x)
可以說 XGBoost 用一種比較精準的方式去擬合 residual 建立子樹 f_m(x)
Data
之後用到的例子,數據如下:
假設有多筆 data sample,目標是用 drug dosage 預測 drug effectiveness
如何建一顆 XGB tree f_m(x) ?
Regression problem 上,XGB 在所有 data sample x 的每個特徵下的值裡尋找最佳分裂點,最終建成一顆 binary tree f_m(x)
建樹的過程涉及
- Fitting Target 擬合目標
- 分裂好壞的恆量,如 CART 用 gini gain 衡量分類樹
- Pruning 剪枝
- Output Value 決定每個 leaf node 的唯一輸出
f_m(x) 擬合的目標是什麼?
f_m(x) 擬合的目標是 \text{residual} ,利用 data sample x 的所有特徵建一顆特殊的 \text{regression tree} 去擬合 \text{residual}
以 m=1 時舉例
- XGBoost 的 predict 初始值 F_0(x),預設皆為 0.5
- ep_0_predict: XGBoost 的初始預測值 F_0(x),預設都是 0.5
- ep_1_residual: observed 與 F_0(x) 間的 residual 也就是 XGB tree f_1(x) 要擬合的目標
建 tree 時如何衡量分裂點好壞?
建分支時依序在特徵 \text{Drug Dosage} 的 data sample value \text{[10, 20, 25, 35]} 中尋找最優分裂點切分 residual \text{[-10.5, 6.5, 7.5 -7.5]}
決定分裂點的優劣取決於 Gain
分裂 node,會產生 left child node 與 right child node,分別計算三者的 \text{similarity score}
- \lambda is a regularization parameter,這邊先假設 0
注意!! 排序的是 \text{Drug Dosage},分裂點依序在 \text{Drug Dosage} 中找,但被分開到左右子樹的是 \text{residual}
在 data sample 的特徵 \textit{drug dosage} 中找出 gain 最大的做為分裂點
以 Dosage < 15 當作分裂點的 gain = 110.25 + 14.08 - 4 = 120.33
以 Dosage < 22.5 當作分裂點的 gain = 8 + 0 -4 = 4
顯然以 Dosage < 15 當作分裂點,好於以 Dosage < 22.5 當作分裂點。
當然,還得把剩下的可能分裂點看完,才能決定最終分裂點。
找個第一個分裂點,還得找下個子樹的分裂點,如此周而復始,最終得到樹的結構
如何 Pruning ?
XGBoost 對 new tree f_m(x) 的 pruning 建立在 gain 上,透過設定一個 gain threshold \tau 決定是否剪枝
- 若 \tau = 130,則 分裂點 "Dosage < 30" 的 gain = 140.17 > 130 = \tau,不會被剪枝,因爲子節點沒被剪枝,父節點 \textit{Dosage < 15} 也保留
- 若 \tau =150,則 分裂點 "Dosage < 30" 的 gain = 140.17 < 150 = \tau ,會被剪枝,最終只保留 父節點 \textit{Dosage < 15},因爲需要一個根節點
P.S. 在 XGBoost 論文裡,gain threshold 的符號是 \gamma,但因為 notaion 衝突,這邊換成 \tau,對應到工程 hyper parameter min_split_loss
如何決定 leaf node 的 output value?
決定每個 leaf node 的 output value 公式跟式(2) similarity score 很像,差別在分子部份的 \text{sum of residuals} 是否取平方
- \lambda is a regularization parameter,這邊先假設 0
計算每個 leaf node output value 後
Regularization term \lambda 的作用
prevent overfitting in training data
regularization paramater \lambda 的作用是防止 overfitting,\lambda 可以減少 similarity 對 resiudal 值的敏感程度
若 \lambda > 0 值越大則分母越大, similarity score 會越小,代表分子 \text{sum of residual } 的作用越小
similarity score 越小
- similarity score 越小,在分裂階段,分裂點的 Gain = Left_{Similarity} + Right_{similarity} - Root_{similarity} 就越小
- \lambda 對不同 node 的影響是非線性的
- similarity score 越小 , gain 也越小,在剪枝階段,其被剪枝的可能性越大。
如何整合多棵樹 f_1(x), f_2(x),…,f_m(x) 的輸出
F_M(x) 的計算與 GBDT 一樣
假設只建立一顆 XGB tree f_1(x), \text{learning rate = 0.8}
則每個 data sample 新的 prediction 為
- ep_0_predict 表 F_0(x) 對每個 data sample 的預測值, XGBoost 初始預設值是 0.5
- ep_1_leaf_output 表 data sample 在 XGB tree f_1(x) 下所屬 leaf node 的輸出值,其值擬合 ep_1_residual
- ep_1_predict 表 F_1(x) 表 data sample 在 m=1 的預測值
XGBoost Regression Math Background
XGBoost 的通用 Objective Function
- g_i 為 first derivative of loss function related to data sample x_i : g_i = \cfrac{d}{d \ F_{m-1}} \ l(y_i, \hat{y_i})
- h_i 為 second derivative of loss function related to data sample x_i: h_i = \cfrac{d^2}{d \ F_{m-1}^2} l(y_i, \hat{y_i})
- T_m is the number of leaf in tree f_m
- \tau 表對 T_m 的 factor
- \gamma_{j,m} 表 m 步 XGB tree f_m 第 j 個 leaf node 的輸出值
- R_{m, j}表 m 步 XGB tree f_m 下 第 j 個 leaf node 得 data sample 集合
optimal output \gamma_{j,m}^* of leaf node j
詳細推導參閱 透視 XGBoost(3) 蘋果樹下的 objective function
Regression Leaf output 公式怎麼來的?
式(3) each leaf node 的 output 公式怎麼得出的?
從式 (5),可以直接求 regression 的 optimal leaf node output
regression 的 loss 通常是 square error ,先將 l(y_i, \hat{y_i}) = \cfrac{1}{2}(y_i - \hat{y_i})^2 代入 h_i, g_i
代入 式(5) 得到 \gamma_{j,m}^*
- i \in R_{j,m} 表 leaf node j 下的 data sample x_i
- \lambda is a regularization parameter
故得證 XGB tree f_m(x) for regression each leaf node j 的輸出為
Regression 的 Similarity Score 怎麼來的?
式 (2) similarity score 怎麼得出的
XGBoost 分裂的目的是要使 式(4) objective function 越小越好,怎麼評判分裂前後收益?式(1) 評價了分裂後 left/right leaf node 可以得到的"score"與分裂前 root node 的 "score" 差值計算分裂前後增益 gain
所以 similarity score 肯定得跟 objective function 有關,才能正確的恆量 gain,但 similarity score 是 "score “ 越大越好, objective function 是要 minimize 的,得越小越好,兩者如何扯上關係?
觀察一下 objective function
因為我們要衡量單個 node 得 gain,式 (4)中,跟某個 node 直接相關的 part 為 summation of all leaf node 裡面的 equation
- R_{m, j}表 m 步 XGB tree f_m 下 第 j 個 leaf node 得 data sample 集合
將 式(5) 代入 式(6) 可以得出 式(6)的極小值
因爲要的是 "score" ,所以讓 loss 對 x 軸做對稱,拿掉係數項 \frac{1}{2}
g_i 為 first derivative of loss function related to data sample x_i : g_i = \cfrac{d}{d \ F_{m-1}} \ l(y_i, \hat{y_i})
h_i 為 second derivative of loss function related to data sample x_i: h_i = \cfrac{d^2}{d \ F_{m-1}^2} l(y_i, \hat{y_i})
因爲要的是 "score" ,所以讓 loss 對 x 軸做對稱,拿掉係數項 \frac{1}{2}
式 (8) 中的 g_i, h_i 分別表 loss function l(y,\hat{y}) 的 first derivative and second derivative
當 loss function 為 square error 時
- g_i = -(y_i - \hat{y}_i) = \text{negative residual}
- h_i = \cfrac{d}{d \ \hat{y}_i} -(y_i - \hat{y_i}) = 1
代入式(8) 得到 square error 下的 similarity score,得證:
Reference
- Chen, T., & Guestrin, C. (2016). XGBoost: A scalable tree boosting system. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 13-17-Augu, 785–794. https://doi.org/10.1145/2939672.2939785
- What makes “XGBoost” so Extreme? https://medium.com/analytics-vidhya/what-makes-xgboost-so-extreme-e1544a4433bb
- XGBoost-from-scratch-python
- Boosting algorithm: XGBoost https://towardsdatascience.com/boosting-algorithm-xgboost-4d9ec0207d
- https://www.hrwhisper.me/machine-learning-xgboost/
透視 XGBoost(1) 圖解 Regression
Be the first person to leave a comment!