GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹算法瓦堵，該算法由多棵決策樹組成，所有樹的結論累加起來做最終答案。它在被提出之初就和SVM一起被認為是泛化能力（generalization)較強的算法。近些年更因為被用于搜索排序的機器學習模型而引起大家關注控漠。

后記：發(fā)現(xiàn)GBDT除了我描述的殘差版本外還有另一種GBDT描述，兩者大概相同客蹋，但求解方法（Gradient應用）不同。其區(qū)別和另一版本的介紹鏈接見這里孽江。由于另一版本介紹博客中亦有不少錯誤讶坯，建議大家還是先看本篇，再跳到另一版本描述岗屏，這個順序當能兩版本都看懂辆琅。

****第1~4節(jié)：GBDT算法內部究竟是如何工作的？
第5節(jié)：它可以用于解決哪些問題这刷？
**第6節(jié)：它又是怎樣應用于搜索排序的呢婉烟？ **

在此先給出我比較推薦的兩篇英文文獻，喜歡英文原版的同學可直接閱讀：
【1】Boosting Decision Tree入門教程
【2】LambdaMART用于搜索排序入門教程

GBDT主要由三個概念組成：Regression Decistion Tree（即DT)崭歧，Gradient Boosting（即GB)隅很，Shrinkage (算法的一個重要演進分枝，目前大部分源碼都按該版本實現(xiàn)）率碾。搞定這三個概念后就能明白GBDT是如何工作的叔营，要繼續(xù)理解它如何用于搜索排序則需要額外理解RankNet概念，之后便功德圓滿所宰。下文將逐個碎片介紹贮缅，最終把整張圖拼出來医增。

一、 DT：回歸樹 Regression Decision Tree
提起決策樹（DT, Decision Tree) 絕大部分人首先想到的就是C4.5分類決策樹。但如果一開始就把GBDT中的樹想成分類樹析砸，那就是一條歪路走到黑代虾，一路各種坑栈戳，最終摔得都要咯血了還是一頭霧水說的就是LZ自己啊有木有安聘。咳嗯麦向，所以說千萬不要以為GBDT是很多棵分類樹瘟裸。決策樹分為兩大類，回歸樹和分類樹诵竭。前者用于預測實數(shù)值话告，如明天的溫度、用戶的年齡卵慰、網頁的相關程度沙郭；后者用于分類標簽值，如晴天/陰天/霧/雨裳朋、用戶性別病线、網頁是否是垃圾頁面。這里要強調的是，前者的結果加減是有意義的送挑，如10歲+5歲-3歲=12歲夜矗，后者則無意義，如男+男+女=到底是男是女让虐？ GBDT的核心在于累加所有樹的結果作為最終結果，就像前面對年齡的累加（-3是加負3）罢荡，而分類樹的結果顯然是沒辦法累加的赡突，所以GBDT中的樹都是回歸樹，不是分類樹区赵，這點對理解GBDT相當重要（盡管GBDT調整后也可用于分類但不代表GBDT的樹是分類樹）惭缰。那么回歸樹是如何工作的呢？

下面我們以對人的性別判別/年齡預測為例來說明笼才，每個instance都是一個我們已知性別/年齡的人漱受，而feature則包括這個人上網的時長、上網的時段骡送、網購所花的金額等昂羡。

作為對比，先說分類樹摔踱，我們知道C4.5分類樹在每次分枝時虐先，是窮舉每一個feature的每一個閾值，找到使得按照feature<=閾值派敷，和feature>閾值分成的兩個分枝的熵最大的feature和閾值（熵最大的概念可理解成盡可能每個分枝的男女比例都遠離1:1）蛹批，按照該標準分枝得到兩個新節(jié)點，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點篮愉，或達到預設的終止條件腐芍，若最終葉子節(jié)點中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點的性別试躏。

回歸樹總體流程也是類似猪勇，不過在每個節(jié)點（不一定是葉子節(jié)點）都會得一個預測值，以年齡為例冗酿，該預測值等于屬于這個節(jié)點的所有人年齡的平均值埠对。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標準不再是最大熵裁替，而是最小化均方差--即（每個人的年齡-預測年齡）^2 的總和 / N项玛，或者說是每個人的預測誤差平方和 除以 N。這很好理解弱判，被預測出錯的人數(shù)越多襟沮，錯的越離譜，均方差就越大，通過最小化均方差能夠找到最靠譜的分枝依據开伏。分枝直到每個葉子節(jié)點上人的年齡都唯一（這太難了）或者達到預設的終止條件（如葉子個數(shù)上限）膀跌，若最終葉子節(jié)點上人的年齡不唯一，則以該節(jié)點上所有人的平均年齡做為該葉子節(jié)點的預測年齡固灵。若還不明白可以Google "Regression Tree"捅伤，或閱讀本文的第一篇論文中Regression Tree部分。

