[原]【機器學習基礎】梯度提升決策樹

上一節中介紹了 《隨機森林算法》 ，該算法使用bagging的方式作出一些決策樹來，同時在決策樹的學習過程中加入了更多的隨機因素。該模型可以自動做到驗證過程同時還可以進行特征選擇。

這一節，我們將決策樹和AdaBoost算法結合起來，在AdaBoost中每一輪迭代，都會給數據更新一個權重，利用這個權重，我們學習得到一個g，在這里我們得到一個決策樹，最終利用線性組合的方式得到多個決策樹組成的G。

在引言中介紹了，我們利用AdaBoost的思想，為數據賦予不同的權重，而在將要介紹的Adaptive Boosted Decision Tree中，要建立加權的決策樹，所以接下來就要介紹它。

在之前含有權重的算法中，權重作為衡量數據重要性的一項指標，用來評估訓練誤差，如下面的公式所示：

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

在AdaBoost-DTree中，為了簡單起見，我們不去改變AdaBoost的框架，也不去修改決策樹的內部細節，而只是通過基于權重的訓練數據的采樣來實現。

在AdaBoost算法中，我們通過錯誤率εt來計算單個的g的權重αt，那么如果我們使用決策樹作為g的時候，g是一個完全長成的樹，該樹對整個數據集進行細致的切分導致Ein=0，那么這使得εt=0，但計算得到的權重αt會變成無限大。

其意義是，如果使用一個能力很強的樹作為g的話，那么該算法會賦予該樹無限大的權重或票數，最終得到了一棵“獨裁”的樹（因為AdaBoost的哲學意義是庶民政治，就是集中多方的意見，及時有的意見可能是錯誤的），違背了AdaBoost的宗旨。

上面的問題出在使用了所有的數據和讓樹完全長成這兩方面。針對這兩個問題，我們要通過剪枝和部分訓練數據得到一個弱一點的樹。

所以實際上，AdaBoost-DTree是通過sampling的方式得到部分訓練數據，通過剪枝的方式限制樹的高度，得到弱一點的決策樹。

什么樣是樹才是弱決策樹呢？

我們這里限制這棵樹只有一層，即決策樁(Decision Stump)。這樣我們需要讓CART樹的不純度(impurity)盡可能低，學習一個決策樁。

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

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

其中權重un(t+1)通過◆t對un(t)進行修正得到，由于◆t是一個大于1的數，對錯誤數據加大權重以讓算法更加重視錯分的數據。

我們可以用下面的方式來描述un(t+1)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

梯度提升應用于回歸問題時，誤差函數選中均方誤差函數。

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

要求解最佳化問題，需要h(xn)和(sn-yn)的方向相反，而h(xn)的大小其實不是我們關系的問題，因為步長問題是由參數η決定的。

如果將h(xn)強制限制為1或者某個常數的話，那么就得到了一個有條件的最佳化問題，增加了求解的難度。不如我們將懲罰項h(xn)的平方放進最佳化式子中（意思是，如果h(xn)越大，我們就越不希望如此）。

我們可以將平方式子變換一下，得到有關(h(xn)-(yn-sn))^2的式子，所以我們要求一個帶懲罰項的近似函數梯度的問題，就等效于求xn和余數(residual)yn-sn的回歸問題。

確定步長η：

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

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

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

機器學習技法課程，林軒田，臺灣大學