初看Xgboost，翻了多篇博客發(fā)現(xiàn)關(guān)于xgboost原理的描述實(shí)在難以忍受，缺乏邏輯性，寫一篇供討論。

觀其大略，而后深入細(xì)節(jié)，一開始扎進(jìn)公式反正我是覺得效率不高，還容易打消人的積極性。

首先說(shuō)下決策樹

決策樹是啥？舉個(gè)例子，有一堆人，我讓你分出男女，你依靠頭發(fā)長(zhǎng)短將人群分為兩撥，長(zhǎng)發(fā)的為“女”，短發(fā)為“男”，你是不是依靠一個(gè)指標(biāo)“頭發(fā)長(zhǎng)短”將人群進(jìn)行了劃分，你就形成了一個(gè)簡(jiǎn)單的決策樹，官方細(xì)節(jié)版本自行baidu或google

劃分的依據(jù)是啥？這個(gè)時(shí)候，你肯定問(wèn)，為什么用“頭發(fā)長(zhǎng)短”劃分啊，我可不可以用“穿的鞋子是否是高跟鞋”，“有沒有喉結(jié)”等等這些來(lái)劃分啊，Of course！那么肯定就需要判斷了，那就是哪一種分類效果好，我就選哪一種啊。

分類效果如何評(píng)價(jià)量化呢？怎么判斷“頭發(fā)長(zhǎng)短”或者“是否有喉結(jié)”…是最好的劃分方式，效果怎么量化。直觀來(lái)說(shuō)，如果根據(jù)某個(gè)標(biāo)準(zhǔn)分裂人群后，純度越高效果越好，比如說(shuō)你分為兩群，“女”那一群都是女的，“男”那一群全是男的，這個(gè)效果是最好的，但事實(shí)不可能那么巧合，所以越接近這種情況，我們認(rèn)為效果越好。于是量化的方式有很多，信息增益（ID3）、信息增益率（C4.5）、基尼系數(shù)（CART）等等，來(lái)用來(lái)量化純度

其他細(xì)節(jié)如剪枝、過(guò)擬合、優(yōu)缺點(diǎn)、并行情況等自己去查吧。決策樹的靈魂就已經(jīng)有了，依靠某種指標(biāo)進(jìn)行樹的分裂達(dá)到分類/回歸的目的（上面的例子是分類），總是希望純度越高越好。

說(shuō)下Xgboost的建樹過(guò)程

Xgboost是很多CART回歸樹集成

概念1：回歸樹與決策樹事實(shí)上，分類與回歸是一個(gè)型號(hào)的東西，只不過(guò)分類的結(jié)果是離散值，回歸是連續(xù)的，本質(zhì)是一樣的，都是特征（feature）到結(jié)果/標(biāo)簽（label）之間的映射。說(shuō)說(shuō)決策樹和回歸樹，在上面決策樹的講解中相信決策樹分類已經(jīng)很好理解了。

回歸樹是個(gè)啥呢？

直接摘抄人家的一句話，分類樹的樣本輸出（即響應(yīng)值）是類的形式，如判斷蘑菇是有毒還是無(wú)毒，周末去看電影還是不去。而回歸樹的樣本輸出是數(shù)值的形式，比如給某人發(fā)放房屋貸款的數(shù)額就是具體的數(shù)值，可以是0到120萬(wàn)元之間的任意值。

那么，這時(shí)候你就沒法用上述的信息增益、信息增益率、基尼系數(shù)來(lái)判定樹的節(jié)點(diǎn)分裂了，你就會(huì)采用新的方式，預(yù)測(cè)誤差，常用的有均方誤差、對(duì)數(shù)誤差等。而且節(jié)點(diǎn)不再是類別，是數(shù)值（預(yù)測(cè)值），那么怎么確定呢，有的是節(jié)點(diǎn)內(nèi)樣本均值，有的是最優(yōu)化算出來(lái)的比如Xgboost。細(xì)節(jié)http://blog.csdn.net/app_12062011/article/details/52136117博主講的不錯(cuò)

