一、?前言

最近在做Kaggle比賽的時候，看到別人的Kenels中都用到了lightgbm，自己也試圖用了一下，發(fā)現(xiàn)效果很好，最重要的是它相對于XGBoost算法，大大的降低了運行的速度。所以就對Lightgbm的原理探了個究竟，這里就對Lightgbm論文的理解以及對官網(wǎng)上對Lightgbm的介紹做一個學(xué)習(xí)筆記。

傳統(tǒng)的boosting算法（如GBDT和XGBoost）已經(jīng)有相當(dāng)好的效率，但是在如今的大樣本和高維度的環(huán)境下，傳統(tǒng)的boosting似乎在效率和可擴展性上不能滿足現(xiàn)在的需求了，主要的原因就是傳統(tǒng)的boosting算法需要對每一個特征都要掃描所有的樣本點來選擇最好的切分點，這是非常的耗時。為了解決這種在大樣本高緯度數(shù)據(jù)的環(huán)境下耗時的問題，Lightgbm使用了如下兩種解決辦法：一是GOSS（Gradient-based One-Side Sampling,?基于梯度的單邊采樣），不是使用所用的樣本點來計算梯度，而是對樣本進行采樣來計算梯度；二是EFB（Exclusive?Feature?Bundling，?互斥特征捆綁） ，這里不是使用所有的特征來進行掃描獲得最佳的切分點，而是將某些特征進行捆綁在一起來降低特征的維度，是尋找最佳切分點的消耗減少。這樣大大的降低的處理樣本的時間復(fù)雜度，但在精度上，通過大量的實驗證明，在某些數(shù)據(jù)集上使用Lightgbm并不損失精度，甚至有時還會提升精度。下面就主要介紹這兩種方法。

本文的主要內(nèi)容，首先介紹GOSS和EFB方法，然后再根據(jù)Lightgbm官網(wǎng)的介紹，談一談Lightgbm的特性以及調(diào)參。

二、Gradient-based One-Side Sampling（GOSS）介紹

GOSS（基于梯度的單邊采樣）方法的主要思想就是，梯度大的樣本點在信息增益的計算上扮演著主要的作用，也就是說這些梯度大的樣本點會貢獻更多的信息增益，因此為了保持信息增益評估的精度，當(dāng)我們對樣本進行下采樣的時候保留這些梯度大的樣本點，而對于梯度小的樣本點按比例進行隨機采樣即可。

2.1 GOSS算法

在AdaBoost算法中，我們在每次迭代時更加注重上一次錯分的樣本點，也就是上一次錯分的樣本點的權(quán)重增大，而在GBDT中并沒有本地的權(quán)重來實現(xiàn)這樣的過程，所以在AdaBoost中提出的采樣模型不能應(yīng)用在GBDT中。但是，每個樣本的梯度對采樣提供了非常有用的信息。也就是說，如果一個樣本點的梯度小，那么該樣本點的訓(xùn)練誤差就小并且已經(jīng)經(jīng)過了很好的訓(xùn)練。一個直接的辦法就是直接拋棄梯度小的樣本點，但是這樣做的話會改變數(shù)據(jù)的分布和損失學(xué)習(xí)的模型精度。GOSS的提出就是為了避免這兩個問題的發(fā)生。下面就是GOSS算法的偽代碼：

下面將對上述算法進行描述。

2.2 GOSS算法描述

輸入：訓(xùn)練數(shù)據(jù)，迭代步數(shù)d，大梯度數(shù)據(jù)的采樣率a，小梯度數(shù)據(jù)的采樣率b，損失函數(shù)和若學(xué)習(xí)器的類型（一般為決策樹）；

輸出：訓(xùn)練好的強學(xué)習(xí)器；

（1）根據(jù)樣本點的梯度的絕對值對它們進行降序排序；

（2）對排序后的結(jié)果選取前a*100%的樣本生成一個大梯度樣本點的子集；

（3）對剩下的樣本集合（1-a）*100%的樣本，隨機的選取b*（1-a）*100%個樣本點，生成一個小梯度樣本點的集合；

（4）將大梯度樣本和采樣的小梯度樣本合并；

