更好的閱讀體驗請?zhí)D(zhuǎn)至XGBoost原理
一.緒論
在實際應(yīng)用的機器學(xué)習(xí)方法里，GradientTree Boosting （GBDT）是一個在很多應(yīng)用里都很出彩的技術(shù)莫矗。XGBoost是一套提升樹可擴展的機器學(xué)習(xí)系統(tǒng)捅膘。2015年Kaggle發(fā)布的29個獲勝方法里有17個用了XGBoost涡上。在這些方案里猩系，有8個僅用了XGBoost，另外的大多數(shù)用它結(jié)合了神經(jīng)網(wǎng)絡(luò)兆蕉。對比來看羽戒，第二流行的方法，深度神經(jīng)網(wǎng)絡(luò)虎韵，只被用了11次易稠。這個系統(tǒng)的成功性也被KDDCup2015所見證了，前十的隊伍都用了XGBoost包蓝。此外驶社，據(jù)勝出的隊伍說，很少有別的集成學(xué)習(xí)方法效果能超過調(diào)好參的XGBoost测萎。
主要創(chuàng)新點：
設(shè)計和構(gòu)建高度可擴展的端到端提升樹系統(tǒng)衬吆。
提出了一個理論上合理的加權(quán)分位數(shù)略圖（weighted quantile
sketch ）來計算候選集。
引入了一種新穎的稀疏感知算法用于并行樹學(xué)習(xí)绳泉。 令缺失值有默認方向逊抡。
提出了一個有效的用于核外樹形學(xué)習(xí)的緩存感知塊結(jié)構(gòu)。 用緩存加速尋找排序后被打亂的索引的列數(shù)據(jù)的過程零酪。
二.算法原理
1.學(xué)習(xí)目標
首先來看下我們是如何預(yù)測的：
XGBoost是一個樹集成模型冒嫡，他將K（樹的個數(shù)）個樹的結(jié)果進行求和，作為最終的預(yù)測值四苇。即：
假設(shè)給定的樣本集有n個樣本孝凌，m個特征，則
其中 xi 表示第i個樣本月腋，yi 表示第i個類別標簽蟀架，回歸樹（CART樹）的空間F為
其中q代表每棵樹的結(jié)構(gòu)，他將樣本映射到對應(yīng)的葉節(jié)點榆骚；T是對應(yīng)樹的葉節(jié)點個數(shù)片拍；f(x)對應(yīng)樹的結(jié)構(gòu)q和葉節(jié)點權(quán)重w。所以XGBoost的預(yù)測值是每棵樹對應(yīng)的葉節(jié)點的值的和妓肢。
我們的目標是學(xué)習(xí)這k個樹捌省，所以我們最小化下面這個帶正則項的目標函數(shù)：
上式的第一項是損失誤差，如MSE和logistic等碉钠，第二項是正則項纲缓，控制樹的復(fù)雜度卷拘，防止過擬合。
式子2中目標函數(shù)的優(yōu)化參數(shù)是模型（functions）祝高，不能使用傳統(tǒng)的優(yōu)化方法在歐氏空間優(yōu)化栗弟，但是模型在訓(xùn)練時，是一種加法的方式（additive manner）工闺，所以在第t輪乍赫，我們將f（t）加入模型，最小化下面的目標函數(shù)：
訓(xùn)練時斤寂，新的一輪加入一個新的f函數(shù)耿焊，來最大化的降低目標函數(shù)，在第t輪遍搞，我們的目標函數(shù)為 ：
接下來我們將目標函數(shù)進行泰勒展開罗侯，取前三項，移除高階小無窮小項溪猿，最后我們的目標函數(shù)轉(zhuǎn)化為：
其中：
接下來我們求解這個目標函數(shù)
最終我們將關(guān)于樹模型的迭代轉(zhuǎn)化為關(guān)于樹的葉子節(jié)點的迭代钩杰，并求出最優(yōu)的葉節(jié)點分數(shù)。
將葉節(jié)點的最優(yōu)值帶入目標函數(shù)诊县，最終目標函數(shù)的形式為：
上式可以作為得分函數(shù)用來測量樹結(jié)構(gòu)q的質(zhì)量讲弄，他類似與決策樹的不純度得分，只是他通過更廣泛的目標函數(shù)得到
通過上式我們可以看到依痊，當樹結(jié)構(gòu)確定時避除，樹的結(jié)構(gòu)得分只與其一階倒數(shù)和二階倒數(shù)有關(guān)，得分越小胸嘁，說明結(jié)構(gòu)越好瓶摆。
節(jié)點劃分
而通常情況下，我們無法枚舉所有可能的樹結(jié)構(gòu)然后選取最優(yōu)的性宏，所以我們選擇用一種貪婪算法來代替：我們從單個葉節(jié)點開始群井，迭代分裂來給樹添加節(jié)點。節(jié)點切分后的損失函數(shù)：
上式用來評估切分后的損失函數(shù)毫胜，我們的目標是尋找一個特征及對應(yīng)的值书斜，使得切分后的loss reduction最大。γ除了控制樹的復(fù)雜度酵使，另一個作用是作為閾值荐吉，只有當分裂后的增益大于γ時，才選擇分裂凝化，起到了預(yù)剪枝的作用稍坯。
縮減與列采樣
除了在目標函數(shù)中引入正則項，為了防止過擬合搓劫，XGBoost還引入了縮減(shrinkage)和列抽樣（column subsampling）瞧哟，通過在每一步的boosting中引入縮減系數(shù)，降低每個樹和葉子對結(jié)果的影響枪向；列采樣是借鑒隨機森林中的思想勤揩，根據(jù)反饋，列采樣有時甚至比行抽樣效果更好秘蛔，同時陨亡，通過列采樣能加速計算。
尋找最佳分割點算法
樹模型學(xué)習(xí)的一個關(guān)鍵問題是如何尋找最優(yōu)分割點深员。第一種方法稱為基本精確貪心算法（exact greedy algorithm）：枚舉所有特征的所有可能劃分负蠕，尋找最優(yōu)分割點。該算法要求為連續(xù)特征枚舉所有可能的切分倦畅，這個對計算機要求很高遮糖，為了有效做到這一點，XGBoost首先對特征進行排序叠赐，然后順序訪問數(shù)據(jù)欲账，累計loss reduction中的梯度統(tǒng)計量（式6）。
上述方法是一個非常精確的分割點算法芭概，但是當數(shù)據(jù)無法完全加載進內(nèi)存或分布式的情況下赛不，該算法就不是特別有效了。為了支持這兩種場景罢洲，提出了一種近似算法：根據(jù)特征分布的百分位數(shù)踢故，提出n個候選切分點，然后將樣本映射到對應(yīng)的兩個相鄰的切分點組成的桶中惹苗，聚會統(tǒng)計值殿较，通過聚會后的統(tǒng)計值及推薦分割點，計算最佳分割點鸽粉。該算法有兩種形式：全局近似和局部近似斜脂，其差別是全局近似是在生成一棵樹之前，對各個特征計算其分位點并劃分樣本触机；局部近似是在每個節(jié)點進行分裂時采用近似算法帚戳。近似算法的流程：
帶權(quán)重的分位數(shù)略圖（weighted quantile sketch）算法
在近似算法中重要的一步是尋找候選分割點，通常情況下儡首，特征的百分位數(shù)使數(shù)據(jù)均勻的分布在數(shù)據(jù)上∑危現(xiàn)在我們定義一個數(shù)據(jù)集Dk = {(x1k, h1), (x2k, h2) ... }代表樣本的第k個特征及其對應(yīng)的二階梯度，現(xiàn)在我們定義一個函數(shù)rk：
上式代表特征k小于特征z的樣本比例蔬胯，我們的目標是尋找候選分割點{sk1, sk2,...}对供，使它滿足：
其中e是候選因子，即切分的百分位數(shù)，所以最后有大約1/e個候選分割點产场。那為什么可以用二階倒數(shù)h來代替權(quán)重呢鹅髓？我們將目標函數(shù)變形為
上式可以看成是label是gi/hi，權(quán)重是hi的平方損失京景，這對于大數(shù)據(jù)下尋找劃分點非常重要窿冯。在以往的分位法中，沒有考慮權(quán)值确徙，許多存在的近似方法中醒串，或者通過排序或者通過啟發(fā)式方法（沒有理論保證）劃分。文章的貢獻是提供了理論保證的分布式加權(quán)分位法鄙皇。
為什么要對目標函數(shù)進行類似的變形芜赌？思考一下我們劃分分割點的目標是什么？是希望均勻的劃分loss伴逸，而不同樣本對loss的權(quán)重不同缠沈，不考慮權(quán)重直接按樣本劃分時，loss的分布是不均勻的违柏，對應(yīng)的分位點就會有偏差博烂。
PS：文章中的近似變形感覺不太近似，更近似的變形可能是
即label是-gi/hi的帶權(quán)重平方損失漱竖。不知道文章內(nèi)為啥是另一種形式
稀疏自適應(yīng)分割策略
實際情況下避免不了數(shù)據(jù)稀疏禽篱，產(chǎn)生數(shù)據(jù)稀疏的原因主要有三個：1，數(shù)據(jù)缺失馍惹，2躺率，統(tǒng)計上為0，3万矾，one-hot編碼悼吱。而適應(yīng)稀疏數(shù)據(jù)非常重要。XGBoost提出的是在計算分割后的分數(shù)時良狈，遇到缺失值后添，分別將缺失值帶入左右兩個分割節(jié)點，然后取最大值的方向為其默認方向薪丁。
以上就是XGBoost所涉及的算法原理遇西。
3.XGBoost的優(yōu)缺點
與GBDT對比
1.GBDT的基分類器只支持CART樹，而XGBoost支持線性分類器严嗜，此時相當于帶有L1和L2正則項的邏輯回歸（分類問題）和線性回歸（回歸問題）粱檀。
2.GBDT在優(yōu)化時只使用了一階倒數(shù)，而XGBoost對目標函數(shù)進行二階泰勒展開漫玄，此外茄蚯，XGBoost支持自定義損失函數(shù)，只要損失函數(shù)二階可導(dǎo)
3.XGBoost借鑒隨機森林算法，支持列抽樣和行抽樣渗常，這樣即能降低過擬合風(fēng)險壮不，又能降低計算。
4.XGBoost在目標函數(shù)中引入了正則項凳谦，正則項包括葉節(jié)點的個數(shù)及葉節(jié)點的輸出值的L2范數(shù)忆畅。通過約束樹結(jié)構(gòu)衡未，降低模型方差尸执，防止過擬合。
5.XGBoost對缺失值不敏感缓醋，能自動學(xué)習(xí)其分裂方向
6.XGBoost在每一步中引入縮減因子如失，降低單顆樹對結(jié)果的影響，讓后續(xù)模型有更大的優(yōu)化空間送粱，進一步防止過擬合褪贵。
7.XGBoost在訓(xùn)練之前，對數(shù)據(jù)預(yù)先進行排序并保存為block抗俄，后續(xù)迭代中重復(fù)使用脆丁，減少計算，同時在計算分割點時动雹，可以并行計算
8.可并行的近似直方圖算法槽卫，樹結(jié)點在進行分裂時，需要計算每個節(jié)點的增益胰蝠，若數(shù)據(jù)量較大歼培，對所有節(jié)點的特征進行排序，遍歷的得到最優(yōu)分割點茸塞，這種貪心法異常耗時躲庄，這時引進近似直方圖算法，用于生成高效的分割點钾虐，即用分裂后的某種值減去分裂前的某種值噪窘，獲得增益，為了限制樹的增長效扫，引入閾值倔监，當增益大于閾值時，進行分裂荡短；
與LightGBM對比
1.XGBoost采用預(yù)排序丐枉，在迭代之前，對結(jié)點的特征做預(yù)排序掘托，遍歷選擇最優(yōu)分割點瘦锹，數(shù)據(jù)量大時，貪心法耗時，LightGBM方法采用histogram算法弯院，占用的內(nèi)存低辱士，數(shù)據(jù)分割的復(fù)雜度更低，但是不能找到最精確的數(shù)據(jù)分割點听绳。同時颂碘，不精確的分割點可以認為是降低過擬合的一種手段。
2.LightGBM借鑒Adaboost的思想椅挣，對樣本基于梯度采樣头岔，然后計算增益，降低了計算
3.LightGBM對列進行合并鼠证，降低了計算
4.XGBoost采樣level-wise策略進行決策樹的生成峡竣，同時分裂同一層的節(jié)點，采用多線程優(yōu)化量九，不容易過擬合适掰，但有些節(jié)點分裂增益非常小，沒必要進行分割荠列，這就帶來了一些不必要的計算类浪；LightGBM采樣leaf-wise策略進行樹的生成，每次都選擇在當前葉子節(jié)點中增益最大的節(jié)點進行分裂肌似，如此迭代费就，但是這樣容易產(chǎn)生深度很深的樹，產(chǎn)生過擬合锈嫩，所以增加了最大深度的限制受楼，來保證高效的同時防止過擬合。
參考：https://arxiv.org/pdf/1603.02754.pdf
https://www.zhihu.com/question/41354392/answer/98658997
