前言
XGBoost（eXtreme Gradient Boosting）全名叫極端梯度提升，XGBoost是集成學習方法的王牌，在Kaggle數據挖掘比賽中，大部分獲勝者用了XGBoost，XGBoost在絕大多數的回歸和分類問題上表現的十分頂尖，本文較詳細的介紹了XGBoost的算法原理。
目錄
1. 最優模型的構建方法
2. Boosting的回歸思想
3. XGBoost的目標函數推導
4. XGBoost的回歸樹構建方法
5. XGBoost與GDBT的區別
最優模型的構建方法
構建最優模型的一般方法是最小化訓練數據的損失函數，我們用字母 L表示，如下式：
式（1）稱為經驗風險最小化，訓練得到的模型複雜度較高。當訓練數據較小時，模型很容易出現過擬合問題。
因此，為了降低模型的複雜度，常採用下式：
其中J(f)為模型的複雜度，式（2）稱為結構風險最小化，結構風險最小化的模型往往對訓練數據以及未知的測試數據都有較好的預測 。
應用：決策樹的生成和剪枝分別對應了經驗風險最小化和結構風險最小化，XGBoost的決策樹生成是結構風險最小化的結果，後續會詳細介紹。
Boosting方法的回歸思想
Boosting法是結合多個弱學習器給出最終的學習結果，不管任務是分類或回歸，我們都用回歸任務的思想來構建最優Boosting模型 。
回歸思想：把每個弱學習器的輸出結果當成連續值，這樣做的目的是可以對每個弱學習器的結果進行累加處理，且能更好的利用損失函數來優化模型。
假設
是第 t 輪弱學習器的輸出結果，
是模型的輸出結果，
是實際輸出結果，表達式如下：
上面兩式就是加法模型，都默認弱學習器的輸出結果是連續值。因為回歸任務的弱學習器本身是連續值，所以不做討論，下面詳細介紹分類任務的回歸思想。
分類任務的回歸思想：
根據2.1式的結果，得到最終的分類器：
分類的損失函數一般選擇指數函數或對數函數，這裡假設損失函數為對數函數，學習器的損失函數是
若實際輸出結果yi=1，則：
求（2.5）式對
的梯度，得：
負梯度方向是損失函數下降最快的方向，（2.6）式取反的值大於0，因此弱學習器是往增大
的方向迭代的，圖形表示為：
如上圖，當樣本的實際標記 yi 是 1 時，模型輸出結果
隨著迭代次數的增加而增加（紅線箭頭），模型的損失函數相應的減小；當樣本的實際標記 yi 是 -1時，模型輸出結果
隨著迭代次數的增加而減小（紅線箭頭），模型的損失函數相應的減小 。這就是加法模型的原理所在，通過多次的迭代達到減小損失函數的目的。
小結：Boosting方法把每個弱學習器的輸出看成是連續值，使得損失函數是個連續值，因此可以通過弱學習器的迭代達到優化模型的目的，這也是集成學習法加法模型的原理所在 。
XGBoost算法的目標函數推導
目標函數，即損失函數，通過最小化損失函數來構建最優模型，由第一節可知， 損失函數應加上表示模型複雜度的正則項，且XGBoost對應的模型包含了多個CART樹，因此，模型的目標函數為：
（3.1）式是正則化的損失函數，等式右邊第一部分是模型的訓練誤差，第二部分是正則化項，這裡的正則化項是K棵樹的正則化項相加而來的。
CART樹的介紹：
上圖為第K棵CART樹，確定一棵CART樹需要確定兩部分，第一部分就是樹的結構，這個結構將輸入樣本映射到一個確定的葉子節點上，記為
。第二部分就是各個葉子節點的值，q(x)表示輸出的葉子節點序號，
表示對應葉子節點序號的值。由定義得：
樹的複雜度定義
XGBoost法對應的模型包含了多棵cart樹，定義每棵樹的複雜度：
其中T為葉子節點的個數，||w||為葉子節點向量的模 。γ表示節點切分的難度，λ表示L2正則化係數。
如下例樹的複雜度表示：
目標函數推導
根據（3.1）式，共進行t次迭代的學習模型的目標函數為：
泰勒公式的二階導近似表示：
令
為Δx，則（3.5）式的二階近似展開：
其中：
表示前t-1棵樹組成的學習模型的預測誤差，gi和hi分別表示預測誤差對當前模型的一階導和二階導 ，當前模型往預測誤差減小的方向進行迭代。
忽略（3.8）式常數項，並結合（3.4）式，得：
通過（3.2）式簡化（3.9）式：
（3.10）式第一部分是對所有訓練樣本集進行累加，因為所有樣本都是映射為樹的葉子節點，我們換種思維，從葉子節點出發，對所有的葉子節點進行累加，得：
令
Gj 表示映射為葉子節點 j 的所有輸入樣本的一階導之和，同理，Hj表示二階導之和。
得：
對於第 t 棵CART樹的某一個確定結構（可用q(x)表示），其葉子節點是相互獨立的，Gj和Hj是確定量，因此，（3.12）可以看成是關於葉子節點的一元二次函數 。最小化（3.12）式，得：
得到最終的目標函數：
（3.14）也稱為打分函數(scoring function)，它是衡量樹結構好壞的標準，值越小，代表這樣的結構越好 。我們用打分函數選擇最佳切分點，從而構建CART樹。
CART回歸樹的構建方法
上節推導得到的打分函數是衡量樹結構好壞的標準，因此，可用打分函數來選擇最佳切分點。首先確定樣本特徵的所有切分點，對每一個確定的切分點進行切分，切分好壞的標準如下：
Gain表示單節點obj*與切分後的兩個節點的樹obj*之差，遍歷所有特徵的切分點，找到最大Gain的切分點即是最佳分裂點，根據這種方法繼續切分節點，得到CART樹。若 γ 值設置的過大，則Gain為負，表示不切分該節點，因為切分後的樹結構變差了。γ值越大，表示對切分後obj下降幅度要求越嚴，這個值可以在XGBoost中設定。
XGBoost與GDBT的區別
1. XGBoost生成CART樹考慮了樹的複雜度，GDBT未考慮，GDBT在樹的剪枝步驟中考慮了樹的複雜度。
2. XGBoost是擬合上一輪損失函數的二階導展開，GDBT是擬合上一輪損失函數的一階導展開，因此，XGBoost的準確性更高，且滿足相同的訓練效果，需要的迭代次數更少。
3. XGBoost與GDBT都是逐次迭代來提高模型性能，但是XGBoost在選取最佳切分點時可以開啟多線程進行，大大提高了運行速度。
PS:本節只選取了與本文內容相關的幾個區別。
參考
陳天奇 《XGBoost:A Scalable Tree Boosting System》
李航 《統計學習方法》
-END-