這篇文章打算介紹一下boosting 和xgboost，這兩天也看了好多文章，也感覺(jué)了解的不深，算是做個(gè)記錄。
Boost算法
先簡(jiǎn)單提一下Bagging， 原理是從現(xiàn)有數(shù)據(jù)中有放回的抽取若干個(gè)樣本構(gòu)建分類器，重復(fù)若干次建立若干個(gè)分類器進(jìn)行投票。
而Boost（提升）是指每一步都產(chǎn)生一個(gè)弱預(yù)測(cè)模型，然后加權(quán)累加到總模型中。每一步弱預(yù)測(cè)模型生成的依據(jù)都是損失函數(shù)的負(fù)梯度方向，若干步以后就可以達(dá)到逼近損失函數(shù)局部的最小值。
首先Boost是一個(gè)加法模型，有若干個(gè)基函數(shù)及其權(quán)重乘積之和的累加。
其中b是基函數(shù)，beta是基函數(shù)的系數(shù)，這就是最終分類器的樣子。目標(biāo)就是想辦法使損失函數(shù)的期望最小值。
一步對(duì)m個(gè)分類起優(yōu)化太難，因此有一個(gè)稍微折中的辦法，因?yàn)槭羌臃Ｐ?，每一步只?duì)其中一個(gè)基函數(shù)及其系數(shù)進(jìn)行求解，逐步逼近損失函數(shù)的最小值。
要使損失函數(shù)最小，那么新加的這一項(xiàng)剛好等于損失函數(shù)的負(fù)梯度。這樣一步一步就使得損失函數(shù)下降最快。
這里的lambda可以和beta合并表示步長(zhǎng)。對(duì)于這個(gè)基函數(shù)而言，其實(shí)就是關(guān)于x和這個(gè)函數(shù)梯度的一個(gè)擬合，然后步長(zhǎng)的選擇可以根據(jù)線性搜索，即尋找在這個(gè)梯度上下降最小值的那個(gè)步長(zhǎng)，盡快逼近損失函數(shù)的最小值。
梯度提升完
GBDT
首先既然是樹(shù)，上一篇介紹過(guò)，基函數(shù)是決策樹(shù)，而損失函數(shù)則是根據(jù)具體問(wèn)題具體分析，不過(guò)總體方法都是一樣，梯度下降。
比如到第m步， 計(jì)算殘差。
有了殘差，再用（xi， rim）去擬合第m個(gè)基函數(shù)。假設(shè)這顆樹(shù)把輸入空間劃分成j個(gè)空間R1m, R2m, ...., Rjm。假設(shè)在每個(gè)空間的輸出為bjm。這樣，第m棵樹(shù)可以表示如下：
下一步，對(duì)樹(shù)的每個(gè)區(qū)域分別用線性搜索的方法尋找最佳步長(zhǎng)，然后與上面的區(qū)域預(yù)測(cè)值合并，最后可以得到第m步的目標(biāo)函數(shù)。
對(duì)于GBDT容易出現(xiàn)過(guò)擬合，所以有必要增加一點(diǎn)正則項(xiàng)，比如葉子節(jié)點(diǎn)數(shù)目或葉子節(jié)點(diǎn)預(yù)測(cè)值的平方和，限制模型復(fù)雜度的過(guò)度提升。
XGBoost
之前用的梯度下降只考慮了一階信息，根據(jù)泰勒展開(kāi)，把二階信息用上：
其中fm為參數(shù)的函數(shù)是正則項(xiàng)。可以表示如下：
對(duì)于決策樹(shù)而言，最重要的一共有多少個(gè)節(jié)點(diǎn)以及節(jié)點(diǎn)的權(quán)值。所以決策樹(shù)可以表示為：
各種公式，最后得到
可以得到的結(jié)果是：把新一步函數(shù)的損失函數(shù)變成了只與上一步相關(guān)的一個(gè)新的損失函數(shù)。這樣可以遍歷數(shù)據(jù)中所有的分割點(diǎn)，尋找新的損失函數(shù)下降最多的分割點(diǎn)，重復(fù)上述操作。
相比于梯度下降提升，XGBoost在劃分新的樹(shù)的時(shí)候還用到了二階信息，因此能夠更快的收斂；由于用c/c++寫的，速度也快。在尋找最加分割點(diǎn)的時(shí)候，還可以引入并行計(jì)算，因此速度進(jìn)一步提高。
參考文章：
XGBoost 與 Boosted Tree:多看幾遍