（5）將小梯度樣本乘上一個權(quán)重系數(shù)；

（6）使用上述的采樣的樣本，學(xué)習(xí)一個新的弱學(xué)習(xí)器；

（7）不斷地重復(fù)（1）~（6）步驟直到達到規(guī)定的迭代次數(shù)或者收斂為止。

通過上面的算法可以在不改變數(shù)據(jù)分布的前提下不損失學(xué)習(xí)器精度的同時大大的減少模型學(xué)習(xí)的速率。

從上面的描述可知，當(dāng)a=0時，GOSS算法退化為隨機采樣算法；當(dāng)a=1時，GOSS算法變?yōu)椴扇≌麄€樣本的算法。在許多情況下，GOSS算法訓(xùn)練出的模型精確度要高于隨機采樣算法。另一方面，采樣也將會增加若學(xué)習(xí)器的多樣性，從而潛在的提升了訓(xùn)練出的模型泛化能力。

三、Exclusive?Feature?Bundling（EFB）介紹

Lightgbm實現(xiàn)中不僅進行了數(shù)據(jù)采樣，也進行了特征抽樣，使得模型的訓(xùn)練速度進一步的減少。但是該特征抽樣又與一般的特征抽樣有所不同，是將互斥特征綁定在一起從而減少特征維度。主要思想就是，通常在實際應(yīng)用中高緯度的數(shù)據(jù)往往都是稀疏數(shù)據(jù)（如one-hot編碼），這使我們有可能設(shè)計一種幾乎無損的方法來減少有效特征的數(shù)量。尤其，在稀疏特征空間中許多特征都是互斥的（例如，很少同時出現(xiàn)非0值）。這就使我們可以安全的將互斥特征綁定在一起形成一個特征，從而減少特征維度。但是怎樣的將互斥特征綁定在一起了？Lightgbm作者使用的是基于直方圖（histograms）的方法。

3.1?EFB算法

由于將特征劃分為更小的互斥綁定數(shù)量，這是一個NP-hard問題，即在多項式時間內(nèi)不可能去找到準(zhǔn)確的解決辦法。所以這里使用的是一種近似的解決辦法，即特征之間允許存在少數(shù)的樣本點并不是互斥的（如存在某些對應(yīng)的樣本點之間不同時為非0值），允許小部分的沖突可以得到更小的特征綁定數(shù)量，更進一步的提高了計算的有效性。在理論上可以證明，通過允許小部分的沖突的話，使得模型的accuracy被影響，這里的是每個綁定的最大沖突率。所以，當(dāng)我們選擇很小的時，我們可以在精確度和效率上獲得很好的權(quán)衡。下面就是互斥特征綁定（Exclusive?Feature?Bundling）的算法：

下面將對上述算法進行描述。

3.2?EFB算法描述

輸入：特征F，最大沖突數(shù)K，圖G；

輸出：特征捆綁集合bundles；

（1）構(gòu)造一個邊帶有權(quán)重的圖，其權(quán)值對應(yīng)于特征之間的總沖突；

（2）通過特征在圖中的度來降序排序特征；

（3）檢查有序列表中的每個特征，并將其分配給具有小沖突的現(xiàn)有bundling（由控制），或創(chuàng)建新bundling。

上述算法的時間復(fù)雜度為并且在模型訓(xùn)練之前僅僅被處理一次即可。在特征維度不是很大時，這樣的復(fù)雜度是可以接受的。但是當(dāng)樣本維度較高時，這種方法就會特別的低效。所以對于此，作者又提出的另外一種更加高效的算法：按非零值計數(shù)排序，這類似于按度數(shù)排序，因為更多的非零值通常會導(dǎo)致更高的沖突概率。?這僅僅改變了上述算法的排序策略，所以只是針對上述算法將按度數(shù)排序改為按非0值數(shù)量排序，其他不變。

3.3?合并互斥特征

Lightgbm關(guān)于互斥特征的合并用到了直方圖（Histogram）算法。直方圖算法的基本思想是先把連續(xù)的特征值離散化成k個整數(shù)，同時構(gòu)造一個寬度為k的直方圖。在遍歷數(shù)據(jù)的時候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點。

