LightGBM explained系列——Exclusive Feature Bundling（EFB）是什麼？

之前有介紹

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）是什麼？

這次是介紹一下，LightGBM用來降維的演算法 "Exclusive Feature Bundling"
中文名稱翻作"獨立特徵合併"

Lightgbm explained-Exclusive Feature Bundling（EFB）

Exclusive Feature Bundling（EFB） 獨立特徵合併

LightGBM從直方圖優化演算法的想法出發，EFB演算法也是用bundle的方法進行互斥特徵的合併，從而減少特徵的數目，是LightGBM用來降維的演算法。

前情提要：

一個有高維（high-dimensional）特徵空間的資料往往是稀疏的，而稀疏的特徵空間中，許多特徵是互斥（mutually exclusive）的。

「互斥」的定義：這些特徵從來不會同時具有非零值。

特徵A（是否是零值）	特徵B（是否是零值）	是否互斥
O	O	否
X	O	否
O	X	否
X	X	是（同時有非零值）

註：

Jason Brownlee在A Gentle Introduction to Sparse Matrices for Machine Learning提到”Matrices that contain mostly zero values are called sparse, distinct from matrices where most of the values are non-zero, called dense.”

換句話說，稀疏的矩陣會有很多零值，緊密的矩陣會有很多非零值。

當矩陣出現空值時，1.面臨記憶體上的考驗 2.增加時間複雜度O（N^3），所以EFB是要解決這個大問題。

機器學習中的訓練資料往往都是幾千萬維（特徵很多）的稀疏資料，例如：one-hot encoding所產生大量的類別特徵，每多一個特徵就增加一個維度。而GBDT演算法在劃分節點時，需要考慮所有特徵，因此EFB演算法對不同維度的資料合併在一起使得一個稀疏（sparse）陣列變成一個稠密（dense）矩陣，減少不必要的特徵（降維）。

這裡有兩個問題：

1. 如何決定將哪些特徵該合併成一個bundle？
2. 如何將bundle內的特徵合併為新的特徵？

Greedy Bundling演算法：

1.如何決定將哪些特徵該合併成一個bundle？

將互斥/相互獨立（mutually exclusive）的特徵合併是一個NP難問題，把特徵看作是G中的點V，共有|V|個特徵，特徵之間的總衝突看作是圖中的邊E。而尋找合併特徵且使得合併的bundle個數最小，這是一個圖著色問題（GCP），需要使用近似的貪婪演算法來完成。

https://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Petersen_graph_3-coloring.svg/1920px-Petersen_graph_3-coloring.svg.png

註：圖著色問題（Graph Coloring Problem；GCP）是最著名的NP-完全問題之一。

1.對與錯問題（Determinant） 2.優化問題（Optimization）

給定一個無向圖$G=(V,E)$，其中$V$為頂點集合，$E$為邊集合，圖著色問題即為將$V$分為K個顏色組，每個組形成一個獨立集，即其中沒有相鄰的頂點。其優化版本是希望獲得最小的K值。

步驟：

1. 建立一個”帶權圖”G註：將所有特徵視為G的頂點，將不是互斥的頂點（特徵）用一條邊連接起來，每個邊有權重（weight）：兩個相連接的特徵的之間的衝突值（cnt），多種計算方法1.相乘2.零的個數3.內積 $〈a,b〉=‖a‖‖b‖  cos⁡θ$，需要合併的特徵就是在GCP中要塗上同一種顏色的那些點。
2. searchOrder:按照降冪排列圖中的度數（Degree）來排序特徵。註：度數越大=非零值越多，其他點（特徵）的衝突越大。
3. 檢查每個searchOrder中的每個特徵，對於當前特徵i，有兩種狀況：

(1)   當cnt + bundlesConflict[i]≦K: max conflict count （needNew = False），將i合併到使得衝突最小（$γ$決定大小）的bundle:bundles[j]。

(2)   當needNew = True，建立一個新的bundle:F[i]。

優化：

1.通常只有少量的特徵之間並非100%互斥，但是絕大多數情況下並不會同時有非零值。若構建bundle的演算法允許小的衝突，就能得到更少數的bundle，進一步提高效率。可以證明，隨機的污染（polluting）一部分特徵則最多影響精確度 $O([1-γ]n)^(-2/3)$，$γ$ 為最大的特徵衝突率；如果γ極小，就可以在速度和準確度之間達到平衡。

設j特徵的最大variance gain為$V_j$、最大variance gain為$V$。如果隨機汙染rate是$γ$，隨機污染的最大variance gain為$V^γ$。在第$j_1$特徵$V=V_(j_1 )$，在第$j_2$特徵$V^γ=V_(j_2)^γ$。

→有無隨機汙染的最大誤差會被限制在$|V-V^γ |≤[（1-γ）n]^(-2/3)$（n代表訓練資料量）

2.演算法複雜度為O（#feature^2），當特徵數很大的時候，仍然效率不高。為了繼續提高效率，LightGBM提出一個更加高效的無圖的排序策略：將特徵按照非零值個數排序，這和使用圖節點的度數排序相似，因為更多的非零值通常會導致衝突，新EFB演算法在之前演算法基礎上改變了排序策略。（這也是一種貪婪作法）

Merge Exclusive features演算法（MEF）：

2.如何將bundle內的特徵合併為新的特徵？

在同一個bundle裡合併幾個特徵，最重要的是需要保證合併前的原始特徵值可以在新的bundle中識別。考慮到直方圖優化演算法將連續的特徵值保存在各個離散的bins，MEF演算法將互斥特徵分到bundle中的不同bins中，透過對原始特徵的值添加偏移/偏置常量（offset）來實現。

例如：一個bundle中有兩個特徵A和B，A∈[0,10), B∈[0,20)。

將特徵B添加偏移量10，使得B的值域範圍變為B∈[10,30)；此時，即可將A和B合併成值域為[0,30]新特徵取代原先的A和B。

由於每一個bundle當中，特徵的值域範圍都是不一樣，所以我們需要重新構建合併後bundle特徵的值域範圍。

• 第一個for迴圈當中，計算每個特徵與之前特徵的累積總值域範圍（binRanges）。

• 第二個for迴圈當中，根據binRanges重新計算出新的bin值域範圍（如果F[j].bin[i]≠0，newBin[i] = F[j].bin[i] + binRanges[j]）。

註：針對於稀疏陣列進行優化。由於先前Greedy Bundling演算法對特徵進行衝突檢查，確保bundle內特徵衝突盡可能少，所以特徵之間的非零元素不會有太多的衝突。

EFB演算法好處：

建立長條圖的時間複雜度將從O（#feature×#data）變為O（#bundle×#data），而#bundle<<#feature。EFB演算法不僅降低了資料特徵規模，還提高了模型的訓練速度，這樣GBDT能在精準度不損失的情況下進一步提高訓練速度。

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://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://zhuanlan.zhihu.com/p/31986189
• LightGBM新特性总结
  https://www.cnblogs.com/wmx24/p/9699793.html
• lightGBM
  http://www.arvinzyy.cn/2017/11/18/lightGBM/
• 『我爱机器学习』集成学习（四）LightGBM
  https://www.hrwhisper.me/machine-learning-lightgbm/
• A Gentle Introduction to Sparse Matrices for Machine Learning https://machinelearningmastery.com/sparse-matrices-for-machine-learning/