我的CSDN博客地址：紅色石頭的專欄

我的知乎主頁：紅色石頭 我的微博：RedstoneWill的微博 我的GitHub：RedstoneWill的GitHub 我的微信公眾號：紅色石頭的機器學習之路（ID：redstonewill）

歡迎大家關注我！共同學習，共同進步！

上節課我們主要介紹了Random Forest演算法模型。Random Forest就是通過bagging的方式將許多不同的decision tree組合起來。除此之外，在decision tree中加入了各種隨機性和多樣性，比如不同特徵的線性組合等。RF還可以使用OOB樣本進行self-validation，而且可以通過permutation test進行feature selection。本節課將使用Adaptive Boosting的方法來研究decision tree的一些演算法和模型。

1. Adaptive Boosted Decision Tree

Random Forest的演算法流程我們上節課也詳細介紹過，就是先通過bootstrapping「複製」原樣本集D，得到新的樣本集D』；然後對每個D』進行訓練得到不同的decision tree和對應的 g_t ；最後再將所有的 g_t 通過uniform的形式組合起來，即以投票的方式得到G。這裡採用的Bagging的方式，也就是把每個 g_t 的預測值直接相加。現在，如果將Bagging替換成AdaBoost，處理方式有些不同。首先每輪bootstrap得到的D』中每個樣本會賦予不同的權重 u^{(t)} ；然後在每個decision tree中，利用這些權重訓練得到最好的 g_t ；最後得出每個 g_t 所佔的權重，線性組合得到G。這種模型稱為AdaBoost-D Tree。

但是在AdaBoost-DTree中需要注意的一點是每個樣本的權重 u^{(t)} 。我們知道，在Adaptive Boosting中進行了bootstrap操作， u^{(t)} 表示D中每個樣本在D』中出現的次數。但是在決策樹模型中，例如C&RT演算法中並沒有引入 u^{(t)} 。那麼，如何在決策樹中引入這些權重 u^{(t)} 來得到不同的 g_t 而又不改變原來的決策樹演算法呢？

在Adaptive Boosting中，我們使用了weighted algorithm，形如：

E_{in}^u(h)=frac1Nsum_{n=1}^Nu_ncdot err(y_n,h(x_n))

每個犯錯誤的樣本點乘以相應的權重，求和再平均，最終得到了 E_{in}^u(h)。如果在決策樹中使用這種方法，將當前分支下犯錯誤的點賦予權重，每層分支都這樣做，會比較複雜，不易求解。為了簡化運算，保持決策樹演算法本身的穩定性和封閉性，我們可以把決策樹演算法當成一個黑盒子，即不改變其結構，不對演算法本身進行修改，而從數據來源D』上做一些處理。按照這種思想，我們來看權重u實際上表示該樣本在bootstrap中出現的次數，反映了它出現的概率。那麼可以根據u值，對原樣本集D進行一次重新的隨機sampling，也就是帶權重的隨機抽樣。sampling之後，會得到一個新的D』，D』中每個樣本出現的幾率與它權重u所佔的比例應該是差不多接近的。因此，使用帶權重的sampling操作，得到了新的樣本數據集D』，可以直接代入決策樹進行訓練，從而無需改變決策樹演算法結構。sampling可看成是bootstrap的反操作，這種對數據本身進行修改而不更改演算法結構的方法非常重要！

所以，AdaBoost-DTree結合了AdaBoost和DTree，但是做了一點小小的改變，就是使用sampling替代權重 u^{(t)} ，效果是相同的。

上面我們通過使用sampling，將不同的樣本集代入決策樹中，得到不同的 g_t 。除此之外，我們還要確定每個 g_t 所佔的權重 alpha_t 。之前我們在AdaBoost中已經介紹過，首先算出每個 g_t 的錯誤率 epsilon_t ，然後計算權重：

alpha_t=ln diamond_t=ln sqrt{frac{1-epsilon_t}{epsilon_t}}

