XGBoost原理詳解及系統(tǒng)優(yōu)化

XGBoost鸭廷，全稱(chēng)“Extreme Gradient Boosting”枣抱，和GBDT一樣屬于Boosting類(lèi)型的模型，也是一種加法模型辆床。

1 XGBoost原理

1.1 監(jiān)督學(xué)習(xí)概念回顧

1.1.1模型和參數(shù)

監(jiān)督學(xué)習(xí)中模型表示從樣本輸入 $x_{i}$ 到預(yù)測(cè)輸出 $y_{i}$ 的映射關(guān)系佳晶，參數(shù)是我們要學(xué)習(xí)的部分，比如線(xiàn)性回歸模型 $\hat{y}_{i}=\sum_{j}^{ }\theta _{j}*x_{ij}$ 佛吓， $\theta$ 是我們要學(xué)習(xí)的參數(shù)宵晚。

1.1.2 目標(biāo)函數(shù)：損失+正則

模型訓(xùn)練的過(guò)程就是尋找最優(yōu)參數(shù)，使得模型能夠很好的擬合樣本和標(biāo)簽维雇。為了評(píng)價(jià)模型擬合樣本和標(biāo)簽的好快程度淤刃，我們需要一個(gè)評(píng)估指標(biāo)，即模型的目標(biāo)函數(shù)吱型。

通常目標(biāo)函數(shù)由兩部分組成：損失部分和正則部分： $obj(\theta ) = L(\theta ) + \Omega (\theta )$ 逸贾，其中L是損失函數(shù)，衡量模型的預(yù)測(cè)能力津滞， $\Omega$ 是正則項(xiàng)铝侵，控制模型的復(fù)雜度，防止模型過(guò)擬合触徐。

1.2 決策樹(shù)加法模型

1.2.1 加法模型的訓(xùn)練Additive Training

XGBoost是基于CART決策樹(shù)的加法模型咪鲜，形式可以表示為：

$\hat{y}_{i}=\sum_{k=1}^{K}f_{k}(x_{i}), f_{k}\epsilon F$

其中K表示樹(shù)的棵數(shù)，f是函數(shù)空間F中的函數(shù)撞鹉，F(xiàn)代表所有可能的CART樹(shù)疟丙。目標(biāo)函數(shù)表示為

$obj(\theta )=\sum_{i}^{n}l(y_{i}, \hat{y}_{i}) + \sum_{k=1}^{K}\Omega(f_{k})$

有了目標(biāo)函數(shù)之后颖侄，XGBoost的訓(xùn)練過(guò)程就是尋找最優(yōu)參數(shù)最小化目標(biāo)函數(shù)。XGBoost的參數(shù)是什么呢享郊？XGBoost和GBDT一樣览祖，是函數(shù)空間的加法模型，其參數(shù)為函數(shù)炊琉，每個(gè)函數(shù)表示一棵CART樹(shù)展蒂，包含樹(shù)的結(jié)構(gòu)和樹(shù)中葉子節(jié)點(diǎn)的分?jǐn)?shù)。

XGBoost的加法模型表示為：

$\hat{y}_{i}^{(0)} = 0$

$\hat{y}_{i}^{(1)} = f_{1}(x_{i}) = \hat{y}_{i}^{(0)} + f_{1}(x_{i})$

$\hat{y}_{i}^{(2)} = f_{1}(x_{i}) + f_{2}(x_{i}) = \hat{y}_{i}^{(1)} + f_{2}(x_{i})$

...

$\hat{y}_{i}^{(t)} = \sum_{k=1}^{t}f_{k}(x_{i}) = \hat{y}_{i}^{(t-1)} + f_{t}(x_{i})$

在每一步中苔咪，我們想要學(xué)習(xí)的函數(shù)或CART樹(shù)必須能夠使得目標(biāo)函數(shù)最優(yōu)：

$obj^{(t)} = \sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t)}) + \sum_{i=1}^{t}\Omega(f_{i})$

??? $=\sum_{i=1}^{n}l(y_{i}, \hat{y}_{i}^{(t-1)} + f_{t}(x_{i})) + \Omega(f_{t}) + constant$

