本文主要分享自己總結(jié)的關(guān)于 xgboost 的筆記。

基礎(chǔ)知識(shí)

基學(xué)習(xí)器 CART
$$\begin{gathered} Regression:L(y_i,{\hat{y}}_i)=(y_i?f(x_i){)}^2 \\ Classification:Gini(D)=\sum _{k=1}^K{p}_k(1?p_k)=1?\sum _{k=1}^K{p}_k^2 \end{gathered}$$
回歸單樣本的損失函數(shù)，和分類時(shí)在數(shù)據(jù)集D上的基尼指數(shù)。f 表示樹，f(x) 則是 x 對(duì)應(yīng)的葉子節(jié)點(diǎn)的值。

對(duì)于分類問題，在 CART 分割時(shí)，我們按照 Gini 指數(shù)最小來確定分割點(diǎn)的位置。即：
$$\begin{gathered} cutpoint(A)=argmi{n}_{v\in A_V}\sum _{i=1}^2\frac{|D_i|}{|D|}Gini(D_i) \\ bestA,best\_v=argmi{n}_{A\in features}[argmi{n}_{v\in A_V}\sum _{i=1}^2\frac{|D_i|}{|D|}Gini(D_i)] \end{gathered}$$

XGBoost 的目標(biāo)函數(shù)：

$$\begin{gathered} Obj=\sum _{i=1}^{n}L(y_i,{\hat{y}}_i)+\sum _{k=1}^K\Omega (f_k) \\ whereL(y_i,{\hat{y}}_i)=(y_i?f(x_i){)}^2 \\ \Omega (f)=\gamma T+\frac{1}{2}\lambda ||\omega |{|}^2=\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T||{\omega }_j|{|}^2 \end{gathered}$$
假設(shè)有 n 個(gè)樣本，K 棵樹。目標(biāo)函數(shù)由兩部分構(gòu)成，第一部分用來衡量預(yù)測(cè)分?jǐn)?shù)和真實(shí)分?jǐn)?shù)的差距，另一部分則是正則化項(xiàng)。正則化項(xiàng)同樣包含兩部分，T 表示葉子結(jié)點(diǎn)的個(gè)數(shù)，w 表示葉子節(jié)點(diǎn)的分?jǐn)?shù)。$\gamma$ 可以控制葉子結(jié)點(diǎn)的個(gè)數(shù)，λ 可以控制葉子節(jié)點(diǎn)的分?jǐn)?shù)不會(huì)過大，防止過擬合。

自問自答

常用的參數(shù)都有哪些？

一開始，當(dāng)然是要先設(shè)置 booster，一版直接默認(rèn)用 gbtree 就可以了，另外還有兩個(gè)常用的全局設(shè)置項(xiàng)是 nthread、verbosity。

接下來，幾個(gè)常用的能影響到模型擬合能力的參數(shù)是：

• num_boost_round(n_estimators)
• max_depth(樹的深度)
• eta(learning_rate)

然后，有兩個(gè)正則化、類似于用來控制預(yù)剪枝的參數(shù)是：

• gamma(分裂時(shí)目標(biāo)函數(shù)增益的閾值)
• min_child_weight(分裂時(shí)孩子權(quán)重之和的閾值)

另外幾個(gè)用于控制正則項(xiàng)的參數(shù)是：

• lambda(這是葉子節(jié)點(diǎn) L2 正則項(xiàng)的系數(shù))
• alpha(這是葉子節(jié)點(diǎn) L1 正則項(xiàng)的系數(shù))
• subsample(訓(xùn)練數(shù)據(jù)"被隨機(jī)采樣用來訓(xùn)練"的比例)
• colsample_bytree(訓(xùn)練數(shù)據(jù)的所有特征"被隨機(jī)選擇用來訓(xùn)練一棵樹"的比例)

對(duì)于數(shù)據(jù)不平衡問題，可能還用到的重要參數(shù)是：

• scale_pos_weight(一般設(shè)置成正例和負(fù)例樣本數(shù)量的比值)
• max_delta_step

如何通過優(yōu)化目標(biāo)函數(shù)值來計(jì)算葉子節(jié)點(diǎn)權(quán)重？

