light.png

本文為官方文檔翻譯，點(diǎn)擊查看英文原版。

LightGBM(Light Gradient Boosting Machine)是微軟的開源分布式高性能Gradient Boosting框架，使用基于決策樹的學(xué)習(xí)算法。下面介紹下此框架的優(yōu)化。

1、速度、內(nèi)存方面的優(yōu)化

許多提升工具使用基于預(yù)排序的算法(近似直方圖算法)（例如XGBoost中的默認(rèn)算法）來進(jìn)行決策樹學(xué)習(xí)。這是一個比較簡單的解決方案，但不容易優(yōu)化。LightGBM使用基于直方圖的算法，它將連續(xù)特征值存儲到離散區(qū)間。這可以加快訓(xùn)練速度并減少了內(nèi)存使用量。
1.1 直方圖算法的優(yōu)點(diǎn)

• 降低計算分裂增益的成本

1. 基于預(yù)排序的算法具有時間復(fù)雜性 O(訓(xùn)練樣本的個數(shù))，計算直方圖具有時間復(fù)雜度O(訓(xùn)練樣本的個數(shù))，但這僅當(dāng)在執(zhí)行總結(jié)操作時發(fā)生；
2. 構(gòu)建完直方圖后，基于直方圖的算法具有時間復(fù)雜度O(某個特征不同值的個數(shù))，因為某個特征不同值的個數(shù)遠(yuǎn)小于訓(xùn)練樣本的個數(shù)；

• 使用直方圖的相減進(jìn)一步加速

1. 在計算某個葉子節(jié)點(diǎn)的直方圖時，通過它的父節(jié)點(diǎn)和它的相鄰節(jié)點(diǎn)的直方圖相減，得到；
2. 根據(jù)上條可知，每次分裂僅需要為一個葉子節(jié)點(diǎn)構(gòu)建直方圖，另一個葉子節(jié)點(diǎn)的可以通過直方圖的減法獲得，成本較低；

• 減少內(nèi)存的使用
  用離散箱替換連續(xù)值。如果某個特征不同值的個數(shù)很小，可以使用小數(shù)據(jù)類型，例如uint8_t來存儲訓(xùn)練數(shù)據(jù)，無需存儲用于預(yù)排序特征值的其他信息

• 降低并行學(xué)習(xí)的通信成本

2、針對稀疏特征優(yōu)化

對于稀疏的特征只需要O(2 * 非零值的樣本個數(shù))的時間復(fù)雜度來構(gòu)造直方圖

3、優(yōu)化樹的生長策略來提高準(zhǔn)確率

3.1 最好的葉子節(jié)點(diǎn)優(yōu)先分裂(Leaf_wise)的決策樹生成策
大多數(shù)決策樹學(xué)習(xí)算法生成樹的策略是以同樣的深度生成樹(Level_wise)，生成樹的示例見下圖：

image

而LightGBM以Leaf_wise的方式生成。它將選擇具有最大增益損失的葉子節(jié)點(diǎn)來分裂。當(dāng)兩種方式生成的樹具有相等的葉子節(jié)點(diǎn)時，Leaf_wise策略生成的樹會比Level_wise的擬合度更高。
對于樣本較少的情況，Leaf_wise方式可能會導(dǎo)致過度擬合，因此LightGBM中利用參數(shù)max_depth來限制樹的深度。Leaf_wise方式生成的樹示例如下：

image

3.2 特征的最優(yōu)分割點(diǎn)
通常使用獨(dú)熱編碼來轉(zhuǎn)換分類特征，但這種方法對于決策樹的學(xué)習(xí)并不是有益的。特別是對于不同值較多的特征，獨(dú)熱編碼后構(gòu)建的樹往往是不平衡的，并且需要非常大的深度才能獲得較好的準(zhǔn)確率。
事實上，最佳解決方案是通過將類別劃分為2個子集。如果特征具有K個不同的值，就是在2^(k-1) - 1種情況里找到最優(yōu)的分割點(diǎn)。對于回歸樹而言，有一種解決方案可以保證在O(k * log(k))的時間復(fù)雜度內(nèi)找到最優(yōu)分割點(diǎn)。
找到特征的最優(yōu)分割點(diǎn)的基本思想是根據(jù)訓(xùn)練目標(biāo)的相關(guān)性對類別進(jìn)行重排序。 更具體的說，根據(jù)累加值(sum_gradient / sum_hessian)重新對（類別特征的）直方圖進(jìn)行排序，然后在排好序的直方圖中尋找最優(yōu)的分割點(diǎn)。

4、網(wǎng)絡(luò)通信的優(yōu)化

在LightGBM的并行學(xué)習(xí)中，它只需要使用一些聚合通信算法，如“All reduce”，“All gather”和“Reduce scatter”。LightGBM實現(xiàn)了最先進(jìn)的state-of-art算法。這些聚合通信算法可以提供比點(diǎn)對點(diǎn)通信更好的性能。

5、并行學(xué)習(xí)中的優(yōu)化

LightGBM提供以下并行學(xué)習(xí)算法的優(yōu)化：特征并行、數(shù)據(jù)并行、投票并行。

5.1 特征并行
傳統(tǒng)算法中的特征并行，主要是體現(xiàn)在找到最好的分割點(diǎn)，其步驟為：

1. 垂直分區(qū)數(shù)據(jù)（不同的線程具有不同的數(shù)據(jù)集）；
2. 在本地數(shù)據(jù)集上找到最佳分割點(diǎn)，包括特征，閾值；
3. 再進(jìn)行各個劃分的通信整合并得到最佳劃分；
4. 以最佳劃分方法對數(shù)據(jù)進(jìn)行劃分，并將數(shù)據(jù)劃分結(jié)果傳遞給其他線程；
5. 其他線程對接受到的數(shù)據(jù)進(jìn)一步劃分；

