XGBoost是數(shù)據(jù)挖掘類競(jìng)賽中經(jīng)常使用的一大利器，它幫助選手在Kaggle歇盼、阿里天池大數(shù)據(jù)比賽等比賽取得了很好的成績(jī)违寿。XGBoost被很多人使用，但很少人知道其原理扫倡，前幾天看了一下陳天奇大神的論文有了更多的理解谦秧。XGBoost是基于GBDT(Gradient Boosting Decision Tree) 改進(jìn)而來(lái)的，本文將對(duì)XGBoost算法原理進(jìn)行介紹撵溃，主要通過(guò)以下幾個(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）
下面通過(guò)一個(gè)具體的例子來(lái)說(shuō)明：預(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)的好處是防止過(guò)擬合宙暇，這個(gè)好處是由兩方面體現(xiàn)的：一是預(yù)剪枝，因?yàn)檎齽t項(xiàng)中有限定葉子節(jié)點(diǎn)數(shù)议泵；二是正則項(xiàng)里leaf scroe的L2模平方的系數(shù)占贫，對(duì)leaf scroe做了平滑。
接下來(lái)我們對(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)方向來(lái)應(yīng)對(duì)稀疏輸入。論文實(shí)驗(yàn)表明稀疏感知算法 要比傳統(tǒng)方法快50倍奋姿，算法如下：
下面通過(guò)例子具體說(shuō)明：
注： 紅色路徑代表默認(rèn)方向
Shrinkage: 可以理解為學(xué)習(xí)率锄开，算法每次迭代后會(huì)乘這個(gè)系數(shù)；
列采樣： 降低過(guò)擬合称诗，論文實(shí)驗(yàn)表明列采樣比行采樣效果好萍悴。
