1.算法公式推導(dǎo)

? ? ????XGBoost目標(biāo)函數(shù)不止有損失函數(shù)雕沉，同時(shí)加入樹的結(jié)構(gòu)風(fēng)險(xiǎn)項(xiàng)（即正則項(xiàng)），這樣在構(gòu)建樹的過程颇玷，會(huì)約束樹的生長結(jié)構(gòu)笨农，減少過擬合問題。這樣一來帖渠，目標(biāo)函數(shù)就變成：

? ? ????再來看看如何表示一棵樹的復(fù)雜度谒亦，T為樹的節(jié)點(diǎn)數(shù)，w為樹節(jié)點(diǎn)的取值阿弃。w,T前是正則項(xiàng)的超參數(shù)：

? ?????要最小化這個(gè)目標(biāo)函數(shù)诊霹，我們需要枚舉所有可能的樹組合羞延，然后選擇損失函數(shù)最小的模型渣淳，這是十分不現(xiàn)實(shí)的，是NP完全問題伴箩，所以采用一種貪心思想入愧，假設(shè)已經(jīng)建好了最優(yōu)的k-1棵樹，那么第k棵樹是什么樣的呢嗤谚？無非就是前k-1棵樹加上第k棵樹的預(yù)測值與真實(shí)值最接近棺蛛，使總損失最小，目標(biāo)函數(shù)可以寫成：

????????在GBDT中巩步，僅用了損失函數(shù)的負(fù)梯度去構(gòu)建當(dāng)前第k棵樹旁赊，而XGBoost則用了損失函數(shù)的二階近似，加快損失函數(shù)的下降速度椅野，使迭代速度更快终畅。具體的，對上面的目標(biāo)函數(shù)作二階泰勒展開竟闪，得到：

?????????去掉常數(shù)項(xiàng)得? ? ? ?

? ? ? ? 因?yàn)闃涞墓?jié)點(diǎn)已經(jīng)確定离福，可以知道那些樣本落在樹的那些節(jié)點(diǎn)上。對樹節(jié)點(diǎn)上的所有樣本做求和炼蛤，得到損失函數(shù)為：

????????式6中是關(guān)于wj的 二次函數(shù)妖爷，當(dāng)樹結(jié)構(gòu)固定時(shí),wj的最優(yōu)值為：

? ? ? ? 目標(biāo)函數(shù)的最小值為：

? ? ? ? 上圖公式可以作為構(gòu)建決策樹時(shí)特征選擇和決策點(diǎn)選擇的依據(jù)，加到某個(gè)節(jié)點(diǎn)分裂為兩個(gè)子樹理朋，則一定是分裂后的損失比原來的損失要小絮识，二者的差為：

2.分裂算法介紹

????????精確貪心算法(Basic Exact Greedy Algorithm )

????????尋找一個(gè)最優(yōu)的分裂點(diǎn)，遍歷每個(gè)特征的每個(gè)可能的分裂點(diǎn)嗽上，找到目標(biāo)函數(shù)增加最大的點(diǎn)作為新的分裂特征和分裂點(diǎn)次舌。

????????近似算法

????????當(dāng)數(shù)據(jù)量過大，精確算法就不好用了炸裆，因?yàn)橐闅v每個(gè)分割點(diǎn)垃它，甚至內(nèi)存都放不下，所以，xgb提出了額外一種近似算法能加快運(yùn)行時(shí)間：

? ? ? ? 這個(gè)算法根據(jù)特征的分布情況国拇，然后做個(gè)proposal洛史，然后這一列的分割點(diǎn)就從這幾個(gè)proposed candidate points里選，能大大提高效率酱吝。有兩種proposal的方式也殖，分別是global和local。global的是在建樹之前就做proposal然后每次分割都要更新一下proposal务热，local的方法是在每次split之后更新proposal忆嗜。通常發(fā)現(xiàn)local的方法需要更少的candidate，而global的方法在有足夠的candidate的時(shí)候效果跟local差不多崎岂。系統(tǒng)能充分支持exact greedy跑在單臺(tái)機(jī)器或多臺(tái)機(jī)器上捆毫，也支持這個(gè)proposal的近似算法，并且都能設(shè)定global還是local的proposal方式冲甘。

????????存在稀疏值時(shí)的分裂 Sparsity-aware Split Finding

????????另外绩卤，在分割的時(shí)候，這個(gè)系統(tǒng)還能感知稀疏值江醇，我們給每個(gè)樹的結(jié)點(diǎn)都加了一個(gè)默認(rèn)方向濒憋，當(dāng)一個(gè)值是缺失值時(shí)，我們就把他分類到默認(rèn)方向陶夜，每個(gè)分支有兩個(gè)選擇凛驮，論文提出一個(gè)算法，枚舉向左和向右的情況条辟，哪個(gè)gain大選哪個(gè)：

3.總結(jié)

????????基于決策樹的集成學(xué)習(xí)在傳統(tǒng)機(jī)器學(xué)習(xí)方法中取得了非常好的效果黔夭，尤其是XGB，被數(shù)據(jù)科學(xué)家廣泛使用捂贿，并在很多問題上有很好的表現(xiàn)纠修。

????????論文除了給出XGB的模型和算法，在工程實(shí)現(xiàn)方面精耕細(xì)作厂僧，做了盡可能的優(yōu)化扣草，這些方法也保證了模型能夠取得更好的效果，并能夠構(gòu)建端到端的學(xué)習(xí)系統(tǒng)颜屠。