$$\begin{gathered} Obj=\sum _{i=1}^{n}L(y_i,{\hat{y}}_i)+\sum _{k=1}^K\Omega (f_k) \\ whereL(y_i,{\hat{y}}_i)=(y_i?f(x_i){)}^2 \\ \Omega (f)=\gamma T+\frac{1}{2}\lambda ||\omega |{|}^2=\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2 \end{gathered}$$
那么，假設(shè)樹的結(jié)構(gòu)已經(jīng)確定，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)于一部分樣本，即可以將決策樹表示為一個(gè)映射 $q:R^d\to \{1,2,...,T\}$ ，每個(gè) d 維的樣本 $x_i$ 可以映射到?jīng)Q策樹 T 個(gè)葉子節(jié)點(diǎn)中的一個(gè)，要如何計(jì)算對(duì)應(yīng)的葉子節(jié)點(diǎn)權(quán)重和相應(yīng)的目標(biāo)函數(shù)值呢？

一種簡(jiǎn)單粗暴的方法是，對(duì)于分類問題，將葉子節(jié)點(diǎn)的值設(shè)置為該節(jié)點(diǎn)樣本集中樣本數(shù)量最多類別；對(duì)于回歸問題，則設(shè)置為標(biāo)簽值的平均。但是，這就完全忽略目標(biāo)函數(shù)的存在了，我們的目標(biāo)是要最小化目標(biāo)函數(shù)。

以下對(duì)目標(biāo)函數(shù)進(jìn)行一些化簡(jiǎn)：

假設(shè)現(xiàn)在學(xué)習(xí)到了第 t 棵樹，記為 $f_t(x)$ ，那么 ${\hat{y}}^t={\hat{y}}^{t?1}+f_t(x)$ 。我們的目標(biāo)是使得 ${\hat{y}}^t$ 盡量等于 $y$ ，即 $ \hat y^{t-1} + f_t(x)$ 盡量趨近于 $y$ ，也就是讓 $f_t(x)$ 趨近于 $y?{\hat{y}}^{t?1}$ ，換言之， $y?{\hat{y}}^{t?1}$ 就是當(dāng)前這棵樹的擬合目標(biāo)，或者說樣本的標(biāo)簽值（說起來，這和 GBDT 其實(shí)是一樣的，只是這里目標(biāo)函數(shù)不同，導(dǎo)致最后擬合出來的葉子節(jié)點(diǎn)的權(quán)重會(huì)有所不同）。代入目標(biāo)函數(shù)中：
$$Ob{j}^{(t)}=\sum _{i=1}^{n}L(y_i,{\hat{y}}_i^{t?1}+f_t(x_i))+\Omega (f_t)$$
我們知道有泰勒公式二階展開：
$$f(x+\Delta x)=f(x)+f^{\prime }(x)?\Delta x+\frac{1}{2}{f}^{\prime \prime }(x)?(\Delta x{)}^2$$
將 $y_i^{t?1}$ 看作上式中的 x，$f_t(x)$ 看作上式中的 $\Delta x$ ，$L(y_i,{\hat{y}}_i^{t?1})$ 看作上式的 $f(x)$ 。那么目標(biāo)函數(shù)可以改寫成：
$$Ob{j}^{(t)}\approx \sum _{i=1}^n[L(y_i,{\hat{y}}_i^{t?1})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t)$$
這里的 $g_i，h_i$ 分別是 $L(y_i,{\hat{y}}_i^{t?1})$ 關(guān)于 ${\hat{y}}_i^{t?1}$ 的一階導(dǎo)和二階導(dǎo)。若以 平方誤差 作為損失函數(shù)，即 $L(y_i,{\hat{y}}_i^{t?1})=(y_i?{\hat{y}}_i^{t?1}{)}^2$ ，那么有 $g_i=2({\hat{y}}_i^{t?1}?y_i)$ , $h_i=2$ 。

由于 $L(y_i,{\hat{y}}_i^{t?1})$ 是常數(shù)項(xiàng)不影響我們把目標(biāo)函數(shù)最小化，所以上式可以簡(jiǎn)寫成：
$$Ob{j}^{(t)}\approx \sum _{i=1}^n[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t)$$
假設(shè)樹的結(jié)構(gòu)已經(jīng)確定，對(duì)目標(biāo)函數(shù)進(jìn)一步化簡(jiǎn)：

