如何看待微軟新開源的LightGBM?

11-24

地址：GitHub - Microsoft/LightGBM: LightGBM is a fast, distributed, high performance gradient boosting (GBDT, GBRT, GBM or MART) framework based on decision tree algorithms, used for ranking, classification and many other machine learning tasks.
與Xgboost相比如何

Experiments · Microsoft/LightGBM Wiki · GitHub
看他們自己實驗的結果，真是驚人

10/19/2017 更新：

完整的更新列表可以參考： Microsoft/LightGBM/Key-Events.md

下面列出一些比較大的更新

R-package 已完成
缺失值（missing value）的自動處理
類別特徵(Categorical Feature) 的進一步優化，不再使用類似one-hot coding的分割方式。對於類別數量很多的類別特徵，使用one-vs-other的切分方式會長出很不平衡的樹，不能實現較好的精度。這是樹模型在支持類別特徵的一個痛點。 LightGBM可以找出類別特徵的最優切割，即many-vs-many的切分方式。並且最優分割的查找的時間複雜度可以在線性時間完成，和原來的one-vs-other的複雜度幾乎一致。

cf: NIPS 2017 有什麼值得關注的亮點？

12/17/2016 更新：

完成了python-package，歡迎使用。
直接支持類別特徵(Categorical Feature)，不需要進行0/1展開。相對0/1展開的解決方案，速度快非常多，且精度一致。

大多數機器學習工具都無法直接支持類別特徵作為輸入，一般需要轉換成多維0/1特徵，帶來計算和內存上的額外消耗。LightGBM增加了針對於類別特徵的決策規則，這在決策樹上也很好實現。主要的思想是，在對類別特徵計算分割增益的時候，不是按照數值特徵那樣由一個閾值進行切分，而是直接把其中一個類別當成一類，其他的類別當成另一類。這實際上與0/1展開的效果是一樣的。

---------------------------------------

正好開源了一個月，強答一下。

GBDT 雖然是個強力的模型，但卻有著一個致命的缺陷，不能用類似 mini batch 的方式來訓練，需要對數據進行無數次的遍歷。如果想要速度，就需要把數據都預載入在內存中，但這樣數據就會受限於內存的大小；如果想要訓練更多的數據，就要使用外存版本的決策樹演算法。雖然外存演算法也有較多優化，SSD 也在普及，但在頻繁的 IO 下，速度還是比較慢的。

為了能讓 GBDT 高效地用上更多的數據，我們把思路轉向了分散式 GBDT，然後就有了 LightGBM。設計的思路主要是兩點，1. 單個機器在不犧牲速度的情況下，儘可能多地用上更多的數據；2.
多機並行的時候，通信的代價儘可能地低，並且在計算上可以做到線性加速。

基於這兩個需求，LightGBM 選擇了基於 histogram 的決策樹演算法。相比於另一個主流的演算法 pre-sorted（如 xgboost 中的 exact 演算法），histogram 在內存消耗和計算代價上都有不少優勢。