由于基于直方圖的算法存儲的是離散的bins而不是連續(xù)的特征值，我們可以通過讓互斥特征駐留在不同的bins中來構(gòu)造feature bundle。這可以通過增加特征原始值的偏移量來實現(xiàn)。比如，假設(shè)我們有兩個特征，特征A的取值范圍是[0,10)，而特征B的取值范圍是[0,20)，我們可以給特征B增加偏移量10，使得特征B的取值范圍為[10, 30)，最后合并特征A和B，形成新的特征，取值范圍為[0,30)來取代特征A和特征B。

當(dāng)然，Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點，所以會對結(jié)果產(chǎn)生影響。但在不同的數(shù)據(jù)集上的結(jié)果表明，離散化的分割點對最終的精度影響并不是很大，甚至有時候會更好一點。原因是決策樹本來就是弱模型，分割點是不是精確并不是太重要；差一點的切分點也有正則化的效果，可以有效地防止過擬合；即使單棵樹的訓(xùn)練誤差比精確分割的算法稍大，但在Gradient Boosting的框架下沒有太大的影響。

Histogram算法有如下的一些優(yōu)點：

（1）減少分割增益的計算量：xgboost中默認(rèn)使用的是pre-sorted算法，需要次的計算，而Histogram算法只需要計算次，并且遠小于；

（2）通過直方圖相減來進一步的加速模型的訓(xùn)練：在二叉樹中可以通過利用葉節(jié)點的父節(jié)點和相鄰節(jié)點的直方圖的相減來獲得該葉節(jié)點的直方圖。所以僅僅需要為一個葉節(jié)點建立直方圖 (其小于它的相鄰節(jié)點)就可以通過直方圖的相減來獲得相鄰節(jié)點的直方圖，而這花費的代價（）很小。

（3）減少內(nèi)存的使用：可以將連續(xù)的值替換為離散的bins。 如果較小, 可以利用較小的數(shù)據(jù)類型來存儲訓(xùn)練數(shù)據(jù)并且無需為 pre-sorting 特征值存儲額外的信息。

（4）減少并行學(xué)習(xí)的通信代價。

我們稱使用GOSS算法和EFB算法的梯度提升樹（GBDT）稱之為LightGBM。

四、Lightgbm的一些其它特性

4.1?Leaf-wise的決策樹生長策略

大部分決策樹的學(xué)習(xí)算法通過 level-wise 策略生長樹，記一次分裂同一層的葉子，不加區(qū)分的對待同一層的葉子，而實際上很多葉子的分裂增益較低沒必要進行分裂，帶來了沒必要的開銷。如下圖：

LightGBM 通過 leaf-wise 策略來生長樹。每次從當(dāng)前所有葉子中，找到分裂增益最大的一個葉子，然后分裂，如此循環(huán)。因此同Level-wise相比，在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。但是，當(dāng)樣本量較小的時候，leaf-wise 可能會造成過擬合。 所以，LightGBM 可以利用額外的參數(shù)?max_depth?來限制樹的深度并避免過擬合。

4.2?類別特征值的最優(yōu)分割

對于類別型的數(shù)據(jù)，我們通常將類別特征轉(zhuǎn)化為one-hot/啞變量編碼。 然而，對于學(xué)習(xí)樹來說這不是個好的解決方案。 原因是，對于一個基數(shù)較大的類別特征，學(xué)習(xí)樹會生長的非常不平衡，并且需要非常深的深度才能來達到較好的準(zhǔn)確率。

事實上，最好的解決方案是將類別特征劃分為兩個子集，總共有種可能的切分。比如有一個顏色特征，每個樣本的顏色特征是{紅、黃、藍、綠}四種類別中的一種，如果使用ne-hot/啞變量編碼很好理解這里不再敘述，但是如果使用LightGBM的切分策略，就是將紅、黃、藍、綠對應(yīng)的四類樣本分為兩類的所有可能策略，比如：紅黃一類，藍綠一類。那么就會有 種策略，這樣才能充分的挖掘該維特征所包含的信息，找到最優(yōu)的分割策略。?但是這樣尋找最優(yōu)分割策略的時間復(fù)雜度就會很大。對于回歸樹有個有效的解決方案。為了尋找最優(yōu)的劃分需要大約??。基本的思想是根據(jù)訓(xùn)練目標(biāo)的相關(guān)性對類別進行重排序。 更具體的說，根據(jù)累加值()重新對（類別特征的）直方圖進行排序，然后在排好序的直方圖中尋找最好的分割點。

