XGBoost全名叫（eXtreme Gradient Boosting）極端梯度提升，或者叫極值梯度提升演算法，經常被用在一些比賽中，其效果顯著，它是大規模并行boosted tree的工具，它是目前最快最好的開源boosted tree工具包，XGBoost 所應用的演算法就是 GBDT（gradient boosting decision tree）的改進，既可以用于分類也可以用于回歸問題中，GBDT和xgboost在競賽和工業界使用都非常頻繁，GBDT是以決策樹（CART）為基學習器的GB演算法，xgboost擴展和改進了GDBT，xgboost演算法更快，準確率也相對高一些，現在Kaggle 大賽的情況基本是這樣的，凡是非結構化資料相關，比如語音、影像，基本都是深度學習獲勝，凡是結構化資料上的競賽，基本都是 XGBoost 獲勝，Xgboost可以說集成思想達到頂峰的一個模型，至少目前是這樣，所以學習機器學習演算法，掌握這個是很有必要的，
學習Xgboost之前，需要了解決策樹，集成學習，GBDT等演算法的概念，會幫助更好的去理解Xgboost，
Gradient boosting回顧
機器學習中學習演算法的目標是為了優化或者說最小化loss Function， Gradient boosting的思想是迭代生多個（M個）弱的模型，然后將每個弱模型的預測結果相加，后面的模型$F_{m+1}(x)$基于前面學習模型F_{m}(x)的的效果生成的，關系如下：$$F_{m+1}(x) = F_{m}(x)+ h(x) , 1 < m < M$$
GB演算法的思想很簡單，關鍵是怎么生成$h(x)$，如果目標函式是回歸問題的均方誤差，很容易想到最理想的$h(x)$應該是能夠完全擬合$y - F_{m}(x)$，這就是常說基于殘差的學習，殘差學習在回歸問題中可以很好的使用，但是為了一般性（分類，排序問題），實際中往往是基于loss Function 在函式空間的的負梯度學習，對于回歸問題殘差和負梯度也是相同的，因此基于Loss Function函式空間的負梯度的學習也稱為“偽殘差”，
回顧GBDT的回歸演算法迭代的流程：
輸入是訓練集樣本：$T=\{(x_,y_1),(x_2,y_2), ...,(x_m,y_m)\}$， 最大迭代次數$T$, 損失函式$L$，
輸出是強學習器：$f(x)$是一顆回歸樹，
1) 初始化弱學習器（估計使損失函式極小化的常數值，它是只有一個根節點的樹，一般平方損失函式為節點的均值，而絕對損失函式為節點樣本的中位數）：$$f_0(x) = \underset{c}{arg\; min}\sum\limits_{i=1}^{m}L(y_i, c)$$
2) 對迭代輪數t=1,2,...,T有（即生成的弱學習器個數）：
(2.1)對樣本i=1,2，...,m，計算負梯度（損失函式的負梯度在當前模型的值將它作為殘差的估計，對于平方損失函式為，它就是通常所說的殘差；而對于一般損失函式，它就是殘差的近似值（偽殘差））：$$r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)}$$
(2.2)利用$(x_i,r_{ti})\;\; (i=1,2,..m)$，即$\{(x_1,r_{t1}), ...,(x_i,r_{ti})\}$，擬合一顆CART回歸樹,得到第t顆回歸樹，其對應的葉子節點區域為$R_{tj},j =1,2,...,J$，其中J為回歸樹t的葉子節點的個數，
(2.3)對葉子區域j =1,2,..J,計算最佳擬合值：$$c_{tj} = \underset{c}{arg\; min}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c)$$
(2.4)更新強學習器：$$f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj}) $$
3) 得到最終的回歸樹，即強學習器f(x)的運算式：$$f(x) = f_T(x) =f_0(x) + \sum\limits_{t=1}^{T}\sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})$$
從上面可以看出，對于GBDT的第t顆決策樹，先是得到負梯度(2.1)，或者是泰勒展開式的一階導數；然后是第一個優化求解(2.2)，即基于殘差擬合一顆CART回歸樹，得到J個葉子節點區域；再然后是第二個優化求解(2.3)，在第一個優化求解的結果上，對每個節點區域再做一次線性搜索，得到每個葉子節點區域的最優取值；最終得到當前輪的強學習器(2.4)，
從上面可以看出，我們要求解這個問題，需要求解當前決策樹最優的所有J個葉子節點區域和每個葉子節點區域的最優解$c_{tj}$，GBDT采樣的方法是分兩步走，先求出最優的所有J個葉子節點區域，再求出每個葉子節點區域的最優解，
對于XGBoost，它期望把第(2.2)步擬合一個回歸樹（弱分類器）和第(2.3)步計算最佳擬合值合并在一起做，即一次求解出決策樹最優的所有J個葉子節點區域和每個葉子節點區域的最優解$c_{tj}$，下文會具體介紹，
從GBDT到XGBoost
XGBoost作為GBDT的高效實作，XGBoost是一個上限特別高的演算法，因此在演算法競賽中比較受歡迎，簡單來說，對比原演算法GBDT，XGBoost主要從下面三個方面做了優化：
(1). 演算法本身的優化：在演算法的弱學習器模型選擇上，對比GBDT只支持決策樹，XGBoost還可以支持很多其他的弱學習器，在演算法的損失函式上，除了本身的損失，還加上了正則化部分，在演算法的優化方式上，GBDT的損失函式只對誤差部分做負梯度（一階泰勒）展開，而XGBoost損失函式對誤差部分做二階泰勒展開，更加準確，演算法本身的優化是我們后面討論的重點，
(2). 演算法運行效率的優化：對每個弱學習器，比如決策樹建立的程序做并行選擇，找到合適的子樹分裂特征和特征值，在并行選擇之前，先對所有的特征的值進行排序分組，方便前面說的并行選擇，對分組的特征，選擇合適的分組大小，使用CPU快取進行讀取加速，將各個分組保存到多個硬碟以提高IO速度，
(3). 演算法健壯性的優化：對于缺失值的特征，通過列舉所有缺失值在當前節點是進入左子樹還是右子樹來決定缺失值的處理方式，演算法本身加入了L1和L2正則化項，可以防止過擬合，泛化能力更強，
Xgboost必備概念梳理（知識點）
1. 回顧Boosting集成學習的模型預測函式和損失函式：
預測模型為：
$$\hat{y}_{i} = \sum_{k=1}^{K}f_{k}(x_{i})$$
其中$K$為樹的總個數，$f_{k}$表示第$k$顆樹，$\hat{y}_{i}$表示樣本$x_{i}$的預測結果，
損失函式為：
$$Obj(\theta) = \sum_{i=1}^{n}l(y_{i},\hat{y_{i}}) + \sum_{k=1}^{K}\Omega(f_{k})$$
其中$l(y_{i},\hat{y_{i}}$為樣本$x_{i}$的訓練誤差，$\Omega(f_{k})$表示第$k$棵樹的正則項，
【補充】一般的目標函式都包含下面兩項：$$Obj(\Theta) = L(\Theta) + \Omega(\Theta )$$
誤差/損失函式$ L(\Theta)$：指模型擬合資料的程度；
正則化項$\Omega(\Theta )$：指懲罰復雜模型，
其中，誤差/損失函式鼓勵我們的模型盡量去擬合訓練資料，使得最后的模型會有比較少的 bias，而正則化項則鼓勵更加簡單的模型，因為當模型簡單之后，有限資料擬合出來結果的隨機性比較小，不容易過擬合，使得最后模型的預測更加穩定，
2. 回顧加法模型：
其中對于預測模型采用加法策略可以表示如下：
初始化(模型中沒有樹時，其預測結果為0)：$\hat{y}_{i}^{(0)} = 0$
往模型中加入第一棵樹：$\hat{y}_{i}^{(1)} = f_{1}(x_{i}) = \hat{y}_{i}^{(0)} + f_{1}(x_{i})$
往模型中加入第二棵樹：$\hat{y}_{i}^{(2)} = f_{1}(x_{i}) + f_{2}(x_{i}) = \hat{y}_{i}^{(1)} + f_{2}(x_{i})$
…
往模型中加入第t棵樹：$\hat{y}_{i}^{(t)} = \sum_{k=1}^{t}f_{k}(x_{i}) = \hat{y}_{i}^{(t-1)} + f_{t}(x_{i})$
其中$f_{k}$表示第$k$棵樹，$\hat{y}_{i}^{(t)}$表示組合$t$棵樹模型對樣本$x_{i}$的預測結果，
3. 樹的結構與復雜度：
從單一的樹來考慮，對于其中每一棵回歸樹，其模型可以寫成：$$f_{t}(x) = w_{q(x)},w \in R^T, q : R ^ d —> \{1,2,...,T \}$$
樹拆分成結構部分$q$和葉子權重部分$w$，其中$w$為葉子節點的得分值，$q(x)$表示樣本$x$對應的葉子節點，$T$為該樹的葉子節點個數，
Xgboost對樹的復雜度包含了兩個部分：（1）一個是樹里面葉子節點的個數$T$；（2）一個是樹上葉子節點的得分$w$的$L2$模平方（對$w$進行$L2$正則化，相當于針對每個葉結點的得分增加$L2$平滑，目的是為了避免過擬合），
因此可以將該樹的復雜度寫成：$$\Omega(h_t) = \gamma T + \frac{1}{2}\lambda\sum\limits_{j=1}^{T}w_{j}^2$$
其中，$γ$為$L1$正則的懲罰項，$λ$為$L2$正則的懲罰項，
樹的復雜度函式和樣例：
定義樹的結構和復雜度的原因很簡單，這樣就可以衡量模型的復雜度了啊，從而可以有效控制過擬合，
4. Xgboost中的boosting tree模型：
例如要預測一家人對電子游戲的喜好程度，考慮到年輕和年老相比，年輕更可能喜歡電子游戲，以及男性和女性相比，男性更喜歡電子游戲，故先根據年齡大小區分小孩和大人，然后再通過性別區分開是男是女，逐一給各人在電子游戲喜好程度上打分，如下圖所示：
看上圖訓練出2棵樹tree1和tree2，類似之前GBDT的原理（Xgboost與GBDT比較大的不同就是目標函式的定義，下文會具體介紹），兩棵樹的結論累加起來便是最終的結論，所以小孩的預測分數就是兩棵樹中小孩所落到的結點的分數相加：2 + 0.9 = 2.9，爺爺的預測分數同理：-1 + （-0.9）= -1.9，
和傳統的boosting tree模型一樣，Xgboost的提升模型也是采用的殘差（或梯度負方向），不同的是分裂結點選取的時候不一定是最小平方損失，
5. Xgboost目標/損失函式：
因為XGBoost也是集成學習方法的一種，所以預測模型和損失函式都可用上式表示，
XGBoost預測模型：
$$\hat{y}_{i} = \phi(x_{i}) = \sum_{k=1}^{K}f_{k}(x_{i}) $$
$$where \ F = \{f_{t}(x) = w_{q(x)}\},(w \in R^T, q : R ^ d —> \{1,2,...,T \})$$
$w_q(x)$為葉子節點$q$的分數，$F$對應了所有$K$棵回歸樹（regression tree）的集合，而$f(x)$為其中一棵回歸樹，XGBoost演算法的核心就是不斷地添加樹，不斷地進行特征分裂來生長一棵樹，每次添加一個樹，其實是學習一個新函式，去擬合上次預測的殘差，當我們訓練完成得到k棵樹，我們要預測一個樣本的分數，其實就是根據這個樣本的特征，在每棵樹中會落到對應的一個葉子節點，每個葉子節點就對應一個分數，最后只需要將每棵樹對應的分數加起來就是該樣本的預測值，顯然，我們的目標是要使得樹群的預測值盡量接近真實值，而且有盡量大的泛化能力，所以，從數學角度看這是一個泛函最優化問題，故把目標函式簡化如下，
XGBoost損失函式：
$$L(\phi) = \sum_{i}l(\hat{y}_{i},y_{i}) + \sum_{k}\Omega (f_{k})$$
$$where \ \Omega(f) = \gamma T + \frac{1}{2}\lambda \left \| w \right \|^2$$
從上式可以看出，這個目標函式分為兩部分：損失函式和正則化項，且損失函式揭示訓練誤差（即預測分數和真實分數的差距），正則化定義復雜度，對于上式而言，是整個累加模型的輸出，正則化項是則表示樹的復雜度的函式，值越小復雜度越低，泛化能力越強，其中T表示葉子節點的個數，w表示葉子節點的分數，直觀上看，目標要求預測誤差盡量小，且葉子節點T盡量少（γ控制葉子結點的個數），節點數值w盡量不極端（λ控制葉子節點的分數不會過大），防止過擬合，
6. Xgboost目標函式的改寫：
我們知道，每次往模型中加入一棵樹，其損失函式便會發生變化，另外在加入第$t$棵樹時，則前面第$t-1$棵樹已經訓練完成，此時前面$t-1$棵樹的正則項和訓練誤差都成已知常數項，再強調一下，考慮到第$t$輪的模型預測值$\hat{y_{i}}^{(t)}$ = 前$t-1$輪的模型預測$\hat{y_{i}}^{(t-1)}$ + $f_{t}(x_{i})$，因此誤差函式記為：$ l \left (y_{i},\hat{y_{i}}^{(t-1)} + f_{t}(x_{i}) \right )$，后面一項為正則化項，
所以目標函式可以寫成：
$$\begin{align} Obj^{(t)} & = \sum_{i=1}^{n}l(y_{i},\hat{y_{i}}^{(t)}) + \sum_{i=1}^{t}\Omega(f_{i}) \\ & = \sum_{i=1}^{n}l \left (y_{i},\hat{y_{i}}^{(t-1)} + f_{t}(x_{i}) \right ) + \Omega(f_{t}) + constant \end{align}$$
注意對于上面這個誤差函式的式子而言，在第$t$步，$y_{i}$是真實值，即已知，$\hat{y_{i}}^{(t-1)}$可由上一步第$t-1$步中的$\hat{y_{i}}^{(t-2)}$加上$f_{t-1}(x_{i})$計算所得，某種意義上也算已知值，故模型學習的是$f$，
上面那個Obj的公式表達的這樣看有些過于抽象，看不出二次函式的概念，此時來看一個特例，當$l$采用平方誤差的情況（相當于$ l(y_{i},\hat{y_{i}}) = (y_{i} - \hat{y_{i}})^2$），這個時候目標可以被寫成下面這樣的二次函式（下式中$2( \hat{y_{i}}^{(t-1)} - y_{i})f_{t}(x_{i})$部分表示的就是預測值和真實值之間的殘差）：
$$\begin{align} Obj^{(t)} & = \sum_{i=1}^{n}l \left (y_{i},\hat{y_{i}}^{(t-1)} + f_{t}(x_{i}) \right ) + \Omega(f_{t}) + constant \\ & = \sum_{i=1}^{n} \left [ 2( \hat{y_{i}}^{(t-1)} - y_{i})f_{t}(x_{i}) + f_{t}(x_{i})^2 \right ] + \Omega(f_{t}) + constant \end{align}$$
如果不是特例，而是普通的損失函式，如果找到通用的方法，即考慮到損失函式不是二次函式該怎么辦？此時需要利用泰勒展開，不是二次的想辦法近似為二次（看下面Xgboost論文里的解釋，定義了一階導和二階導
）：
從而保留二次項，最終的目標函式只依賴于每個資料點的在誤差函式上的一階導數和二階導數，這么寫的原因很明顯，由于之前的目標函式求最優解的程序中只對平方損失函式時候方便求，對于其他的損失函式變得很復雜，通過二階泰勒展開式的變換，這樣求解其他損失函式變得可行了，
7. 泰勒公式
在數學中，泰勒公式（英語：Taylor's Formula）是一個用函式在某點的資訊描述其附近取值的公式，這個公式來自于微積分的泰勒定理（Taylor's theorem），泰勒定理描述了一個可微函式，如果函式足夠光滑的話，在已知函式在某一點的各階導數值的情況之下，泰勒公式可以用這些導數值做系數構建一個多項式來近似函式在這一點的鄰域中的值，這個多項式稱為泰勒多項式（Taylor polynomial），
相當于告訴我們可由利用泰勒多項式的某些次項做原函式的近似，
泰勒定理：
設 $n $是一個正整數，如果定義在一個包含$ a$ 的區間上的函式$ f$ 在 $a $點處 $n+1$ 次可導，那么對于這個區間上的任意 $x$，都有：
$$f(x) = f(a) + \frac{f{}'(a)}{1!}(x-a) + \frac{f^{(2)}(a)}{2!}(x-a)^2 + ... + \frac{f^{(n)}(a)}{n!}(x-a)^n + R_{n}(x)$$
其中的多項式稱為函式在$a$ 處的泰勒展開式，剩余的$R_{n}(x)$是泰勒公式的余項，是$(x-a)^n$的高階無窮小，
泰勒二階展開：$$f(x + \Delta x) \simeq f(x) + f{}'(x)\Delta x + \frac{1}{2}f{}''(x)\Delta x^2$$
8. Xgboost的泰勒展開推導程序
對應到Xgboost的目標函式里頭：$$Obj^{(t)} = \sum_{i=1}^{n}l \left (y_{i},\hat{y_{i}}^{(t-1)} + f_{t}(x_{i}) \right ) + \Omega(f_{t}) + constant$$
忽略損失函式$l$中的$y_{i}$（因為上面說的“ 在第$t$步，$y_{i}$是真實值，即已知 ”，所以不影響后續目標函式對$\hat{y_{i}}^{(t-1)}$的偏導計算），做下一一對應：
泰勒二階展開$f$ 里的$x$對應目標函式里的$\hat{y_{i}}^{(t-1)}$；
$f$ 里的$\Delta x$對應目標函式的$f_{t}(x_{i})$；
從而$f $對$x$求導數時，對應為目標函式對$\hat{y_{i}}^{(t-1)}$求偏導，
則原目標函式可以寫成(泰勒展開具體推導步驟)：
$$\begin{align} Obj^{(t)} & = \sum_{i=1}^{n}l(y_{i},\hat{y_{i}}^{(t)}) + \sum_{i=1}^{t}\Omega(f_{i}) \\ & = \sum_{i=1}^{n}l \left (y_{i},\hat{y_{i}}^{(t-1)} + f_{t}(x_{i}) \right ) + \Omega(f_{t}) + constant \\ & \approx \sum_{i=1}^{n} \left [ l(y_{i},\hat{y_{i}}^{(t-1)}) + \partial _{\hat{y}_{i}^{(t-1)}} \ \ l(y_{i},\hat{y}_{i}^{(t-1)})f_{t}(x_{i}) + \frac{1}{2}\partial^2 _{\hat{y_{i}}^{(t-1)}} \ \ l(y_{i},\hat{y_{i}}^{(t-1)})f_{t}(x_{i})^2 \right ] + \Omega(f_{t}) + constant \end{align}$$
其中，$g_{i} = \partial _{\hat{y}_{i} \ ^{(t-1)}} \ \ l(y_{i},\hat{y_{i}} \ ^{(t-1)}) $，$\partial^2 _{\hat{y}_{i} \ ^{(t-1)}} \ \ l(y_{i},\hat{y_{i}} \ ^{(t-1)})$，
則目標損失函式可以寫成：$$Obj^{(t)} \simeq \sum_{i=1}^{n} \left [ l(y_{i},\hat{y_{i}}^{(t-1)}) + g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f^2_{t}(x_{i}) \right ] + \Omega(f_{t}) + constant $$
還需要注意這里的第$t $顆回歸樹是根據前面的$t-1$顆回歸樹的殘差得來的，相當于$t-1$顆樹的值$\hat{y_{i}}^{(t-1)}$是已知的，換句話說，損失函式里面$l(y_{i},\hat{y_{i}}^{(t)})$是常數，對目標函式的優化不影響（最小化），可以直接去掉，且常數項constant也可以移除，從而得到如下一個比較統一的目標函式：
$$Obj^{(t)} \simeq \sum_{i=1}^{n} \left [ + g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f^2_{t}(x_{i}) \right ] + \Omega(f_{t})$$
這時，目標函式只依賴于每個資料點在誤差函式上的一階導數和二階導數
（這里體現xgboost和gbdt的不同了，目標函式保留了泰勒展開的二次項），
回歸前面樹的復雜度介紹，我們知道：$f_{t}(x) = w_{q(x)},w \in R^T, q : R ^ d —> \{1,2,...,T \}$，同時將目標函式全部轉換成在第$t$棵樹葉子節點的形式，對這里的$f_{t}(x_{i})$的理解：當一個樣本進來的時候，不管是回歸問題還是分類問題，最終都會掉到葉子結點上，而每顆樹的每個葉子節點都會對應有一個得分（想象一下回歸問題，每個葉子節點對應的是落入該葉子結點的所有訓練樣本的均值），所以$f_{t}(x_{i})$可以理解為一個樣本在$t$輪最終的得分函式，
即每個決策樹的第$j$個葉子節點的取值最侄訓是同一個值$w_{j}$，另外代入正則項，
損失函式可以繼續化簡：
$$ \begin{align} Obj^{(t)} & \simeq \sum_{i=1}^{n} \left [ g_{i}f_{t}(x_{i}) + \frac{1}{2}h_{i}f^2_{t}(x_{i}) \right ] + \Omega(f_{t}) \\ & = \sum_{i=1}^{n} \left [ g_{i}w_{q(x_{i})} + \frac{1}{2}h_{i}w^2_{q(x_{i}} \right ] + \gamma T + \frac{1}{2}\lambda\sum\limits_{j=1}^{T}w_{j}^2 \\ & = \sum_{j=1}^{T} \left [ (\sum_{i\epsilon I_{j}}g_{i})w_{j} + \frac{1}{2}(\sum_{i\epsilon I_{j}}h_{i})w^2_{j} \right ] + \gamma T + \frac{1}{2}\lambda\sum\limits_{j=1}^{T}w_{j}^2 \\ & = \sum_{j=1}^{T} \left [ (\sum_{i\epsilon I_{j}}g_{i})w_{j} + \frac{1}{2}(\sum_{i\epsilon I_{j}}h_{i} + \lambda )w^2_{j} \right ] + \gamma T \end{align}$$
這里的$w_{q(x}$描述了一整顆樹的模型，因此能分解成每個葉子結點的集合，而$w_{j}$剛好是每個葉子節點的得分函式，即$w_{j}$為第$j$個葉子節點的得分值，這兩個可以相互轉化，其中$T$為第t棵樹中總葉子節點的個數，$I_{j}$被定義為每個葉節點 $j$上面樣本下標的集合 $I_{j} = i | q(x_{i} = j)$，即表示$i$樣本落在第$j$個葉子節點上，這個定義里的$q(x_{i})$要表達的是：每個樣本值$x_{i}$ 都能通過函式$q(x_{i})$映射到樹上的某個葉子節點，從而通過這個定義把兩種累加統一到了一起，g是一階導數，h是二階導數，這一步是由于xgboost目標函式第二部分加了兩個正則項，一個是葉子節點個數(T),一個是葉子節點的分數(w)，
繼續把每個葉子節點區域樣本的一階和二階導數的和單獨表示如下：$G_{j} = \sum_{i\epsilon I_{j}}g_{i}$，$H_{j} = \sum_{i\epsilon I_{j}}h_{i}$
最終損失函式的形式可以表示為：
$$ Obj^{(t)} = \sum_{j=1}^{T} \left [ G_{i}w_{j} + \frac{1}{2}(H_{i} + \lambda )w^2_{j} \right ] + \gamma T$$
現在我們得到了最終的損失函式，那么回到前面講到的問題，如何一次求解出決策樹最優的所有$J$個葉子節點區域和每個葉子節點區域的最優解$w_{j}$呢？
9. XGBoost損失函式的優化求解
關于如何一次求解出決策樹最優的所有$J$個葉子節點區域和每個葉子節點區域的最優解$w_{j}$，可以把它拆分成2個問題：
1) 如果我們已經求出了第$t$個決策樹的$J$個最優的葉子節點區域，如何求出每個葉子節點區域的最優解$w_{j}$？
2) 對當前決策樹做子樹分裂決策時，應該如何選擇哪個特征和特征值進行分裂，使最終我們的損失函式$L$最小？
對于第一個問題，其實是比較簡單的，直接基于損失函式對$w_{j}$求導并令導數為0得到：$G_{i} + (H_{i} + \lambda )w_{j} = 0$
從而可得到葉子節點區域的最優解$w_{j}$運算式：$$w^*_{j} = - \frac{G_{j}}{H_{j} + \lambda }$$
【補充】這個葉子節點的運算式不是XGBoost首創，實際上在GBDT的分類演算法里，已經在使用了，大家在GBDT演算法介紹中葉子節點區域值的近似解(2.3)步計算最佳擬合值$c_{ti}$：
$$c_{tj} = \sum\limits_{x_i \in R_{tj}}r_{ti}\bigg / \sum\limits_{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|)$$
它其實就是使用了上式來計算最終的$c_{tj}$，例如回顧二元分類的損失函式是：$L(y, f(x)) = log(1+ exp(-yf(x)))$
其每個樣本的一階導數為：$g_i=-r_i= -y_i/(1+exp(y_if(x_i)))$
其每個樣本的二階導數為：$h_i =\frac{exp(y_if(x_i)}{(1+exp(y_if(x_i))^2} = |g_i|(1-|g_i|) $
由于沒有正則化項，則$c_{tj} = -\frac{g_i}{h_i} $，即可得到GBDT二分類葉子節點區域的近似值，
現在我們回到XGBoost，我們已經解決了第一個問題，現在來看XGBoost優化拆分出的第二個問題：如何選擇哪個特征和特征值進行分裂，使最終我們的損失函式$L$最小？在GBDT里面，我們是直接擬合的CART回歸樹，所以樹節點分裂使用的是均方誤差，XGBoost這里不使用均方誤差，而是使用貪心法，即每次分裂都期望最小化我們的損失函式的誤差，
注意到在$w_{j}$取最優解的時候，原損失函式對應的運算式為：$$Obj = -\frac{1}{2}\sum\limits_{j=1}^J\frac{G_{j}^2}{H_{j} + \lambda} +\gamma T$$
Obj代表了當指定一個樹的結構的時候，在目標上面最多減少多少，結構分數(structure score)，這里結構分數越小代表這顆樹的結構越好，
1) 樹結構的打分函式
這里的結構分數(structure score)可以理解為類似于Gain系數一樣更加一般的對于樹打分的函式，
具體打分函式例子：
Xgboost演算法的步驟和GB基本相同，都是首先初始化為一個常數，gb是根據一階導數$r_{i}$，Xgboost是根據一階導數$g_{i}$和二階導數$h_{i}$，迭代生成基學習器，相加更新學習器，對于每一次嘗試去對已有的葉子加入一個分割，每次做左右子樹分裂時，目標是最大程度的減少損失函式的損失，也就是說，假設當前節點左右子樹的一階二階導數和為$GL$,$HL$,$GR$,$HR$則我們期望最大化下式：
$$Gain = \frac{1}{2}\left [ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+ \lambda} \right ] - \gamma$$
其中$\frac{G_{L}^2}{H_{L} + \lambda}$表示左子樹分數，$\frac{G_{R}^2}{H_{R}+\lambda}$表示右子樹分數，$\frac{(G_{L}+G_{R})^2}{H_{L}+H_{R}+ \lambda}$表示不可分割我們可以拿到的分數，$\gamma$表示加入新葉子節點引入的復雜度代價，
也就是說，Xgboost里的決策樹分裂標準不再使用CART回歸樹的均方誤差，而是上式了，這樣就可以在建樹的程序中動態的選擇是否要添加一個結點， 聯想決策樹中資訊增益，這里的原理類似，這一步實質上是為了尋找分裂結點的候選集，每次做左右子樹分裂時，可以最大程度的減少損失函式的損失就最好了，
2) 尋找分裂結點標準
對于每次擴展，我們要列舉所有的分割方案，如何高效地列舉所有的分割呢？比如設定一個值a，然后列舉所有x < a，a < x這樣的條件，對于某個特定的分割a我們要計算a左邊和右邊的導數和，
具體如何分裂呢？舉個簡單的年齡特征的例子，假設我們選擇年齡這個特征的值a作為決策樹的分裂標準，x代表某個特征比如年齡age，把age從小到大排序：假定從左至右依次增大，則比a小的放在左邊，比a大的放在右邊，計算a左邊和右邊的導數和，
比如總共五個人，按年齡排好序后，一開始我們總共有如下4種劃分方法：
- 把第一個人和后面四個人劃分開
- 把前兩個人和后面三個人劃分開
- 把前三個人和后面兩個人劃分開
- 把前面四個人和后面一個人劃分開
接下來，把上面4種劃分方法全都各自計算一下Gain，看哪種劃分方法得到的Gain值最大則選取哪種劃分方法，經過計算，發現把第2種劃分方法“前面兩個人和后面三個人劃分開”得到的Gain值最大，這樣可以分別計算出左右子樹的一階和二階導數和，進而求出最終的上式的值，
然后我們使用其他的不是值a的劃分標準，可以得到其他組合的一階和二階導數和，進而求出上式的值，最終我們找出可以使上式最大的組合，以它對應的特征值來分裂子樹，
可以發現對于所有的a，我們只要做一遍從左到右的掃描就可以列舉出所有分割的梯度和$G_{L}$和 $G_{R}$，然后用上面的公式計算每個分割方案的分數就可以了，
至此，我們解決了XGBoost的2個優化子問題的求解方法，
10. 尋找分裂結點
確定好損失函式以及最優解之后，接下來需要確定樹的結構，即如何選出最優分裂節點，可以參考決策樹演算法：ID3選擇資訊增益為切分準則，C4.5選擇資訊增益率為切分準則，Xgboost基本思想和決策樹一致，貪心法列舉所有節點，計算各個節點分裂前后的資訊增益，選出資訊增益最大的，
很顯然，一棵樹的生成是由一個節點一分為二，然后不斷分裂最終形成為整棵樹，那么樹怎么分裂的就成為了接下來我們要探討的關鍵，對于一個葉子節點如何進行分裂，根據Xgboost的Gain公式，Xgboost作者在其原始論文中給出了兩種分裂節點的方法（切分演算法），
1) 列舉所有不同樹結構的貪心法（精確貪心演算法）：
在所有特征上暴力列舉所有可能的切分點，
貪心法，從樹深度0開始，每一節點都遍歷所有的特征，比如年齡、性別等等，然后對于某個特征，先按照該特征里的值進行排序，然后線性掃描該特征進而確定最好的分割點，最后對所有特征進行分割后，我們選擇所謂的增益Gain最高的那個特征，
2) 近似演算法：
主要針對資料太大，不能直接進行計算，基本思想是通過特征的統計分布（分位數），按照百分比確定一組候選分裂點，（對于連續屬性特征，根據候選切分點進行離散化）然后通過遍歷所有的候選分裂點來找到最佳分裂點，近似演算法有兩種版本：global variant和local variant，global variant在樹初始化時就確定了候選切分點；local variant是在每次節點分裂后重新選出候選點，
兩種策略：全域策略和區域策略，在全域策略中，對每一個特征確定一個全域的候選分裂點集合，就不再改變；而在區域策略中，每一次分裂 都要重選一次分裂點，前者需要較大的分裂集合，后者可以小一點，對比補充候選集策略與分裂點數目對模型的影響， 全域策略需要更細的分裂點才能和區域策略差不多，
XGBoosting演算法流程總結
這里總結下XGBoost的演算法主流程，基于決策樹弱分類器，不涉及運行效率的優化和健壯性優化的內容，
輸入是訓練集樣本$I=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$， 最大迭代次數$T$, 損失函式$L$， 正則化系數$\lambda,\gamma$；
輸出是強學習器：$f(x)$，
對迭代輪數$t=1,2,...,T$有：
1) 計算第$i$個樣本$(i-1,2,..,m)$在當前輪損失函式$L$基于$f_{t-1}(x_i)$的一階導數$g_{ti}$，二階導數$h_{ti}$,計算所有樣本的一階導數和$G_t = \sum\limits_{i=1}^mg_{ti}$,二階導數和$H_t = \sum\limits_{i=1}^mh_{ti}$
2) 基于當前節點嘗試分裂決策樹，默認分數score=0，G和H為當前需要分裂的節點的一階二階導數之和，
對特征序號 k=1,2...K:
a) $G_L=0, H_L=0$
b) 將樣本按特征k從小到大排列，依次取出第i個樣本，依次計算當前樣本放入左子樹后，左右子樹一階和二階導數和：$$G_L = G_L+ g_{ti}, G_R=G-G_L$$$$H_L = H_L+ h_{ti}, H_R=H-H_L$$
c) 嘗試更新最大的分數：$$score = max(score, \frac{1}{2}\frac{G_L^2}{H_L + \lambda} + \frac{1}{2}\frac{G_R^2}{H_R+\lambda} - \frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+ \lambda} -\gamma )$$
3) 基于最大score對應的劃分特征和特征值分裂子樹，
4) 如果最大score為0，則當前決策樹建立完畢，計算所有葉子區域的$w_{tj}$, 得到弱學習器$h_t(x)$，更新強學習器$f_t(x)$,進入下一輪弱學習器迭代.如果最大score不是0，則轉到第2)步繼續嘗試分裂決策樹，
XGBoost演算法運行效率的優化
Boosting演算法的弱學習器是沒法并行迭代的，但是單個弱學習器里面最耗時的是決策樹的分裂程序，XGBoost針對這個分裂做了比較大的并行優化，對于不同的特征的特征劃分點，XGBoost分別在不同的執行緒中并行選擇分裂的最大增益，
同時，對訓練的每個特征排序并且以塊的的結構存盤在記憶體中，方便后面迭代重復使用，減少計算量，計算量的減少參見上面演算法流程總結，首先默認所有的樣本都在右子樹，然后從小到大迭代，依次放入左子樹，并尋找最優的分裂點，這樣做可以減少很多不必要的比較，
具體的程序如下圖所示：
此外，通過設定合理的分塊的大小，充分利用了CPU快取進行讀取加速（cache-aware access），使得資料讀取的速度更快，另外，通過將分塊進行壓縮（block compressoin）并存盤到硬碟上，并且通過將分塊磁區到多個硬碟上實作了更大的IO，
XGBoosting涉及的演算法工程優化策略：
1. 對記憶體的優化（列分塊）；
2. 對CPU Cache的優化：a) 提前取數(Prefetching)，b) 合理設定分塊大小；
3. 對IO的優化：a) Block壓縮優化，b) Block 分片優化，
XGBoost演算法健壯性的優化
XGBoost在演算法健壯性的優化方面，除了上面講到的正則化項提高演算法的泛化能力外，XGBoost還對特征的缺失值做了處理，XGBoost沒有假設缺失值一定進入左子樹還是右子樹，則是嘗試通過列舉所有缺失值在當前節點是進入左子樹，還是進入右子樹更優來決定一個處理缺失值默認的方向，這樣處理起來更加的靈活和合理，
也就是說，上面Xgboost演算法流程總結的步驟a),b)和c)會執行2次，第一次假設特征k所有有缺失值的樣本都走左子樹，第二次假設特征k所有缺失值的樣本都走右子樹，然后每次都是針對沒有缺失值的特征k的樣本走上述流程，而不是所有的的樣本，
如果是所有的缺失值走右子樹，使用上面a),b)和c)即可，如果是所有的樣本走左子樹，則上面
a)步要變成：
$G_R=0, H_R=0$
b)步要更新為：
$G_R = G_R+g_{ti}, G_L=G-G_R$
$H_R = H_R+h_{ti}, H_L=H-H_R$
XGBoosting的優缺點總結
在分析XGBooting優缺點的時候，通過比較該演算法與GBDT的差異，即可有較清楚的描述，具體表現在如下方面，
1）基分類器的差異
- GBDT演算法只能利用CART樹作為基學習器，滿足分類應用；
- XGBoost演算法除了以CART樹中的回歸樹作為基分類器之外還支持線性的基學習器，因此其一方面可以解決帶L1與L2正則化項的邏輯回歸分類問題，也可以解決線性回問題，
2）節點分類方法的差異
- GBDT演算法主要是利用Gini impurity針對特征進行節點劃分；
- XGBoost經過公式推導，提出的weighted quantile sketch劃分方法，依據影響Loss的程度來確定連續特征的切分值，
3）模型損失函式的差異
- 傳統GBDT在優化時只用到一階導數資訊；
- xgboost則對代價函式進行了二階泰勒展開，二階導數有利于梯度下降的更快更準，
4）模型防止過擬合的差異
- GBDT演算法無正則項，可能出現過擬合；
- Xgboost在代價函式里加入了正則項，用于控制模型的復雜度，降低了過擬合的可能性，
5）模型實作上的差異
決策樹的學習最耗時的一個步驟就是對特征的值進行排序（因為要確定最佳分割點），xgboost在訓練之前，預先對資料進行了排序，然后保存為block結構，后面的迭代中重復地使用這個結構，大大減小計算量，其能夠實作在特征粒度的并行，
參考文章：
https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
https://arxiv.org/pdf/1603.02754.pdf
https://zhuanlan.zhihu.com/p/90520307
https://www.cnblogs.com/pinard/p/10979808.html
https://blog.csdn.net/v_JULY_v/article/details/81410574
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/154306.html
標籤：Python