透視 XGBoost(1) 圖解 Regression

Introduction

XGboost 是 gradient boosting machine 的一種實作方式，xgboost 也是建一顆新樹 $f_m(x)$ 去擬合上一步模型輸出 $F_{m-1}(x)$ 的 $\text{residual}$

$$\begin{aligned} F_m(x) & = F_{m-1}(x) + f_m(x) \\ F_{m-1}(x) &= F_0(x) + \sum_{i=0}^{m-1}f_{m-1}(x) \end{aligned}$$

不同的是，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

以下章節主要分兩大塊

1. XGBoost for Regression： 藉由 regression 介紹 XGBoost 如何 train 一棵 XGB tree，以圖文方式說明 XGB tree 如何擬合目標到剪枝。此章節不涉及公式證明，只有少量運算，適合快速理解 XGB 訓練流程
2. 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)$ 組成模型

$$F_m(x) = F_0(x) + \nu\sum^m_{i=1} f_i(x) = F_{m-1} + \nu f_{m-1}(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)$

建樹的過程涉及

1. Fitting Target 擬合目標
2. 分裂好壞的恆量，如 CART 用 gini gain 衡量分類樹
3. Pruning 剪枝
4. Output Value 決定每個 leaf node 的唯一輸出

$f_m(x)$ 擬合的目標是什麼？

$f_m(x)$ 擬合的目標是 $\text{residual}$ ，利用 data sample x 的所有特徵建一顆特殊的 $\text{regression tree}$ 去擬合 $\text{residual}$

$$\text{residual = observed - predicted}$$

以 $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$

$$Gain = Left_{\text{similarity}} + Right_{\text{similarity}} - Root_{\text{similarity}} \tag{1}$$

分裂 node，會產生 left child node 與 right child node，分別計算三者的 $\text{similarity score}$

$$\text{Similarity Score} = \cfrac{(\sum \text{residual})^2}{\text{Number of Residuals } + \lambda} \tag{2}$$

• $\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}$ 是否取平方

$$\text{output value} = \cfrac{\sum(\text{residuals})}{\text{Number of Residuals} + \lambda}\tag{3}$$

• $\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$ 值的敏感程度

$$\text{Similarity Score} = \cfrac{(\sum \text{residual})^2}{\text{Number of Residuals } + \lambda}$$

若 $\lambda > 0$ 值越大則分母越大， similarity score 會越小，代表分子 $\text{sum of residual }$ 的作用越小

similarity score 越小

1. similarity score 越小，在分裂階段，分裂點的 $Gain = Left_{Similarity} + Right_{similarity} - Root_{similarity}$ 就越小
   • $\lambda$ 對不同 node 的影響是非線性的
2. similarity score 越小 ， gain 也越小，在剪枝階段，其被剪枝的可能性越大。

如何整合多棵樹 $f_1(x), f_2(x),…,f_m(x)$ 的輸出

$F_M(x)$ 的計算與 GBDT 一樣

$$F_M(x) = F_0(x) + \nu\sum^M_{i=1} f_i(x) = F_{M-1} + \nu f_m(x)$$

假設只建立一顆 XGB tree $f_1(x)$， $\text{learning rate = 0.8}$

則每個 data sample 新的 prediction 為

$$F_1(x) = F_0(x) + 0.8* f_1(x)$$

• 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

$$\begin{aligned} \mathcal{\tilde{L}}^{(m)} &= \sum^{T_m}_{j=1}[(\sum_{i \in R_{m,j}}g_i) \gamma_{j,m} + \cfrac{1}{2}(\sum_{i \in R_{j,m} }h_i + \lambda)\gamma_{j,m}^2] + \tau T_m \end{aligned} \tag{4}$$

• $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$

$$\gamma_{j,m}^*=- \cfrac{\sum_{i\in R_{j,m}} g_i}{\sum_{i \in R_{j,m}}h_i + \lambda} \tag{5}$$

詳細推導參閱 透視 XGBoost(3) 蘋果樹下的 objective function

Regression Leaf output 公式怎麼來的？

式(3) each leaf node 的 output 公式怎麼得出的？

$$\text{output value} = \cfrac{\sum(\text{residuals})}{\text{Number of Residuals} + \lambda}\tag{3}$$

