一、模型介紹

上一篇文章介紹了一個梯度提升決策樹模型 XGBoost，這篇文章我們繼續(xù)學(xué)習(xí)一下 GBDT 模型的另一個進(jìn)化版本：LightGBM。LigthGBM 是 boosting 集合模型中的新成員，由微軟提供，它和 XGBoost 一樣是對 GBDT 的高效實(shí)現(xiàn)，原理上它和 GBDT 及 XGBoost 類似。不過GBDT 在每一次迭代的時候，都需要遍歷整個訓(xùn)練數(shù)據(jù)多次。如果把整個訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會限制訓(xùn)練數(shù)據(jù)的大??；如果不裝進(jìn)內(nèi)存，反復(fù)地讀寫訓(xùn)練數(shù)據(jù)又會消耗非常大的時間。尤其面對工業(yè)級海量的數(shù)據(jù)，普通的 GBDT 算法是不能滿足其需求的。

LightGBM 提出的主要原因就是為了解決 GBDT 在海量數(shù)據(jù)遇到的問題，讓 GBDT 可以更好更快地用于工業(yè)實(shí)踐。LightGBM 在很多方面會比 XGBoost 表現(xiàn)的更為優(yōu)秀。這也是我們這篇文章要介紹的重點(diǎn)內(nèi)容。

二、模型原理

LightGBM 的模型原理和 XGBoost 的模型原理基本一致，具體可參考 XGBoost。不過值得一提的是其中使用的兩個算法: GOSS 和 EFB 。

LightGBM 中的 GOSS 和 EFB 算法

提升樹是利用加模型與前向分布算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過程，它有一些高效實(shí)現(xiàn)，如 XGBoost，GBDT(Gradient Boosting Decision Tree) 等。其中 GBDT 采用負(fù)梯度作為劃分的指標(biāo)（信息增益），XGBoost 則利用到二階導(dǎo)數(shù)。他們共同的不足是，計(jì)算信息增益需要掃描所有樣本，從而找到最優(yōu)劃分點(diǎn)。在面對大量數(shù)據(jù)或者特征維度很高時，它們的效率和擴(kuò)展性很難使人滿意。解決這個問題的直接方法就是減少特征量和數(shù)據(jù)量而且不影響精確度，有部分工作根據(jù)數(shù)據(jù)權(quán)重采樣來加速 booisting 的過程，但由于 GBDT 沒有樣本權(quán)重不能應(yīng)用。

LightGBM（基于GBDT的）則很好的解決這些問題，它主要包含兩個算法：

(1) 單邊梯度采樣，Gradient-based One-Side Sampling（GOSS）

GOSS（從減少樣本角度）：排除大部分小梯度的樣本，僅用剩下的樣本計(jì)算信息增益，它是一種在減少數(shù)據(jù)量和保證精度上平衡的算法。

AdaBoost 中，樣本權(quán)重是數(shù)據(jù)重要性的指標(biāo)。然而在 GBDT 中沒有原始樣本權(quán)重，不能應(yīng)用權(quán)重采樣。幸運(yùn)的是，我們觀察到 GBDT 中每個數(shù)據(jù)都有不同的梯度值，對采樣十分有用。即梯度小的樣本，訓(xùn)練誤差也比較小，說明數(shù)據(jù)已經(jīng)被模型學(xué)習(xí)得很好了，直接想法就是丟掉這部分梯度小的數(shù)據(jù)。然而這樣做會改變數(shù)據(jù)的分布，將會影響訓(xùn)練模型的精確度，為了避免此問題，提出了 GOSS 算法。

GOSS 是一個樣本的采樣算法，目的是丟棄一些對計(jì)算信息增益沒有幫助的樣本留下有幫助的。根據(jù)計(jì)算信息增益的定義，梯度大的樣本對信息增益有更大的影響。因此，GOSS 在進(jìn)行數(shù)據(jù)采樣的時候只保留了梯度較大的數(shù)據(jù)，但是如果直接將所有梯度較小的數(shù)據(jù)都丟棄掉勢必會影響數(shù)據(jù)的總體分布。所以，GOSS 首先將要進(jìn)行分裂的特征的所有取值按照絕對值大小降序排序（XGBoost一樣也進(jìn)行了排序，但是 LightGBM 不用保存排序后的結(jié)果），選取 top a 個實(shí)例。然后在剩余的數(shù)據(jù)中隨機(jī)采樣 b 個實(shí)例。接著計(jì)算信息增益時為采樣出的小梯度數(shù)據(jù)乘以 (1-a)/b，這樣算法就會更關(guān)注訓(xùn)練不足的實(shí)例，而不會過多改變原數(shù)據(jù)集的分布。我們證明此措施在相同的采樣率下比隨機(jī)采樣獲得更準(zhǔn)確的結(jié)果，尤其是在信息增益范圍較大時。

