大家好，這是我們xgboost系列的第一篇。xgboost[1]是一個在機器學習面試中被問到的一個算法。
首先我們探討一下理解xgboost的核心的一件事。那就是xgboost的數學模型，想要理解它，這個數學是跳不過去的。本小節主要就是講述xgbosot的數學原理。
xgboost是基於提升樹的概念，這種思想就是說學習一棵樹可能效果很差，因為一棵樹比較不穩定，去除某些特徵或者樣本以後，重新訓練，樹的結構可能會變化，這就導致預測的結果不穩定。
為了讓模型的效果更魯棒（結果更穩定一點），我們可以訓練一棵樹後，然後看樹哪些地方沒訓練好，比如說根據訓練的predict與目標的差距。然後再建一棵樹，擬合這些差距。這就是boost方法的思路，
xgbosot是boost方法的一種。
下面我將從它的目標函數、正則化、分割點的搜尋這幾個方面講一下xgbosot
一、優化的目標函數
首先xgboost的目標函數（損失函數）如下：
等式左邊是t時刻的損失函數，右邊的小l表示每個樣本的損失，n表示樣本數量。
小 L 裡面有兩項，第一項為：
這是需要優化的損失，xgboost的預測值是第t步的預測值和t-1棵樹的所有預測值的和作為預測的值。對於每個樣本，每棵樹都會給他分到一個葉節點。把這t棵樹的葉節點相加就是樹第t步的預測。
我們希望預測和真實值之間相差很小，比如可以選擇mse作為損失函數。
第二項為：
這是一個正則項。式子中的t都表示第t顆樹，也就是說對每棵樹都這麼操作。
二、正則項的真實面目
剛接觸到xgboost，我感覺非常的牛，樹不像LR或者神經網絡一樣有明顯的參數，怎麼做正則化呢？
正則化的本質是減少樹的複雜度，樹的複雜度可以用樹的深度、葉節點的個數表示。
xgboost也用到了類似的想法。xgboost的一棵樹的正則化公式如下：
等式右邊第一項T表示葉節點的個數。第二項的w看著跟神經網絡的參數類似，其實我們可以把樹的葉節點的值當作樹優化的目標，這個w就是每個葉節點的值。兩邊的係數是參數。
三、如何最小化目標函數？
高數中我們都學過泰勒展開式，xgboost也用了泰勒展開式的例子。假如我們在
把損失函數按照二階泰勒公式展開，則損失函數變成：
gi為在
的一階導數，hi為二階導數。
將常數去掉後，損失函數為：
如果定義Ij為第j個葉節點，公式為：
裡面的i是說第i個樣本，q是一個映射函數，意思是將Xi映射到第j個節點。
將損失函數改寫成下式：
我們需要求極值，我們需要求的參數是w，也就是葉節點的值，直接將第二行求導等於0就可以，得：
’
將wj帶入到上面損失函數的式子中得：
四、分裂點的度量
在第三小節，我們知道了當我們知道樹的結構的時候，如何分配葉節點的值，讓損失函數最小化。本小結講述xgboost如何度量分裂點。決策樹可以是信息增益、基尼指數等。xgboost也有一個類似的度量方法，就是根據分割後的損失函數和與原損失函數的差來衡量分割點的優劣。
xgboost是一個二叉樹，也就是說，從根節點出發， 分出兩個岔。它的計算方法是分裂一棵樹，然後計算損失函數減小的值，哪種分裂方法損失函數減小得越多，就選哪種方法，計算公式如下:
這個公式就是把當前的損失減去左右節點的損失。
總結：我們講述了xgboost目標函數、正則化、如何優化目標函數、分裂點的度量，下一節將講述樹的分裂方法。
參考文獻
[1] https://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf
