[機(jī)器學(xué)習(xí)] Boosting算法1 --- AdaBoost

[機(jī)器學(xué)習(xí)] Boosting算法2 --- GBDT

[機(jī)器學(xué)習(xí)] Boosting算法3 --- XGBoost

[機(jī)器學(xué)習(xí)] Boosting算法4 --- LightGBM

目錄

GBDT(Gradient Boosting Decision Tree) 梯度提升決策樹算法

1. DT：回歸樹 Regression Decision Tree

2. GB：梯度迭代 Gradient Boosting

3. Gradient Boosting Decision Tree：梯度提升決策樹

前向分布算法(Forward stagewise additive modeling)

加法模型（additive model）

4. Shrinkage

GBDT的適用范圍

---

GBDT(Gradient Boosting Decision Tree) 梯度提升決策樹算法

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一種迭代的決策樹算法，該算法由多棵決策樹組成，所有樹的結(jié)論累加起來做最終答案。它在被提出之初就和SVM一起被認(rèn)為是泛化能力較強(qiáng)的算法。

GBDT是一種基于boosting集成學(xué)習(xí)（ensemble method）的算法，但和傳統(tǒng)的Adaboost有很大不同。在Adaboost，我們是利用前一輪迭代弱學(xué)習(xí)器的誤差率來更新訓(xùn)練集的權(quán)重，這樣一輪輪的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱學(xué)習(xí)器限定了只能使用CART回歸樹模型，同時迭代思路和Adaboost也有所不同。GBDT的訓(xùn)練過程如下：?

?

GBDT中的樹是回歸樹（不是分類樹），GBDT用來做回歸預(yù)測，調(diào)整后也可以用于分類。

GBDT主要由三個概念組成：

Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage (算法的一個重要演進(jìn)分枝，目前大部分源碼都按該版本實(shí)現(xiàn)）。搞定這三個概念后就能明白GBDT是如何工作的。

1. DT：回歸樹 Regression Decision Tree

提起決策樹（DT, Decision Tree) 絕大部分人首先想到的就是C4.5分類決策樹。但如果一開始就把GBDT中的樹想成分類樹，那就錯了。千萬不要以為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的樹是分類樹）。

回歸樹總體流程類似于分類樹，區(qū)別在于，回歸樹的每一個節(jié)點(diǎn)都會得一個預(yù)測值，以年齡為例，該預(yù)測值等于屬于這個節(jié)點(diǎn)的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化平方誤差。也就是被預(yù)測出錯的人數(shù)越多，錯的越離譜，平方誤差就越大，通過最小化平方誤差能夠找到最可靠的分枝依據(jù)。分枝直到每個葉子節(jié)點(diǎn)上人的年齡都唯一或者達(dá)到預(yù)設(shè)的終止條件(如葉子個數(shù)上限)，若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測年齡。

?

回歸樹算法如下圖（截圖來自《統(tǒng)計(jì)學(xué)習(xí)方法》5.5.1 CART生成）：

?

?

2. GB：梯度迭代 Gradient Boosting

梯度提升（Gradient boosting）是一種用于回歸、分類和排序任務(wù)的機(jī)器學(xué)習(xí)技術(shù)，屬于Boosting算法族的一部分。Boosting是一族可將弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的算法，屬于集成學(xué)習(xí)（ensemble learning）的范疇。Boosting方法基于這樣一種思想：對于一個復(fù)雜任務(wù)來說，將多個專家的判斷進(jìn)行適當(dāng)?shù)木C合所得出的判斷，要比其中任何一個專家單獨(dú)的判斷要好。通俗地說，就是“三個臭皮匠頂個諸葛亮”的道理。梯度提升同其他boosting方法一樣，通過集成（ensemble）多個弱學(xué)習(xí)器，通常是決策樹，來構(gòu)建最終的預(yù)測模型。

Boosting、bagging和stacking是集成學(xué)習(xí)的三種主要方法。

不同于bagging方法，boosting方法通過分步迭代（stage-wise）的方式來構(gòu)建模型，在迭代的每一步構(gòu)建的弱學(xué)習(xí)器都是為了彌補(bǔ)已有模型的不足。Boosting族算法的著名代表是AdaBoost。AdaBoost算法通過給已有模型預(yù)測錯誤的樣本更高的權(quán)重，使得先前的學(xué)習(xí)器做錯的訓(xùn)練樣本在后續(xù)受到更多的關(guān)注的方式來彌補(bǔ)已有模型的不足。

雖然同屬于Boosting族，但是梯度提升方法的優(yōu)點(diǎn)比較多。

