GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹(shù)算法，該算法由多棵決策樹(shù)組成收捣，所有樹(shù)的結(jié)論累加起來(lái)做最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力（generalization)較強(qiáng)的算法摆碉。近些年更因?yàn)楸挥糜谒阉髋判虻臋C(jī)器學(xué)習(xí)模型而引起大家關(guān)注洒放。

后記：發(fā)現(xiàn)GBDT除了我描述的殘差版本外還有另一種GBDT描述，兩者大概相同齐媒，但求解方法（Gradient應(yīng)用）不同蒲每。其區(qū)別和另一版本的介紹鏈接見(jiàn)這里。由于另一版本介紹博客中亦有不少錯(cuò)誤喻括，建議大家還是先看本篇邀杏，再跳到另一版本描述，這個(gè)順序當(dāng)能兩版本都看懂唬血。

第1~4節(jié)：GBDT算法內(nèi)部究竟是如何工作的望蜡？

第5節(jié)：它可以用于解決哪些問(wèn)題？

第6節(jié)：它又是怎樣應(yīng)用于搜索排序的呢拷恨？

在此先給出我比較推薦的兩篇英文文獻(xiàn)脖律，喜歡英文原版的同學(xué)可直接閱讀：

【1】Boosting?Decision?Tree入門教程http://www.schonlau.net/publication/05stata_boosting.pdf

【2】LambdaMART用于搜索排序入門教程http://research.microsoft.com/pubs/132652/MSR-TR-2010-82.pdf

GBDT主要由三個(gè)概念組成：Regression?Decistion?Tree（即DT)，Gradient?Boosting（即GB)腕侄，Shrinkage?(算法的一個(gè)重要演進(jìn)分枝小泉，目前大部分源碼都按該版本實(shí)現(xiàn)）。搞定這三個(gè)概念后就能明白GBDT是如何工作的冕杠，要繼續(xù)理解它如何用于搜索排序則需要額外理解RankNet概念微姊，之后便功德圓滿。下文將逐個(gè)碎片介紹分预，最終把整張圖拼出來(lái)兢交。

一、?DT：回歸樹(shù)?Regression?Decision?Tree

提起決策樹(shù)（DT,?Decision?Tree)?絕大部分人首先想到的就是C4.5分類決策樹(shù)笼痹。但如果一開(kāi)始就把GBDT中的樹(shù)想成分類樹(shù)配喳，那就是一條歪路走到黑，一路各種坑凳干，最終摔得都要咯血了還是一頭霧水說(shuō)的就是LZ自己啊有木有界逛。咳嗯纺座，所以說(shuō)千萬(wàn)不要以為GBDT是很多棵分類樹(shù)。決策樹(shù)分為兩大類溉潭，回歸樹(shù)和分類樹(shù)净响。前者用于預(yù)測(cè)實(shí)數(shù)值，如明天的溫度喳瓣、用戶的年齡馋贤、網(wǎng)頁(yè)的相關(guān)程度；后者用于分類標(biāo)簽值畏陕，如晴天/陰天/霧/雨配乓、用戶性別、網(wǎng)頁(yè)是否是垃圾頁(yè)面。這里要強(qiáng)調(diào)的是犹芹，前者的結(jié)果加減是有意義的崎页，如10歲+5歲-3歲=12歲，后者則無(wú)意義腰埂，如男+男+女=到底是男是女飒焦？?GBDT的核心在于累加所有樹(shù)的結(jié)果作為最終結(jié)果，就像前面對(duì)年齡的累加（-3是加負(fù)3）屿笼，而分類樹(shù)的結(jié)果顯然是沒(méi)辦法累加的牺荠，所以GBDT中的樹(shù)都是回歸樹(shù)，不是分類樹(shù)驴一，這點(diǎn)對(duì)理解GBDT相當(dāng)重要（盡管GBDT調(diào)整后也可用于分類但不代表GBDT的樹(shù)是分類樹(shù)）休雌。那么回歸樹(shù)是如何工作的呢？

