LightGBM原理之論文詳解

作者：立刻有

連結：

https://blog.csdn.net/shine19930820/article/details/79123216

編輯：石頭

原文：LightGBM : A Highly Efficient Gradient Boosting Decision Tree

原文下載：後臺回復「LightGBM"

【Abstract】

Gradient Boosting Decision Tree (GBDT)非常流行卻鮮有實現，只有像XGBoost和pGBRT。當特徵維度較高和數據量巨大的時候，其實現中仍然存在效率和可擴展性的問題。一個主要原因就是對於每一個特徵的每一個分裂點，都需要遍歷全部數據計算信息增益，這一過程非常耗時。針對這一問題，本文提出兩種新方法：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基於梯度的one-side採樣和互斥的特徵捆綁）。在GOSS中，我們排除了重要的比例-具有小梯度的實例，只用剩下的來估計信息增益，我們證明，這些梯度大的實例在計算信息增益中扮演重要角色，GOSS可以用更小的數據量對信息增益進行相當準確的估計。對於EFB，我們捆綁互斥的特徵（什麼是互斥特徵：例如特徵間很少同時非零。），來降低特徵的個數。我們證明完美地捆綁互斥特徵是NP難的，但貪心算法能夠實現相當好的逼近率，因此我們能夠在不損害分割點準確率許多，有效減少特徵的數量。（犧牲一點分割準確率降低特徵數量），這一算法命名為LightGBM。在多個公共數據集實驗證明，LightGBM加速了傳統GBDT訓練過程20倍以上，同時達到了幾乎相同的精度 。

GBDT因為其的有效性、準確性、可解釋性，成為了廣泛使用的機器學習算法。GBDT在許多機器學習任務上取得了最好的效果（ state-of-the-art），例如多分類，點擊預測，排序。但最近幾年隨著大數據的爆發（特徵量和數據量），GBDT面臨平衡準確率和效率的調整。

GBDT缺點：對於每一個特徵的每一個分裂點，都需要遍歷全部數據來計算信息增益。因此，其計算複雜度將受到特徵數量和數據量雙重影響，造成處理大數據時十分耗時。

解決這個問題的直接方法就是減少特徵量和數據量而且不影響精確度，有部分工作根據數據權重採樣來加速boosting的過程，但由於gbdt沒有樣本權重不能應用。而本文提出兩種新方法實現此目標。

Gradient-based One-Side Sampling (GOSS)：GBDT雖然沒有數據權重，但每個數據實例有不同的梯度，根據計算信息增益的定義，梯度大的實例對信息增益有更大的影響，因此在下採樣時，我們應該儘量保留梯度大的樣本（預先設定閾值，或者最高百分位間），隨機去掉梯度小的樣本。我們證明此措施在相同的採樣率下比隨機採樣獲得更準確的結果，尤其是在信息增益範圍較大時。

Exclusive Feature Bundling (EFB)：通常在真實應用中，雖然特徵量比較多，但是由於特徵空間十分稀疏，是否可以設計一種無損的方法來減少有效特徵呢？特別在稀疏特徵空間上，許多特徵幾乎是互斥的（例如許多特徵不會同時為非零值，像one-hot），我們可以捆綁互斥的特徵。最後，我們將捆綁問題歸約到圖著色問題，通過貪心算法求得近似解。

2.1 GBDT and Its Complexity Analysis

GBDT是一種集成模型的決策樹，順序訓練決策樹。每次迭代中，GBDT通過擬合負梯度（殘差）來學到決策樹。

學習決策樹是GBDT主要的時間花銷，而學習決策樹中找到最優切分點最消耗時間。廣泛採用的預排序算法來找到最優切分點，這種方法會列舉預排序中所有可能的切分點。這種算法雖然能夠找到最優的切分點，但對於訓練速度和內存消耗上都效率低。另一種流行算法是直方圖算法（histogram-based algorithm）。直方圖算法並不通過特徵排序找到最優的切分點，而是將連續的特徵值抽象成離散的分箱，並使用這些分箱在訓練過程中構建特徵直方圖，這種算法更加訓練速度和內存消耗上都更加高效，lightGBM使用此種算法。

