XGBoost超詳細推導，終於講明白了！

2019 年 10 月 11 日
筆記

– XGB中樹結點分裂的依據是什麼？ – 如何計算樹節點的權值？ – 為防止過擬合，XGB做了哪些改進？

相信看到這篇文章的各位對XGBoost都不陌生，的確，XGBoost不僅是各大數據科學比賽的必殺武器，在實際工作中，XGBoost也在被各大公司廣泛地使用。

如今演算法崗競爭日益激烈，面試難度之大各位有目共睹，面試前背過幾個常見面試題已經遠遠不夠了，面試官通常會「刨根問底「，重點考察候選人對模型的掌握深度。因此，對於XGBoost，你不僅需要知其然，而且還要知其所以然。

本文重點介紹XGBoost的推導過程，文末會拋出10道面試題考驗一下各位，最後準備了一份「XGB推導攻略圖」，幫助你更好的掌握整個推導過程。

本文結構

從「目標函數」開始，生成一棵樹

1. XGB目標函數

XGBoost的目標函數由訓練損失和正則化項兩部分組成，目標函數定義如下：

變數解釋：

（1）l 代表損失函數，常見的損失函數有：

（2）yi'是第 i 個樣本 xi 的預測值。由於XGBoost是一個加法模型，因此，預測得分是每棵樹打分的累加之和。

（3）將全部k棵樹的複雜度進行求和，添加到目標函數中作為正則化項，用於防止模型過度擬合。

2. 學習第t棵樹

在【1】中提到，XGBoost 是一個加法模型，假設我們第t次迭代要訓練的樹模型是 ft() ，則有：

將上式帶入【1】中的目標函數 Obj ，可以得到：

注意上式中，只有一個變數，那就是第 t 棵樹：

其餘的都是已知量或可通過已知量可以計算出來的（注意要理解哦！）。

細心的同學可以發現，這裡我們將正則化項進行了拆分，由於前 t-1棵樹的結構已經確定，因此，前 t-1 棵樹的複雜度之和可以用一個常量表示：

3. 泰勒公式展開

首先簡單回憶一下，泰勒公式。

泰勒公式是將一個在 x = x0 處具有n階導數的函數 f(x) 利用關於 (x-x0) 的n次多項式來逼近函數的方法。

泰勒公式的二階展開形式如下：

回到我們的問題上來， f(x) 對應於我們的損失函數 l ，x 對應於前 t-1 棵樹的預測值，Δx 對應於我們正在訓練的第 t 棵樹。

首先定義損失函數 l 關於 y『(t-1) 的一階偏導數和二階偏導數：

那麼，我們的損失函數就可以轉化為下式（標出了與泰勒公式中x和Δx的對應關係）。

將上述二階展開式，帶入到【2】中的目標函數 Obj 中，可以得到目標函數 Obj 的近似值：

去掉全部常數項，得到目標函數：

4. 定義一顆樹

我們重新定義一顆樹，包括兩個部分：

葉子結點的權重向量 ω ；
實例 -> 葉子結點的映射關係q（本質是樹的分支結構）；

一棵樹的表達形式定義如下：

5. 定義樹的複雜度

我們定義一顆樹的複雜度 Ω，它由兩部分組成：

葉子結點的數量；
葉子結點權重向量的L2範數；

6. 葉子結點歸組

我們將屬於第 j 個葉子結點的所有樣本 xi , 劃入到一個葉子結點樣本集中，數學表示如下：

然後，將【4】和【5】中一棵樹及其複雜度的定義，帶入到【3】中泰勒展開後的目標函數Obj中，具體推導如下：

為進一步簡化該式，我們進行如下定義：

含義如下：

Gj ：葉子結點 j 所包含樣本的一階偏導數累加之和，是一個常量；
Hj ：葉子結點 j 所包含樣本的二階偏導數累加之和，是一個常量；

將 Gj 和 Hj 帶入目標式Obj，得到我們最終的目標函數（注意，此時式中的變數只剩下第t棵樹的權重向量W）：

7. 樹結構打分

回憶一下高中數學知識。假設有一個一元二次函數，形式如下：

我們可以套用一元二次函數的最值公式輕易地求出最值點：

那回到我們的目標函數 Obj，該如何求出它的最值呢？

先簡單分析一下上面的式子：

對於每個葉子結點 j , 可以將其從目標式 Obj 中拆解出來：

