提升方法學習(AdaBoost、GBDT與XGBoost)

提升(boosting)方法是一種常用的統計學習方法，應用廣泛且有效。

一、提升方法的基本思路

二、AdaBoost算法

1.Adaboost算法分析

2.AdaBoost算法的另一種解釋：

3.加法模型(additive model)                                     

4.前向分布算法(forward stagewise algorithm)

三、提升樹算法

1.提升樹模型

2.提升樹算法步驟

3.回歸樹的表示

4.回歸問題提升樹算法模型

5.回歸提升樹算法描述

四、梯度提升算法(GBDT)

1.梯度提升算法描述

五、XGBoost算法

1.xgboost的優化思路

2.XGBoost算法的學習過程

3.XGBoost建構步驟流程

六、總結

Boosting算法族

AdaBoost

回歸提升樹和AdaBoost

GBDT與回歸提升樹

七、參考文獻

一、提升方法的基本思路

思路：提升方法基于這樣一種思想：對于一個複雜任務來說，将多個專家的判斷進行适當的綜合得出的判斷要比其中任何一個專家單獨的判斷都好。也就是"三個臭皮匠，頂個諸葛亮"。

理論支援：在PAC(probably approximately correct)架構中，一個概念(類)，如果存在一個多項式的學習算法能夠學習它，并且正确率很高，那麼就稱這個概念是強可學習的；一個概念，如果存在一個多項式學習算法能夠學習它，學習的正确率僅比随機猜測好一點，那麼就成這個概念是弱可學習的。

後來Schapire證明強可學習與弱可學習是等價的。也就是說，在PAC架構下，一個概念是強可學習的充要條件是這個概念是弱可學習。

綜上我們可以通過內建一系列弱學習器來得到一個強學習器。

而發現一個弱學習算法比發現一個強學習算法容易的多。是以我們找到了一條曲線救國的路線：低成本得到多個弱學習算法，再通過組合這些弱學習算法将其提升成一個強學習算法。而具體如何進行提升就是我們需要解決的問題。

對于分類問題而言，給定一個訓練樣本集合，發現粗糙分類規則(弱分類器)比發現精确分類規則(強分類器)要容易的多。提升方法就是從弱學習算法出發，反複學習，得到一系列弱分類器，然後組合這些分類器，構成一個強分類器。大多數提升方法都是改變訓練資料的機率分布(訓練資料的權值分布)，針對不同的訓練資料分布調用若學習算法學習一系列弱分類器。

這樣提升方法需要解決兩個問題：

1. 如何獲得多個不同的弱分類器

2. 如何将多個弱分類器組合成一個強分類器

二、AdaBoost算法

AdaBoost(Adaptive Boosting--自适應增強)算法，是Boosting算法的一種實作。是一種二分類器，它使用若分類起的線性組合構造強分類器。

是以針對Bosting算法的兩個問題，AdaBoost算法的做法是：

1. 通過提高前一輪弱分類器錯誤分類樣本的權值，降低正确分類的樣本權值，進而得到不同的弱分類器

2. 采取權重多數表決的方式組合弱分類器。

     具體的：加大分類誤差率小的弱分類器的權值，降低分類錯誤率高的弱分類器 的權值。

AdaBoot就是依照上面兩種規則對Boosting算法的一種具體實作。

• AdaBoost算法是多個弱分類器的線性組合：

表示弱分類器的個數

表示第m個分類器    

為第m個弱分類器的表決權值(反應分類器的重要性)

1.Adaboost算法分析

輸入： 

輸出：分類器 

1.初始化訓練資料的權值分布

2. 

      a.使用具有權值分布

的訓練資料集學習，得到基本分類器

      b.計算

在訓練資料集上的分類誤差率

     c.計算

的系數

               這裡的對數是自然對數

     d.更新訓練資料集的權值分布

是規範化因子，它使

成為一個機率分布

3.建構基本分類器的線性組合

      得到最終分類器：

    以上是AdaBoost算法基本的分析，更詳細的讨論本文不再讨論。更詳細的分析和解釋大家可以參考李航老師 統計學習方法 第二版 P156~P162。

