來源:GBDT入門教程之原理、所解決的問題疹瘦、應(yīng)用場景講解
2017-04-23 機器學(xué)習(xí)算法與Python學(xué)習(xí)
GBDT (Gradient Boosting Decision Tree) 又叫 MART （Multiple Additive Regression Tree)崩哩，是一種迭代的決策樹算法，該算法由多棵決策樹組成言沐，所有樹的結(jié)論累加起來做最終答案琢锋。它在被提出之初就和SVM一起被認(rèn)為是泛化能力（generalization)較強的算法。近些年更因為被用于搜索排序的機器學(xué)習(xí)模型而引起大家關(guān)注呢灶。

****第1~4節(jié)：GBDT算法內(nèi)部究竟是如何工作的吴超？
第5節(jié)：它可以用于解決哪些問題？
**第6節(jié)：它又是怎樣應(yīng)用于搜索排序的呢鸯乃？ **

在此先給出我比較推薦的兩篇英文文獻鲸阻，喜歡英文原版的同學(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主要由三個概念組成：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是很多棵分類樹拿霉。決策樹分為兩大類，回歸樹和分類樹咱扣。前者用于預(yù)測實數(shù)值绽淘，如明天的溫度、用戶的年齡偏窝、網(wǎng)頁的相關(guān)程度收恢；后者用于分類標(biāo)簽值武学，如晴天/陰天/霧/雨、用戶性別伦意、網(wǎng)頁是否是垃圾頁面火窒。這里要強調(diào)的是，前者的結(jié)果加減是有意義的驮肉，如10歲+5歲-3歲=12歲熏矿，后者則無意義，如男+男+女=到底是男是女离钝？ GBDT的核心在于累加所有樹的結(jié)果作為最終結(jié)果票编，就像前面對年齡的累加（-3是加負(fù)3），而分類樹的結(jié)果顯然是沒辦法累加的卵渴，所以GBDT中的樹都是回歸樹慧域，不是分類樹，這點對理解GBDT相當(dāng)重要（盡管GBDT調(diào)整后也可用于分類但不代表GBDT的樹是分類樹）浪读。那么回歸樹是如何工作的呢昔榴？

下面我們以對人的性別判別/年齡預(yù)測為例來說明，每個instance都是一個我們已知性別/年齡的人碘橘，而feature則包括這個人上網(wǎng)的時長互订、上網(wǎng)的時段、網(wǎng)購所花的金額等痘拆。

作為對比仰禽，先說分類樹，我們知道C4.5分類樹在每次分枝時纺蛆，是窮舉每一個feature的每一個閾值吐葵，找到使得按照feature<=閾值，和feature>閾值分成的兩個分枝的熵最大的feature和閾值（熵最大的概念可理解成盡可能每個分枝的男女比例都遠(yuǎn)離1:1）犹撒，按照該標(biāo)準(zhǔn)分枝得到兩個新節(jié)點折联，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點，或達(dá)到預(yù)設(shè)的終止條件识颊，若最終葉子節(jié)點中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點的性別奕坟。

回歸樹總體流程也是類似祥款，不過在每個節(jié)點（不一定是葉子節(jié)點）都會得一個預(yù)測值，以年齡為例月杉，該預(yù)測值等于屬于這個節(jié)點的所有人年齡的平均值刃跛。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標(biāo)準(zhǔn)不再是最大熵苛萎，而是最小化均方差--即（每個人的年齡-預(yù)測年齡）^2 的總和 / N桨昙，或者說是每個人的預(yù)測誤差平方和 除以 N检号。這很好理解，被預(yù)測出錯的人數(shù)越多蛙酪，錯的越離譜齐苛，均方差就越大，通過最小化均方差能夠找到最靠譜的分枝依據(jù)桂塞。分枝直到每個葉子節(jié)點上人的年齡都唯一（這太難了）或者達(dá)到預(yù)設(shè)的終止條件（如葉子個數(shù)上限）凹蜂，若最終葉子節(jié)點上人的年齡不唯一，則以該節(jié)點上所有人的平均年齡做為該葉子節(jié)點的預(yù)測年齡阁危。若還不明白可以Google "Regression Tree"玛痊，或閱讀本文的第一篇論文中Regression Tree部分。

二狂打、 GB：梯度迭代 Gradient Boosting
好吧擂煞，我起了一個很大的標(biāo)題，但事實上我并不想多講Gradient Boosting的原理趴乡，因為不明白原理并無礙于理解GBDT中的Gradient Boosting颈娜。喜歡打破砂鍋問到底的同學(xué)可以閱讀這篇英文wiki http://en.wikipedia.org/wiki/Gradient_boosted_trees#Gradient_tree_boosting

Boosting，迭代浙宜，即通過迭代多棵樹來共同決策官辽。這怎么實現(xiàn)呢？難道是每棵樹獨立訓(xùn)練一遍粟瞬，比如A這個人同仆，第一棵樹認(rèn)為是10歲，第二棵樹認(rèn)為是0歲裙品，第三棵樹認(rèn)為是20歲俗批，我們就取平均值10歲做最終結(jié)論？--當(dāng)然不是市怎！且不說這是投票方法并不是GBDT岁忘，只要訓(xùn)練集不變，獨立訓(xùn)練三次的三棵樹必定完全相同区匠，這樣做完全沒有意義干像。之前說過，GBDT是把所有樹的結(jié)論累加起來做最終結(jié)論的驰弄，所以可以想到每棵樹的結(jié)論并不是年齡本身麻汰，而是年齡的一個累加量。GBDT的核心就在于戚篙，每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差五鲫，這個殘差就是一個加預(yù)測值后能得真實值的累加量。比如A的真實年齡是18歲岔擂，但第一棵樹的預(yù)測年齡是12歲位喂，差了6歲浪耘，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)塑崖，如果第二棵樹真的能把A分到6歲的葉子節(jié)點七冲，那累加兩棵樹的結(jié)論就是A的真實年齡；如果第二棵樹的結(jié)論是5歲弃舒，則A仍然存在1歲的殘差癞埠，第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)聋呢。這就是Gradient Boosting在GBDT中的意義苗踪，簡單吧。

