XGBoost是目前炙手可熱的算法，适合抽象資料的分析問題，在Kaggle等比賽中率獲佳績。市面上雖然有大量介紹XGBoost原理與使用的文章，但少有能清晰透徹的講清其原理的。本文的目标是對XGBoost的原理進行系統而深入的講解，幫助大家真正了解算法的原理。文章是對已經在清華達成出版社出版的《機器學習與應用》（雷明著）的補充。在這本書裡系統的講解了內建學習、bagging與随機森林、boosting與各類AdaBoost算法的原理及其實作、應用。AdaBoost與梯度提升，XGBoost的推導都需要使用廣義加法模型，對此也有深入的介紹。
了解XGBoost的原理需要決策樹（尤其是分類與回歸樹），內建學習，廣義加法模型，牛頓法等基礎知識。其中，決策樹在SIGAI之前的文章“了解決策樹”中已經做了深入的講解。內建學習在之前的文章“随機森林概述”，“大話AdaBoost算法”，“了解AdaBoost算法”中已經做了講解。牛頓法在之前的文章“了解梯度下降法”，“了解凸優化”，“了解牛頓法”中已經進行了介紹。如果讀者對這些知識還不清楚，建議先閱讀這些文章。
分類與回歸樹
決策樹時機器學習中古老的算法，可以看做是一組嵌套的判定規則，這組規則通過訓練得到。從數學上看，決策樹是一個分段常數函數，每個葉子節點對應空間中的一片區域，落入此區域的向量x被預測為該葉子節點的值。
分類與回歸樹是二叉決策樹的一種，既可以用于分類問題，也可以用于回歸問題。訓練時要解決的核心問題是尋找最佳分裂來确定内部節點，遞歸建構樹，為葉子節點賦予标簽值。對于分類問題，尋找最佳分裂時的目标是最大化Gini純度值，簡化後的計算公式為
其中NL是分裂之後左子節點的訓練樣本數，NL,i是左子節點中第i類樣本數；NR是分裂之後右子節點的訓練樣本數，NR,i是右子節點中第i類樣本數。對于回歸問題，尋找最佳分裂時優化的目标是最大化回歸誤差的下降值
因為特征向量中有多個特征，是以實作時需要為每個特征分量計算最佳分裂門檻值，然後取其中最優的。為單個特征計算最佳分裂門檻值時，首先将該節點的所有訓練樣本按照該特征分量從小到大排序，然後依次以每個特征值作為門檻值，将樣本集分為左右兩個子集，然後計算上面的分裂名額，取其最優值。具體原理在《機器學習與應用》一書中已經詳細講述。
第二個問題是葉子節點值的設定。對于分類問題，将葉子節點的值設定成本節點的訓練樣本集中出現機率最大的那個類；對于回歸樹，則設定為本節點訓練樣本标簽值的均值。
內建學習
內建學習是機器學習中的一大類算法，它代表了一種樸素的思想：将多個機器學習模型組合起來使用，得到一個更強的模型。被組合的模型稱為弱學習器，組合之後的模型稱為強學習器。根據組合的政策不同，誕生了各種不同的算法。其中最常用的是bagging與boosting。前者的代表作是随機森林，後者的代表作是AdaBoost，梯度提升，XGBoost。
廣義加法模型
在弱學習器的組合方案中，如果使用加法，即将多個弱學習器的預測函數相加得到強學習器，則稱為廣義加法模型。廣義加法模型拟合的目标函數是多個基函數的線性組合
其中γi為基函數的參數，βi為基函數的權重系數。訓練時要确定的是基函數的參數和權重值，如果用決策樹充當基函數，則參數為比較特征、比較門檻值，葉子節點值等。訓練時的目标是最小化對所有樣本的損失函數
訓練算法采用了逐漸求精的政策，依次确定每個基函數的參數和權重，然後将其加入強學習器中，使得強學習器的精度提升。實際實作時，将目前已經得到的強學習器對訓練樣本的輸出值當做常數。然後采用分階段優化政策，先固定住權重值βi，優化弱學習器。然後再将弱學習器當做常數，優化權重值βi。
以AdaBoost算法為例，強分類器對單個訓練樣本的損失為指數損失函數
将廣義加法模型的預測函數代入上面的損失函數中，得到算法訓練時要優化的目标函數為
這裡将指數函數拆成了兩部分，已有的強分類器Fj-1，以及目前弱分類器f對訓練樣本的損失函數，前者在之前的疊代中已經求出，是以Fj-1 (xi )可以看成常數。這樣目标函數可以簡化為
其中
它隻和前面的疊代得到的強分類器有關，與目前的弱分類器、弱分類器權重無關，這就是AdaBoost算法的樣本權重。這個問題可以分兩步求解，首先将β看成常數，優化f(xi)；然後固定f(xi)，優化β。由此得到了AdaBoost的訓練算法。
從廣義加法模型可以推導出種AdaBoost算法，它們的弱分類器不同，訓練時優化的目标函數也不同，分别是：
離散型AdaBoost
實數型AdaBoost算法
LogitBoost
Gentle型AdaBoost
各種AdaBoost算法的原理以及廣義加法模型在《機器學習與應用》一書中有詳細的講述，限于篇幅，在這裡不過多介紹。
除AdaBoost算法之外，boosting還有其他實作算法，如梯度提升算法。梯度提升算法采用了不同的思路，同樣是使用廣義加法模型，但在求解時采用了最速下降法（梯度下降法的變種）。同樣是依次訓練每個弱學習器，但訓練弱學習器時沒有為訓練樣本加上權重，而是為其計算僞标簽值，該僞标簽值是損失函數對目前已經求得的強學習器對訓練樣本的預測值Fj-1 (xi )的導數的負值：
然後用此次疊代時要訓練的若學習器來拟合該目标。具體實作時分為了訓練弱學習器，尋找最優步長的直線搜尋（line search）這兩步。
牛頓法
牛頓法是求解函數極值的數值優化（近似求解）算法。根據微積分中的Fermat定理，函數在點x*處取得極值的必要條件是導數（對于多元函數是梯度）為0，即：
稱x*為函數的駐點。是以可以通過尋找函數的駐點求解函數的極值。直接計算函數的梯度然後解上面的方程組一般來是非常困難的，如果函數是一個複雜的非線性函數，這個方程組是一個非線性方程組，不易求解。是以大多采用疊代法近似計算。它從一個初始點x0開始，反複使用某種規則從xk移動到下一個點xk+1，直至到達函數的極值點。這些規則一般會利用一階導數資訊即梯度；或者二階導數資訊即Hessian矩陣。牛頓法采用了一階導數與二階導數資訊。
對多元函數在x0處作二階泰勒展開，有：
忽略二次及以上的項，将函數近似成二次函數，并對上式兩邊同時對x求梯度，得到函數的梯度為：
其中▽2 f(x0)即為Hessian矩陣H。令函數的梯度為0，則有：
解這個線性方程組可以得到：
由于在泰勒展開中忽略了高階項，是以這個解并不一定是函數的駐點，需要反複用這個公式進行疊代。從初始點x0處開始，反複計算函數在處的Hessian矩陣和梯度向量，然後用下面的公式進行疊代：
最終會到達函數的駐點處。其中-H-1g稱為牛頓方向。疊代終止的條件是梯度的模接近于0，或者函數值下降小于指定門檻值。對于一進制函數，Hessian矩陣即為二階導數，梯度向量即為一階導數，疊代公式為
在XGBoost的推導中将會使用此方法。
XGBoost
XGBoost是對梯度提升算法的改進，求解損失函數極值時使用了牛頓法，将損失函數泰勒展開到二階，另外在損失函數中加入了正則化項。訓練時的目标函數由兩部分構成，第一部分為梯度提升算法損失，第二部分為正則化項。XGBoost的損失函數定義為
其中n為訓練樣本數，l是對單個樣本的損失，yi'為預測值,yi為樣本真實标簽值，Φ為模型的參數。正則化項定義了模型的複雜程度
其中γ和λ為人工設定的系數，w為決策樹所有葉子節點值形成的向量，T為葉子節點數。正則化項由葉子節點數，葉子節點值向量的模平方兩項構成，第一項展現了決策樹結構的複雜程度，第二項展現了決策樹預測值的複雜程度。定義q為輸入向量X到決策樹葉子節點編号的映射，即根據輸入向量确定用決策樹的第幾個葉子節點值來預測它的輸出值
其中d為特征向量的維數。是以q定義了樹的結構，w定義了樹的輸出值。決策樹的映射函數可以寫成
與梯度提升算法相同，采用加法模型表示強學習器。假設yi,t'為第i個樣本在第t次疊代時的強學習器預測值，訓練時依次确定每一個弱學習器函數ft，加到強學習器預測函數中，即最小化如下目标函數
實作時用貪婪法将ft加入到模型中，以最小化目标函數值。注意，在這裡yi是常數，yi,t-1'+f(xi）是損失函數的自變量，而yi,t-1'也是常數。對于一般的損失函數無法求得上面優化問題的公式解。采用牛頓法近似求解，對目标函數在yi,t-1'點處作二階泰勒展開後得到
損失函數的一階導數為
與梯度提升算法相同，是将之前已經訓練得到的強學習器對樣本的預測值當做變量求導，這一點一定要了解，很多讀者困惑的地方在于不知道這個導數是對誰求導。損失函數的二階導數為
去掉與ft(xi）無關的常數項，可以得到化簡後的損失函數為
如果定義集合
即預測值為第j個葉子節點的訓練樣本集合（樣本下标集合）。由于每個訓練樣本隻屬于某一個葉子節點，目标函數可以拆分成對所有葉子節點損失函數的和
首先介紹葉子節點的值如何确定。如果決策樹的結構即q(x)确定，根據牛頓法可以得到第j個葉子節點的最優值為
這是單個葉子節點的損失函數對wj求導并令導數為0後解方程的結果。前面已經假定對單個樣本的損失函數是凸函數，是以必定是極小值。單個葉子節點的損失函數對wj的一階導數為
令其為0，即可得到上面的結果。
接下來說明如何确定決策樹的結構，即尋找最佳分裂。将wj的最優解代入損失函數，得到隻含有q的損失函數
此函數可以看做是對決策樹結構優劣的一個度量，要求其極小值，類似于決策樹尋找分裂時的不純度名額。假設節點在分裂之前的訓練樣本集為I，分裂之後左子節點的訓練樣本集為IL，右子節點的訓練樣本集為IR。分裂之後的葉子節點數增加1，是以上面目标函數的第二項由γT變為γ(T+1)，二者的內插補點為γ。将上面的目标函數取反，求Lt (q)的極小值等價于求-Lt (q)的極大值。尋找最佳分裂的目标是使得損失函數的下降值最大化
γ是常數，是以上式最右邊的-γ可以忽略。除了使用不同的分裂名額，其他過程與标準的決策樹訓練算法相同。在實作時将上面公式中的求和項定義為幾個變量，分别是所有訓練樣本的一階導數，二階導數之和
左右子集樣本的一階導數，二階導數之和
尋找最佳分裂的算法流程為
輸入資料I：，目前節點的訓練樣本集，訓練樣本數為n
輸入資料d：，特征向量維數
初始化分裂品質：score ← 0
計算所有樣本的一階導數，二階導數之和：G←∑i∈I gi ,H ←∑i∈I hi
循環，對k=1,...,d
對所有訓練樣本按照第k個特征升序排序
初始化左子集所有訓練樣本的一階導數，二階導數之和：GL ←0,HL =0
循環，對j=1,...,n，以第j個樣本的第k個特征分量xjk作為分裂門檻值
計算左子集所有樣本的一階導數和二階導數之和，在之前的基礎上加上本次
被從右
邊分到左邊的樣本的一階導數和二階導數值即可：GL ←GL +gi,HL ←HL +hj
計算右子集所有樣本的一階導數和二階導數之和，可以根據總和，左子集的和快速
計算：GR ←G-GL,HR ←H-HL
計算分裂分數的最大值：
結束循環
傳回：最大分裂品質score及其對應分裂（包括選用的特征，分裂門檻值）
XGBoost實作時還使用了權重收縮與列采樣技術，以抵抗過拟合。權重收縮的做法是在每訓練出一棵決策樹之後将其權重進行縮放，乘上系數η。權重收縮降低了之前的決策樹的影響，為将來要生成的決策樹留下了更多的空間。列采樣的做法與随機森林相同，每次尋找最佳分裂時隻考慮一部分随機抽取的特征分量。
參考文獻
[1] Jerome H Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics. 2001.
[2] Tianqi Chen, Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. knowledge discovery and data mining. 2016.
[3] Jerome Friedman, Trevor Hastie and Robert Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics 28(2), 337–407. 2000.