下面我們以對(duì)人的性別判別/年齡預(yù)測(cè)為例來(lái)說(shuō)明肝断，每個(gè)instance都是一個(gè)我們已知性別/年齡的人杈曲，而feature則包括這個(gè)人上網(wǎng)的時(shí)長(zhǎng)、上網(wǎng)的時(shí)段孝情、網(wǎng)購(gòu)所花的金額等鱼蝉。

作為對(duì)比，先說(shuō)分類樹(shù)箫荡，我們知道C4.5分類樹(shù)在每次分枝時(shí)魁亦，是窮舉每一個(gè)feature的每一個(gè)閾值，找到使得按照f(shuō)eature<=閾值羔挡，和feature>閾值分成的兩個(gè)分枝的熵最大的feature和閾值（熵最大的概念可理解成盡可能每個(gè)分枝的男女比例都遠(yuǎn)離1:1）洁奈，按照該標(biāo)準(zhǔn)分枝得到兩個(gè)新節(jié)點(diǎn)，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點(diǎn)绞灼，或達(dá)到預(yù)設(shè)的終止條件利术，若最終葉子節(jié)點(diǎn)中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點(diǎn)的性別低矮。

回歸樹(shù)總體流程也是類似印叁，不過(guò)在每個(gè)節(jié)點(diǎn)（不一定是葉子節(jié)點(diǎn)）都會(huì)得一個(gè)預(yù)測(cè)值，以年齡為例军掂，該預(yù)測(cè)值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值轮蜕。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵蝗锥，而是最小化均方差--即（每個(gè)人的年齡-預(yù)測(cè)年齡）^2?的總和?/?N跃洛，或者說(shuō)是每個(gè)人的預(yù)測(cè)誤差平方和?除以?N。這很好理解终议，被預(yù)測(cè)出錯(cuò)的人數(shù)越多汇竭，錯(cuò)的越離譜葱蝗，均方差就越大，通過(guò)最小化均方差能夠找到最靠譜的分枝依據(jù)细燎。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一（這太難了）或者達(dá)到預(yù)設(shè)的終止條件（如葉子個(gè)數(shù)上限）两曼，若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測(cè)年齡找颓。若還不明白可以Google?"Regression?Tree"合愈，或閱讀本文的第一篇論文中Regression?Tree部分。

二击狮、?GB：梯度迭代?Gradient?Boosting

好吧佛析，我起了一個(gè)很大的標(biāo)題，但事實(shí)上我并不想多講Gradient?Boosting的原理彪蓬，因?yàn)椴幻靼自聿o(wú)礙于理解GBDT中的Gradient?Boosting寸莫。喜歡打破砂鍋問(wèn)到底的同學(xué)可以閱讀這篇英文wikihttp://en.wikipedia.org/wiki/Gradient_boosted_trees#Gradient_tree_boosting

Boosting，迭代档冬，即通過(guò)迭代多棵樹(shù)來(lái)共同決策膘茎。這怎么實(shí)現(xiàn)呢？難道是每棵樹(shù)獨(dú)立訓(xùn)練一遍酷誓，比如A這個(gè)人披坏，第一棵樹(shù)認(rèn)為是10歲，第二棵樹(shù)認(rèn)為是0歲盐数，第三棵樹(shù)認(rèn)為是20歲棒拂，我們就取平均值10歲做最終結(jié)論？--當(dāng)然不是玫氢！且不說(shuō)這是投票方法并不是GBDT帚屉，只要訓(xùn)練集不變，獨(dú)立訓(xùn)練三次的三棵樹(shù)必定完全相同漾峡，這樣做完全沒(méi)有意義攻旦。之前說(shuō)過(guò)，GBDT是把所有樹(shù)的結(jié)論累加起來(lái)做最終結(jié)論的生逸，所以可以想到每棵樹(shù)的結(jié)論并不是年齡本身牢屋，而是年齡的一個(gè)累加量。GBDT的核心就在于槽袄，每一棵樹(shù)學(xué)的是之前所有樹(shù)結(jié)論和的殘差伟阔，這個(gè)殘差就是一個(gè)加預(yù)測(cè)值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲掰伸，但第一棵樹(shù)的預(yù)測(cè)年齡是12歲，差了6歲怀估，即殘差為6歲狮鸭。那么在第二棵樹(shù)里我們把A的年齡設(shè)為6歲去學(xué)習(xí)合搅，如果第二棵樹(shù)真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹(shù)的結(jié)論就是A的真實(shí)年齡歧蕉；如果第二棵樹(shù)的結(jié)論是5歲灾部，則A仍然存在1歲的殘差，第三棵樹(shù)里A的年齡就變成1歲惯退，繼續(xù)學(xué)赌髓。這就是Gradient?Boosting在GBDT中的意義，簡(jiǎn)單吧催跪。

