一、背景

集成學(xué)習(xí)Boosting一族將多個(gè)弱學(xué)習(xí)器(或稱基學(xué)習(xí)器)提升為強(qiáng)學(xué)習(xí)器，像AdaBoost, GBDT等都屬于“加性模型”(Additive Model)，即基學(xué)習(xí)器的線性組合。1997年Freund和Schapire提出的AdaBoost，它是先從初始訓(xùn)練集訓(xùn)練出一個(gè)基學(xué)習(xí)器，然后基于基學(xué)習(xí)器的在這一輪的表現(xiàn)，在下一輪訓(xùn)練中給預(yù)測(cè)錯(cuò)的訓(xùn)練樣本更大權(quán)重值，以達(dá)到逐步減少在訓(xùn)練集的預(yù)測(cè)錯(cuò)誤率。這種訓(xùn)練機(jī)制像不像做一套卷子，有些重難點(diǎn)題做不出來，那下次又給你做同樣的卷子，但不同的是：之前你做錯(cuò)的重難點(diǎn)題占有很大的分值比重，這樣你會(huì)將更多重心放在了這些難題上，從而提高你的學(xué)習(xí)表現(xiàn)。那除了這種方式，還有沒有其他方法攻克考題上的重難點(diǎn)？有，就是死磕到底，找到這題錯(cuò)在哪？基于此錯(cuò)誤繼續(xù)去做這道題，直到做對(duì)為止。這跟GBDT [1] 的工作機(jī)制就很像了，它是先產(chǎn)生一個(gè)弱學(xué)習(xí)器(CART回歸樹模型)，訓(xùn)練后得到輸入樣本的殘差，然后再產(chǎn)生一個(gè)弱學(xué)習(xí)器，基于上一輪殘差進(jìn)行訓(xùn)練。不斷迭代，最后加權(quán)結(jié)合所有弱學(xué)習(xí)器得到強(qiáng)學(xué)習(xí)器。GBDT的一個(gè)應(yīng)用示意圖如下（某樣本預(yù)測(cè)值 = 它在不同弱學(xué)習(xí)器所在葉子節(jié)點(diǎn)輸出值的累加值）：

圖1：GBDT應(yīng)用示意圖

二、GBDT

第二部分目錄如下：

1.背景知識(shí)

• GBDT弱學(xué)習(xí)器
• GBDT模型框架

2.GBDT回歸

3.GBDT分類

• GBDT二分類
• GBDT多分類

1. 背景知識(shí)

GBDT可用于回歸和分類任務(wù)。在深入了解它在回歸或分類任務(wù)上的訓(xùn)練細(xì)節(jié)之前，我們先了解一些相關(guān)的背景知識(shí)。

（1）GBDT弱學(xué)習(xí)器

決策樹是IF-THEN結(jié)構(gòu)，它學(xué)習(xí)的關(guān)鍵在于如何選擇最優(yōu)劃分屬性。西瓜書 [2] 提到：“隨著劃分過程不斷進(jìn)行，我們希望決策樹的分支結(jié)點(diǎn)所包含的樣本盡可能屬于同一類別，即結(jié)點(diǎn)的“純度”(Purity)越來越高”。衡量純度的指標(biāo)有多種，因此對(duì)應(yīng)有不同類型的決策樹算法，例如ID3決策樹 (以信息增益Information Gain作為屬性劃分標(biāo)準(zhǔn))，C4.5決策樹 (以增益率Gain Ratio選擇最優(yōu)劃分屬性)，CART決策樹 (使用基尼指數(shù)Gini Index)來選擇劃分屬性。

決策樹那么多種，為什么GBDT的弱學(xué)習(xí)器就限定使用CART決策樹？

A： 原因如下所示 (具體細(xì)節(jié)不展開)：

• ID3決策樹只支持類別型變量，而C4.5和CART支持連續(xù)型和類別型變量。
• C4.5適用于小樣本，CART適用于大樣本。

CART決策樹是怎么計(jì)算基尼值呢？

A： 假設(shè)當(dāng)前數(shù)據(jù)集D中第k類樣本所占比例為 (k=1,2,…,)，則基尼值為：