概念2：boosting集成學(xué)習(xí)，由多個(gè)相關(guān)聯(lián)的決策樹聯(lián)合決策，什么叫相關(guān)聯(lián)，舉個(gè)例子，有一個(gè)樣本[數(shù)據(jù)->標(biāo)簽]是[(2，4，5)-> 4]，第一棵決策樹用這個(gè)樣本訓(xùn)練得預(yù)測(cè)為3.3，那么第二棵決策樹訓(xùn)練時(shí)的輸入，這個(gè)樣本就變成了[(2，4，5)-> 0.7]，也就是說(shuō)，下一棵決策樹輸入樣本會(huì)與前面決策樹的訓(xùn)練和預(yù)測(cè)相關(guān)。

與之對(duì)比的是random foreast（隨機(jī)森林）算法，各個(gè)決策樹是獨(dú)立的、每個(gè)決策樹在樣本堆里隨機(jī)選一批樣本，隨機(jī)選一批特征進(jìn)行獨(dú)立訓(xùn)練，各個(gè)決策樹之間沒有啥毛線關(guān)系。

所以首先Xgboost首先是一個(gè)boosting的集成學(xué)習(xí)，這樣應(yīng)該很通俗了

這個(gè)時(shí)候大家就能感覺到一個(gè)回歸樹形成的關(guān)鍵點(diǎn)：（1）分裂點(diǎn)依據(jù)什么來(lái)劃分（如前面說(shuō)的均方誤差最小，loss）；（2）分類后的節(jié)點(diǎn)預(yù)測(cè)值是多少（如前面說(shuō)，有一種是將葉子節(jié)點(diǎn)下各樣本實(shí)際值得均值作為葉子節(jié)點(diǎn)預(yù)測(cè)誤差，或者計(jì)算所得）

是時(shí)候看看Xgboost了

首先明確下我們的目標(biāo)，希望建立K個(gè)回歸樹，使得樹群的預(yù)測(cè)值盡量接近真實(shí)值（準(zhǔn)確率）而且有盡量大的泛化能力（更為本質(zhì)的東西），從數(shù)學(xué)角度看這是一個(gè)泛函最優(yōu)化，多目標(biāo)，看下目標(biāo)函數(shù)：

直觀上看，目標(biāo)要求預(yù)測(cè)誤差盡量小，葉子節(jié)點(diǎn)盡量少，節(jié)點(diǎn)數(shù)值盡量不極端（這個(gè)怎么看，如果某個(gè)樣本label數(shù)值為4，那么第一個(gè)回歸樹預(yù)測(cè)3，第二個(gè)預(yù)測(cè)為1；另外一組回歸樹，一個(gè)預(yù)測(cè)2，一個(gè)預(yù)測(cè)2，那么傾向后一種，為什么呢？前一種情況，第一棵樹學(xué)的太多，太接近4，也就意味著有較大的過(guò)擬合的風(fēng)險(xiǎn)）

ok，聽起來(lái)很美好，可是怎么實(shí)現(xiàn)呢，上面這個(gè)目標(biāo)函數(shù)跟實(shí)際的參數(shù)怎么聯(lián)系起來(lái)，記得我們說(shuō)過(guò)，回歸樹的參數(shù):（1）選取哪個(gè)feature分裂節(jié)點(diǎn)呢；（2）節(jié)點(diǎn)的預(yù)測(cè)值（總不能靠取平均值這么粗暴不講道理的方式吧，好歹高級(jí)一點(diǎn)）。上述形而上的公式并沒有“直接”解決這兩個(gè)，那么是如何間接解決的呢？

先說(shuō)答案：貪心策略+最優(yōu)化（二次最優(yōu)化，恩你沒看錯(cuò)）

通俗解釋貪心策略：就是決策時(shí)刻按照當(dāng)前目標(biāo)最優(yōu)化決定，說(shuō)白了就是眼前利益最大化決定，“目光短淺”策略，他的優(yōu)缺點(diǎn)細(xì)節(jié)大家自己去了解，經(jīng)典背包問(wèn)題等等。

這里是怎么用貪心策略的呢，剛開始你有一群樣本，放在第一個(gè)節(jié)點(diǎn)，這時(shí)候T=1，w多少呢，不知道，是求出來(lái)的，這時(shí)候所有樣本的預(yù)測(cè)值都是w（這個(gè)地方自己好好理解，決策樹的節(jié)點(diǎn)表示類別，回歸樹的節(jié)點(diǎn)表示預(yù)測(cè)值）,帶入樣本的label數(shù)值，此時(shí)loss function變?yōu)?/p>