與GBDT、lambdaMART放在一起，本文更想讨論的是AdaBoost算法的另一種解釋。

2.AdaBoost算法的另一種解釋：

   可以認為AdaBoost算法是模型為加法模型、損失函數為指數函數、學習算法為前向分布算法的二類分類學習方法。

3.加法模型(additive model)

   其中，

為基函數，

為基函數的參數，

為基函數的系數。顯然上式是一個多個基模型進行線性累加的模型。在給定訓練資料及損失函數

條件下，學習加法模型

成為經驗風險極小化，即損失函數極小化問題：

   上式是一個複雜的優化問題。是以我們借助前向分步算法來求解這樣的問題。

4.前向分布算法(forward stagewise algorithm)

前向分步算法的思想是因為學習的是加法模型，如果能夠從前向後，每一步隻學習一個基函數及其系數，逐漸逼近優化目标函數式，這樣可以簡化優化的複雜度。具體來說，每步隻需優化如下損失函數：   

在給定訓練資料集，損失函數和基函數集合的情況下，前向分步算法學習加法模型的算法如下：

輸入：

；損失函數

；基函數集

輸出：加法模型

1.初始化

2. 對

    a.極小化損失函數

                   得到

    b.更新模型

3.得到加法模型

    用這種方式前向分布算法将同時求解從

到

所有參數的

的優化問題簡化為逐次求解各個

的優化問題。是以，當我們把AdaBoost中每一個弱學習器看成加法模型中的一個學習器時，AdaBoost可以看成一個特殊的加法模型，可以通過前向分步算法來學習該加法模型。

    關于AdaBoost的具體證明本文不再贅述，感興趣可以參考統計學習方法 第二版 P156~P162。

三、提升樹算法

1.提升樹模型

提升樹是以決策樹作為基本分類器的提升方法。對于分類問題采用二叉分類樹，對回歸問題采用二叉回歸樹。

提升樹模型可以表示為決策樹的加法模型：

             其中

表示決策樹，

為樹的參數

2.提升樹算法步驟

提升樹算法采用前向分步算法。初始化提升樹

，第

步的模型如下：

為目前模型

通過經驗風險極小化确定下一棵決策樹的參數

:

    對于分類問題和回歸問題兩個問題，提升樹算法的主要差別是損失函數不同。對于分類問題，使用指數函數作為損失函數，而對于回歸問題，使用平方誤差。對于分類問題，提升樹算法隻需要将上面讨論的AdaBoost算法中的基本分類器限制為二類分類樹。此時的提升樹算法是一個特殊的AdaBoost算法。這裡不再詳細讨論，下面主要讨論回歸問題的提升樹算法。

3.回歸樹的表示

回歸樹的數學表達式如下：

為樹的葉子結點數

           其中

表示在回歸樹上，輸入

被映射到葉節點

的影射關系，

為葉節點

的輸出值。

4.回歸問題提升樹算法模型

1. 初始化： 

2. 對

3.得到提升樹

在第

步，給定目前模型的情況下，求解

                  使用平方損失函數

此時，

為目前模型的預測結果，

為真實結果，令

，即

為目前模型預測結果與真實結果的內插補點，我們稱之為殘差。即每一步隻需求解：

5.回歸提升樹算法描述

輸入：

輸出：回歸提升樹

1. 初始化 

2. 對

    a. 計算殘差 

    b. 拟合上一部殘差，得到一個回歸樹

    c. 更新提升樹模型：

3. 得到回歸提升樹：

四、梯度提升算法(GBDT)

    提升樹利用加法模型和前向分布算法實作學習的優化過程。當損失函數是平方損失和指數算是時，每一步的優化是很簡單的。但對于一般損失函數而言，每一步的優化往往沒有那麼容易。針對這一問題，Freidman提出了梯度提升(gradient boosting)算法。這是利用最速下降法的近似方法，其關鍵是利用損失函數的負梯度在目前模型的值。

