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

邀請關注微信公眾號：人工智慧LeadAI（ID:atleadai）

歡迎訪問我們的官方主頁：www.leadai.org

正文共6928個字，22張圖，預計閱讀時間：18分鐘。

xgboost 已然火爆機器學習圈，相信不少朋友都使用過。要想徹底掌握xgboost，就必須搞懂其內部的模型原理。這樣才能將各個參數對應到模型內部，進而理解參數的含義，根據需要進行調參。

本文的目的就是讓大家儘可能輕鬆地理解其內部原理。主要參考文獻是陳天奇的這篇文章introduction to xgboost。在我看來，這篇文章是介紹xgboost最好的，沒有之一。英語好的同學建議直接看英文，若有不是很理解的地方，再來參考本文。

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

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，即：

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

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

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

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

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

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

02xgboost

既然xgboost就是一個監督模型，那麼我們的第一個問題就是：xgboost對應的模型是什麼？

答案就是一堆CART樹。

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

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

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

xgboost為什麼使用CART樹而不是用普通的決策樹呢？

簡單講，對於分類問題，由於CART樹的葉子節點對應的值是一個實際的分數，而非一個確定的類別，這將有利於實現高效的優化演算法。xgboost出名的原因一是准，二是快，之所以快，其中就有選用CART樹的一份功勞。

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

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

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

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

03訓練xgboost

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

問題是參數在哪裡？

我們很自然地想到，xgboost模型由CART樹組成，參數自然存在於每棵CART樹之中。那麼，就單一的 CART樹而言，它的參數是什麼呢？

根據上面對CART樹的介紹，我們知道，確定一棵CART樹需要確定兩部分，第一部分就是樹的結構，這個結構負責將一個樣本映射到一個確定的葉子節點上，其本質上就是一個函數。第二部分就是各個葉子節點上的分數。

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

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

04加法訓練

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

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

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

這個式子非常漂亮，因為它含有ft(xi)的一次式和二次式，而且一次式項的係數是殘差。你可能好奇，為什麼有一次式和二次式就漂亮，因為它會對我們後續的優化提供很多方便，繼續前進你就明白了。

注意：ft(xi)是什麼？它其實就是ft的某個葉子節點的值。之前我們提到過，葉子節點的值是可以作為模型的參數的。

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

其中：

這裡有必要再明確一下，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樹的一次式，二次式，和整棵樹的正則化項。再次提醒，這裡所謂的樹的一次式，二次式，其實都是某個葉子節點的值的一次式，二次式。

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

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

05模型正則化項

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

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

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

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

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

06見證奇蹟的時刻

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

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

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

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

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

obj*代表了什麼呢？

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

07找出最優的樹結構

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

問題是：樹的結構近乎無限多，一個一個去測算它們的好壞程度，然後再取最好的顯然是不現實的。所以，我們仍然需要採取一點策略，這就是逐步學習出最佳的樹結構。這與我們將K棵樹的模型分解成一棵一棵樹來學習是一個道理，只不過從一棵一棵樹變成了一層一層節點而已。如果此時你還是有點蒙，沒關係，下面我們就來看一下具體的學習過程。

我們以上文提到過的判斷一個人是否喜歡計算機遊戲為例子。最簡單的樹結構就是一個節點的樹。我們可以算出這棵單節點的樹的好壞程度obj*。假設我們現在想按照年齡將這棵單節點樹進行分叉，我們需要知道：

1、按照年齡分是否有效，也就是是否減少了obj的值

2、如果可分，那麼以哪個年齡值來分。

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

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

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

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

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

08大功告成

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

原文鏈接：http://www.jianshu.com/p/d8222a84613c

查閱更為簡潔方便的分類文章以及最新的課程、產品信息，請移步至全新呈現的

www.leadai.org

關注人工智慧LeadAI公眾號，查看更多專業文章

http://weixin.qq.com/r/ZDnC2j-E5GKbrXu592x2 (二維碼自動識別)

大家都在看

LSTM模型在問答系統中的應用

基於TensorFlow的神經網路解決用戶流失概覽問題

最全常見演算法工程師面試題目整理（一）

最全常見演算法工程師面試題目整理（二）

TensorFlow從1到2 | 第三章 深度學習革命的開端：卷積神經網路

裝飾器 | Python高級編程

今天不如來複習下Python基礎