from:https://www.cnblogs.com/peizhe123/p/5086128.html

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

?

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

?

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

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

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

?

一、?DT：回歸樹?Regression?Decision?Tree

提起決策樹（DT,?Decision?Tree)?絕大部分人首先想到的就是C4.5分類決策樹。但如果一開始就把GBDT中的樹想成分類樹，那就是一條歪路走到黑，一路各種坑，最終摔得都要咯血了還是一頭霧水說的就是LZ自己啊有木有?？揉?#xff0c;所以說千萬不要以為GBDT是很多棵分類樹。決策樹分為兩大類，回歸樹和分類樹。前者用于預(yù)測實(shí)數(shù)值，如明天的溫度、用戶的年齡、網(wǎng)頁的相關(guān)程度；后者用于分類標(biāo)簽值，如晴天/陰天/霧/雨、用戶性別、網(wǎng)頁是否是垃圾頁面。這里要強(qiáng)調(diào)的是，前者的結(jié)果加減是有意義的，如10歲+5歲-3歲=12歲，后者則無意義，如男+男+女=到底是男是女？?GBDT的核心在于累加所有樹的結(jié)果作為最終結(jié)果，就像前面對年齡的累加（-3是加負(fù)3），而分類樹的結(jié)果顯然是沒辦法累加的，所以GBDT中的樹都是回歸樹，不是分類樹，這點(diǎn)對理解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é)點(diǎn)，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點(diǎn)，或達(dá)到預(yù)設(shè)的終止條件，若最終葉子節(jié)點(diǎn)中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點(diǎn)的性別。

?

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

?

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

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

?

Boosting，迭代，即通過迭代多棵樹來共同決策。這怎么實(shí)現(xiàn)呢？難道是每棵樹獨(dú)立訓(xùn)練一遍，比如A這個人，第一棵樹認(rèn)為是10歲，第二棵樹認(rèn)為是0歲，第三棵樹認(rèn)為是20歲，我們就取平均值10歲做最終結(jié)論？--當(dāng)然不是！且不說這是投票方法并不是GBDT，只要訓(xùn)練集不變，獨(dú)立訓(xùn)練三次的三棵樹必定完全相同，這樣做完全沒有意義。之前說過，GBDT是把所有樹的結(jié)論累加起來做最終結(jié)論的，所以可以想到每棵樹的結(jié)論并不是年齡本身，而是年齡的一個累加量。GBDT的核心就在于，每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差，這個殘差就是一個加預(yù)測值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，但第一棵樹的預(yù)測年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹的結(jié)論就是A的真實(shí)年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)。這就是Gradient?Boosting在GBDT中的意義，簡單吧。

?

三、?GBDT工作過程實(shí)例。

還是年齡預(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é)點(diǎn)做多有兩個，即每棵樹都只有一個分枝，并且限定只學(xué)兩棵樹。我們會得到如下圖2所示結(jié)果：

?

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

?

換句話說，現(xiàn)在A,B,C,D的預(yù)測值都和真實(shí)年齡一致了。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呢？其實(shí)回到第一棵樹結(jié)束時想一想，無論此時的cost?function是什么，是均方差還是均差，只要它以誤差作為衡量標(biāo)準(zhǔn)，殘差向量(-1,?1,?-1,?1)都是它的全局最優(yōu)方向，這就是Gradient。

?

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

?

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

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

我們發(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雖然用了兩棵樹?，但其實(shí)只用了2個feature就搞定了，后一個feature是問答比例，顯然圖2的依據(jù)更靠譜。（當(dāng)然，這里是LZ故意做的數(shù)據(jù)，所以才能靠譜得如此狗血。實(shí)際中靠譜不靠譜總是相對的）?Boosting的最大好處在于，每一步的殘差計(jì)算其實(shí)變相地增大了分錯instance的權(quán)重，而已經(jīng)分對的instance則都趨向于0。這樣后面的樹就能越來越專注那些前面被分錯的instance。就像我們做互聯(lián)網(wǎng)，總是先解決60%用戶的需求湊合著，再解決35%用戶的需求，最后才關(guān)注那5%人的需求，這樣就能逐漸把產(chǎn)品做好，因?yàn)椴煌愋陀脩粜枨罂赡芡耆煌?#xff0c;需要分別獨(dú)立分析。如果反過來做，或者剛上來就一定要做到盡善盡美，往往最終會竹籃打水一場空。