設(shè)每個(gè)葉子節(jié)點(diǎn)的權(quán)重為 $w_j,j\in 1,2,...,T$ ，那么可以將決策樹表示成 $w_{q(x)}$ ，即每個(gè)樣本會(huì)映射到第 q(x) 個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的權(quán)值。假設(shè) $I_j=\{i|q(x_i)=j\}$ 為第 j 個(gè)葉子節(jié)點(diǎn)的樣本集合，則目標(biāo)函數(shù)可進(jìn)一步化為：
$$\begin{gathered} Ob{j}^{(t)}\approx \sum _{i=1}^n[g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t) \\ =\sum _{i=1}^n[g_i{w}_{q(x_i)}+\frac{1}{2}{h}_i{w}_{q(x_i)}^2]+\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2 \\ =\sum _{j=1}^T[\sum _{i\in I_j}{g}_i{w}_j+\frac{1}{2}\sum _{i\in I_j}{h}_i{w}_j^2+\frac{1}{2}\lambda w_j^2]+\gamma T \\ =\sum _{j=1}^T[(\sum _{i\in I_j}{g}_i)w_j+\frac{1}{2}(\sum _{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T \end{gathered}$$
我們之前樣本的集合，現(xiàn)在都改寫成葉子結(jié)點(diǎn)的集合，由于一個(gè)葉子結(jié)點(diǎn)有多個(gè)樣本存在，因此才有了 ${\sum }_{i\in I_j}{g}_i$ 和 ${\sum }_{i\in I_j}{h}_i$ 這兩項(xiàng)，把這兩項(xiàng)簡(jiǎn)寫為 $G_j,H_j$，于是上式變成：
$$Ob{j}^{(t)}=\sum _{j=1}^T[G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2]+\gamma T$$
假設(shè)樹的結(jié)構(gòu)已經(jīng)確定，通過最小化目標(biāo)函數(shù)，求解葉子節(jié)點(diǎn)權(quán)重：

在當(dāng)前假設(shè)下，上式中只有 $w$ 是變量，這是一個(gè)凸函數(shù)，為了使其取得最小值，只需要令目標(biāo)函數(shù)一階導(dǎo)為 0，便可求得：
$${\hat{w}}_j=?\frac{G_j}{H_j+\lambda }$$
通過求得的葉子節(jié)點(diǎn)權(quán)重，計(jì)算目標(biāo)函數(shù)值：
$$Ob{j}^{(t)}=?\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$$

學(xué)習(xí)的過程是怎么進(jìn)行的？

先從總體上進(jìn)行描述：

學(xué)習(xí)的過程就是每次擬合一棵樹，直到滿足停止條件

擬合之前，先計(jì)算出每個(gè)樣本的一階導(dǎo)（前 t-1 棵樹預(yù)測(cè)值和真實(shí)標(biāo)簽值的絕對(duì)差值）和二階導(dǎo)（固定值：2）

用貪心策略生成一棵樹

為每個(gè)葉子節(jié)點(diǎn)計(jì)算權(quán)值

把新增的決策樹加入，這里有個(gè)學(xué)習(xí)率參數(shù)，實(shí)際上，在這里學(xué)習(xí)率的作用更多的是控制過擬合。

生成一棵樹的具體過程是這樣的：

從樹的深度為 0 開始，遍歷每個(gè)特征的每個(gè)分割點(diǎn)，尋找到目標(biāo)函數(shù)增益最大的分割點(diǎn)

針對(duì)每個(gè)特征，把屬于該節(jié)點(diǎn)的訓(xùn)練樣本按特征值升序排列，通過線性掃描的方式來決定該特征的最佳分裂點(diǎn)，并記錄下該特征的最大收益(采用最佳分裂點(diǎn)的目標(biāo)函數(shù)增益)

選擇收益最大的特征作為分裂特征，該特征的最佳分裂點(diǎn)作為分裂位置

如果收益大于 gamma，且滿足 min_child_weight，那么由該節(jié)點(diǎn)生長(zhǎng)出兩個(gè)新的節(jié)點(diǎn)，每個(gè)新節(jié)點(diǎn)關(guān)聯(lián)對(duì)應(yīng)的樣本集

不斷重復(fù)以上兩個(gè)步驟，直到達(dá)到樹的最大深度or沒有滿足條件的分割點(diǎn)

這其實(shí)是一種貪心策略，因?yàn)槲覀冊(cè)诜指畹拿恳徊蕉急M量使收益最大，即每一步都得到局部最優(yōu)解，但無法保證一整棵樹的收益最大。

本質(zhì)是梯度提升樹，和 GBDT 有什么區(qū)別？

我們說 GBDT，一般指的是基于 殘差(y-f(x)) 的梯度提升樹，實(shí)際上，如果以誤差的平方作為損失函數(shù)，那么殘差其實(shí)就是損失函數(shù)關(guān)于 f(x) 的負(fù)梯度，所以擬合殘差就相當(dāng)于擬合了負(fù)梯度（這其實(shí)和神經(jīng)網(wǎng)絡(luò)中通過梯度下降來訓(xùn)練參數(shù)類似），這就是為什么稱之為梯度提升樹。

xgboost 的在 GBDT 的基礎(chǔ)上主要改進(jìn)了兩點(diǎn)，其實(shí)從 目標(biāo)函數(shù) 中都可以看出來。

對(duì)于 GBDT，相當(dāng)于對(duì)目標(biāo)函數(shù)中的 損失函數(shù) 這一項(xiàng)進(jìn)行了 一階泰勒展開，而 XGBoost 用到了二階展開，更為精確一點(diǎn)；

xgboost 將葉子節(jié)點(diǎn)的權(quán)重的 L2 范數(shù)作為正則項(xiàng)，并直接添加到了目標(biāo)函數(shù)中。

都說 xgboost 效果好，為什么好？

從偏差-方差的角度來理解：

由于決策樹本身的靈活性，加上通過 Boosting 的方法，可以通過不斷地迭代學(xué)習(xí)降低偏差；

除了直接在目標(biāo)函數(shù)添加了正則項(xiàng)，還有很多其他措施來減小模型的方差：

比如 subsample，在每一輪只使用一部分隨機(jī)采樣的樣本，通過這種隨機(jī)性來降低前后學(xué)習(xí)得到的基學(xué)習(xí)器的依賴(或者說相關(guān)性)，其實(shí)就是在 Boosting 過程中摻入 Bagging 的思想，用以降低模型的方差。

colsample_bytree 也是類似，只不過這里隨機(jī)采樣的不是樣本，而是隨機(jī)選擇一部分特征進(jìn)行訓(xùn)練。

訓(xùn)練速度快，為什么快？

特征間并行：在進(jìn)行節(jié)點(diǎn)的分裂時(shí)，需要尋找每個(gè)特征的最佳分裂點(diǎn)及其分裂增益，最終選增益最大的那個(gè)特征去做分裂，那么不同特征的增益計(jì)算就可以并行計(jì)算。

決策樹的學(xué)習(xí)最耗時(shí)的一個(gè)步驟之一就是對(duì)特征的值進(jìn)行排序（因?yàn)橐_定最佳分割點(diǎn)），xgboost 的做法是在訓(xùn)練之前，預(yù)先對(duì)數(shù)據(jù)進(jìn)行排序，然后保存為block結(jié)構(gòu)，后面的迭代中重復(fù)地使用這個(gè)結(jié)構(gòu)，大大減小計(jì)算量。這個(gè)block結(jié)構(gòu)也使得并行成為了可能，在進(jìn)行節(jié)點(diǎn)的分裂時(shí)，需要計(jì)算每個(gè)特征的增益，最終選增益最大的那個(gè)特征去做分裂，那么各個(gè)特征的增益計(jì)算就可以開多線程進(jìn)行。

近似直方圖算法。樹節(jié)點(diǎn)在進(jìn)行分裂時(shí)，我們需要計(jì)算每個(gè)特征的每個(gè)分割點(diǎn)對(duì)應(yīng)的增益，即用貪心法枚舉所有可能的分割點(diǎn)。當(dāng)數(shù)據(jù)無法一次載入內(nèi)存或者在分布式情況下，貪心算法效率就會(huì)變得很低，所以xgboost還提出了一種可并行的近似直方圖算法，用于高效地生成候選的分割點(diǎn)。

另外，對(duì)于訓(xùn)練數(shù)據(jù)特別稀疏的情況，稀疏感知的分位點(diǎn)尋找算法也能加速訓(xùn)練。

---

論文閱讀筆記

2. 提升樹 TREE BOOSTING IN A NUTSHELL

2.1 正則項(xiàng) Regularized Learning Objective

本節(jié)提出了目標(biāo)函數(shù)。其中的正則化項(xiàng)可以防止過擬合。

2.2 泰勒二階展開 Gradient Tree Boosting

對(duì)目標(biāo)函數(shù)二階泰勒展開。通過最小化目標(biāo)函數(shù)，可以得到葉子節(jié)點(diǎn)的權(quán)值、以及目標(biāo)函數(shù)值。

分裂前后目標(biāo)函數(shù)值的增益也很容易計(jì)算。

2.3 學(xué)習(xí)率和特征采樣（Shrinkage and Column Subsampling）

Shrinkage:

類似于隨機(jī)梯度下降優(yōu)化算法中的學(xué)習(xí)率，Shrinkage 具體做法是對(duì)每一輪生成的樹的葉子節(jié)點(diǎn)權(quán)重乘上一個(gè)系數(shù) $\eta$ (即希臘字母eta)，這就是為什么 XGBoost 包中學(xué)習(xí)率參數(shù)名稱為 eta。

Column Subsampling:

和隨機(jī)森林里使用的特征采樣類似，這是一個(gè) bagging 思想的應(yīng)用，而且也是第一次被使用在 Tree Boosting 里。效果甚至比傳統(tǒng)的 row sub-sampling（樣本采樣）好。而且，特征采樣還能加速訓(xùn)練。

3. 分裂點(diǎn)尋找算法 SPLIT FINDING ALGORITHMS

3.1 精確貪婪算法（Exact Greedy Algorithm）

每一輪boost，生成一棵樹。由于枚舉所有可能的樹結(jié)構(gòu)是NP-hard問題，不可能完成，所以實(shí)際做法是，在每次進(jìn)行節(jié)點(diǎn)分裂的時(shí)候，以最大化分裂增益（loss reduction）的方式來進(jìn)行節(jié)點(diǎn)的分裂。這是一種貪婪的策略。

事先對(duì)訓(xùn)練樣本按照特征值排序，可以加速訓(xùn)練。

每一層，對(duì)于某一個(gè)特征，基于特征列 Block 結(jié)構(gòu)，并行進(jìn)行所有葉子節(jié)點(diǎn)的分裂點(diǎn)尋找。并行的過程，我現(xiàn)在的理解是這樣的：

對(duì)于某個(gè)線程，在順序遍歷某排好序的特征列時(shí)，對(duì)于每一個(gè)特征值，我們都能知道它對(duì)應(yīng)的哪個(gè)樣本(記為第i個(gè))、哪個(gè)葉子節(jié)點(diǎn)(記為第 j 個(gè))，也因此就能取得該樣本的梯度 $g_i,h_i$，并根據(jù) j 計(jì)算出 $G_{jL},H_{jL}$ 和 $G_{jR},H_{jR}$。遍歷一趟下來，所有葉子節(jié)點(diǎn)在該特征上的最大增益就都出來了。

我之前卡在了這里：就是遍歷時(shí)，對(duì)于每一個(gè)特征值，都要計(jì)算一遍所有葉子節(jié)點(diǎn)的分裂增益，開銷應(yīng)該很大。現(xiàn)在才搞懂，其實(shí)只需要計(jì)算該特征所在的葉子節(jié)點(diǎn)的分裂增益就可以了。這里說的“對(duì)于每一個(gè)特征值”，指的是每個(gè)分裂點(diǎn)前面緊挨著的那個(gè)特征值。

你想，對(duì)于某個(gè) leaf node ，你只記錄了該節(jié)點(diǎn)中包含了哪些樣本(索引)，你怎么取得這個(gè)節(jié)點(diǎn)中這些樣本的該特征的排序值呢？反正我想了好久就是想不通有啥高效的辦法。在這里卡了好久。

所以，其實(shí)相當(dāng)于沒有遍歷葉子節(jié)點(diǎn)這一說，只是，在遍歷特征的所有分裂點(diǎn)的過程中，隱式地完成了對(duì)所有葉子節(jié)點(diǎn)的遍歷。這也是為什么 xgb 總是滿二叉樹。

參考：XGBoost原理及并行實(shí)現(xiàn) 中的 “method 3” 部分。

3.2 近似算法（Approximate Algorithm）

當(dāng)數(shù)據(jù)無法一起加載進(jìn)內(nèi)存，或者在分布式環(huán)境下，精確貪婪算法效率很低。即便正常情況下，有些連續(xù)值特征的取值個(gè)數(shù)可能非常多，這樣計(jì)算起來開銷很大，而且還容易過擬合。所以可以使用分桶的方式，把特征的取值分割成確定數(shù)量的部分。即，我們對(duì)每個(gè)特征都 propose 對(duì)應(yīng)的候選分裂點(diǎn)們（由加權(quán)分位點(diǎn)算法生成，每次生成一系列候選分裂點(diǎn)稱作一次proposal），可用于每棵樹(global)，或者每次分裂(local)。分桶后，需要匯總每個(gè)桶內(nèi)的 $g_i$ 和 $h_i$ （難道這就是論文中的“construct approximate histograms of gradient statistics”？）。

全局（global）：在樹構(gòu)建之前，確定所有特征的候選分裂點(diǎn)，然后在樹的所有層次 split finding 時(shí)都使用相同的proposals（即候選分裂點(diǎn)）。這種方法需要較少的proposal steps，但需要更多的候選分裂點(diǎn)（才能達(dá)到和local版本相同的效果），因?yàn)樵诿看畏至押?#xff0c;候選點(diǎn)們并沒有被提純。