三锁蠕、?GBDT工作過(guò)程實(shí)例。

還是年齡預(yù)測(cè)懊蒸，簡(jiǎn)單起見(jiàn)訓(xùn)練集只有4個(gè)人荣倾，A,B,C,D，他們的年齡分別是14,16,24,26骑丸。其中A舌仍、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工通危。如果是用一棵傳統(tǒng)的回歸決策樹(shù)來(lái)訓(xùn)練铸豁，會(huì)得到如下圖1所示結(jié)果：

現(xiàn)在我們使用GBDT來(lái)做這件事，由于數(shù)據(jù)太少菊碟，我們限定葉子節(jié)點(diǎn)做多有兩個(gè)节芥，即每棵樹(shù)都只有一個(gè)分枝，并且限定只學(xué)兩棵樹(shù)框沟。我們會(huì)得到如下圖2所示結(jié)果：

在第一棵樹(shù)分枝和圖1一樣藏古，由于A,B年齡較為相近，C,D年齡較為相近忍燥，他們被分為兩撥拧晕，每撥用平均年齡作為預(yù)測(cè)值。此時(shí)計(jì)算殘差（殘差的意思就是：?A的預(yù)測(cè)值?+?A的殘差?=?A的實(shí)際值）梅垄，所以A的殘差就是16-15=1（注意厂捞，A的預(yù)測(cè)值是指前面所有樹(shù)累加的和，這里前面只有一棵樹(shù)所以直接是15队丝，如果還有樹(shù)則需要都累加起來(lái)作為A的預(yù)測(cè)值）靡馁。進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1机久。然后我們拿殘差替代A,B,C,D的原值臭墨，到第二棵樹(shù)去學(xué)習(xí)，如果我們的預(yù)測(cè)值和它們的殘差相等膘盖，則只需把第二棵樹(shù)的結(jié)論累加到第一棵樹(shù)上就能得到真實(shí)年齡了胧弛。這里的數(shù)據(jù)顯然是我可以做的尤误，第二棵樹(shù)只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)结缚。此時(shí)所有人的殘差都是0损晤，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值。

換句話說(shuō)红竭，現(xiàn)在A,B,C,D的預(yù)測(cè)值都和真實(shí)年齡一致了尤勋。Perfect!：

A:?14歲高一學(xué)生，購(gòu)物較少茵宪，經(jīng)常問(wèn)學(xué)長(zhǎng)問(wèn)題最冰；預(yù)測(cè)年齡A?=?15?–?1?=?14

B:?16歲高三學(xué)生；購(gòu)物較少眉厨，經(jīng)常被學(xué)弟問(wèn)問(wèn)題锌奴；預(yù)測(cè)年齡B?=?15?+?1?=?16

C:?24歲應(yīng)屆畢業(yè)生；購(gòu)物較多憾股，經(jīng)常問(wèn)師兄問(wèn)題鹿蜀；預(yù)測(cè)年齡C?=?25?–?1?=?24

D:?26歲工作兩年員工；購(gòu)物較多服球，經(jīng)常被師弟問(wèn)問(wèn)題茴恰；預(yù)測(cè)年齡D?=?25?+?1?=?26

那么哪里體現(xiàn)了Gradient呢？其實(shí)回到第一棵樹(shù)結(jié)束時(shí)想一想斩熊，無(wú)論此時(shí)的cost?function是什么往枣，是均方差還是均差，只要它以誤差作為衡量標(biāo)準(zhǔn)粉渠，殘差向量(-1,?1,?-1,?1)都是它的全局最優(yōu)方向分冈，這就是Gradient。

講到這里我們已經(jīng)把GBDT最核心的概念霸株、運(yùn)算過(guò)程講完了雕沉！沒(méi)錯(cuò)就是這么簡(jiǎn)單。不過(guò)講到這里很容易發(fā)現(xiàn)三個(gè)問(wèn)題：

