上一篇文章講述了general GBDT的模型原理，鏈接：http://www.reibang.com/p/943fcb6d651a萄金。本文講述Xgboost的算法原理媚朦。
最好的教材是官網(wǎng)的tutorial询张。有一點(diǎn)不夠general的是，tutorial的Loss函數(shù)假定為均方誤差份氧。本文主要突出Xgboost改進(jìn)的地方蜗帜。
模型目標(biāo)函數(shù)
機(jī)器學(xué)習(xí)問(wèn)題的本質(zhì)是數(shù)據(jù)分布的模型擬合，用數(shù)學(xué)語(yǔ)言表達(dá)就是目標(biāo)函數(shù)的最優(yōu)化問(wèn)題厅缺。跟GBDT類似，Xgboost對(duì)于給定數(shù)據(jù)集進(jìn)行additive trainning诀豁，學(xué)習(xí)K棵樹(shù)舷胜，得到下面的預(yù)測(cè)函數(shù)：
上述預(yù)測(cè)函數(shù)是如何得到的呢？我們需要分析目標(biāo)函數(shù)翻伺，如下：
其中展氓，第一項(xiàng)跟GBDT中是一樣的，選定某個(gè)損失函數(shù)，計(jì)算預(yù)測(cè)值與真實(shí)值的偏差空入，第二項(xiàng)為正則項(xiàng)族檬，傳統(tǒng)的GBDT并沒(méi)有，也是Xgboost改進(jìn)的地方埋凯。我們知道決策樹(shù)的一個(gè)缺點(diǎn)就是易過(guò)擬合扫尖，需要剪枝操作，這里的正則項(xiàng)起到類似的作用甩恼。
第t次迭代沉颂，目標(biāo)函數(shù)具體寫(xiě)作：
然后铸屉，基于前t-1次的預(yù)測(cè)值yt-1處做二階的泰勒展開(kāi)：
而GBDT的這部分則是基于前t-1次的預(yù)測(cè)值yt-1處做一階的泰勒展開(kāi)，這也是Xgboost改進(jìn)的地方顷啼，泰勒二階近似比一階近似更接近真實(shí)的Loss Fnction，自然優(yōu)化的更徹底椰于。
接下來(lái)分析正則項(xiàng)的形式仪搔，如下：
為什么是這樣的形式，官網(wǎng)的說(shuō)明是：
Of course there is more than one way to define the complexity, but this specific one works well in practice.
其中偏陪，T為葉子節(jié)點(diǎn)的數(shù)目煮嫌，w為葉子節(jié)點(diǎn)的value向量。
對(duì)樹(shù)函數(shù)f作如下變換：
將正則項(xiàng)的具體形式和變換后的樹(shù)函數(shù)帶入目標(biāo)函數(shù)饥脑，如下：
統(tǒng)一i灶轰，j的求和刷钢，如下：
可以看出t輪的L函數(shù)是關(guān)于w的二次函數(shù)内地，求極值：
回歸樹(shù)的學(xué)習(xí)策略
上一節(jié)明確了Xgboost每棵樹(shù)的擬合目標(biāo)，但是如何擬合呢非凌？如何確定樹(shù)的結(jié)構(gòu)呢茬祷？
先回顧下一般的樹(shù)的分裂的方法？
Xgboost的打分函數(shù)：
Xgboost的分裂規(guī)則：
還有一個(gè)問(wèn)題，那每棵樹(shù)的非葉子節(jié)點(diǎn)的最佳分割點(diǎn)怎么找沃粗？
解釋下最盅，近似于基于hi的直方圖分割起惕，看成一種近似的分割。我的理解跟特征的離散化很像嘀粱。傳統(tǒng)的暴力搜索十分耗時(shí)辰狡。
與GBDT的其他不同
- Shrinkage（縮減）
xgboost在進(jìn)行完一次迭代后，會(huì)將葉子節(jié)點(diǎn)的權(quán)重乘上該系數(shù)娃磺，主要是為了削弱每棵樹(shù)的影響叫倍，讓后面有更大的學(xué)習(xí)空間。實(shí)際應(yīng)用中涯冠，一般把eta設(shè)置得小一點(diǎn)逼庞，然后迭代次數(shù)設(shè)置得大一點(diǎn)瞻赶。 - 列抽樣
這一點(diǎn)借鑒的是隨機(jī)森林，就是對(duì)特征屬性抽樣璧南。行采樣是對(duì)樣本的數(shù)目采樣师逸。 - 支持并行計(jì)算
首先明確一點(diǎn)的是，并行的方式不是樹(shù)同時(shí)訓(xùn)練动知，而是在訓(xùn)練每棵樹(shù)時(shí)的分裂過(guò)程员辩。排序數(shù)據(jù)是樹(shù)學(xué)習(xí)最耗時(shí)的方面。 為了減少分類成本丹皱，數(shù)據(jù)存儲(chǔ)在稱為“塊”的內(nèi)存單元中。 每個(gè)塊都有按相應(yīng)特征值排序的數(shù)據(jù)列讼油。 這種計(jì)算只需要在訓(xùn)練前完成一次呢簸，以后可以重復(fù)使用。塊的排序可以獨(dú)立完成嘿架，并可以在CPU的并行線程之間分配啸箫。 由于每列的統(tǒng)計(jì)數(shù)據(jù)收集是并行完成的，所以可以并行分割查找忘苛。 -
缺失值處理
缺失值是實(shí)際的機(jī)器學(xué)習(xí)項(xiàng)目中不容忽視的問(wèn)題扎唾。自帶的工具包幫你解決不是好事，因?yàn)槟J(rèn)的處理方式不一定符合你的場(chǎng)景荧呐。Xgboost的處理方式是纸镊，缺失值數(shù)據(jù)會(huì)被分到左子樹(shù)和右子樹(shù)分別計(jì)算損失，選擇較優(yōu)的那個(gè)峰搪。如果訓(xùn)練中沒(méi)有數(shù)據(jù)缺失凯旭，預(yù)測(cè)時(shí)出現(xiàn)了數(shù)據(jù)缺失，默認(rèn)分類到右子樹(shù)鞠柄。