作為回歸問題提升樹算法中的殘差的近似值，以此來拟合一個回歸樹。

1.梯度提升算法描述

輸入：

； 

 損失函數為一般損失函數

輸出：回歸提升樹

1. 初始化

2. 對

    a. 對

    b. 對

 拟合一個回歸樹，得到第

棵樹的葉節點區域

 (得到樹的結構)

    c.對

 計算

      (得到各葉節點的值)

    d. 更新

3. 得到提升樹

GBDT與提升樹之間的差別：

在上述算法的第2(a)步使用損失函數的負梯度在目前模型的值，将它作為殘差的估計值。在回歸提升樹中，将損失函數限定為平方損失，此時它就是通常所說的殘差，而對于一般的損失函數，它就是殘差的近似值。

GBDT算法的缺點：

傳統GBDT的目标函數隻有損失函數一項，容易引起過拟合。

GBDT的實作是比較慢的。因為每次都要先構造出一棵樹，并添加到整個模型序列中，是以引出了xgboost算法。

五、XGBoost算法

XGBoost是一種特殊提升算法，準确的說它是一種梯度提升決策樹。(xgboost其實就是GBDT的加速實作)。

XGBoost在目标函數中增加正則項來防止模型過拟合。

1.xgboost的優化思路

    采用Boosting思想，從一個常量(通常為0)進行預測，每次添加一個新的拟合殘差的函數。

1. 初始化

2. 對

3. 得到提升模型

需要優化的是第二步，需要尋找一種方法來确定第

輪的函數

。

2.XGBoost算法的學習過程

第

輪疊代預測結果：

目标函數為：

優化目标函數

先考慮損失函數為平方損失的情況：

在第

輪，

已經是一個已知量，是以

 是一個常量。是以目标函數為：

此時目标函數轉換成一個關于

的二次函數，此時是很容易求出最優解的。

但是XGBoost并沒有限制損失函數必須是平方損失函數，為了算法的通用型和可擴充性，損失函數使用一般損失函數。此時目标函數還是相當複雜的；

神來之筆泰勒公式

泰勒展開式的二階形式：

           其中，

表示

的高階無窮小，是以有：

觀察我們的目标函數，如果把

看成是

為自變量的函數，把

看做是自變量的增量

,那麼就可以把目标函數按

進行泰勒展開，目标函數轉化為：

               其中

表示目标函數關于

的一階導；

表示目标函數關于

的二階導。

至此，我們得到新的目标函數：

去除常數部分(注意在第

輪時，

是常數)：

至此我們得到一個可以優化的目标函數。

正則項的處理

    目标函數正則化項存在的原因是為了限制模型的複雜度，讓模型在訓練集上能夠取得較好的結果的前提下盡可能的簡單。在XGBoost中，在每一步疊代中模型的複雜度就是目前要學習的決策樹的複雜度。

在這裡我們重新定一下決策樹：

    一個決策樹，假設其葉子結點數為

，該決策樹是由所有葉子結點對應的值組成的向量

,以及一個把樣本特征向量映射到葉子節點的索引函數

組成的，是以決策樹可以定義為：

。

決策樹的複雜度可以定義為：

即決策樹的模型的複雜度由生成樹葉子結點數和葉子節點對應值的向量的

範數決定。

把決策樹複雜度帶入到目标函數中：

求目标函數關于

的導數：

令導數為0，有：

是以我們可以得到所有葉節點的值。此時目标函數的值為：

至此，關于第t輪的一個已經分裂好的決策樹，我們能夠求出其對應的最小化的目标函數。但是如何進行節點分裂得到一棵樹？

窮舉法：窮舉所有可能的樹結構，選擇使目标函數最小的那顆，但是可能的樹結構有無窮多種，在有限的時間内無法找到最 優的那顆決策樹。

XGBoost做法：使用貪心政策一步步增長樹的結構。即從根節點開始，每個節點不斷進行遞歸分類，直到達到限制條件。

尋找最優分裂點

     根據上面的公式我們知道，一個節點分裂對最優目标函數的影響是不分裂的最優目标函數值減去分裂出的兩個子樹的最優目标函數值之和，即：

