前言

XGBoost是一個可擴展的提升樹模型，論文“XGBoost: A Scalable Tree Boosting System”發表在2016年的KDD會議上。文章包括了XGBoost的原理以及對其的優化。本文主要分享XGBoost的推導過程，包含論文內容2.1-2.2部分，這里假設你已掌握決策樹、GBDT的相關知識。

本文約2.7k字，預計閱讀10分鐘。

XGBoost原理

XGBoost最關鍵的思想就是采用二階導來近似取代一般損失函數。整個推導過程分為以下幾個步驟（問題）：

目標函數的構造；

目標函數難以優化，如何近似？

將樹的結構（參數化，因為模型的學習參數在樹中）融入到目標函數；

如何構造最優（局部）二叉樹？采用貪心算法；

目標函數定義

首先我們假設一個數據集中包含個樣本以及每個樣本有個特征，因此數據集可以定義為：

對于提升樹模型來說，我們假設共有個疊加函數（additive functions，即決策樹），那么整個模型可以表示為：

其中：

• ：表示模型對樣本的預測值；

• ：模型函數；

• ：表示單個樣本；

• ：表示第決策樹；

• ；表示決策樹的空間集合；

我們要學習上述集成模型函數（也稱加法模型），則需要最小化正則化后的損失函數（即目標函數，正則化是對復雜決策樹的懲罰）：

表示第個決策樹的復雜度，這里我們先不去參數化和。

梯度提升算法

問題1：?對于上述的目標函數，其實很難在歐氏空間中使用傳統的優化方法。

因此，提升樹模型采用前向分步的學習方法。假設表示在第次迭代時對第個樣本的預測，那么我們可以將目標函數轉化為以下形式（這里假設你已掌握提升樹算法的知識）：

其中，表示第次迭代時，集成模型對樣本的預測，表示第個決策樹。為常數，所以我們只需要學習，當然對于決策樹復雜度的刻畫，前的決策樹的復雜度此時為常數，所以目標函數并沒有包括。

【注】：為一個常數，我們當然盡可能希望其與真實值更近，為兩者之間的一個「殘差」，希望盡可能的趨于0，所以這就是為什么后面我們可以將看成。

問題2：?此時，目標函數變得更為簡單，但是仍然無法描述損失函數，因為并不知道其類型，一般的復雜函數也很難刻畫。

所以，我們需要一個近似函數來表示損失函數。論文中提到，采用在一般設定下，二階近似法（Second-order approximation）可用于快速優化目標。論文這里引用了一篇參考文獻，其實就是通過泰勒公式用函數在某點的信息描述其附近取值。

首先可以了解微分（微分是函數在一點附近的最佳線性近似）來近似表示一般函數【從幾何的角度講，就是在某點的切線來近似于原函數附近的曲線，二階近似則是采用拋物線】：

為高階無窮小，所以：

所以附近的值可以用上述線性近似來表示，「而GBDT就是采用線性近似（微分）來描述一般的損失函數。」 對于XGBoost來說，采用二階近似（二階泰勒公式）來描述損失函數：

那么如何應用在我們定義的損失函數？其實可以對應于，對應于，所以可以得到近似的損失函數：

我們令，因此近似目標函數化簡為

并且為一個常數，所以可以去掉：

【注】：一階導和二階導是已知的，因此需要學習的參數包含在中。

問題3：如何參數化【將需要學習的參數在目標函數中顯示】表示和決策樹的復雜度？

對于，文章給出定義：

其中表示表示單個樹的結構，即樣本對應的葉子結點的索引。表示葉子結點的值。【某個樣本的預測值對應于某個葉子結點的值，這樣就能描述清楚決策樹上對應每個樣本的預測值】。但是下標依舊帶有參數，所以最終作者用：

表示「決策樹中分配到第個葉子結點中的樣本集合」，這樣，所有的葉子結點集合就能描述整個決策樹。

而決策樹的復雜度與葉子結點的數量和葉子結點的值（學習參數）相關，所以一般表示為：

所以，我們將目標函數表示為：

可以看到，這其實是關于的一個二次函數，我們可以使用中學的知識，最優解為，即：

計算對應的目標函數為：

以上便是XGBoost的梯度提升算法的推導過程。

尋找分割點（決策樹構造）

上述近似目標函數可以作為一個決策樹的評價分數，但是我們之前對于最小化目標函數來優化決策樹的值是「假定決策樹的結構是已知的」。簡單來說，就是目前我們可以做到給定一個決策樹的結構，我們可以將它的葉子結點的值進行優化，并且可以達到一個評價它性能的分數。

問題4：如何構造決策樹？

最簡單的方法是將所有決策樹的結構全部羅列出來，然后優化，計算他們的目標函數值，進行比較，選擇最小目標函數值的決策樹。但是如果決策樹深度過深，那么所有決策樹的數量太多，很難完成上述步驟。

所以，文章采用了一種貪心算法（greedy algorithm）的策略，從單個葉子結點開始，迭代的增加分治進行比較。

假設，當前有樣本，目前決策樹為：

其目標函數值可以表示為：

我們對右下葉子結點增加新的分支：

此時目標函數值為：

我們將兩者相減，得到：

如果，則說明可以進行分支，所以我們可以推導出，

其中與指代分割葉子結點后的新的左右葉子結點。通過以上分割方法，就可以分步的找到基于貪心的局部最優決策樹。

總結

上述是我結合論文的2.1和2.2部分內容進行總結、解釋與擴展，并不包括后續的各種優化方法。

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯 本站qq群704220115，加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的【机器学习基础】结合论文理解XGBoost推导过程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。