本文主要簡要的比較了常用的boosting算法的一些區(qū)別挫剑，從AdaBoost到LightGBM,包括AdaBoost,GBDT,XGBoost,LightGBM四個模型的簡單介紹，一步一步從原理到優(yōu)化對比柱衔。
AdaBoost原理：原始的AdaBoost算法是在算法開始的時候樊破，為每一個樣本賦上一個權(quán)重值愉棱，初始的時候，大家都是一樣重要的哲戚。在每一步訓(xùn)練中得到的模型奔滑，會使得數(shù)據(jù)點的估計有對有錯，我們就在每一步結(jié)束后顺少，增加分錯的點的權(quán)重朋其，減少分對的點的權(quán)重，這樣使得某些點如果老是被分錯脆炎，那么就會被“重點關(guān)注”梅猿，也就被賦上一個很高的權(quán)重。然后等進(jìn)行了N次迭代（由用戶指定）秒裕，將會得到N個簡單的分類器（basiclearner）袱蚓，然后我們將它們組合起來（比如說可以對它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等）几蜻，得到一個最終的模型喇潘。
GBDT（Gradient Boosting Decison Tree）中的樹都是回歸樹，GBDT用來做回歸預(yù)測梭稚，調(diào)整后也可以用于分類（設(shè)定閾值响蓉，大于閾值為正例，反之為負(fù)例）哨毁，可以發(fā)現(xiàn)多種有區(qū)分性的特征以及特征組合枫甲。GBDT是把所有樹的結(jié)論累加起來做最終結(jié)論的，GBDT的核心就在于扼褪，每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差(負(fù)梯度)想幻，這個殘差就是一個加預(yù)測值后能得真實值的累加量。比如A的真實年齡是18歲话浇，但第一棵樹的預(yù)測年齡是12歲脏毯，差了6歲，即殘差為6歲幔崖。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)食店，如果第二棵樹真的能把A分到6歲的葉子節(jié)點，那累加兩棵樹的結(jié)論就是A的真實年齡赏寇；如果第二棵樹的結(jié)論是5歲吉嫩，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲嗅定，繼續(xù)學(xué)自娩。Boosting的最大好處在于，每一步的殘差計算其實變相地增大了分錯instance的權(quán)重渠退，而已經(jīng)分對的instance則都趨向于0忙迁。這樣后面的樹就能越來越專注那些前面被分錯的instance脐彩。
Gradient Boost每一次的計算是為了減少上一次的殘差(residual)，而為了消除殘差姊扔，我們可以在殘差減少的梯度(Gradient)方向上建立一個新的模型惠奸。所以說，在Gradient Boost中恰梢，每個新的模型的建立是為了使得之前模型的殘差往梯度方向減少晨川。Shrinkage（縮減）的思想認(rèn)為，每次走一小步逐漸逼近結(jié)果的效果删豺，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過擬合。即它不完全信任每一個棵殘差樹愧怜，它認(rèn)為每棵樹只學(xué)到了真理的一小部分呀页，累加的時候只累加一小部分，通過多學(xué)幾棵樹彌補(bǔ)不足拥坛。本質(zhì)上蓬蝶，Shrinkage為每棵樹設(shè)置了一個weight，累加時要乘以這個weight猜惋，但和Gradient并沒有關(guān)系丸氛。
Adaboost是另一種boost方法，它按分類對錯著摔，分配不同的weight缓窜，計算cost function時使用這些weight，從而讓“錯分的樣本權(quán)重越來越大谍咆，使它們更被重視”禾锤。
Gradient Boost優(yōu)缺點：
優(yōu)點： 它的非線性變換比較多，表達(dá)能力強(qiáng)摹察，而且不需要做復(fù)雜的特征工程和特征變換恩掷。
缺點:Boost是一個串行過程，不好并行化供嚎，而且計算復(fù)雜度高黄娘，同時不太適合高維稀疏特征。
XGBoost
XGBoost能自動利用cpu的多線程克滴，而且適當(dāng)改進(jìn)了gradient boosting逼争，加了剪枝，控制了模型的復(fù)雜程度
傳統(tǒng)GBDT以CART作為基分類器劝赔，特指梯度提升決策樹算法氮凝，而XGBoost還支持線性分類器(gblinear)，這個時候XGBoost相當(dāng)于帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）望忆。
傳統(tǒng)GBDT在優(yōu)化時只用到一階導(dǎo)數(shù)信息罩阵，xgboost則對代價函數(shù)進(jìn)行了二階泰勒展開竿秆，同時用到了一階和二階導(dǎo)數(shù)。順便提一下稿壁，xgboost工具支持自定義代價函數(shù)幽钢，只要函數(shù)可一階和二階求導(dǎo)。
xgboost在代價函數(shù)里加入了正則項傅是，用于控制模型的復(fù)雜度匪燕。正則項里包含了樹的葉子節(jié)點個數(shù)、每個葉子節(jié)點上輸出的score的L2模的平方和喧笔。從Bias-variance
tradeoff角度來講帽驯，正則項降低了模型的variance，使學(xué)習(xí)出來的模型更加簡單书闸，防止過擬合尼变，這也是xgboost優(yōu)于傳統(tǒng)GBDT的一個特性。
xgboost中樹節(jié)點分裂時所采用的公式：
Shrinkage（縮減）浆劲，相當(dāng)于學(xué)習(xí)速率（xgboost中的eta）嫌术。xgboost在進(jìn)行完一次迭代后，會將葉子節(jié)點的權(quán)重乘上該系數(shù)牌借，主要是為了削弱每棵樹的影響度气，讓后面有更大的學(xué)習(xí)空間。實際應(yīng)用中膨报，一般把eta設(shè)置得小一點磷籍，然后迭代次數(shù)設(shè)置得大一點。（傳統(tǒng)GBDT的實現(xiàn)也有學(xué)習(xí)速率）
列抽樣（column subsampling）现柠。xgboost借鑒了隨機(jī)森林的做法择示，支持列抽樣，不僅能降低過擬合晒旅，還能減少計算栅盲，這也是xgboost異于傳統(tǒng)gbdt的一個特性。
對缺失值的處理废恋。對于特征的值有缺失的樣本谈秫，xgboost可以自動學(xué)習(xí)出它的分裂方向。
xgboost工具支持并行鱼鼓。注意xgboost的并行不是tree粒度的并行拟烫，xgboost也是一次迭代完才能進(jìn)行下一次迭代的（第t次迭代的代價函數(shù)里包含了前面t-1次迭代的預(yù)測值）。xgboost的并行是在特征粒度上的迄本。我們知道硕淑，決策樹的學(xué)習(xí)最耗時的一個步驟就是對特征的值進(jìn)行排序（因為要確定最佳分割點），xgboost在訓(xùn)練之前，預(yù)先對數(shù)據(jù)進(jìn)行了排序置媳，然后保存為block結(jié)構(gòu)于樟，后面的迭代中重復(fù)地使用這個結(jié)構(gòu)，大大減小計算量拇囊。這個block結(jié)構(gòu)也使得并行成為了可能迂曲，在進(jìn)行節(jié)點的分裂時，需要計算每個特征的增益寥袭，最終選增益最大的那個特征去做分裂路捧，那么各個特征的增益計算就可以開多線程進(jìn)行。(特征粒度上的并行传黄，block結(jié)構(gòu)杰扫，預(yù)排序)。
這個公式形式上跟ID3算法膘掰、CART算法是一致的章姓，都是用分裂后的某種值減去分裂前的某種值，從而得到增益炭序。為了限制樹的生長，我們可以加入閾值苍日，當(dāng)增益大于閾值時才讓節(jié)點分裂惭聂，上式中的gamma即閾值，它是正則項里葉子節(jié)點數(shù)T的系數(shù)相恃，所以xgboost在優(yōu)化目標(biāo)函數(shù)的同時相當(dāng)于做了預(yù)剪枝辜纲。另外，上式中還有一個系數(shù)lambda拦耐，是正則項里leafscore的L2模平方的系數(shù)耕腾，對leaf score做了平滑，也起到了防止過擬合的作用杀糯，這個是傳統(tǒng)GBDT里不具備的特性扫俺。
XGBoost優(yōu)勢小結(jié)：
（1）內(nèi)置交叉驗證方法
（2）能夠輸出特征重要性文件輔助特征篩選
（3）顯式地將樹模型的復(fù)雜度作為正則項加在優(yōu)化目標(biāo)
（4）公式推導(dǎo)里用到了二階導(dǎo)數(shù)信息，而普通的GBDT只用到一階
（5）允許使用列抽樣(column(feature) sampling)來防止過擬合固翰，借鑒了Random Forest的思想狼纬，sklearn里的gbm好像也有類似實現(xiàn)。
（6）實現(xiàn)了一種分裂節(jié)點尋找的近似算法骂际，用于加速和減小內(nèi)存消耗疗琉。
（7）節(jié)點分裂算法能自動利用特征的稀疏性。
（8）樣本數(shù)據(jù)事先排好序并以block的形式存儲歉铝，利于并行計算
（9）penalty function Omega主要是對樹的葉子數(shù)和葉子分?jǐn)?shù)做懲罰盈简，這點確保了樹的簡單性。
（10）支持分布式計算可以運行在MPI，YARN上柠贤，得益于底層支持容錯的分布式通信框架rabit香浩。
lightGBM：基于決策樹算法的分布式梯度提升框架。
與xgboost的主要區(qū)別：
切分算法(切分點的選取) 占用的內(nèi)存更低种吸，只保存特征離散化后的值弃衍，而這個值一般用8位整型存儲就足夠了，內(nèi)存消耗可以降低為原來的1/8坚俗。
降低了計算的代價：預(yù)排序算法每遍歷一個特征值就需要計算一次分裂的增益镜盯，而直方圖算法只需要計算k次（k可以認(rèn)為是常數(shù)），時間復(fù)雜度從O(#data#feature)優(yōu)化到O(k#features)猖败。(相當(dāng)于LightGBM犧牲了一部分切分的精確性來提高切分的效率速缆，實際應(yīng)用中效果還不錯)
空間消耗大，需要保存數(shù)據(jù)的特征值以及特征排序的結(jié)果(比如排序后的索引恩闻，為了后續(xù)快速計算分割點)艺糜，需要消耗兩倍于訓(xùn)練數(shù)據(jù)的內(nèi)存
時間上也有較大開銷，遍歷每個分割點時都需要進(jìn)行分裂增益的計算幢尚，消耗代價大
對cache優(yōu)化不友好破停，在預(yù)排序后，特征對梯度的訪問是一種隨機(jī)訪問尉剩，并且不同的特征訪問的順序不一樣真慢，無法對cache進(jìn)行優(yōu)化。同時理茎，在每一層長樹的時候黑界，需要隨機(jī)訪問一個行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣皂林，也會造成較大的cache
miss朗鸠。
XGBoost使用的是pre-sorted算法（對所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序，基本思想是對所有特征都按照特征的數(shù)值進(jìn)行預(yù)排序础倍；然后在遍歷分割點的時候用O(#data)的代價找到一個特征上的最好分割點最后烛占，找到一個特征的分割點后，將數(shù)據(jù)分裂成左右子節(jié)點沟启。優(yōu)點是能夠更精確的找到數(shù)據(jù)分隔點扰楼；但這種做法有以下缺點
LightGBM使用的是histogram算法，基本思想是先把連續(xù)的浮點特征值離散化成k個整數(shù)美浦，同時構(gòu)造一個寬度為k的直方圖弦赖。在遍歷數(shù)據(jù)的時候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計量浦辨，當(dāng)遍歷一次數(shù)據(jù)后蹬竖，直方圖累積了需要的統(tǒng)計量沼沈，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點币厕；優(yōu)點在于
決策樹生長策略上：
XGBoost采用的是帶深度限制的level-wise生長策略列另，Level-wise過一次數(shù)據(jù)可以能夠同時分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化旦装，不容易過擬合页衙；但不加區(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷（因為實際上很多葉子的分裂增益較低阴绢，沒必要進(jìn)行搜索和分裂）店乐。
LightGBM采用leaf-wise生長策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個葉子呻袭，然后分裂眨八，如此循環(huán)；但會生長出比較深的決策樹左电，產(chǎn)生過擬合（因此LightGBM 在leaf-wise之上增加了一個最大深度的限制廉侧，在保證高效率的同時防止過擬合）。
histogram做差加速篓足。一個容易觀察到的現(xiàn)象：一個葉子的直方圖可以由它的父親節(jié)點的直方圖與它兄弟的直方圖做差得到段誊。通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)栈拖，但直方圖做差僅需遍歷直方圖的k個桶连舍。利用這個方法，LightGBM可以在構(gòu)造一個葉子的直方圖后辱魁，可以用非常微小的代價得到它兄弟葉子的直方圖烟瞧，在速度上可以提升一倍诗鸭。
直接支持類別特征：LightGBM優(yōu)化了對類別特征的支持染簇，可以直接輸入類別特征，不需要額外的0/1展開强岸。并在決策樹算法上增加了類別特征的決策規(guī)則锻弓。
分布式訓(xùn)練方法上(并行優(yōu)化)
在特征并行算法中，通過在本地保存全部數(shù)據(jù)避免對數(shù)據(jù)切分結(jié)果的通信蝌箍；
在數(shù)據(jù)并行中使用分散規(guī)約(Reduce
scatter)把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器青灼，降低通信和計算，并利用直方圖做差妓盲，進(jìn)一步減少了一半的通信量杂拨。基于投票的數(shù)據(jù)并行(Parallel
Voting)則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價悯衬，使通信代價變成常數(shù)級別弹沽。
特征并行的主要思想是在不同機(jī)器在不同的特征集合上分別尋找最優(yōu)的分割點，然后在機(jī)器間同步最優(yōu)的分割點。
數(shù)據(jù)并行則是讓不同的機(jī)器先在本地構(gòu)造直方圖策橘，然后進(jìn)行全局的合并炸渡，最后在合并的直方圖上面尋找最優(yōu)分割點。
原始
LightGBM針對這兩種并行方法都做了優(yōu)化丽已，
Cache命中率優(yōu)化
基于直方圖的稀疏特征優(yōu)化
DART(Dropout + GBDT)
GOSS(Gradient-based
One-Side Sampling):一種新的Bagging(row subsample)方法,前若干輪(1.0f /
gbdtconfig->learning_rate)不Bagging;之后Bagging時, 采樣一定比例g(梯度)大的樣本
LightGBM優(yōu)點小結(jié)(相較于XGBoost)
速度更快
內(nèi)存消耗更低
參考博文：點擊進(jìn)入