三削锰、 GBDT工作過程實例通铲。
還是年齡預(yù)測，簡單起見訓(xùn)練集只有4個人器贩，A,B,C,D颅夺，他們的年齡分別是14,16,24,26。其中A蛹稍、B分別是高一和高三學(xué)生吧黄；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。如果是用一棵傳統(tǒng)的回歸決策樹來訓(xùn)練唆姐，會得到如下圖1所示結(jié)果：

現(xiàn)在我們使用GBDT來做這件事拗慨，由于數(shù)據(jù)太少，我們限定葉子節(jié)點做多有兩個奉芦，即每棵樹都只有一個分枝默怨，并且限定只學(xué)兩棵樹善延。我們會得到如下圖2所示結(jié)果：

換句話說徒像，現(xiàn)在A,B,C,D的預(yù)測值都和真實年齡一致了黍特。Perfect!：
A: 14歲高一學(xué)生，購物較少锯蛀，經(jīng)常問學(xué)長問題灭衷；預(yù)測年齡A = 15 – 1 = 14
B: 16歲高三學(xué)生；購物較少旁涤，經(jīng)常被學(xué)弟問問題翔曲；預(yù)測年齡B = 15 + 1 = 16
C: 24歲應(yīng)屆畢業(yè)生；購物較多劈愚，經(jīng)常問師兄問題瞳遍；預(yù)測年齡C = 25 – 1 = 24
D: 26歲工作兩年員工；購物較多菌羽，經(jīng)常被師弟問問題掠械；預(yù)測年齡D = 25 + 1 = 26

那么哪里體現(xiàn)了Gradient呢？其實回到第一棵樹結(jié)束時想一想算凿，無論此時的cost function是什么份蝴，是均方差還是均差，只要它以誤差作為衡量標(biāo)準(zhǔn)氓轰，殘差向量(-1, 1, -1, 1)都是它的全局最優(yōu)方向婚夫，這就是Gradient。

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

1）既然圖1和圖2 最終效果相同靴庆，為何還需要GBDT呢时捌？
答案是過擬合。過擬合是指為了讓訓(xùn)練集精度更高炉抒，學(xué)到了很多”僅在訓(xùn)練集上成立的規(guī)律“奢讨，導(dǎo)致?lián)Q一個數(shù)據(jù)集當(dāng)前規(guī)律就不適用了。其實只要允許一棵樹的葉子節(jié)點足夠多焰薄，訓(xùn)練集總是能訓(xùn)練到100%準(zhǔn)確率的（大不了最后一個葉子上只有一個instance)拿诸。在訓(xùn)練精度和實際精度（或測試精度）之間扒袖，后者才是我們想要真正得到的。

