在集成學(xué)習(xí)之Adaboost算法原理小結(jié)中，我們對(duì)Boosting家族的Adaboost算法做了總結(jié)，本文就對(duì)Boosting家族中另一個(gè)重要的算法梯度提升樹(shù)(Gradient Boosting Decison Tree, 以下簡(jiǎn)稱(chēng)GBDT)做一個(gè)總結(jié)。GBDT有很多簡(jiǎn)稱(chēng)，有GBT（Gradient Boosting Tree）,?GTB（Gradient Tree Boosting?），?GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)，其實(shí)都是指的同一種算法，本文統(tǒng)一簡(jiǎn)稱(chēng)GBDT。GBDT在BAT大廠中也有廣泛的應(yīng)用，假如要選擇3個(gè)最重要的機(jī)器學(xué)習(xí)算法的話(huà)，個(gè)人認(rèn)為GBDT應(yīng)該占一席之地。

1. GBDT概述

　　　　GBDT也是集成學(xué)習(xí)Boosting家族的成員，但是卻和傳統(tǒng)的Adaboost有很大的不同。回顧下Adaboost，我們是利用前一輪迭代弱學(xué)習(xí)器的誤差率來(lái)更新訓(xùn)練集的權(quán)重，這樣一輪輪的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱學(xué)習(xí)器限定了只能使用CART回歸樹(shù)模型，同時(shí)迭代思路和Adaboost也有所不同。

　　　　在GBDT的迭代中，假設(shè)我們前一輪迭代得到的強(qiáng)學(xué)習(xí)器是ft?1(x)ft?1(x), 損失函數(shù)是L(y,ft?1(x))L(y,ft?1(x)), 我們本輪迭代的目標(biāo)是找到一個(gè)CART回歸樹(shù)模型的弱學(xué)習(xí)器ht(x)ht(x)，讓本輪的損失函數(shù)L(y,ft(x)=L(y,ft?1(x)+ht(x))L(y,ft(x)=L(y,ft?1(x)+ht(x))最小。也就是說(shuō)，本輪迭代找到?jīng)Q策樹(shù)，要讓樣本的損失盡量變得更小。

　　　　GBDT的思想可以用一個(gè)通俗的例子解釋，假如有個(gè)人30歲，我們首先用20歲去擬合，發(fā)現(xiàn)損失有10歲，這時(shí)我們用6歲去擬合剩下的損失，發(fā)現(xiàn)差距還有4歲，第三輪我們用3歲擬合剩下的差距，差距就只有一歲了。如果我們的迭代輪數(shù)還沒(méi)有完，可以繼續(xù)迭代下面，每一輪迭代，擬合的歲數(shù)誤差都會(huì)減小。

　　　　從上面的例子看這個(gè)思想還是蠻簡(jiǎn)單的，但是有個(gè)問(wèn)題是這個(gè)損失的擬合不好度量，損失函數(shù)各種各樣，怎么找到一種通用的擬合方法呢？

2. GBDT的負(fù)梯度擬合

　　　　在上一節(jié)中，我們介紹了GBDT的基本思路，但是沒(méi)有解決損失函數(shù)擬合方法的問(wèn)題。針對(duì)這個(gè)問(wèn)題，大牛Freidman提出了用損失函數(shù)的負(fù)梯度來(lái)擬合本輪損失的近似值，進(jìn)而擬合一個(gè)CART回歸樹(shù)。第t輪的第i個(gè)樣本的損失函數(shù)的負(fù)梯度表示為

rti=?[?L(yi,f(xi)))?f(xi)]f(x)=ft?1(x)rti=?[?L(yi,f(xi)))?f(xi)]f(x)=ft?1(x)

　　　　利用(xi,rti)(i=1,2,..m)(xi,rti)(i=1,2,..m),我們可以擬合一顆CART回歸樹(shù)，得到了第t顆回歸樹(shù)，其對(duì)應(yīng)的葉節(jié)點(diǎn)區(qū)域Rtj,j=1,2,...,JRtj,j=1,2,...,J。其中J為葉子節(jié)點(diǎn)的個(gè)數(shù)。

