xgboost的原理沒你想像的那么難

xgboost 已然火爆機器學習圈，相信不少朋友都使用過。要想徹底掌握xgboost，就必須搞懂其內部的模型原理。這樣才能將各個參數對應到模型內部，進而理解參數的含義，根據需要進行調參。本文的目的就是讓大家盡可能輕松地理解其內部原理。主要參考文獻是陳天奇的這篇文章introduction to xgboost。在我看來，這篇文章是介紹xgboost最好的，沒有之一。英語好的同學建議直接看英文，若有不是很理解的地方，再來參考本文。

1、你需要提前掌握的幾個知識點

1、監督學習
監督學習就是訓練數據有標簽的學習。比如說，我有10萬條數據，每個數據有100個特征，還有一個標簽。標簽的內容取決于學習的問題，如果數據是病人進行癌癥診斷做的各項檢查的結果，標簽就是病人是否得癌癥。是為1，不是為0.

監督學習就是要從這10萬條數據中學習到根據檢查結果診斷病人是否得癌癥的知識。由于學習的范圍限定在這10萬條數據中，也就是說，學習的知識必須是從這10萬條數據中提煉出來。形象地理解，就是在這10萬條帶標簽數據的“監督”下進行學習。因此稱為監督學習。
2、監督學習的成果
監督學習學習到的知識如何表示，又是如何被我們人類使用呢？簡單講，學習到的知識用一個模型來表示，我們人類就用這個模型來使用學習到的知識。
那么，模型是什么東西？
模型就是一個數學表達式。最簡單的一個模型就是線性模型，它長這個樣子：y^i=∑jθjxij。用我們上面的例子講，xi就是我們10萬條數據中的第i條，xij就是第i條數據中的第j個檢查結果。y^i就是模型對這條數據的預測結果，這個值越大，表明病人得癌癥的概率也大。通常，我們還需將y^i處理成0到1的值，以更清晰地表明這是一個概率預測，處理的方法一般是用sigmoid函數，不熟悉的朋友可參考其他資料。θj就是第j個檢查結果對病人是否得癌癥的“貢獻度”，它是我們模型的參數，也就是我們從10條數據中學習到的知識。

可見，所謂監督學習，就是兩步，一是定出模型確定參數，二是根據訓練數據找出最佳的參數值，所謂最佳，從應用角度看，就是最大程度地吸收了10萬條訓練數據中的知識，但從我們尋找參數的過程來看，卻有另一番解釋，下文會詳細解釋，找到最佳參數后，我們就得出一個參數都是已知的模型，此時，知識就在其中，我們可以自由使用。

3、如何找出最佳參數
以上面的線性模型為例，病人有100個檢查結果，那么就有100個參數θj（j從1到100）。每個參數可取值都是實數，100個參數的組合顯然有無窮多個，我們怎么評判一組參數是不是最佳的呢？
此時，我們需要另外一個函數來幫助我們來確定參數是否是最佳的，這就是目標函數(object function)。

目標函數如何確定呢？用我們上面的例子來講，我們要判斷病人是否得癌癥，假設我們對上面的線性模型的值y^i進行了處理，將它規約到了0和1之間。我們的10萬條訓練數據中，得癌癥的病人標簽為1，沒得的標簽為0.那么顯然，最佳的參數一定就是能夠將得癌癥的病人全預測為1，沒得癌癥的病人全部預測為0的參數。這幾乎就是完美的參數！
因此，我們的目標函數可以設為MSE函數：obj = ∑i(sigmoid(∑jθjxij) - yi)^2

上面的函數的意思就是對第i條數據，將模型預測的值規約到0和1，然后與該條數據的真是標簽值（0和1）做差，再求平方。這個平方值越大，表明預測的越不準，就是模型的預測誤差，最后，我們將模型對10萬條數據的預測誤差求和。就得出了一組具體的參數的預測好壞的度量值。

果真這樣就完美了嗎？
不是的。上面的目標函數僅僅評測了參數對訓練數據來說的好壞，并沒有評測我們使用模型做預測時，這組參數表現好壞。也就是說，對訓練數據來說是好的參數，未必在預測時就是好的。為什么？
一是10萬條數據中有錯誤存在
二是10萬條數據未必涵蓋了所有種類的樣本，舉個極端的例子，假如10萬條數據全是60歲以上老人的檢查結果，我們用學習到的模型取預測一個10歲的小孩，很可能是不準的。

那么，怎么評測一組參數是否對預測是好的呢？
答案是測了才知道！

這不是廢話嗎。

事實就是這樣。真實的預測是最權威的評判。但我們還是可以有所作為的，那就是正則化。

