本文節(jié)選自《機器學習入門基礎（微課版）》

10.5 XGBoost 算法

XGBoost 是 2014 年 2 月由華盛頓大學的博士生陳天奇發(fā)明的基于梯度提升算法(GBDT)的機器學習算法，其算法不但具有優(yōu)良的學習效果，而且訓練速度高效，在數(shù)據(jù)競賽中大放異彩。

XGBoost 是大規(guī)模并行 Boosting Tree 的工具，它是性能和速度俱佳的開源 Boosting Tree 工具包，比常見的工具包快很多倍。XGBoost 和 GBDT 兩者都是 Boosting 方法，除了工程實現(xiàn)、解決問題上的一些差異外，最大的不同就是目標函數(shù)的定義。

10.5.1 算法思想

XGBoost 算法原理主要是以下幾個方面：

1.防止過擬合

機器學習算法的泛化誤差可以分為偏差(Bias)和方差(Variance)兩部分。偏差指的是算法的期望預測與真實預測之間的偏差程度，反應了模型本身的擬合能力；方差度量了同等大小的訓練集的變動導致學習性能的變化，刻畫了數(shù)據(jù)擾動所導致的影響。

如圖 10-9 所示，隨著機器學習的模型復雜度增加，偏差越來越小，但方差卻越來越大，而當模型越簡單時，模型的方差很小，偏差卻往往越大，也就是說，高方差導致過擬合，而高偏差導致欠擬合。

XGBoost 有效解決了過擬合問題，對葉節(jié)點的權重進行了懲罰，防止過擬合，懲罰相當于添加了 正則項，即目標函數(shù)為：訓練損失加上正則項。

2.采用二階泰勒展開加快收斂

GBDT 的損失函數(shù)用了一階收斂，用到了梯度下降，XGBoost 的方法是用牛頓法進行二階收斂，即將損失函數(shù)做二階泰勒展開，使用前兩階作為改進的殘差。梯度下降法是用了目標函數(shù)的一階偏導數(shù)，而牛頓法就是用用了目標函數(shù)的二階偏導數(shù)，二階偏導數(shù)考慮了梯度的變化趨勢，所以牛頓法會更容易收斂。圖 10-10 顯示了牛頓法(左)和梯度下降法(右)的迭代路徑，可以發(fā)現(xiàn)，左邊的路徑更符合最優(yōu)下降路徑。使用二階收斂，這也是 XGBoost 加快收斂的原因。

3.樹構造的分裂條件采用導數(shù)統(tǒng)計量

在尋找最佳分割點時，XGBoost 也實現(xiàn)了一種完全搜索式的精確的貪心算法(Exact Greedy Algorithm)。這種搜索算法會遍歷一個特征上所有可能的分裂點，分別計算其損失減小量，然后選擇最優(yōu)的分裂點。根據(jù)結構分數(shù)的增益情況計算出來選擇哪個特征的哪個分割點，某個特征的重要性，就是它在所有樹中出現(xiàn)的次數(shù)之和。即增益(Gain)計算完了之后會選擇一個增益最高的特征來分裂，然后這個特征的重要性加 1。

4.支持并行計算，可以采用多線程優(yōu)化技術

XGBoost 的并行，并不是說每棵樹可以并行訓練，XGBoost 本質(zhì)上仍然采用 boosting 思想，每棵樹訓練前需要等前面的樹訓練完成才能開始訓練。

XGBoost 的并行，指的是特征維度的并行：在訓練之前，每個特征按特征值對樣本進行預排序，并存儲為 Block 結構，在后面查找特征分割點時可以重復使用，而且特征已經(jīng)被存儲為一個個 block 結構，那么在尋找每個特征的最佳分割點時，可以利用多線程對每個 block 并行計算。

10.5.2 XGBoost 算法推導