局部（local）：re-propose after each split. 這樣的好處是，每次分裂后，樣本減少，純度更高，相當(dāng)于對(duì)候選分裂點(diǎn)進(jìn)行了提純(refine)，所以需要的候選分裂點(diǎn)可以較少。潛在地，也更適合于構(gòu)建深層的樹。

XGBoost支持在單機(jī)環(huán)境下高效地使用精確貪婪算法，或者在任何環(huán)境下使用局部或全局的近似算法。

3.3 加權(quán)分位點(diǎn)算法（weighted quantile sketch）

以第 k 個(gè)特征為例，對(duì)于每一個(gè)樣本，由前面的 t-1 棵樹可以得到其二階導(dǎo) h，以此作為該樣本的權(quán)重。n 個(gè)樣本的集合記為： $D_k=\{(x_{1k},h_1),(x_{2k},h_2),...,(x_{nk},h_n)\}$

對(duì)樣本按照特征值升序排列，那么對(duì)于一個(gè)值 z，可以得到樣本值小于 z 的樣本權(quán)重之和 占 所有樣本權(quán)重之和 的比例：
$$r_k(z)=\frac{1}{{\sum }_{(x,h)\in D_k}h}?\sum _{(x,h)\in D_k,x<z}h$$
我們的目標(biāo)是從該特征的這些取值中找到候選分裂點(diǎn) $\{s_{k1},s_{k2},...,s_{kl}\}$ ，滿足：