暫停下，這里你發(fā)現(xiàn)了沒，二次函數(shù)最優(yōu)化！

要是損失函數(shù)不是二次函數(shù)咋辦，哦，泰勒展開式會(huì)否？，不是二次的想辦法近似為二次。

接著來(lái)，接下來(lái)要選個(gè)feature分裂成兩個(gè)節(jié)點(diǎn)，變成一棵弱小的樹苗，那么需要：

（1）確定分裂用的feature，how？最簡(jiǎn)單的是粗暴的枚舉，選擇loss function效果最好的那個(gè)（關(guān)于粗暴枚舉，Xgboost的改良并行方式咱們后面看）

（2）如何確立節(jié)點(diǎn)的w以及最小的loss function，大聲告訴我怎么做？對(duì)，二次函數(shù)的求最值（細(xì)節(jié)的會(huì)注意到，計(jì)算二次最值是不是有固定套路，導(dǎo)數(shù)=0的點(diǎn)，ok）

那么節(jié)奏是，選擇一個(gè)feature分裂，計(jì)算loss function最小值，然后再選一個(gè)feature分裂，又得到一個(gè)loss function最小值…你枚舉完，找一個(gè)效果最好的，把樹給分裂，就得到了小樹苗。

在分裂的時(shí)候，你可以注意到，每次節(jié)點(diǎn)分裂，loss function被影響的只有這個(gè)節(jié)點(diǎn)的樣本，因而每次分裂，計(jì)算分裂的增益（loss function的降低量）只需要關(guān)注打算分裂的那個(gè)節(jié)點(diǎn)的樣本。原論文這里會(huì)推導(dǎo)出一個(gè)優(yōu)雅的公式，我不想敲latex公式了，

想研究公式的去這里吧

http://matafight.github.io/2017/03/14/XGBoost-%E7%AE%80%E4%BB%8B/

接下來(lái)，繼續(xù)分裂，按照上述的方式，形成一棵樹，再形成一棵樹，每次在上一次的預(yù)測(cè)基礎(chǔ)上取最優(yōu)進(jìn)一步分裂/建樹，是不是貪心策略？！

凡是這種循環(huán)迭代的方式必定有停止條件，什么時(shí)候停止呢：

（1）當(dāng)引入的分裂帶來(lái)的增益小于一個(gè)閥值的時(shí)候，我們可以剪掉這個(gè)分裂，所以并不是每一次分裂loss function整體都會(huì)增加的，有點(diǎn)預(yù)剪枝的意思（其實(shí)我這里有點(diǎn)疑問(wèn)的，一般后剪枝效果比預(yù)剪枝要好點(diǎn)吧，只不過(guò)復(fù)雜麻煩些，這里大神請(qǐng)指教，為啥這里使用的是預(yù)剪枝的思想，當(dāng)然Xgboost支持后剪枝），閾值參數(shù)為γ正則項(xiàng)里葉子節(jié)點(diǎn)數(shù)T的系數(shù)（大神請(qǐng)確認(rèn)下）；

（2）當(dāng)樹達(dá)到最大深度時(shí)則停止建立決策樹，設(shè)置一個(gè)超參數(shù)max_depth，這個(gè)好理解吧，樹太深很容易出現(xiàn)的情況學(xué)習(xí)局部樣本，過(guò)擬合；

（3）當(dāng)樣本權(quán)重和小于設(shè)定閾值時(shí)則停止建樹，這個(gè)解釋一下，涉及到一個(gè)超參數(shù)-最小的樣本權(quán)重和min_child_weight，和GBM的 min_child_leaf 參數(shù)類似，但不完全一樣，大意就是一個(gè)葉子節(jié)點(diǎn)樣本太少了，也終止同樣是過(guò)擬合；

看下Xgboost的一些重點(diǎn)

w是最優(yōu)化求出來(lái)的，不是啥平均值或規(guī)則指定的，這個(gè)算是一個(gè)思路上的新穎吧；

正則化防止過(guò)擬合的技術(shù)，上述看到了，直接loss function里面就有；

支持自定義loss function，哈哈，不用我多說(shuō)，只要能泰勒展開（能求一階導(dǎo)和二階導(dǎo)）就行，你開心就好；