　　　　針對(duì)每一個(gè)葉子節(jié)點(diǎn)里的樣本，我們求出使損失函數(shù)最小，也就是擬合葉子節(jié)點(diǎn)最好的的輸出值ctjctj如下：

ctj=argminc∑xi∈RtjL(yi,ft?1(xi)+c)ctj=argmin?c∑xi∈RtjL(yi,ft?1(xi)+c)

　　　　這樣我們就得到了本輪的決策樹(shù)擬合函數(shù)如下：

ht(x)=∑j=1JctjI(x∈Rtj)ht(x)=∑j=1JctjI(x∈Rtj)

　　　　從而本輪最終得到的強(qiáng)學(xué)習(xí)器的表達(dá)式如下：

ft(x)=ft?1(x)+∑j=1JctjI(x∈Rtj)ft(x)=ft?1(x)+∑j=1JctjI(x∈Rtj)

　　　　通過(guò)損失函數(shù)的負(fù)梯度來(lái)擬合，我們找到了一種通用的擬合損失誤差的辦法，這樣無(wú)輪是分類(lèi)問(wèn)題還是回歸問(wèn)題，我們通過(guò)其損失函數(shù)的負(fù)梯度的擬合，就可以用GBDT來(lái)解決我們的分類(lèi)回歸問(wèn)題。區(qū)別僅僅在于損失函數(shù)不同導(dǎo)致的負(fù)梯度不同而已。

?3.?GBDT回歸算法

　　　　好了，有了上面的思路，下面我們總結(jié)下GBDT的回歸算法。為什么沒(méi)有加上分類(lèi)算法一起？那是因?yàn)榉诸?lèi)算法的輸出是不連續(xù)的類(lèi)別值，需要一些處理才能使用負(fù)梯度，我們?cè)谙乱还?jié)講。

　　　　輸入是訓(xùn)練集樣本T={(x,y1),(x2,y2),...(xm,ym)}T={(x,y1),(x2,y2),...(xm,ym)}， 最大迭代次數(shù)T, 損失函數(shù)L。

　　　　輸出是強(qiáng)學(xué)習(xí)器f(x)

　　　　1) 初始化弱學(xué)習(xí)器

f0(x)=argminc∑i=1mL(yi,c)f0(x)=argmin?c∑i=1mL(yi,c)

　　　　2) 對(duì)迭代輪數(shù)t=1,2,...T有：

　　　　　　a)對(duì)樣本i=1,2，...m，計(jì)算負(fù)梯度

rti=?[?L(yi,f(xi)))?f(xi)]f(x)=ft?1(x)rti=?[?L(yi,f(xi)))?f(xi)]f(x)=ft?1(x)

　　　　　　b)利用(xi,rti)(i=1,2,..m)(xi,rti)(i=1,2,..m), 擬合一顆CART回歸樹(shù),得到第t顆回歸樹(shù)，其對(duì)應(yīng)的葉子節(jié)點(diǎn)區(qū)域?yàn)镽tj,j=1,2,...,JRtj,j=1,2,...,J。其中J為回歸樹(shù)t的葉子節(jié)點(diǎn)的個(gè)數(shù)。

　　　　　　c) 對(duì)葉子區(qū)域j =1,2,..J,計(jì)算最佳擬合值

ctj=argminc∑xi∈RtjL(yi,ft?1(xi)+c)ctj=argmin?c∑xi∈RtjL(yi,ft?1(xi)+c)

　　　　　　d) 更新強(qiáng)學(xué)習(xí)器

ft(x)=ft?1(x)+∑j=1JctjI(x∈Rtj)ft(x)=ft?1(x)+∑j=1JctjI(x∈Rtj)

　　　　3) 得到強(qiáng)學(xué)習(xí)器f(x)的表達(dá)式

f(x)=fT(x)=f0(x)+∑t=1T∑j=1JctjI(x∈Rtj)f(x)=fT(x)=f0(x)+∑t=1T∑j=1JctjI(x∈Rtj)

4. GBDT分類(lèi)算法

