本文主要簡(jiǎn)要的比較了常用的boosting算法的一些區(qū)別，從AdaBoost到LightGBM,包括AdaBoost,GBDT,XGBoost,LightGBM四個(gè)模型的簡(jiǎn)單介紹，一步一步從原理到優(yōu)化對(duì)比。 AdaBoost原理 原始的AdaBoost算法是在算法開(kāi)始的時(shí)候，為每一個(gè)樣本賦上一個(gè)權(quán)重值，初始的時(shí)候，大家都是一樣重要的。在每一步訓(xùn)練中得到的模型，會(huì)使得數(shù)據(jù)點(diǎn)的估計(jì)有對(duì)有錯(cuò)，我們就在每一步結(jié)束后，增加分錯(cuò)的點(diǎn)的權(quán)重，減少分對(duì)的點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老是被分錯(cuò)，那么就會(huì)被“重點(diǎn)關(guān)注”，也就被賦上一個(gè)很高的權(quán)重。然后等進(jìn)行了N次迭代（由用戶指定），將會(huì)得到N個(gè)簡(jiǎn)單的分類(lèi)器（basic learner），然后我們將它們組合起來(lái)（比如說(shuō)可以對(duì)它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等），得到一個(gè)最終的模型。 關(guān)鍵字：樣本的權(quán)重分布 GBDT概述 GBDT（Gradient Boosting Decison Tree）中的樹(shù)都是回歸樹(shù)，GBDT用來(lái)做回歸預(yù)測(cè)，調(diào)整后也可以用于分類(lèi)（設(shè)定閾值，大于閾值為正例，反之為負(fù)例），可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合。GBDT是把所有樹(shù)的結(jié)論累加起來(lái)做最終結(jié)論的，GBDT的核心就在于，每一棵樹(shù)學(xué)的是之前所有樹(shù)結(jié)論和的殘差(負(fù)梯度)，這個(gè)殘差就是一個(gè)加預(yù)測(cè)值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，但第一棵樹(shù)的預(yù)測(cè)年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹(shù)里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹(shù)真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹(shù)的結(jié)論就是A的真實(shí)年齡；如果第二棵樹(shù)的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹(shù)里A的年齡就變成1歲，繼續(xù)學(xué)。 Boosting的最大好處在于，每一步的殘差計(jì)算其實(shí)變相地增大了分錯(cuò)instance的權(quán)重，而已經(jīng)分對(duì)的instance則都趨向于0。這樣后面的樹(shù)就能越來(lái)越專(zhuān)注那些前面被分錯(cuò)的instance。 Gradient Boost與AdaBoost的區(qū)別 Gradient Boost每一次的計(jì)算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度(Gradient)方向上建立一個(gè)新的模型。所以說(shuō)，在Gradient Boost中，每個(gè)新的模型的建立是為了使得之前模型的殘差往梯度方向減少。Shrinkage（縮減）的思想認(rèn)為，每次走一小步逐漸逼近結(jié)果的效果，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過(guò)擬合。即它不完全信任每一個(gè)棵殘差樹(shù)，它認(rèn)為每棵樹(shù)只學(xué)到了真理的一小部分，累加的時(shí)候只累加一小部分，通過(guò)多學(xué)幾棵樹(shù)彌補(bǔ)不足。本質(zhì)上，Shrinkage為每棵樹(shù)設(shè)置了一個(gè)weight，累加時(shí)要乘以這個(gè)weight，但和Gradient并沒(méi)有關(guān)系。 Adaboost是另一種boost方法，它按分類(lèi)對(duì)錯(cuò)，分配不同的weight，計(jì)算cost function時(shí)使用這些weight，從而讓“錯(cuò)分的樣本權(quán)重越來(lái)越大，使它們更被重視” Gradient Boost優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 它的非線性變換比較多，表達(dá)能力強(qiáng)，而且不需要做復(fù)雜的特征工程和特征變換。 缺點(diǎn):Boost是一個(gè)串行過(guò)程，不好并行化，而且計(jì)算復(fù)雜度高，同時(shí)不太適合高維稀疏特征。
XGBoost XGBoost能自動(dòng)利用cpu的多線程，而且適當(dāng)改進(jìn)了gradient boosting，加了剪枝，控制了模型的復(fù)雜程度 傳統(tǒng)GBDT以CART作為基分類(lèi)器，特指梯度提升決策樹(shù)算法，而XGBoost還支持線性分類(lèi)器(gblinear)，這個(gè)時(shí)候XGBoost相當(dāng)于帶L1和L2正則化項(xiàng)的邏輯斯蒂回歸（分類(lèi)問(wèn)題）或者線性回歸（回歸問(wèn)題）。 傳統(tǒng)GBDT在優(yōu)化時(shí)只用到一階導(dǎo)數(shù)信息，xgboost則對(duì)代價(jià)函數(shù)進(jìn)行了二階泰勒展開(kāi)，同時(shí)用到了一階和二階導(dǎo)數(shù)。順便提一下，xgboost工具支持自定義代價(jià)函數(shù)，只要函數(shù)可一階和二階求導(dǎo)。 xgboost在代價(jià)函數(shù)里加入了正則項(xiàng)，用于控制模型的復(fù)雜度。正則項(xiàng)里包含了樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)、每個(gè)葉子節(jié)點(diǎn)上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來(lái)講，正則項(xiàng)降低了模型的variance，使學(xué)習(xí)出來(lái)的模型更加簡(jiǎn)單，防止過(guò)擬合，這也是xgboost優(yōu)于傳統(tǒng)GBDT的一個(gè)特性。
xgboost中樹(shù)節(jié)點(diǎn)分裂時(shí)所采用的公式： Shrinkage（縮減），相當(dāng)于學(xué)習(xí)速率（xgboost中的eta）。xgboost在進(jìn)行完一次迭代后，會(huì)將葉子節(jié)點(diǎn)的權(quán)重乘上該系數(shù)，主要是為了削弱每棵樹(shù)的影響，讓后面有更大的學(xué)習(xí)空間。實(shí)際應(yīng)用中，一般把eta設(shè)置得小一點(diǎn)，然后迭代次數(shù)設(shè)置得大一點(diǎn)。（傳統(tǒng)GBDT的實(shí)現(xiàn)也有學(xué)習(xí)速率） 列抽樣（column subsampling）。xgboost借鑒了隨機(jī)森林的做法，支持列抽樣，不僅能降低過(guò)擬合，還能減少計(jì)算，這也是xgboost異于傳統(tǒng)gbdt的一個(gè)特性。 對(duì)缺失值的處理。對(duì)于特征的值有缺失的樣本，xgboost可以自動(dòng)學(xué)習(xí)出它的分裂方向。 xgboost工具支持并行。注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能進(jìn)行下一次迭代的（第t次迭代的代價(jià)函數(shù)里包含了前面t-1次迭代的預(yù)測(cè)值）。xgboost的并行是在特征粒度上的。我們知道，決策樹(shù)的學(xué)習(xí)最耗時(shí)的一個(gè)步驟就是對(duì)特征的值進(jìn)行排序（因?yàn)橐_定最佳分割點(diǎn)），xgboost在訓(xùn)練之前，預(yù)先對(duì)數(shù)據(jù)進(jìn)行了排序，然后保存為block結(jié)構(gòu)，后面的迭代中重復(fù)地使用這個(gè)結(jié)構(gòu)，大大減小計(jì)算量。這個(gè)block結(jié)構(gòu)也使得并行成為了可能，在進(jìn)行節(jié)點(diǎn)的分裂時(shí)，需要計(jì)算每個(gè)特征的增益，最終選增益最大的那個(gè)特征去做分裂，那么各個(gè)特征的增益計(jì)算就可以開(kāi)多線程進(jìn)行。(特征粒度上的并行，block結(jié)構(gòu)，預(yù)排序)
內(nèi)置交叉驗(yàn)證方法 能夠輸出特征重要性文件輔助特征篩選
XGBoost優(yōu)勢(shì)小結(jié)： 顯式地將樹(shù)模型的復(fù)雜度作為正則項(xiàng)加在優(yōu)化目標(biāo) 公式推導(dǎo)里用到了二階導(dǎo)數(shù)信息，而普通的GBDT只用到一階 允許使用列抽樣(column(feature) sampling)來(lái)防止過(guò)擬合，借鑒了Random Forest的思想，sklearn里的gbm好像也有類(lèi)似實(shí)現(xiàn)。 實(shí)現(xiàn)了一種分裂節(jié)點(diǎn)尋找的近似算法，用于加速和減小內(nèi)存消耗。 節(jié)點(diǎn)分裂算法能自動(dòng)利用特征的稀疏性。 樣本數(shù)據(jù)事先排好序并以block的形式存儲(chǔ)，利于并行計(jì)算 penalty function Omega主要是對(duì)樹(shù)的葉子數(shù)和葉子分?jǐn)?shù)做懲罰，這點(diǎn)確保了樹(shù)的簡(jiǎn)單性。 支持分布式計(jì)算可以運(yùn)行在MPI，YARN上，得益于底層支持容錯(cuò)的分布式通信框架rabit。
LightGBM lightGBM：基于決策樹(shù)算法的分布式梯度提升框架。 lightGBM與XGBoost的區(qū)別： 占用的內(nèi)存更低，只保存特征離散化后的值，而這個(gè)值一般用8位整型存儲(chǔ)就足夠了，內(nèi)存消耗可以降低為原來(lái)的1/8。 降低了計(jì)算的代價(jià)：預(yù)排序算法每遍歷一個(gè)特征值就需要計(jì)算一次分裂的增益，而直方圖算法只需要計(jì)算k次（k可以認(rèn)為是常數(shù)），時(shí)間復(fù)雜度從O(#data#feature)優(yōu)化到O(k#features)。(相當(dāng)于LightGBM犧牲了一部分切分的精確性來(lái)提高切分的效率，實(shí)際應(yīng)用中效果還不錯(cuò))
空間消耗大，需要保存數(shù)據(jù)的特征值以及特征排序的結(jié)果(比如排序后的索引，為了后續(xù)快速計(jì)算分割點(diǎn))，需要消耗兩倍于訓(xùn)練數(shù)據(jù)的內(nèi)存 時(shí)間上也有較大開(kāi)銷(xiāo)，遍歷每個(gè)分割點(diǎn)時(shí)都需要進(jìn)行分裂增益的計(jì)算，消耗代價(jià)大 對(duì)cache優(yōu)化不友好，在預(yù)排序后，特征對(duì)梯度的訪問(wèn)是一種隨機(jī)訪問(wèn)，并且不同的特征訪問(wèn)的順序不一樣，無(wú)法對(duì)cache進(jìn)行優(yōu)化。同時(shí)，在每一層長(zhǎng)樹(shù)的時(shí)候，需要隨機(jī)訪問(wèn)一個(gè)行索引到葉子索引的數(shù)組，并且不同特征訪問(wèn)的順序也不一樣，也會(huì)造成較大的cache miss。
XGBoost使用的是pre-sorted算法（對(duì)所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序，基本思想是對(duì)所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序；然后在遍歷分割點(diǎn)的時(shí)候用O(#data)的代價(jià)找到一個(gè)特征上的最好分割點(diǎn)最后，找到一個(gè)特征的分割點(diǎn)后，將數(shù)據(jù)分裂成左右子節(jié)點(diǎn)。優(yōu)點(diǎn)是能夠更精確的找到數(shù)據(jù)分隔點(diǎn)；但這種做法有以下缺點(diǎn) LightGBM使用的是histogram算法，基本思想是先把連續(xù)的浮點(diǎn)特征值離散化成k個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為k的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)；優(yōu)點(diǎn)在于
XGBoost采用的是帶深度限制的level-wise生長(zhǎng)策略，Level-wise過(guò)一次數(shù)據(jù)可以能夠同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，不容易過(guò)擬合；但不加區(qū)分的對(duì)待同一層的葉子，帶來(lái)了很多沒(méi)必要的開(kāi)銷(xiāo)（因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂） LightGBM采用leaf-wise生長(zhǎng)策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個(gè)葉子，然后分裂，如此循環(huán)；但會(huì)生長(zhǎng)出比較深的決策樹(shù)，產(chǎn)生過(guò)擬合（因此 LightGBM 在leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過(guò)擬合）。
histogram 做差加速。一個(gè)容易觀察到的現(xiàn)象：一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的k個(gè)桶。利用這個(gè)方法，LightGBM可以在構(gòu)造一個(gè)葉子的直方圖后，可以用非常微小的代價(jià)得到它兄弟葉子的直方圖，在速度上可以提升一倍。 直接支持類(lèi)別特征：LightGBM優(yōu)化了對(duì)類(lèi)別特征的支持，可以直接輸入類(lèi)別特征，不需要額外的0/1展開(kāi)。并在決策樹(shù)算法上增加了類(lèi)別特征的決策規(guī)則。 分布式訓(xùn)練方法上(并行優(yōu)化)
在特征并行算法中，通過(guò)在本地保存全部數(shù)據(jù)避免對(duì)數(shù)據(jù)切分結(jié)果的通信； 在數(shù)據(jù)并行中使用分散規(guī)約(Reduce scatter)把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算，并利用直方圖做差，進(jìn)一步減少了一半的通信量?；谕镀钡臄?shù)據(jù)并行(Parallel Voting)則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價(jià)，使通信代價(jià)變成常數(shù)級(jí)別。
LightGBM優(yōu)點(diǎn)小結(jié)(相較于XGBoost) |
