引言

上一節(jié)中介紹了《隨機(jī)森林算法》，該算法使用bagging的方式作出一些決策樹來，同時在決策樹的學(xué)習(xí)過程中加入了更多的隨機(jī)因素。該模型可以自動做到驗(yàn)證過程同時還可以進(jìn)行特征選擇。
這一節(jié)，我們將決策樹和AdaBoost算法結(jié)合起來，在AdaBoost中每一輪迭代，都會給數(shù)據(jù)更新一個權(quán)重，利用這個權(quán)重，我們學(xué)習(xí)得到一個g，在這里我們得到一個決策樹，最終利用線性組合的方式得到多個決策樹組成的G。

1. 加權(quán)的決策樹算法(Weighted Decision Tree Algorithm)

在引言中介紹了，我們利用AdaBoost的思想，為數(shù)據(jù)賦予不同的權(quán)重，而在將要介紹的Adaptive Boosted Decision Tree中，要建立加權(quán)的決策樹，所以接下來就要介紹它。
在之前含有權(quán)重的算法中，權(quán)重作為衡量數(shù)據(jù)重要性的一項(xiàng)指標(biāo)，用來評估訓(xùn)練誤差，如下面的公式所示：

上面的公式中，權(quán)重是包含在誤差的公式中的，也就是說，我們想要構(gòu)造一個帶有權(quán)重的決策樹算法，需要改造決策樹的誤差度量函數(shù)。然而換一個角度，權(quán)重也可以等效于數(shù)據(jù)的重復(fù)次數(shù)，重復(fù)次數(shù)越多的數(shù)據(jù)，說明其越重要。在廣義的隨機(jī)算法中，我們可以根據(jù)權(quán)重比例來進(jìn)行隨機(jī)采樣（比如，如果權(quán)重比例是30%，那么采樣該數(shù)據(jù)的概率就是30%），根據(jù)這種方式得到一組新的數(shù)據(jù)，那么這組新的數(shù)據(jù)中的比例大概就是和權(quán)重的比例呈正比的，也就是說它能夠表達(dá)權(quán)重對于數(shù)據(jù)的意義。

在AdaBoost-DTree中，為了簡單起見，我們不去改變AdaBoost的框架，也不去修改決策樹的內(nèi)部細(xì)節(jié)，而只是通過基于權(quán)重的訓(xùn)練數(shù)據(jù)的采樣來實(shí)現(xiàn)。

1.1 弱決策樹算法

在AdaBoost算法中，我們通過錯誤率εt來計(jì)算單個的g的權(quán)重αt，那么如果我們使用決策樹作為g的時候，g是一個完全長成的樹，該樹對整個數(shù)據(jù)集進(jìn)行細(xì)致的切分導(dǎo)致Ein=0，那么這使得εt=0，但計(jì)算得到的權(quán)重αt會變成無限大。
其意義是，如果使用一個能力很強(qiáng)的樹作為g的話，那么該算法會賦予該樹無限大的權(quán)重或票數(shù)，最終得到了一棵“獨(dú)裁”的樹（因?yàn)锳daBoost的哲學(xué)意義是庶民政治，就是集中多方的意見，及時有的意見可能是錯誤的），違背了AdaBoost的宗旨。

上面的問題出在使用了所有的數(shù)據(jù)和讓樹完全長成這兩方面。針對這兩個問題，我們要通過剪枝和部分訓(xùn)練數(shù)據(jù)得到一個弱一點(diǎn)的樹。
所以實(shí)際上，AdaBoost-DTree是通過sampling的方式得到部分訓(xùn)練數(shù)據(jù)，通過剪枝的方式限制樹的高度，得到弱一點(diǎn)的決策樹。

1.2 AdaBoost-Stump

什么樣是樹才是弱決策樹呢？
我們這里限制這棵樹只有一層，即決策樁(Decision Stump)。這樣我們需要讓CART樹的不純度(impurity)盡可能低，學(xué)習(xí)一個決策樁。

所以，使用決策樁作為弱分類器的AdaBoost稱為AdaBoost-Stump，它是一種特殊的AdaBoost-DTree。

2. AdaBoost深入解釋和最佳化

我們回顧一下AdaBoost算法流程：

