透視 XGBoost(4) 神奇 optimization 在哪裡？

  Machine Learning23 minutes read (About 3515 words)0 visits

XGBoost 不只在算法上的改造，真正讓 XGBoost 大放異彩的是與工程優化的結合，這讓 XGBoost 在工業上可以應用於大規模數據的處理。

  • Approximate Greedy Algorithm
  • Weighted Quantile Sketch & Parallel Learning
  • Sparsity-Aware Split Finding
  • System Design

Approximate Greedy Algorithm

XGBoost 有兩種 split finding 策略，Exact Greedy and Approximate Greedy

data sample 量小的情況下， XGB tree 在建立分支時，會逐一掃過每個可能分裂點 (已對特徵值排序) 計算 similarity score 跟 gain， 即是 greedy algorithm。

greedy algorithm 會窮舉所有可能分裂點，因此能達到最準確的結果，因為他把所有可能的結果都看過一遍後選了一個最佳的。

但如果 data sample 不僅數量多 (row)，特徵維度也多 (columns)，採用 greedy algorithm，雖然準確卻也沒效率。

因此在數據量大的情況下，XGBoost 只會選出多個切分點，稱為 candidate splits ，這樣就能大幅降低計算量，此即 Approximate Greedy Algorithm，candidate splits 越多也意味更加耗時。

怎麼找 Candidate Splits ?

XGBoost proposes candidate splitting points according to percentiles of feature distribution

XGBoost 原則上是利用 data sample 的 feature 分佈的 quantiles 尋找 candidate splits，為什麼說是原則上呢，因為跟一般的 quantiles 有點不同，這留到 Weighted Quantile Sketch 章節再細說。

$\phi$ - Quantiles 計算

1
2
3
data:  [39. 21. 24. 61. 81. 11. 89. 56. 12. 51.]
sort:  [11. 12. 21. 24. 39. 51. 56. 61. 81. 89.]
rank:  [ 1.  2.  3.  4.  5.  6.  7.  8.  9. 10.]

以上總共 $N=10$ 筆 data 則

  • $\phi = 0.1$ ⇒ 0.1 quantile ⇒ $0.1*10 = 1$ ⇒ rank = 1 ⇒ 11，故 0.1 quantile = 11
  • $\phi = 0.5$ ⇒ 0.5 quantile ⇒ $0.5 * 10 = 5$ ⇒ rank = 5 ⇒ 39， 故 0.5 quantile = 39

可以發現 $\phi N$ 就是在找 rank 與其對應的 data 值，下面是一個 quantiles = [0.1, 0.3, 0.5, 0.6, 0.9] 的例子

1
2
3
quantiles 	 [0.1, 0.3, 0.5, 0.6, 0.9]
rank query	 [1.0, 3.0, 5.0, 6.0, 9.0]
data query 	 [11, 21, 39, 51, 81]

但 $\phi$ - Quantiles 在數據量大時難以對所有 data sample 排序，更遑論找確切的 candidate splits。

所以 XGBoost 採用了 $\epsilon \text{-approximate} \ \phi \text{-quantiles}$ 的思想來得到近似的 candidate splite ，容許 $\phi N$ 找出的 rank 有一定誤差 $\varepsilon N$。

$\epsilon \text{-approximate} \ \phi \text{-quantiles}$

$\epsilon \text{-approximate}$ 容許找出的 rank 落在一定範圍內：

  • $\varepsilon=0.1$ , 0.1 quantile ⇒ {11, 12}
  • $\varepsilon =0.1$ , 0.2 quantile ⇒ {11, 12, 21}
  • $\varepsilon =0.1$ , 0.3 quantile ⇒ {12, 21, 24}

換句話說，在區間內的值都可以作為 candidate splits，當 $\varepsilon =0.1$ quantiles = [0.1, 0.3, 0.5, 0.6, 0.9] 下，可以接受的 rank 與對應的 data 值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
quantile: 0.1
	 query rank: [1, 2]
	 query data: [11, 12]
quantile: 0.3
	 query rank: [2, 3, 4]
	 query data: [12, 21, 24]