　　　　這里我們?cè)倏纯碐BDT分類(lèi)算法，GBDT的分類(lèi)算法從思想上和GBDT的回歸算法沒(méi)有區(qū)別，但是由于樣本輸出不是連續(xù)的值，而是離散的類(lèi)別，導(dǎo)致我們無(wú)法直接從輸出類(lèi)別去擬合類(lèi)別輸出的誤差。

　　　　為了解決這個(gè)問(wèn)題，主要有兩個(gè)方法，一個(gè)是用指數(shù)損失函數(shù)，此時(shí)GBDT退化為Adaboost算法。另一種方法是用類(lèi)似于邏輯回歸的對(duì)數(shù)似然損失函數(shù)的方法。也就是說(shuō)，我們用的是類(lèi)別的預(yù)測(cè)概率值和真實(shí)概率值的差來(lái)擬合損失。本文僅討論用對(duì)數(shù)似然損失函數(shù)的GBDT分類(lèi)。而對(duì)于對(duì)數(shù)似然損失函數(shù)，我們又有二元分類(lèi)和多元分類(lèi)的區(qū)別。

4.1 二元GBDT分類(lèi)算法

　　　　對(duì)于二元GBDT，如果用類(lèi)似于邏輯回歸的對(duì)數(shù)似然損失函數(shù)，則損失函數(shù)為：

L(y,f(x))=log(1+exp(?yf(x)))L(y,f(x))=log(1+exp(?yf(x)))

　　　　其中y∈{?1,+1}y∈{?1,+1}。則此時(shí)的負(fù)梯度誤差為

rti=?[?L(y,f(xi)))?f(xi)]f(x)=ft?1(x)=yi/(1+exp(yif(xi)))rti=?[?L(y,f(xi)))?f(xi)]f(x)=ft?1(x)=yi/(1+exp(yif(xi)))

　　　　對(duì)于生成的決策樹(shù)，我們各個(gè)葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合值為

ctj=argminc∑xi∈Rtjlog(1+exp(?yi(ft?1(xi)+c)))ctj=argmin?c∑xi∈Rtjlog(1+exp(?yi(ft?1(xi)+c)))

　　　　由于上式比較難優(yōu)化，我們一般使用近似值代替

ctj=∑xi∈Rtjrti/∑xi∈Rtj|rti|(1?|rti|)ctj=∑xi∈Rtjrti/∑xi∈Rtj|rti|(1?|rti|)

　　　　除了負(fù)梯度計(jì)算和葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合的線性搜索，二元GBDT分類(lèi)和GBDT回歸算法過(guò)程相同。

4.2 多元GBDT分類(lèi)算法

　　　　多元GBDT要比二元GBDT復(fù)雜一些，對(duì)應(yīng)的是多元邏輯回歸和二元邏輯回歸的復(fù)雜度差別。假設(shè)類(lèi)別數(shù)為K，則此時(shí)我們的對(duì)數(shù)似然損失函數(shù)為：

L(y,f(x))=?∑k=1Kyklogpk(x)L(y,f(x))=?∑k=1Kyklogpk(x)

　　　　其中如果樣本輸出類(lèi)別為k，則yk=1yk=1。第k類(lèi)的概率pk(x)pk(x)的表達(dá)式為：

pk(x)=exp(fk(x))/∑l=1Kexp(fl(x))pk(x)=exp(fk(x))/∑l=1Kexp(fl(x))

　　　　集合上兩式，我們可以計(jì)算出第tt輪的第ii個(gè)樣本對(duì)應(yīng)類(lèi)別ll的負(fù)梯度誤差為

rtil=?[?L(yi,f(xi)))?f(xi)]fk(x)=fl,t?1(x)=yil?pl,t?1(xi)rtil=?[?L(yi,f(xi)))?f(xi)]fk(x)=fl,t?1(x)=yil?pl,t?1(xi)

　　　　觀察上式可以看出，其實(shí)這里的誤差就是樣本ii對(duì)應(yīng)類(lèi)別ll的真實(shí)概率和t?1t?1輪預(yù)測(cè)概率的差值。

　　　　對(duì)于生成的決策樹(shù)，我們各個(gè)葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合值為

