XGBoost是數(shù)據(jù)挖掘類競(jìng)賽中經(jīng)常使用的一大利器，它幫助選手在Kaggle、阿里天池大數(shù)據(jù)比賽等比賽取得了很好的成績(jī)。XGBoost被很多人使用，但很少人知道其原理，前幾天看了一下陳天奇大神的論文有了更多的理解。XGBoost是基于GBDT(Gradient Boosting Decision Tree) 改進(jìn)而來的，本文將對(duì)XGBoost算法原理進(jìn)行介紹，主要通過以下幾個(gè)部分進(jìn)行介紹：boosted trees、目標(biāo)函數(shù)正則化、節(jié)點(diǎn)切分算法。
注： 本文假設(shè)讀者理解回歸樹算法、泰勒公式、梯度下降法和牛頓法
1. Boosted trees
Boosted trees是一種集成方法，Boosting算法是一種加法模型(additive training)，定義如下：
q(x)表示將樣本x分到了某個(gè)葉子節(jié)點(diǎn)上，w是葉子節(jié)點(diǎn)的分?jǐn)?shù)（leaf score）
下面通過一個(gè)具體的例子來說明：預(yù)測(cè)一個(gè)人是否喜歡電腦游戲，下圖表明小男孩更喜歡打游戲。
2. 目標(biāo)函數(shù)正則化
XGBoost使用的目標(biāo)函數(shù)如下：
我們可以看出XGBoost在GBDT的誤差函數(shù)基礎(chǔ)上加入了L1和L2正則項(xiàng)，其中Loss函數(shù)可以是平方損失或邏輯損失，T代表葉子節(jié)點(diǎn)數(shù)，w代表葉子節(jié)點(diǎn)的分?jǐn)?shù)。加入正則項(xiàng)的好處是防止過擬合，這個(gè)好處是由兩方面體現(xiàn)的：一是預(yù)剪枝，因?yàn)檎齽t項(xiàng)中有限定葉子節(jié)點(diǎn)數(shù)；二是正則項(xiàng)里leaf scroe的L2模平方的系數(shù)，對(duì)leaf scroe做了平滑。
接下來我們對(duì)目標(biāo)函數(shù)進(jìn)行目標(biāo)函數(shù)的求解：
該目標(biāo)函數(shù)表示：第i樣本的第t次迭代誤差函數(shù)，后面的推導(dǎo)基于上式。這種學(xué)習(xí)方式已經(jīng)從函數(shù)空間轉(zhuǎn)到了函數(shù)空間：
下面對(duì)目標(biāo)函數(shù)進(jìn)行泰勒公式二級(jí)展開、化簡(jiǎn)：
如果確定了樹的結(jié)構(gòu)，為了使目標(biāo)函數(shù)最小，可以令其導(dǎo)數(shù)為0，解得每個(gè)葉節(jié)點(diǎn)的最優(yōu)預(yù)測(cè)分?jǐn)?shù)為：
代入目標(biāo)函數(shù)，解得最小損失為：
3. 節(jié)點(diǎn)切分算法
注： 近似算法中使用到了分位數(shù)，關(guān)于分位數(shù)的選取，論文提出了一種算法Weighted Quantile Sketch 。XGBoost不是按照樣本個(gè)數(shù)進(jìn)行分位，而是以二階導(dǎo)數(shù)為權(quán)重
Q: 為什么使用hi加權(quán)？
A: 比較直觀的解釋是因?yàn)槟繕?biāo)函數(shù)可以化簡(jiǎn)為如下形式：
-
其他
在實(shí)際工作中，大多數(shù)輸入是稀疏的。造成稀疏的原因有很多種，比如：缺失值、one-hot編碼等。因此，論文提出為樹中的節(jié)點(diǎn)設(shè)置一個(gè)默認(rèn)方向來應(yīng)對(duì)稀疏輸入。論文實(shí)驗(yàn)表明稀疏感知算法 要比傳統(tǒng)方法快50倍，算法如下：
下面通過例子具體說明：
注： 紅色路徑代表默認(rèn)方向
Shrinkage: 可以理解為學(xué)習(xí)率，算法每次迭代后會(huì)乘這個(gè)系數(shù)；
列采樣： 降低過擬合，論文實(shí)驗(yàn)表明列采樣比行采樣效果好。
