集成學習演算法LightGBM
LightGBM
在Kaggle，KDD等各類數據競賽中，無論是分類問題還是回歸問題亦或是排序問題，以GBDT（分類回歸決策樹）為基礎的梯度提升樹，如XGBoost、LightGBM、Thunder Boost等均佔有無撼動的主導地位。尤其是在數據維度（屬性）較少時，特徵工程加XGBoost的pipeline幾乎已經成為了各類比賽的冠軍方案。不得不說先驗知識再加上「分而治之」的方法在特徵維數較低且易於表示時仍然具有「解釋性好」、精度高、速度快等深度神經網路無法媲美的優點（深度神經網路真正取得突破的是在圖像和語音這類特徵抽象，表徵困難其過去進步較小的領域，而NLP中深度網取得的進步仍然有限，這一方要歸咎於數據量的不足，但還有一點是語言的學習從小開始，其已經擁有大量的人工知識）。
Introduction
首先簡單的回顧GBDT的思想（更加詳細的介紹可以參看我的這篇筆記）
PoderLee：集成學習中的XGBoost
對於決策樹的構建主要分為兩類方法，即深度優先（損失更小，與廣度優先相比，在leaf數目相同時樹根深，因此容易造成過擬合，但是構建過程更加靈活且容易在大規模數據集上使用）和廣度優先（樹的構建更加平衡，但是精度較差），決策樹通過「分而治之」的思想將樣本進行分類。在決策樹構建的過程中最困難且最耗時的就是結點的分裂，這裡不同的分裂策略即對應了不同版本的決策樹，如根據信息增益構建ID3，根據信息增益率構建C4.5，根據Gini index構建CART等，split策略的不同也將帶來decision tree的不同偏好。然而單一的決策樹其性能有限，且容易造成過擬合，而通過剪枝或限制樹深等手段雖然能在一定程度上緩解overfitting，但是其精度也將受到損失。因此，研究人員便以決策樹為基學習器，通過集成的思想來提升模型的性能，梯度提升決策樹就是典型代表，此外包括AdaBoost、Random Forest等均被廣泛採用。
GBDT通過迭代生成每一棵樹，每次迭代中通過擬合前一棵樹的殘差使得精度不斷提高，而樹的構建則是使損失函數的負梯度方向為指導原則。然而在每次計算最佳split point時演算法需要遍歷所有數據計算split criterion，這嚴重製約了演算法的速度，因此我們有必要對此改進。
Algorithm
無論是XGB還是LGB均以GBDT為基礎，而GBDT構建的最大困難即使分裂點的選擇，而原始的做法需要演算法遍歷每一屬性的所有數據點計算尋找最優解，該操作的複雜度為 ，因此當數據量較大且特徵較多時，其成本將難以接受。同時我們也觀察到，演算法時間成本與分裂次數正相關而分裂過程中的微小改變不會引起結果的巨大變化，因此基於直方圖的分裂方法則是將特徵值劃分為塊，以bin為最小單位進行分裂而不直接對每個特徵值進行計算。此操作直接將演算法的複雜度減小為
，同時內存空間也顯著減少，然而對於bin數量的選擇將帶來速度與精度的trade-off。此外，bin的劃分方式也多種多樣，最簡單的則是等間隔劃分，然而對於分布不平衡的數據這將帶來很大問題。故XGBoost對於bin的劃分則採用gradient statistics的策略，使其更加平衡。另外，在split過程中經常會出現數據稀疏的問題，XGB和LGB則均是首先忽略所有0元素，然後將缺失數據分配至分割的任意一邊，以減少損失加快訓練速度。
相較於XGBoost，LightBoost最大的改進啊包括以下兩點：
- Subsampling the data: Gradient-based One-Side Sampling(GOSS)
- Exclusive Feature Bundling(EFB)
（1）GOSS
對於所有的數據樣本，其在樹的訓練過程中貢獻度大小不一，擁有較小提度提升的樣本意味著其已被擬合的足夠好，因此貢獻程度較小，而我們真正需要關注的是那先梯度較大的樣本。因此最簡單的想法是在計算分裂時對數據進行採樣，忽略那些梯度較小的數據。然而該操作將帶來改變數據分布的風險，而使得習得的模型將有所偏好。因此為緩和或避免這一風險，LGB同時也在梯度較小的樣本中進行隨機採樣，同時在計算其對損失的contribution時，賦予更大的權重。故GOSS本質上是一種對任意分布依照重要度進行採樣的技術。
從上圖可以看出，對於梯度較小的數據我們從中隨機採樣，比利為「 」，同時為其賦予權值
。而對於梯度較大的數據我們則選擇loss提升最大的前「
」個樣本。
（2）EFB
此外，原始高維數據一般較為稀疏，即其中存在大量相互依存或相互排斥的特徵（多個特徵不能同時取非0值，one-hot編碼），這就啟示我們可以將多個特徵進行合併（「bundled」）處理而不損失任何信息（類似PCA）。然而在所有的特徵中找到最有效的bundle方式是NP難問題，因此作者將其轉化為圖著色的問題，則使用了一種近似的貪心演算法，即允許特徵間存在一定的重疊（個特徵並非完全獨立），如下：
如上圖所示，我們以每個feature作為圖節點，將各feature間的總衝突（反映特徵間的互斥程度）作為邊，構建圖。特徵的合併問題即轉化尋找最小bundles的問題（允許一定的重疊）。而當bundles確定後，每一個bundle其各個特徵的取值範圍都會有所差別，所以在進行特徵融合時為使各個特徵取值不發生重疊（即保證各特徵的差異性），我們對其進行偏置處理，重新分配各特徵的取值範圍以保證各特徵間取值互不相同，然後進行合併。
從上圖可以明顯看出feature1與feature2明顯互斥，因此我們對其進行EFB操作，可以看到feature1的取值範圍為[1,4]（0為nan），為確保合併後各原始特徵不發生重疊，因此我們將feature2加上4（feature1的最大值，bundle size）的偏置，然後進行合併。該操作使得合併後的feature bundle仍能完成保留feature1和feature2的特徵差異，即feature_bundle的5，6代表表feature2，1-4代表feature2。
綜上，通過對梯度提升較小樣本進行隨機採樣操作和合併相關屬性操作，LightGBM在保證精度的前提下獲得了一定的加速。
Conclusion
當前在深度網路這種連接主義「紅得發紫」的時代，以決策樹為代表的符號主義其主要採用「分而治之」的思想，即通過選擇不同的屬性指標，並將其以某種方式組合，從而實現樣本的分類。其中樹的構建採用一種深度優先的演算法，在樹構建的過程中一般希望通過儘可能少的指標組合來竟可能的區分樣本，即希望決策樹的分支結點包含的樣本儘可能屬於同一類別，結點的「純度」越來越高。為了量化純度的和純度提升的大小，這裡定義信息熵、信息增益和基尼係數來直觀反映。其中，ID3決策樹學習演算法是以信息增益為準則來劃分屬性，而信息增益可能會對取值數目較多的屬性有所偏好，這將有可能導致模型過擬合，即模型的泛華能力受到影響，為緩解這種影響，故又定義了信息增益率，然而信息增益率通常會對取值數目較少的屬性有所偏好，因此一般演算法首先從候選的劃分屬性中找出信息增益高於平均水平的屬性，然後在從中選擇增益率最高的屬性。著名的C4.5決策樹即採用「增益率」來選擇最有劃分屬性。此外，相較於信息增益和信息增益率，基尼係數是另一種屬性劃分方法，我們可以使用Gini index構建二叉樹，如著名的GBDT、XGBoost、LightGBM等。此外在樹的構建過程為防止過擬合一般可以採用前剪枝和後剪枝處理。
然而，單棵樹的擬合能力畢竟有限，為提高模型的分類能力則一般採用集成策略。集成分為同質學習（ 個體學習器類型相同）和異質學習（個體學習器類型不同），而針對集成方法的不同其又可以分為串列集成Boosting，即個體學習器間存在強依賴的關係，後一個學習器的生成需依賴前一個學習器的結果；並行集成Bagging，即個體學習器間不存在依賴關係，可以同時訓練多個學習器，適合分散式並行計算。並行集成相較於串列集成其最大的優點就是速度快，但是其精度將會有所損失。
在Boosting演算法簇中，其主要代表包括AdaBoost、GBDT、XGBoost及其改進等。其工作機制大致為：①從初始訓練集中訓練出一個基學習器；②根據基學習器的性能表現調整樣本分布，使得分類錯誤的樣本在後續的訓練中得到更多的關注；③基於調整後的樣本調整訓練下一個基學習器：④重複步驟①、②直至基學習器達到指定數目；⑤對基學習器預測結果進行加權融合，輸出。如AdaBoost則是首先初始化樣本權值分布，訓練初始基學習器，並根據學習器分類結果賦予其權值，同時調整樣本分布權值。然後根據樣本分布不斷訓練基學習器，並不斷調樣本分布權值。最後，根據多個基學習器的權值將各個分類器的結果加權輸出。而GBDT則是以CART為分類器的Boosting演算法，其本質上也是一個加法模型。XGBoost與GBDT相比，其主要區別在於：①誤差函數考慮二階泰勒展開，因此收斂更快；②損失函數中引入正則化項，對樹的複雜程度進行懲罰，以避免過擬合的發生。此外由於XGBoost在每次結點的分裂時均需要遍歷所有數據，這樣即造成了時間成本和空間成本較高的缺陷，於是在此基礎上則有發展出了更快的梯度提升方法，LightGBM。LightGBM與XGBoost相比最大的改進在於其引入了GOSS和EFB操作，即對梯度提升較小的樣本進行隨機採樣同時對相關特徵進行融合，其在保證精度的前提下減少了演算法的計算時間和存儲空間。 相較於Boosting，Bagging則是典型的並行集成方法，其主要思想是通過拔靴法（有放回採樣）隨機抽取多個樣本集同時訓練多個分類器，進行集成。Bagging演算法效率較高，其時間複雜度與訓練基學習器同階。此外Bagging還能很好的適用於回歸和多分類等問題，其中隨機森林演算法被廣泛使用。隨機森林主要思想是在樣本隨機選擇的同時，多棵決策樹的構建過程中每棵決策樹的屬性的選擇也隨機，然後根據選擇屬性構建最優決策樹進行集成。這樣基學習器的多樣性不僅來自於樣本的擾動，同時還來自屬性的擾動，也就是說，隨機森林的隨機性主要體現在兩個方面：（1）樣本的隨機選擇（2） 屬性的隨機選擇。因此隨機森林最終集成的泛華性能和個體學習器的差異進一步加大。此外，由於隨機森林每棵樹的訓練都是獨立的，其並不依賴前一棵樹的分類結果，因此隨機森林天生就適應並行，故其訓練效率和模型的泛化誤差往往均優於Boosting，然而該模型的精度較低（一般情況下低於Boosting幾個百分點）。 總而言之，集成學習的思想已被各類學習器借鑒吸收，此外在工程實踐中其也得到了廣泛的使用。Reference
[1] keitakurita. LightGBM and XGBoost Explained
推薦閱讀：