?

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，計(jì)算cost?function時使用這些weight，從而讓“錯分的樣本權(quán)重越來越大，使它們更被重視”。Bootstrap也有類似思想，它在每一步迭代時不改變模型本身，也不計(jì)算殘差，而是從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的方法被實(shí)踐證明是一種很好的防止過擬合的方法，但至于為什么則至今沒從理論上被證明。GBDT也可以在使用殘差的同時引入Bootstrap?re-sampling，GBDT多數(shù)實(shí)現(xiàn)版本中也增加的這個選項(xiàng)，但是否一定使用則有不同看法。re-sampling一個缺點(diǎn)是它的隨機(jī)性，即同樣的數(shù)據(jù)集合訓(xùn)練兩遍結(jié)果是不一樣的，也就是模型不可穩(wěn)定復(fù)現(xiàn)，這對評估是很大挑戰(zhàn)，比如很難說一個模型變好是因?yàn)槟氵x用了更好的feature，還是由于這次sample的隨機(jī)因素。

?

?

四、Shrinkage?

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

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

y(i+1)?=?殘差(y1~yi)，?其中：?殘差(y1~yi)?=??y真實(shí)值?-?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ù)一點(diǎn)點(diǎn)，其實(shí)就是把大步切成了很多小步。本質(zhì)上，Shrinkage為每棵樹設(shè)置了一個weight，累加時要乘以這個weight，但和Gradient并沒有關(guān)系。這個weight就是step。就像Adaboost一樣，Shrinkage能減少過擬合發(fā)生也是經(jīng)驗(yàn)證明的，目前還沒有看到從理論的證明。

?

五、?GBDT的適用范圍

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

?

六、?搜索引擎排序應(yīng)用?RankNet

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

?

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

?

就像所有的機(jī)器學(xué)習(xí)一樣，搜索排序的學(xué)習(xí)也需要訓(xùn)練集，這里一般是用人工標(biāo)注實(shí)現(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ù)估計(jì)兩者順序和逆序的概率P1。然后同理用機(jī)器學(xué)習(xí)到的分差計(jì)算概率P2（sigmoid的好處在于它允許機(jī)器學(xué)習(xí)得到的分值是任意實(shí)數(shù)值，只要它們的分差和標(biāo)準(zhǔn)分的分差一致，P2就趨近于P1）。這時利用P1和P2求的兩者的交叉熵，該交叉熵就是cost?function。它越低說明機(jī)器學(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àn)槊恳徊阶顑?yōu)方向，累加的步數(shù)多了，總能走到局部最優(yōu)點(diǎn)，若該點(diǎn)恰好為全局最優(yōu)點(diǎn)，那和用殘差的效果是一樣的。這時套到之前講的邏輯，GDBT就已經(jīng)可以上了。那么最終排序怎么產(chǎn)生呢？很簡單，每個樣本通過Shrinkage累加都會得到一個最終得分，直接按分?jǐn)?shù)從大到小排序就可以了（因?yàn)闄C(jī)器學(xué)習(xí)產(chǎn)生的是實(shí)數(shù)域的預(yù)測分，極少會出現(xiàn)在人工標(biāo)注中常見的兩文檔分?jǐn)?shù)相等的情況，幾乎不同考慮同分文檔的排序方式）

?

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

轉(zhuǎn)載于:https://www.cnblogs.com/Arborday/p/10912543.html

總結(jié)

以上是生活随笔為你收集整理的[转] GDBT详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。