(2) 互斥特征綁定，Exclusive Feature Bundling（EFB）

EFB（從減少特征角度）：EFB是通過特征捆綁的方式減少特征維度（其實(shí)是降維技術(shù)）的方式，來提升計(jì)算效率。

通常真是應(yīng)用中，雖然特征量比較多，但是由于特征空間十分稀疏，是否可以設(shè)計(jì)一種無損的方法來減少有效特征呢？特別在稀疏特征空間上，許多特征幾乎是互斥的（例如許多特征不會同時為非零值，像 one-hot），我們可以捆綁互斥的特征。通常被捆綁的特征都是互斥的（一個特征值為零,一個特征值不為零），這樣兩個特征捆綁起來才不會丟失信息。如果兩個特征并不是完全互斥（部分情況下兩個特征都是非零值），可以用一個指標(biāo)對特征不互斥程度進(jìn)行衡量，稱之為沖突比率，當(dāng)這個值較小時，我們可以選擇把不完全互斥的兩個特征捆綁，而不影響最后的精度。最后，我們將捆綁問題歸約到圖著色問題，通過貪心算法求得近似解。

EBF的算法步驟如下：

• 將特征按照非零值的個數(shù)進(jìn)行排序。
• 計(jì)算不同特征之間的沖突比率。
• 遍歷每個特征并嘗試合并特征，使沖突比率最小化。

當(dāng)然，這里面有兩個非常重要的問題：

• 怎么判定那些特征應(yīng)該綁在一起（build bundled）?
• 怎么把特征綁為一個（merge feature）?

由于這兩個問題過于復(fù)雜，這里只作簡單的思路描述。

bundle（什么樣的特征被綁定）算法流程：

• 建立一個圖，每個點(diǎn)代表特征，每個邊有權(quán)重，其權(quán)重和特征之間總體沖突相關(guān)。
• 按照降序排列圖中的度數(shù)來排序特征。
• 檢查排序之后的每個特征，對他進(jìn)行特征綁定或者建立新的綁定使得操作之后的總體沖突最小。

merging features(特征合并)：

如何合并同一個 bundle 的特征來降低訓(xùn)練時間復(fù)雜度。關(guān)鍵在于原始特征值可以從 bundle 中區(qū)分出來。鑒于直方圖算法存儲離散值而不是連續(xù)特征值，我們通過將互斥特征放在不同的箱中來構(gòu)建 bundle。這可以通過將偏移量添加到特征原始值中實(shí)現(xiàn)，例如，假設(shè) bundle 中有兩個特征，原始特征 A 取值 [0, 10]， B 取值 [0, 20]。我們添加偏移量 10 到 B 中，因此 B 取值 [10, 30]。通過這種做法，就可以安全地將 A、B 特征合并，使用一個取值 [0, 30] 的特征取代 AB。