quantile: 0.5
	 query rank: [4, 5, 6]
	 query data: [24, 39, 51]
quantile: 0.6
	 query rank: [5, 6, 7]
	 query data: [39, 51, 56]
quantile: 0.9
	 query rank: [8, 9, 10]
	 query data: [61, 81, 89]

ε-Approximate Quantile Summary

An ε-approximate quantile summary of a sequence of N elements is a data structure that can answer quantile queries about the sequence to within a precision of εN

因爲在區間內的值都可以作為 candidate splits，可以看出 quantiles 之間 query 出來的 rank 會有 overlapping，於是我們可以只選取特定幾個 quantiles，每個 quantile 只需要保存 $[\lfloor (\phi -\epsilon)\times N \rfloor , \lfloor (\phi + \epsilon) \times N\rfloor ]$ 中的代表的 rank 值 (最小值 and 最大值) 即可。

例如 $\varepsilon = 0.1$ ，quantiles = [0.1, 0.3, 0.5, 0.6, 0.9] ，分別選定 rank 區間內的最大值做為 summary:

1
2
3
quantiles:     [0.1, 0.3, 0.5, 0.6, 0.9]
rank summary:  [2,   4,   6,    7,  10]
query data:    [12, 24,  51,   56,  89]

在使用時也很簡單：

  • 找 0.1 quantile ⇒ rank =2 ⇒ 12 ⇒ 0.1 quantile = 12
  • 找 0.8 quantile ⇒ rank = $0.8 * 10 = 8$ ⇒ 與 8 最接近的 rank 為 7 ⇒ 56 ⇒ 0.8 quantile = 56

因此在 data samples 很大的情況下，一台運算機器無法將所有 data samples 存放進 memory 時，可以透過近似的方式找出 quantile 代表的值做為 candidate split。

Weighted Quantile Sketch & Parallel Learning

上面提到 XGBoost 在數據量大的時候，會採用 Approximate Greedy Algorithm 選出多個 candidate splits ，加快運算效率。

問題是分佈運算 (Parallel Learning) 時要怎麼 approximate quantiles？

Parallel Learning 下的 quantiles

簡單來說， data samples 會被拆成很多份在不同的運算單元計算某個特徵值的 gain and similarity score，但計算過程需要全局 data samples 的特徵 distribution 才有辦法算出 approximate quantiles ，因此各個運算單元會彙整 (merge) 出一張 approximate histogram，然後在這張 histogram 上計算 $\varepsilon$-approximate quantiles

什麼是 Weighted Quantile Sketch?

每筆 data sample 都帶有 weight，XGBoost 在 計算 approximate quantiles 時，盡量確保每個 quantiles 之間的 $\text{sum of data weight}$ 是差不多的的，而一般的 quantiles 是確保 quantiles 之間的 data 數量相同，此即 weighted quantile

下面這張 weighted quantile sketch 示意圖，展示每個 quantile 的 sum of data weight 皆等於 10，

示意圖，參考就好

為什麼需要 Weighted Quantile Sketch？

Put observation with low confidence into quantiles with fewer observation

以分類問題當例子，假設我們有六筆 data samples 如下

如果按照數量決定 quantiles，紅框內的兩個 data sample 不管怎樣都會被分在一起分不開。

再看 classification leaf node 的 output value 公式

兩者的 residual 一正一負，剛好會互相 cancel，這對於 predicted probability 的收斂有負面影響。

如果依照 weight 來切分，盡可能使每個 quantile 的 sum of weight 相等， 就有機會將兩者分開到不同 leaf node 下

data sample $x_i$ 的 weight 應該要反映出 $F(x_i)$ 的預測值的 confidence，在分類問題中，predicted probability 在 0.5 附近時，代表 classifier 其實不確定 data sample $x_i$ 屬於 positive or negative， 所以 XGBoost 利用 weight quantile 加大 $x_i$的 weight 讓 XGB tree $f$ 在分裂時更可以考慮到 $x_i$。

Weight Quantile 的實際作用為讓 low confidence 的 data sample 有更高的 weight，以便在計算 candidate split 時， low confidence 的 data sample 能跟 hight confidence 的 data sample 分開來 split