二巫玻、 GB：梯度迭代 Gradient Boosting
好吧丛忆，我起了一個很大的標題，但事實上我并不想多講Gradient Boosting的原理仍秤，因為不明白原理并無礙于理解GBDT中的Gradient Boosting熄诡。喜歡打破砂鍋問到底的同學可以閱讀這篇英文wiki

Boosting，迭代诗力，即通過迭代多棵樹來共同決策凰浮。這怎么實現(xiàn)呢？難道是每棵樹獨立訓練一遍苇本，比如A這個人袜茧，第一棵樹認為是10歲，第二棵樹認為是0歲圈澈，第三棵樹認為是20歲惫周，我們就取平均值10歲做最終結論？--當然不是康栈！且不說這是投票方法并不是GBDT递递，只要訓練集不變，獨立訓練三次的三棵樹必定完全相同啥么，這樣做完全沒有意義登舞。之前說過，GBDT是把所有樹的結論累加起來做最終結論的悬荣，所以可以想到每棵樹的結論并不是年齡本身菠秒，而是年齡的一個累加量。GBDT的核心就在于氯迂，每一棵樹學的是之前所有樹結論和的殘差践叠，這個殘差就是一個加預測值后能得真實值的累加量。比如A的真實年齡是18歲嚼蚀，但第一棵樹的預測年齡是12歲禁灼，差了6歲，即殘差為6歲轿曙。那么在第二棵樹里我們把A的年齡設為6歲去學習弄捕，如果第二棵樹真的能把A分到6歲的葉子節(jié)點僻孝，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲守谓，則A仍然存在1歲的殘差穿铆，第三棵樹里A的年齡就變成1歲，繼續(xù)學斋荞。這就是Gradient Boosting在GBDT中的意義荞雏，簡單吧。

三平酿、 GBDT工作過程實例讯檐。
還是年齡預測，簡單起見訓練集只有4個人染服，A,B,C,D，他們的年齡分別是14,16,24,26叨恨。其中A柳刮、B分別是高一和高三學生；C,D分別是應屆畢業(yè)生和工作兩年的員工痒钝。如果是用一棵傳統(tǒng)的回歸決策樹來訓練秉颗，會得到如下圖1所示結果：

現(xiàn)在我們使用GBDT來做這件事，由于數(shù)據太少送矩，我們限定葉子節(jié)點做多有兩個蚕甥，即每棵樹都只有一個分枝，并且限定只學兩棵樹栋荸。我們會得到如下圖2所示結果：

換句話說瓶殃，現(xiàn)在A,B,C,D的預測值都和真實年齡一致了充包。Perfect!：
A: 14歲高一學生，購物較少遥椿，經常問學長問題基矮；預測年齡A = 15 – 1 = 14
B: 16歲高三學生；購物較少冠场，經常被學弟問問題家浇；預測年齡B = 15 + 1 = 16
C: 24歲應屆畢業(yè)生；購物較多碴裙，經常問師兄問題钢悲；預測年齡C = 25 – 1 = 24
D: 26歲工作兩年員工；購物較多舔株，經常被師弟問問題莺琳；預測年齡D = 25 + 1 = 26

那么哪里體現(xiàn)了Gradient呢？其實回到第一棵樹結束時想一想载慈，無論此時的cost function是什么惭等，是均方差還是均差，只要它以誤差作為衡量標準办铡，殘差向量(-1, 1, -1, 1)都是它的全局最優(yōu)方向辞做，這就是Gradient。

講到這里我們已經把GBDT最核心的概念寡具、運算過程講完了凭豪！沒錯就是這么簡單。不過講到這里很容易發(fā)現(xiàn)三個問題：

