LightGBM的出現被微軟稱爲超越XGBoost的神器，在平時的工作中用得多，來談談LightGBM的特性以及它和XGBoost的不同點。

一、LightGBM

（1）快（是真的快，比XGBoost快很多，比GBDT就快更多了）

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 算法僅需要存儲 featurebin value (離散化後的數值)，不需要原始的 feature value，也不用排序，而 binvalue 用 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，速度依然很慢。）。

最後，在數據並行的時候，用 histgoram 可以大幅降低通信代價。用 pre-sorted 算法的話，通信代價是非常大的（幾乎是沒辦法用的）。所以 xgoobst 在並行的時候也使用 histogram 進行通信。

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

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

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

（2）支持類別型特徵的直接輸入（可以說是一種創新，之前的算法都不支持）

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