ctjl=argmincjl∑i=0m∑k=1KL(yk,ft?1,l(x)+∑j=0JcjlI(xi∈Rtjl))ctjl=argmin?cjl∑i=0m∑k=1KL(yk,ft?1,l(x)+∑j=0JcjlI(xi∈Rtjl))

　　　　由于上式比較難優(yōu)化，我們一般使用近似值代替

ctjl=K?1K∑xi∈Rtjlrtil∑xi∈Rtil|rtil|(1?|rtil|)ctjl=K?1K∑xi∈Rtjlrtil∑xi∈Rtil|rtil|(1?|rtil|)

　　　　除了負(fù)梯度計(jì)算和葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合的線性搜索，多元GBDT分類(lèi)和二元GBDT分類(lèi)以及GBDT回歸算法過(guò)程相同。

5. GBDT常用損失函數(shù)

　　　　這里我們?cè)賹?duì)常用的GBDT損失函數(shù)做一個(gè)總結(jié)。

　　　　對(duì)于分類(lèi)算法，其損失函數(shù)一般有對(duì)數(shù)損失函數(shù)和指數(shù)損失函數(shù)兩種:

　　　　a) 如果是指數(shù)損失函數(shù)，則損失函數(shù)表達(dá)式為

L(y,f(x))=exp(?yf(x))L(y,f(x))=exp(?yf(x))

　　　　其負(fù)梯度計(jì)算和葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合參見(jiàn)Adaboost原理篇。

　　　　b)?如果是對(duì)數(shù)損失函數(shù)，分為二元分類(lèi)和多元分類(lèi)兩種，參見(jiàn)4.1節(jié)和4.2節(jié)。

　　　　

　　　　對(duì)于回歸算法，常用損失函數(shù)有如下4種:

　　　　a)均方差，這個(gè)是最常見(jiàn)的回歸損失函數(shù)了

L(y,f(x))=(y?f(x))2L(y,f(x))=(y?f(x))2

　　　　b)絕對(duì)損失，這個(gè)損失函數(shù)也很常見(jiàn)

L(y,f(x))=|y?f(x)|L(y,f(x))=|y?f(x)|

　　　　　　對(duì)應(yīng)負(fù)梯度誤差為：

sign(yi?f(xi))sign(yi?f(xi))

　　　　c)Huber損失，它是均方差和絕對(duì)損失的折衷產(chǎn)物，對(duì)于遠(yuǎn)離中心的異常點(diǎn)，采用絕對(duì)損失，而中心附近的點(diǎn)采用均方差。這個(gè)界限一般用分位數(shù)點(diǎn)度量。損失函數(shù)如下：

?

