XGBoost簡介

XGBoost

Extreme Gradient Boosting(XGBoost)是由華盛頓大學（University of Washington）的陳天奇作為 Distributed (Deep) Machine Learning Community (DMLC) 組員所開發(fā)的一個研究項目。在陳天奇與隊友一起贏得了Higgs Machine Learning Challenge后，許多的數(shù)據(jù)科學競賽隊伍使用XGBoost并獲得了冠軍，促進了該工具在數(shù)據(jù)科學應用中的廣泛使用。

目標函數(shù)

在有監(jiān)督學習中，我們的目標函數(shù)可以分解為訓練損失和正則化項：
obj(\theta)=L(\theta)+\Omega(\theta)
如果對每個樣本，訓練損失函數(shù)為l(y,\hat{y})，則L(\theta)=\sum\limits_{i=1}^n l(y_i,\hat{y}_i)
對樹模型而言，\hat{y}=f(x)=w_{q(x)},\ w\in R^T,\ q:\mathbb{R}^d\rightarrow\{1,2,\cdots,T\}，其中w_i是第i個葉子結(jié)點上的socre，每個樣本點x會落在某一個葉子節(jié)點q(x)上，T是葉子數(shù)。在XGBoost中，樹的復雜度描述為：
\Omega(f)=\gamma T+\frac{1}{2}\lambda \sum\limits_{i=1}^Tw_i^2
當然還可以加上其他正則項，如L1正則（對應正則化系數(shù)\alpha）等。

Boosting

Boosting的過程，是擬合一個加性模型。假設我們已經(jīng)訓練了t-1步，對應的模型為\hat{y}^{(t-1)}(x)=\sum\limits_{k=1}^{t-1}f_k(x)
第t步，我們的目標是找到f_t(x)，以最小化目標函數(shù)：
\begin{align} \min\limits_{f_k}\quad &obj^{(t)}=\sum\limits_{i=1}^n l(y_i,\hat{y}_i^{(t)})+\Omega(f_t)\\ where\quad & \hat{y}_i^{(t)} = \sum\limits_{k=1}^{t}f_k(x_i)\\ \end{align}