相比于AdaBoost，梯度提升方法的優(yōu)點(diǎn):

• 1、與AdaBoost算法不同，梯度提升方法在迭代的每一步構(gòu)建一個能夠沿著梯度最陡的方向降低損失（steepest-descent）的學(xué)習(xí)器來彌補(bǔ)已有模型的不足。
• 2、經(jīng)典的AdaBoost算法只能處理采用指數(shù)損失函數(shù)的二分類學(xué)習(xí)任務(wù)，而梯度提升方法通過設(shè)置不同的可微損失函數(shù)可以處理各類學(xué)習(xí)任務(wù)（多分類、回歸、Ranking等），應(yīng)用范圍大大擴(kuò)展。
• 3、AdaBoost算法對異常點(diǎn)（outlier）比較敏感，而梯度提升算法通過引入bagging思想、加入正則項(xiàng)等方法能夠有效地抵御訓(xùn)練數(shù)據(jù)中的噪音，具有更好的健壯性。

? ?? 提升樹是迭代多棵回歸樹來共同決策。當(dāng)采用平方誤差損失函數(shù)時，每一棵回歸樹學(xué)習(xí)的是之前所有樹的結(jié)論和殘差，擬合得到一個當(dāng)前的殘差回歸樹，殘差的意義如公式：殘差 = 真實(shí)值 - 預(yù)測值 。提升樹即是整個迭代過程生成的回歸樹的累加。

GBDT的核心就在于，每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差，這個殘差就是一個加預(yù)測值后能得真實(shí)值的累加量。

?

3. Gradient Boosting Decision Tree：梯度提升決策樹

為什么梯度提升方法傾向于選擇決策樹（通常是CART樹）作為基學(xué)習(xí)器呢？

這與決策樹算法自身的優(yōu)點(diǎn)有很大的關(guān)系：

決策樹可以認(rèn)為是if-then規(guī)則的集合，易于理解，可解釋性強(qiáng)，預(yù)測速度快；

決策樹算法相比于其他的算法需要更少的特征工程，比如可以不用做特征標(biāo)準(zhǔn)化，可以很好的處理字段缺失的數(shù)據(jù)，也可以不用關(guān)心特征間是否相互依賴等

決策樹能夠自動組合多個特征，它可以毫無壓力地處理特征間的交互關(guān)系并且是非參數(shù)化的，因此你不必?fù)?dān)心異常值或者數(shù)據(jù)是否線性可分。舉個例子，西瓜a（烏黑色、紋路清晰）可能是好瓜，西瓜b（青綠色，紋路清晰）的也可能是好瓜。決策樹一樣可以處理。

決策樹有優(yōu)點(diǎn)，自然也有缺點(diǎn)，不過，可以通過梯度提升方法解決這個缺點(diǎn)。單獨(dú)使用決策樹算法時，有容易過擬合缺點(diǎn)。

怎么解決呢？

• 通過各種方法，抑制決策樹的復(fù)雜性，降低單棵決策樹的擬合能力
• 通過梯度提升的方法集成多個決策樹，則預(yù)測效果上來的同時，也能夠很好的解決過擬合的問題。
  （這一點(diǎn)具有bagging的思想，降低單個學(xué)習(xí)器的擬合能力，提高方法的泛化能力。）

由此可見，梯度提升方法和決策樹學(xué)習(xí)算法可以互相取長補(bǔ)短，是一對完美的搭檔。

怎么降低單棵決策樹的復(fù)雜度？

抑制單顆決策樹的復(fù)雜度的方法有很多：

• 限制樹的最大深度、限制葉子節(jié)點(diǎn)的最少樣本數(shù)量、限制節(jié)點(diǎn)分裂時的最少樣本數(shù)量
• 吸收bagging的思想對訓(xùn)練樣本采樣（subsample），在學(xué)習(xí)單顆決策樹時只使用一部分訓(xùn)練樣本
• 借鑒隨機(jī)森林的思路在學(xué)習(xí)單顆決策樹時只采樣一部分特征
• 在目標(biāo)函數(shù)中添加正則項(xiàng)懲罰復(fù)雜的樹結(jié)構(gòu)等。

現(xiàn)在主流的GBDT算法實(shí)現(xiàn)中這些方法基本上都有實(shí)現(xiàn)，因此GBDT算法的超參數(shù)還是比較多的，應(yīng)用過程中需要精心調(diào)參，并用交叉驗(yàn)證的方法選擇最佳參數(shù)。