使用展開(kāi)到二階的泰勒展開(kāi)式 $f(x) = \frac{f(x_{0})}{0!} + \frac{f'(x_{0})(x-x_{0})}{1!} + \frac{f''(x_{0})(x-x_{0})^2}{2!} + ...+\frac{f^{(n)}(x_{0})(x-x_{0})^{n}}{n!} + R_{n}(x)$

將目標(biāo)函數(shù)展開(kāi)到二階項(xiàng)：

$obj^{(t)} = \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}) + constant$

其中：

$g_{i} = \partial_{\hat{y}_{i}^{(t-1)}}l(y_{i}, \hat{y}_{i}^{(t-1)})$

$h_{i} = \partial_{\hat{y}_{i}^{(t-1)}}^2l(y_{i}, \hat{y}_{i}^{(t-1)})$

移除所有的常數(shù)項(xiàng)之后锰悼，在第t步的目標(biāo)函數(shù)就變?yōu)椋?/p>

$obj^{(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})$

這就是我們每學(xué)習(xí)一棵新決策樹(shù)時(shí)的優(yōu)化目標(biāo)，該優(yōu)化目標(biāo)的值只依賴(lài)于 $g_{i}$ 和 $h_{i}$ 团赏，這也就是為什么XGBoost支持自定義損失函數(shù)的原因：只要損失函數(shù)是一階和二階可導(dǎo)的松捉，我們就可以一階導(dǎo)數(shù)和二階導(dǎo)數(shù)優(yōu)化目標(biāo)函數(shù)。

1.2.2 模型復(fù)雜度

目標(biāo)函數(shù)中除了損失之外馆里，還有一項(xiàng)：正則項(xiàng)，也就是說(shuō)我們還需要定義決策樹(shù)的復(fù)雜度可柿。

首先鸠踪，定義一棵決策樹(shù)為：

$f_{t}(x) = w_{q(x)}, w\epsilon R^T, q: R^d \rightarrow \left \{1,2,...,T\right \}$

其中 $w$ 是表示葉子節(jié)點(diǎn)的分?jǐn)?shù)的向量， $q$ 表示把每個(gè)樣本映射到對(duì)應(yīng)葉子節(jié)點(diǎn)的函數(shù)复斥， $T$ 是葉子節(jié)點(diǎn)的數(shù)量营密。

基于以上的決策樹(shù)定義，XGBoost中決策樹(shù)復(fù)雜度定義為：

$\Omega(f) = \gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^2$

當(dāng)然目锭，決策樹(shù)復(fù)雜度的定義可以有多種评汰，但是這里使用的定義方式在實(shí)踐中比較有效。很多關(guān)于樹(shù)模型的算法包中經(jīng)常忽略正則項(xiàng)痢虹，是因?yàn)閭鹘y(tǒng)樹(shù)的學(xué)習(xí)重點(diǎn)關(guān)注提高節(jié)點(diǎn)純度被去。XGBoost通過(guò)在目標(biāo)函數(shù)中增加決策樹(shù)復(fù)雜度，we can get a better idea of what we are learning and obtain models that perform well in the wild.

1.2.3 模型訓(xùn)練

在定義了決策樹(shù)復(fù)雜度之后奖唯，我們?cè)诘趖步的目標(biāo)函數(shù)可以進(jìn)一步做如下變換：

$obj^{(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 \epsilon I_{j}}^{}g_{i})w_{j} + \frac{1}{2}(\sum_{i \epsilon I_{j}}^{}h_{i} + \lambda )w_{j}^2] + \gamma T$

其中 $I_{j} = \left \{i|q(x_{i}) = j \right \}$ 是分配到葉子節(jié)點(diǎn)j的樣本集合惨缆。由于同屬一個(gè)葉子節(jié)點(diǎn)的樣本具有相同的分?jǐn)?shù)，所以可以進(jìn)行以上的變換丰捷。

如果定義：

$G_{j} = \sum_{i\epsilon I_{j}}^{}g_{i}$

$H_{j} = \sum_{i\epsilon I_{j}}^{}h_{i}$

那么上面的目標(biāo)函數(shù)可以簡(jiǎn)化為：

$obj^{(t)}=\sum_{j=1}^{T}[G_{j}w_{j} + \frac{1}{2}(H_{j} + \lambda )w_{j}^2] + \gamma T$