所謂正則化就是對參數施加一定的控制，防止參數走向極端。以上面的例子來說，假如10萬條數據中，得癌癥的病人都是60歲以上老人，沒得癌癥的病人都是30歲以下年輕人，檢查結果中有一項是骨質密度，通常，老人骨質密度低，年輕人骨質密度高。那么我們學習到的模型很可能是這樣的，對骨質密度這項對應的參數θj設的非常大，其他的參數都非常小，簡單講，模型傾向于就用這一項檢查結果去判斷病人是否得癌癥，因為這樣會讓目標函數最小。

明眼人一看便知，這樣的參數做預測肯定是不好的。

正則化可以幫助我們規避這樣的問題。

常用的正則化就是L2正則，也就是所有參數的平方和。我們希望這個和盡可能小的同時，模型對訓練數據有盡可能好的預測。

最后，我們將L2正則項加到最初的目標函數上，就得出了最終的目標函數：
obj = ∑_i(sigmoid(∑_jθjxij) - yi)^2 + ∑j(θj^2)

能使這個函數值最小的那組參數就是我們要找的最佳參數。這個obj包含的兩項分別稱為損失函數和正則項。
這里的正則項，本質上是用來控制模型的復雜度。

Notes:
上面，我們為了盡可能簡單地說明問題，有意忽略了一些重要的方面。比如，我們的例子是分類，但使用的損失函數卻是MSE，通常是不這樣用的。
對于回歸問題，我們常用的損失函數是MSE，即：

回歸.PNG

對于分類問題，我們常用的損失函數是對數損失函數：

分類.PNG

乍一看，這個損失函數怪怪的，我們不免要問，為什么這個函數就是能評判一組參數對訓練數據的好壞呢？

我們用上面的例子來說明，假如有一條樣本，它的標簽是1，也就是yi = 1，那么關于這條樣本的損失函數中就只剩下了左邊那一部分，由于yi = 1，最終的形式就是這樣的：

對數1.PNG

頭上帶一個小尖帽的yi就是我們模型的預測值，顯然這個值越大，則上面的函數越傾向于0，yi趨向于無窮大時，損失值為0。這符合我們的要求。

同理，對于yi=0的樣本也可以做出類似的分析。

至于這個損失函數是怎么推導出來的，有兩個辦法，一個是用LR，一個是用最大熵。具體的推導過程請參閱其他資料。

2、xgboost

既然xgboost就是一個監督模型，那么我們的第一個問題就是：xgboost對應的模型是什么？
答案就是一堆CART樹。
此時，可能我們又有疑問了，CART樹是什么？這個問題請查閱其他資料，我的博客中也有相關文章涉及過。然后，一堆樹如何做預測呢？答案非常簡單，就是將每棵樹的預測值加到一起作為最終的預測值，可謂簡單粗暴。

下圖就是CART樹和一堆CART樹的示例，用來判斷一個人是否會喜歡計算機游戲：

predict1.PNG predict2.PNG

第二圖的底部說明了如何用一堆CART樹做預測，就是簡單將各個樹的預測分數相加。

xgboost為什么使用CART樹而不是用普通的決策樹呢？
簡單講，對于分類問題，由于CART樹的葉子節點對應的值是一個實際的分數，而非一個確定的類別，這將有利于實現高效的優化算法。xgboost出名的原因一是準，二是快，之所以快，其中就有選用CART樹的一份功勞。

知道了xgboost的模型，我們需要用數學來準確地表示這個模型，如下所示：

predict3.PNG

這里的K就是樹的棵數，F表示所有可能的CART樹，f表示一棵具體的CART樹。這個模型由K棵CART樹組成。模型表示出來后，我們自然而然就想問，這個模型的參數是什么？因為我們知道，“知識”蘊含在參數之中。第二，用來優化這些參數的目標函數又是什么？

我們先來看第二個問題，模型的目標函數，如下所示：

predict4.PNG

這個目標函數同樣包含兩部分，第一部分就是損失函數，第二部分就是正則項，這里的正則化項由K棵樹的正則化項相加而來，你可能會好奇，一棵樹的正則化項是什么？可暫時保持住你的好奇心，后面會有答案。現在看來，它們都還比較抽象，不要著急，后面會逐一將它們具體化。

3、訓練xgboost

上面，我們獲取了xgboost模型和它的目標函數，那么訓練的任務就是通過最小化目標函數來找到最佳的參數組。

問題是參數在哪里？

我們很自然地想到，xgboost模型由CART樹組成，參數自然存在于每棵CART樹之中。那么，就單一的 CART樹而言，它的參數是什么呢？
根據上面對CART樹的介紹，我們知道，確定一棵CART樹需要確定兩部分，第一部分就是樹的結構，這個結構負責將一個樣本映射到一個確定的葉子節點上，其本質上就是一個函數。第二部分就是各個葉子節點上的分數。