其中權(quán)重un(t+1)通過◆t對un(t)進(jìn)行修正得到，由于◆t是一個大于1的數(shù)，對錯誤數(shù)據(jù)加大權(quán)重以讓算法更加重視錯分的數(shù)據(jù)。
我們可以用下面的方式來描述un(t+1)：

下面的公式是我們將un(T+1)展開，我們看到圖中橘色的部分∑αt·gt(xn)是G(x)中的分?jǐn)?shù)，它出現(xiàn)在AdaBoost的權(quán)重的表達(dá)式中，我們稱∑αt·gt(xn)為投票分?jǐn)?shù)(voting score)。

所以，AdaBoost里面每一個數(shù)據(jù)的權(quán)重，和exp(-yn(voting score on xn))呈正比。

2.1 投票分?jǐn)?shù)(Voting Score)和間隔(Margin)的關(guān)系

線性混合(linear blending)等價于將假設(shè)看做是特征轉(zhuǎn)換的線性模型：

其中αt·gt(xn)如果換作是wT·φ(xn)可能就更清楚了，這與下面給出的在SVM中的margin表達(dá)式對比，我們可以明白投票分?jǐn)?shù)∑αt·gt(xn)的物理意義，即可以看做是沒有正規(guī)化的邊界(margin)。

所以，yn(voting score)是有符號的、沒有正規(guī)化的邊界距離，從這個角度來說，我們希望yn(voting score)越大越好，因?yàn)檫@樣的泛化能力越強(qiáng)。于是，exp(-yn(voting score))越小越好，那么un(T+1)越小越好。

AdaBoost在迭代過程中，是讓∑un(t)越來越小的過程，在這個過程中，逐漸達(dá)到SVM中最大分類間隔的效果。

2.2 AdaBoost誤差函數(shù)

上面解釋到了，AdaBoost在迭代學(xué)習(xí)的過程，就是希望讓∑un(t)越來越小的過程，那么我們新的目標(biāo)就是最佳化∑un(T+1)：

我們可以畫出0/1錯誤和AdaBoost誤差函數(shù)err(s,y) = exp(-ys)的函數(shù)曲線，我們發(fā)現(xiàn)AdaBoost的誤差函數(shù)（稱為exponential error measure）實(shí)際上也是0/1錯誤函數(shù)的上限函數(shù)，于是，我們可以通過最小化該函數(shù)來起到最佳化的效果。

2.3 AdaBoost誤差函數(shù)的梯度下降求解

為了最小化AdaBoost的誤差函數(shù)Ein，我們可以將Ein函數(shù)在所在點(diǎn)的附近做泰勒展開，我們就可以發(fā)現(xiàn)在該點(diǎn)的附近可以被梯度所描述，我們希望求一個最好的方向（最大梯度相反的方向），然后在該方向上走一小步，這樣我們就可以做到比現(xiàn)在的函數(shù)效果好一點(diǎn)點(diǎn)，依次進(jìn)行梯度下降，最終達(dá)到最小化誤差函數(shù)的效果。

現(xiàn)在我們把gt當(dāng)做方向，希望去找到這個gt（這里函數(shù)方向gt和上面介紹的最大梯度的方向向量沒有什么差別，只是表示方式有所不同而已）。

我們解釋一下上面的公式：

• 我們需要找到一個新的函數(shù)，這里表示為h(xn)和步長η，將這個函數(shù)加入到表達(dá)式中去；
• 我們將第一個公式中紫色的部分合起來，簡化表示為權(quán)重un(t)；
• 將exp(-y·η·h(xn))在原點(diǎn)處做泰勒展開，得到(1-yn·η·h(xn))；
• 然后拆成兩部分∑un(t)和η·∑un(t)·yn·h(xn)，第一部分是Ein，第二部分就是要最小化的目標(biāo)。
  

我們對∑un(t)·yn·h(xn)整理一下，對于二元分類情形，我們把yn和h(xn)是否同號進(jìn)行分別討論：

上面的公式中，我們特意將∑un(t)·yn·h(xn)拆成-∑un(t)和Ein(h)的形式，這里最小化Ein對應(yīng)于AdaBoost中的A（弱學(xué)習(xí)算法），好的弱學(xué)習(xí)算法就是對應(yīng)于梯度下降的函數(shù)方向。

2.4 最佳化步長η

