LightGBM原理分析

LightGBM是Research Asia的一篇實(shí)用GBM的paper

1. Abstract

在之前我介紹過(guò)XGB模型，這次想跟大家分享一下LightGBM這個(gè)模型。LightGBM論文的標(biāo)題為A Highly Efficient Gradient Boosting Decision Tree。這說(shuō)明LightGBM它是對(duì)于XGB提升性能的版本。而LightGBM相對(duì)于其他GBM來(lái)說(shuō)具有相近的準(zhǔn)確率而且是其訓(xùn)練速度20倍。

2. Comparse with XGB

LightGBM主要的對(duì)比對(duì)象就是XGB，所以我們先說(shuō)一下XGB有什么優(yōu)缺點(diǎn)先。

優(yōu)點(diǎn) （詳情可以看看我之前的blog）

  • XGB利用了二階梯度來(lái)對(duì)節(jié)點(diǎn)進(jìn)行劃分，相對(duì)其他GBM來(lái)說(shuō)，精度更加高。
  • 利用局部近似算法對(duì)分裂節(jié)點(diǎn)的貪心算法優(yōu)化，取適當(dāng)?shù)膃ps時(shí)，可以保持算法的性能且提高算法的運(yùn)算速度。
  • 在損失函數(shù)中加入了L1/L2項(xiàng)，控制模型的復(fù)雜度，提高模型的魯棒性。
  • 提供并行計(jì)算能力，主要是在樹(shù)節(jié)點(diǎn)求不同的候選的分裂點(diǎn)的Gain Infomation（分裂后，損失函數(shù)的差值）
  • Tree Shrinkage，column subsampling等不同的處理細(xì)節(jié)。

缺點(diǎn)

  • 需要pre-sorted，這個(gè)會(huì)耗掉很多的內(nèi)存空間（2 * #data * # features）
  • 數(shù)據(jù)分割點(diǎn)上，由于XGB對(duì)不同的數(shù)據(jù)特征使用pre-sorted算法而不同特征其排序順序是不同的，所以分裂時(shí)需要對(duì)每個(gè)特征單獨(dú)做依次分割，遍歷次數(shù)為#data * #features來(lái)將數(shù)據(jù)分裂到左右子節(jié)點(diǎn)上。
  • 盡管使用了局部近似計(jì)算，但是處理粒度還是太細(xì)了
  • 由于pre-sorted處理數(shù)據(jù)，在尋找特征分裂點(diǎn)時(shí)（level-wise），會(huì)產(chǎn)生大量的cache隨機(jī)訪問(wèn)。

因此LightGBM針對(duì)這些缺點(diǎn)進(jìn)行了相應(yīng)的改進(jìn)。

  1. LightGBM基于histogram算法代替pre-sorted所構(gòu)建的數(shù)據(jù)結(jié)構(gòu)，利用histogram后，會(huì)有很多有用的tricks。例如histogram做差，提高了cache命中率（主要是因?yàn)槭褂昧薼eaf-wise）。
  2. 在機(jī)器學(xué)習(xí)當(dāng)中，我們面對(duì)大數(shù)據(jù)量時(shí)候都會(huì)使用采樣的方式（根據(jù)樣本權(quán)值）來(lái)提高訓(xùn)練速度。又或者在訓(xùn)練的時(shí)候賦予樣本權(quán)值來(lái)關(guān)于于某一類樣本（如Adaboost）。LightGBM利用了GOSS來(lái)做采樣算法。
  3. 由于histogram算法對(duì)稀疏數(shù)據(jù)的處理時(shí)間復(fù)雜度沒(méi)有pre-sorted好。因?yàn)閔istogram并不管特征值是否為0。因此我們采用了EFB來(lái)預(yù)處理稀疏數(shù)據(jù)。

下來(lái)我們針對(duì)這些改進(jìn)來(lái)說(shuō)明一下。

3. Histogram Algorithm（直方圖）

相對(duì)于pre-sorted算法，它的內(nèi)存空間需要相對(duì)小很多。因?yàn)閜re-sorted算法需要保存起來(lái)每一個(gè)特征的排序結(jié)構(gòu)，所以其需要的內(nèi)存大小是2 * #data * #feature * 4Bytes（起始我認(rèn)為保存排序后的數(shù)據(jù)可以用row_id來(lái)代替）而histogram只需保存離散值bin value（EFB會(huì)談到bin）而且我們不需要原始的feature value，所以占用的內(nèi)存大小為：#data * # feature * 1Byte，因?yàn)殡x散值bin value使用uint8_t已經(jīng)足夠了。另外對(duì)于求子節(jié)點(diǎn)相應(yīng)的feature histogram時(shí)，我們只需構(gòu)造一個(gè)子節(jié)點(diǎn)的feature histogram，另外一個(gè)子節(jié)點(diǎn)的feature histogram我們用父節(jié)點(diǎn)的histogram減去剛構(gòu)造出來(lái)的子節(jié)點(diǎn)的histogram便可，時(shí)間復(fù)雜度就壓縮到O(k)，k為histogram的桶數(shù)。這是一個(gè)很巧妙的做差法。

4. Gradient-based One-Side Sampling（GOSS）

