1、概述
LightGBM是微軟于2017年提出的boosting框架，其基本原理與XGBoost一樣，使用基于學習算法的決策樹，只是在框架上做了一優(yōu)化（重點在模型的訓練速度的優(yōu)化）。我在參加 Kaggle 比賽的過程中發(fā)現，除了 XGBoost，表現較好的且使用較為廣泛的 GBM 模型就是 LightGBM 。因此我認為大概了解背后的原理是必要的。
在論文摘要中作者提到，GBDT 是一種非常流行的機器學習算法，有很多有效的實現，雖然在這些實現中采用了許多工程優(yōu)化方法，但在特征維數高、數據量大的情況下，其效率和可擴展性仍不能令人滿意。一個主要的原因是，對于每個特征，需要掃描所有的數據實例來估計所有可能的分割點的信息增益，這是非常耗時的。
為了解決這個問題，作者提出了兩種新的技術：
- 1、GOSS(Gradient based One Side Sampling)：移除梯度較小的數據實例，只使用其余的數據估計信息增益。由于梯度較大的數據實例在信息增益的計算中起著更重要的作用，所以GOSS可以在較小的數據量下獲得相當準確的信息增益估計。
- 2、EFB(Exclusive Feature Bundling)：bundle 不會同時為零的特征（互斥），達到減少特征數量的目的。尋找互斥特征的最優(yōu) bundle 是 NP-Hard 的，但是貪心算法可以獲得很好的近似比（因此可以有效地減少特征的數量，而不會對分割點的確定造成很大的影響）。
在多個公共數據集上的實驗表明，LightGBM 可以將傳統(tǒng) GBDT 的訓練速度提高20倍以上，同時達到幾乎相同的精度。
2、LightGBM 輕量級提升學習方法
2.1、基于直方圖的排序算法
傳統(tǒng)的 GDBT 方法的主要計算開銷是各 Decision Tree 的學習過程，而學習過程的主要開銷是最優(yōu)劃分點的尋找。
最流行的方法是 Pre-sorted 方法，也就是預先將所有特征進行排序，然后對所有數據，遍歷所有可能的劃分點，這樣就可以找到最優(yōu)劃分點。但是這種算法的計算開銷和空間占用都很大。
另一種算法便是基于直方圖的算法。該算法將連續(xù)的特征值進行離散化分桶，然后用桶中的特征值數量來構建直方圖。然后根據直方圖的離散值，遍歷尋找最優(yōu)的分割點。相比 Pre-sorted 算法，基于直方圖的算法在時間和空間開銷上都較小。
算法流程如下：
看起來很復雜的樣子，拆解開來實際上就是：設置一個最大深度，然后遍歷每一層，在每一層中遍歷各個葉子節(jié)點，然后對每個結點中的數據，遍歷所有特征，根據當前特征的分桶規(guī)則將當前結點中的所有數據進行分桶，并實時更新各桶中的數據量以及梯度之和，以供后續(xù)尋找最優(yōu)劃分點使用。
想象這樣一個例子，某個結點上的數據點為，也就是說在第一維特征上，前兩個樣本點是屬于 bin1 的，后兩個樣本點是屬于 bin 2 的，在第二維特征上，而第二和第三個樣本點是屬于 bin 1 的，第一和第四個樣本點是屬于 bin 2 的，現在這個結點保存了兩個直方圖（對于兩個維度），而我們需要考慮兩個劃分點（即第一維上 bin 1和 bin 2中間的劃分點以及第二維上 bin 1和 bin 2中間的劃分點），假設按第一維來劃分增益較多，則我們將結點劃分為
和
兩個子結點，此時產生左結點的兩個直方圖，第一維特征的直方圖很簡單，只需要將 bin 2 的部分清零即可，第二維的直方圖則需要根據結點中樣本的第二維特征（實際上第二維特征就等于其在第二維上所屬的 bin 的序號）進行更新，實際上就是按照上圖所示的算法建立直方圖，然后右結點的兩個直方圖可由父親結點和左子結點做差得出。
不難看出，上述算法中，建立直方圖的計算復雜度是，通過直方圖找到最佳劃分點的復雜度為
。由于
通常比
大得多，因此總的復雜度是
量級的。也就是說，想降低復雜度，要減少所用的數據量或者所用特征數量。
相比之下，Pre-sorted 算法尋找最優(yōu)劃分的復雜度為。也就是說，直方圖算法減小了尋找最優(yōu)劃分點的計算開銷。
實際上，基于直方圖的算法還可以進一步節(jié)約計算開銷，LightGBM 的直方圖可以做差加速。所謂做差加速，即一個葉子的直方圖可以由它的父親結點的直方圖與它兄弟的直方圖做差得到。構造的直方圖本來需要遍歷該葉子結點上所有數據，但是直方圖做差僅需遍歷直方圖的個桶即可（即直方圖區(qū)間），速度上可以提升一倍。
此外，直方圖算法不僅不需要額外存儲預排序的結果，而且可以只保存特征離散化后的值，而這個值一般用 8 位整型存儲就足夠了，內存消耗可以降低為原來的。
基于直方圖的算法的時間復雜度為，為了進一步提高算法的運行效率。需要減少所需的樣本數量或者特征數量，而 LightGBM 提出的 GOSS 和 EFB 就是用來做這兩件事的。接下來我們看一下這兩個算法的具體流程和原理。
2.2、GOSS采樣策略
既然要對樣本進行采樣，就要樹立規(guī)則來判斷各樣本對模型的重要程度，或者說對損失函數的貢獻程度。一種隱形的采樣方法在 AdaBoost 中有所運用，即通過給樣本賦予不同的權重來表示其重要性，權重大的樣本會在分類器的訓練過程中得到重點關注。
作者提出了類似的權重概念，來定義樣本的重要性。樣本的梯度越小，則樣本的訓練誤差越小，表示樣本訓練得越好，其對于模型表現的提高的重要性就越小，因此賦予較小的權重，而大梯度的樣本則賦予較大權重。
要想減少樣本數量，我們只需要移除梯度較小的這部分樣本即可。但此時會產生一個問題，那就是破壞原始的數據分布。
為解決這個問題，lightGBM 采用了 one-side 采樣的方式來適配：保留所有的大梯度樣本，對小梯度樣本進行隨機采樣（只對小梯度樣本采樣，因此名為 one-side），同時為了保證分布的一致性，在計算信息增益的時候，將采樣的小梯度樣本乘以一個常量：，這里
表示大梯度樣本采樣比例，
表示小梯度樣本的采樣比例（這里的百分比都是相對于全部樣本而言的）。
舉例來說，100個樣本中，大梯度樣本有 20 個，小梯度樣本有 80 個，小梯度樣本量是大梯度樣本數據量的 4 倍，則大樣本采樣比率 等于 0.2，假設小梯度樣本的采樣率為 40%，則
等于 0.4，小梯度樣本的采樣數目等于 0.4 ×100 = 40 個，為了保證采樣前后樣本的分布保持一致，最后小梯度樣本采樣得到的數據在計算信息增益時需要乘以
。
整個算法流程如圖所示：
接下來文章進一步給出了 GOSS 的理論證明，說明了：
（1）GOSS 采樣可以得到和使用全部數據差不多的結果。
（2）GOSS 的泛化性能可能更好，因為采樣過程起到了防止過擬合的作用。
2.3、EFB特征合并
高維數據通常是非常稀疏的，而且很多特征是互斥的（即兩個或多個特征列不會同時為0），lightGBM 對這類數據采用了 EFB（exclusive feature bundling）的優(yōu)化策略，將這些互斥特征分組合并為個維度。通過這種方式，將特征的維度降下來。
算法要解決的問題有兩個：
- 1、哪些特征可以 bundle 在一起；
- 2、如何構建 bundle，實現特征降維。
對于第一個問題，作者說明了將特征劃分為最少數量的互斥特征 bundle 本質上屬于 NP-Hard 問題。因為我們可以由圖著色問題（Graph Coloring Problem）歸約到此問題。
圖著色問題就是給定一張圖，用最少種類的顏色對圖進行著色，使得任意相鄰的兩個頂點顏色不同。
創(chuàng)建一個圖，令圖中的節(jié)點
表示特征，將不互斥的特征用一條邊連接起來，邊的權重就是兩個相連接的特征的總沖突值，這樣一來，需要綁定的特征就是在圖著色問題中要涂上同一種顏色的那些點（特征）。
即然此問題是 NP-Hard 的，那么我們就找不到多項式的算法來得到精確解，因此論文中給出了一種貪心算法：
簡單來說，算法流程如下：
1、創(chuàng)建圖
，令圖中的節(jié)點
表示特征，邊權為特征間的沖突數。
2、將特征按照在圖中的度進行降序排序。
3、遍歷排序后的特征，對每個特征，遍歷現有的 bundle，若將當前特征加入當前 bundle 中后 bundle 的總沖突數不超過閾值
，則加入，否則檢查下一個 bundle，若現有 bundle 均不滿足條件，則新開一個 bundle 并將當前特征放入其中。
采用這種方法對于特征數目不大的數據性能還不錯，但是對于超大規(guī)模的特征將會出現性能瓶頸。一個優(yōu)化的方向就是：按照非零值的個數進行排序，通常非零值越多沖突就越大，我們就把它排得更靠前。
對于第二個問題：應該如何如何構建bundle？關鍵在于構建前的特征的值在構建后的 bundle 中依然能夠被識別。
由于基于直方圖的方法存儲的是離散的 bin 而不是連續(xù)的數值，因此我們將不同特征的 bin 值設定為不同的區(qū)間即可。例如，特征 A 的 bin 值為 [0,10)，特征 B 的 bin 值為 [0,20)，要想將兩個特征 bin 合并，我們可以將特征 B 的特征 bin 的值加上10，其取值區(qū)間將變?yōu)?[10,30)。之后，將特征 A 和 B 合并，使用范圍 [0,30] 的 bundle 來代替原來的特征 A 和 B 即可。
算法流程如下：
下面舉例說明上述算法流程，設 bundle 中有 2 個特征，
的 bin 為
和
，
的 bin 為
和
，則第一個循環(huán)結束后，我們可以得到
?，F在假設我們有一個數據
，其原來的 bin 值為
，即
落在第二個 bin 中，
落在第一個 bin 中，經過第二個循環(huán)后，其 bin 值更新為
，即
。
有了 EFB 方法，數據的 shape 就可以由原來的 縮小為現在的
，且
?？梢钥吹?，EFB 方法降低了數據特征規(guī)模，提高了模型的訓練速度。
2.4、Leaf-wise (Best-first) Tree Growth
在樹的生成方式上，lightGBM 與 XGBoost 有所區(qū)別。
XGBoost 決策樹的生長策略是 level-wise，即逐層對各層的每個結點進行劃分，直至達到終止條件。它不加區(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷，因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。
lightGBM 決策樹的生長策略是 leaf-wise。與 level-wise 不同，leaf-wise 策略以降低模型損失最大化為目的，對當前葉子中切分增益最大的葉子進行切分。這種方法可以降低更多的誤差，得到更好的精度，但缺點是可能會長出比較深的決策樹，產生過擬合。因此 LightGBM 在 leaf-wise 之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。
2.5、直接支持類別特征（即不需要做 one-hot 編碼）
大多數機器學習工具都無法直接支持類別特征，一般需要把類別特征，轉化到多維的 one-hot 編碼特征，降低了空間和時間的效率。而類別特征的使用是在實踐中很常用的?；谶@個考慮，LightGBM 優(yōu)化了對類別特征的支持，可以直接輸入類別特征，不需要額外的 one-hot 編碼展開。并在決策樹算法上增加了類別特征的決策規(guī)則。
2.6、直接支持高效并行
LightGBM 還具有支持高效并行的優(yōu)點。LightGBM 原生支持并行學習，目前支持特征并行和數據并行的兩種。
- 1、特征并行的主要思想是在不同機器在不同的特征集合上分別尋找最優(yōu)的分割點，然后在機器間同步最優(yōu)的分割點。
- 2、數據并行則是讓不同的機器先在本地構造直方圖，然后進行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點。
LightGBM 針對這兩種并行方法都做了優(yōu)化，在特征并行算法中，通過在本地保存全部數據避免對數據切分結果的通信；在數據并行中使用分散規(guī)約 (Reduce scatter)把直方圖合并的任務分攤到不同的機器，降低通信和計算，并利用直方圖做差，進一步減少了一半的通信量。
Reference：
https://fuhailin.github.io/LightGBM/