如果現在有一棵完全長成的樹（fully grown tree），由所有的樣本 x_n 訓練得到。若每個樣本都不相同的話，一刀刀切割分支，直到所有的 x_n 都被完全分開。這時候， E_{in}(g_t)=0 ，加權的 E_{in}^u(g_t)=0 而且 epsilon_t 也為0，從而得到權重 alpha_t=infty 。 alpha_t=infty 表示該 g_t 所佔的權重無限大，相當於它一個就決定了G結構，是一種autocracy，而其它的 g_t 對G沒有影響。

顯然 alpha_t=infty 不是我們想看到的，因為autocracy總是不好的，我們希望使用aggregation將不同的 g_t 結合起來，發揮集體智慧來得到最好的模型G。首先，我們來看一下什麼原因造成了 alpha_t=infty 。有兩個原因：一個是使用了所有的樣本 x_n 進行訓練；一個是樹的分支過多，fully grown。針對這兩個原因，我們可以對樹做一些修剪（pruned），比如只使用一部分樣本，這在sampling的操作中已經起到這類作用，因為必然有些樣本沒有被採樣到。除此之外，我們還可以限制樹的高度，讓分支不要那麼多，從而避免樹fully grown。

因此，AdaBoost-DTree使用的是pruned DTree，也就是說將這些預測效果較弱的樹結合起來，得到最好的G，避免出現autocracy。

剛才我們說了可以限制樹的高度，那索性將樹的高度限制到最低，即只有1層高的時候，有什麼特性呢？當樹高為1的時候，整棵樹只有兩個分支，切割一次即可。如果impurity是binary classification error的話，那麼此時的AdaBoost-DTree就跟AdaBoost-Stump沒什麼兩樣。也就是說AdaBoost-Stump是AdaBoost-DTree的一種特殊情況。

值得一提是，如果樹高為1時，通常較難遇到 epsilon_t=0 的情況，且一般不採用sampling的操作，而是直接將權重u代入到演算法中。這是因為此時的AdaBoost-DTree就相當於是AdaBoost-Stump，而AdaBoost-Stump就是直接使用u來優化模型的。

2. Optimization View of AdaBoost

接下來，我們繼續將繼續探討AdaBoost演算法的一些奧妙之處。我們知道AdaBoost中的權重的迭代計算如下所示：

之前對於incorrect樣本和correct樣本， u_n^{(t+1)} 的表達式不同。現在，把兩種情況結合起來，將 u_n^{(t+1)} 寫成一種簡化的形式：

u_n^{(t+1)}=u_n^{(t)}cdot diamond_t^{-y_ng_t(x_n)}=u_n^{(t)}cdot exp(-y_nalpha_tg_t(x_n))

其中，對於incorrect樣本， y_ng_t(x_n)<0 ，對於correct樣本， y_ng_t(x_n)>0 。從上式可以看出， u_n^{(t+1)} 由 u_n^{(t)} 與某個常數相乘得到。所以，最後一輪更新的 u_n^{(T+1)} 可以寫成 u_n^{(1)} 的級聯形式，我們之前令 u_n^{(1)}=frac1N ，則有如下推導：

u_n^{(T+1)}=u_n^{(1)}cdot prod_{t=1}^Texp(-y_nalpha_tg_t(x_n))=frac1Ncdot exp(-y_nsum_{t=1}^Talpha_tg_t(x_n))

上式中 sum_{t=1}^Talpha_tg_t(x_n) 被稱為voting score，最終的模型 G=sign(sum_{t=1}^Talpha_tg_t(x_n)) 。可以看出，在AdaBoost中， u_n^{(T+1)} 與 exp(-y_n(voting score on x_n)) 成正比。

接下來我們繼續看一下voting score中蘊含了哪些內容。如下圖所示，voting score由許多 g_t(x_n) 乘以各自的係數 alpha_t 線性組合而成。從另外一個角度來看，我們可以把 g_t(x_n) 看成是對 x_n 的特徵轉換 phi_i(x_n) ， alpha_t 就是線性模型中的權重 w_i 。看到這裡，我們回憶起之前SVM中，w與 phi (x_n) 的乘積再除以w的長度就是margin，即點到邊界的距離。另外，乘積項再與 y_n 相乘，表示點的位置是在正確的那一側還是錯誤的那一側。所以，回過頭來，這裡的voting score實際上可以看成是沒有正規化（沒有除以w的長度）的距離，即可以看成是該點到分類邊界距離的一種衡量。從效果上說，距離越大越好，也就是說voting score要儘可能大一些。

