LightGBM原理及實(shí)現(xiàn)
LigthGBM是boosting集合模型中的新進(jìn)成員赖舟，它和xgboost一樣是對GBDT的高效實(shí)現(xiàn)捺信，很多方面會比xgboost表現(xiàn)的更為優(yōu)秀姿搜。原理上它和GBDT及xgboot類似，都采用損失函數(shù)的負(fù)梯度作為當(dāng)前決策樹的殘差近似值，去擬合新的決策樹囊榜。
LightGBM vs xGBoost
xgBoost算法的優(yōu)點(diǎn)：
- XGB利用了二階梯度來對節(jié)點(diǎn)進(jìn)行劃分，相對其他GBM來說亥宿，精度更高卸勺。
- 利用局部近似算法對分裂節(jié)點(diǎn)的貪心算法優(yōu)化，取適當(dāng)?shù)膃ps時烫扼，可以保持算法的性能且提高算法的運(yùn)算速度曙求。
- 在損失函數(shù)中加入了L1/L2項，控制模型的復(fù)雜度映企，提高模型的魯棒性圆到。
- 提供并行計算能力，主要是在樹節(jié)點(diǎn)求不同的候選的分裂點(diǎn)的Gain Infomation（分裂后卑吭，損失函數(shù)的差值）
- Tree Shrinkage芽淡，column subsampling等不同的處理細(xì)節(jié)。
xgBoost算法的缺點(diǎn)：
- 需要pre-sorted豆赏，這個會耗掉很多的內(nèi)存空間（2 * #data * # features）
- 數(shù)據(jù)分割點(diǎn)上挣菲，由于XGB對不同的數(shù)據(jù)特征使用pre-sorted算法而不同特征其排序順序是不同的富稻，所以分裂時需要對每個特征單獨(dú)做依次分割，遍歷次數(shù)為#data * #features來將數(shù)據(jù)分裂到左右子節(jié)點(diǎn)上白胀。
- 盡管使用了局部近似計算椭赋，但是處理粒度還是太細(xì)了
- 由于pre-sorted處理數(shù)據(jù)，在尋找特征分裂點(diǎn)時（level-wise）或杠，會產(chǎn)生大量的cache隨機(jī)訪問哪怔。
LightGBM的優(yōu)化點(diǎn)
1、基于Histogram（直方圖）的決策樹算法向抢，代替pre-sorted所構(gòu)建的數(shù)據(jù)結(jié)構(gòu)认境，利用histogram后，會有很多有用的tricks挟鸠。例如histogram做差叉信，提高了cache命中率（主要是因?yàn)槭褂昧?strong>帶深度限制的leaf-wise的葉子生長策略）。
2艘希、在機(jī)器學(xué)習(xí)當(dāng)中硼身，面對大數(shù)據(jù)量時候都會使用采樣的方式（根據(jù)樣本權(quán)值）來提高訓(xùn)練速度。又或者在訓(xùn)練的時候賦予樣本權(quán)值來關(guān)于于某一類樣本（如Adaboost）覆享。LightGBM利用了GOSS（基于梯度的one-side采樣） GOSS來做采樣算法佳遂。
3、由于histogram算法對稀疏數(shù)據(jù)的處理時間復(fù)雜度沒有pre-sorted好撒顿。因?yàn)閔istogram并不管特征值是否為0讶迁。因此采用EFB（互斥的特征捆綁）來預(yù)處理稀疏數(shù)據(jù)。
直方圖算法（Histogram）
直方圖算法是先把連續(xù)的浮點(diǎn)特征值離散化成k個整數(shù)核蘸，同時構(gòu)造一個寬度為k的直方圖巍糯。遍歷數(shù)據(jù)時，根據(jù)離散化后的值作為索引在直方圖中積累統(tǒng)計量客扎，當(dāng)遍歷一次數(shù)據(jù)后祟峦，直方圖積累了需要的統(tǒng)計量，然后根據(jù)直方圖的離散值徙鱼，遍歷尋找最優(yōu)的分割點(diǎn)宅楞。
- 直方圖只需對直方圖統(tǒng)計量計算信息增益，相比較于預(yù)排序算法每次都遍歷所有的值袱吆，信息增益的計算量要小很多厌衙。
- 相對于pre-sorted算法，它的內(nèi)存空間需要相對小很多绞绒。因?yàn)閜re-sorted算法需要保存起來每一個特征的排序結(jié)構(gòu)婶希，所以其需要的內(nèi)存大小是2 * #data * #feature * 4Bytes（起始我認(rèn)為保存排序后的數(shù)據(jù)可以用row_id來代替）而histogram只需保存離散值bin value（EFB會談到bin）而且我們不需要原始的feature value，所以占用的內(nèi)存大小為：#data * # feature * 1Byte蓬衡，因?yàn)殡x散值bin value使用uint8_t已經(jīng)足夠了喻杈。
- 求子節(jié)點(diǎn)相應(yīng)的feature histogram時彤枢，只需構(gòu)造一個子節(jié)點(diǎn)的feature histogram，另外一個子節(jié)點(diǎn)的feature histogram用父節(jié)點(diǎn)的histogram減去剛構(gòu)造出來的子節(jié)點(diǎn)的histogram便可筒饰，時間復(fù)雜度就壓縮到O(k)缴啡，k為histogram的桶數(shù)。這是一個很巧妙的做差法瓷们。
Gradient-based One-Side Sampling（GOSS）
GOSS是通過區(qū)分不同梯度的實(shí)例业栅，保留較大梯度實(shí)例同時對較小梯度隨機(jī)采樣的方式減少計算量，從而達(dá)到提升效率的目的谬晕。
這里有一個問題碘裕，為什么只對梯度小的樣本進(jìn)行采樣呢？
因?yàn)樵谔嵘龢溆?xùn)練過程中目標(biāo)函數(shù)學(xué)習(xí)的就是負(fù)梯度（近似殘差）固蚤，梯度小說明訓(xùn)練誤差已經(jīng)很小了，對這部分?jǐn)?shù)據(jù)的進(jìn)一步學(xué)習(xí)的效果不如對梯度大的樣本進(jìn)行學(xué)習(xí)的效果好或者說對梯度小的樣本進(jìn)行進(jìn)一步學(xué)習(xí)對改善結(jié)果精度幫助其實(shí)并不大歹茶。
GOSS的計算步驟如下：
- 選取前a%個較大梯度的值作為大梯度值的訓(xùn)練樣本
- 從剩余的1 - a%個較小梯度的值中夕玩，我們隨機(jī)選取其中的b%個作為小梯度值的訓(xùn)練樣本
- 對于較小梯度的樣本，也就是b% * (1 - 1%) * #samples惊豺，我們在計算信息增益時將其放大(1 - a) / b倍
總的來說就是a% * #samples + b% * (1 - a%) * #samples個樣本作為訓(xùn)練樣本燎孟。 而這樣的構(gòu)造是為了盡可能保持與總的數(shù)據(jù)分布一致，并且保證小梯度值的樣本得到訓(xùn)練尸昧。
Exclusive Feature Bundling（獨(dú)立特征合并）
EFB是通過特征捆綁的方式減少特征維度（其實(shí)是降維技術(shù)）的方式來提升計算效率揩页。通常被捆綁的特征都是互斥的（一個特征值為零一個特征值不為零），這樣兩個特征捆綁起來才不會丟失信息烹俗。如果兩個特征并不是完全互斥（部分情況下兩個特征都是非零值）爆侣，可以用一個指標(biāo)對特征不互斥程度進(jìn)行衡量，稱之為沖突比率幢妄，當(dāng)這個值較小時兔仰，可以選擇把不完全互斥的兩個特征捆綁，而不影響最后的精度蕉鸳。
這里就有兩個問題：1. 如何確定哪些特征用于融合且效果為較好乎赴。2. 如何將這些特征合并到一起。
1潮尝、問題1是一個NP-hard問題榕吼。把feature看作是圖中的點(diǎn)（V），feature之間的總沖突看作是圖中的邊（E）勉失。而尋找尋找合并特征且使得合并的bundles個數(shù)最小羹蚣，這是一個圖著色問題。所以這個找出合并的特征且使得bundles個數(shù)最小的問題需要使用近似的貪心算法來完成乱凿。
構(gòu)建一個以feature為圖中的點(diǎn)（V）度宦，以feature之間的總沖突為圖中的邊（E）這里說的沖突值應(yīng)該是feature之間cos夾角值踢匣，因?yàn)橐M可能保證feature之間非0元素不在同一個row上。首先按照度來對每個點(diǎn)（feature）做降序排序（度數(shù)越大與其他點(diǎn)的沖突越大）戈抄，然后將特征合并到?jīng)_突數(shù)小于K的bundle或者新建另外一個bundle离唬。算法的時間復(fù)雜度為O(#feature^2)。
2划鸽、第二問題是將這些bundles中的特征合并起來输莺。由于每一個bundle當(dāng)中，features的range都是不一樣裸诽，所以我們需要重新構(gòu)建合并后bundle feature的range缸废。在第一個for循環(huán)當(dāng)中，我們記錄每個feature與之前features累積totalRange单绑。在第二個for循環(huán)當(dāng)中币厕，根據(jù)之前的binRanges重新計算出新的bin value（F[j]bin[i] + binRanges[j]）保證feature之間的值不會沖突。這是針對于稀疏矩陣進(jìn)行優(yōu)化埂蕊。由于之前Greedy Bundling算法對features進(jìn)行沖突檢查確保bundle內(nèi)特征沖突盡可能少往弓，所以特征之間的非零元素不會有太多的沖突。
EBF的算法步驟如下：
- 將特征按照非零值的個數(shù)進(jìn)行排序
- 計算不同特征之間的沖突比率
- 遍歷每個特征并嘗試合并特征蓄氧，使沖突比率最小化
我們稱使用GOSS算法和EFB算法的梯度提升樹（GBDT）稱之為LightGBM函似。
Leaf-wise的決策樹生長策略
大部分決策樹的學(xué)習(xí)算法通過 level-wise 策略生長樹，記一次分裂同一層的葉子喉童，不加區(qū)分的對待同一層的葉子撇寞，而實(shí)際上很多葉子的分裂增益較低沒必要進(jìn)行分裂，帶來了沒必要的開銷堂氯。如下圖：
支持并行學(xué)習(xí)
LightGBM原生支持并行學(xué)習(xí)，目前支持特征并行(Featrue Parallelization)和數(shù)據(jù)并行(Data Parallelization)兩種咖祭，還有一種是基于投票的數(shù)據(jù)并行(Voting Parallelization)掩宜。
- 特征并行的主要思想是在不同機(jī)器、在不同的特征集合上分別尋找最優(yōu)的分割點(diǎn)么翰，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)牺汤。
- 數(shù)據(jù)并行則是讓不同的機(jī)器先在本地構(gòu)造直方圖，然后進(jìn)行全局的合并浩嫌，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)檐迟。
LightGBM針對這兩種并行方法都做了優(yōu)化。
- 特征并行算法中码耐，（1）每個Worker都在本地特征集上尋找最佳劃分點(diǎn)｛特征追迟， 閾值｝；（2）本地進(jìn)行各個劃分的通信整合并得到最佳劃分骚腥；（3）執(zhí)行最佳劃分敦间。
- 數(shù)據(jù)并行中使用分散規(guī)約 (Reduce scatter) 把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計算束铭，并利用直方圖做差廓块，進(jìn)一步減少了一半的通信量。
-
基于投票的數(shù)據(jù)并行(Voting Parallelization)則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價纯露，使通信代價變成常數(shù)級別剿骨。在數(shù)據(jù)量很大的時候代芜，使用投票并行可以得到非常好的加速效果埠褪。
在直方圖合并的時候，通信代價比較大挤庇，基于投票的數(shù)據(jù)并行能夠很好的解決這一點(diǎn)钞速。
Lightgbm基本原理介紹
LightGBM——提升機(jī)器算法（圖解+理論+安裝方法+python代碼）
LightGBM原理分析
機(jī)器學(xué)習(xí)——LightGBM
LightGBM，XGBoost
