LightGBM explained系列——Gradient-based One-Side Sampling（GOSS）是什麼？

之前有介紹

LightGBM, Light Gradient Boosting Machine

演算法如何使用，那天我突然覺得會使用machine learning的package固然很厲害，但有些時候還是要有一個尋根的心態，所以想帶給大家一個新的系列：
Lightgbm explained系列

如果想更了解LightGBM，可以看我的LightGBM explained系列文：

• LightGBM + GridSearchCV 調整參數（調參）feat. Categorical Data處理
• LightGBM explained系列——Histogram-based algorithm是什麼？
• LightGBM explained系列——Exclusive Feature Bundling（EFB）是什麼？
• LightGBM explained系列——Gradient-based One-Side Sampling（GOSS）是什麼？

這次是介紹一下，lgb在減少計算成本所用的抽樣演算法 "Gradient-based One-Side Sampling（GOSS）"
中文名稱翻作"梯度單邊抽樣"

Lightgbm explained-Gradient-based One-Side Sampling(GOSS)

Gradient-based One-Side Sampling（GOSS） 梯度單邊抽樣

是一種抽樣（sampling）演算法，保留較大梯度樣本同時對較小梯度隨機抽樣的方式減少計算成本，可以在減少資料樣本數量和保證學習決策樹的準確性之間取得良好的平衡。

• 在AdaBoost中，樣本權值（sample weight；每個樣本，根據是否被分錯，會有一個權值）是資料樣本重要性的良好指標。
• 在GBDT中，沒有原始樣本權值，因此AdaBoost提出的抽樣方法不能直接應用。但是注意到在GBDT中的每個資料樣本的梯度提供了有用的資料抽樣資訊。
  註：AdaBoost在分錯後，在下回合會針對被分錯的加重權質，因為想分對。

為什麼只對梯度小的樣本進行抽樣呢？

因為在decision tree的訓練過程中目標函數學習的就是負梯度（近似殘差），梯度小說明訓練誤差已經很小了，對這部分資料的進一步學習的效果不如對梯度大的樣本進行學習的效果好或者說對梯度小的樣本進行進一步學習對改善結果精度幫助其實並不大；但如果全部不用會影響資料分佈（進而影響精準度），所以lgb採用GOSS進行抽樣解決這個問題。

GOSS的計算步驟如下：

1. 排列樣本資料：根據樣本的梯度將樣本降冪（decending）排序。
2. 建立梯度值較大的資料樣本：保留前topN （a%）個資料樣本，作為資料子集topSet。
   →$topSet=sorted[1:topN]$
       $topN=（a%）×#samples$
3. 建立梯度值較小的資料樣本：對於剩下的資料的樣本（1-a%），隨機抽樣獲得大小為randN （b%）的資料子集randSet。
   →$randSet=RandomPick（sorted[topN:],randN）$
       $randN=（b%）×#samples$
4. 產生New Data Set（計算information gain）：為了不改變原資料分佈，在計算information gain時，對randSet樣本的梯度資料乘以權重：$w=(1-a)/b$
   →$UsedSet=topSet+randN$
       $UsedN=（a%）×#samples+（b%）×#samples$

Theoretical Analysis：

假設：

• $n個獨立同分布（independent identical distribution）的資料集{x_1,…,x_n }，其中x_i 是空間χ^s 中的n維向量$
• $loss function的負梯度{g_1,…,g_n }$

首先討論variance gain，類似變異降低variance reduction的概念，針對連續數性在reduction過後計算regression函數。

論文中比較$V_(j|O) （d）$（用全部資料所算的information gain）和$V ̃_(j|O) （d）$（用GOSS抽樣的資料所算的information gain）。

註：在V上的”~”，又叫做tilde，通常會有估計的意思。

如果能計算出在GOSS降低資料樣本的狀況下，可以達到相同或接近的精準度，那代表GOSS的時間複雜度會下降許多，幫助decision tree的生成。

針對近似誤差approximation error（對現有訓練集的訓練誤差），論文中在計算$V_(j|O) （d）$和$V ̃_(j|O) （d）$之間的error差，在$1-δ$的機率會在一個bound內。在bound內，即可以找到$δ,a,b$。

狀況：

• 當$n_l^j （d）≥Ο(√n)$和$n_r^j （d）≥Ο(√n)$時，代表splitting feature選的恰當，代表$2DC_(a,b) √(ln⁡〖1/δ〗/n)$會是比較重要的部分，當在$n→∞$時，近似誤差會趨近於0，代表$V ̃_(j|O) （d）$準確度會接近$V_(j|O) （d）$。
• GOSS會比隨機抽樣表現比較佳。

針對泛化性能generalization ability（指機器學習演算法對新鮮樣本的適應能力），論文以三角不等式：$|a-b|≤|a-c|+|c-b|$的方式證明，當$ε_GOSS (d)$極小時，$ε_gen^GOSS (d)≈ε_gen （d）$，且在抽樣的狀況下也可以增加多樣性，提高犯化性能。 

GOSS優點：

• 計算成本：相較於所有樣本來確定分割點，GOSS可以大大減少計算成本。
• 近似誤差approximation error：相較於隨機抽樣，GOSS不會失去太多訓練精度，在$n→∞$時，$Ο（√n）$，代表近似值會非常準確。
• 泛化性能generalization ability：如果GOSS近似值是準確的，則GOSS的泛化誤差將接近使用完整資料實例計算的誤差。另一方面，抽樣會增加training model的多樣性，這可能有助於提高泛化性能。

Reference

• Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. “LightGBM: A Highly Efficient Gradient Boosting Decision Tree”. In Advances in Neural Information Processing Systems （NIPS）, pp. 3149-3157. 2017.
  https://www.microsoft.com/en-us/research/wp-content/uploads/2017/11/lightgbm.pdf
• LightGBM and XGBoost Explained
  https://mlexplained.com/2018/01/05/lightgbm-and-xgboost-explained/
• 学习笔记——LightGBM（Light Gradient Boosting Machine）
  https://blog.rocuku.cc/lightgbm-summary/
• 快的不要不要的lightGBM
  https://zhuanlan.zhihu.com/p/31986189
• 『我爱机器学习』集成学习（四）LightGBM （有附加code）
  https://www.hrwhisper.me/machine-learning-lightgbm/
• Entropy-Based Decision Tree Induction （as in ID3 and C4.5）
  http://www.cs.bc.edu/~alvarez/ML/id3
• ID3 Pseudocode
  https://www.cs.swarthmore.edu/~meeden/cs63/f05/id3.html
• 資訊的度量- Information Entropy
  https://blog.xuite.net/metafun/life/69851478-%E8%B3%87%E8%A8%8A%E7%9A%84%E5%BA%A6%E9%87%8F-+Information+Entropy
• LightGBM原理分析
  https://www.jianshu.com/p/3daf08229d78
• LightGBM算法论文 A Highly Efficient Gradient Boosting Decision Tree 阅读笔记
  https://huangzhanpeng.github.io/2018/01/04/A-Highly-Ef%EF%AC%81cient-Gradient-Boosting-Decision-Tree/
• 机器学习——LightGBM
  https://www.cnblogs.com/wkslearner/p/9333168.html
• What makes LightGBM lightning fast? https://medium.com/@abhisheksharma_57055/what-makes-lightgbm-lightning-fast-a27cf0d9785e
• Do not lightGBM fast
  http://bazyd.com/do-not-lightgbm-fast/