GBDT和XGboost介紹

注：本文轉自https://blog.csdn.net/legendavid/article/details/78904353并對文章進行了優化（原文沒有圖檔），對方也是轉載，原作者不知哪位大神。

GBDT（Gradient Boosting Decision Tree）是一種基于疊代所構造的決策樹算法，它又可以簡稱為MART（Multiple Additive Regression Tree）或GBRT（Gradient Boosting Regression Tree）。雖然名字上又是Gradient又是Boosting的，但它的原理還是很淺顯易懂（當然詳細的推導還是有一些難度）。簡單來講，這種算法在實際問題中将生成多棵決策樹，并将所有樹的結果進行彙總來得到最終答案。也就是說，該算法将決策樹與內建思想進行了有效的結合。

今天所要學習的GBDT同樣是屬于Boosting大家庭中的一員，自算法的誕生之初，它就和SVM一起被認為是泛化能力（generalization）較強的算法。近些年來更因為被用于建構搜尋排序的機器學習模型而引起廣泛的關注。

除此之外，GBDT還是目前競賽中最為常用的一種機器學習算法，因為它不僅可以适用于多種場景，而且相比較于其他算法還有着出衆的準确率，如此優異的性能也讓GBDT收獲了機器學習領域的“屠龍刀”這一贊譽。

那麼，如此優秀的算法在實際中是如何進行工作的呢？背後的基本原理又是什麼？接下來，我們就來走進算法内部，揭開這把“屠龍寶刀”的神秘面紗。

一、GBDT之DT——回歸樹

GBDT主要由三個概念組成：Regression Decistion Tree、Gradient Boosting與Shrinkage，隻有弄清楚這三個概念，我們才能明白算法的基本原理。首先來學習第一個概念：Regression Decistion Tree，即回歸決策樹。

提到決策樹，相信很多人會潛意識的想到最常見的分類決策樹（ID3、C4.5、CART等等），但要把GBDT中的DT也了解為分類決策樹那就大錯特錯了。實際上，決策樹不僅可以用于分類，還可用于回歸，它的作用在于數值預測，例如明天的溫度、使用者的年齡等等，而且對基于回歸樹所得到的數值進行加減是有意義的（例如10歲+5歲-3歲=12歲），這是差別于分類樹的一個顯著特征（畢竟男+女=是男是女?，這樣的運算是毫無道理的）。GBDT在運作時就使用到了回歸樹的這個性質，它将累加所有樹的結果作為最終結果。是以，GBDT中的所有決策樹都是回歸樹，而非分類樹。

接着，我們對問題進行進一步細分，來分析具體的一棵回歸樹的運作流程。

作為對比，簡要回顧下分類樹的運作過程：以ID3為例，窮舉每一個屬性特征的資訊增益值，每一次都選取使資訊增益最大的特征進行分枝，直到分類完成或達到預設的終止條件，實作決策樹的遞歸建構。

回歸樹的運作流程與分類樹基本類似，但有以下兩點不同之處：

• 第一，回歸樹的每個節點得到的是一個預測值而非分類樹式的樣本計數，假設在某一棵樹的某一節點使用了年齡進行分枝（并假設在該節點上人數

  

  ），那麼這個預測值就是屬于這個節點的所有人年齡的平均值。
• 第二，在分枝節點的選取上，回歸樹并沒有選用最大熵值來作為劃分标準，而是使用了最小化均方差，即

  

  。這很好了解，被預測出錯的次數越多，錯的越離譜，均方差就越大，通過最小化均方差也就能夠找到最靠譜的分枝依據。

一般來講，回歸樹的分枝不太可能實作每個葉子節點上的屬性值都唯一，更多的是達到我們預設的終止條件即可（例如葉子個數上限），這樣勢必會存在多個屬性取值，那麼該節點處的預測值自然就為基于這些樣本所得到的平均值了。

二、GBDT之GB——梯度提升

在簡單了解了回歸樹後，繼續來看第二個概念：梯度提升（Gradient Boosting）。

首先需要明确，GB本身是一種理念而非一個具體的算法，其基本思想為：沿着梯度方向，構造一系列的弱分類器函數，并以一定權重組合起來，形成最終決策的強分類器（由于梯度提升的具體内容與數學推導有一些複雜，而且即使不了解這塊知識的來龍去脈也不妨礙對算法本身的了解，出于這樣的考慮，本文将不涉及'Gradient'）。

那麼這一系列的弱分類器是怎麼樣形成的呢？這就是GBDT的核心所在：每一棵樹所學習的是之前所有樹結論和的殘差，這個殘差就是一個加預測值後能得真實值的累加量。