4.3?Lightgbm中的并行學(xué)習(xí)

4.3.1?特征并行

1、傳統(tǒng)算法的的特征并行

傳統(tǒng)的特征并行算法旨在于在并行化決策樹中的尋找最佳切分點，主要流程如下：

（1）垂直切分?jǐn)?shù)據(jù)（不同的Worker有不同的特征集）；

（2）在本地特征集尋找最佳切分點 {特征, 閾值}；

（3）在各個機器之間進行通信，拿出自己的最佳切分點，然后從所有的最佳切分點中推舉出一個最好的切分點，作為全局的切分點；

（4）以最佳劃分方法對數(shù)據(jù)進行劃分，并將數(shù)據(jù)劃分結(jié)果傳遞給其他Worker；

（5）其他Worker對接受到的數(shù)據(jù)進一步劃分。

2、傳統(tǒng)的特征并行方法主要不足:

（1）存在計算上的局限，傳統(tǒng)特征并行無法加速特征切分（時間復(fù)雜度為 ）。 因此，當(dāng)數(shù)據(jù)量很大的時候，難以加速。

（2）需要對劃分的結(jié)果進行通信整合，其額外的時間復(fù)雜度約為。（一個數(shù)據(jù)一個字節(jié)）

3、LightGBM 中的特征并行

在數(shù)據(jù)量很大時，傳統(tǒng)并行方法無法有效地對特征進行并行，LightGBM 做了一些改變：不再垂直劃分?jǐn)?shù)據(jù)，即每個Worker都持有全部數(shù)據(jù)。 因此，LighetGBM中沒有數(shù)據(jù)劃分結(jié)果之間通信的開銷，各個Worker都知道如何劃分?jǐn)?shù)據(jù)。 而且，樣本量也不會變得更大，所以，使每個機器都持有全部數(shù)據(jù)是合理的。

LightGBM 中特征并行的流程如下：

（1）每個Worker都在本地特征集上尋找最佳劃分點｛特征， 閾值｝；

（2）本地進行各個劃分的通信整合并得到最佳劃分；

（3）執(zhí)行最佳劃分。

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

4.3.2?數(shù)據(jù)并行

1、傳統(tǒng)的數(shù)據(jù)并行算法

數(shù)據(jù)并行目的是并行化整個決策學(xué)習(xí)過程。數(shù)據(jù)并行的主要流程如下：

（1）水平劃分?jǐn)?shù)據(jù)；

（2）Worker以本地數(shù)據(jù)構(gòu)建本地直方圖；

（3）將所有Worker的本地直方圖整合成全局整合圖；

（4）在全局直方圖中尋找最佳切分，然后執(zhí)行此切分。

2、傳統(tǒng)數(shù)據(jù)并行的不足：

高通訊開銷。 如果使用點對點的通訊算法，一個Worker的通訊開銷大約為。 如果使用集體通訊算法（例如， “All Reduce”等），通訊開銷大約為。

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

LightGBM 中通過減少數(shù)據(jù)并行過程中的通訊開銷，來減少數(shù)據(jù)并行的開銷：

（1）不同于傳統(tǒng)數(shù)據(jù)并行算法中的，整合所有本地直方圖以形成全局直方圖的方式，LightGBM 使用Reduce scatter的方式對不同Worker的不同特征（不重疊的）進行整合。 然后Worker從本地整合直方圖中尋找最佳劃分并同步到全局的最佳劃分中。

（2）如上面提到的，LightGBM 通過直方圖做差法加速訓(xùn)練。 基于此，我們可以進行單葉子的直方圖通訊，并且在相鄰直方圖上使用做差法。

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

4.3.3?投票并行