在【6】中我們提到，Gj 和 Hj 相對於第 t 棵樹來說是可以計算出來的。那麼，這個式子就是一個只包含一個變數 葉子結點權重wj 的一元二次函數，上面也提到了，我們可以通過最值公式求出它的最值點。

再次分析一下目標函數Obj，可以發現，各個葉子結點的目標子式是相互獨立的，也就是說，當每個葉子結點的子式都達到最值點時，整個目標函數式Obj才達到最值點。

那麼，假設目前樹的結構已經固定，套用一元二次函數的最值公式，我們可以輕易求出，每個葉子結點的權重 wj* 及其此時達到最優的 Obj 的目標值：

實例演示：

一棵樹的生長細節

1. 分裂一個結點

在實際訓練過程中，當建立第 t 棵樹時，XGBoost採用貪心法進行樹結點的分裂：

從樹深為0時開始：

對樹中的每個葉子結點嘗試進行分裂；
每次分裂後，原來的一個葉子結點繼續分裂為左右兩個子葉子結點，原葉子結點中的樣本集將根據該結點的判斷規則分散到左右兩個葉子結點中；
新分裂一個結點後，我們需要檢測這次分裂是否會給損失函數帶來增益，增益的定義如下：

如果增益Gain>0，即分裂為兩個葉子節點後，目標函數下降了，那麼我們會考慮此次分裂的結果。

但是，在一個結點分裂時，可能有很多個分裂點，每個分裂點都會產生一個增益，如何才能尋找到最優的分裂點呢？接下來會講到。

2. 尋找最佳分裂點

在分裂一個結點時，我們會有很多個候選分割點，尋找最佳分割點的大致步驟如下：

遍歷每個結點的每個特徵；
對每個特徵，按特徵值大小將特徵值排序；
線性掃描，找出每個特徵的最佳分裂特徵值；
在所有特徵中找出最好的分裂點（分裂後增益最大的特徵及特徵值）

上面是一種貪心的方法，每次進行分裂嘗試都要遍歷一遍全部候選分割點，也叫做全局掃描法。

但當數據量過大導致記憶體無法一次載入或者在分散式情況下，貪心演算法的效率就會變得很低，全局掃描法不再適用。

基於此，XGBoost提出了一系列加快尋找最佳分裂點的方案：

特徵預排序+快取：XGBoost在訓練之前，預先對每個特徵按照特徵值大小進行排序，然後保存為block結構，後面的迭代中會重複地使用這個結構，使計算量大大減小。
分位點近似法：對每個特徵按照特徵值排序後，採用類似分位點選取的方式，僅僅選出常數個特徵值作為該特徵的候選分割點，在尋找該特徵的最佳分割點時，從候選分割點中選出最優的一個。
並行查找：由於各個特性已預先存儲為block結構，XGBoost支援利用多個執行緒並行地計算每個特徵的最佳分割點，這不僅大大提升了結點的分裂速度，也極利於大規模訓練集的適應性擴展。

3. 停止生長

一棵樹不會一直生長下去，下面是一些常見的限制條件。

(1) 當新引入的一次分裂所帶來的增益Gain<0時，放棄當前的分裂。這是訓練損失和模型結構複雜度的博弈過程。

(2) 當樹達到最大深度時，停止建樹，因為樹的深度太深容易出現過擬合，這裡需要設置一個超參數max_depth。

(3) 當引入一次分裂後，重新計算新生成的左、右兩個葉子結點的樣本權重和。如果任一個葉子結點的樣本權重低於某一個閾值，也會放棄此次分裂。這涉及到一個超參數:最小樣本權重和，是指如果一個葉子節點包含的樣本數量太少也會放棄分裂，防止樹分的太細，這也是過擬合的一種措施。

每個葉子結點的樣本權值和計算方式如下：

高頻面試題

XGB與GBDT、隨機森林等模型相比，有什麼優缺點？
XGB為什麼可以並行訓練？
XGB用二階泰勒展開的優勢在哪？
XGB為了防止過擬合，進行了哪些設計？
XGB如何處理缺失值？
XGB如何分裂一個結點？如何選擇特徵？
XGB中一顆樹停止生長的條件有哪些？
XGB葉子結點的權重有什麼含義？如何計算？
訓練一個XGB模型，經歷了哪些過程？調參步驟是什麼？
XGB如何給特徵評分？

備忘單

經過前面幾個部分的細心講解，相信大家對XGBoost底層原理已經很了解了，下面特意又準備了一份備忘單，希望能夠幫助大家系統化的掌握XGB原理的整個推導過程，同時又能夠起到快速回憶的作用。