2.1.3 互斥特征捆綁算法

高維特征往往是稀疏的，而且特征間可能是相互排斥的（如兩個特征不同時取非零值），如果兩個特征并不完全互斥（如只有一部分情況下是不同時取非零值），可以用互斥率表示互斥程度。互斥特征捆綁算法（Exclusive Feature Bundling, EFB）指出如果將一些特征進行融合綁定，則可以降低特征數量。

針對這種想法，我們會遇到兩個問題：

1. 哪些特征可以一起綁定？
2. 特征綁定后，特征值如何確定？

對于問題一：EFB 算法利用特征和特征間的關系構造一個加權無向圖，并將其轉換為圖著色算法。我們知道圖著色是個 NP-Hard 問題，故采用貪婪算法得到近似解，具體步驟如下：

1. 構造一個加權無向圖，頂點是特征，邊是兩個特征間互斥程度；
2. 根據節點的度進行降序排序，度越大，與其他特征的沖突越大；
3. 遍歷每個特征，將它分配給現有特征包，或者新建一個特征包，是的總體沖突最小。

算法允許兩兩特征并不完全互斥來增加特征捆綁的數量，通過設置最大互斥率 來平衡算法的精度和效率。EFB 算法的偽代碼如下所示：

我們看到時間復雜度為 O(#feature^2) ，在特征不多的情況下可以應付，但如果特征維度達到百萬級別，計算量則會非常大，為了改善效率，我們提出了一個更快的解決方案：將 EFB 算法中通過構建圖，根據節點度來排序的策略改成了根據非零值的技術排序，因為非零值越多，互斥的概率會越大。

對于問題二：論文給出特征合并算法，其關鍵在于原始特征能從合并的特征中分離出來。假設 Bundle 中有兩個特征值，A 取值為 [0, 10]、B 取值為 [0, 20]，為了保證特征 A、B 的互斥性，我們可以給特征 B 添加一個偏移量轉換為 [10, 30]，Bundle 后的特征其取值為 [0, 30]，這樣便實現了特征合并。具體算法如下所示：

2.1.4 帶深度限制的 Leaf-wise 算法

在建樹的過程中有兩種策略：

• Level-wise：基于層進行生長，直到達到停止條件；
• Leaf-wise：每次分裂增益最大的葉子節點，直到達到停止條件。

XGBoost 采用 Level-wise 的增長策略，方便并行計算每一層的分裂節點，提高了訓練速度，但同時也因為節點增益過小增加了很多不必要的分裂，降低了計算量；LightGBM 采用 Leaf-wise 的增長策略減少了計算量，配合最大深度的限制防止過擬合，由于每次都需要計算增益最大的節點，所以無法并行分裂。

2.1.5 類別特征最優分割

大部分的機器學習算法都不能直接支持類別特征，一般都會對類別特征進行編碼，然后再輸入到模型中。常見的處理類別特征的方法為 one-hot 編碼，但我們知道對于決策樹來說并不推薦使用 one-hot 編碼：

1. 會產生樣本切分不平衡問題，切分增益會非常小。如，國籍切分后，會產生是否中國，是否美國等一系列特征，這一系列特征上只有少量樣本為 1，大量樣本為 0。這種劃分的增益非常小：較小的那個拆分樣本集，它占總樣本的比例太小。無論增益多大，乘以該比例之后幾乎可以忽略；較大的那個拆分樣本集，它幾乎就是原始的樣本集，增益幾乎為零；
2. 影響決策樹學習：決策樹依賴的是數據的統計信息，而獨熱碼編碼會把數據切分到零散的小空間上。在這些零散的小空間上統計信息不準確的，學習效果變差。本質是因為獨熱碼編碼之后的特征的表達能力較差的，特征的預測能力被人為的拆分成多份，每一份與其他特征競爭最優劃分點都失敗，最終該特征得到的重要性會比實際值低。

LightGBM 原生支持類別特征，采用 many-vs-many 的切分方式將類別特征分為兩個子集，實現類別特征的最優切分。假設有某維特征有 k 個類別，則有 2^{(k-1)} - 1 中可能，時間復雜度為 O(2^k) ，LightGBM 基于 Fisher 大佬的 《On Grouping For Maximum Homogeneity》實現了 O(klog_2k) 的時間復雜度。

上圖為左邊為基于 one-hot 編碼進行分裂，后圖為 LightGBM 基于 many-vs-many 進行分裂，在給定深度情況下，后者能學出更好的模型。

其基本思想在于每次分組時都會根據訓練目標對類別特征進行分類，根據其累積值 \\frac{\\sum gradient }{\\sum hessian} 對直方圖進行排序，然后在排序的直方圖上找到最佳分割。此外，LightGBM 還加了約束條件正則化，防止過擬合。

我們可以看到這種處理類別特征的方式使得 AUC 提高了 1.5 個點，且時間僅僅多了 20%。

2.2 工程實現

2.2.1 特征并行

傳統的特征并行算法在于對數據進行垂直劃分，然后使用不同機器找到不同特征的最優分裂點，基于通信整合得到最佳劃分點，然后基于通信告知其他機器劃分結果。

傳統的特征并行方法有個很大的缺點：需要告知每臺機器最終劃分結果，增加了額外的復雜度（因為對數據進行垂直劃分，每臺機器所含數據不同，劃分結果需要通過通信告知）。

LightGBM 則不進行數據垂直劃分，每臺機器都有訓練集完整數據，在得到最佳劃分方案后可在本地執行劃分而減少了不必要的通信。

2.2.2 數據并行

傳統的數據并行策略主要為水平劃分數據，然后本地構建直方圖并整合成全局直方圖，最后在全局直方圖中找出最佳劃分點。

這種數據劃分有一個很大的缺點：通訊開銷過大。如果使用點對點通信，一臺機器的通訊開銷大約為 O(#machine * #feature *#bin ) ；如果使用集成的通信，則通訊開銷為 O(2 * #feature *#bin ) ，

LightGBM 采用分散規約（Reduce scatter）的方式將直方圖整合的任務分攤到不同機器上，從而降低通信代價，并通過直方圖做差進一步降低不同機器間的通信。

2.2.3 投票并行

針對數據量特別大特征也特別多的情況下，可以采用投票并行。投票并行主要針對數據并行時數據合并的通信代價比較大的瓶頸進行優化，其通過投票的方式只合并部分特征的直方圖從而達到降低通信量的目的。

大致步驟為兩步：

1. 本地找出 Top K 特征，并基于投票篩選出可能是最優分割點的特征；
2. 合并時只合并每個機器選出來的特征。

2.2.4 緩存優化

上邊說到 XGBoost 的預排序后的特征是通過索引給出的樣本梯度的統計值，因其索引訪問的結果并不連續，XGBoost 提出緩存訪問優化算法進行改進。

而 LightGBM 所使用直方圖算法對 Cache 天生友好：

1. 首先，所有的特征都采用相同的方法獲得梯度（區別于不同特征通過不同的索引獲得梯度），只需要對梯度進行排序并可實現連續訪問，大大提高了緩存命中；
2. 其次，因為不需要存儲特征到樣本的索引，降低了存儲消耗，而且也不存在 Cache Miss的問題。

2.3 與 XGBoost 的對比

本節主要總結下 LightGBM 相對于 XGBoost 的優點，從內存和速度兩方面進行介紹。

2.3.1 內存更小

1. XGBoost 使用預排序后需要記錄特征值及其對應樣本的統計值的索引，而 LightGBM 使用了直方圖算法將特征值轉變為 bin 值，且不需要記錄特征到樣本的索引，將空間復雜度從 O(2*#data) 降低為 O(#bin) ，極大的減少了內存消耗；
2. LightGBM 采用了直方圖算法將存儲特征值轉變為存儲 bin 值，降低了內存消耗；
3. LightGBM 在訓練過程中采用互斥特征捆綁算法減少了特征數量，降低了內存消耗。

2.3.2 速度更快

1. LightGBM 采用了直方圖算法將遍歷樣本轉變為遍歷直方圖，極大的降低了時間復雜度；
2. LightGBM 在訓練過程中采用單邊梯度算法過濾掉梯度小的樣本，減少了大量的計算；
3. LightGBM 采用了基于 Leaf-wise 算法的增長策略構建樹，減少了很多不必要的計算量；
4. LightGBM 采用優化后的特征并行、數據并行方法加速計算，當數據量非常大的時候還可以采用投票并行的策略；
5. LightGBM 對緩存也進行了優化，增加了 Cache hit 的命中率。

參考文獻

1. XGBoost: A Scalable Tree Boosting System
2. 陳天奇論文演講 PPT