反映了從數(shù)據(jù)集D隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概念，因此越小，數(shù)據(jù)集D的純度越高。基于此，屬性a的基尼指數(shù)定義為：

假設(shè)屬性a有V個(gè)可能的取值{}，則是指第v個(gè)分支結(jié)點(diǎn)包含D中所有在屬性a上取值為的樣本。是給分支結(jié)點(diǎn)賦予權(quán)重，獲得樣本數(shù)更多的結(jié)點(diǎn)，影響更大。

舉個(gè)具體計(jì)算基尼指數(shù)的例子，假如按照“芯片為高通驍龍865和非高通驍龍865進(jìn)行機(jī)型檔位劃分”：

表1：基尼指數(shù)計(jì)算樣例集

當(dāng)芯片為高通驍龍865時(shí)，有旗艦機(jī)2個(gè)，中端機(jī)1個(gè)：

當(dāng)芯片非高通驍龍865時(shí)，有中端機(jī)1個(gè)，低端機(jī)1個(gè)：

最后，特征”芯片”下數(shù)據(jù)集的基尼指數(shù)是：

為什么GBDT用回歸樹，不用分類樹？

A： 因?yàn)镚BDT要計(jì)算殘差，且預(yù)測(cè)結(jié)果是通過累加所有樹結(jié)果得到的。因此分類樹沒法產(chǎn)生連續(xù)型結(jié)果滿足GBDT的需求。

（2）GBDT模型框架

圖2：GBDT算法實(shí)現(xiàn)流程圖及偽代碼 [3]

GBDT的偽代碼如圖2所示，假設(shè)我們有個(gè)樣本集，想用M個(gè)弱學(xué)習(xí)器加性組合成GBDT強(qiáng)學(xué)習(xí)器，我們得按以下步驟進(jìn)行實(shí)現(xiàn) (詳情參考 [4])：

1）初始化一個(gè)弱學(xué)習(xí)器。它使損失函數(shù)最小化，具體如下：

這里是什么呢？請(qǐng)接著看下去，假設(shè)這里損失函數(shù)為平方損失，則對(duì)求導(dǎo)：

由于這里的損失函數(shù)為凸函數(shù)，所以只要令上面這個(gè)導(dǎo)數(shù)為0即可，那么可以求得：

因此，是所有訓(xùn)練樣本標(biāo)簽值的均值，它是一個(gè)常數(shù)，所以弱學(xué)習(xí)器就只有一個(gè)根節(jié)點(diǎn)。

注意：因損失函數(shù)不同而不同。

2）迭代訓(xùn)練m = 1, 2, … , M棵樹。

（a）對(duì)每個(gè)樣本i = 1, 2, …, N，計(jì)算負(fù)梯度:

（b）將上步（a）得到的負(fù)梯度作為新樣本值，將新數(shù)據(jù), I = 1, 2, …, N作為下顆樹的訓(xùn)練數(shù)據(jù)，擬合得到新樹，新樹上的葉子節(jié)點(diǎn)區(qū)域?yàn)?img src="http://file1.elecfans.com/web2/M00/8E/33/wKgZomTDZzGAXF34AAACE3D9N-c154.jpg" alt="圖片" />（j = 1, 2, …,，其中為葉子結(jié)點(diǎn)的個(gè)數(shù)）。

（c）對(duì)每個(gè)葉子節(jié)點(diǎn)j = 1, 2, …, ，計(jì)算最佳擬合（即使損失函數(shù)最小，擬合葉子節(jié)點(diǎn)最好的輸出值）：

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

是CART回歸樹模型的表達(dá)式，其中J是指數(shù)據(jù)集被劃分為J個(gè)單元（即葉子節(jié)點(diǎn)），是第m輪迭代訓(xùn)練下，CART樹第j個(gè)單元的輸出值。而是指示函數(shù)，若，則I=1，否則I=0。這里第m輪下的強(qiáng)學(xué)習(xí)器 = 第m-1輪下的強(qiáng)學(xué)習(xí)器 + 第m輪的弱學(xué)習(xí)器。

3）輸出最終學(xué)習(xí)器GBDT:

上述公式展示的就是一系列弱學(xué)習(xí)器累加后得到強(qiáng)學(xué)習(xí)器的結(jié)果。