XGBoost 中最主要的基學習器為 CART(分類與回歸樹)，這里定義 是葉子的權重，  是將每個節(jié)點分配給葉子的函數(shù)， 是樹的數(shù)量，并定義 為一個常數(shù)。假設前 步迭代優(yōu)化得到的模型為 ，在第 步中，待求參數(shù)為 ，則第 步的目標函數(shù)為：

公式(10.14)第一部分 是預測值 和目標真實值 之間的訓練誤差，第二部分 是每棵樹的復雜度之和。

根據(jù)泰勒展開公式，使用了二階泰勒展開：

把 看成 則， 就可以看成 ，則：

在上面公式中：

為 的一階偏導數(shù)：

為 的二階偏導數(shù)：

則公式(10.14)可以轉(zhuǎn)化為：

在這里，我們首先改進一棵樹的定義   如下：

在 XGBoost 中，我們將復雜度定義為：

則目標函數(shù)可以定義為：

很明顯， 是一個常數(shù)，可以用 替代，對于目標函數(shù) 無影響，則目標函數(shù)可以轉(zhuǎn)換為：

其中定義 是分配給第    個葉子的數(shù)據(jù)點的索引的集合。因為在同一葉子上，所有數(shù)據(jù)點的分數(shù)相同，所以在第二行中，我們更改了總和的索引。因此公式等價于：

即：

我們可以通過定義 ， 來進一步壓縮表達式，則：

對 求偏導，如果有一個給定的樹的結構 ，那么在上式達到最小的情況下(即導數(shù)為 0)，得到：

則：

并且得到相對應的最優(yōu)目標函數(shù)值：

以圖 10-11 為例：

根據(jù)已知的數(shù)據(jù)，得到相應的參數(shù)如圖 10-12：

圖 10-12 的數(shù)據(jù)，，根據(jù)公式(10.30)，則：

分數(shù)越小，代表這個樹的結構越好。

在尋找最佳分割點時，使用一種完全搜索式的精確貪心算法(Exact Greedy Algorithm)。這種搜索算法會遍歷一個特征上所有可能的分裂點，分別計算其損失減小量，然后選擇最優(yōu)的分裂點。精確貪心算法的流程見算法 10.1。

算法思路：由于樹的結構是未知的，而且也不可能去遍歷所有的樹結構。因此，XGBoost 采用貪婪算法來分裂節(jié)點，從根節(jié)點開始，遍歷所有屬性，遍歷屬性的可能取值，計算復雜度是：決策樹葉子節(jié)點數(shù)減去 1。根據(jù)定義 ，記分到左、右子樹的樣本集為 、，，則分裂該節(jié)點導致的損失減少值為：

即：

其中： 為分割后左子樹的分數(shù)， 為分割后右子樹的分數(shù)， 為未分割的樹的分數(shù)， 為新葉子的正則化項，即加入新葉子節(jié)點引入的復雜度代價，我們希望找到一個屬性以及其對應的大小，使得  取值最大。

10.5.3 XGBoost 算法總結

XGBoost 是算法競賽中最熱門的算法之一，它將 GBDT 的優(yōu)化走向了一個極致：

(1) XGBoost 生成 CART 樹考慮了樹的復雜度，GDBT 未考慮，GDBT 在樹的剪枝步驟中考慮了樹的復雜度。

(2) XGBoost 是擬合上一輪損失函數(shù)的二階導展開，GDBT 是擬合上一輪損失函數(shù)的一階導展開，因此，XGBoost 的準確性更高，且滿足相同的訓練效果，需要的迭代次數(shù)更少。

(3) XGBoost 與 GDBT 都是逐次迭代來提高模型性能，但是 XGBoost 在選取最佳分割點時可以開啟多線程進行，大大提高了運行速度。當然，后續(xù)微軟又出了 LightGBM，在內(nèi)存占用和運行速度上又做了不少優(yōu)化，但是從算法本身來說，優(yōu)化點則并沒有比 XGBoost 多。