源于博客

GBRT（梯度提升回歸樹(shù)）有好多名字，標(biāo)題全是它的別名。
它是一種迭代的回歸樹(shù)算法，由多棵回歸樹(shù)組成，所有樹(shù)的結(jié)論累加起來(lái)得到最終結(jié)果。在被提出之初與SVM一起被認(rèn)為是泛化能力較強(qiáng)的算法。
主要由三個(gè)概念組成：回歸決策樹(shù)Regression Decistion Tree（即DT)，梯度提升Gradient Boosting（即GB)，Shrinkage 。搞定這三個(gè)概念后就能明白GBDT是如何工作的，要繼續(xù)理解它如何用于搜索排序則需要額外理解RankNet概念，之后便功德圓滿(mǎn)。下文將逐個(gè)碎片介紹，最終把整張圖拼出來(lái)。

1. DT：回歸樹(shù)Regression Decistion Tree

決策樹(shù)分為兩大類(lèi)：回歸樹(shù)和分類(lèi)樹(shù)，前者用于預(yù)測(cè)實(shí)數(shù)值，如明天的溫度，用戶(hù)年齡，網(wǎng)頁(yè)相關(guān)程度等，后者用于分類(lèi)標(biāo)簽值，如用戶(hù)性別、晴天/陰天/雨、網(wǎng)頁(yè)是否是垃圾頁(yè)面等。注意到前者的結(jié)果的加減是有意義的，后者則無(wú)意義。GBRT的核心在于累加所有樹(shù)的結(jié)果作為最終結(jié)果，對(duì)于分類(lèi)樹(shù)的結(jié)果是無(wú)法累加的，從而，GBDT中的樹(shù)都是回歸樹(shù)，不是分類(lèi)樹(shù)。下面以性別判別/年齡預(yù)測(cè)（每個(gè)例子都是已知性別/年齡的人，而特征包括這個(gè)人上網(wǎng)的時(shí)長(zhǎng)、上網(wǎng)的時(shí)間段、網(wǎng)購(gòu)所花金額等）來(lái)說(shuō)明回歸樹(shù)如何工作：

先說(shuō)一下分類(lèi)樹(shù)，分類(lèi)樹(shù)在每次分枝時(shí)，是窮舉每一個(gè)特征的每一個(gè)閾值，找到使得（閾值<特征）（特征<=閾值）分成的兩個(gè)分枝的熵最大的特征和閾值（熵最大的概念可理解成盡可能每個(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ù)總體流程也是類(lèi)似，不過(guò)在每個(gè)節(jié)點(diǎn)（不一定是葉子節(jié)點(diǎn)）都會(huì)得一個(gè)預(yù)測(cè)值，以年齡為例，該預(yù)測(cè)值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值。分枝時(shí)，是窮舉每一個(gè)特征的每一個(gè)閾值找到最好的分割點(diǎn)，衡量的標(biāo)準(zhǔn)改為最小化均方差（而不是最大熵），即（每個(gè)人的年齡-預(yù)測(cè)年齡）平方和除以n。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一（這太難了）或者達(dá)到預(yù)設(shè)的終止條件（如葉子個(gè)數(shù)上限）。若最終葉子結(jié)點(diǎn)上年齡不唯一，則以該節(jié)點(diǎn)上所有人平均年齡作為預(yù)測(cè)年齡。

2. GB:梯度提升Gradient Boosting

Boosting，迭代，即通過(guò)迭代多棵樹(shù)來(lái)共同決策，每棵樹(shù)的結(jié)論并不是年齡本身，而是年齡的一個(gè)累加量。GBRT的核心就在于，每一棵樹(shù)學(xué)的是之前所有樹(shù)的結(jié)論和的殘差，這個(gè)殘差就是一個(gè)加上預(yù)測(cè)值后能得真實(shí)值的累加量。比如，一個(gè)人的真實(shí)年齡是18歲，但是第一棵樹(shù)預(yù)測(cè)年齡是12歲，差了6歲，殘差為6；那么第二棵樹(shù)我們把其年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹(shù)真的能把其分到6歲的葉子節(jié)點(diǎn)，那么累加兩棵樹(shù)的年齡就是真實(shí)值，如果第二棵樹(shù)的結(jié)論是5歲，仍剩余1歲的殘差，需要繼續(xù)學(xué)習(xí)。