我們再來看，若voting score與 y_n 相乘，則表示一個有對錯之分的距離。也就是說，如果二者相乘是負數，則表示該點在錯誤的一邊，分類錯誤；如果二者相乘是正數，則表示該點在正確的一邊，分類正確。所以，我們演算法的目的就是讓 y_n 與voting score的乘積是正的，而且越大越好。那麼在剛剛推導的 u_n^{(T+1)} 中，得到 exp(-y_n(voting score)) 越小越好，從而得到 u_n^{(T+1)} 越小越好。也就是說，如果voting score表現不錯，與 y_n 的乘積越大的話，那麼相應的 u_n^{(T+1)} 應該是最小的。

那麼在AdaBoost中，隨著每輪學習的進行，每個樣本的 u_n^{(t)} 是逐漸減小的，直到 u_n^{(T+1)} 最小。以上是從單個樣本點來看的。總體來看，所有樣本的 u_n^{(T+1)} 之和應該也是最小的。我們的目標就是在最後一輪（T+1）學習後，讓所有樣本的 u_n^{(T+1)} 之和儘可能地小。 u_n^{(T+1)} 之和表示為如下形式：

上式中， sum_{t=1}^Talpha_tg_t(x_n) 被稱為linear score，用s表示。對於0/1 error：若ys<0，則 err_{0/1}=1 ；若ys>=0，則 err_{0/1}=0 。如下圖右邊黑色折線所示。對於上式中提到的指數error，即 hat{err}_{ADA}(s,y)=exp(-ys) ，隨著ys的增加，error單調下降，且始終落在0/1 error折線的上面。如下圖右邊藍色曲線所示。很明顯， hat{err}_{ADA}(s,y) 可以看成是0/1 error的上界。所以，我們可以使用 hat{err}_{ADA}(s,y) 來替代0/1 error，能達到同樣的效果。從這點來說， sum_{n=1}^Nu_n^{(T+1)} 可以看成是一種error measure，而我們的目標就是讓其最小化，求出最小值時對應的各個 alpha_t 和 g_t(x_n) 。

下面我們來研究如何讓 sum_{n=1}^Nu_n^{(T+1)} 取得最小值，思考是否能用梯度下降（gradient descent）的方法來進行求解。我們之前介紹過gradient descent的核心是在某點處做一階泰勒展開：

其中， w_t 是泰勒展開的位置，v是所要求的下降的最好方向，它是梯度 abla E_{in}(w_t) 的反方向，而 eta 是每次前進的步長。則每次沿著當前梯度的反方向走一小步，就會不斷逼近谷底（最小值）。這就是梯度下降演算法所做的事情。

現在，我們對 check{E}_{ADA} 做梯度下降演算法處理，區別是這裡的方向是一個函數 g_t ，而不是一個向量 w_t 。其實，函數和向量的唯一區別就是一個下標是連續的，另一個下標是離散的，二者在梯度下降演算法應用上並沒有大的區別。因此，按照梯度下降演算法的展開式，做出如下推導：

上式中， h(x_n) 表示當前的方向，它是一個矩， eta 是沿著當前方向前進的步長。我們要求出這樣的 h(x_n) 和 eta ，使得 check{E}_{ADA} 是在不斷減小的。當 check{E}_{ADA} 取得最小值的時候，那麼所有的方向即最佳的 h(x_n) )和 eta 就都解出來了。上述推導使用了在 -y_neta h(x_n)=0 處的一階泰勒展開近似。這樣經過推導之後， check{E}_{ADA} 被分解為兩個部分，一個是前N個u之和 sum_{n=1}^Nu_n^{(t)} ，也就是當前所有的 E_{in} 之和；另外一個是包含下一步前進的方向 h(x_n) 和步進長度 eta 的項 -etasum_{n=1}^Nu_n^{(t)}y_nh(x_n) 。 check{E}_{ADA} 的這種形式與gradient descent的形式基本是一致的。