從式 (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$

$$\begin{aligned} g_i &= -(y_i - \hat{y}_i) = \text{negative residual} \\ h_i &= \cfrac{d}{d \ \hat{y}_i} -(y_i - \hat{y_i}) = 1 \end{aligned}$$

代入 式(5) 得到 $\gamma_{j,m}^*$

$$\gamma_{j,m} = \cfrac{\sum_{i \in R_{j,m}}(y_i - F_{m-1}(x_i))}{(\sum_{i \in R_{j,m}}1) + \lambda} = \cfrac{\text{sum of residual}}{\text{number of residual } + \lambda }$$

• $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$ 的輸出為

$$\gamma_{j,m} = \cfrac{\text{sum of residual}}{\text{number of residual } + \lambda }$$

Regression 的 Similarity Score 怎麼來的？

式 (2) similarity score 怎麼得出的

$$\text{Similarity Score} = \cfrac{(\sum \text{residual})^2}{\text{Number of Residuals } + \lambda} \tag{2}$$

XGBoost 分裂的目的是要使 式(4) objective function 越小越好，怎麼評判分裂前後收益？式(1) 評價了分裂後 left/right leaf node 可以得到的＂score＂與分裂前 root node 的 ＂score＂ 差值計算分裂前後增益 gain

$$Gain = Left_{\text{similarity}} + Right_{\text{similarity}} - Root_{\text{similarity}} \tag{1}$$

所以 similarity score 肯定得跟 objective function 有關，才能正確的恆量 gain，但 similarity score 是 ＂score “ 越大越好， objective function 是要 minimize 的，得越小越好，兩者如何扯上關係？

觀察一下 objective function

$$\begin{aligned} \mathcal{\tilde{L}}^{(m)} &= \sum^{T_m}_{j=1}[(\sum_{i \in R_{m,j}}g_i) \gamma_{j,m} + \cfrac{1}{2}(\sum_{i \in R_{j,m} }h_i + \lambda)\gamma_{j,m}^2] + \tau T_m \end{aligned} \tag{4}$$

因為我們要衡量單個 node 得 gain，式 (4)中，跟某個 node 直接相關的 part 為 summation of all leaf node 裡面的 equation

$$[(\sum_{i \in R_{m,j}}g_i) \gamma_{j,m} + \cfrac{1}{2}(\sum_{i \in R_{j,m} }h_i + \lambda)\gamma_{j,m}^2] \tag{6}$$

• $R_{m, j}$表 m 步 XGB tree $f_m$ 下 第 $j$ 個 leaf node 得 data sample 集合

將 式(5) 代入 式(6) 可以得出 式(6)的極小值

$$\begin{aligned} (\sum_{i \in R_{m,j}}g_i) \gamma_{j,m} + \cfrac{1}{2}(\sum_{i \in R_{j,m} }h_i + \lambda)\gamma_{j,m}^2 &= -（\sum_{i \in R_{j,m}}g_i)\cfrac{\sum_{i\in R_{j,m}} g_i}{\sum_{i \in R_{j,m}}h_i + \lambda} + \cfrac{1}{2}(\sum_{i \in R_{j,m} }h_i + \lambda)(\cfrac{\sum_{i\in R_{j,m}} g_i}{\sum_{i \in R_{j,m}}h_i + \lambda})^2 \\ & = -\cfrac{(\sum g_i)^2}{\sum h_i + \lambda} + \cfrac{1}{2} \cfrac{(\sum g_i)^2}{\sum h_i + \lambda} \\ & = -\cfrac{1}{2}\cfrac{(\sum g_i)^2}{\sum h_i + \lambda} \end{aligned} \tag{7}$$

因爲要的是 ＂score＂ ，所以讓 loss 對 x 軸做對稱，拿掉係數項 $\frac{1}{2}$

$$\text{Similarity Score} = \cfrac{(\sum g_i)^2}{\sum h_i + \lambda} \tag{8}$$

• $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，得證：

$$\text{Similarity Score} = \cfrac{(\sum g_i)^2}{\sum h_i + \lambda} = \cfrac{(\sum \text{residual})^2}{\text{Number of Residuals } + \lambda}$$

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 Part 1 (of 4): Regression

• XGBoost Part 3 (of 4): Mathematical Details

• my post

  • 一步步透視 GBDT Regression Tree
  • 一步步透視 GBDT Classifier