其中文為梯度單邊采樣。大致的意思是根據(jù)樣本某一特征上的單梯度作為樣本的權(quán)值進(jìn)行訓(xùn)練。其采樣的方式有點(diǎn)巧妙：

  1. 選取前a%個(gè)較大梯度的值作為大梯度值的訓(xùn)練樣本
  2. 從剩余的1 - a%個(gè)較小梯度的值中，我們隨機(jī)選取其中的b%個(gè)作為小梯度值的訓(xùn)練樣本
  3. 對(duì)于較小梯度的樣本，也就是b% * (1 - 1%) * #samples，我們?cè)谟?jì)算信息增益時(shí)將其放大(1 - a) / b倍

總的來(lái)說(shuō)就是a% * #samples + b% * (1 - a%) * #samples個(gè)樣本作為訓(xùn)練樣本。 而這樣的構(gòu)造是為了盡可能保持與總的數(shù)據(jù)分布一致，并且保證小梯度值的樣本得到訓(xùn)練。

GOSS的算法流程

5. Exclusive Feature Bundling

EFB中文名叫獨(dú)立特征合并，顧名思義它就是將若干個(gè)特征合并在一起。使用這個(gè)算法的原因是因?yàn)槲覀円鉀Q數(shù)據(jù)稀疏的問(wèn)題。在很多時(shí)候，數(shù)據(jù)通常都是幾千萬(wàn)維的稀疏數(shù)據(jù)。因此我們對(duì)不同維度的數(shù)據(jù)合并一齊使得一個(gè)稀疏矩陣變成一個(gè)稠密矩陣。這里就有兩個(gè)問(wèn)題：1. 如何確定哪些特征用于融合且效果為較好。2. 如何將這些特征合并到一齊。

  1. 對(duì)于第一個(gè)問(wèn)題，這是一個(gè)NP-hard問(wèn)題。我們把feature看作是圖中的點(diǎn)（V），feature之間的總沖突看作是圖中的邊（E）。而尋找尋找合并特征且使得合并的bundles個(gè)數(shù)最小，這是一個(gè)圖著色問(wèn)題。所以這個(gè)找出合并的特征且使得bundles個(gè)數(shù)最小的問(wèn)題需要使用近似的貪心算法來(lái)完成。
    Greedy Bundling

    它將問(wèn)題一換成圖著色算法去解決。構(gòu)建一個(gè)以feature為圖中的點(diǎn)（V），以feature之間的總沖突為圖中的邊（E）這里說(shuō)的沖突值應(yīng)該是feature之間cos夾角值，因?yàn)槲覀兪潜M可能保證feature之間非0元素不在同一個(gè)row上。首先按照度來(lái)對(duì)每個(gè)點(diǎn)（feature）做降序排序（度數(shù)越大與其他點(diǎn)的沖突越大），然后將特征合并到?jīng)_突數(shù)小于K的bundle或者新建另外一個(gè)bundle。算法的時(shí)間復(fù)雜度為O(#feature^2)。

  2. 第二問(wèn)題是將這些bundles中的特征合并起來(lái)。


    Merge Exclusive Features

    由于每一個(gè)bundle當(dāng)中，features的range都是不一樣，所以我們需要重新構(gòu)建合并后bundle feature的range。在第一個(gè)for循環(huán)當(dāng)中，我們記錄每個(gè)feature與之前features累積totalRange。在第二個(gè)for循環(huán)當(dāng)中，根據(jù)之前的binRanges重新計(jì)算出新的bin value（F[j]bin[i] + binRanges[j]）保證feature之間的值不會(huì)沖突。這是針對(duì)于稀疏矩陣進(jìn)行優(yōu)化。由于之前Greedy Bundling算法對(duì)features進(jìn)行沖突檢查確保bundle內(nèi)特征沖突盡可能少，所以特征之間的非零元素不會(huì)有太多的沖突。

如此一來(lái)，數(shù)據(jù)的shape就變成了#samples * #bundles，且#bundles << #features。EFB降低了數(shù)據(jù)特征規(guī)模提高了模型的訓(xùn)練速度。

6 Leaf-wise (Best-first) Tree Growth

LightGBM對(duì)于樹(shù)的生長(zhǎng)使用的是Leaf-wise，而不是Level-wise。這樣的做法主要是因?yàn)長(zhǎng)ightGBM認(rèn)為L(zhǎng)evel-wise的做法會(huì)產(chǎn)生一些低信息增益的節(jié)點(diǎn)，浪費(fèi)運(yùn)算資源。其實(shí)通常來(lái)說(shuō)，Level-wise對(duì)于防止過(guò)擬合還是很有作用的，所以大家都比較青睞與它相比與Leaf-wise。作者認(rèn)為L(zhǎng)eaf-wise能夠追求更好的精度，讓產(chǎn)生更好精度的節(jié)點(diǎn)做分裂。但這樣帶來(lái)過(guò)擬合的問(wèn)題，所以作者使用的max_depth來(lái)控制它的最大高度。還有原因是因?yàn)長(zhǎng)ightGBM在做數(shù)據(jù)合并，Histogram Algorithm和GOSS等各個(gè)操作，其實(shí)都有天然正則化的作用，所以使用Leaf-wise來(lái)提高精度是一個(gè)很不錯(cuò)的選擇。


7. References

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容