這里 $?$ 是一個(gè)近似系數(shù)。直覺上可知，大約有 $1/?$ 個(gè)候選分裂點(diǎn)。

若使用均方誤差作為損失函數(shù)，那么實(shí)際上所有樣本的 h 值都為 2。對(duì)于所有樣本權(quán)重相等的情況，一個(gè)已知的分位點(diǎn)算法 quantile sketch 可以解決該問題。

XGBoost支持對(duì)樣本設(shè)置權(quán)重，這樣一來樣本的二階導(dǎo) h 也應(yīng)當(dāng)乘以相應(yīng)的權(quán)重，這就導(dǎo)致每個(gè)樣本的權(quán)重可以各不相同。本文提出的加權(quán)分位點(diǎn)算法可以解決該問題。

3.4 稀疏感知的分裂點(diǎn)尋找（Sparsity-aware Split Finding）

數(shù)據(jù)稀疏可能由幾個(gè)原因造成：

• 數(shù)據(jù)值缺失
• 統(tǒng)計(jì)值經(jīng)常為 0
• 人為的特征工程（比如 one-hot）

當(dāng)樣本的某個(gè)數(shù)據(jù)值缺失時(shí)，該樣本會(huì)被分到默認(rèn)的分支（獲得最大增益的方向）。

具體的算法思路如下：

