上一篇文章講述了general GBDT的模型原理，鏈接：http://www.itdecent.cn/p/943fcb6d651a。本文講述Xgboost的算法原理。
最好的教材是官網(wǎng)的tutorial。有一點不夠general的是，tutorial的Loss函數(shù)假定為均方誤差。本文主要突出Xgboost改進(jìn)的地方。
模型目標(biāo)函數(shù)
機(jī)器學(xué)習(xí)問題的本質(zhì)是數(shù)據(jù)分布的模型擬合，用數(shù)學(xué)語言表達(dá)就是目標(biāo)函數(shù)的最優(yōu)化問題。跟GBDT類似，Xgboost對于給定數(shù)據(jù)集進(jìn)行additive trainning，學(xué)習(xí)K棵樹，得到下面的預(yù)測函數(shù)：
上述預(yù)測函數(shù)是如何得到的呢？我們需要分析目標(biāo)函數(shù)，如下：
其中，第一項跟GBDT中是一樣的，選定某個損失函數(shù)，計算預(yù)測值與真實值的偏差，第二項為正則項，傳統(tǒng)的GBDT并沒有，也是Xgboost改進(jìn)的地方。我們知道決策樹的一個缺點就是易過擬合，需要剪枝操作，這里的正則項起到類似的作用。
第t次迭代，目標(biāo)函數(shù)具體寫作：
然后，基于前t-1次的預(yù)測值yt-1處做二階的泰勒展開：
而GBDT的這部分則是基于前t-1次的預(yù)測值yt-1處做一階的泰勒展開，這也是Xgboost改進(jìn)的地方，泰勒二階近似比一階近似更接近真實的Loss Fnction，自然優(yōu)化的更徹底。
接下來分析正則項的形式，如下：
為什么是這樣的形式，官網(wǎng)的說明是：
Of course there is more than one way to define the complexity, but this specific one works well in practice.
其中，T為葉子節(jié)點的數(shù)目，w為葉子節(jié)點的value向量。
對樹函數(shù)f作如下變換：
將正則項的具體形式和變換后的樹函數(shù)帶入目標(biāo)函數(shù)，如下：
統(tǒng)一i，j的求和，如下：
可以看出t輪的L函數(shù)是關(guān)于w的二次函數(shù)，求極值：
回歸樹的學(xué)習(xí)策略
上一節(jié)明確了Xgboost每棵樹的擬合目標(biāo)，但是如何擬合呢？如何確定樹的結(jié)構(gòu)呢？
先回顧下一般的樹的分裂的方法？
Xgboost的打分函數(shù)：
Xgboost的分裂規(guī)則：
還有一個問題，那每棵樹的非葉子節(jié)點的最佳分割點怎么找？
解釋下，近似于基于hi的直方圖分割，看成一種近似的分割。我的理解跟特征的離散化很像。傳統(tǒng)的暴力搜索十分耗時。
與GBDT的其他不同
- Shrinkage（縮減）
xgboost在進(jìn)行完一次迭代后，會將葉子節(jié)點的權(quán)重乘上該系數(shù)，主要是為了削弱每棵樹的影響，讓后面有更大的學(xué)習(xí)空間。實際應(yīng)用中，一般把eta設(shè)置得小一點，然后迭代次數(shù)設(shè)置得大一點。 - 列抽樣
這一點借鑒的是隨機(jī)森林，就是對特征屬性抽樣。行采樣是對樣本的數(shù)目采樣。 - 支持并行計算
首先明確一點的是，并行的方式不是樹同時訓(xùn)練，而是在訓(xùn)練每棵樹時的分裂過程。排序數(shù)據(jù)是樹學(xué)習(xí)最耗時的方面。 為了減少分類成本，數(shù)據(jù)存儲在稱為“塊”的內(nèi)存單元中。 每個塊都有按相應(yīng)特征值排序的數(shù)據(jù)列。 這種計算只需要在訓(xùn)練前完成一次，以后可以重復(fù)使用。塊的排序可以獨立完成，并可以在CPU的并行線程之間分配。 由于每列的統(tǒng)計數(shù)據(jù)收集是并行完成的，所以可以并行分割查找。 -
缺失值處理
缺失值是實際的機(jī)器學(xué)習(xí)項目中不容忽視的問題。自帶的工具包幫你解決不是好事，因為默認(rèn)的處理方式不一定符合你的場景。Xgboost的處理方式是，缺失值數(shù)據(jù)會被分到左子樹和右子樹分別計算損失，選擇較優(yōu)的那個。如果訓(xùn)練中沒有數(shù)據(jù)缺失，預(yù)測時出現(xiàn)了數(shù)據(jù)缺失，默認(rèn)分類到右子樹。
