Loading [MathJax]/jax/output/PreviewHTML/jax.js

透視 XGBoost(1) 圖解 Regression

Introduction

XGBoost

XGBoost

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

以下章節主要分兩大塊

  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 說起

GBDT Framework

GBDT Framework

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)

建樹的過程涉及

  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}

m=1 時舉例

  • XGBoost 的 predict 初始值 F_0(x),預設皆為 0.5

  • ep_0_predict: XGBoost 的初始預測值 F_0(x),預設都是 0.5
  • ep_1_residual: observedF_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 越小

  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 一樣

假設只建立一顆 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_mj 個 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

透視 XGBoost(1) 圖解 Regression

https://seed9d.github.io/xgboost-for-regression/

Author

seed9D

Posted on

2021-02-16

Updated on

2021-02-18

Licensed under


Comments

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!