基于 Boosting 框架的主流集成算法介紹（下）

2.1.3 互斥特征捆綁算法

高維特征往往是稀疏的，而且特征間可能是相互排斥的（如兩個特征不同時取非零值），如果兩個特征并不完全互斥（如只有一部分情況下是不同時取非零值），可以用互斥率表示互斥程度?；コ馓卣骼壦惴ǎ‥xclusive Feature Bundling, EFB）指出如果將一些特征進(jìn)行融合綁定，則可以降低特征數(shù)量。

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

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

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

1. 構(gòu)造一個加權(quán)無向圖，頂點(diǎn)是特征，邊是兩個特征間互斥程度；
2. 根據(jù)節(jié)點(diǎn)的度進(jìn)行降序排序，度越大，與其他特征的沖突越大；
3. 遍歷每個特征，將它分配給現(xiàn)有特征包，或者新建一個特征包，是的總體沖突最小。

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

我們看到時間復(fù)雜度為 O(#feature^2) ，在特征不多的情況下可以應(yīng)付，但如果特征維度達(dá)到百萬級別，計(jì)算量則會非常大，為了改善效率，我們提出了一個更快的解決方案：將 EFB 算法中通過構(gòu)建圖，根據(jù)節(jié)點(diǎn)度來排序的策略改成了根據(jù)非零值的技術(shù)排序，因?yàn)榉橇阒翟蕉?，互斥的概率會越大?/p>

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

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

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

• Level-wise：基于層進(jìn)行生長，直到達(dá)到停止條件；
• Leaf-wise：每次分裂增益最大的葉子節(jié)點(diǎn)，直到達(dá)到停止條件。

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

2.1.5 類別特征最優(yōu)分割

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

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

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

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

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

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

2.2 工程實(shí)現(xiàn)

2.2.1 特征并行

傳統(tǒng)的特征并行算法在于對數(shù)據(jù)進(jìn)行垂直劃分，然后使用不同機(jī)器找到不同特征的最優(yōu)分裂點(diǎn)，基于通信整合得到最佳劃分點(diǎn)，然后基于通信告知其他機(jī)器劃分結(jié)果。

傳統(tǒng)的特征并行方法有個很大的缺點(diǎn)：需要告知每臺機(jī)器最終劃分結(jié)果，增加了額外的復(fù)雜度（因?yàn)閷?shù)據(jù)進(jìn)行垂直劃分，每臺機(jī)器所含數(shù)據(jù)不同，劃分結(jié)果需要通過通信告知）。

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

2.2.2 數(shù)據(jù)并行

傳統(tǒng)的數(shù)據(jù)并行策略主要為水平劃分?jǐn)?shù)據(jù)，然后本地構(gòu)建直方圖并整合成全局直方圖，最后在全局直方圖中找出最佳劃分點(diǎn)。

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

LightGBM 采用分散規(guī)約（Reduce scatter）的方式將直方圖整合的任務(wù)分?jǐn)偟讲煌瑱C(jī)器上，從而降低通信代價，并通過直方圖做差進(jìn)一步降低不同機(jī)器間的通信。

2.2.3 投票并行

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

大致步驟為兩步：

1. 本地找出 Top K 特征，并基于投票篩選出可能是最優(yōu)分割點(diǎn)的特征；
2. 合并時只合并每個機(jī)器選出來的特征。

2.2.4 緩存優(yōu)化

上邊說到 XGBoost 的預(yù)排序后的特征是通過索引給出的樣本梯度的統(tǒng)計(jì)值，因其索引訪問的結(jié)果并不連續(xù)，XGBoost 提出緩存訪問優(yōu)化算法進(jìn)行改進(jìn)。

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

1. 首先，所有的特征都采用相同的方法獲得梯度（區(qū)別于不同特征通過不同的索引獲得梯度），只需要對梯度進(jìn)行排序并可實(shí)現(xiàn)連續(xù)訪問，大大提高了緩存命中；
2. 其次，因?yàn)椴恍枰鎯μ卣鞯綐颖镜乃饕?，降低了存儲消耗，而且也不存?Cache Miss的問題。

2.3 與 XGBoost 的對比

本節(jié)主要總結(jié)下 LightGBM 相對于 XGBoost 的優(yōu)點(diǎn)，從內(nèi)存和速度兩方面進(jìn)行介紹。

2.3.1 內(nèi)存更小

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

2.3.2 速度更快

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

參考文獻(xiàn)

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