不久前微軟DMTK（分布式機器學習工具包）團隊在GitHub上開源了性能超越其他boosting工具的LightGBM，在三天之內GitHub上被star了1000+次，fork了200+次。知乎上有近千人關注“如何看待微軟開源的LightGBM？”問題，被評價為“速度驚人”，“非常有啟發”，“支持分布式”，“代碼清晰易懂”，“占用內存小”等。本文邀請了微軟亞洲研究院DMTK團隊的研究員們為我們撰文解讀，教你玩轉LightGBM。

GBDT (Gradient Boosting Decision Tree) 是機器學習中一個長盛不衰的模型，其主要思想是利用弱分類器（決策樹）迭代訓練以得到最優模型，該模型具有訓練效果好、不易過擬合等優點。GBDT在工業界應用廣泛，通常被用于點擊率預測，搜索排序等任務。GBDT也是各種數據挖掘競賽的致命武器，據統計Kaggle上的比賽有一半以上的冠軍方案都是基于GBDT。

LightGBM （Light Gradient Boosting Machine）(https://github.com/Microsoft/LightGBM)是一個實現GBDT算法的框架，支持高效率的并行訓練，并且具有以下優點：

更快的訓練速度

更低的內存消耗

更好的準確率

分布式支持，可以快速處理海量數據

從LightGBM的GitHub主頁上可以直接看到實驗結果：

從下圖實驗數據可以看出，在Higgs數據集上LightGBM比XGBoost快將近10倍，內存占用率大約為XGBoost的1/6，并且準確率也有提升。在其他數據集上也可以觀察到相似的結論。

>>>>

訓練速度方面

>>>>

內存消耗方面

>>>>

準確率方面

（我們只和xgboost進行對比，因為xgboost號稱比其他的boosting 工具都要好，從他們的實驗結果來看也是如此。）

XGBoost 與其他方法在Higgs-1M數據的比較：

　　XGBoost 與其他方法在Yahoo LTR數據的比較：

　　看完這些驚人的實驗結果以后，對下面兩個問題產生了疑惑：

Xgboost已經十分完美了，為什么還要追求速度更快、內存使用更小的模型？

對GBDT算法進行改進和提升的技術細節是什么？

提出LightGBM的動機

常用的機器學習算法，例如神經網絡等算法，都可以以mini-batch的方式訓練，訓練數據的大小不會受到內存限制。

而GBDT在每一次迭代的時候，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大小；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。尤其面對工業級海量的數據，普通的GBDT算法是不能滿足其需求的。

LightGBM提出的主要原因就是為了解決GBDT在海量數據遇到的問題，讓GBDT可以更好更快地用于工業實踐。

改進的細節

1. Xgboost是如何工作的？

目前已有的GBDT工具基本都是基于預排序的方法（pre-sorted）的決策樹算法(如 xgboost)。這種構建決策樹的算法基本思想是：

首先，對所有特征都按照特征的數值進行預排序。

其次，在遍歷分割點的時候用O(#data)的代價找到一個特征上的最好分割點。

最后，找到一個特征的分割點后，將數據分裂成左右子節點。

這樣的預排序算法的優點是能精確地找到分割點。

缺點也很明顯：

首先，空間消耗大。這樣的算法需要保存數據的特征值，還保存了特征排序的結果（例如排序后的索引，為了后續快速的計算分割點），這里需要消耗訓練數據兩倍的內存。

其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。

最后，對cache優化不友好。在預排序后，特征對梯度的訪問是一種隨機訪問，并且不同的特征訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，并且不同特征訪問的順序也不一樣，也會造成較大的cache miss。

2. LightGBM在哪些地方進行了優化？

基于Histogram的決策樹算法

帶深度限制的Leaf-wise的葉子生長策略

直方圖做差加速

直接支持類別特征(Categorical Feature)

Cache命中率優化

基于直方圖的稀疏特征優化

多線程優化

下面主要介紹Histogram算法、帶深度限制的Leaf-wise的葉子生長策略和直方圖做差加速。

>>>>

Histogram算法

直方圖算法的基本思想是先把連續的浮點特征值離散化成k個整數，同時構造一個寬度為k的直方圖。在遍歷數據的時候，根據離散化后的值作為索引在直方圖中累積統計量，當遍歷一次數據后，直方圖累積了需要的統計量，然后根據直方圖的離散值，遍歷尋找最優的分割點。

　　圖：直方圖算法

使用直方圖算法有很多優點。首先，最明顯就是內存消耗的降低，直方圖算法不僅不需要額外存儲預排序的結果，而且可以只保存特征離散化后的值，而這個值一般用8位整型存儲就足夠了，內存消耗可以降低為原來的1/8。

　　圖:內存占用優化為預排序算法的1/8

然后在計算上的代價也大幅降低，預排序算法每遍歷一個特征值就需要計算一次分裂的增益，而直方圖算法只需要計算k次（k可以認為是常數），時間復雜度從O(#data*#feature)優化到O(k*#features)。

當然，Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點，所以會對結果產生影響。但在不同的數據集上的結果表明，離散化的分割點對最終的精度影響并不是很大，甚至有時候會更好一點。原因是決策樹本來就是弱模型，分割點是不是精確并不是太重要；較粗的分割點也有正則化的效果，可以有效地防止過擬合；即使單棵樹的訓練誤差比精確分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下沒有太大的影響。

>>>>

帶深度限制的Leaf-wise的葉子生長策略

在Histogram算法之上，LightGBM進行進一步的優化。首先它拋棄了大多數GBDT工具使用的按層生長 (level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。Level-wise過一次數據可以同時分裂同一層的葉子，容易進行多線程優化，也好控制模型復雜度，不容易過擬合。但實際上Level-wise是一種低效的算法，因為它不加區分的對待同一層的葉子，帶來了很多沒必要的開銷，因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。

Leaf-wise則是一種更為高效的策略，每次從當前所有葉子中，找到分裂增益最大的一個葉子，然后分裂，如此循環。因此同Level-wise相比，在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點是可能會長出比較深的決策樹，產生過擬合。因此LightGBM在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

>>>>

直方圖差加速

LightGBM另一個優化是Histogram（直方圖）做差加速。一個容易觀察到的現象：一個葉子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到。通常構造直方圖，需要遍歷該葉子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。利用這個方法，LightGBM可以在構造一個葉子的直方圖后，可以用非常微小的代價得到它兄弟葉子的直方圖，在速度上可以提升一倍。

>>>>

直接支持類別特征

實際上大多數機器學習工具都無法直接支持類別特征，一般需要把類別特征，轉化到多維的0/1特征，降低了空間和時間的效率。而類別特征的使用是在實踐中很常用的。基于這個考慮，LightGBM優化了對類別特征的支持，可以直接輸入類別特征，不需要額外的0/1展開。并在決策樹算法上增加了類別特征的決策規則。在Expo數據集上的實驗，相比0/1展開的方法，訓練速度可以加速8倍，并且精度一致。據我們所知，LightGBM是第一個直接支持類別特征的GBDT工具。

LightGBM的單機版本還有很多其他細節上的優化，比如cache訪問優化，多線程優化，稀疏特征優化等等，更多的細節可以查閱 Github Wiki (https://github.com/Microsoft/LightGBM/wiki) 上的文檔說明。

優化匯總對比表:

在探尋了LightGBM的優化之后，發現LightGBM還具有支持高效并行的優點。LightGBM原生支持并行學習，目前支持特征并行和數據并行的兩種。特征并行的主要思想是在不同機器在不同的特征集合上分別尋找最優的分割點，然后在機器間同步最優的分割點。數據并行則是讓不同的機器先在本地構造直方圖，然后進行全局的合并，最后在合并的直方圖上面尋找最優分割點。LightGBM針對這兩種并行方法都做了優化，在特征并行算法中，通過在本地保存全部數據避免對數據切分結果的通信；在數據并行中使用分散規約 (Reduce scatter) 把直方圖合并的任務分攤到不同的機器，降低通信和計算，并利用直方圖做差，進一步減少了一半的通信量。基于投票的數據并行則進一步優化數據并行中的通信代價，使通信代價變成常數級別。在數據量很大的時候，使用投票并行可以得到非常好的加速效果。更具體的內容可以看我們在NIPS2016的文章[1]。

　　LightGBM的工作還在持續進行，近期將會增加更多的新功能，如：

R, Julia 等語言支持（目前已原生支持python，R語言正在開發中）

更多平臺(如Hadoop和Spark)的支持

GPU加速

此外，LightGBM開發人員呼吁大家在Github上對LightGBM貢獻自己的代碼和建議，一起讓LightGBM變得更好。DMTK也會繼續開源更多優秀的機器學習工具，敬請期待。

[1] Meng, Qi, Guolin Ke, Taifeng Wang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, and Tieyan Liu. "A Communication-Efficient Parallel Algorithm for Decision Tree." In Advances In Neural Information Processing Systems, pp. 1271-1279. 2016.