1）既然圖1和圖2?最終效果相同去件，為何還需要GBDT呢坡椒？

答案是過(guò)擬合。過(guò)擬合是指為了讓訓(xùn)練集精度更高尤溜，學(xué)到了很多”僅在訓(xùn)練集上成立的規(guī)律“倔叼，導(dǎo)致?lián)Q一個(gè)數(shù)據(jù)集當(dāng)前規(guī)律就不適用了。其實(shí)只要允許一棵樹(shù)的葉子節(jié)點(diǎn)足夠多宫莱，訓(xùn)練集總是能訓(xùn)練到100%準(zhǔn)確率的（大不了最后一個(gè)葉子上只有一個(gè)instance)丈攒。在訓(xùn)練精度和實(shí)際精度（或測(cè)試精度）之間，后者才是我們想要真正得到的。

我們發(fā)現(xiàn)圖1為了達(dá)到100%精度使用了3個(gè)feature（上網(wǎng)時(shí)長(zhǎng)巡验、時(shí)段识椰、網(wǎng)購(gòu)金額），其中分枝“上網(wǎng)時(shí)長(zhǎng)>1.1h”?很顯然已經(jīng)過(guò)擬合了深碱，這個(gè)數(shù)據(jù)集上A,B也許恰好A每天上網(wǎng)1.09h,?B上網(wǎng)1.05小時(shí)，但用上網(wǎng)時(shí)間是不是>1.1小時(shí)來(lái)判斷所有人的年齡很顯然是有悖常識(shí)的藏畅；

相對(duì)來(lái)說(shuō)圖2的boosting雖然用了兩棵樹(shù)?敷硅，但其實(shí)只用了2個(gè)feature就搞定了，后一個(gè)feature是問(wèn)答比例愉阎，顯然圖2的依據(jù)更靠譜绞蹦。（當(dāng)然，這里是LZ故意做的數(shù)據(jù)榜旦，所以才能靠譜得如此狗血幽七。實(shí)際中靠譜不靠譜總是相對(duì)的）?Boosting的最大好處在于，每一步的殘差計(jì)算其實(shí)變相地增大了分錯(cuò)instance的權(quán)重溅呢，而已經(jīng)分對(duì)的instance則都趨向于0澡屡。這樣后面的樹(shù)就能越來(lái)越專注那些前面被分錯(cuò)的instance。就像我們做互聯(lián)網(wǎng)咐旧，總是先解決60%用戶的需求湊合著驶鹉，再解決35%用戶的需求，最后才關(guān)注那5%人的需求铣墨，這樣就能逐漸把產(chǎn)品做好室埋，因?yàn)椴煌愋陀脩粜枨罂赡芡耆煌枰謩e獨(dú)立分析伊约。如果反過(guò)來(lái)做姚淆，或者剛上來(lái)就一定要做到盡善盡美，往往最終會(huì)竹籃打水一場(chǎng)空屡律。

2）Gradient呢腌逢？不是“G”BDT么？

到目前為止疹尾，我們的確沒(méi)有用到求導(dǎo)的Gradient上忍。在當(dāng)前版本GBDT描述中，的確沒(méi)有用到Gradient纳本，該版本用殘差作為全局最優(yōu)的絕對(duì)方向窍蓝，并不需要Gradient求解.

3）這不是boosting吧？Adaboost可不是這么定義的繁成。