將樣本損失函數(shù)在y'=\hat{y}^{(t-1)}處做二階泰勒展開,
l(y,y')=l(y,\hat{y}^{(t-1)})+\dfrac{\partial l(y,y')}{\partial y'}\Bigg|_{y'=\hat{y}^{(t-1)}}f_t(x)+\frac{1}{2}\dfrac{\partial^2 l(y,y')}{\partial y'\partial y'}\Bigg|_{y'=\hat{y}^{(t-1)}}f_t^2(x)+O(f_t^2(x))
對應地，將每個樣本代入可得：
obj^{(t)}=\sum\limits_{i=1}^n \left[l(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t)
其中
\begin{align} g_i&=\dfrac{\partial l(y_i,y')}{\partial y'}\Bigg|_{y'=\hat{y}_i^{(t-1)}} \\ h_i&=\dfrac{\partial^2 l(y_i,y')}{\partial y'\partial y'}\Bigg|_{y'=\hat{y}_i^{(t-1)}}\\ \end{align}
而\sum\limits_{i=1}^n l(y_i,\hat{y}_i^{(t-1)})是與f_t(x)無關(guān)的，因此，我們的目標函數(shù)可以簡化為：
obj^{(t)}\approx\sum\limits_{i=1}^n \left[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)\right]+\Omega(f_t)

第t棵樹的目標函數(shù)是理論目標函數(shù)最優(yōu)值與前t-1棵樹預測的目標函數(shù)值的殘差，即以目標函數(shù)的負梯度來作為第t棵樹的學習目標。

樹的分裂準則

我們可以將目標函數(shù)重寫為
\begin{align} obj^{(t)}&\approx \sum\limits_{i=1}^n[ g_i w_{q(x_i)}+ \frac{1}{2}h_i w^2_{q(x_i)}]+\gamma T+ \frac{1}{2}\lambda \sum\limits_{j=1}^Tw_j^2\\ &= \sum\limits_{j=1}^T\left[\left(\sum\limits_{i\in I_j}g_i\right)w_j+ \frac{1}{2}\left(\sum\limits_{i\in I_j}h_i+\lambda\right)w_j^2\right]+\gamma T\\ &\triangleq \sum\limits_{j=1}^T\left[G_jw_j+ \frac{1}{2}\left(H_j+\lambda\right)w_j^2\right]+\gamma T\\ \end{align}
其中I_j=\{i | q(x_i) = j\}。因此，
\begin{align} w_j^*&=-\frac{G_j}{H_j+\lambda}\\ obj^*&=-\frac{1}{2} \sum\limits_{j=1}^T \dfrac{G^2}{H_j+\lambda}+\gamma T\\ \end{align}
因此后者可以用來衡量樹結(jié)構(gòu)的好壞，用來決定樹的分裂。這里我們定義結(jié)點分裂的增益為
\begin{align} 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 \end{align}

特性

  1. 支持線性分類器、DART（Dropouts meet Multiple Additive Regression Trees）以及Tweedie Regression；支持分類、回歸、排序任務；
  2. 二階導信息。傳統(tǒng)GBDT在優(yōu)化時只用到一階導數(shù)信息，xgboost則對代價函數(shù)進行了二階泰勒展開，同時用到了一階和二階導數(shù)。順便提一下，xgboost工具支持自定義代價函數(shù)，只要函數(shù)可一階和二階求導。
  3. 正則化項。xgboost在代價函數(shù)里加入了正則項，用于控制模型的復雜度。正則項里包含了樹的葉子節(jié)點個數(shù)、每個葉子節(jié)點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過擬合，這也是xgboost優(yōu)于傳統(tǒng)GBDT的一個特性。
  4. 縮減（Shrinkage）。相當于學習速率（xgboost中的eta）。xgboost在進行完一次迭代后，會將葉子節(jié)點的權(quán)重乘上該系數(shù)，主要是為了削弱每棵樹的影響，讓后面有更大的學習空間。實際應用中，一般把eta設置得小一點，然后迭代次數(shù)設置得大一點。（補充：傳統(tǒng)GBDT的實現(xiàn)也有學習速率）
  5. 列抽樣（column subsampling）。xgboost借鑒了隨機森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算，這也是xgboost異于傳統(tǒng)gbdt的一個特性。
  6. 對缺失值的處理。xgboost把缺失值當做稀疏矩陣來對待，本身的在節(jié)點分裂時不考慮的缺失值的數(shù)值。缺失值數(shù)據(jù)會被分到左子樹和右子樹分別計算損失，選擇較優(yōu)的那一個。如果訓練中沒有數(shù)據(jù)缺失，預測時出現(xiàn)了數(shù)據(jù)缺失，那么默認被分類到右子樹。
  7. 支持并行。boosting不是一種串行的結(jié)構(gòu)嗎?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能進行下一次迭代的（第t次迭代的代價函數(shù)里包含了前面t-1次迭代的預測值）。xgboost的并行是在特征粒度上的。我們知道，決策樹的學習最耗時的一個步驟就是對特征的值進行排序（因為要確定最佳分割點），xgboost在訓練之前，預先對數(shù)據(jù)進行了排序，然后保存為block結(jié)構(gòu)，后面的迭代中重復地使用這個結(jié)構(gòu)，大大減小計算量。這個block結(jié)構(gòu)也使得并行成為了可能，在進行節(jié)點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那么各個特征的增益計算就可以開多線程進行。
  8. 可并行的近似直方圖算法。樹節(jié)點在進行分裂時，我們需要計算每個特征的每個分割點對應的增益，即用貪心法枚舉所有可能的分割點。當數(shù)據(jù)無法一次載入內(nèi)存或者在分布式情況下，貪心算法效率就會變得很低，所以xgboost還提出了一種可并行的近似直方圖算法，用于高效地生成候選的分割點，大致的思想是根據(jù)百分位法列舉幾個可能成為分割點的候選者，然后從候選者中計算Gain按最大值找出最佳的分割點。
  9. 特征重要性。XGBoost在訓練的過程中給出各個特征的評分，Gain、Cover、Frequency，從而表明每個特征對模型訓練的重要性。

常見問題

  1. XGBoost在什么地方做的剪枝，怎么做的？
    答：XGBoost 先從頂?shù)降捉渲钡阶畲笊疃龋購牡椎巾敺聪驒z查是否有不滿足分裂條件的結(jié)點，進行剪枝。

  2. XGBoost如何分布式？特征分布式和數(shù)據(jù)分布式？ 各有什么存在的問題？
    答：XGBoost在訓練之前，預先對數(shù)據(jù)按列進行排序，然后保存block結(jié)構(gòu)。（1）特征分布式/特征間并行：由于將數(shù)據(jù)按列存儲，可以同時訪問所有列，那么可以對所有屬性同時執(zhí)行split finding算法，從而并行化split finding（切分點尋找）；（2）數(shù)據(jù)分布式/特征內(nèi)并行：可以用多個block(Multiple blocks)分別存儲不同的樣本集，多個block可以并行計算。
    問題：（1）不能從本質(zhì)上減少計算量；（2）通訊代價高。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容