上面的目標(biāo)函數(shù)中 $G_{j}w_{j} + \frac{1}{2}(H_{j} + \lambda )w_{j}^2$ 可以看做是關(guān)于 $w_{j}$ 的二次方程坯墨，那么使得目標(biāo)函數(shù)取得最優(yōu)值時(shí)的 $w_{j}$ 以及目標(biāo)函數(shù)的最優(yōu)值分別為：

$w_{j}^* = -\frac{G_{j}}{H_{j}+\lambda }$

$obj^* = -\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}^2}{H_{j}+\lambda } + \gamma T$

對(duì)于一棵決策樹(shù)， $w_{j}^2$ 定義了葉子節(jié)點(diǎn)的分?jǐn)?shù)病往， $obj^*$ 相當(dāng)于樹(shù)的純度捣染，并且包含了樹(shù)復(fù)雜度的度量。

有了樹(shù)的度量標(biāo)準(zhǔn)之后停巷，理想情況下可以遍歷所有可能的樹(shù)結(jié)構(gòu)耍攘，選擇最優(yōu)的結(jié)構(gòu)榕栏。但是在實(shí)際中是行不通的，所以我們選擇每次優(yōu)化樹(shù)的一層結(jié)構(gòu)少漆，即當(dāng)我們需要把樹(shù)的一個(gè)葉子節(jié)點(diǎn)分裂成兩個(gè)的時(shí)候臼膏，分裂的Gain為：

$Gain = \frac{1}{2}[\frac{G_{L}^2}{H_{L} + \lambda } + \frac{G_{R}^2}{H_{R} + \lambda } - \frac{(G_{L} + G_{R})^2}{H_{L} + H_{R} + \lambda }] - \gamma$

Gain由四部分組成：1）分裂之后左邊葉子節(jié)點(diǎn)的分?jǐn)?shù)；2）分裂之后右邊葉子節(jié)點(diǎn)的分?jǐn)?shù)示损；3）分裂之前葉子節(jié)點(diǎn)的分?jǐn)?shù)渗磅；4）一個(gè)葉子節(jié)點(diǎn)分裂為兩個(gè)葉子節(jié)點(diǎn)時(shí)額外增加的正則。

從Gain的表達(dá)式可以看出检访，如果葉子節(jié)點(diǎn)分裂的分?jǐn)?shù)差小于 $\gamma$ 始鱼，就不要再進(jìn)行分裂了。

Gain就是XGBoost在選擇分裂點(diǎn)時(shí)的評(píng)估依據(jù)脆贵。在實(shí)際進(jìn)行分裂時(shí)医清，為了比較高效的選擇最優(yōu)的分裂點(diǎn)，通常我們先把樣本按照候選特征進(jìn)行排序卖氨，然后進(jìn)行遍歷并計(jì)算每個(gè)可能分裂點(diǎn)的Gain会烙。

2 XGBoost算法優(yōu)化

2.1 Shrinkage and Column Subsampling

除了使用正則項(xiàng)之外，XGBoost還使用另外兩種技術(shù)進(jìn)一步防止過(guò)擬合筒捺。第一個(gè)是shrinkage柏腻，由Friedman提出（就是那個(gè)提出GBDT算法的Friedman）。Shrinkage對(duì)新學(xué)習(xí)到的樹(shù)節(jié)點(diǎn)的分?jǐn)?shù)進(jìn)行縮放系吭，類(lèi)似于梯度優(yōu)化中的學(xué)習(xí)率五嫂，shrinkage對(duì)單棵樹(shù)的預(yù)測(cè)結(jié)果進(jìn)行縮放，降低了單棵樹(shù)的預(yù)測(cè)結(jié)果在模型中的權(quán)重肯尺，并且給以后的樹(shù)留出了學(xué)習(xí)空間沃缘。第二個(gè)是列采樣，列采樣通常被用在RandomForest中则吟。列采樣相比行采樣（也就是對(duì)樣本進(jìn)行采樣槐臀，XGBoost也支持行采樣），防止過(guò)擬合的效果更好氓仲，同時(shí)峰档，列采樣也一定程度上加速了XGBoost的并行計(jì)算。

2.2 最佳分裂點(diǎn)尋找算法