那每筆 data 的 weight 怎麼來的？

每筆 data 的 weight 其實就是通用 objective function 裡的 second derivative of the loss function $h_i$

參見 透視 XGBoost(3) 蘋果樹下的 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, F_{m-1}(x_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, F_{m-1}(x_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 的輸出值

Proof:

從 objective function 開始推導

  • regularization term $\Omega({f_m} ) =\tau T_m + \cfrac{1}{2}\lambda \sum^T_{j} \gamma_{m,j}^2$
  • $g_i = \cfrac{d}{d \ F_{m-1}} \ l(y_i, F_{m-1}(x_i))$，已知項
  • $h_i = \cfrac{d^2}{d \ F_{m-1}^2} l(y_i, F_{m-1}(x_i))$ ，已知項

仔細觀察，each data sample is weighted by $h_i$

  • 因為是求 weight ，係數項只是 scalar，所有 data sample 都乘一樣的值，相當於不用乘
  • 論文中這一段堆導應該是筆誤了，少了一個負號

故得證 each data sample $x_i$’s weight is actually its second derivative of the loss function $h_i$

Regression 下 data sample weight

已知 data sample $x_i$’s weight is actually its second derivative of the loss function，來求 regression 的 data sample weight 。

Regression 的 loss function 通常是 square error ， $l(y_i, \hat{y_i}) = \cfrac{1}{2}(y_i - \hat{y_i})^2$

我們已知 square error 的 $h_i = \cfrac{d}{d \ \hat{y}_i} -(y_i - \hat{y_i}) = 1$

所以事實上，loss function 為 square error 的 regression 所有 data sample weight 都是 1

Classification 下 data sample weight

classification 在 cross entropy/logit loss 作為 loss function 時，second derivative of the loss function $h_i$:

  • previous probability $p_i$ 表 data sample $x_i$ 在 $F_{m-1}(x_i)$ 輸出的 probability

classification 的 sample weight 是個開口向下的拋物線，兩側越往 $p_i=0.5$ 靠近 sample weight 越大。這很好理解，當 classifier 預測出的 probability 為 0.5 時，對這筆 data sample 是 low confidence 的，所以得加大其 weight 凸顯他。

Sparsity-Aware Split Finding

XGBoost 有兩種 missing values (NAs) 處理機制，一種是最簡單的，直接指定 leaf node 方向，EX: missing value 直接放到 leaf node 。

另一種是 learning from data，訓練時對於特徵中的 missing values (NAs)，在分裂計算 gain 時處理。

XGBoost 會分別考慮將 missing values 放到 left leaf node and right leaf node 的情形下計算 $\text{Gain}_{Left}, \text{Gain}_{Right}$

選擇能讓 gain 最大的那一側做為 missing values 所在 leaf node ，在 inference 階段遇到此特徵的 missing value 時將之歸入

EX：

假設我們有數筆 complete data 和兩筆含有 missing values 的 data

分別計算 $Gain_{Left}$ and $Gain_{Right}$ 後選擇 $\max(\text{Gain}_{Left}, \text{Gain}_{Right})$ 最大的那邊作為 missing values (NAs) 的歸屬 leaf node

System Design

XGBoost 一系列 System 上的 optimization 都是圍繞著 Memory Block 展開的

Column Block for Parallel Learning

block 是個連續的 memory 區塊，XGBoost 將 data sample 以 CSC (Compressed Sparse Column) format 存進 block 中，這麼做的好處是

  1. XGBoost 的 input 常常為大規模的 sparse data samples，使用 CSC 可以以 column 為 index 僅存放非 0 元素，有效減少 data sample size in memory 。
  2. CSC 因為是 columns index ，所以在 training tree 時，能快速定位到確切的 column
  3. 在建 XGB tree $f_m(x)$ 時須依據不同 column (X feature column) 的 feature value sorting data，才能 split data ，有了 block 之後，只需一開始對全局所有 columns 的 feature value sorting 一次，即可在之後建任何 XGB tree $f_m(x)$ 時使用

在 exact greedy algorithm，全局只有一個 block 計算 split; 在 approximate algorithms 中，因爲 data samples size 過大導致一運算單元容不下，所以 data samples 會根據 rows 切分成多個 blocks 分散到多個運算單元。

也因為根據 row 切分成不同 blocks，所以在 multi blocks 之上運算的 Weighted Quantile Sketch 也能 parallel for split finding

Time Complexity of Split Finding

若不事先對 block 內的 columns sorting，則整體 time complexity 為

  • $K$ it total tree in XGBoost
  • $d$ is the maximum depth of the tree
  • $| \text{x}|_0$ number of non-missing entries
  • $| \text{x}|_0 \log n$ related to sorting algorithm ，每一棵樹的每一層都要 sorting 一次的意思

若事先對 block columns sorting 則 Exact greedy algorithm time complexity 為

  • $O(| \text{x}|_0 \log n)$ 為事先 sorting
  • $O(Kd |\text{x}|_0 )$ 為建 K 個 tree

Approximate algorithm 的 time complexity 為

  • 單建一顆 tree 的 complexity 為 $| \text{x} |_0 \log q$，$q$ is the number of proposal split candidates in dataset
  • $B$ is the maximum number of rows in each block。因爲 parallel computing 所以 $O$ 只記入最耗時的那個 block

綜合以上，事先對 block 內的 columns sorting 加上 approximate algorithm 的 proposal candidate split，可以大幅降低 time complexity。

Cache-Aware Access

使用 memory block structure 對 columns sorting，對於 split finding 能有效降低 time complexity，但同時會造成 CPU cache $g_i$ $h_i$ 時的 cache miss rate 上升。

  • $g_i$ first derivative of loss function
  • $h_i$ second derivative of loss function

$g_i \ h_i$的計算跟當前 $x_i$ 的 loss 有關，所以當 split finding 由小到大取時，$g_i \ h_i$ 在 memory 中實際上是無序的存放的，得透過 pointer 對應之，CPU 要 cache 時，不容易 copy 需要的 $g_i \ h_i$ 到 cache，造成 cache missing

在 exact greedy algorithm，使用 cache-aware prefetching algorithm，使用另一個

thread 提前 access (prefetch) $g_i \ h_i$ 到 memory buffer 中讓 CPU cache 住。當 training thread 要提取時，直接就可以從 cache 拿，就算沒 cache 住，在 memory 中也是連續空間。

在 multi block 下的 approximate greedy algorithm 得對 each block size 合理設置，也就是 each block 下的 row number (data sample 數) 有關。

a block size 過大 cache 會裝不下，造成 cache missing ; a block size 過小會使 total block number 過多，使的 parallel 運算沒效率，是個 trade-off 的參數。

經過實驗，block size $2^{16}$ 是個相對合適的設置。

Blocks for out-of-core Computation

當 data samples 大到所有的計算單元的 memory 也無法容納時，XGBoost 會使用 out-of-core。我們知道 XGBoost 以 block 為單位切分 data sample，無法被 memory 裝下的 blocks 會被成塊且連續的存入 hard disk。

計算時也會開一條 thread 去 hard disk pre-fetch blocks into memory，這樣 XGBoost 就不會消耗過多時間再 I/O 上，可以一邊訓練一邊讀取 block。

Block Compression

存放在 hard disks 上的 out-of-core blocks 會被壓縮，減少讀取 I/O 的耗時。

壓縮方式大致上為保留 column index，對 row index 進行壓縮，只保留 beginning index of row in block，然後 利用一個 16bit 的 integer 儲存 row index 的 offset，類似 C 裡面的 pointer 跟 array 的關係。

Block Sharding

當有多個 hard disks 可供存放時，會將 data 劃分到多個 hard disks 上，好處是 pre-fetch thread 就可以同時讀取多個 hard disks 提高 I/O throughput 。

Reference

透視 XGBoost(4) 神奇 optimization 在哪裡？

https://seed9d.github.io/XGBoost-cool-optimization/

Author

seed9D

Posted on

2021-02-17

Updated on

2021-02-18

Licensed under

 

Comments

Recents

Follow
×