投票并行進一步的減少數(shù)據(jù)并行的的通信消耗為常數(shù)級別。它使用兩階段的投票來減少特征直方圖的通信消耗。

五、LightGBM中的主要調(diào)節(jié)的參數(shù)

5.1?針對 Leaf-wise（Best-first）樹的參數(shù)優(yōu)化

（1）num_leaves這是控制樹模型復(fù)雜度的主要參數(shù)。理論上, 借鑒 depth-wise 樹, 我們可以設(shè)置?num_leaves=??但是, 這種簡單的轉(zhuǎn)化在實際應(yīng)用中表現(xiàn)不佳. 這是因為, 當(dāng)葉子數(shù)目相同時, leaf-wise 樹要比 depth-wise 樹深得多, 這就有可能導(dǎo)致過擬合. 因此, 當(dāng)我們試著調(diào)整?num_leaves?的取值時, 應(yīng)該讓其小于?. 舉個例子, 當(dāng)?max_depth=7時，depth-wise 樹可以達到較高的準(zhǔn)確率.但是如果設(shè)置?num_leaves?為?128?時, 有可能會導(dǎo)致過擬合, 而將其設(shè)置為?70?或?80?時可能會得到比 depth-wise 樹更高的準(zhǔn)確率. 其實,?depth?的概念在 leaf-wise 樹中并沒有多大作用, 因為并不存在一個從?leaves?到?depth?的合理映射。

（2）min_data_in_leaf. 這是處理 leaf-wise 樹的過擬合問題中一個非常重要的參數(shù). 它的值取決于訓(xùn)練數(shù)據(jù)的樣本個樹和?num_leaves. 將其設(shè)置的較大可以避免生成一個過深的樹, 但有可能導(dǎo)致欠擬合. 實際應(yīng)用中, 對于大數(shù)據(jù)集, 設(shè)置其為幾百或幾千就足夠了。

（3）max_depth（默認(rèn)不限制，一般設(shè)置該值為5—10即可）?你也可以利用?max_depth?來顯式地限制樹的深度。

5.2?針對更快的訓(xùn)練速度

（1）通過設(shè)置?bagging_fraction?和?bagging_freq?參數(shù)來使用 bagging 方法；

（2）通過設(shè)置?feature_fraction?參數(shù)來使用特征的子抽樣；

（3）使用較小的?max_bin；

（4）使用?save_binary?在以后的學(xué)習(xí)過程對數(shù)據(jù)進行加速加載。

5.3?針對更好的準(zhǔn)確率

（1）使用較大的?max_bin?（學(xué)習(xí)速度可能變慢）；

（2）使用較小的?learning_rate?和較大的?num_iterations；

（3）使用較大的?num_leaves?（可能導(dǎo)致過擬合）；

（4）使用更大的訓(xùn)練數(shù)據(jù)；

（5）嘗試?dart（一種在多元Additive回歸樹種使用dropouts的算法）.

5.4?處理過擬合

（1）使用較小的?max_bin（默認(rèn)為255）

（2）使用較小的?num_leaves（默認(rèn)為31）

（3）使用?min_data_in_leaf（默認(rèn)為20）?和?min_sum_hessian_in_leaf（默認(rèn)為）

（4）通過設(shè)置?bagging_fraction?（默認(rèn)為1.0）和?bagging_freq?（默認(rèn)為0，意味著禁用bagging，k表示每k次迭代執(zhí)行一個bagging）來使用 bagging

（5）通過設(shè)置?feature_fraction（默認(rèn)為1.0）?來使用特征子抽樣

（6）使用更大的訓(xùn)練數(shù)據(jù)

（7）使用?lambda_l1（默認(rèn)為0）,?lambda_l2?（默認(rèn)為0）和?min_split_gain（默認(rèn)為0，表示執(zhí)行切分的最小增益）?來使用正則

（8）嘗試?max_depth?來避免生成過深的樹

六、參考文獻

（1）LightGBM: A Highly Efficient Gradient Boosting Decision Tree?論文

（2）LightGBM官網(wǎng)

總結(jié)

以上是生活随笔為你收集整理的Lightgbm基本原理介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。