最近因為實習的緣故，是以開始複習各種算法推導~~~就先拿這個xgboost練練手吧。
(參考原作者ppt
連結：https://pan.baidu.com/s/1MN2eR-4BMY-jA5SIm6WCGg
提取碼：bt5s )
1.xgboost的原理
首先值得說明的是，xgboost是gbdt的更新版，有興趣的話可以先看看gbdt的推導。xgboost同樣是構造一棵棵樹來拟合殘差，但不同之處在于（1）gbdt使用一階導，xgboost使用二階導。（2）xgboost在loss中包括模型複雜度，gbdt沒有。
首先我們來定義一下模型：
1.符号定義：
2.模型定義
假設我們疊代T輪，意味着我們要生成T棵殘差樹:
值得注意的幾點：
1.其實一般來說，前面還要加上一個
，但是作者在這裡初始化的時候将
設定為0，是以不用加了。
2.ft(xi)表示的是第t棵殘差樹對xi的第t輪殘差的預測值。
3.每一輪殘差)樹的訓練資料是什麼呢？假如，yt表示t棵cart殘差樹的和，也就是最終預測值,y表示x的真實标簽，那麼第t+1棵樹的訓練資料就是（x,y-yt)
4.F是殘差樹的函數空間。
5.從函數的角度來說，每一個殘差樹類似一個分段函數。
2.損失函數定義
從公式的角度，xgboost的誤差來源主要是：訓練誤差和模型複雜度。
3.如何訓練殘差樹？
由于xgboost采取的是增量訓練，也就是說隻有前一棵樹訓練好了，才能開始訓練下一棵樹。這也就意味着，當我訓練第t棵樹的時候，1~t-1棵樹的參數都是固定的了，與其相關的量都是常量。我們可以将目标函數簡化一下：
上面的損失函數是沒有具體到每一輪的訓練，為了友善推導，我們把第t輪的loss表示如下：
由于存在以下關系：
是以，第t輪的loss化簡如下：
對于第一部分loss，由于泰勒展開式
，我們把
當作
，
當作
，那麼訓練loss可以化簡為：
那麼總loss變為：
在這個目标函數中，我們需要求的就隻有第t棵殘差樹的參數了。那麼一棵樹的參數又包括哪些呢？或者說我們要怎樣去表示這棵樹呢？在xgboost的原作者ppt中是這樣定義的：
其中，q(x)就表示x屬于哪一個葉子節點，比如說是第三個葉子節點，那麼wq(x)就表示第三個葉子節點的權值了，也可以了解為ft對x第t輪殘差的的預測值。另外K表示葉子節點的個數（我用的符号和原PPT不太一樣，原PPT用的符号是T，感覺和殘差樹的個數搞重了，是以就換了一個符号）。
下面說一下，模型複雜度的定義：
K是葉子節點的個數，K值越小，樹的結構就越簡單，進而不容易過拟合，這個很好了解，但是為什麼還要限制w呢，從某種意義上來說，w是ft對x第t輪殘差的的預測值,這個有必要限制嘛？我的思考是這樣的：xgboost不希望一次性就把資料拟合得很好，而是每次拟合一個大概就可以了，反正還可以繼續學的，也就是說每個殘差樹都是一個弱分類器，這樣也可以防止過拟合。其實這也是boosting一個比較重要的思想。那麼如何限制分類器拟合得太好呢，直接限制w的取值就可以了，試想如果某一個w很大，那麼目前這棵棵殘差樹在所有殘差樹就占很大的權重，這樣就容易導緻過拟合了。（自己的了解，有錯請指正）。
接下來，我們我們用具體的預測值來代替函數，在下面的變換中，loss的計算由以樣本為機關求和變味了以葉子節點為機關求和。
因為G和H都是常數，那麼這個問題就變成了一個二次問題了，求解最小值的方法就不多說了，直接給出結果（這個二次問題應該是開口向下的，我沒有主動算過，主要是看
的大小，但是常見的損失函數二次導應該是正的，大家可以去驗證一下）
我們說，目前我們得到的最優結果是基于這棵樹的結構已經确定的情況下得到的，但是樹的結構有很多種，那麼該如何确定這棵樹的結構呢？
原論文中采取貪婪算法來生成這棵樹：
1.從根節點開始；
2.周遊所有特征
3.對于每一個特征，如果是連續型特征，則将其按照從小到大排列，我們樣本數量假設有n個，那麼這個連續型的特征的切分點就有n-1個，我們就在每一個切分點都計算出一個“分裂增益值”，這個分裂增益值是什麼意思呢？它是用來判斷目前節點要不要進行分裂，如果分裂那麼選擇哪個特征的哪個切分點最好。那麼分裂增益值要怎麼算呢？原論文給出的算法如下：
GL是指左節點中所有樣本的g和，GR,HL,HR同理（這裡對g不知道是什麼的東西的同學，我把下面的公式再貼一次）
要知道，分裂後的改變就是葉子節點數多了一個，然後樣本被劃分到不同的葉子節點。這個Gain公式的原理用白話講就是，用左節點增益加右節點增益減去未進行分裂前的那個節點的增益減去因為多增加了一個節點而産生的
，那麼為什麼
可以表示一個節點的收益呢？由于
（剛剛計算出的當樹結構确定時的最優總loss），仔細觀察其結構，就是葉子節點總數乘以一個系數減去所有葉子節點的
和乘以一個系數，為了使得loss減小，那麼
越大越好，是以我們可以将
當作是第k個葉子節點的增益。
4.關于樹的剪枝
作者提出了兩種剪枝的方法pre-stopping和Post-Prunning,其實就是預剪枝和後減枝：
pre-stopping：我們在計算分裂增益值時，有可能得到負數，這個時候可以直接停止分裂了，這就是pre-stopping的思想，但是這種方法有缺陷：可能這次分裂雖然得到了負增益，但是可能會為後面的節點分裂帶來更好的收益。
Post-Prunning：這種方法是先按照上面的算法，不管深度，直接生成能夠達到的最大深度的樹，然後再根據負增益遞歸從下往上減枝。
5.一些其他問題
1.如果樣本帶有權重該怎麼辦？
假設樣本xi的權重為a，那麼将gi和hi分别變成a*gi,a*hi
2.還有什麼防止過拟合的方法？
變成
，
一般取0.1，這個意思和之前關于loss的構成解釋差不多，還是希望，前面的殘差樹不要學得太好，把細節末枝留給後面的樹學。（其實感覺這個是所有boosting方法防止過拟合的做法）
轉載于:https://www.cnblogs.com/tangweijqxx/p/10649468.html