2.2.1 精確貪婪算法

樹(shù)訓(xùn)練中的一個(gè)比較重要的問(wèn)題就是尋找最佳分裂點(diǎn)寨昙。最基本的精確貪婪算法通過(guò)遍歷所有可能的分裂點(diǎn)讥巡，然后計(jì)算Gain，選擇Gain最大的分裂點(diǎn)舔哪。為了提高遍歷效率欢顷，需要首先對(duì)樣本按照特征值進(jìn)行排序。精確貪婪算法的流程見(jiàn)Algorithm1捉蚤。

image-20200326135621161.png

2.2.2 近似算法

精確貪婪算法因?yàn)橐闅v所有可能的分裂點(diǎn)抬驴，所以總是能夠找到最佳的分裂點(diǎn)炼七，但是當(dāng)數(shù)據(jù)量足夠大，超出內(nèi)存容量的時(shí)候布持，這種方式就失效了豌拙。另外，在分布式計(jì)算的情況下题暖，數(shù)據(jù)分布在不同的節(jié)點(diǎn)上按傅，精確貪婪算法也不能進(jìn)行有效的計(jì)算。在這兩種情況下胧卤，就需要采用近似算法唯绍。近似算法首先根據(jù)特征值分布的百分位數(shù)產(chǎn)生一些候選分割點(diǎn)，然后根據(jù)候選分割點(diǎn)把連續(xù)的特征離散化枝誊，然后計(jì)算梯度統(tǒng)計(jì)gi和hi况芒，根據(jù)梯度統(tǒng)計(jì)計(jì)算obj*和gain，進(jìn)而尋找最佳候選分割點(diǎn)叶撒。詳細(xì)的算法流程見(jiàn)Algorithm2.

2.png

根據(jù)候選分割點(diǎn)在什么時(shí)候產(chǎn)生绝骚，近似算法又分成兩種形式。第一種是global variant祠够，是在樹(shù)構(gòu)造之前首先產(chǎn)生所有的候選分割點(diǎn)皮壁，后面在樹(shù)的每一層進(jìn)行分裂的時(shí)候都使用這些候選分割點(diǎn)。另外一種是Local variant哪审，是在每次節(jié)點(diǎn)分裂之后，根據(jù)分配到節(jié)點(diǎn)的樣本重新產(chǎn)生候選分割點(diǎn)虑瀑。Global variant只產(chǎn)生一次候選分割點(diǎn)湿滓，而local variant需要多次產(chǎn)生候選分割點(diǎn)，但是由于屬于樹(shù)中間層節(jié)點(diǎn)的樣本較少舌狗，尤其是隨著樹(shù)的深度增加叽奥，local variant相比global variant產(chǎn)生的候選分割點(diǎn)數(shù)量更少，而且由于local variant產(chǎn)生候選分割點(diǎn)只依賴(lài)于當(dāng)前節(jié)點(diǎn)的樣本特征值痛侍，因此更適合于deeper tree朝氓。

為了對(duì)比global variant和local variant，我們?cè)贖iggs boson dataset（一個(gè)kaggle比賽的數(shù)據(jù)集）上對(duì)兩種方式進(jìn)行試驗(yàn)主届，試驗(yàn)結(jié)果見(jiàn)下圖赵哲。

3.png

（說(shuō)明：eps越小，說(shuō)明產(chǎn)生的候選分割點(diǎn)越多君丁，原因或原理見(jiàn)2.2.3）

試驗(yàn)結(jié)果：1）global eps=0.05和exact greedy對(duì)比說(shuō)明枫夺，近似算法的global variant如果產(chǎn)生足夠多數(shù)量的候選分裂點(diǎn)，基本達(dá)到和精確貪婪算法同樣的模型效果绘闷；2）global eps=0.3和local eps=0.3對(duì)比說(shuō)明橡庞，產(chǎn)生候選分裂點(diǎn)數(shù)量相同的情況下较坛，local variant相比global variant能達(dá)到更好的模型效果（因?yàn)樵跇?shù)的非根節(jié)點(diǎn)，相同數(shù)量的候選分裂點(diǎn)的情況下扒最，實(shí)際上local variant要比global variant劃分的更加精細(xì)）丑勤，或者反過(guò)來(lái)說(shuō)也可以，要達(dá)到同樣的模型效果吧趣，local variant相比global variant需要更少的候選分裂點(diǎn)法竞。