那麼接下來，如果要最小化 check{E}_{ADA} 的話，就要讓第二項 -etasum_{n=1}^Nu_n^{(t)}y_nh(x_n) 越小越好。則我們的目標就是找到一個好的 h(x_n) （即好的方向）來最小化 sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) ，此時先忽略步進長度 eta 。

對於binary classification， y_n 和 h(x_n) 均限定取值-1或+1兩種。我們對 sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) 做一些推導和平移運算：

最終 sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) 化簡為兩項組成，一項是 -sum_{n=1}^Nu_n^{(t)} ；另一項是 2E_{in}^{u(t)}(h)cdot N 。則最小化 sum_{n=1}^Nu_n^{(t)}(-y_nh(x_n)) 就轉化為最小化 E_{in}^{u(t)}(h) 。要讓 E_{in}^{u(t)}(h) 最小化，正是由AdaBoost中的base algorithm所做的事情。所以說，AdaBoost中的base algorithm正好幫我們找到了梯度下降中下一步最好的函數方向。

以上就是從數學上，從gradient descent角度驗證了AdaBoost中使用base algorithm得到的 g_t 就是讓 check{E}_{ADA} 減小的方向，只不過這個方向是一個函數而不是向量。

在解決了方向問題後，我們需要考慮步進長度 eta 如何選取。方法是在確定方向 g_t 後，選取合適的 eta ，使 check{E}_{ADA} 取得最小值。也就是說，把 check{E}_{ADA} 看成是步進長度 eta 的函數，目標是找到 check{E}_{ADA} 最小化時對應的 eta 值。

目的是找到在最佳方向上的最大步進長度，也就是steepest decent。我們先把 check{E}_{ADA} 表達式寫下來：

check{E}_{ADA}=sum_{n=1}^Nu_n^{(t)}exp(-y_neta g_t(x_n))

上式中，有兩種情況需要考慮：

  • y_n=g_t(x_n) ： u_n^{(t)}exp(-eta) correct
  • y_n eq g_t(x_n) ： u_n^{(t)}exp(+eta) incorrect

經過推導，可得：

check{E}_{ADA}=(sum_{n=1}^Nu_n^{(t)})cdot ((1-epsilon_t)exp(-eta)+epsilon_t exp(+eta))

然後對 eta 求導，令 frac{partial check{E}_{ADA}}{partial eta}=0 ，得：

eta_t=lnsqrt{frac{1-epsilon_t}{epsilon_t}}=alpha_t

由此看出，最大的步進長度就是 alpha_t ，即AdaBoost中計算 g_t 所佔的權重。所以，AdaBoost演算法所做的其實是在gradient descent上找到下降最快的方向和最大的步進長度。這裡的方向就是 g_t ，它是一個函數，而步進長度就是 alpha_t 。也就是說，在AdaBoost中確定 g_t 和 alpha_t 的過程就相當於在gradient descent上尋找最快的下降方向和最大的步進長度。

3. Gradient Boosting

前面我們從gradient descent的角度來重新介紹了AdaBoost的最優化求解方法。整個過程可以概括為：

以上是針對binary classification問題。如果往更一般的情況進行推廣，對於不同的error function，比如logistic error function或者regression中的squared error function，那麼這種做法是否仍然有效呢？這種情況下的GradientBoost可以寫成如下形式：

仍然按照gradient descent的思想，上式中， h(x_n) 是下一步前進的方向， eta 是步進長度。此時的error function不是前面所講的exp了，而是任意的一種error function。因此，對應的hypothesis也不再是binary classification，最常用的是實數輸出的hypothesis，例如regression。最終的目標也是求解最佳的前進方向 h(x_n) 和最快的步進長度 eta 。

接下來，我們就來看看如何求解regression的GradientBoost問題。它的表達式如下所示：

