影片+案例，玩轉LightGBM
- 2019 年 10 月 28 日
- 筆記
LightGBM在Higgs數據集上LightGBM比XGBoost快將近10倍，記憶體佔用率大約為XGBoost的1/6，並且準確率也有提升。 Xgboost已經十分完美了，為什麼還要追求速度更快、記憶體使用更小的模型？ 對GBDT演算法進行改進和提升的技術細節是什麼？ 一、提出LightGBM的動機 常用的機器學習演算法，例如神經網路等演算法，都可以以mini-batch的方式訓練，訓練數據的大小不會受到記憶體限制。 而GBDT在每一次迭代的時候，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進記憶體則會限制訓練數據的大小；如果不裝進記憶體，反覆地讀寫訓練數據又會消耗非常大的時間。尤其面對工業級海量的數據，普通的GBDT演算法是不能滿足其需求的。 LightGBM提出的主要原因就是為了解決GBDT在海量數據遇到的問題，讓GBDT可以更好更快地用於工業實踐。
改進的細節 Xgboost是如何工作的？ 目前已有的GBDT工具基本都是基於預排序的方法（pre-sorted）的決策樹演算法(如xgboost)。這種構建決策樹的演算法基本思想是： 首先，對所有特徵都按照特徵的數值進行預排序。 其次，在遍歷分割點的時候用O(#data)的代價找到一個特徵上的最好分割點。 最後，找到一個特徵的分割點後，將數據分裂成左右子節點。 這樣的預排序演算法的優點是能精確地找到分割點。 缺點也很明顯： 首先，空間消耗大。這樣的演算法需要保存數據的特徵值，還保存了特徵排序的結果（例如排序後的索引，為了後續快速的計算分割點），這裡需要消耗訓練數據兩倍的記憶體。 其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。 最後，對cache優化不友好。在預排序後，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。 二、LightGBM在哪些地方進行了優化？ a) 基於Histogram的決策樹演算法 b) 帶深度限制的Leaf-wise的葉子生長策略 c) 直方圖做差加速直接 d) 支援類別特徵(Categorical Feature) e) Cache命中率優化 f) 基於直方圖的稀疏特徵優化多執行緒優化。
Stacking：Catboost、Xgboost、LightGBM、Adaboost、RF etc