支持并行化，這個(gè)地方有必要說(shuō)明下，因?yàn)檫@是xgboost的閃光點(diǎn)，直接的效果是訓(xùn)練速度快，boosting技術(shù)中下一棵樹依賴上述樹的訓(xùn)練和預(yù)測(cè)，所以樹與樹之間應(yīng)該是只能串行！那么大家想想，哪里可以并行？！沒錯(cuò)，在選擇最佳分裂點(diǎn)，進(jìn)行枚舉的時(shí)候并行！（據(jù)說(shuō)恰好這個(gè)也是樹形成最耗時(shí)的階段）

Attention：同層級(jí)節(jié)點(diǎn)可并行。具體的對(duì)于某個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)選擇最佳分裂點(diǎn)，候選分裂點(diǎn)計(jì)算增益用多線程并行。—–

較少的離散值作為分割點(diǎn)倒是很簡(jiǎn)單，比如“是否是單身”來(lái)分裂節(jié)點(diǎn)計(jì)算增益是很easy，但是“月收入”這種feature，取值很多，從5k~50k都有，總不可能每個(gè)分割點(diǎn)都來(lái)試一下計(jì)算分裂增益吧？（比如月收入feature有1000個(gè)取值，難道你把這1000個(gè)用作分割候選？缺點(diǎn)1：計(jì)算量，缺點(diǎn)2：出現(xiàn)葉子節(jié)點(diǎn)樣本過(guò)少，過(guò)擬合）我們常用的習(xí)慣就是劃分區(qū)間，那么問(wèn)題來(lái)了，這個(gè)區(qū)間分割點(diǎn)如何確定（難道平均分割），作者是這么做的：

方法名字：Weighted Quantile Sketch大家還記得每個(gè)樣本在節(jié)點(diǎn)（將要分裂的節(jié)點(diǎn)）處的loss function一階導(dǎo)數(shù)gi和二階導(dǎo)數(shù)hi，衡量預(yù)測(cè)值變化帶來(lái)的loss function變化，舉例來(lái)說(shuō)，將樣本“月收入”進(jìn)行升序排列，5k、5.2k、5.3k、…、52k，分割線為“收入1”、“收入2”、…、“收入j”，滿足(每個(gè)間隔的樣本的hi之和/總樣本的hi之和）為某個(gè)百分比?（我這個(gè)是近似的說(shuō)法），那么可以一共分成大約1/?個(gè)分裂點(diǎn)。

數(shù)學(xué)形式，我再偷懶下（可是latex敲這種公式真的很頭疼）：

而且，有適用于分布式的算法設(shè)計(jì)；

XGBoost還特別設(shè)計(jì)了針對(duì)稀疏數(shù)據(jù)的算法，假設(shè)樣本的第i個(gè)特征缺失時(shí)，無(wú)法利用該特征對(duì)樣本進(jìn)行劃分，這里的做法是將該樣本默認(rèn)地分到指定的子節(jié)點(diǎn)，至于具體地分到哪個(gè)節(jié)點(diǎn)還需要某算法來(lái)計(jì)算，

算法的主要思想是，分別假設(shè)特征缺失的樣本屬于右子樹和左子樹，而且只在不缺失的樣本上迭代，分別計(jì)算缺失樣本屬于右子樹和左子樹的增益，選擇增益最大的方向?yàn)槿笔?shù)據(jù)的默認(rèn)方向（咋一看如果缺失情況為3個(gè)樣本，那么劃分的組合方式豈不是有8種？指數(shù)級(jí)可能性啊，仔細(xì)一看，應(yīng)該是在不缺失樣本情況下分裂后（有大神的請(qǐng)確認(rèn)或者修正），把第一個(gè)缺失樣本放左邊計(jì)算下loss function和放右邊進(jìn)行比較，同樣對(duì)付第二個(gè)、第三個(gè)…缺失樣本，這么看來(lái)又是可以并行的？？）；

可實(shí)現(xiàn)后剪枝

交叉驗(yàn)證，方便選擇最好的參數(shù)，early stop，比如你發(fā)現(xiàn)30棵樹預(yù)測(cè)已經(jīng)很好了，不用進(jìn)一步學(xué)習(xí)殘差了，那么停止建樹。

行采樣、列采樣，隨機(jī)森林的套路（防止過(guò)擬合）