EFB 算法能夠?qū)⒃S多互斥的特征變?yōu)榈途S稠密的特征，就能夠有效的避免不必要 0 值特征的計(jì)算。實(shí)際，通過用表記錄數(shù)據(jù)中的非零值，來忽略零值特征，達(dá)到優(yōu)化基礎(chǔ)的直方圖算法。通過掃描表中的數(shù)據(jù)，建直方圖的時間復(fù)雜度將從 O(#data) 降到 O(#non_zero_data)。當(dāng)然，這種方法在構(gòu)建樹過程中需要而額外的內(nèi)存和計(jì)算開銷來維持預(yù)特征表。我們在 LightGBM 中將此優(yōu)化作為基本函數(shù)，因?yàn)楫?dāng) bundles 是稀疏的時候，這個優(yōu)化與 EFB 不沖突（可以用于 EFB）。

三、模型細(xì)節(jié)

1. XGBoost 的缺點(diǎn)

(1) 精確貪心算法

每輪迭代時，都需要遍歷整個訓(xùn)練數(shù)據(jù)多次。如果把整個訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會限制訓(xùn)練數(shù)據(jù)的大??；如果不裝進(jìn)內(nèi)存，反復(fù)地讀寫訓(xùn)練數(shù)據(jù)又會消耗非常大的時間。

• 優(yōu)點(diǎn)：可以找到精確的劃分條件。
• 缺點(diǎn)：計(jì)算量巨大，內(nèi)存占用巨大，易產(chǎn)生過擬合。

(2) 預(yù)排序方法（pre-sorted）

首先，空間消耗大。這樣的算法需要保存數(shù)據(jù)的特征值，還保存了特征排序的結(jié)果（例如排序后的索引，為了后續(xù)快速的計(jì)算分割點(diǎn)），這里需要消耗訓(xùn)練數(shù)據(jù)兩倍的內(nèi)存。其次時間上也有較大的開銷，在遍歷每一個分割點(diǎn)的時候，都需要進(jìn)行分裂增益的計(jì)算，消耗的代價大。

• 優(yōu)點(diǎn)：可以使用多線程，可以加速精確貪心算法
• 缺點(diǎn)：效率低下，可能產(chǎn)生不必要的葉結(jié)點(diǎn)

(3) level-wise

生成決策樹是 level-wise 級別的，也就是預(yù)先設(shè)置好樹的深度之后，每一顆樹都需要生長到設(shè)置的那個深度，這樣有些樹在某一次分裂之后效果甚至沒有提升但仍然會繼續(xù)劃分樹枝，然后再次劃分....之后就是無用功了，耗時。

(4) 對 cache 優(yōu)化不友好

在預(yù)排序后，特征對梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣，無法對 cache 進(jìn)行優(yōu)化。同時，在每一層長樹的時候，需要隨機(jī)訪問一個行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會造成較大的 cache miss。

2. LightGBM對Xgboost的優(yōu)化

• 1. 基于Histogram的決策樹算法
• 2. 直方圖做差加速
• 3. 直接支持類別特征 (Categorical Feature)
• 4. 基于直方圖的稀疏特征優(yōu)化
• 5. 帶深度限制的Leaf-wise的葉子生長策略
• 6. Cache命中率優(yōu)化
• 7. 多線程優(yōu)化

(1) Histogram算法

Histogram algorithm 應(yīng)該翻譯為直方圖算法，直方圖算法的思想也很簡單，首先將連續(xù)的浮點(diǎn)數(shù)據(jù)轉(zhuǎn)換為 bin 數(shù)據(jù)，具體過程是首先確定對于每一個特征需要多少的桶 bin，然后均分，將屬于該桶的樣本數(shù)據(jù)更新為 bin 的值，最后用直方圖表示。將連續(xù)的浮點(diǎn)特征離散成 k 個離散值，并構(gòu)造寬度為 k 的 Histogram。然后遍歷訓(xùn)練數(shù)據(jù)，統(tǒng)計(jì)每個離散值在直方圖中的累計(jì)統(tǒng)計(jì)量。在進(jìn)行特征選擇時，只需要根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。

image.png

使用直方圖算法有很多優(yōu)點(diǎn)。首先最明顯就是內(nèi)存消耗的降低，直方圖算法不僅不需要額外存儲預(yù)排序的結(jié)果，而且可以只保存特征離散化后的值，而這個值一般用 8 位整型存儲就足夠了，內(nèi)存消耗可以降低為原來的 1/8。

然后在計(jì)算上的代價也大幅降低，預(yù)排序算法每遍歷一個特征值就需要計(jì)算一次分裂的增益，而直方圖算法只需要計(jì)算 k 次（k可以認(rèn)為是常數(shù)），時間復(fù)雜度從 O(#data#feature) 優(yōu)化到 O(k#features)。

Histogram 算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會對結(jié)果產(chǎn)生影響。但在實(shí)際的數(shù)據(jù)集上表明，離散化的分裂點(diǎn)對最終的精度影響并不大，甚至?xí)靡恍?。原因在?decision tree 本身就是一個弱學(xué)習(xí)器，采用 Histogram 算法會起到正則化的效果，有效地防止模型的過擬合。時間上的開銷由原來的 O(#data * #features) 降到 O(k * #features)。由于離散化，#bin 遠(yuǎn)小于 #data，因此時間上有很大的提升。

Histogram 算法有幾個需要注意的地方：

• 使用 bin 替代原始數(shù)據(jù)相當(dāng)于增加了正則化。
• 使用 bin 意味著很多數(shù)據(jù)的細(xì)節(jié)特征被放棄了，相似的數(shù)據(jù)可能被劃分到相同的桶中，這樣的數(shù)據(jù)之間的差異就消失了。
• bin 數(shù)量選擇決定了正則化的程度，bin 越少懲罰越嚴(yán)重，欠擬合風(fēng)險越高。
• 構(gòu)建直方圖時不需要對數(shù)據(jù)進(jìn)行排序（比XGBoost快），因?yàn)轭A(yù)先設(shè)定了bin的范圍。
• 直方圖除了保存劃分閾值和當(dāng)前 bin 內(nèi)樣本數(shù)以外還保存了當(dāng)前 bin 內(nèi)所有樣本的一階梯度和（一階梯度和的平方的均值等價于均方損失）。
• 閾值的選取是按照直方圖從小到大遍歷，使用了上面的一階梯度和，目的是得到劃分之后 △loss 最大的特征及閾值。

Histogram 算法的優(yōu)缺點(diǎn)：

Histogram 算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會對結(jié)果產(chǎn)生影響。但在實(shí)際的數(shù)據(jù)集上表明，離散化的分裂點(diǎn)對最終的精度影響并不大，甚至?xí)靡恍?。原因在?decision tree 本身就是一個弱學(xué)習(xí)器，采用 Histogram 算法會起到正則化的效果，有效地防止模型的過擬合。時間上的開銷由原來的 O(#data * #features) 降到 O(k * #features) 。由于離散化，#bin 遠(yuǎn)小于 #data，因此時間上有很大的提升。

(2) 直方圖差加速:

LightGBM 另一個優(yōu)化是 Histogram（直方圖）做差加速。一個容易觀察到的現(xiàn)象：一個葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的k個桶。利用這個方法，LightGBM 可以在構(gòu)造一個葉子的直方圖后，可以用非常微小的代價得到它兄弟葉子的直方圖，在速度上可以提升一倍。

(3) 直接支持類別特征:

實(shí)際上大多數(shù)機(jī)器學(xué)習(xí)工具都無法直接支持類別特征，一般需要把類別特征，轉(zhuǎn)化 one-hot 特征，降低了空間和時間的效率。而類別特征的使用是在實(shí)踐中很常用的?；谶@個考慮，LightGBM 優(yōu)化了對類別特征的支持，可以直接輸入類別特征，不需要額外的 0/1 展開。并在決策樹算法上增加了類別特征的決策規(guī)則。

one-hot 編碼是處理類別特征的一個通用方法，然而在樹模型中，這可能并不一定是一個好的方法，尤其當(dāng)類別特征中類別個數(shù)很多的情況下。主要的問題是：

• 可能無法在這個類別特征上進(jìn)行切分（即浪費(fèi)了這個特征）。使用 one-hot 編碼，意味著在每一個決策節(jié)點(diǎn)上只能使用 one vs other 的切分方式。當(dāng)類別值很多時，每個類別上的數(shù)據(jù)可能會比較少，這時候切分會產(chǎn)生不平衡，這意味著切分增益也會很?。ū容^直觀的理解是，不平衡的切分和不切分沒有區(qū)別）。

• 會影響決策樹的學(xué)習(xí)。因?yàn)榫退憧梢栽谶@個類別特征進(jìn)行切分，也會把數(shù)據(jù)切分到很多零碎的小空間上。如下圖左邊所示，而決策樹學(xué)習(xí)時利用的是統(tǒng)計(jì)信息，在這些數(shù)據(jù)量小的空間上，統(tǒng)計(jì)信息不準(zhǔn)確，學(xué)習(xí)會變差。但如果使用下圖右邊的分裂方式，數(shù)據(jù)會被切分到兩個比較大的空間，進(jìn)一步的學(xué)習(xí)也會更好。

  
  
  image.png

