快的不要不要的lightGBM

上一篇文章介紹了一個梯度提升決策樹模型XGBoost 機器學習競賽大殺器XGBoost--原理篇，這篇文章我們繼續學習一下GBDT模型的另一個進化版本：lightGBM。之所以說他快的不要不要的，是因為它真的很快- -，下圖是我在京東的信貸預測競賽中使用xgb和lgb做訓練的訓練時間對比，lgb是有多快一目了然。

在一些機器學習任務的實際應用中，我們面對的數據集維度可能非常高（特徵多），同時數據樣本也很大（訓練實例多），這樣一來許多演算法在訓練速度和可擴展性方面就顯得力不從心了。最主要的原因是，對於每一個特徵這些演算法需要掃描每一個數據實例來計算最佳的信息增益從而確定最佳的分裂節點，這是非常耗時間的。特別的，我們來講一下XGBoost的缺點：

1. 每次迭代訓練時需要讀取整個數據集，耗時耗內存；
2. 使用Basic Exact Greedy Algorithm計算最佳分裂節點時需要預先將特徵的取值進行排序，排序之後為了保存排序的結果，費時又費內存；
3. 計算分裂節點時需要遍歷每一個候選節點，然後計算分裂之後的信息增益，費時；
4. 生成決策樹是level-wise級別的，也就是預先設置好樹的深度之後，每一顆樹都需要生長到設置的那個深度，這樣有些樹在某一次分裂之後效果甚至沒有提升但仍然會繼續劃分樹枝，然後再次劃分....之後就是無用功了，耗時。

為了避免上述XGB的缺陷，並且能夠在不損害準確率的條件下加快GBDT模型的訓練速度，lightGBM在傳統的GBDT演算法上加了兩個技術：

1. 單邊梯度採樣 Gradient-based One-Side Sampling (GOSS)；
2. 互斥稀疏特徵綁定 Exclusive Feature Bundling (EFB)

使用GOSS可以減少大量只具有小梯度的數據實例，這樣在計算信息增益的時候只利用剩下的具有高梯度的數據就可以了，相比XGB遍歷所有特徵值節省了不少開銷；使用EFB可以將許多互斥的特徵綁定為一個特徵，這樣達到了降維的目的。

下面正式進入lightGBM。

一、 Gradient-based One-Side Sampling

GOSS是一個樣本實例的採樣演算法，目的是丟棄一些對計算信息增益沒有幫助的實例留下有幫助的。首先來了解一下信息增益（略，下次講）。可以看到具有較大梯度的數據對計算信息增益的貢獻比較大（參考論文Greedy Function Approximation: A Gradient Boosting Machine的證明），因此GOSS在進行數據採樣的時候只保留了梯度較大的數據，但是如果直接將所有梯度較小的數據都丟棄掉勢必會影響數據的總體分布，因此GOSS首先將要進行分裂的特徵的所有取值按照絕對值大小降序排序（XGB一樣也進行了排序，但是lgb不用保存排序後的結果），選取絕對值最大的a*100%個數據，然後在剩下的教小梯度數據中隨機選擇b*100%個數據，並且將這b%個數據乘以一個常數 %，最後使用這（a+b）%個數據來計算信息增益。下圖是GOSS的具體演算法

從以上演算法看，在d次迭代中lightGBM只使用了useSet個實例進行訓練，每一輪迭代都學習了一個弱學習器，並且在進行下一輪學習時，前面的每一輪所學習的弱學習器都將影響該輪的學習。

二、 Exclusive Feature Bundling

高維度的數據通常是非常稀疏的，這樣的特性為特徵的相互之間結合提供了便利。通過將一些特徵進行融合綁定在一起，可以使特徵數量大大減少，這樣在進行histogram building時時間複雜度從O(#data * #feature)變為O(#data * #bundle)，這裡#bundle遠小於#feature。

那麼將哪些特徵綁定在一起呢？又要怎麼綁定呢？

對於第一個問題，將相互獨立的特徵進行bunding是一個NP難問題，lightGBM將這個問題轉化為圖著色的為題來求解，將所有特徵視為圖G的一個頂點，將不是相互獨立的特徵用一條邊連接起來，邊的權重就是兩個相連接的特徵的總衝突值，這樣需要綁定的特徵就是在圖著色問題中要塗上同一種顏色的那些點（特徵）。

對於第二個問題，綁定幾個特徵在同一個bundle里需要保證綁定前的原始特徵的值可以在bundle中識別，考慮到 histogram-based演算法將連續的值保存為離散的bins，我們可以使得不同特徵的值分到bundle中的不同bins中，這可以通過在特徵值中加一個偏置常量來解決，比如，我們在bundle中綁定了兩個特徵A和B，A特徵的原始取值為區間[0,10)，B特徵的原始取值為區間[0,20），我們可以在B特徵的取值上加一個偏置常量10，將其取值範圍變為[10,30），這樣就可以放心的融合特徵A和B了，因為在樹模型中對於每一個特徵都會計算分裂節點的，也就是通過將他們的取值範圍限定在不同的bins中，在分裂時可以將不同特徵很好的分裂到樹的不同分支中去。

三、 Histogram-based Algorithm

Histogram-based 演算法不是lightGBM所特有的，其他GBDT演算法也採用了這樣的演算法，XGB也有，但是它和lightGBM有所不同，這裡介紹一下lgb的Histogram-based 演算法。

Histogram-based 演算法將連續的特徵映射到離散的buckets中，組成一個個的bins，然後使用這些bins建立直方圖。簡而言之就是將連續變數離散化。

四、Leaf-wise

前面講了XGB是level-wise。而lightGBM是Leaf-wise，即帶深層限制的Leaf-wise的葉子生長策略，它具有快速收斂的效果，lgb在生成樹的過程中不需要達到設置的樹的深度只要樹的葉子數量達到了設置的個數之後就終止當前樹的生長，這樣就不會為了達到深度而去生長一些對任務貢獻不大的樹葉。這也是lightGBM訓練速度快的一個原因。但是Leaf-wise也容易過擬合，如果你設置參數不得當。

參考資料：

論文：Guolin Ke等， LightGBM: A Highly Efficient Gradient Boosting Decision Tree

推薦閱讀：