作者：柯國霖
鏈接：/question/51644470/answer/130946285
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請註明出處。
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上的文檔：/Microsoft/LightGBM/wiki/Features