我們要最小化Eada，需要找到好的函數(shù)方向gt，但是得打這個gt的代價有些大，梯度下降的過程中，每走一小步，就需要計(jì)算得到一個gt。如果轉(zhuǎn)換一下思路，我們現(xiàn)在已經(jīng)確定了好的gt，我們希望快速找到梯度下降的最低點(diǎn)，那么我們需要找到一個合適的最大步長η。

我們這里使用貪心算法來得到最大步長η，稱為steepest decent for optimization。

讓Eada對η求偏微分，得到最陡時候的ηt，我們發(fā)現(xiàn)這時ηt等于AdaBoost的αt。所以在AdaBoost中αt是在偷偷地做最佳化的工作。

2.5 小結(jié)

在第二小節(jié)中，我們從另外一個角度介紹了AdaBoost算法，它其實(shí)是steepest gradient decent。

上面的式子很清楚了，我們將AdaBoost的誤差函數(shù)看做是指數(shù)誤差函數(shù)，AdaBoost就是在這個函數(shù)上一步一步做最佳化，每一步求得一個h，并將該h當(dāng)做是gt，決定這個gt上面要走多長的距離ηt，最終得到這個gt的票數(shù)αt。

3. 梯度提升(Gradient Boosting)

梯度提升是對AdaBoost的延伸，它不再要求誤差函數(shù)是指數(shù)誤差函數(shù)，而可能是任意一種誤差函數(shù)（因?yàn)檫@里是用梯度下降法來最佳化誤差函數(shù)，所以這里要求誤差函數(shù)是平滑的）。

在這個架構(gòu)下，我們就可以使用不同的假設(shè)和模型，來解決分類或者回歸的問題。

3.1 梯度提升應(yīng)用于回歸問題

梯度提升應(yīng)用于回歸問題時，誤差函數(shù)選中均方誤差函數(shù)。

緊接著，我們對這個誤差函數(shù)中變量s在sn處進(jìn)行一階泰勒展開的近似，我們發(fā)現(xiàn)要最小化的實(shí)際是∑h(xn)·2(sn-yn)，要讓該表達(dá)式最小，需要h(xn)和(sn-yn)的方向相反：

要求解最佳化問題，需要h(xn)和(sn-yn)的方向相反，而h(xn)的大小其實(shí)不是我們關(guān)系的問題，因?yàn)椴介L問題是由參數(shù)η決定的。
如果將h(xn)強(qiáng)制限制為1或者某個常數(shù)的話，那么就得到了一個有條件的最佳化問題，增加了求解的難度。不如我們將懲罰項(xiàng)h(xn)的平方放進(jìn)最佳化式子中（意思是，如果h(xn)越大，我們就越不希望如此）。
我們可以將平方式子變換一下，得到有關(guān)(h(xn)-(yn-sn))^2的式子，所以我們要求一個帶懲罰項(xiàng)的近似函數(shù)梯度的問題，就等效于求xn和余數(shù)(residual)yn-sn的回歸問題。

確定步長η：

我們現(xiàn)在確定了gt，接著我們要確定步長η，這里我們可以將誤差函數(shù)寫成余數(shù)(yn-sn)的形式，這是一個單變量的線性回歸問題，其中輸入是用gt轉(zhuǎn)換后的數(shù)據(jù)，輸出是余數(shù)(residual)。

4. 梯度提升決策樹

綜合第三小節(jié)的步驟，我們就可以得到梯度提升決策樹的算法流程：

• 在每一次迭代過程，解決一個回歸問題，這里可以用CART算法來解{xn, (yn-sn)}的回歸問題；
• 然后，用gt做轉(zhuǎn)換，做一個{gt(xn), yn-sn}的單變量線性回歸問題；
• 更新分?jǐn)?shù)sn；
• 經(jīng)過T輪迭代，得到G(x)。
  這個GBDT算法可以看做是AdaBoost-DTree的回歸問題版本。

參考資料

機(jī)器學(xué)習(xí)技法課程，林軒田，臺灣大學(xué)
決策樹模型組合之隨機(jī)森林與GBDT
機(jī)器學(xué)習(xí)——Gradient Boost Decision Tree(&Treelink)

轉(zhuǎn)載請注明作者Jason Ding及其出處
GitCafe博客主頁(http://jasonding1354./)
Github博客主頁(http://jasonding1354./)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進(jìn)入我的博客主頁