2.2.3 加權(quán)的百分位數(shù)候選分裂點(diǎn)產(chǎn)生方法（weighted quantile sketch）

近似算法中重要的一步就是產(chǎn)生合理的候選分裂點(diǎn)，通常是根據(jù)特征值的百分位數(shù)點(diǎn)產(chǎn)生候選分割點(diǎn)再菊，這樣可以把特征值平均的分成若干個(gè)區(qū)間爪喘。實(shí)際上，XGBoost中采取的方法是纠拔，計(jì)算 $D_{k} = \left\{(x_{1k}, h_{1}), (x_{2k}, h_{2}), ... (x_{nk}, h_{n})\right\}$ 秉剑，其中 $x_{nk}$ 表示第k個(gè)特征的第n個(gè)樣本的值， $h_{n}$ 表示目標(biāo)函數(shù)關(guān)于 $x_{nk}$ 的二階導(dǎo)數(shù)稠诲，然后定義排序函數(shù) $r_{k}, R\rightarrow \left [0,+\infty \right ]$ ：

$r_{k}(z)=\frac{1}{\sum_{(x,h)\epsilon D_{k}}^{}h}\sum_{(x,h)\epsilon D_{k},x<z}^{}h$

表示在 $D_{k}$ 中特征值小于z的樣本加權(quán)占比侦鹏，權(quán)重為h。

為什么把二階導(dǎo)數(shù)作為權(quán)重呢臀叙？原因來(lái)源于目標(biāo)函數(shù)表達(dá)式：

$obj^{(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})$

對(duì)以上表達(dá)式變換一下：

$\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}\frac{1}{2}h_{i}(f_{t}(x_{i}) - \frac{g_{i}}{h_{i}})^2 + \Omega(f_{t}) + constant$

這個(gè)表達(dá)式格式可以看做是以 $\frac{g_{i}}{h_{i}}$ 為label略水，以 $h_{i}$ 為權(quán)重的加權(quán)平方損失。

定義排序函數(shù)的目標(biāo)是尋找候選分裂點(diǎn) $\left\{s_{k1},s_{k2}, ...s_{kl}\right\}$ 劝萤，候選分裂點(diǎn)必須滿(mǎn)足：

$|r_{k}(s_{k}, j) - r_{k}(s_{k}, j+1)| < \epsilon , s_{k1}=\underset{i}{min}\mathbf{x}_{ik},s_{kl}=\underset{i}{max}\mathbf{x}_{ik}$

這里 $\epsilon$ 是一個(gè)超參數(shù)（2.2.2中的eps就是指的這個(gè)超參數(shù)）渊涝，直觀上可以理解為，候選分裂點(diǎn)的數(shù)量大概為 $\frac{1}{\epsilon }$ .

2.2.4 稀疏數(shù)據(jù)的最佳分裂點(diǎn)尋找算法

在實(shí)際應(yīng)用中床嫌，最常見(jiàn)的是類(lèi)型是稀疏類(lèi)型的特征跨释，就是特征里面可能包含大量的缺失值。為了使XGBoost能夠適用大量缺失值的場(chǎng)景厌处，在樹(shù)分裂的時(shí)候鳖谈，給缺失值一個(gè)默認(rèn)的分裂方向（全部分裂到左子節(jié)點(diǎn)或者全部分裂到右子節(jié)點(diǎn)），默認(rèn)的分裂方向是通過(guò)在訓(xùn)練數(shù)據(jù)上學(xué)習(xí)得到的阔涉。學(xué)習(xí)默認(rèn)分裂方向的算法見(jiàn)Algorithm3缆娃。算法只遍歷沒(méi)有缺失的樣本，然后把有缺失值的樣本當(dāng)做一個(gè)整體瑰排，通過(guò)全部將其分到左子節(jié)點(diǎn)或右子節(jié)點(diǎn)贯要，比較分到左邊或右邊的效果更好，就把全部缺失值樣本分到哪邊椭住。

clip_image001.png