利用梯度下降的思想，我們把上式進行一階泰勒展開，寫成梯度的形式：

上式中，由於regression的error function是squared的，所以，對s的導數就是 2(s_n-y_n) 。其中標註灰色的部分表示常數，對最小化求解並沒有影響，所以可以忽略。很明顯，要使上式最小化，只要令 h(x_n) 是梯度 2(s_n-y_n) 的反方向就行了，即 h(x_n)=-2(s_n-y_n) 。但是直接這樣賦值，並沒有對 h(x_n) 的大小進行限制，一般不直接利用這個關係求出 h(x_n) 。

實際上 h(x_n) 的大小並不重要，因為有步進長度 eta 。那麼，我們上面的最小化問題中需要對 h(x_n) 的大小做些限制。限制 h(x_n) 的一種簡單做法是把 h(x_n) 的大小當成一個懲罰項（ h^2(x_n) ）添加到上面的最小化問題中，這種做法與regularization類似。如下圖所示，經過推導和整理，忽略常數項，我們得到最關心的式子是：

min sum_{n=1}^N((h(x_n)-(y_n-s_n))^2)

上式是一個完全平方項之和， y_n-s_n 表示當前第n個樣本真實值和預測值的差，稱之為餘數。餘數表示當前預測能夠做到的效果與真實值的差值是多少。那麼，如果我們想要讓上式最小化，求出對應的 h(x_n) 的話，只要讓 h(x_n) 儘可能地接近餘數 y_n-s_n 即可。在平方誤差上儘可能接近其實很簡單，就是使用regression的方法，對所有N個點 (x_n,y_n-s_n) 做squared-error的regression，得到的回歸方程就是我們要求的 g_t(x_n) 。

以上就是使用GradientBoost的思想來解決regression問題的方法，其中應用了一個非常重要的概念，就是餘數 y_n-s_n 。根據這些餘數做regression，得到好的矩 g_t(x_n) ，方向函數 g_t(x_n) 也就是由余數決定的。

在求出最好的方向函數 g_t(x_n) 之後，就要來求相應的步進長度 eta 。表達式如下：

同樣，對上式進行推導和化簡，得到如下表達式：

上式中也包含了餘數 y_n-s_n ，其中 g_t(x_n) 可以看成是 x_n 的特徵轉換，是已知量。那麼，如果我們想要讓上式最小化，求出對應的 eta 的話，只要讓 eta g_t(x_n) 儘可能地接近餘數 y_n-s_n 即可。顯然，這也是一個regression問題，而且是一個很簡單的形如y=ax的線性回歸，只有一個未知數 eta 。只要對所有N個點 (eta g_t(x_n),y_n-s_n) 做squared-error的linear regression，利用梯度下降演算法就能得到最佳的 eta 。

將上述這些概念合併到一起，我們就得到了一個最終的演演算法Gradient Boosted Decision Tree(GBDT)。可能有人會問，我們剛才一直沒有說到Decison Tree，只是講到了GradientBoost啊？下面我們來看看Decison Tree究竟是在哪出現並使用的。其實剛剛我們在計算方向函數 g_t 的時候，是對所有N個點 (x_n,y_n-s_n) 做squared-error的regression。那麼這個回歸演算法就可以是決策樹C&RT模型（決策樹也可以用來做regression）。這樣，就引入了Decision Tree，並將GradientBoost和Decision Tree結合起來，構成了真正的GBDT演算法。GBDT演算法的基本流程圖如下所示：

值得注意的是， s_n 的初始值一般均設為0，即 s_1=s_2=cdots =s_N=0 。每輪迭代中，方向函數 g_t 通過C&RT演算法做regression，進行求解；步進長度 eta 通過簡單的單參數線性回歸進行求解；然後每輪更新 s_n 的值，即 s_nleftarrow s_n+alpha_tg_t(x_n) 。T輪迭代結束後，最終得到 G(x)=sum_{t=1}^Talpha_tg_t(x) 。