histogram-based算法通過直方圖尋找最優切分點，其建直方圖消耗O(#data * #feature)，尋找最優切分點消耗O(#bin * # feature)，而#bin的數量遠小於#data，所以建直方圖為主要時間消耗。如果能夠減少數據量或特徵量，那麼還能夠夠加速GBDT的訓練。

2.2 Related Work

GBDT有許多實現，如XGBoost，PGBRT，Scikit-learn，gbm in R。Scikit-learn和gbm in R實現都用了預排序，pGBRT使用了直方圖算法，XGBoost支持預排序和直方圖算法，由於XGBoost勝過其他算法，我們用它作為baseline。

為了減小訓練數據集，通常做法是下採樣。例如過濾掉權重小於閾值的數據。SGB每次迭代中用隨機子集訓練弱學習器。或者採樣率基於訓練過程動態調整。除了基於AdaBoost的SGB不能直接應用於GBDT，因為GBDT中沒有原始的權重。雖然SGB也能間接應用於GBDT，但往往會影響精度。

同樣，過濾掉弱特徵（什麼是弱特徵）來減少特徵量。通常用主成分分析或者投影法。當然，這些方法依賴於一個假設-特徵包含高度的冗餘，但實際中往往不是。（設計特徵來自於其獨特的貢獻，移除任一維度都可以某種程度上影響精度）。

實際中大規模的數據集通常都是非常稀疏的，使用預排序算法的GBDT能夠通過無視為0的特徵來降低訓練時間消耗。然後直方圖算法沒有優化稀疏的方案。因為直方圖算法無論特徵值是否為0，都需要為每個數據檢索特徵區間值。如果基於直方圖的GBDT能夠有效利用稀疏特徵將是最優。

下圖是兩個算法的對比：

3. Gradient-based One-Side Sampling

GOSS是一種在減少數據量和保證精度上平衡的算法。

3.1 Algorithm Description

AdaBoost中，樣本權重是數據實例重要性的指標。然而在GBDT中沒有原始樣本權重，不能應用權重採樣。幸運的事，我們觀察到GBDT中每個數據都有不同的梯度值，對採樣十分有用，即實例的梯度小，實例訓練誤差也就較小，已經被學習得很好了，直接想法就是丟掉這部分梯度小的數據。然而這樣做會改變數據的分布，將會影響訓練的模型的精確度，為了避免此問題，我們提出了GOSS。

GOSS保留所有的梯度較大的實例，在梯度小的實例上使用隨機採樣。為了抵消對數據分布的影響，計算信息增益的時候，GOSS對小梯度的數據引入常量乘數。GOSS首先根據數據的梯度絕對值排序，選取top a個實例。然後在剩餘的數據中隨機採樣b個實例。接著計算信息增益時為採樣出的小梯度數據乘以(1-a)/b，這樣算法就會更關注訓練不足的實例，而不會過多改變原數據集的分布。

3.2 Theoretical Analysis

GBDT使用決策樹，來學習獲得一個將輸入空間映射到梯度空間的函數。假設訓練集有n個實例x1，...，xn，特徵維度為s。每次梯度迭代時，模型數據變量的損失函數的負梯度方向為g1，...，gn，決策樹通過最優切分點（最大信息增益點）將數據分到各個節點。GBDT通過分割後的方差衡量信息增益。

定義3.1：O表示某個固定節點的訓練集，分割特徵 j 的分割點d定義為：

其中，

遍歷每個特徵分裂點 j，找到

對應最大的分裂節點，並計算最大的信息增益。然後，將數據根據特徵的分裂點將數據分到左右節點。

在GOSS中，

1. 首先根據數據的梯度將訓練降序排序。

2. 保留top a個數據實例，作為數據子集A。

3. 對於剩下的數據的實例，隨機採樣獲得大小為b的數據子集B。

4. 最後我們通過以下方程估計信息增益:

此處GOSS通過較小的數據集估計信息增益，將大大地減小計算量。更重要的是，我們接下來理論表明GOSS不會丟失許多訓練精度，勝過（outperform）隨機採樣。理論的證明再附加材料。

Theorem 3.2  我們定義GOSS近似誤差為：，且

，

概率至少是1−δ，有：

其中：

根據理論3.2，我們得出以下結論：

1. GOSS的漸進逼近比率是：

如果數據分割不是極不平衡，比如：

且

近似誤差主要由第二項主導，當n趨於無窮（數據量很大）時，

趨於0。即數據量越大，誤差越小，精度越高。

2. 隨機採樣是GOSS在a=0的一種情況。多數情況下，GOSS性能優於隨機採樣，即以下情況：

即：

其中，

下面分析GOSS的泛化性。考慮GOSS泛化誤差：

這是GOSS抽樣的的實例計算出的方差增益與實際樣本方差增益之間的差距。

變換為：

因此，在GOSS準確的情況下，GOSS泛化誤差近似於全數據量的真實數據。另一方面，採樣將增加基學習器的多樣性（因為每次採樣獲得的數據可能會不同），這將提高泛化性。

4. Exclusive Feature Bundling 

這一章介紹如何有效減少特徵的數量

高維的數據通常是稀疏的，這種稀疏性啟發我們設計一種無損地方法來減少特徵的維度。特別的，稀疏特徵空間中，許多特徵是互斥的，例如他們從不同時為非零值。我們可以綁定互斥的特徵為單一特徵，通過仔細設計特徵搜尋算法，我們從特徵捆綁中構建了與單個特徵相同的特徵直方圖。這種方式的間直方圖時間複雜度從O(#data * #feature)降到O(#data * #bundle)，由於#bundle << # feature，我們能夠極大地加速GBDT的訓練過程而且損失精度。

有兩個問題：

1. 怎麼判定那些特徵應該綁在一起（build bundled）？

2. 怎麼把特徵綁為一個（merge feature）？

4.1 bundle（什麼樣的特徵被綁定）？

**理論 4.1：**將特徵分割為較小量的互斥特徵群是NP難的。

證明：將圖著色問題歸約為此問題，而圖著色是NP難的，所以此問題就是NP難的。

給定圖著色實例G=(V, E)。以G的關聯矩陣的每一行為特徵，得到我們問題的一個實例有|V|個特徵。 很容易看到，在我們的問題中，一個獨特的特徵包與一組具有相同顏色的頂點相對應，反之亦然。

理論4.1說明多項式時間中求解這個NP難問題不可行。為了尋找好的近似算法，我們將最優捆綁問題歸結為圖著色問題，如果兩個特徵之間不是相互排斥，那麼我們用一個邊將他們連接，然後用合理的貪婪算法（具有恆定的近似比）用於圖著色來做特徵捆綁。 此外，我們注意到通常有很多特徵，儘管不是100％相互排斥的，也很少同時取非零值。 如果我們的算法可以允許一小部分的衝突，我們可以得到更少的特徵包，進一步提高計算效率。經過簡單的計算，隨機汙染小部分特徵值將影響精度最多為：

γ是每個綁定中的最大衝突比率，當其相對較小時，能夠完成精度和效率之間的平衡。

**算法3：**基於上面的討論，我們設計了算法3，偽代碼見下圖，具體算法：

1.建立一個圖，每個點代表特徵，每個邊有權重，其權重和特徵之間總體衝突相關。

2. 按照降序排列圖中的度數來排序特徵。

3. 檢查排序之後的每個特徵，對他進行特徵綁定或者建立新的綁定使得操作之後的總體衝突最小。

算法3的時間複雜度是O(#feature^2)，訓練之前只處理一次，其時間複雜度在特徵不是特別多的情況下是可以接受的，但難以應對百萬維的特徵。為了繼續提高效率，我們提出了一個更加高效的無圖的排序策略：將特徵按照非零值個數排序，這和使用圖節點的度排序相似，因為更多的非零值通常會導致衝突，新算法在算法3基礎上改變了排序策略。

4.2 merging features(特徵合併)

如何合併同一個bundle的特徵來降低訓練時間複雜度。關鍵在於原始特徵值可以從bundle中區分出來。鑑於直方圖算法存儲離散值而不是連續特徵值，我們通過將互斥特徵放在不同的箱中來構建bundle。這可以通過將偏移量添加到特徵原始值中實現，例如，假設bundle中有兩個特徵，原始特徵A取值[0, 10]，B取值[0, 20]。我們添加偏移量10到B中，因此B取值[10, 30]。通過這種做法，就可以安全地將A、B特徵合併，使用一個取值[0, 30]的特徵取代AB。算法見算法4，

EFB算法能夠將許多互斥的特徵變為低維稠密的特徵，就能夠有效的避免不必要0值特徵的計算。實際，通過用表記錄數據中的非零值，來忽略零值特徵，達到優化基礎的直方圖算法。通過掃描表中的數據，建直方圖的時間複雜度將從O(#data)降到O(#non_zero_data)。當然，這種方法在構建樹過程中需要而額外的內存和計算開銷來維持預特徵表。我們在lightGBM中將此優化作為基本函數，因為當bundles是稀疏的時候，這個優化與EFB不衝突（可以用於EFB）。

這部分主要寫了lightGBM的實驗結果，主要用了五個公開數據集，如下

微軟的排序數據集（LETOR）包括30K的網頁搜索，數據集幾乎都是稠密的數值特徵。

Allstate是保險和航空延誤數據都包含了大量的one-hot特徵。

後兩個是KDD CUP2010和KDD CPU2012數據集，使用了冠軍解決方案中的特徵，其中包含了稀疏和稠密的特徵，並且這兩個數據集特別大。

這些數據集都比較大，而且包含了稀疏和稠密的特徵，涵蓋了很多真實的業務，因此它們能夠完全地測試lightGBM的性能。

5.1 Overall Comparison

XGBoost和lightGBM without GOSS 和EFB（lgb baseline），作為比較的基準。XGBoost使用了兩個版本：xgb_exa(預排序)和xgb_his(直方圖算法)。對於xgb_exa做了參數調整，使XGBoost長成和其他算法相似的樹。並且調整參數在速度和準確率間平衡。對於Allstate、KDD10 和 KDD2012，設置a = 0.05 , b = 0.05 ，對於航空延誤和LETOR，我們設置a = 0.1 , b = 0.1 ，數據集EFB我們設置γ = 0 。所有的算法有固定迭代次數。在一定迭代次數內，我們取最高的分數。

下表是訓練時間對比（時間是每次迭代的平均時間）

下表是精確度對比，分類使用AUC評價，排序使用NDCG評價。

下圖是飛行延時和LETOR的訓練曲線。

5.2 Analysis on GOSS

**速度上：**GOSS具有加速訓練的能力，表2中可以看出GOSS幾乎加速了兩倍。雖然GOSS用了10%-20%的數據訓練，但是由於有一些額外的計算，所以加速並不和數據量成反比，但是GOSS仍然極大加速了訓練。

**精度上：**從表4中可以看出，同樣採樣率，GOSS精度總比SGB好。

5.3 Analysis on EFB

表2表明，EFB在大數據集上能夠極大加速訓練。因為EFB合併大量的稀疏特徵到低維稠密的特徵，並且由於之前的孤立的特徵被bundle到一起，能能夠極大提高緩存的命中率，因此，它全部的效率提高是動態的。

綜上這些分析，EFB是改進直方圖算法稀疏性的非常高效的算法，能夠極大地加速GBDT訓練。

本文提出了新穎的GBDT算法–LightGBM，它包含了連個新穎的技術：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基於梯度的one-side採樣和互斥的特徵捆綁）來處理大數據量和高維特徵的場景。我們在理論分析和實驗研究表明，GOSS和EFB使得LightGBM在計算速度和內存消耗上明顯優於XGBoost和SGB。

未來，我們將研究優化如何在GOSS中選擇a，b。繼續提高EFB在高維特徵上的性能，無論其是否是稀疏的。

推薦閱讀

LightGBM算法原理小結