似乎遇到麻煩了，你要說葉子節點的分數作為參數，還是沒問題的，但樹的結構如何作為參數呢？而且我們還不是一棵樹，而是K棵樹!

讓我們想像一下，如果K棵樹的結構都已經確定，那么整個模型剩下的就是所有K棵樹的葉子節點的值，模型的正則化項也可以設為各個葉子節點的值的平方和。此時，整個目標函數其實就是一個K棵樹的所有葉子節點的值的函數，我們就可以使用梯度下降或者隨機梯度下降來優化目標函數。現在這個辦法不靈了，必須另外尋找辦法。

4、加法訓練

所謂加法訓練，本質上是一個元算法，適用于所有的加法模型，它是一種啟發式算法。關于這個算法，我的另一篇講GBDT的文章中有詳細的介紹，這里不再重復，不熟悉的朋友，可以看一下。運用加法訓練，我們的目標不再是直接優化整個目標函數，這已經被我們證明是行不通的。而是分步驟優化目標函數，首先優化第一棵樹，完了之后再優化第二棵樹，直至優化完K棵樹。整個過程如下圖所示：

predict6.PNG

在第t步時，我們添加了一棵最優的CART樹ft，這棵最優的CART樹ft是怎么得來的呢？非常簡單，就是在現有的t-1棵樹的基礎上，使得目標函數最小的那棵CART樹，如下圖所示：

10.PNG

假如我們使用的損失函數時MSE，那么上述表達式會變成這個樣子：

11.PNG

這個式子非常漂亮，因為它含有ft(xi)的一次式和二次式，而且一次式項的系數是殘差。你可能好奇，為什么有一次式和二次式就漂亮，因為它會對我們后續的優化提供很多方便，繼續前進你就明白了。
注意：ft(xi)是什么？它其實就是ft的某個葉子節點的值。之前我們提到過，葉子節點的值是可以作為模型的參數的。

但是對于其他的損失函數，我們未必能得出如此漂亮的式子，所以，對于一般的損失函數，我們需要將其作泰勒二階展開，如下所示：

12.PNG

其中：

13.PNG

這里有必要再明確一下，gi和hi的含義。gi怎么理解呢？現有t-1棵樹是不是？這t-1棵樹組成的模型對第i個訓練樣本有一個預測值y^i是不是？這個y^i與第i個樣本的真實標簽yi肯定有差距是不是？這個差距可以用l(yi,y^i)這個損失函數來衡量是不是？現在gi和hi的含義你已經清楚了是不是？

來，答一個小問題，在優化第t棵樹時，有多少個gi和hi要計算？嗯，沒錯就是各有N個，N是訓練樣本的數量。如果有10萬樣本，在優化第t棵樹時，就需要計算出個10萬個gi和hi。感覺好像很麻煩是不是？但是你再想一想，這10萬個gi之間是不是沒有啥關系？是不是可以并行計算呢？聰明的你想必再一次感受到了，為什么xgboost會辣么快！

好，現在我們來審視下這個式子，哪些是常量，哪些是變量。式子最后有一個constant項，聰明如你，肯定猜到了，它就是前t-1棵樹的正則化項。l(yi, yi^t-1)也是常數項。剩下的三個變量項分別是第t棵CART樹的一次式，二次式，和整棵樹的正則化項。再次提醒，這里所謂的樹的一次式，二次式，其實都是某個葉子節點的值的一次式，二次式。

我們的目標是讓這個目標函數最小化，常數項顯然沒有什么用，我們把它們去掉，就變成了下面這樣：

14.PNG

好，現在我們可以回答之前的一個問題了，為什么一次式和二次式顯得那么漂亮。因為這些一次式和二次式的系數是gi和hi，而gi和hi可以并行地求出來。而且，gi和hi是不依賴于損失函數的形式的，只要這個損失函數二次可微就可以了。這有什么好處呢？好處就是xgboost可以支持自定義損失函數，只需滿足二次可微即可。強大了我的哥是不是？

5、模型正則化項

上面的式子已然很漂亮，但是，后面的Ω(ft)仍然是云遮霧罩，不清不楚。現在我們就來定義如何衡量一棵樹的正則化項。這個事兒并沒有一個客觀的標準，可以見仁見智。為此，我們先對CART樹作另一番定義，如下所示：

16.PNG

需要解釋下這個定義，首先，一棵樹有T個葉子節點，這T個葉子節點的值組成了一個T維向量w，q(x)是一個映射，用來將樣本映射成1到T的某個值，也就是把它分到某個葉子節點，q(x)其實就代表了CART樹的結構。w_q(x)自然就是這棵樹對樣本x的預測值了。

有了這個定義，xgboost就使用了如下的正則化項：