值得一提的是，本節課第一部分介紹的AdaBoost-DTree是解決binary classification問題，而此處介紹的GBDT是解決regression問題。二者具有一定的相似性，可以說GBDT就是AdaBoost-DTree的regression版本。

4. Summary ofAggregation Models

從機器學習技法課程的第7節課筆記到現在的第11節課筆記，我們已經介紹完所有的aggregation模型了。接下來，我們將對這些內容進行一個簡單的總結和概括。

首先，我們介紹了blending。blending就是將所有已知的 g_t aggregate結合起來，發揮集體的智慧得到G。值得注意的一點是這裡的 g_t 都是已知的。blending通常有三種形式：

  • uniform：簡單地計算所有 g_t 的平均值
  • non-uniform：所有 g_t 的線性組合
  • conditional：所有 g_t 的非線性組合

其中，uniform採用投票、求平均的形式更注重穩定性；而non-uniform和conditional追求的更複雜準確的模型，但存在過擬合的危險。

剛才講的blending是建立在所有 g_t 已知的情況。那如果所有 g_t 未知的情況，對應的就是learning模型，做法就是一邊學 g_t ，一邊將它們結合起來。learning通常也有三種形式（與blending的三種形式一一對應）：

  • Bagging：通過bootstrap方法，得到不同 g_t ，計算所有 g_t 的平均值
  • AdaBoost：通過bootstrap方法，得到不同 g_t ，所有 g_t 的線性組合
  • Decision Tree：通過數據分割的形式得到不同的 g_t ，所有 g_t 的非線性組合

然後，本節課我們將AdaBoost延伸到另一個模型GradientBoost。對於regression問題，GradientBoost通過residual fitting的方式得到最佳的方向函數 g_t 和步進長度 eta 。

除了這些基本的aggregation模型之外，我們還可以把某些模型結合起來得到新的aggregation模型。例如，Bagging與Decision Tree結合起來組成了Random Forest。Random Forest中的Decision Tree是比較「茂盛」的樹，即每個樹的 eta 都比較強一些。AdaBoost與Decision Tree結合組成了AdaBoost-DTree。AdaBoost-DTree的Decision Tree是比較「矮弱」的樹，即每個樹的 eta 都比較弱一些，由AdaBoost將所有弱弱的樹結合起來，讓綜合能力更強。同樣，GradientBoost與Decision Tree結合就構成了經典的演算法GBDT。

Aggregation的核心是將所有的 g_t 結合起來，融合到一起，即集體智慧的思想。這種做法之所以能得到很好的模型G，是因為aggregation具有兩個方面的優點：cure underfitting和cure overfitting。

第一，aggregation models有助於防止欠擬合（underfitting）。它把所有比較弱的 g_t 結合起來，利用集體智慧來獲得比較好的模型G。aggregation就相當於是feature transform，來獲得複雜的學習模型。

第二，aggregation models有助於防止過擬合（overfitting）。它把所有 g_t 進行組合，容易得到一個比較中庸的模型，類似於SVM的large margin一樣的效果，從而避免一些極端情況包括過擬合的發生。從這個角度來說，aggregation起到了regularization的效果。

由於aggregation具有這兩個方面的優點，所以在實際應用中aggregation models都有很好的表現。

5. Summary

本節課主要介紹了Gradient Boosted Decision Tree。首先講如何將AdaBoost與Decision Tree結合起來，即通過sampling和pruning的方法得到AdaBoost-D Tree模型。然後，我們從optimization的角度來看AdaBoost，找到好的hypothesis也就是找到一個好的方向，找到權重 alpha 也就是找到合適的步進長度。接著，我們從binary classification的0/1 error推廣到其它的error function，從Gradient Boosting角度推導了regression的squared error形式。Gradient Boosting其實就是不斷迭代，做residual fitting。並將其與Decision Tree演算法結合，得到了經典的GBDT演算法。最後，我們將所有的aggregation models做了總結和概括，這些模型有的能防止欠擬合有的能防止過擬合，應用十分廣泛。

更多乾貨文章請關注公眾號：AI有道（ID：redstonewill）


推薦閱讀：
相關文章