我們發(fā)現(xiàn)圖1為了達(dá)到100%精度使用了3個feature（上網(wǎng)時長亩码、時段季率、網(wǎng)購金額），其中分枝“上網(wǎng)時長>1.1h” 很顯然已經(jīng)過擬合了描沟，這個數(shù)據(jù)集上A,B也許恰好A每天上網(wǎng)1.09h, B上網(wǎng)1.05小時飒泻，但用上網(wǎng)時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的；
相對來說圖2的boosting雖然用了兩棵樹 吏廉，但其實只用了2個feature就搞定了泞遗，后一個feature是問答比例，顯然圖2的依據(jù)更靠譜迟蜜。（當(dāng)然刹孔，這里是LZ故意做的數(shù)據(jù)，所以才能靠譜得如此狗血娜睛。實際中靠譜不靠譜總是相對的） Boosting的最大好處在于髓霞，每一步的殘差計算其實變相地增大了分錯instance的權(quán)重，而已經(jīng)分對的instance則都趨向于0畦戒。這樣后面的樹就能越來越專注那些前面被分錯的instance方库。就像我們做互聯(lián)網(wǎng)，總是先解決60%用戶的需求湊合著障斋，再解決35%用戶的需求纵潦，最后才關(guān)注那5%人的需求，這樣就能逐漸把產(chǎn)品做好垃环，因為不同類型用戶需求可能完全不同邀层，需要分別獨立分析。如果反過來做遂庄，或者剛上來就一定要做到盡善盡美寥院，往往最終會竹籃打水一場空。

2）Gradient呢涛目？不是“G”BDT么秸谢？
到目前為止，我們的確沒有用到求導(dǎo)的Gradient霹肝。在當(dāng)前版本GBDT描述中估蹄，的確沒有用到Gradient，該版本用殘差作為全局最優(yōu)的絕對方向沫换，并不需要Gradient求解.

3）這不是boosting吧臭蚁？Adaboost可不是這么定義的。
這是boosting，但不是Adaboost刊棕。GBDT不是Adaboost Decistion Tree炭晒。就像提到?jīng)Q策樹大家會想起C4.5待逞，提到boost多數(shù)人也會想到Adaboost甥角。Adaboost是另一種boost方法，它按分類對錯识樱，分配不同的weight嗤无，計算cost function時使用這些weight，從而讓“錯分的樣本權(quán)重越來越大怜庸，使它們更被重視”当犯。Bootstrap也有類似思想，它在每一步迭代時不改變模型本身割疾，也不計算殘差嚎卫，而是從N個instance訓(xùn)練集中按一定概率重新抽取N個instance出來（單個instance可以被重復(fù)sample），對著這N個新的instance再訓(xùn)練一輪宏榕。由于數(shù)據(jù)集變了迭代模型訓(xùn)練結(jié)果也不一樣拓诸，而一個instance被前面分錯的越厲害，它的概率就被設(shè)的越高麻昼，這樣就能同樣達(dá)到逐步關(guān)注被分錯的instance奠支，逐步完善的效果。Adaboost的方法被實踐證明是一種很好的防止過擬合的方法抚芦，但至于為什么則至今沒從理論上被證明倍谜。GBDT也可以在使用殘差的同時引入Bootstrap re-sampling，GBDT多數(shù)實現(xiàn)版本中也增加的這個選項叉抡，但是否一定使用則有不同看法尔崔。re-sampling一個缺點是它的隨機性，即同樣的數(shù)據(jù)集合訓(xùn)練兩遍結(jié)果是不一樣的褥民，也就是模型不可穩(wěn)定復(fù)現(xiàn)季春，這對評估是很大挑戰(zhàn)，比如很難說一個模型變好是因為你選用了更好的feature轴捎，還是由于這次sample的隨機因素鹤盒。