傳統(tǒng)特征并行的缺點(diǎn)：

1. 計算成本較大，傳統(tǒng)特征并行沒有實現(xiàn)得到"split"（時間復(fù)雜度為“O（訓(xùn)練樣本的個數(shù))"）的加速。當(dāng)數(shù)據(jù)量很大的時候，難以加速；
2. 需要對劃分的結(jié)果進(jìn)行通信整合，其額外的時間復(fù)雜度約為 “O（訓(xùn)練樣本的個數(shù)/8）”（一個數(shù)據(jù)一個字節(jié)）；

LightGBM中的并行特征

由于特征并行在訓(xùn)練樣本的個數(shù)大的時候不能很好地加速，LightGBM做了以下優(yōu)化：不是垂直分割數(shù)據(jù)，而是每個線程都擁有完整的全部數(shù)據(jù)。因此，LightGBM不需要為分割數(shù)據(jù)結(jié)果進(jìn)行通信，因為每個線程都知道如何劃分?jǐn)?shù)據(jù)。并且訓(xùn)練樣本的個數(shù)不會變大，因此這種方案是合理的。

LightGBM中實現(xiàn)特征并行的過程：

1. 每個線程在本地數(shù)據(jù)集上找到最佳分割點(diǎn)，包括特征，閾值；
2. 本地進(jìn)行各個劃分的通信整合并得到最佳劃分；
3. 執(zhí)行最佳劃分；

然而，該并行算法在數(shù)據(jù)量很大時仍然存在計算上的局限。因此，建議在數(shù)據(jù)量很大時使用數(shù)據(jù)并行。

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

傳統(tǒng)算法數(shù)據(jù)并行旨在并行化整個決策學(xué)習(xí)。數(shù)據(jù)并行的過程是：

1. 水平劃分?jǐn)?shù)據(jù)；
2. 線程以本地數(shù)據(jù)構(gòu)建本地直方圖；
3. 將本地直方圖整合成全局直方圖；
4. 在全局直方圖中尋找最佳劃分，然后執(zhí)行此劃分；

傳統(tǒng)數(shù)據(jù)并行的缺點(diǎn)：通信成本高。如果使用點(diǎn)對點(diǎn)通信算法，則一臺機(jī)器的通信成本約為O(#machine * #feature * #bin)。如果使用聚合通信算法（例如“All Reduce”），通信成本約為O(2 * #feature * #bin)。

LightGBM中的數(shù)據(jù)并行

LightGBM中通過下面方法來降低數(shù)據(jù)并行的通信成本：

1. 不同于“整合所有本地直方圖以形成全局直方圖”的方式，LightGBM 使用分散規(guī)約(Reduce scatter)的方式對不同線程的不同特征（不重疊的）進(jìn)行整合。 然后線程從本地整合直方圖中尋找最佳劃分并同步到全局的最佳劃分中；
2. LightGBM通過直方圖的減法加速訓(xùn)練。 基于此，我們可以進(jìn)行單葉子節(jié)點(diǎn)的直方圖通訊，并且在相鄰直方圖上作減法；

通過上述方法，LightGBM 將數(shù)據(jù)并行中的通訊開銷減少到O(0.5 * #feature * #bin)。

5.3 投票并行
投票并行進(jìn)一步降低了數(shù)據(jù)并行中的通信成本，使其減少至常數(shù)級別。它使用兩階段投票來降低特征直方圖的通信成本。

6、GPU支持

參見英文文檔

7、支持的應(yīng)用和度量

7.1 應(yīng)用

• 回歸，目標(biāo)函數(shù)是L2損失
• 二進(jìn)制分類，目標(biāo)函數(shù)是logloss(對數(shù)損失)
• 多分類
• 交叉熵，目標(biāo)函數(shù)是logloss，支持非二進(jìn)制標(biāo)簽的訓(xùn)練
• lambdarank，目標(biāo)函數(shù)為基于NDCG的lambdarank

7.2 度量

• L1 loss：絕對值損失
• L2 loss：MSE，平方損失
• Log loss：對數(shù)損失
• 分類錯誤率
• AUC（Area Under Curve）：ROC曲線下的面積
• NDCG（Normalized Discounted Cumulative Gain）：歸一化折損累積增益
• MAP（Mean Average Precision）：平均精度均值
• 多類別對數(shù)損失
• 多類別分類錯誤率
• Fair損失
• Huber損失
• Possion：泊松回歸
• Quantile：分位數(shù)回歸
• MAPE（Mean Absolute Percent Error）：平均絕對百分比誤差
• kullback_leibler：Kullback-Leibler divergence
• gamma：negative log-likelihood for Gamma regression
• tweedie：negative log-likelihood for Tweedie regression
• 更多閱讀原文

7.3 其他

• 限制樹的最大深度max_depth
• DART：Dropouts meet Multiple Additive Regression Trees
• L1 / L2正則化
• 套袋
• 隨即選擇列(特征)子集
• Continued train with input GBDT model
• Continued train with the input score file
• Weighted training
• Validation metric output during training
• 交叉驗證
• Multi metrics
• 提前停止（訓(xùn)練和預(yù)測）
• Prediction for leaf index
• 更多閱讀原文

image

LightGBM實例

一、北京市Pm2.5回歸預(yù)測
參數(shù)選擇圖

image

image

二、成年人收入分類
參數(shù)選擇圖

image

image

實例代碼：LightGBM，掃描下方二維碼或者微信公眾號直接搜索”Python范兒“，關(guān)注微信公眾號pythonfan， 獲取更多實例和代碼。

pythonfan.jpg