lightgbm：了解為什麼它很快
儘管盡我所能進行谷歌搜索，但不幸的是，我無法找到 lightgbm 速度快的原因。lightgbm 文檔解釋說，遵循的策略是“逐葉（最佳優先）樹生長”，而不是“逐級樹生長”。我無法理解其中的區別。據我了解，在決策樹中，在每個節點處，在拆分之前，都會計算每個候選特徵所產生的信息增益，並選擇該特徵用於該節點的拆分，這將在該節點處提供最大的信息增益. 在這篇論文中在 lightgbm 上，（Guolin Ke 等人）提到了基於梯度的單側採樣（GOSS）。不幸的是，我也無法理解這一點。我熟悉測量雜質中信息增益的概念，但無法理解梯度在其中的作用以及數據點梯度的含義。是否可以用外行的語言提供幫助。
由於要求更詳細的解釋：
LightGBM 速度快的三個原因：
- 基於直方圖的拆分
- 基於梯度的單側採樣 (GOSS)
- 獨家功能捆綁 (EFB)
自 1990 年代後期以來，**基於直方圖的拆分就出現在文獻中，但它在 Xgboost 中變得流行，這是第一個公開可用的實現它的包。**由於在有大量數據時找到精確的最佳拆分非常昂貴（因為它涉及測試每個可能的拆分點），因此使用基於分位數（或直方圖）的近似解決方案可以使拆分過程更快，而不會損失太多準確性。這涉及計算特徵的一些最佳加權分位數（即將數據分組到箱中），並選擇這些分位數之間的分割點。這個過程的算法可以在Xgboost 的論文中找到。Xgboost 提出了局部和全局直方圖，這意味著它們將在算法開始時（全局）或每次新拆分（局部）時為每個特徵計算。LightGBM 簡要地說，它的工作基於基於直方圖的拆分（有很多關於此的論文），但它沒有說明直方圖的計算方式，也沒有說明如何與 GOSS 一起實現。
**基於梯度的單側採樣 (GOSS)**是 LightGBM 的獨有功能，它是數據的某種高級二次採樣。由於拆分查找的計算時間與特徵和實例的數量成正比，因此對實例進行二次採樣會使這個問題更快，這也是Stochastic Gradient Boosting背後的思想通過弗里德曼。但是，SGB 對數據進行隨機採樣，通常會導致模型的準確性下降。GOSS 所做的與 Adaboost 類似——記錄由它們的偽殘差加權——因為殘差低的實例對訓練的影響很小，因為它們已經訓練有素。因此，保留高殘差記錄，同時對低殘差記錄進行大量二次抽樣，並重新校準它們的權重以避免在殘差分佈中插入偏差。這大大減少了實例的數量，同時保持了極好的性能，這也是該算法比其他基於直方圖的軟件包（如 H2O 或 XGboost）性能更好的原因之一。
**Exclusive Feature Bundling (EFB)**用於處理稀疏特徵。我根本不會深入細節，主要是因為我對它們不是特別熟悉；但是，可以說 EFB 用於將稀疏特徵捆綁在一起（這些特徵永遠不會非零在一起），從而大大減少了大型稀疏數據集的計算工作量（如前所述，找到拆分也與總數成正比的特徵）。稀疏特徵的最優捆綁通常是一個 NP-hard 問題，但通過貪心算法可以很好地近似解決。
在他們的文檔中，他們還首先提到了樹木的葉子生長。據我所知，這在論文中沒有提到，但它應該用於提高準確性而不是速度。
資料來源：LightGBM 論文:)