1）既然圖1和圖2 最終效果相同晒杈，為何還需要GBDT呢嫂伞？
答案是過擬合。過擬合是指為了讓訓練集精度更高拯钻，學到了很多”僅在訓練集上成立的規(guī)律“帖努，導致?lián)Q一個數(shù)據集當前規(guī)律就不適用了。其實只要允許一棵樹的葉子節(jié)點足夠多粪般，訓練集總是能訓練到100%準確率的（大不了最后一個葉子上只有一個instance)拼余。在訓練精度和實際精度（或測試精度）之間，后者才是我們想要真正得到的亩歹。
我們發(fā)現(xiàn)圖1為了達到100%精度使用了3個feature（上網時長匙监、時段凡橱、網購金額），其中分枝“上網時長>1.1h” 很顯然已經過擬合了亭姥，這個數(shù)據集上A,B也許恰好A每天上網1.09h, B上網1.05小時稼钩，但用上網時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的；
相對來說圖2的boosting雖然用了兩棵樹 达罗，但其實只用了2個feature就搞定了坝撑，后一個feature是問答比例，顯然圖2的依據更靠譜粮揉。（當然巡李，這里是LZ故意做的數(shù)據，所以才能靠譜得如此狗血扶认。實際中靠譜不靠譜總是相對的） Boosting的最大好處在于侨拦，每一步的殘差計算其實變相地增大了分錯instance的權重，而已經分對的instance則都趨向于0辐宾。這樣后面的樹就能越來越專注那些前面被分錯的instance阳谍。就像我們做互聯(lián)網，總是先解決60%用戶的需求湊合著螃概，再解決35%用戶的需求，最后才關注那5%人的需求鸽疾，這樣就能逐漸把產品做好吊洼，因為不同類型用戶需求可能完全不同，需要分別獨立分析制肮。如果反過來做冒窍，或者剛上來就一定要做到盡善盡美，往往最終會竹籃打水一場空豺鼻。

2）Gradient呢综液？不是“G”BDT么？
到目前為止儒飒，我們的確沒有用到求導的Gradient谬莹。在當前版本GBDT描述中，的確沒有用到Gradient桩了，該版本用殘差作為全局最優(yōu)的絕對方向附帽，并不需要Gradient求解.

3）這不是boosting吧？Adaboost可不是這么定義的井誉。
這是boosting蕉扮，但不是Adaboost。GBDT不是Adaboost Decistion Tree颗圣。就像提到決策樹大家會想起C4.5喳钟，提到boost多數(shù)人也會想到Adaboost屁使。Adaboost是另一種boost方法，它按分類對錯奔则，分配不同的weight蛮寂，計算cost function時使用這些weight，從而讓“錯分的樣本權重越來越大应狱，使它們更被重視”共郭。Bootstrap也有類似思想，它在每一步迭代時不改變模型本身疾呻，也不計算殘差除嘹，而是從N個instance訓練集中按一定概率重新抽取N個instance出來（單個instance可以被重復sample），對著這N個新的instance再訓練一輪岸蜗。由于數(shù)據集變了迭代模型訓練結果也不一樣尉咕，而一個instance被前面分錯的越厲害，它的概率就被設的越高璃岳，這樣就能同樣達到逐步關注被分錯的instance年缎，逐步完善的效果。Adaboost的方法被實踐證明是一種很好的防止過擬合的方法铃慷，但至于為什么則至今沒從理論上被證明单芜。GBDT也可以在使用殘差的同時引入Bootstrap re-sampling，GBDT多數(shù)實現(xiàn)版本中也增加的這個選項犁柜，但是否一定使用則有不同看法洲鸠。re-sampling一個缺點是它的隨機性，即同樣的數(shù)據集合訓練兩遍結果是不一樣的馋缅，也就是模型不可穩(wěn)定復現(xiàn)扒腕，這對評估是很大挑戰(zhàn)，比如很難說一個模型變好是因為你選用了更好的feature萤悴，還是由于這次sample的隨機因素瘾腰。

**四、Shrinkage **
Shrinkage（縮減）的思想認為覆履，每次走一小步逐漸逼近結果的效果蹋盆，要比每次邁一大步很快逼近結果的方式更容易避免過擬合。即它不完全信任每一個棵殘差樹硝全，它認為每棵樹只學到了真理的一小部分怪嫌，累加的時候只累加一小部分，通過多學幾棵樹彌補不足柳沙。用方程來看更清晰岩灭，即
沒用Shrinkage時：（yi表示第i棵樹上y的預測值， y(1~i)表示前i棵樹y的綜合預測值）
y(i+1) = 殘差(y1~yi)赂鲤， 其中： 殘差(y1~yi) = y真實值 - y(1 ~ i)
y(1 ~ i) = SUM(y1, ..., yi)
Shrinkage不改變第一個方程噪径，只把第二個方程改為：
y(1 ~ i) = y(1 ~ i-1) + step * yi