17.PNG

注意：這里出現了γ和λ，這是xgboost自己定義的，在使用xgboost時，你可以設定它們的值，顯然，γ越大，表示越希望獲得結構簡單的樹，因為此時對較多葉子節點的樹的懲罰越大。λ越大也是越希望獲得結構簡單的樹。

為什么xgboost要選擇這樣的正則化項？很簡單，好使！效果好才是真的好。

6、見證奇跡的時刻

至此，我們關于第t棵樹的優化目標已然很清晰，下面我們對它做如下變形，請睜大雙眼，集中精力：

18.PNG

這里需要停一停，認真體會下。Ij代表什么？它代表一個集合，集合中每個值代表一個訓練樣本的序號，整個集合就是被第t棵CART樹分到了第j個葉子節點上的訓練樣本。理解了這一點，再看這步轉換，其實就是內外求和順序的改變。如果感覺還有困難，歡迎評論留言。

進一步，我們可以做如下簡化：

19.PNG

其中的Gj和Hj應當是不言自明了。

對于第t棵CART樹的某一個確定的結構（可用q(x)表示），所有的Gj和Hj都是確定的。而且上式中各個葉子節點的值wj之間是互相獨立的。上式其實就是一個簡單的二次式，我們很容易求出各個葉子節點的最佳值以及此時目標函數的值。如下所示：

20.PNG

obj*代表了什么呢？
它表示了這棵樹的結構有多好，值越小，代表這樣結構越好！也就是說，它是衡量第t棵CART樹的結構好壞的標準。注意~注意~注意~，這個值僅僅是用來衡量結構的好壞的，與葉子節點的值可是無關的。為什么？請再仔細看一下obj*的推導過程。obj*只和Gj和Hj和T有關，而它們又只和樹的結構(q(x))有關，與葉子節點的值可是半毛關系沒有。如下圖所示：

23.PNG

7、找出最優的樹結構

好了，有了評判樹的結構好壞的標準，我們就可以先求最佳的樹結構，這個定出來后，最佳的葉子結點的值實際上在上面已經求出來了。

問題是：樹的結構近乎無限多，一個一個去測算它們的好壞程度，然后再取最好的顯然是不現實的。所以，我們仍然需要采取一點策略，這就是逐步學習出最佳的樹結構。這與我們將K棵樹的模型分解成一棵一棵樹來學習是一個道理，只不過從一棵一棵樹變成了一層一層節點而已。如果此時你還是有點蒙，沒關系，下面我們就來看一下具體的學習過程。
我們以上文提到過的判斷一個人是否喜歡計算機游戲為例子。最簡單的樹結構就是一個節點的樹。我們可以算出這棵單節點的樹的好壞程度obj*。假設我們現在想按照年齡將這棵單節點樹進行分叉，我們需要知道：
1、按照年齡分是否有效，也就是是否減少了obj的值
2、如果可分，那么以哪個年齡值來分。

為了回答上面兩個問題，我們可以將這一家五口人按照年齡做個排序。如下圖所示：

29.PNG

按照這個圖從左至右掃描，我們就可以找出所有的切分點。對每一個確定的切分點，我們衡量切分好壞的標準如下：

27.PNG

這個Gain實際上就是單節點的obj*減去切分后的兩個節點的樹obj*，Gain如果是正的，并且值越大，表示切分后obj*越小于單節點的obj*，就越值得切分。同時，我們還可以觀察到，Gain的左半部分如果小于右側的γ，則Gain就是負的，表明切分后obj反而變大了。γ在這里實際上是一個臨界值，它的值越大，表示我們對切分后obj下降幅度要求越嚴。這個值也是可以在xgboost中設定的。

掃描結束后，我們就可以確定是否切分，如果切分，對切分出來的兩個節點，遞歸地調用這個切分過程，我們就能獲得一個相對較好的樹結構。

注意：xgboost的切分操作和普通的決策樹切分過程是不一樣的。普通的決策樹在切分的時候并不考慮樹的復雜度，而依賴后續的剪枝操作來控制。xgboost在切分的時候就已經考慮了樹的復雜度，就是那個γ參數。所以，它不需要進行單獨的剪枝操作。

8、大功告成

最優的樹結構找到后，確定最優的葉子節點就很容易了。我們成功地找出了第t棵樹！撒花！！！

</div><!-- --><div class="show-foot"><a class="notebook" href="/nb/7305482"><i class="iconfont ic-search-notebook"></i><span>機器學習</span>

</div><div class="modal-wrap" data-report-note=""><a id="report-modal"></a></div></div> </div>

總結

以上是生活随笔為你收集整理的一篇写的很好的XGBoost的博客（于简书转载）的全部內容，希望文章能夠幫你解決所遇到的問題。

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