舉一個簡單的例子，同樣使用年齡進行分枝，假設我們A的真實年齡是18歲，但第一棵樹的預測年齡是12歲，即殘差為6歲。那麼在第二棵樹裡我們把A的年齡設為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子節點，那累加兩棵樹的結論就是A的真實年齡；如果第二棵樹的結論是5歲，則A仍然存在1歲的殘差，第三棵樹裡A的年齡就變成1歲……以此類推學習下去，這就是梯度提升在GBDT算法中的直覺意義。

三、GBDT算法的簡單應用

接下來還是通過訓練一個用于預測年齡的模型來展現算法的運作流程（本節的内容與圖檔引用自部落格文章GBDT（MART） 疊代決策樹入門教程 | 簡介）

首先，訓練集有4個人A、B、C、D，他們的年齡分别是14、16、24、26。其中A，B分别是高一和高三學生；C，D分别是應屆畢業生和工作兩年的員工，可用于分枝的特征包括上網時長、購物金額、上網時段和對百度知道的使用方式等。如果是用一棵傳統的回歸決策樹來訓練，會得到如下圖所示結果：

但如果是用GBDT來做這件事，由于資料太少，我們限定葉子節點做多有兩個，即每棵樹都隻有一個分枝，并且限定隻學兩棵樹。我們會得到如下圖所示結果：

第一棵樹的分枝與之前一樣，也是使用購物金額進行區分，兩撥人各自用年齡均值作為預測值，得到殘內插補點-1、1、-1、1，然後拿這些殘內插補點替換初始值去訓練生成第二棵回歸樹，如果新的預測值和殘差相等，則隻需把第二棵樹的結論累加到第一棵樹上就能得到真實年齡了。

第二棵樹隻有兩個值1和-1，直接可分成兩個節點。此時所有人的殘差都是0，即每個人都得到了真實的預測值。

将兩棵回歸樹預測結果進行彙總，解釋如下：

• A：14歲高一學生；購物較少；經常問學長問題；預測年齡A = 15 – 1 = 14
• B：16歲高三學生；購物較少；經常被學弟問問題；預測年齡B = 15 + 1 = 16
• C：24歲應屆畢業生；購物較多，經常問師兄問題；預測年齡C = 25 – 1 = 24
• D：26歲工作兩年員工；購物較多，經常被師弟問問題；預測年齡D = 25 + 1 = 26

對比初始的回歸樹與GBDT所生成的回歸樹，可以發現，最終的結果是相同的，那我們為什麼還要使用GBDT呢？

答案就是對模型過拟合的考慮。過拟合是指為了讓訓練集精度更高，學到了很多“僅在訓練集上成立的規律”，導緻換一個資料集後，目前規律的預測精度就不足以使人滿意了。畢竟，在訓練精度和實際精度（或測試精度）之間，後者才是我們想要真正得到的。

在上面這個例子中，初始的回歸樹為達到100%精度使用了3個特征（上網時長、時段、網購金額），但觀察發現，分枝“上網時長>1.1h”很顯然過拟合了，不排除恰好A上網1.5h, B上網1小時，是以用上網時間是不是>1.1小時來判斷所有人的年齡很顯然是有悖常識的。

而在GBDT中，兩棵回歸樹僅使用了兩個特征（購物金額與對百度知道的使用方式）就實作了100%的預測精度，其分枝依據更合乎邏輯（當然這裡是相比較于上網時長特征而言），算法在運作中也展現了“如無必要，勿增實體”的奧卡姆剃刀原理。

四、GBDT之Shrinkage——縮減

Shrinkage是GBDT的第三個基本概念，中文含義為“縮減”。它的基本思想就是：每次走一小步逐漸逼近結果的效果，要比每次邁一大步很快逼近結果的方式更容易避免過拟合。換句話說縮減思想不完全信任每一個棵殘差樹，它認為每棵樹隻學到了真理的一小部分，累加的時候隻累加一小部分，隻有通過多學幾棵樹才能彌補不足。

Shrinkage仍然以殘差作為學習目标，但由于它采用的是逐漸逼近目标的方式，導緻各個樹的殘差是漸變的而不是陡變的。之是以這樣做也是基于模型過拟合的考慮（更為詳細的内容可參考文末給出的參考資料）。

GBDT的基本内容大緻介紹完畢，在下一文中，我們将從梯度的角度對算法進行推導與學習。

一、GBDT的梯度提升過程