即Shrinkage仍然以殘差作為學習目標柱恤，但對于殘差學習出來的結果，只累加一小部分（step殘差）逐步逼近目標找爱，step一般都比較小梗顺，如0.01~0.001（注意該step非gradient的step），導致各個樹的殘差是漸變的而不是陡變的车摄。直覺上這也很好理解寺谤，不像直接用殘差一步修復誤差，而是只修復一點點吮播，其實就是把大步切成了很多小步变屁。本質上，Shrinkage為每棵樹設置了一個weight意狠，累加時要乘以這個weight粟关，但和Gradient并沒有關系。*這個weight就是step环戈。就像Adaboost一樣闷板，Shrinkage能減少過擬合發(fā)生也是經驗證明的，目前還沒有看到從理論的證明院塞。

五遮晚、 GBDT的適用范圍
該版本GBDT幾乎可用于所有回歸問題（線性/非線性），相對logistic regression僅能用于線性回歸拦止，GBDT的適用面非常廣县遣。亦可用于二分類問題（設定閾值，大于閾值為正例创泄，反之為負例）。

六括蝠、 搜索引擎排序應用 RankNet
搜索排序關注各個doc的順序而不是絕對值鞠抑，所以需要一個新的cost function，而RankNet基本就是在定義這個cost function忌警，它可以兼容不同的算法（GBDT搁拙、神經網絡...）。

實際的搜索排序使用的是LambdaMART算法法绵，必須指出的是由于這里要使用排序需要的cost function箕速，LambdaMART迭代用的并不是殘差。Lambda在這里充當替代殘差的計算方法朋譬，它使用了一種類似Gradient*步長模擬殘差的方法盐茎。這里的MART在求解方法上和之前說的殘差略有不同，其區(qū)別描述見這里徙赢。

就像所有的機器學習一樣字柠，搜索排序的學習也需要訓練集探越，這里一般是用人工標注實現(xiàn)，即對每一個(query,doc) pair給定一個分值（如1,2,3,4）,分值越高表示越相關窑业，越應該排到前面钦幔。然而這些絕對的分值本身意義不大，例如你很難說1分和2分文檔的相關程度差異是1分和3分文檔差距的一半常柄。相關度本身就是一個很主觀的評判鲤氢，標注人員無法做到這種定量標注，這種標準也無法制定西潘。但標注人員很容易做到的是”AB都不錯卷玉，但文檔A比文檔B更相關，所以A是4分秸架，B是3分“揍庄。RankNet就是基于此制定了一個學習誤差衡量方法，即cost function东抹。具體而言蚂子，RankNet對任意兩個文檔A,B，通過它們的人工標注分差缭黔，用sigmoid函數(shù)估計兩者順序和逆序的概率P1食茎。然后同理用機器學習到的分差計算概率P2（sigmoid的好處在于它允許機器學習得到的分值是任意實數(shù)值，只要它們的分差和標準分的分差一致馏谨，P2就趨近于P1）别渔。這時利用P1和P2求的兩者的交叉熵，該交叉熵就是cost function惧互。它越低說明機器學得的當前排序越趨近于標注排序哎媚。為了體現(xiàn)NDCG的作用（NDCG是搜索排序業(yè)界最常用的評判標準），RankNet還在cost function中乘以了NDCG喊儡。

好拨与，現(xiàn)在我們有了cost function，而且它是和各個文檔的當前分值yi相關的艾猜，那么雖然我們不知道它的全局最優(yōu)方向买喧，但可以求導求Gradient，Gradient即每個文檔得分的一個下降方向組成的N維向量匆赃，N為文檔個數(shù)（應該說是query-doc pair個數(shù)）淤毛。這里僅僅是把”求殘差“的邏輯替換為”求梯度“，可以這樣想：梯度方向為每一步最優(yōu)方向算柳，累加的步數(shù)多了低淡，總能走到局部最優(yōu)點，若該點恰好為全局最優(yōu)點，那和用殘差的效果是一樣的查牌。這時套到之前講的邏輯事期，GDBT就已經可以上了。那么最終排序怎么產生呢纸颜？很簡單兽泣，每個樣本通過Shrinkage累加都會得到一個最終得分，直接按分數(shù)從大到小排序就可以了（因為機器學習產生的是實數(shù)域的預測分胁孙，極少會出現(xiàn)在人工標注中常見的兩文檔分數(shù)相等的情況唠倦，幾乎不同考慮同分文檔的排序方式）

另外，如果feature個數(shù)太多涮较，每一棵回歸樹都要耗費大量時間稠鼻，這時每個分支時可以隨機抽一部分feature來遍歷求最優(yōu)（ELF源碼實現(xiàn)方式）。