對(duì)于每個(gè)特征：假設(shè)將缺失值分到右分支的情況下，遍歷所有特征值不缺失的特征值，尋找最佳分裂點(diǎn)再假設(shè)將缺失值分到左分支的情況下，遍歷所有特征值不缺失的特征值，尋找最佳分裂點(diǎn)得到增益最大的分裂點(diǎn)，同時(shí)，該最大增益是在哪種假設(shè)情況下得到的，哪種假設(shè)就作為缺失值的默認(rèn)分支

需要注意的是，該算法將 non-presence 視作缺失值處理，并按照學(xué)得的方向進(jìn)行分支。

我所理解的 non-presence 是類似于 one-hot 之后的 0 值，不知道對(duì)不對(duì)？

作者在一個(gè)由于 one-hot 導(dǎo)致數(shù)據(jù)極其稀疏的數(shù)據(jù)集 Allstate-10K 上進(jìn)行測(cè)試，該稀疏感知算法能比原始算法提升 50 倍的速度。

所以，我的理解是，稀疏感知算法既有效處理了缺失值，又加速了訓(xùn)練。

4. 系統(tǒng)設(shè)計(jì) SYSTEM DESIGN

4.1 Column Block for Parallel Learning

訓(xùn)練樹的時(shí)候，最消耗時(shí)間的部分是，對(duì)數(shù)據(jù)進(jìn)行排序。本文提出一種方法，將數(shù)據(jù)保存在內(nèi)存單元里，保存的結(jié)構(gòu)被稱為 block。