**四、Shrinkage **
Shrinkage（縮減）的思想認(rèn)為侦副，每次走一小步逐漸逼近結(jié)果的效果侦锯，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過擬合。即它不完全信任每一個棵殘差樹秦驯，它認(rèn)為每棵樹只學(xué)到了真理的一小部分尺碰，累加的時候只累加一小部分，通過多學(xué)幾棵樹彌補不足。用方程來看更清晰亲桥，即
沒用Shrinkage時：（yi表示第i棵樹上y的預(yù)測值洛心， y(1~i)表示前i棵樹y的綜合預(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仍然以殘差作為學(xué)習(xí)目標(biāo)词身，但對于殘差學(xué)習(xí)出來的結(jié)果，只累加一小部分（step殘差）逐步逼近目標(biāo)番枚，step一般都比較小法严，如0.01~0.001（注意該step非gradient的step），導(dǎo)致各個樹的殘差是漸變的而不是陡變的葫笼。直覺上這也很好理解深啤，不像直接用殘差一步修復(fù)誤差，而是只修復(fù)一點點路星，其實就是把大步切成了很多小步溯街。本質(zhì)上，Shrinkage為每棵樹設(shè)置了一個weight洋丐，累加時要乘以這個weight呈昔，但和Gradient并沒有關(guān)系。*這個weight就是step垫挨。就像Adaboost一樣韩肝，Shrinkage能減少過擬合發(fā)生也是經(jīng)驗證明的，目前還沒有看到從理論的證明九榔。

五哀峻、 GBDT的適用范圍
該版本GBDT幾乎可用于所有回歸問題（線性/非線性），相對logistic regression僅能用于線性回歸哲泊，GBDT的適用面非常廣剩蟀。亦可用于二分類問題（設(shè)定閾值，大于閾值為正例切威，反之為負(fù)例）育特。

六、 搜索引擎排序應(yīng)用 RankNet
搜索排序關(guān)注各個doc的順序而不是絕對值先朦，所以需要一個新的cost function缰冤，而RankNet基本就是在定義這個cost function，它可以兼容不同的算法（GBDT喳魏、神經(jīng)網(wǎng)絡(luò)...）棉浸。

實際的搜索排序使用的是LambdaMART算法，必須指出的是由于這里要使用排序需要的cost function刺彩，LambdaMART迭代用的并不是殘差迷郑。Lambda在這里充當(dāng)替代殘差的計算方法枝恋，它使用了一種類似Gradient*步長模擬殘差的方法。

就像所有的機器學(xué)習(xí)一樣嗡害，搜索排序的學(xué)習(xí)也需要訓(xùn)練集焚碌，這里一般是用人工標(biāo)注實現(xiàn)，即對每一個(query,doc) pair給定一個分值（如1,2,3,4）,分值越高表示越相關(guān)霸妹，越應(yīng)該排到前面十电。然而這些絕對的分值本身意義不大，例如你很難說1分和2分文檔的相關(guān)程度差異是1分和3分文檔差距的一半抑堡。相關(guān)度本身就是一個很主觀的評判摆出，標(biāo)注人員無法做到這種定量標(biāo)注，這種標(biāo)準(zhǔn)也無法制定首妖。但標(biāo)注人員很容易做到的是”AB都不錯，但文檔A比文檔B更相關(guān)爷恳，所以A是4分有缆，B是3分“。RankNet就是基于此制定了一個學(xué)習(xí)誤差衡量方法温亲，即cost function棚壁。具體而言，RankNet對任意兩個文檔A,B栈虚，通過它們的人工標(biāo)注分差袖外，用sigmoid函數(shù)估計兩者順序和逆序的概率P1。然后同理用機器學(xué)習(xí)到的分差計算概率P2（sigmoid的好處在于它允許機器學(xué)習(xí)得到的分值是任意實數(shù)值魂务，只要它們的分差和標(biāo)準(zhǔn)分的分差一致曼验，P2就趨近于P1）。這時利用P1和P2求的兩者的交叉熵粘姜，該交叉熵就是cost function鬓照。它越低說明機器學(xué)得的當(dāng)前排序越趨近于標(biāo)注排序。為了體現(xiàn)NDCG的作用（NDCG是搜索排序業(yè)界最常用的評判標(biāo)準(zhǔn)）孤紧，RankNet還在cost function中乘以了NDCG豺裆。

好，現(xiàn)在我們有了cost function号显，而且它是和各個文檔的當(dāng)前分值yi相關(guān)的臭猜，那么雖然我們不知道它的全局最優(yōu)方向，但可以求導(dǎo)求Gradient押蚤，Gradient即每個文檔得分的一個下降方向組成的N維向量蔑歌，N為文檔個數(shù)（應(yīng)該說是query-doc pair個數(shù)）。這里僅僅是把”求殘差“的邏輯替換為”求梯度“活喊，可以這樣想：梯度方向為每一步最優(yōu)方向丐膝，累加的步數(shù)多了量愧，總能走到局部最優(yōu)點，若該點恰好為全局最優(yōu)點帅矗，那和用殘差的效果是一樣的偎肃。這時套到之前講的邏輯，GDBT就已經(jīng)可以上了浑此。那么最終排序怎么產(chǎn)生呢累颂？很簡單，每個樣本通過Shrinkage累加都會得到一個最終得分凛俱，直接按分?jǐn)?shù)從大到小排序就可以了（因為機器學(xué)習(xí)產(chǎn)生的是實數(shù)域的預(yù)測分紊馏，極少會出現(xiàn)在人工標(biāo)注中常見的兩文檔分?jǐn)?shù)相等的情況，幾乎不同考慮同分文檔的排序方式）

另外蒲犬，如果feature個數(shù)太多朱监，每一棵回歸樹都要耗費大量時間，這時每個分支時可以隨機抽一部分feature來遍歷求最優(yōu)（ELF源碼實現(xiàn)方式）http://elf-project.sourceforge.net/