大多數(shù)已有的樹(shù)學(xué)習(xí)算法要么僅針對(duì)密集數(shù)據(jù)進(jìn)行了優(yōu)化郭毕，要么需要特定的過(guò)程來(lái)處理有限的情況，例如分類(lèi)編碼函荣。 XGBoost以統(tǒng)一的方式處理所有稀疏模式显押。更重要的是扳肛，我們的方法利用了稀疏性，使計(jì)算復(fù)雜度與輸入中非缺失項(xiàng)的數(shù)量呈線(xiàn)性關(guān)系乘碑。

2.3 并行學(xué)習(xí)（Column Block for Parallel Learning）

XGBoost中最耗時(shí)的部分是對(duì)特征進(jìn)行排序挖息。為了提高排序的效率，我們采取事先把數(shù)據(jù)存儲(chǔ)在被稱(chēng)為block的內(nèi)存單元里兽肤，每個(gè)block中的數(shù)據(jù)是以列壓縮（CSC）的格式存儲(chǔ)套腹，每列都按照該列的數(shù)值大小進(jìn)行排序。這種輸入數(shù)據(jù)只需要在訓(xùn)練之前計(jì)算一次资铡，就可以重復(fù)用于之后每棵樹(shù)的迭代訓(xùn)練电禀。

在精確貪婪算法中，我們把整個(gè)數(shù)據(jù)集存儲(chǔ)在同一個(gè)block中笤休，并且存儲(chǔ)在block中的數(shù)據(jù)已經(jīng)是按照每列的特征值進(jìn)行排序后的尖飞，所以只需要遍歷一次block，并且根據(jù)每個(gè)樣本點(diǎn)屬于哪個(gè)葉子節(jié)點(diǎn)店雅，就能同時(shí)為每個(gè)葉子節(jié)點(diǎn)尋找到最佳分裂點(diǎn)政基。下圖表示了如何把數(shù)據(jù)集轉(zhuǎn)換成列壓縮（CSC)的格式，并且使用block高效的完成尋找最佳分裂點(diǎn)闹啦。

5.png

在近似算法尋找最佳分裂點(diǎn)中沮明，采取的block存儲(chǔ)方式與精確貪婪算法中有所不同，近似算法中采取用多個(gè)block對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)窍奋，每個(gè)block對(duì)應(yīng)于一部分樣本數(shù)據(jù)荐健，并且block可以分布在不同的機(jī)器上，或存儲(chǔ)在磁盤(pán)上琳袄。因?yàn)槊總€(gè)block是根據(jù)特征值預(yù)先排序的（此處江场，我理解應(yīng)該是整體數(shù)據(jù)集先排序之后，然后分散在不同的block中）挚歧，近似算法中的分位數(shù)搜索就變成了線(xiàn)性搜索，尤其是在local proposal模式下吁峻，候選分割點(diǎn)需要在每個(gè)分支下搜索產(chǎn)生滑负，線(xiàn)性搜索相比分位數(shù)搜索極大的提高了效率。

收集每列的梯度統(tǒng)計(jì)信息可以并行進(jìn)行用含，從而為我們提供了一種候選分裂點(diǎn)查找的并行算法矮慕。另外重要的是，CSC列壓縮存儲(chǔ)格式和block存儲(chǔ)結(jié)構(gòu)支持列采樣啄骇，所以可以很方便的選擇block中的部分列痴鳄。

2.4 Cache-aware Access緩存感知訪(fǎng)問(wèn)

block結(jié)構(gòu)降低了選取候選分裂點(diǎn)的計(jì)算復(fù)雜度，但是由于block中的數(shù)據(jù)是按照CSC的列壓縮格式存儲(chǔ)的缸夹，并且每列是按照特征值排序的痪寻，除了特征值之外螺句，還存儲(chǔ)了指針從特征值指向樣本索引，所以在選取候選分割點(diǎn)的時(shí)候橡类，會(huì)不斷的根據(jù)特征值對(duì)應(yīng)的樣本索引去取梯度統(tǒng)計(jì)值蛇尚，也就是說(shuō)CPU會(huì)不斷地訪(fǎng)問(wèn)非連續(xù)的內(nèi)存單元，增加CPU的負(fù)擔(dān)顾画。最簡(jiǎn)單的實(shí)現(xiàn)方法是取劫，CPU讀取一次內(nèi)存單元中的梯度統(tǒng)計(jì)值，就進(jìn)行一次累計(jì)計(jì)算研侣，就回引起CPU在累計(jì)計(jì)算和訪(fǎng)問(wèn)非連續(xù)的內(nèi)存單元之間的讀寫(xiě)依賴(lài)關(guān)系谱邪。如果block中的梯度統(tǒng)計(jì)數(shù)據(jù)不能進(jìn)入CPU緩存（比如block太大等原因），或者發(fā)生緩存丟失cache miss庶诡，就會(huì)降低候選分裂點(diǎn)選取的效率惦银。