L(y,f(x))={12(y?f(x))2δ(|y?f(x)|?δ2)|y?f(x)|≤δ|y?f(x)|>δL(y,f(x))={12(y?f(x))2|y?f(x)|≤δδ(|y?f(x)|?δ2)|y?f(x)|>δ

　　　　對(duì)應(yīng)的負(fù)梯度誤差為：

?

r(yi,f(xi))={yi?f(xi)δsign(yi?f(xi))|yi?f(xi)|≤δ|yi?f(xi)|>δr(yi,f(xi))={yi?f(xi)|yi?f(xi)|≤δδsign(yi?f(xi))|yi?f(xi)|>δ

　　　　d) 分位數(shù)損失。它對(duì)應(yīng)的是分位數(shù)回歸的損失函數(shù)，表達(dá)式為

L(y,f(x))=∑y≥f(x)θ|y?f(x)|+∑y<f(x)(1?θ)|y?f(x)|L(y,f(x))=∑y≥f(x)θ|y?f(x)|+∑y<f(x)(1?θ)|y?f(x)|

　　　　　　其中θθ為分位數(shù)，需要我們?cè)诨貧w前指定。對(duì)應(yīng)的負(fù)梯度誤差為：

?

r(yi,f(xi))={θθ?1yi≥f(xi)yi<f(xi)r(yi,f(xi))={θyi≥f(xi)θ?1yi<f(xi)

　　　　對(duì)于Huber損失和分位數(shù)損失，主要用于健壯回歸，也就是減少異常點(diǎn)對(duì)損失函數(shù)的影響。

6. GBDT的正則化

　　　　和Adaboost一樣，我們也需要對(duì)GBDT進(jìn)行正則化，防止過(guò)擬合。GBDT的正則化主要有三種方式。

　　　　第一種是和Adaboost類(lèi)似的正則化項(xiàng)，即步長(zhǎng)(learning rate)。定義為νν,對(duì)于前面的弱學(xué)習(xí)器的迭代

fk(x)=fk?1(x)+hk(x)fk(x)=fk?1(x)+hk(x)

　　　　如果我們加上了正則化項(xiàng)，則有

fk(x)=fk?1(x)+νhk(x)fk(x)=fk?1(x)+νhk(x)

　　　　νν的取值范圍為0<ν≤10<ν≤1。對(duì)于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的νν意味著我們需要更多的弱學(xué)習(xí)器的迭代次數(shù)。通常我們用步長(zhǎng)和迭代最大次數(shù)一起來(lái)決定算法的擬合效果。

?

　　　　第二種正則化的方式是通過(guò)子采樣比例（subsample）。取值為(0,1]。注意這里的子采樣和隨機(jī)森林不一樣，隨機(jī)森林使用的是放回抽樣，而這里是不放回抽樣。如果取值為1，則全部樣本都使用，等于沒(méi)有使用子采樣。如果取值小于1，則只有一部分樣本會(huì)去做GBDT的決策樹(shù)擬合。選擇小于1的比例可以減少方差，即防止過(guò)擬合，但是會(huì)增加樣本擬合的偏差，因此取值不能太低。推薦在[0.5, 0.8]之間。

　　　　使用了子采樣的GBDT有時(shí)也稱(chēng)作隨機(jī)梯度提升樹(shù)(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采樣，程序可以通過(guò)采樣分發(fā)到不同的任務(wù)去做boosting的迭代過(guò)程，最后形成新樹(shù)，從而減少弱學(xué)習(xí)器難以并行學(xué)習(xí)的弱點(diǎn)。

?

　　　　第三種是對(duì)于弱學(xué)習(xí)器即CART回歸樹(shù)進(jìn)行正則化剪枝。在決策樹(shù)原理篇里我們已經(jīng)講過(guò)，這里就不重復(fù)了。

7. GBDT小結(jié)　

　　　　GBDT終于講完了，GDBT本身并不復(fù)雜，不過(guò)要吃透的話(huà)需要對(duì)集成學(xué)習(xí)的原理，決策樹(shù)原理和各種損失函樹(shù)有一定的了解。由于GBDT的卓越性能，只要是研究機(jī)器學(xué)習(xí)都應(yīng)該掌握這個(gè)算法，包括背后的原理和應(yīng)用調(diào)參方法。目前GBDT的算法比較好的庫(kù)是xgboost。當(dāng)然scikit-learn也可以。

　　　　最后總結(jié)下GBDT的優(yōu)缺點(diǎn)。

　　　　GBDT主要的優(yōu)點(diǎn)有：

　　　　1) 可以靈活處理各種類(lèi)型的數(shù)據(jù)，包括連續(xù)值和離散值。

　　　　2) 在相對(duì)少的調(diào)參時(shí)間情況下，預(yù)測(cè)的準(zhǔn)確率也可以比較高。這個(gè)是相對(duì)SVM來(lái)說(shuō)的。

　　　　3）使用一些健壯的損失函數(shù)，對(duì)異常值的魯棒性非常強(qiáng)。比如 Huber損失函數(shù)和Quantile損失函數(shù)。

　　　　GBDT的主要缺點(diǎn)有：

　　　　1)由于弱學(xué)習(xí)器之間存在依賴(lài)關(guān)系，難以并行訓(xùn)練數(shù)據(jù)。不過(guò)可以通過(guò)自采樣的SGBT來(lái)達(dá)到部分并行。

?

　　　　以上就是GBDT的原理總結(jié)，后面會(huì)講GBDT的scikit-learn調(diào)參，敬請(qǐng)期待。

來(lái)源:https://www.cnblogs.com/pinard/p/6140514.html

總結(jié)

以上是生活随笔為你收集整理的梯度提升树(GBDT)原理小结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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