負(fù)梯度和殘差的關(guān)系是什么？

A： 負(fù)梯度是函數(shù)下降最快的方向，也是GBDT目標(biāo)函數(shù)下降最快的方向，所以，我們用負(fù)梯度去擬合模型。而殘差只是一個(gè)負(fù)梯度的特例，當(dāng)損失函數(shù)為均方損失時(shí)，負(fù)梯度剛好是殘差（這點(diǎn)在上面 "對(duì)求導(dǎo)" 處有做假設(shè)展示）。

2. GBDT回歸

上面”GBDT通用框架”就是以平方損失為損失函數(shù)的一種GBDT回歸模型學(xué)習(xí)過程，不同損失函數(shù)導(dǎo)致使用的負(fù)梯度不同，因此也就產(chǎn)生了不同的GBDT回歸算法，總結(jié)了下GBDT回歸模型所用的損失和負(fù)梯度如下：

表2：GBDT回歸樹常用損失函數(shù)及負(fù)梯度 [5]

這里特別說下Huber損失，它對(duì)于中間附近的點(diǎn) ()采用均方誤差，對(duì)遠(yuǎn)離中心的異常點(diǎn) ()，采用絕對(duì)損失。邊界點(diǎn)δ的值受絕對(duì)損失函數(shù)而不是平方誤差損失控制，定義了這些被認(rèn)為是“離群點(diǎn)”的殘差值?？偟膩碚f，Huber結(jié)合了均方差和絕對(duì)損失，在抵抗長(zhǎng)尾誤差分布和異常值的同時(shí)，還保持了對(duì)正態(tài)分布誤差的高效率。它和分位數(shù)損失一樣，適用于穩(wěn)健回歸，用于減少異常點(diǎn)對(duì)損失函數(shù)的影響。

3. GBDT分類

由于分類有二分類和多分類任務(wù)，所以GBDT分類有所區(qū)別，這里分開對(duì)它們進(jìn)行展開解釋：

** （1） GBDT二分類**

我們上面也講到了，GBDT本質(zhì)上就是一系列弱學(xué)習(xí)器之和：

而GBDT分類跟邏輯回歸的思路是類似的，將的作為下列函數(shù)的輸入，便可以得到類別概率值：

假設(shè)樣本獨(dú)立且同分布，極大似然估計(jì)(即選取合適的參數(shù)使被選取的樣本在總體中出現(xiàn)的可能性最大)的損失函數(shù)為：

為了方便對(duì)損失函數(shù)求導(dǎo)，會(huì)加入對(duì)數(shù)，求最大對(duì)數(shù)似然估計(jì)：

上面的損失函數(shù)并非最終的函數(shù)，而是最大似然估計(jì)函數(shù)（數(shù)值越大越好），由于損失函數(shù)應(yīng)該使越小越好，所以要對(duì)上面的L取相反數(shù)，同時(shí)為了得到平均到每個(gè)樣本的損失值，要除以樣本數(shù)N，這樣得到了最終的損失函數(shù)：

對(duì)損失函數(shù)計(jì)算負(fù)梯度：

由此看來，GBDT負(fù)梯度即為殘差，表示真實(shí)概率和預(yù)測(cè)概率的差值。接下來計(jì)算過程跟著GBDT通用框架進(jìn)行就好了。

** （2） GBDT多分類**

GBDT多分類原理跟Softmax一樣的，假設(shè)我們有k個(gè)類別，將作為以下函數(shù)的輸入，便可以類別q對(duì)應(yīng)的概率值：

其損失函數(shù)為：

多類別任務(wù)下，只有一個(gè)類別是1，其余為0，假設(shè)這不為0的一類為q，我們對(duì)它Softmax的損失函數(shù)求負(fù)梯度得：

跟二分類一樣，本質(zhì)上負(fù)梯度就是真實(shí)概率和預(yù)測(cè)概率的插值。

三、其它

第三部分講下GBDT的其它內(nèi)容：

1. 正則化

2. 優(yōu)缺點(diǎn)

3. 與RF的對(duì)比

1. 正則化

GBDT采用了三種正則化手段：

（1）學(xué)習(xí)率v和樹數(shù)量M的平衡