為了解決 one-hot 編碼處理類別特征的不足。LightGBM 采用了 many vs many 的切分方式，實(shí)現(xiàn)了類別特征的最優(yōu)切分。用 LightGBM 可以直接輸入類別特征，并產(chǎn)生上圖右邊的效果。在 1 個 k 維的類別特征中尋找最優(yōu)切分，樸素的枚舉算法的復(fù)雜度是 O(2^k)，而LightGBM采用了如 On Grouping For Maximum Homogeneity 的方法實(shí)現(xiàn)了 O(k log k) 的算法。

算法流程下圖所示：在枚舉分割點(diǎn)之前，先把直方圖按每個類別的均值進(jìn)行排序；然后按照均值的結(jié)果依次枚舉最優(yōu)分割點(diǎn)。從下圖可以看到，Sum(y)/Count(y) 為類別的均值。當(dāng)然，這個方法很容易過擬合，所以在 LightGBM 中加入了很多對這個方法的約束和正則化。

image.png

(4) 基于直方圖的稀疏特征優(yōu)化

(5) 帶深度限制的 Leaf-wise 的葉子生長策略

在 Histogram 算法之上，LightGBM 進(jìn)行進(jìn)一步的優(yōu)化。首先它拋棄了大多數(shù) GBDT 工具使用的按層生長 (level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。

• XGBoost 采用的是按層生長 level-wise 生長策略，能夠同時分裂同一層的葉子，從而進(jìn)行多線程優(yōu)化，不容易過擬合；但不加區(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。

• LightGBM 采用 leaf-wise 生長策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個葉子，然后分裂，如此循環(huán)。因此同 Level-wise相比，在分裂次數(shù)相同的情況下，Leaf-wise 可以降低更多的誤差，得到更好的精度。Leaf-wise 的缺點(diǎn)是可能會長出比較深的決策樹，產(chǎn)生過擬合。因此 LightGBM 在 Leaf-wise 之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

(6) Cache 命中率優(yōu)化

(7) 線程優(yōu)化

直接支持高效并行。LightGBM 原生支持并行學(xué)習(xí)，目前支持特征并行和數(shù)據(jù)并行的兩種。特征并行的主要思想是在不同機(jī)器在不同的特征集合上分別尋找最優(yōu)的分割點(diǎn)，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)。數(shù)據(jù)并行則是讓不同的機(jī)器先在本地構(gòu)造直方圖，然后進(jìn)行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)。