對于任一節點，隻有當

為正時，才表示此次分裂有收益。

最優分裂點尋找方法：

1.對每一個待分裂點，枚舉出所有特征

2.對于每一個特征。根據該特征g所有的進行排序

3.周遊該特征的每可能值作為分裂點時對應的gain，将擷取最大gain的特征及對應的取值作為分裂點進行分裂。

剪枝政策

前剪枝：目前最優分裂點的收益為負，停止分裂。

後剪枝：先将決策樹增長到他的最大深度，在遞歸的進行剪枝。

前剪枝存在的問題是可能存在收益更大的後續分裂。是以一般我們采用後剪枝，建樹完成後再減掉那些收益為負的葉子結點。

防止單步過拟合

在AdaBoost中，每個基模型的預測結果都會乘以一個自身的權值，這個權值反應基模型在整個模型中的重要性。在XGBoost中，每個基模型也都會乘以一個權值

，隻不過

是固定，它不反應基模型的重要度，而是為了防止單步過拟合，稱為學習率。

3.XGBoost建構步驟流程

輸入：

； 

輸出：梯度提升樹 

1. 初始化

2. 對

    a. 對

        計算  

    b. 使用貪心政策建構決策樹

，以使得下列目标函數最小化

    c. 更新：

3. 得到XGBoost提升樹

六、總結

Boosting算法族

提升(Boosting)是內建學習方法裡的一個重要方法，其主要思想是将弱分類器組裝成一個強分類器。在PCA(機率近似正确)學習架構下，一定可以将弱分類器組合成強分類器。

AdaBoost、GBDT、XGBoost都屬于(加法模型、前向分步、指數損失函數)家族，都實作了将多個弱分類器組合成一個強分類器的過程。

AdaBoost

AdaBoost是一種典型的分類回歸樹，适合解決二分類問題。

AdaBoost是一種采用加法模型、前向分步算法、損失函數為指數損失函數的提升樹，可以認為AdaBoost是Boosting前向分步算法的一個特例。

回歸提升樹和AdaBoost

回歸提升樹與AdaBoost不同之處在于它使用平方損失函數來解決回歸問題，通過計算殘差發現目前模型的問題，并不斷拟合殘差來建構新的弱分類器(樹)。

GBDT與回歸提升樹

a.梯度提升樹看做一種特殊的回歸提升樹。它通過計算損失函數的負梯度在目前模型的值， 近似替代回歸提升樹中的殘 差，并通過拟合該"殘差"建構新的弱分類器。

b.回歸提升樹初始化

；GBDT初始化時，令基學習器等于使損失函數最小化的常數。

c.回歸提升樹限制損失函數為平方損失，并以此計算殘差；GBDT不限制損失函數，通過損失函數負梯度來計算法殘差。

XGBoost與GBDT

1.XGBoost其實是GBDT的高效實作，xgboost中的基學習器出了可以是CART(決策樹), 還可以是線性分類器。

2.xgboost在目标函數中顯示的加入了正則化項，用于控制模型的複雜度。

3.GBDT使用損失函數的一階導來計算僞殘差，xgboost使用了損失函數的一階導與二階導

4.CART回歸樹中尋找最佳分割點的衡量标準是最小化均方差；xgboost中尋找最優分割點的标準是目标函數最小化

5.列抽樣(column subsampling)。xgboost借鑒了随機森林的做法，支援列抽樣，不僅能降低過拟合，還能減少計算。

七、參考文獻

1.李航統計學習方法 第二版

2.提升樹算法總結 http://ihoge.cn/2018/boosting.html

3.GBDT與XGBoost詳解 https://fengxc.me/GBDT%E8%AF%A6%E8%A7%A3.html

4.機器學習算法系列（36）：GBDT算法原理深入解析

    本文主要是自己學習筆記的整理，在學習參考文獻中内容的基礎上加了自己一些了解，不能算自己的原創。感興趣的同學可以同時把參考文獻中的内容一起閱讀，以加深了解。