對(duì)于精確的貪婪算法，我們可以通過(guò)緩存感知的預(yù)提取算法來(lái)緩解問(wèn)題灌砖。具體來(lái)說(shuō)璧函，我們給每個(gè)線(xiàn)程分配一個(gè)內(nèi)部緩沖區(qū)，將梯度統(tǒng)計(jì)信息提取到其中基显，然后以小批量的方式執(zhí)行累加蘸吓。這種預(yù)提取將直接讀/寫(xiě)依賴(lài)關(guān)系更改為更長(zhǎng)的依賴(lài)關(guān)系，并在行數(shù)較大時(shí)幫助減少運(yùn)行開(kāi)銷(xiāo)撩幽。在數(shù)據(jù)集較大時(shí)库继，精確貪婪算法的可感知緩存的運(yùn)行速度是普通版本的兩倍。

對(duì)于近似算法窜醉，我們通過(guò)選擇合適的block大小來(lái)解決該問(wèn)題宪萄。我們將block大小定義為一個(gè)block中包含的最大樣本數(shù)，因?yàn)檫@反映了梯度統(tǒng)計(jì)信息的緩存存儲(chǔ)成本榨惰。選擇過(guò)小的block大小會(huì)較小每個(gè)線(xiàn)程的工作量拜英，但是同時(shí)也會(huì)降低并行化效率。另一方面琅催，太大的block會(huì)導(dǎo)致高速緩存丟失cache miss居凶，因此 block大小的選擇應(yīng)該要平衡這兩個(gè)因素。通過(guò)在不同數(shù)據(jù)集上的測(cè)試藤抡，block大小設(shè)置為 $2^{16}$ 是個(gè)合適的選擇侠碧。

2.5 Block for Out-of-core Computation核外計(jì)算

為了充分利用機(jī)器的資源來(lái)實(shí)現(xiàn)可擴(kuò)展的學(xué)習(xí)，除了處理器和內(nèi)存之外缠黍，利用磁盤(pán)空間來(lái)處理不能放在主內(nèi)存的數(shù)據(jù)也很重要弄兜。為了實(shí)現(xiàn)核外計(jì)算，我們將數(shù)據(jù)分為多個(gè)block，并將每個(gè)block存儲(chǔ)在磁盤(pán)上替饿。在計(jì)算過(guò)程中语泽，重要的是要使用獨(dú)立的線(xiàn)程將block預(yù)提取到主存儲(chǔ)器緩沖區(qū)中，這樣就可以在讀取磁盤(pán)的同時(shí)進(jìn)行計(jì)算盛垦。但是湿弦，磁盤(pán)讀取占用了大部分計(jì)算時(shí)間，所以要減少開(kāi)銷(xiāo)并增加磁盤(pán)IO的吞吐量腾夯。我們主要使用兩種技術(shù)來(lái)改進(jìn)核外計(jì)算颊埃。

1）block壓縮

將block按列進(jìn)行壓縮，然后在加載到內(nèi)存時(shí)通過(guò)獨(dú)立的線(xiàn)程解壓縮蝶俱，相當(dāng)于用解壓縮時(shí)間換取磁盤(pán)讀取成本班利。我們使用通用壓縮算法來(lái)壓縮特征值。對(duì)于行索引榨呆，我們把block中每個(gè)樣本的索引值都減去開(kāi)始索引罗标，并使用16位整數(shù)存儲(chǔ)每個(gè)樣本的索引偏移量。在我們測(cè)試的大多數(shù)數(shù)據(jù)集中积蜻，我們實(shí)現(xiàn)了大約26％至29％的壓縮率闯割。