image.png

LightGBM 針對這兩種并行方法都做了優(yōu)化，在特征并行算法中，通過在本地保存全部數(shù)據(jù)避免對數(shù)據(jù)切分結(jié)果的通信；在數(shù)據(jù)并行中使用分散規(guī)約 (Reduce scatter) 把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算，并利用直方圖做差，進(jìn)一步減少了一半的通信量。

image.png

基于投票的數(shù)據(jù)并行則進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價，使通信代價變成常數(shù)級別。在數(shù)據(jù)量很大的時候，使用投票并行可以得到非常好的加速效果。

image.png

更具體的內(nèi)容可以看NIPS2016的文章：A Communication-Efficient Parallel Algorithm for Decision Tree

四、模型優(yōu)缺點(diǎn)

五、模型使用

import lightgbm as lgb
model = lgb.LGBMClassifier(boosting_type='gbdt', num_leaves=31, max_depth=-1,
                 learning_rate=0.1, n_estimators=100,
                 subsample_for_bin=200000, objective=None, class_weight=None,
                 min_split_gain=0., min_child_weight=1e-3, min_child_samples=20,
                 subsample=1., subsample_freq=0, colsample_bytree=1.,
                 reg_alpha=0., reg_lambda=0., random_state=None,
                 n_jobs=-1, silent=True, importance_type='split')
model.fit(X_train, y_train, eval_metric='l2',
            eval_set=[(X_train, y_train), (X_eval, y_eval)],
            eval_names=['train', 'evals'],
            early_stopping_rounds=50,
            verbose=500,
            categorical_feature=categorical_feature)
model.predict(test_x)
model.predict_proba(test_x)