在上一文中，我們詳細講述了GBDT算法的基本概念，并通過一個簡單的小例子闡述它在實際使用中的運作流程，可以說我們對算法已經有了一個初步的認識。不過還留有一個問題尚待解決，那就是如何了解GBDT中的Gradient（梯度）？

衆所周知，基于Boosting的內建學習是通過疊代得到一系列的弱學習器，進而通過不同的組合政策得到相應的強學習器。在GBDT的疊代中，假設前一輪得到的強學習器為

，對應的損失函數則為

。是以新一輪疊代的目的就是找到一個弱學習器

，使得損失函數

達到最小。

是以問題的關鍵就在于對損失函數的度量，這也正是難點所在，畢竟損失函數多種多樣，怎麼樣才能找到一種通用的拟合方法呢？

針對這一問題，機器學習界的大牛Freidman提出了梯度提升算法：利用最速下降的近似方法，即利用損失函數的負梯度在目前模型的值，作為回歸問題中提升樹算法的殘差的近似值，拟合一個回歸樹。

這樣的話，第

輪的第

個樣本的負梯度表示為：

，

接下來對算法步驟進行詳細解釋：

• 初始化弱學習器

  

  ，得到使損失函數極小化的一個常數值，此時樹僅有一個根節點
• 計算損失函數的負梯度值，以此作為殘差的估計
  • 針對選取的不同的損失函數（平方、絕對值、Huber），對應圖1中不同的梯度值；
  • 算法中嵌套兩層循環，分别為疊代輪數

    

    和樣本

    

• 利用計算得到的

  

  拟合一棵CART回歸樹，得到第

  

  輪的回歸樹，對應的葉子節點區域為

  

  （

  

  為回歸樹

  

  的葉子節點的個數）
• 接着，對葉子區域計算最佳拟合值

  

  （損失函數極小化）并更新強學習器

  

• 最後，在疊代結束後輸出最終模型

  

二、GBDT小結

至此，GBDT的内容就基本講完了，對這個算法，一方面我們可以從殘差的角度來了解，每一棵回歸樹都是在學習之前的樹的殘差；另一方面也可以從梯度的角度掌握算法，即每一棵回歸樹通過梯度下降法學習之前的樹的梯度下降值。

這樣看來，這兩種了解角度從總體流程和輸入輸出上沒有差別的，它們都是疊代回歸樹，都是累加每棵樹結果作為最終結果，每棵樹都在學習前面樹尚存的不足。而不同之處就在于每一步疊代時的求解方法的不同，前者使用殘差（殘差是全局最優值），後者使用梯度（梯度是局部最優方向），簡單一點來講就是前者每一步都在試圖向最終結果的方向優化，後者則每一步試圖讓目前結果更好一點。

看起來前者更科學一點，畢竟有絕對最優方向不學，為什麼舍近求遠去估計一個局部最優方向呢？原因在于靈活性。前者最大問題是，由于它依賴殘差，損失函數一般固定為反映殘差的均方差，是以很難處理純回歸問題之外的問題。而後者求解方法為梯度下降，隻要可求導的損失函數都可以使用。

最後小結一下GBDT算法的優缺點。

優點：

• 預測精度高
• 适合低維資料
• 能處理非線性資料

缺點：

• 并行麻煩（因為上下兩棵樹有聯系）
• 如果資料次元較高時會加大算法的計算複雜度

一、XGBoost簡介

在GBDT的學習過程中，不少部落格都提到了該算法的更新版——XGBoost，并對它贊賞有加。是以，這一塊的知識（包括算法的基本内容，數學推導與案例實作）将使用兩篇文章的篇幅來進行學習掌握。

經過前面的學習，我們已經知道，GBDT是一種基于內建思想下的Boosting學習器，并采用梯度提升的方法進行每一輪的疊代最終組建出強學習器，這樣的話算法的運作往往要生成一定數量的樹才能達到令我們滿意的準确率。當資料集大且較為複雜時，運作一次極有可能需要幾千次的疊代運算，這将對我們使用算法造成巨大的計算瓶頸。

針對這一問題，華盛頓大學的陳天奇博士開發出了XGBoost（eXtreme Gradient Boosting），它是Gradient Boosting Machine的一個c++實作，并在原有的基礎上加以改進，進而極大地提升了模型訓練速度和預測精度。可以說，XGBoost是Gradient Boosting的高效實作。