這是boosting吓笙，但不是Adaboost。GBDT不是Adaboost?Decistion?Tree巾腕。就像提到?jīng)Q策樹(shù)大家會(huì)想起C4.5面睛，提到boost多數(shù)人也會(huì)想到Adaboost絮蒿。Adaboost是另一種boost方法，它按分類對(duì)錯(cuò)叁鉴，分配不同的weight土涝，計(jì)算cost?function時(shí)使用這些weight，從而讓“錯(cuò)分的樣本權(quán)重越來(lái)越大幌墓，使它們更被重視”但壮。Bootstrap也有類似思想，它在每一步迭代時(shí)不改變模型本身常侣，也不計(jì)算殘差蜡饵，而是從N個(gè)instance訓(xùn)練集中按一定概率重新抽取N個(gè)instance出來(lái)（單個(gè)instance可以被重復(fù)sample），對(duì)著這N個(gè)新的instance再訓(xùn)練一輪胳施。由于數(shù)據(jù)集變了迭代模型訓(xùn)練結(jié)果也不一樣溯祸，而一個(gè)instance被前面分錯(cuò)的越厲害，它的概率就被設(shè)的越高舞肆，這樣就能同樣達(dá)到逐步關(guān)注被分錯(cuò)的instance焦辅，逐步完善的效果。Adaboost的方法被實(shí)踐證明是一種很好的防止過(guò)擬合的方法胆绊，但至于為什么則至今沒(méi)從理論上被證明氨鹏。GBDT也可以在使用殘差的同時(shí)引入Bootstrap?re-sampling，GBDT多數(shù)實(shí)現(xiàn)版本中也增加的這個(gè)選項(xiàng)压状，但是否一定使用則有不同看法仆抵。re-sampling一個(gè)缺點(diǎn)是它的隨機(jī)性，即同樣的數(shù)據(jù)集合訓(xùn)練兩遍結(jié)果是不一樣的种冬，也就是模型不可穩(wěn)定復(fù)現(xiàn)镣丑，這對(duì)評(píng)估是很大挑戰(zhàn)，比如很難說(shuō)一個(gè)模型變好是因?yàn)槟氵x用了更好的feature娱两，還是由于這次sample的隨機(jī)因素莺匠。

四、Shrinkage

Shrinkage（縮減）的思想認(rèn)為十兢，每次走一小步逐漸逼近結(jié)果的效果趣竣，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過(guò)擬合。即它不完全信任每一個(gè)棵殘差樹(shù)旱物，它認(rèn)為每棵樹(shù)只學(xué)到了真理的一小部分遥缕，累加的時(shí)候只累加一小部分，通過(guò)多學(xué)幾棵樹(shù)彌補(bǔ)不足宵呛。用方程來(lái)看更清晰单匣，即

沒(méi)用Shrinkage時(shí)：（yi表示第i棵樹(shù)上y的預(yù)測(cè)值，?y(1~i)表示前i棵樹(shù)y的綜合預(yù)測(cè)值）

y(i+1)?=?殘差(y1~yi)，?其中：?殘差(y1~yi)?=??y真實(shí)值?-?y(1?~?i)

y(1?~?i)?=?SUM(y1,?...,?yi)

Shrinkage不改變第一個(gè)方程户秤，只把第二個(gè)方程改為：

y(1?~?i)?=?y(1?~?i-1)?+?step?*?yi

即Shrinkage仍然以殘差作為學(xué)習(xí)目標(biāo)码秉，但對(duì)于殘差學(xué)習(xí)出來(lái)的結(jié)果，只累加一小部分（step*殘差）逐步逼近目標(biāo)鸡号，step一般都比較小转砖，如0.01~0.001（注意該step非gradient的step），導(dǎo)致各個(gè)樹(shù)的殘差是漸變的而不是陡變的鲸伴。直覺(jué)上這也很好理解堪藐，不像直接用殘差一步修復(fù)誤差，而是只修復(fù)一點(diǎn)點(diǎn)挑围，其實(shí)就是把大步切成了很多小步。本質(zhì)上糖荒，Shrinkage為每棵樹(shù)設(shè)置了一個(gè)weight杉辙，累加時(shí)要乘以這個(gè)weight，但和Gradient并沒(méi)有關(guān)系捶朵。這個(gè)weight就是step蜘矢。就像Adaboost一樣，Shrinkage能減少過(guò)擬合發(fā)生也是經(jīng)驗(yàn)證明的综看，目前還沒(méi)有看到從理論的證明品腹。

五、?GBDT的適用范圍

該版本GBDT幾乎可用于所有回歸問(wèn)題（線性/非線性）红碑，相對(duì)logistic?regression僅能用于線性回歸舞吭，GBDT的適用面非常廣。亦可用于二分類問(wèn)題（設(shè)定閾值析珊，大于閾值為正例羡鸥，反之為負(fù)例）。