Shrinkage，你可以是幾個(gè)回歸樹的葉子節(jié)點(diǎn)之和為預(yù)測(cè)值，也可以是加權(quán)，比如第一棵樹預(yù)測(cè)值為3.3，label為4.0，第二棵樹才學(xué)0.7，….再后面的樹還學(xué)個(gè)鬼，所以給他打個(gè)折扣，比如3折，那么第二棵樹訓(xùn)練的殘差為4.0-3.3*0.3=3.01，這就可以發(fā)揮了啦，以此類推，作用是啥，防止過(guò)擬合，如果對(duì)于“偽殘差”學(xué)習(xí)，那更像梯度下降里面的學(xué)習(xí)率；

xgboost還支持設(shè)置樣本權(quán)重，這個(gè)權(quán)重體現(xiàn)在梯度g和二階梯度h上，是不是有點(diǎn)adaboost的意思，重點(diǎn)關(guān)注某些樣本。

看下Xgboost的工程優(yōu)化

這部分因?yàn)闆]有實(shí)戰(zhàn)經(jīng)驗(yàn)，都是論文、博客解讀來(lái)的，所以也不十分確定，供參考。

Column Block for Parallel Learning總的來(lái)說(shuō)：按列切開，升序存放；方便并行，同時(shí)解決一次性樣本讀入炸內(nèi)存的情況

由于將數(shù)據(jù)按列存儲(chǔ)，可以同時(shí)訪問(wèn)所有列，那么可以對(duì)所有屬性同時(shí)執(zhí)行split finding算法，從而并行化split finding（切分點(diǎn)尋找）-特征間并行可以用多個(gè)block(Multiple blocks)分別存儲(chǔ)不同的樣本集，多個(gè)block可以并行計(jì)算-特征內(nèi)并行

Blocks for Out-of-core Computation數(shù)據(jù)大時(shí)分成多個(gè)block存在磁盤上，在計(jì)算過(guò)程中，用另外的線程讀取數(shù)據(jù)，但是由于磁盤IO速度太慢，通常更不上計(jì)算的速度，將block按列壓縮，對(duì)于行索引，只保存第一個(gè)索引值，然后只保存該數(shù)據(jù)與第一個(gè)索引值之差(offset)，一共用16個(gè)bits來(lái)保存 offset，因此，一個(gè)block一般有2的16次方個(gè)樣本。

與GDBT、深度學(xué)習(xí)對(duì)比下

Xgboost第一感覺就是防止過(guò)擬合+各種支持分布式/并行，所以一般傳言這種大殺器效果好（集成學(xué)習(xí)的高配）+訓(xùn)練效率高（分布式），與深度學(xué)習(xí)相比，對(duì)樣本量和特征數(shù)據(jù)類型要求沒那么苛刻，適用范圍廣。

說(shuō)下GBDT：有兩種描述版本，把GBDT說(shuō)成一個(gè)迭代殘差樹，認(rèn)為每一棵迭代樹都在學(xué)習(xí)前N-1棵樹的殘差；把GBDT說(shuō)成一個(gè)梯度迭代樹，使用梯度迭代下降法求解，認(rèn)為每一棵迭代樹都在學(xué)習(xí)前N-1棵樹的梯度下降值。有說(shuō)法說(shuō)前者是后者在loss function為平方誤差下的特殊情況。這里說(shuō)下我的理解：第一棵樹形成之

Xgboost和深度學(xué)習(xí)的關(guān)系，陳天奇在Quora上的解答如下：不同的機(jī)器學(xué)習(xí)模型適用于不同類型的任務(wù)。深度神經(jīng)網(wǎng)絡(luò)通過(guò)對(duì)時(shí)空位置建模，能夠很好地捕獲圖像、語(yǔ)音、文本等高維數(shù)據(jù)。而基于樹模型的XGBoost則能很好地處理表格數(shù)據(jù)，同時(shí)還擁有一些深度神經(jīng)網(wǎng)絡(luò)所沒有的特性（如：模型的可解釋性、輸入數(shù)據(jù)的不變性、更易于調(diào)參等）。這兩類模型都很重要，并廣泛用于數(shù)據(jù)科學(xué)競(jìng)賽和工業(yè)界。舉例來(lái)說(shuō)，幾乎所有采用機(jī)器學(xué)習(xí)技術(shù)的公司都在使用tree boosting，同時(shí)XGBoost已經(jīng)給業(yè)界帶來(lái)了很大的影響。