XGBoost最大的特點在于它能夠自動利用CPU的多線程進行并行計算，同時在算法上加以改進提高了精度。在Kaggle的希格斯子信号識别競賽中，XGBoost因為出衆的效率與較高的預測準确度在比賽論壇中引起了參賽選手的廣泛關注，在1700多支隊伍的激烈競争中占有一席之地。随着它在Kaggle社群知名度的提高，在其他的比賽中也有隊伍借助XGBoost奪得第一。

接下來學習XGBoost算法的數學推導過程。

二、目标函數：損失與正則

在監督學習中，我們通常會構造一個目标函數和一個預測函數，使用訓練樣本對目标函數最小化學習到相關的參數，然後用預測函數和訓練樣本得到的參數來對未知的樣本進行分類的标注或者數值的預測。在XGBoost中，目标函數的形式為：

• 

  ：損失函數，常用損失函數有：
  • 平方損失：

    

  • Logistic損失：

    

• 

  ：正則化項，之是以要引入它是因為我們的目标是希望生成的模型能準确的預測新的樣本（即應用于測試資料集），而不是簡單的拟合訓練集的結果（這樣會導緻過拟合）。是以需要在保證模型“簡單”的基礎上最小化訓練誤差，這樣得到的參數才具有好的泛化性能。而正則項就是用于懲罰複雜模型，避免預測模型過分拟合訓練資料，常用的正則有

  

  正則與

  

  正則。

如果目标函數中的損失函數權重過高，那麼模型的預測精度則不盡人意，反之如果正則項的權重過高，所生成的模型則會出現過拟合情況，難以對新的資料集做出有效預測。隻有平衡好兩者之間的關系，控制好模型複雜度，并在此基礎上對參數進行求解，生成的模型才會“簡單有效”（這也是機器學習中的偏差方差均衡）。

三、XGBoost的推導過程

1. 目标函數的疊代與泰勒展開

由于之前已經學習過樹的生成及內建方法，這裡不再贅述。首先，我們可以把某一次疊代後內建的模型表示為：

（

也就是上文中的

）

相對應的目标函數：

将這兩個公式進行擴充，應用在前

輪的模型疊代中，具體表示為：

就是前

輪的模型預測，

為新

輪加入的預測函數。

這裡自然就涉及一個問題：如何選擇在每一輪中加入的

呢？答案很直接，選取的

必須使得我們的目标函數盡量最大地降低（這裡應用到了Boosting的基本思想，即目前的基學習器重點關注以前所有學習器犯錯誤的那些資料樣本，以此來達到提升的效果）。先對目标函數進行改寫，表示如下：

如果我們考慮使用平方誤差作為損失函數，公式可改寫為：

更加一般的，對于不是平方誤差的情況，我們可以采用如下的泰勒展開近似來定義一個近似的目标函數，友善我們進行這一步的計算。

泰勒展開：

其中

，

如果移除掉常數項，我們會發現這個目标函數有一個非常明顯的特點，它隻依賴于每個資料點的在誤差函數上的一階導數和二階導數（

）。有人可能會問，這個公式似乎比我們之前學過的決策樹學習難懂。為什麼要花這麼多力氣來做推導呢？

這是因為，這樣做會使我們可以很清楚地了解整個目标是什麼，并且一步一步推導出如何進行樹的學習。這一個抽象的形式對于實作機器學習工具也是非常有幫助的。因為它包含所有可以求導的目标函數，也就是說有了這個形式，我們寫出來的代碼可以用來求解包括回歸，分類和排序的各種問題，正式的推導可以使得機器學習的工具更加一般化。

2. 決策樹的複雜度

接着來讨論如何定義樹的複雜度。我們先對于

的定義做一下細化，把樹拆分成結構部分

和葉子權重部分

。其中結構函數

把輸入映射到葉子的索引号上面去，而

給定了每個索引号對應的葉子分數是什麼。具體公式為：

當我們給定上述定義後，那麼一棵樹的複雜度就為

這個複雜度包含了一棵樹裡面節點的個數（左側），以及每個樹葉子節點上面輸出分數的

模平方（右側）。當然這不是唯一的一種定義方式，不過這一定義方式學習出的樹效果一般都比較不錯。

簡單提及一下

和

兩個系數的作用，

作為葉子節點的系數，使XGBoost在優化目标函數的同時相當于做了預剪枝；

作為

平方模的系數也是要起到防止過拟合的作用。

3. 目标函數的最小化

接下來就是非常關鍵的一步，在這種新的定義下，我們可以把目标函數進行如下改寫，其中

被定義為每個葉子上面樣本集合

分别定義

與

，上式簡化為

由此，我們将目标函數轉換為一個一進制二次方程求最小值的問題（在此式中，變量為

，函數本質上是關于