每一個(gè) block 存儲(chǔ)一列特征，在 block 中，特征值已經(jīng)排好序，并且記錄了每個(gè)特征值對(duì)應(yīng)的樣本索引(這樣可以節(jié)省大量的存儲(chǔ)空間)。block 的數(shù)據(jù)格式是 壓縮的列（CSC格式）。Block 中特征之所以記錄了指向樣本的索引，是為了能根據(jù)特征的值來取梯度。

輸入數(shù)據(jù)的排序只在訓(xùn)練開始前計(jì)算一次，之后每次迭代都可以復(fù)用。

4.2 Cache-aware Access

使用Block結(jié)構(gòu)的一個(gè)缺點(diǎn)是取梯度的時(shí)候，是通過索引來獲取的，而這些梯度的獲取順序是按照特征的大小順序的。這將導(dǎo)致非連續(xù)的內(nèi)存訪問，可能使得CPU cache緩存命中率低，從而影響算法效率。

因此，對(duì)于exact greedy算法中, 使用緩存預(yù)取（cache-aware prefetching）。具體來說，對(duì)每個(gè)線程分配一個(gè)連續(xù)的buffer，讀取梯度信息并存入Buffer中（這樣就實(shí)現(xiàn)了非連續(xù)到連續(xù)的轉(zhuǎn)化），然后再統(tǒng)計(jì)梯度信息。

對(duì)于大規(guī)模數(shù)據(jù)，效果十分明顯，大約快了一倍。

在 approximate 算法中，對(duì)Block的大小進(jìn)行了合理的設(shè)置。定義Block的大小為Block中最多的樣本數(shù)。設(shè)置合適的大小是很重要的，設(shè)置過大則容易導(dǎo)致命中率低，過小則容易導(dǎo)致并行化效率不高。經(jīng)過實(shí)驗(yàn)，發(fā)現(xiàn)2^16比較好。

4.3 Blocks for Out-of-core Computation

當(dāng)數(shù)據(jù)量太大不能全部放入主內(nèi)存的時(shí)候，為了使得out-of-core計(jì)算成為可能，將數(shù)據(jù)劃分為多個(gè)Block并存放在磁盤上。計(jì)算的時(shí)候，使用獨(dú)立的線程預(yù)先將Block放入主內(nèi)存，因此可以在計(jì)算的同時(shí)讀取磁盤。

但是由于磁盤IO速度太慢，通常跟不上計(jì)算的速度。因此，需要提升磁盤IO的吞吐量。Xgboost采用了2個(gè)策略：

• Block壓縮（Block Compression）：將Block按列壓縮（LZ4壓縮算法？），讀取的時(shí)候用另外的線程解壓。對(duì)于行索引，只保存第一個(gè)索引值，然后只保存該數(shù)據(jù)與第一個(gè)索引值之差(offset)，一共用16個(gè)bits來保存
  offset，因此，一個(gè)block一般有2的16次方個(gè)樣本。

• Block拆分（Block Sharding）：將數(shù)據(jù)劃分到不同磁盤上，為每個(gè)磁盤分配一個(gè)預(yù)取（pre-fetcher）線程，并將數(shù)據(jù)提取到內(nèi)存緩沖區(qū)中。然后，訓(xùn)練線程交替地從每個(gè)緩沖區(qū)讀取數(shù)據(jù)。這有助于在多個(gè)磁盤可用時(shí)增加磁盤讀取的吞吐量。

總結(jié)

以上是生活随笔為你收集整理的【Datawhale|天池】心跳信号分类预测 (4) - 模型 之 XGBoost的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。