2）block分片

將block中的數(shù)據(jù)分片到多個(gè)磁盤(pán)上，并且給每個(gè)磁盤(pán)分配獨(dú)立的線(xiàn)程竿拆，將數(shù)據(jù)提前取入內(nèi)存緩沖區(qū)中宙拉，然后，訓(xùn)練線(xiàn)程可以從每個(gè)緩沖區(qū)讀取數(shù)據(jù)丙笋。當(dāng)有多個(gè)磁盤(pán)可用時(shí)谢澈，這有助于增加磁盤(pán)讀取的吞吐量。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末御板，一起剝皮案震驚了整個(gè)濱河市锥忿，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌怠肋，老刑警劉巖敬鬓，帶你破解...
沈念sama閱讀 211,743評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異笙各，居然都是意外死亡钉答，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,296評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)酪惭，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)希痴，“玉大人者甲，你說(shuō)我怎么就攤上這事春感。” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 157,285評(píng)論 0贊 348
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵鲫懒，是天一觀的道長(zhǎng)嫩实。經(jīng)常有香客問(wèn)我，道長(zhǎng)窥岩，這世上最難降的妖魔是什么甲献？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,485評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮颂翼，結(jié)果婚禮上晃洒，老公的妹妹穿的比我還像新娘。我一直安慰自己朦乏，他們只是感情好球及，可當(dāng)我...
茶點(diǎn)故事閱讀 65,581評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著呻疹，像睡著了一般吃引。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上刽锤，一...
開(kāi)封第一講書(shū)人閱讀 49,821評(píng)論 1贊 290
城市分裂傳說(shuō)
那天镊尺，我揣著相機(jī)與錄音，去河邊找鬼并思。笑死庐氮，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的纺荧。我是一名探鬼主播旭愧，決...
沈念sama閱讀 38,960評(píng)論 3贊 408
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼宙暇！你這毒婦竟也來(lái)了输枯？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 37,719評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤占贫，失蹤者是張志新（化名）和其女友劉穎桃熄，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體型奥，經(jīng)...
沈念sama閱讀 44,186評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡瞳收，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,516評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了厢汹。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片螟深。...
茶點(diǎn)故事閱讀 38,650評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖烫葬，靈堂內(nèi)的尸體忽然破棺而出界弧，到底是詐尸還是另有隱情凡蜻，我是刑警寧澤，帶...
沈念sama閱讀 34,329評(píng)論 4贊 330
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布垢箕，位于F島的核電站划栓，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏条获。R本人自食惡果不足惜忠荞，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,936評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望帅掘。院中可真熱鬧委煤，春花似錦、人聲如沸修档。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,757評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)萍悴。三九已至头遭，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間癣诱，已是汗流浹背计维。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,991評(píng)論 1贊 266
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留撕予，地道東北人鲫惶。一個(gè)月前我還...
沈念sama閱讀 46,370評(píng)論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像实抡，于是被迫代替她去往敵國(guó)和親欠母。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,527評(píng)論 2贊 349

XGBoost原理詳解及系統(tǒng)優(yōu)化

1 XGBoost原理

1.1 監(jiān)督學(xué)習(xí)概念回顧

1.1.1模型和參數(shù)

1.1.2 目標(biāo)函數(shù)：損失+正則

1.2 決策樹(shù)加法模型

1.2.1 加法模型的訓(xùn)練Additive Training

1.2.2 模型復(fù)雜度

1.2.3 模型訓(xùn)練

2 XGBoost算法優(yōu)化

2.1 Shrinkage and Column Subsampling

2.2 最佳分裂點(diǎn)尋找算法

2.2.1 精確貪婪算法

2.2.2 近似算法

2.2.3 加權(quán)的百分位數(shù)候選分裂點(diǎn)產(chǎn)生方法（weighted quantile sketch）

2.2.4 稀疏數(shù)據(jù)的最佳分裂點(diǎn)尋找算法

2.3 并行學(xué)習(xí)（Column Block for Parallel Learning）

2.4 Cache-aware Access緩存感知訪(fǎng)問(wèn)

2.5 Block for Out-of-core Computation核外計(jì)算

推薦閱讀更多精彩內(nèi)容