提升樹利用加法模型和前向分步算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過程。當(dāng)損失函數(shù)時平方損失和指數(shù)損失函數(shù)時，每一步的優(yōu)化很簡單，如平方損失函數(shù)學(xué)習(xí)殘差回歸樹。

?

前向分布算法(Forward stagewise additive modeling)

提升方法其實(shí)是一個比adaboost概念更大的算法，因?yàn)閍daboost可以表示為boosting的前向分布算法(Forward stagewise additive modeling)的一個特例，boosting最終可以表示為：

其中的w是權(quán)重，Φ是弱分類器(回歸器)的集合,其實(shí)就是一個加法模型(即基函數(shù)的線性組合)

前向分布算法實(shí)際上是一個貪心的算法，也就是在每一步求解弱分類器Φ(m)和其參數(shù)w(m)的時候不去修改之前已經(jīng)求好的分類器和參數(shù)：

前向分布算法 來自《統(tǒng)計(jì)學(xué)習(xí)方法》

為了表示方便，我們以后用β代替w進(jìn)行描述了，圖中的b是之前說的Φ弱分類器

OK，這也就是提升方法（之前向分布算法）的大致結(jié)構(gòu)了，可以看到其中存在變數(shù)的部分其實(shí)就是極小化損失函數(shù) 這關(guān)鍵的一步了，如何選擇損失函數(shù)決定了算法的最終效果(名字)……這一步你可以看出算法的“趨勢”，以后再單獨(dú)把“趨勢”拿出來說吧，因?yàn)槲腋杏X理解算法的關(guān)鍵之一就是理解算法公式的“趨勢”

各種提升方法

不同的損失函數(shù)和極小化損失函數(shù)方法決定了boosting的最終效果，我們現(xiàn)在來說幾個常見的boosting：

廣義上來講，所謂的Gradient Boosting 其實(shí)就是在更新的時候選擇梯度下降的方向來保證最后的結(jié)果最好，一些書上講的“殘差” 方法其實(shí)就是L2Boosting吧，因?yàn)樗x的殘差其實(shí)就是L2Boosting的Derivative，接下來我們著重講一下弱回歸器是決策樹的情況，也就是GBDT。

加法模型（additive model）

GBDT算法可以看成是由K棵樹組成的加法模型：

其中F為所有樹組成的函數(shù)空間，以回歸任務(wù)為例，回歸樹可以看作為一個把特征向量映射為某個score的函數(shù)。該模型的參數(shù)為：Θ = {f1, f2, ... , fk} 。于一般的機(jī)器學(xué)習(xí)算法不同的是，加法模型不是學(xué)習(xí)d維空間中的權(quán)重，而是直接學(xué)習(xí)函數(shù)（決策樹）集合。上述加法模型的目標(biāo)函數(shù)定義為：

其中Ω表示決策樹的復(fù)雜度，那么該如何定義樹的復(fù)雜度呢？比如，可以考慮樹的節(jié)點(diǎn)數(shù)量、樹的深度或者葉子節(jié)點(diǎn)所對應(yīng)的分?jǐn)?shù)的L2范數(shù)等等。

如何來學(xué)習(xí)加法模型呢？

解這一優(yōu)化問題，可以用前向分布算法（forward stagewise algorithm）。因?yàn)閷W(xué)習(xí)的是加法模型，如果能夠從前往后，每一步只學(xué)習(xí)一個基函數(shù)及其系數(shù)（結(jié)構(gòu)），逐步逼近優(yōu)化目標(biāo)函數(shù)，那么就可以簡化復(fù)雜度。這一學(xué)習(xí)過程稱之為Boosting。具體地，我們從一個常量預(yù)測開始，每次學(xué)習(xí)一個新的函數(shù)，過程如下：

舉個例子，參考自一篇博客, 該博客舉出的例子較直觀地展現(xiàn)出多棵決策樹線性求和過程以及殘差的意義。
還是年齡預(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的殘差就是15-16=-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)算過程講完了！沒錯就是這么簡單。

該例子很直觀的能看到，預(yù)測值等于所有樹值得累加，如A的預(yù)測值 = 樹1左節(jié)點(diǎn) 值 15 + 樹2左節(jié)點(diǎn) -1 = 14。
因此，給定當(dāng)前模型 fm-1(x)，只需要簡單的擬合當(dāng)前模型的殘差。現(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ú)立分析。如果反過來做，或者剛上來就一定要做到盡善盡美，往往最終會竹籃打水一場空。

4. 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ù)例）。

總結(jié)

以上是生活随笔為你收集整理的[机器学习] Boosting算法2 --- GBDT的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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