我們前面得到，第m輪下的強(qiáng)學(xué)習(xí)器 = 第m-1輪下的強(qiáng)學(xué)習(xí)器 + 第m輪的弱學(xué)習(xí)器，如下：

GBDT原論文提到，樹數(shù)量越多，越容易過擬合，所以限制樹數(shù)量可以避免過擬合，但歷史研究又給出：通過收縮 (即學(xué)習(xí)率v減少) 實(shí)現(xiàn)的正則化比通過限制項(xiàng) (即樹數(shù)量M減少) 實(shí)現(xiàn)的正則化效果更好。這是什么意思呢？請(qǐng)先看下面的公式：

該公式加入了學(xué)習(xí)率v，這里跟神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)率相反，如果我們學(xué)習(xí)率下降，每個(gè)樹的貢獻(xiàn)就會(huì)減低，反而還實(shí)現(xiàn)了正則化，但如果我們放開訓(xùn)練(即不固定樹數(shù)量)，只減低學(xué)習(xí)率的話，GBDT還是會(huì)過擬合，因?yàn)楫a(chǎn)生了更多的樹。因此，GBDT作者建議，我們要實(shí)現(xiàn)v-M之間的權(quán)衡，理想的應(yīng)該是在正則效果合適下，學(xué)習(xí)率降低的同時(shí)，也能盡可能保證樹數(shù)量少些。這里當(dāng)然也有出于對(duì)計(jì)算資源的考慮，增加M會(huì)帶來計(jì)算開銷。

（2）子采樣比例

子采樣是將原數(shù)據(jù)集中抽樣一定的樣本去擬合GBDT。與隨機(jī)森林不同的是，GBDT采樣不放回抽樣，因?yàn)镚BDT串行訓(xùn)練要求所有弱學(xué)習(xí)器使用同一套樣本集，不然在不同抽樣樣本空間計(jì)算的殘差，缺乏一致性。

（3）決策樹常用正則化手段

這塊的參數(shù)都涉及到弱學(xué)習(xí)器樹本身的正則化，例如：決策樹最大深度、劃分所需最少樣本數(shù)、葉子節(jié)點(diǎn)最少樣本數(shù)、葉子節(jié)點(diǎn)最小樣本權(quán)重、最大葉子節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)劃分最小不純度等。

2. 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 采用基于“殘差”(嚴(yán)格來說是負(fù)梯度)的Boosting集成手段。
• 適用于回歸、二分類和多分類任務(wù)。
• 預(yù)測(cè)精度比RF高。
• 對(duì)異常值的魯棒性強(qiáng)（采用了Huber損失和分位數(shù)損失）。

缺點(diǎn)：

• 串行方式的模型訓(xùn)練，難并行，造成計(jì)算開銷。
• 不適合高維稀疏離散特征。這是決策樹的痛點(diǎn)，比如動(dòng)物類別采用one-hot編碼后，會(huì)產(chǎn)生是否為狗，是否為貓一系列特征，而若這一系列特征中大量樣本為狗，其它動(dòng)物很少，那么樹在劃分屬性時(shí)，很容易就劃分為“是否為狗”，從而產(chǎn)生過擬合，它不像LR等線性模型f(w,x)的正則化權(quán)重是對(duì)樣本懲罰（可以實(shí)現(xiàn)對(duì)狗樣本給與更大的懲罰項(xiàng)），而樹的懲罰項(xiàng)往往是樹結(jié)構(gòu)相關(guān)的，因此樣本層面的懲罰較小，使得在高維稀疏特征時(shí)，GBDT表現(xiàn)不好。

3. 與RF的對(duì)比

[4] 總結(jié)的很好，我就不重復(fù)造輪子了：

圖3：GBDT與RF的區(qū)別 [4]

四、代碼參考

scikit-learn已提供封裝好的庫(kù)直接調(diào)用就好了，受限于篇幅，這里不詳細(xì)展開，詳見官方文檔 [6]。

from sklearn.datasets import make_regression
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.model_selection import train_test_split


X, y = make_regression(random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
reg = GradientBoostingRegressor(random_state=0)
reg.fit(X_train, y_train)
reg.predict(X_test[1:2])
reg.score(X_test, y_test)