XGBoost
Extreme Gradient Boosting(XGBoost)是由華盛頓大學(xué)（University of Washington）的陳天奇作為 Distributed (Deep) Machine Learning Community (DMLC) 組員所開發(fā)的一個(gè)研究項(xiàng)目。在陳天奇與隊(duì)友一起贏得了Higgs Machine Learning Challenge后谆奥，許多的數(shù)據(jù)科學(xué)競(jìng)賽隊(duì)伍使用XGBoost并獲得了冠軍，促進(jìn)了該工具在數(shù)據(jù)科學(xué)應(yīng)用中的廣泛使用。
目標(biāo)函數(shù)
在有監(jiān)督學(xué)習(xí)中，我們的目標(biāo)函數(shù)可以分解為訓(xùn)練損失和正則化項(xiàng)：
如果對(duì)每個(gè)樣本棕兼，訓(xùn)練損失函數(shù)為违寞，則
對(duì)樹模型而言，锭沟，其中
是第
個(gè)葉子結(jié)點(diǎn)上的socre，每個(gè)樣本點(diǎn)
會(huì)落在某一個(gè)葉子節(jié)點(diǎn)
上识补，
是葉子數(shù)族淮。在XGBoost中，樹的復(fù)雜度描述為：
當(dāng)然還可以加上其他正則項(xiàng)凭涂，如L1正則（對(duì)應(yīng)正則化系數(shù)）等祝辣。
Boosting
Boosting的過程，是擬合一個(gè)加性模型切油。假設(shè)我們已經(jīng)訓(xùn)練了步蝙斜，對(duì)應(yīng)的模型為
第步，我們的目標(biāo)是找到
澎胡，以最小化目標(biāo)函數(shù)：
將樣本損失函數(shù)在處做二階泰勒展開,
對(duì)應(yīng)地孕荠，將每個(gè)樣本代入可得：
其中
而是與
無關(guān)的娩鹉，因此，我們的目標(biāo)函數(shù)可以簡(jiǎn)化為：
第棵樹的目標(biāo)函數(shù)是理論目標(biāo)函數(shù)最優(yōu)值與前
棵樹預(yù)測(cè)的目標(biāo)函數(shù)值的殘差稚伍，即以目標(biāo)函數(shù)的負(fù)梯度來作為第
棵樹的學(xué)習(xí)目標(biāo)弯予。
樹的分裂準(zhǔn)則
我們可以將目標(biāo)函數(shù)重寫為
其中。因此个曙，
因此后者可以用來衡量樹結(jié)構(gòu)的好壞锈嫩，用來決定樹的分裂。這里我們定義結(jié)點(diǎn)分裂的增益為
特性
- 支持線性分類器垦搬、DART（Dropouts meet Multiple Additive Regression Trees）以及Tweedie Regression呼寸；支持分類、回歸猴贰、排序任務(wù)对雪；
- 二階導(dǎo)信息。傳統(tǒng)GBDT在優(yōu)化時(shí)只用到一階導(dǎo)數(shù)信息米绕，xgboost則對(duì)代價(jià)函數(shù)進(jìn)行了二階泰勒展開慌植，同時(shí)用到了一階和二階導(dǎo)數(shù)。順便提一下义郑，xgboost工具支持自定義代價(jià)函數(shù)，只要函數(shù)可一階和二階求導(dǎo)丈钙。
- 正則化項(xiàng)非驮。xgboost在代價(jià)函數(shù)里加入了正則項(xiàng)，用于控制模型的復(fù)雜度雏赦。正則項(xiàng)里包含了樹的葉子節(jié)點(diǎn)個(gè)數(shù)劫笙、每個(gè)葉子節(jié)點(diǎn)上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講星岗，正則項(xiàng)降低了模型的variance填大，使學(xué)習(xí)出來的模型更加簡(jiǎn)單，防止過擬合俏橘，這也是xgboost優(yōu)于傳統(tǒng)GBDT的一個(gè)特性允华。
- 縮減（Shrinkage）。相當(dāng)于學(xué)習(xí)速率（xgboost中的eta）寥掐。xgboost在進(jìn)行完一次迭代后靴寂，會(huì)將葉子節(jié)點(diǎn)的權(quán)重乘上該系數(shù)，主要是為了削弱每棵樹的影響召耘，讓后面有更大的學(xué)習(xí)空間百炬。實(shí)際應(yīng)用中，一般把eta設(shè)置得小一點(diǎn)污它，然后迭代次數(shù)設(shè)置得大一點(diǎn)剖踊。（補(bǔ)充：傳統(tǒng)GBDT的實(shí)現(xiàn)也有學(xué)習(xí)速率）
- 列抽樣（column subsampling）庶弃。xgboost借鑒了隨機(jī)森林的做法，支持列抽樣德澈，不僅能降低過擬合歇攻，還能減少計(jì)算，這也是xgboost異于傳統(tǒng)gbdt的一個(gè)特性圃验。
- 對(duì)缺失值的處理掉伏。xgboost把缺失值當(dāng)做稀疏矩陣來對(duì)待，本身的在節(jié)點(diǎn)分裂時(shí)不考慮的缺失值的數(shù)值澳窑。缺失值數(shù)據(jù)會(huì)被分到左子樹和右子樹分別計(jì)算損失斧散，選擇較優(yōu)的那一個(gè)。如果訓(xùn)練中沒有數(shù)據(jù)缺失摊聋，預(yù)測(cè)時(shí)出現(xiàn)了數(shù)據(jù)缺失鸡捐，那么默認(rèn)被分類到右子樹。
- 支持并行麻裁。boosting不是一種串行的結(jié)構(gòu)嗎?怎么并行的箍镜？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能進(jìn)行下一次迭代的（第t次迭代的代價(jià)函數(shù)里包含了前面t-1次迭代的預(yù)測(cè)值）煎源。xgboost的并行是在特征粒度上的色迂。我們知道，決策樹的學(xué)習(xí)最耗時(shí)的一個(gè)步驟就是對(duì)特征的值進(jìn)行排序（因?yàn)橐_定最佳分割點(diǎn)）手销，xgboost在訓(xùn)練之前歇僧，預(yù)先對(duì)數(shù)據(jù)進(jìn)行了排序，然后保存為block結(jié)構(gòu)锋拖，后面的迭代中重復(fù)地使用這個(gè)結(jié)構(gòu)诈悍，大大減小計(jì)算量。這個(gè)block結(jié)構(gòu)也使得并行成為了可能兽埃，在進(jìn)行節(jié)點(diǎn)的分裂時(shí)侥钳，需要計(jì)算每個(gè)特征的增益，最終選增益最大的那個(gè)特征去做分裂柄错，那么各個(gè)特征的增益計(jì)算就可以開多線程進(jìn)行舷夺。
- 可并行的近似直方圖算法。樹節(jié)點(diǎn)在進(jìn)行分裂時(shí)鄙陡，我們需要計(jì)算每個(gè)特征的每個(gè)分割點(diǎn)對(duì)應(yīng)的增益冕房，即用貪心法枚舉所有可能的分割點(diǎn)。當(dāng)數(shù)據(jù)無法一次載入內(nèi)存或者在分布式情況下趁矾，貪心算法效率就會(huì)變得很低耙册，所以xgboost還提出了一種可并行的近似直方圖算法，用于高效地生成候選的分割點(diǎn)毫捣，大致的思想是根據(jù)百分位法列舉幾個(gè)可能成為分割點(diǎn)的候選者详拙，然后從候選者中計(jì)算Gain按最大值找出最佳的分割點(diǎn)帝际。
- 特征重要性。XGBoost在訓(xùn)練的過程中給出各個(gè)特征的評(píng)分饶辙，Gain蹲诀、Cover、Frequency弃揽，從而表明每個(gè)特征對(duì)模型訓(xùn)練的重要性脯爪。
常見問題
XGBoost在什么地方做的剪枝，怎么做的矿微？
答：XGBoost 先從頂?shù)降捉渲钡阶畲笊疃群勐購(gòu)牡椎巾敺聪驒z查是否有不滿足分裂條件的結(jié)點(diǎn)，進(jìn)行剪枝涌矢。XGBoost如何分布式掖举？特征分布式和數(shù)據(jù)分布式？ 各有什么存在的問題娜庇？
答：XGBoost在訓(xùn)練之前塔次，預(yù)先對(duì)數(shù)據(jù)按列進(jìn)行排序，然后保存block結(jié)構(gòu)名秀。（1）特征分布式/特征間并行：由于將數(shù)據(jù)按列存儲(chǔ)励负，可以同時(shí)訪問所有列，那么可以對(duì)所有屬性同時(shí)執(zhí)行split finding算法匕得，從而并行化split finding（切分點(diǎn)尋找）熄守；（2）數(shù)據(jù)分布式/特征內(nèi)并行：可以用多個(gè)block(Multiple blocks)分別存儲(chǔ)不同的樣本集，多個(gè)block可以并行計(jì)算耗跛。
問題：（1）不能從本質(zhì)上減少計(jì)算量；（2）通訊代價(jià)高攒发。
