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

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

首先說下決策樹

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

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

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

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

說下Xgboost的建樹過程

Xgboost是很多CART回歸樹集成

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

回歸樹是個啥呢？

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

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

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

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

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

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

是時候看看Xgboost了

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

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

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

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

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

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

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

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

接著來，接下來要選個feature分裂成兩個節(jié)點，變成一棵弱小的樹苗，那么需要：

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

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

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

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

想研究公式的去這里吧

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

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

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

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

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

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

看下Xgboost的一些重點

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

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

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

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

Attention：同層級節(jié)點可并行。具體的對于某個節(jié)點，節(jié)點內(nèi)選擇最佳分裂點，候選分裂點計算增益用多線程并行?！C

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

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

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

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

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

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

可實現(xiàn)后剪枝

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

行采樣、列采樣，隨機森林的套路（防止過擬合）

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

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

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

這部分因為沒有實戰(zhàn)經(jīng)驗，都是論文、博客解讀來的，所以也不十分確定，供參考。

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

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

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

與GDBT、深度學習對比下

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

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

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