Lightgbm源论文解析：LightGBM: A Highly Efficient Gradient Boosting Decision Tree
寫這篇博客的原因是，網(wǎng)上很多關(guān)于Lightgbm的講解都是從Lightgbm的官方文檔來的，官方文檔只會(huì)告訴你怎么用，很多細(xì)節(jié)都沒講。所以自己翻過來Lightgbm的源論文：LightGBM: A Highly Efficient Gradient Boosting Decision Tree仔細(xì)看了幾遍，現(xiàn)在整理一下源論文，加深自己對Lightgbm技術(shù)細(xì)節(jié)的認(rèn)識(shí)和思考。
首先感謝網(wǎng)友立刻有的博客，省去了我很多翻譯的工作。我更改了他博客的部分不當(dāng)（翻譯或者公式）的地方，又加入了自己的一些思考。
Abstract
Gradient Boosting Decision Tree (GBDT)非常流行卻鮮有實(shí)現(xiàn)，只有像XGBoost和pGBRT實(shí)現(xiàn)。當(dāng)特征維度較高和數(shù)據(jù)量巨大的時(shí)候，仍然存在效率和可擴(kuò)展性的問題。一個(gè)主要原因就是對于每一個(gè)特征的每一個(gè)分裂點(diǎn)，都需要遍歷全部數(shù)據(jù)計(jì)算信息增益，這一過程非常耗時(shí)。針對這一問題，本文提出兩種新方法：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度的one-side采樣和互斥的特征捆綁）。在GOSS中，我們排除了重要的比例-具有小梯度的實(shí)例，只用剩下的來估計(jì)信息增益，我們證明，這些梯度大的實(shí)例在計(jì)算信息增益中扮演重要角色，GOSS可以用更小的數(shù)據(jù)量對信息增益進(jìn)行相當(dāng)準(zhǔn)確的估計(jì)。對于EFB，我們捆綁互斥的特征（例如，特征間很少同時(shí)非零的特征），來降低特征的個(gè)數(shù)。我們完美地證明了捆綁互斥特征是NP難的，但貪心算法能夠?qū)崿F(xiàn)相當(dāng)好的逼近率，因此我們能夠在不損害分割點(diǎn)準(zhǔn)確率許多的情況下，有效減少特征的數(shù)量。（犧牲一點(diǎn)分割準(zhǔn)確率降低特征數(shù)量），這一算法命名為LightGBM。在多個(gè)公共數(shù)據(jù)集實(shí)驗(yàn)證明，LightGBM加速了傳統(tǒng)GBDT訓(xùn)練過程20倍以上，同時(shí)達(dá)到了幾乎相同的精度。
?
1. Introduction
GBDT因?yàn)槠浔旧淼挠行浴?zhǔn)確性、可解釋性，成為了廣泛使用的機(jī)器學(xué)習(xí)算法。GBDT在許多機(jī)器學(xué)習(xí)任務(wù)上均取得了最好的效果，例如多分類，點(diǎn)擊預(yù)測，排序。但最近幾年隨著大數(shù)據(jù)的爆發(fā)（特征量和數(shù)據(jù)量），GBDT面臨平衡準(zhǔn)確率和效率的調(diào)整。
GBDT缺點(diǎn)：對于每一個(gè)特征的每一個(gè)分裂點(diǎn)，都需要遍歷全部數(shù)據(jù)來計(jì)算信息增益。因此，其計(jì)算復(fù)雜度將受到特征數(shù)量和數(shù)據(jù)量雙重影響，造成處理大數(shù)據(jù)時(shí)十分耗時(shí)。
解決這個(gè)問題的直接方法就是減少特征量和數(shù)據(jù)量而且不影響精確度，有部分工作根據(jù)數(shù)據(jù)權(quán)重采樣來加速boosting的過程，但由于gbdt沒有樣本權(quán)重而不能應(yīng)用。而本文提出兩種新方法實(shí)現(xiàn)此目標(biāo)。
Gradient-based One-Side Sampling (GOSS)：GBDT雖然沒有數(shù)據(jù)權(quán)重，但每個(gè)數(shù)據(jù)實(shí)例有不同的梯度，根據(jù)計(jì)算信息增益的定義，梯度大的實(shí)例對信息增益有更大的影響，因此在下采樣時(shí)，我們應(yīng)該盡量保留梯度大的樣本（預(yù)先設(shè)定閾值，或者最高百分位間），隨機(jī)去掉梯度小的樣本。我們證明此措施在相同的采樣率下比隨機(jī)采樣獲得更準(zhǔn)確的結(jié)果，尤其是在信息增益范圍較大時(shí)。
Exclusive Feature Bundling (EFB)：通常在真實(shí)應(yīng)用中，雖然特征量比較多，但是由于特征空間十分稀疏，是否可以設(shè)計(jì)一種無損的方法來減少有效特征呢？特別在稀疏特征空間上，許多特征幾乎是互斥的（例如許多特征不會(huì)同時(shí)為非零值，像one-hot），我們可以捆綁互斥的特征。最后，我們將捆綁問題歸約到圖著色問題，通過貪心算法求得近似解。
?
2. Preliminaries
2.1 GBDT and Its Complexity Analysis
GBDT是一種集成模型的決策樹，順序訓(xùn)練決策樹。每次迭代中，GBDT通過擬合負(fù)梯度（殘差）來學(xué)到?jīng)Q策樹。
學(xué)習(xí)決策樹是GBDT主要的時(shí)間花銷，而學(xué)習(xí)決策樹中找到最優(yōu)切分點(diǎn)最消耗時(shí)間。廣泛采用的預(yù)排序算法來找到最優(yōu)切分點(diǎn)，這種方法會(huì)列舉預(yù)排序中所有可能的切分點(diǎn)。這種算法雖然能夠找到最優(yōu)的切分點(diǎn)，但對于訓(xùn)練速度和內(nèi)存消耗上都效率低。另一種流行算法是直方圖算法（histogram-based algorithm）。直方圖算法并不通過特征排序找到最優(yōu)的切分點(diǎn)，而是將連續(xù)的特征值抽象成離散的分箱，并使用這些分箱在訓(xùn)練過程中構(gòu)建特征直方圖，這種算法更加訓(xùn)練速度和內(nèi)存消耗上都更加高效，lightGBM使用此種算法。
histogram-based算法通過直方圖尋找最優(yōu)切分點(diǎn)，其建直方圖消耗O(#data * #feature)，尋找最優(yōu)切分點(diǎn)消耗O(#bin * # feature)，而#bin的數(shù)量遠(yuǎn)小于#data，所以建直方圖為主要時(shí)間消耗。如果能夠減少數(shù)據(jù)量或特征量，那么還能夠夠加速GBDT的訓(xùn)練。（尋找最優(yōu)切分點(diǎn)已經(jīng)進(jìn)行了優(yōu)化，那么我們現(xiàn)在應(yīng)該對建直方圖的時(shí)間進(jìn)行優(yōu)化）
2.2 Related Work
GBDT有許多實(shí)現(xiàn)，如XGBoost，PGBRT，Scikit-learn，gbm in R。Scikit-learn和gbm in R實(shí)現(xiàn)都用了預(yù)排序，pGBRT使用了直方圖算法，XGBoost支持預(yù)排序和直方圖算法，由于XGBoost勝過其他算法，我們用它作為baseline。
為了減小訓(xùn)練數(shù)據(jù)集，通常做法是下采樣。例如過濾掉權(quán)重小于閾值的數(shù)據(jù)。SGB每次迭代中用隨機(jī)子集訓(xùn)練弱學(xué)習(xí)器。或者采樣率基于訓(xùn)練過程動(dòng)態(tài)調(diào)整。基于AdaBoost的SGB不能直接應(yīng)用于GBDT，因?yàn)镚BDT中沒有原始的權(quán)重。雖然SGB也能間接應(yīng)用于GBDT，但往往會(huì)影響精度。
同樣，可以考慮過濾掉弱特征（什么是弱特征）來減少特征量。通常用主成分分析或者投影法。當(dāng)然，這些方法依賴于一個(gè)假設(shè)-特征有高冗余性，但實(shí)際中往往不是。（設(shè)計(jì)特征來自于其獨(dú)特的貢獻(xiàn)，移除任何一維度都可以某種程度上影響精度）。
實(shí)際中大規(guī)模的數(shù)據(jù)集通常都是非常稀疏的，使用預(yù)排序算法的GBDT能夠通過無視為0的特征來降低訓(xùn)練時(shí)間消耗。然而直方圖算法沒有優(yōu)化稀疏的方案。因?yàn)橹狈綀D算法無論特征值是否為0，都需要為每個(gè)數(shù)據(jù)檢索特征區(qū)間值。如果基于直方圖的GBDT能夠有效解決稀疏特征中的0值，那么這樣將會(huì)有很好的性能。
下圖為直方圖算法的流程：
3. Gradient-based One-Side Sampling
GOSS是一種在減少數(shù)據(jù)量和保證精度上平衡的算法。
3.1 Algorithm Description
AdaBoost中，樣本權(quán)重是數(shù)據(jù)實(shí)例重要性的指標(biāo)。然而在GBDT中沒有原始樣本權(quán)重，不能應(yīng)用權(quán)重采樣。幸運(yùn)的事，我們觀察到GBDT中每個(gè)數(shù)據(jù)都有不同的梯度值，對采樣十分有用，即實(shí)例的梯度小，實(shí)例訓(xùn)練誤差也就較小，已經(jīng)被學(xué)習(xí)得很好了，直接想法就是丟掉這部分梯度小的數(shù)據(jù)。然而這樣做會(huì)改變數(shù)據(jù)的分布，將會(huì)影響訓(xùn)練的模型的精確度，為了避免此問題，我們提出了GOSS。
GOSS保留所有的梯度較大的實(shí)例，在梯度小的實(shí)例上使用隨機(jī)采樣。為了抵消對數(shù)據(jù)分布的影響，計(jì)算信息增益的時(shí)候，GOSS對小梯度的數(shù)據(jù)引入常量乘數(shù)。GOSS首先根據(jù)數(shù)據(jù)的梯度絕對值排序，選取top a個(gè)實(shí)例。然后在剩余的數(shù)據(jù)中隨機(jī)采樣b個(gè)實(shí)例。接著計(jì)算信息增益時(shí)為采樣出的小梯度數(shù)據(jù)乘以(1-a)/b（即，小梯度樣本總數(shù)/隨機(jī)采樣出的小梯度樣本數(shù)量），這樣算法就會(huì)更關(guān)注訓(xùn)練不足的實(shí)例，而不會(huì)過多改變原數(shù)據(jù)集的分布。
GOSS的算法流程如下：
3.2 Theoretical Analysis
GBDT使用決策樹，來學(xué)習(xí)獲得一個(gè)將輸入空間映射到梯度空間的函數(shù)。假設(shè)訓(xùn)練集有n個(gè)實(shí)例 ，特征維度為s。每次迭代時(shí)，模型數(shù)據(jù)變量的損失函數(shù)的負(fù)梯度方向表示為，決策樹通過最優(yōu)切分點(diǎn)（最大信息增益點(diǎn)）將數(shù)據(jù)分到各個(gè)節(jié)點(diǎn)。GBDT通過分割后的方差衡量信息增益
定義3.1：O表示某個(gè)固定葉子節(jié)點(diǎn)的訓(xùn)練集，分割特征j的分割點(diǎn)d定義為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
其中，(某個(gè)固定葉子節(jié)點(diǎn)的訓(xùn)練集樣本的個(gè)數(shù))，(在第j個(gè)特征上值小于等于d的樣本個(gè)數(shù))，(在第j個(gè)特征上值大于d的樣本個(gè)數(shù))。
遍歷每個(gè)特征的每個(gè)分裂點(diǎn)，找到 并計(jì)算最大的信息增益，然后，將數(shù)據(jù)根據(jù)特征的分裂點(diǎn)?將數(shù)據(jù)分到左右子節(jié)點(diǎn)。
在GOSS中，
首先根據(jù)數(shù)據(jù)的梯度進(jìn)行降序排序。
保留top %a個(gè)數(shù)據(jù)實(shí)例，作為數(shù)據(jù)子集A。
對于剩下的數(shù)據(jù)的實(shí)例集合，隨機(jī)采樣獲得大小為的數(shù)據(jù)子集B。
最后我們在集合上，通過以下方程估計(jì)信息增益:
? ? ? ? ? ? ? ? ?
此處GOSS通過較小的數(shù)據(jù)集估計(jì)信息增益 ，將大大地減小計(jì)算量。更重要的是，我們接下來理論表明GOSS不會(huì)丟失許多訓(xùn)練精度，且勝過隨機(jī)采樣，理論的證明在附加材料(參考文獻(xiàn)【2】)。
Theorem 3.2：我們定義GOSS近似誤差為，，，概率至少是，有：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
其中。
根據(jù)理論3.2，我們得出以下結(jié)論：
GOSS的漸近近似比率?。如果數(shù)據(jù)分割不是極不平衡（也就是 且），那么定理3.2中近似誤差將由第二項(xiàng)主導(dǎo)，且在第二項(xiàng)中，當(dāng)n趨于無窮（數(shù)據(jù)量很大）時(shí)將趨于0，即數(shù)據(jù)量越大，誤差越小，精度越高。
隨機(jī)采樣是GOSS在a=0的一種情況。多數(shù)情況下，GOSS性能優(yōu)于隨機(jī)采樣，即以下情況：(C代表誤差，即隨機(jī)抽比例的誤差大于先抽top a%比例再抽比例的誤差)，等價(jià)于，其中。
（其實(shí)這里，，代入，就可以得到等價(jià)的不等式）
下面分析GOSS的泛化性。考慮GOSS泛化誤差，這是GOSS抽樣的的實(shí)例計(jì)算出的方差增益與實(shí)際樣本方差增益之間的差距。變換為，，因此，在GOSS準(zhǔn)確的情況下，GOSS泛化誤差近似于全量的真實(shí)數(shù)據(jù)。另一方面，采樣將增加基學(xué)習(xí)器的多樣性（因?yàn)槊看尾蓸荧@得的數(shù)據(jù)可能會(huì)不同），這將提高泛化性。
4 Exclusive Feature Bundling
這一章介紹如何有效減少特征的數(shù)量。
高維的數(shù)據(jù)通常是稀疏的，這種稀疏性啟發(fā)我們可以設(shè)計(jì)一種無損地方法來減少特征的維度。特別地，在稀疏特征空間中，許多特征是互斥的，即它們從不同時(shí)為非零值。我們可以綁定互斥的特征為單一特征，通過仔細(xì)設(shè)計(jì)特征掃描算法，我們從特征捆綁中構(gòu)建了與單個(gè)特征相同的特征直方圖。這種方式的構(gòu)建直方圖時(shí)間復(fù)雜度從O(#data * #feature)降到O(#data * #bundle)，由于#bundle << # feature，我們能夠極大地加速GBDT的訓(xùn)練過程而且不損失精度。(構(gòu)造直方圖的時(shí)候，遍歷一個(gè)“捆綁的大特征”可以得到一組exclusive feature的直方圖。這樣只需要遍歷這些“大特征”就可以獲取到所有特征的直方圖，降低了需要遍歷的特征量。)
有兩個(gè)問題：
怎么判定哪些特征應(yīng)該綁在一起（build bundled）？
怎么把特征綁為一個(gè)（merge feature）？
4.1 bundle（什么樣的特征被綁定）？
理論 4.1：將特征分割為較小量的互斥特征群是NP難的。
證明：將圖著色問題歸約為此問題，而圖著色是NP難的，所以此問題就是NP難的。
給定圖著色實(shí)例G=(V, E)。以G的關(guān)聯(lián)矩陣的每一行為特征，得到我們問題的一個(gè)實(shí)例有|V|個(gè)特征。 很容易看到，在我們的問題中，一個(gè)獨(dú)特的特征捆綁包與一組具有相同顏色的頂點(diǎn)相對應(yīng)，反之亦然。
對于第1個(gè)問題，理論4.1說明在多項(xiàng)式時(shí)間中求解這個(gè)NP難問題是不可行的。為了尋找好的近似算法，我們將最優(yōu)捆綁問題歸結(jié)為圖著色問題，如果兩個(gè)特征之間不是相互排斥，那么我們用一個(gè)邊將他們連接，然后用合理的貪婪算法（具有恒定的近似比）用于圖著色來做特征捆綁。 此外，我們注意到通常有很多特征，盡管不是100％相互排斥的，也很少同時(shí)取非零值。 如果我們的算法可以允許一小部分的沖突，我們可以得到更少的特征包，進(jìn)一步提高計(jì)算效率。經(jīng)過簡單的計(jì)算，隨機(jī)污染小部分特征值將影響精度最多(參考文獻(xiàn)【2】)， 是每個(gè)綁定中的最大沖突比率，當(dāng)其相對較小時(shí)，能夠完成精度和效率之間的平衡。
基于上面的討論，我們設(shè)計(jì)了算法3，偽代碼見下圖，具體算法：
算法3的時(shí)間復(fù)雜度是，訓(xùn)練之前只處理一次，其時(shí)間復(fù)雜度在特征不是特別多的情況下是可以接受的，但難以應(yīng)對百萬維的特征。為了繼續(xù)提高效率，我們提出了一個(gè)更加高效的不用構(gòu)建圖的排序策略：將特征按照非零值個(gè)數(shù)排序，這和使用圖節(jié)點(diǎn)的度排序相似，因?yàn)楦嗟姆橇阒低ǔ?huì)導(dǎo)致沖突。新算法在算法3基礎(chǔ)上只是改變了排序策略。
4.2 merging features(特征合并)
對于第2個(gè)問題，如何合并同一個(gè)bundle的特征來降低訓(xùn)練時(shí)間復(fù)雜度。關(guān)鍵在于原始特征值可以從bundle中區(qū)分出來。鑒于直方圖算法存儲(chǔ)離散值而不是連續(xù)特征值，我們通過將互斥特征放在不同的箱中來構(gòu)建bundle。這可以通過將偏移量添加到特征原始值中實(shí)現(xiàn)，例如，假設(shè)bundle中有兩個(gè)特征，原始特征A取值[0, 10]，B取值[0, 20]。我們添加偏移量10到B中，因此B取值[10, 30]。通過這種做法，就可以安全地將A、B特征合并，使用一個(gè)取值[0, 30]的特征取代A和B。算法見算法4，算法流程如下：
EFB算法能夠?qū)⒃S多互斥的特征變?yōu)榈途S稠密的特征，就能夠有效的避免不必要0值特征的計(jì)算。實(shí)際，對每一個(gè)特征，建立一個(gè)記錄數(shù)據(jù)中的非零值的表，通過用這個(gè)表，來忽略零值特征，達(dá)到優(yōu)化基礎(chǔ)的直方圖算法的目的。通過掃描表中的數(shù)據(jù)，建直方圖的時(shí)間復(fù)雜度將從O(#data)降到O(#non_zero_data)。當(dāng)然，這種方法在構(gòu)建樹過程中需要而額外的內(nèi)存和計(jì)算開銷來維持這種表。我們在lightGBM中將此優(yōu)化作為基本函數(shù)，因?yàn)楫?dāng)bundles是稀疏的時(shí)候，這個(gè)優(yōu)化與EFB不沖突（可以用于EFB）
5?Experiments
實(shí)驗(yàn)部分，比較簡單。主要用了五個(gè)公開數(shù)據(jù)集，且這些數(shù)據(jù)集都比較大，而且包含了稀疏和稠密的特征，涵蓋了很多真實(shí)的業(yè)務(wù)，因此它們能夠完全地測試lightGBM的性能。
經(jīng)過與XGBoost，lightgbm without GOSS and EFB和SGB的對比，證明了LightGBM在計(jì)算速度和內(nèi)存消耗上明顯優(yōu)于XGBoost和SGB，且不損失準(zhǔn)確率。
這部分詳細(xì)內(nèi)容可以看參考文獻(xiàn)1和2.
6 Conclusion
本文提出了新穎的GBDT算法–LightGBM，它包含了2個(gè)新穎的技術(shù)：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度的one-side采樣和互斥的特征捆綁）來處理大數(shù)據(jù)量和高維特征的場景。我們在理論分析和實(shí)驗(yàn)研究表明，GOSS和EFB使得LightGBM在計(jì)算速度和內(nèi)存消耗上明顯優(yōu)于XGBoost和SGB。
未來，我們將研究優(yōu)化如何在GOSS中選擇a，b。繼續(xù)提高EFB在高維特征上的性能，無論其是否是稀疏的。
?
參考文獻(xiàn)
【1】https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf
【2】https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree
【3】https://blog.csdn.net/shine19930820/article/details/79123216
總結(jié)
以上是生活随笔為你收集整理的Lightgbm源论文解析：LightGBM: A Highly Efficient Gradient Boosting Decision Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 信贷种类
- 下一篇： 基于Python对Lending Clu