Pre-sorted 演算法需要的內存約是訓練數據的兩倍(2 * #data * #features
* 4Bytes)，它需要用32位浮點來保存 feature value，並且對每一列特徵，都需要一個額外的排好序的索引，這也需要32位的存儲空間。對於 histogram 演算法，則只需要(#data
* #features * 1Bytes)的內存消耗，僅為 pre-sorted演算法的1/8。因為 histogram 演算法僅需要存儲 feature
bin value (離散化後的數值)，不需要原始的 feature value，也不用排序，而 bin
value 用 uint8_t (256
bins) 的類型一般也就足夠了。
在計算上的優勢則主要體現在「數據分割」。決策樹演算法有兩個主要操作組成，一個是「尋找分割點」，另一個是「數據分割」。從演算法時間複雜度來看，Histogram 演算法和 pre-sorted 演算法在「尋找分割點」的代價是一樣的，都是O(#feature*#data)。而在「數據分割」時，pre-sorted 演算法需要O(#feature*#data)，而 histogram 演算法是O(#data)。因為 pre-sorted 演算法的每一列特徵的順序都不一樣，分割的時候需要對每個特徵單獨進行一次分割。Histogram演算法不需要排序，所有特徵共享同一個索引表，分割的時候僅需對這個索引表操作一次就可以。（更新: 這一點不完全正確，pre-sorted 與 level-wise 結合的時候，其實可以共用一個索引表(row_idx_to_tree_node_idx)。然後在尋找分割點的時候，同時操作同一層的節點，省去分割的步驟。但這樣做的問題是會有非常多隨機訪問，有很大的chche miss，速度依然很慢。）。
另一個計算上的優勢則是大幅減少了計算分割點增益的次數。對於一個特徵，pre-sorted 需要對每一個不同特徵值都計算一次分割增益，而 histogram 只需要計算 #bin (histogram 的橫軸的數量) 次。
最後，在數據並行的時候，用 histgoram 可以大幅降低通信代價。用 pre-sorted 演算法的話，通信代價是非常大的（幾乎是沒辦法用的）。所以 xgoobst 在並行的時候也使用 histogram 進行通信。

當然， histogram 演算法也有缺點，它不能找到很精確的分割點，訓練誤差沒有 pre-sorted 好。但從實驗結果來看， histogram 演算法在測試集的誤差和 pre-sorted 演算法差異並不是很大，甚至有時候效果更好。實際上可能決策樹對於分割點的精確程度並不太敏感，而且較「粗」的分割點也自帶正則化的效果。

在 histogram 演算法之上， LightGBM 進行進一步的優化。首先它拋棄了大多數 GBDT 工具使用的按層生長
(level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 演算法。 level-wise 過一次數據可以同時分裂同一層的葉子，容易進行多線程優化，不容易過擬合。但實際上level-wise是一種低效的演算法，因為它不加區分的對待同一層的葉子，帶來了很多沒必要的開銷。因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。leaf-wise則是一種更為高效的策略，每次從當前所有葉子中，找到分裂增益最大(一般也是數據量最大)的一個葉子，然後分裂，如此循環。因此同 level-wise 相比，在分裂次數相同的情況下，leaf-wise 可以降低更多的誤差，得到更好的精度。leaf-wise 的缺點是可能會長出比較深的決策樹，產生過擬合。因此 LightGBM 在leaf-wise 之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

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

如需要更多的細節，可以參考github上的文檔：https://github.com/Microsoft/LightGBM/wiki/Features

下午跑了一個分類實驗，30萬樣本，40維特徵，lightGBM在22秒內跑完，速度驚人，比xgboost快不少，精度與xgboost不相上下。但是易用性和特性相比xgboost還有待提高，cv，early stopping這兩個我覺得非常重要的特性並沒有找到。當然，相信這些特性很快就會有了。

對於數據挖掘(競賽)愛好者來說，又多了一項好工具。

Excited!

剛剛跑完lightGBM，相比於xgboost，速度的確很快。5萬多樣本，60多個feature，300的樹，3秒跑完！
在github上面看到，lightgbm改進的地方主要是特徵選擇方法上，使用的是histogram bin 的方式，而不是全部特徵進行計算。還支持真正的分散式，多台機器一起跑，而且配置文件相當簡單
可喜的是第一個版本竟然就支持lambdaMART的排序功能，這個很不錯
其他的，由於沒有詳細的論文，具體細節還無法得知

缺點也是很明顯的，沒有cv, imbalance , verbose, early stopping 等，以及還沒支持PYTHON,R等語言的介面，不過相信肯定會儘快完善

非常贊的工作，實現了和XGBoost不一樣的搜索策略，所以在演算法效果上並不是完全一樣。

- XGBoost在單機默認是exact greedy，搜索所有的可能分割點。分散式是dynamic histogram，每一輪迭代重新estimate 潛在split candidate。
- LightGBM和最近的FastBDT都採取了提前histogram binning再在bin好的數據上面進行搜索。在限定好candidate splits,
- 主要的速度提升似乎來自於兩點。一個是搜索的時候選取delta比較大的葉子擴展。第二個是pre-bin之後的histogram的求和用了一個非常巧妙的減法trick，省了一半的時間。

在演算法和效果上面

最近比較多的工作都開始基於提前限定分割點的近似演算法然後快速求histogram。這一類演算法的潛在問題是限制了分割點只能是一開始的定下來的潛在這些。不知道這一點對於實際應用的影響會有多大。理論上數據越多，樹越深的時候，需要的潛在分割點越多，可能需要根據訓練來動態更新潛在的分割點。

在演算法上面採用delta比較大的擴展方向可以集中搜索提高比較重要的區域。一個潛在的問題是可能會忽略掉一些未來有潛力的節點。

當然這些討論都和具體的應用場景有關。個人覺得exact greedy和histogram方法的還會共存一段時間。或許可以比較好的在系統上面對這兩個一起支持

在系統上面

因為集中做針對葉子的分割，似乎會對於數據集的random access有一定的要求。如果不shuffle data的情況下可能會有cache 的問題。這個數據結構是一個有趣的問題

非常值得學習，機器學習系統優化是非常重要的方向。希望可以看到越來越多這樣實際的工作

XGBOOST缺點：
在選擇樹的分隔點時，需要遍歷所有的特徵值，這在時間、空間上都是很大的開銷；
LightGBM改進：
1. 基於Histogram的決策樹演算法；
2. 帶深度限制的Leaf-wise的葉子生長策略；
3. 直接支持類別特徵(Categorical Feature)
4. ......

第一點:

先把連續的浮點特徵值離散化成k個整數，同時構造一個寬度為k的直方圖。在遍曆數據的時候，根據離散化後的值作為索引在直方圖中累積統計量。

第二點：

Level-wise過一次數據可以同時分裂同一層的葉子，容易進行多線程優化，也好控制模型複雜度，不容易過擬合。但實際上Level-wise是一種低效的演算法，因為它不加區分的對待同一層的葉子，帶來了很多沒必要的開銷，因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。

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

試驗了一下，訓練時間提升了75%以上，相同召回情況下，準確率略降。

對數據感興趣的小夥伴，歡迎交流，微信公共號:一白侃數

微軟出品值得學習, 對實現原理感興趣的可以參考這篇文檔，基本原理應該一致。
LightGBM中GBDT的實現
http://files.cnblogs.com/files/rocketfan/LightGBM%E4%B8%AD%E7%9A%84GBDT%E5%AE%9E%E7%8E%B0.pdf
GBDT的基本原理
GBDT原理實例演示 1
GBDT原理實例演示 2

圖源鏈接如下：

Microsoft/LightGBM

最近一份圍繞GBM演算法的速度測評表在從github流出，其中gpu加速版的LightGBM更比年前那個秒殺XGBoost的表現更上一層樓。陳奕迅也唱道「聽別人故事，如何的春風得意，也是別人故事」啊！那麼好玩的東西，今天等我來試試！

安裝過程遇到些許困難，具體原因就是雖然R的console顯示的是64-bit R，但在安裝過程卻奇怪地默認了32-bit的R來安裝，於是安裝界面一直報錯。後來上github留言報錯情況，開發人員回復很及時；意識到原因後重裝了R與Rtools，在安裝流程中只給64-bit打勾，不管32-bit，最後重新安裝LightGBM，就成功了！

小編留意到很多機器學習愛好者的電腦都沒有配備著像1080 / TITAN X這樣的高端顯卡，我們統計譯文編輯部秉著「人人都能玩「的精神，用出貨量最高的1060顯卡進行測評。這次測評用了三個量級的著名數據集，分別是只有234Kb的iris數據集，121 Mb的MNIST數據集以及7.48Gb的Higss Bosom數據集。硬體與軟體配置如下：

硬體

cpu：AMD Ryzen 7 1700 8核 16線程

gpu：Nvdia gtx 1060 6G

內存：8 Gb

軟體

系統：Windows 10

OpenCL：Cuda 8

Boost Binary：msvc-14.1-64

計算軟體：R語言 3.3.3 + Rtools 3.4

計算軟體包：LightGBM 0.2 + XGBoost 0.6-4

GBM演算法參數設定：

nrounds = 100

learning rate / eta = 1

early_stopping_rounds = 10

mission：iris(3分類) / MINST(10分類) / Higss Bosom(2分類)

測評結果如下:

我們不妨把上面每個數據集分類任務中用時最短的演算法的秒數定為1，再計算其他演算法用時的倍數：

從上面兩張測評結果，我們得到一些結論：

在小型和中型數據集裡面，gpu版LightGBM都不是最快的；所以在處理量級偏小的數據集時，不必大費周章上gpu了。
gpu-LightGBM與另外兩個版本在處理速率上的差距隨著數據集的量級增加而減少，並在大型數據集裡面超越了cpu-LightGBM和XGBoost，果然gpu加速是科學計算之光啊！所以經常處理大型數據集的朋友趕緊入手gpu版本吧。
在大型數據集上，gpu版本的LightGBM已經比cpu版本的快1倍了，更不用說遠遠拋離了cpu版本的XGboost。不過在這裡僅使用cpu版本XGBoost，以後有機會上gpu版本的XGBoost再更新這個測評結果。
這三個版本的測評結果都顯示隨著數據集從Kb到Mb，再到Gb，這數個1024倍的跳躍，都沒有造成演算法在計算速度有指數級的增加，這顯示這三個版本的軟體包背後優秀的吞吐優化，以及對大型數據集的優異運算性能。

最後來一份視頻看看gtx 1060加速下的LightGBM計算7.48Gb的希格斯粒子數據集的速度吧！（礦機卡都好意思拿出來...哪位看官貢獻個1080ti請留言嘻嘻）

LightGBM_趣味科普人文_科技_bilibili_嗶哩嗶哩

下期繼續圍繞LightGBM展開翻譯，包括：

教大家怎麼安裝gpu-LightGBM (小編還會把需要提前安裝的軟體放上網盤)
LightGBM參數解釋以及調參說明

敬請期待我們的公眾號——統計譯文！

http://weixin.qq.com/r/cC93bwDE5l2ZrUQM93pi (二維碼自動識別)

用Datacastle微額人品預測的數據測試了下，參數取的論文中的比較參數，得出結果是精度相同，速度比xgboost提升了30%！！

Boosted Trees

論文筆記：XGBoost: A Scalable Tree Boosting System

LightGBM vs XGBoost

我看xgb的paper 說也實現了按histo來找分割點並且有全局分段和逐層重採樣兩種方法. 但是貌似沒有選擇開關. 單機貌似就用的greedy方式. 是不是xgb加個選擇開關就行了？單機按10G數據來算的話其實greedy的速度也還能接受不過我想更快點因為按histo其實也沒啥大的精度損失吧.