的二次函數），略去求解步驟，最終結果如下所示：

，

乍一看目标函數的計算與樹的結構函數

沒有什麼關系，但是如果我們仔細回看目标函數的構成，就會發現其中

和

的取值都是由第

個樹葉上資料樣本所決定的。而第

個樹葉上所具有的資料樣本則是由樹結構函數

決定的。也就是說，一旦樹的結構

确定，那麼相應的目标函數就能夠根據上式計算出來。那麼樹的生成問題也就轉換為找到一個最優的樹結構

，使得它具有最小的目标函數。

計算求得的

代表了當指定一個樹的結構的時候，目标函數上面最多減少多少。所有我們可以把它叫做結構分數(structure score)。

4. 枚舉樹的結構——貪心法

在前面分析的基礎上，當尋找到最優的樹結構時，我們可以不斷地枚舉不同樹的結構，利用這個打分函數來尋找出一個最優結構的樹，加入到我們的模型中，然後再重複這樣的操作。不過枚舉所有樹結構這個操作不太可行，在這裡XGBoost采用了常用的貪心法，即每一次嘗試去對已有的葉子加入一個分割。對于一個具體的分割方案，我們可以獲得的增益可以由如下公式計算得到：

其中

代表左子樹分數，

代表右子樹分數，

代表不分割時我們可以獲得的分數，

代表加入新葉子節點引入的複雜度代價。

對于每次擴充，我們還是要枚舉所有可能的分割方案，那麼如何高效地枚舉所有的分割呢？假設需要枚舉所有

這樣的條件，那麼對于某個特定的分割

我們要計算

左邊和右邊的導數和，

我們可以發現對于所有的

，我們隻要做一遍從左到右的掃描就可以枚舉出所有分割的梯度與

和

。然後用上面的公式計算每個分割方案的分數就可以了。

但需要注意是：引入的分割不一定會使得情況變好，因為在引入分割的同時也引入新葉子的懲罰項。是以通常需要設定一個門檻值，如果引入的分割帶來的增益小于一個閥值的時候，我們可以剪掉這個分割。此外在XGBoost的具體實踐中，通常會設定樹的深度來控制樹的複雜度，避免單個樹過于複雜帶來的過拟合問題。

到這裡為止，XGBoost的數學推導就簡要介紹完畢。

一、XGBoost的優良特性

同樣是梯度提升，同樣是內建學習，那麼XGBoost比GBDT要好在哪裡呢？

可大緻總結為以下幾點：

• GBDT是以CART為基分類器，但XGBoost在此基礎上還支援線性分類器，此時XGBoost相當于帶

  

  和

  

  正則化項的Logistics回歸（分類問題）或者線性回歸（回歸問題）
• XGBoost在目标函數裡加入了正則項，用于控制模型的複雜度。正則項裡包含了樹的葉子節點個數和每棵樹葉子節點上面輸出分數的

  

  模平方。從偏差方差權衡的角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過拟合
• 傳統的GBDT在優化時隻用到一階導數，XGBoost則對目标函數進行了二階泰勒展開，同時用到了一階和二階導數。（順便提一下，XGBoost工具支援自定義代價函數，隻要函數可一階和二階求導）
• 樹節點在進行分裂時，我們需要計算每個特征的每個分割點對應的增益，即用貪心法枚舉所有可能的分割點。當資料無法一次載入記憶體或者在分布式情況下，貪心算法效率就會變得很低，是以XGBoost采用了一種近似的算法。大緻的思想是根據百分位法列舉幾個可能成為分割點的候選者，然後從候選者中根據上面求分割點的公式計算找出最佳的分割點
• Shrinkage（縮減），相當于學習速率（XGBoost中的eta）。XGBoost在進行完一次疊代後，會将葉子節點的權重乘上該系數，主要是為了削弱每棵樹的影響，讓後面有更大的學習空間。實際應用中，一般把eta設定得小一點，然後疊代次數設定得大一點。（當然普通的GBDT實作也有學習速率）
• 特征列排序後以塊的形式存儲在記憶體中，在疊代中可以重複使用；雖然boosting算法疊代必須串行，但是在處理每個特征列時可以做到并行
• 列抽樣（column subsampling）：XGBoost借鑒了随機森林的做法，支援列抽樣，不僅能降低過拟合，還能減少計算，這也是XGBoost異于傳統GBDT的一個特性
• 除此之外，XGBoost還考慮了當資料量比較大，記憶體不夠時怎麼有效的使用磁盤，主要是結合多線程、資料壓縮、分片的方法，盡可能的提高算法效率