3. Boost與Gradient boost：提升與梯度提升

原始的Boost算法是在算法開(kāi)始的時(shí)候，為每一個(gè)樣本賦上一個(gè)權(quán)重值，初始的時(shí)候，大家都是一樣重要的。在每一步訓(xùn)練中得到的模型，會(huì)使得數(shù)據(jù)點(diǎn)的估計(jì)有對(duì)有錯(cuò)，我們就在每一步結(jié)束后，增加分錯(cuò)的點(diǎn)的權(quán)重，減少分對(duì)的點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老是被分錯(cuò)，那么就會(huì)被“嚴(yán)重關(guān)注”，也就被賦上一個(gè)很高的權(quán)重。然后等進(jìn)行了N次迭代（由用戶(hù)指定），將會(huì)得到N個(gè)簡(jiǎn)單的分類(lèi)器（basic learner），然后我們將它們組合起來(lái)（比如說(shuō)可以對(duì)它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等），得到一個(gè)最終的模型。而Gradient Boost與傳統(tǒng)的Boost的區(qū)別是，每一次的計(jì)算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度(Gradient)方向上建立一個(gè)新的模型。所以說(shuō)，在Gradient Boost中，每個(gè)新的模型的簡(jiǎn)歷是為了使得之前模型的殘差往梯度方向減少，與傳統(tǒng)Boost對(duì)正確、錯(cuò)誤的樣本進(jìn)行加權(quán)有著很大的區(qū)別

4. GBDT工作實(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ù)過(guò)少，限定的葉子結(jié)點(diǎn)最多有兩個(gè)，即每棵樹(shù)都只有一個(gè)分枝，并且限定只學(xué)兩棵樹(shù)，我們會(huì)得到以下結(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è)值。

很容易發(fā)現(xiàn)幾個(gè)問(wèn)題:
1）既然上面兩個(gè)方法最終效果相同，為何還需要GBDT呢？
過(guò)擬合。過(guò)擬合是指為了讓訓(xùn)練集精度更高，學(xué)到了很多“僅在訓(xùn)練集上成立的規(guī)律”，導(dǎo)致?lián)Q一個(gè)數(shù)據(jù)集當(dāng)前規(guī)律就不適應(yīng)了。其實(shí)只要允許一棵樹(shù)的葉子結(jié)點(diǎn)足夠多，訓(xùn)練集總是能夠訓(xùn)練到100%準(zhǔn)確率的。
我們發(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ù)更靠譜。Boosting的最大好處在于，每一步的殘差計(jì)算其實(shí)變相地增大了分錯(cuò)instance的權(quán)重，而已經(jīng)分對(duì)的instance則都趨向于0。這樣后面的樹(shù)就能越來(lái)越專(zhuān)注那些前面被分錯(cuò)的instance。

2）這個(gè)不是boosting吧，Adaboost不是這么定義的
這是boosting不是Adaboost。Adaboost是另一種提升方法，它按分類(lèi)對(duì)錯(cuò)，分配不同的權(quán)重，使用這些權(quán)重計(jì)算cost function，從而讓錯(cuò)分的樣本權(quán)重越來(lái)越大，使他們更被重視。Bootstrap也有類(lèi)似思想，它在每一步迭代時(shí)不改變模型本身，也不計(jì)算殘差，而是從n個(gè)例子訓(xùn)練集中按照一定的概率重新抽取n個(gè)例子出來(lái)，對(duì)這n個(gè)新的例子再訓(xùn)練一輪。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ī)因素。

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

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的GBRT(GBDT)(MART)(Tree Net)(Tree link)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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