1 簡(jiǎn)介

本文根據(jù)2017年microsoft研究所等人寫的論文《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》翻譯總結(jié)。

Gradient Boosting Decision Tree (GBDT)已是一個(gè)流行的機(jī)器學(xué)習(xí)方法，也存在一些實(shí)施，例如XGBoost和pGBRT。可以進(jìn)行多類別分類、點(diǎn)擊率預(yù)測(cè)、學(xué)習(xí)排名等應(yīng)用場(chǎng)景。但他們的效率和可擴(kuò)展性還是不太滿意，尤其是針對(duì)高維度數(shù)據(jù)和大數(shù)據(jù)時(shí)。其中一個(gè)主要原因是：對(duì)于每個(gè)特征，他們需要掃描所有的數(shù)據(jù)實(shí)例來評(píng)估所有可能分割點(diǎn)的信息增益，這非常花費(fèi)時(shí)間。

為了解決這個(gè)問題，我們引入了兩項(xiàng)技術(shù)：Gradient-based One-Side Sampling (GOSS) and
Exclusive Feature Bundling (EFB，排除在外特征的捆綁打包). 采用GOSS和EFB的GBDT算法，我們叫做LightGBM。

采用GOSS，我們可以排除相當(dāng)比例的小梯度信息的數(shù)據(jù)實(shí)例，僅使用剩下的數(shù)據(jù)實(shí)例評(píng)估信息增益。擁有大梯度的數(shù)據(jù)實(shí)例在信息增益計(jì)算中扮演重要的角色。
即GOSS用來減少訓(xùn)練數(shù)據(jù)量。

采用EFB，我們可以把互斥的特征（他們很少同時(shí)擁有非零值）打包在一起，來減少特征的數(shù)量。尋找互斥特征的最優(yōu)打包是NP-hard（NP是指多項(xiàng)式復(fù)雜程度的非確定性問題non-deterministic polynomial，縮寫NP）的，但一個(gè)貪婪的算法可以完成很好的近似比率。
即EFB用來減少特征維度。

LightGBM在完成相同正確率的情況下，相比傳統(tǒng)的GBDT有20倍以上的速度。文中主要將LightGBM和XGBoost對(duì)比。

2 預(yù)備知識(shí)

2.1 GBDT及其復(fù)雜度分析

GBDT是決策樹的集成算法，它會(huì)按順序訓(xùn)練。在每個(gè)迭代中，GBDT通過擬合負(fù)梯度（殘差）來學(xué)習(xí)決策樹。

GBDT最主要的時(shí)間花費(fèi)是學(xué)習(xí)決策樹，在學(xué)習(xí)決策樹時(shí)，最花費(fèi)時(shí)間的地方是找到最佳分割點(diǎn)。其中一個(gè)流行的尋找分割點(diǎn)方法是預(yù)排序算法，它會(huì)在預(yù)排序好的特征值上迭代所有可能的分割點(diǎn)。這種算法簡(jiǎn)單，可以找到最優(yōu)的分割點(diǎn)，但是它在訓(xùn)練速度和內(nèi)存使用上效率不高。

另一個(gè)流行的算法是基于直方圖的算法。該算法將連續(xù)的特征值分割到一些離散的箱體中，然后在訓(xùn)練中使用這些箱體來構(gòu)建特征直方圖。該算法在訓(xùn)練速度和內(nèi)存使用上更加有效。LightGBM將擴(kuò)展此方法。

基于直方圖的算法如上圖，其基于特征直方圖尋找最佳分割點(diǎn)。它花費(fèi)O(#data * #feature)來構(gòu)建直方圖，花費(fèi)O(#bin * #feature)進(jìn)行分割點(diǎn)查找。因?yàn)?bin通常比#data小很多，所有構(gòu)建直方圖決定計(jì)算的復(fù)雜度，如果我們減少#data或者#feture，就可以很大的提升GBDT訓(xùn)練速度。

2.2 相關(guān)工作

Scikit-learn 、 gbm in R是預(yù)排序算法；
pGBRT是基于直方圖的算法；
XGBoost支持預(yù)排序和基于直方圖。XGBoost優(yōu)于Scikit-learn 、 gbm in R、pGBRT。本文主要是將LightGBM與XGBoost對(duì)比。

為了減少訓(xùn)練數(shù)據(jù)的大小，常用的方法是下采樣數(shù)據(jù)。例如如果數(shù)據(jù)實(shí)例的權(quán)重小于某個(gè)閾值，就過濾掉。SGB(Stochastic gradient boosting)使用一個(gè)隨機(jī)分組在每個(gè)迭代中訓(xùn)練弱學(xué)習(xí)者。采樣比例可以在訓(xùn)練過程中動(dòng)態(tài)調(diào)整。但是除了SGB，其他算法是基于AdaBoost的，不能直接應(yīng)用于GBDT，因?yàn)闆]有天然的權(quán)重可以用于GBDT的數(shù)據(jù)。雖然SGB可以應(yīng)用于GBDT，但它會(huì)損害準(zhǔn)確率，不是一個(gè)好的選擇。

同時(shí)，對(duì)于減少特征維度，自然也是過濾弱的特征，通常是通常主成分分析或者投影追蹤（projection pursuit）。但是這些方法都假設(shè)特征值們擁有足夠的富裕度，這在實(shí)際中也許并不總是這樣。特征通常是有他們各自獨(dú)特的貢獻(xiàn)，去除特征中的任何一個(gè)都可能影響訓(xùn)練的準(zhǔn)確度。

實(shí)際場(chǎng)景中大數(shù)據(jù)通常是稀疏的。基于預(yù)排序的GBDT可以忽略那些零值，減少訓(xùn)練成本。但是基于直方圖算法的GBDT沒有有效的稀疏優(yōu)化解決方案，因?yàn)槠湫枰』靥卣飨潴w值，無論特征值是零或非零。故基于直方圖算法的GBDT可以有效利益這種稀疏特性。

3 GOSS （Gradient-based One-Side Sampling）

3.1 算法描述

我們發(fā)現(xiàn)在GBDT中，每個(gè)數(shù)據(jù)實(shí)例的梯度對(duì)數(shù)據(jù)采樣提供了有用的信息。
GOSS會(huì)保有帶有大梯度的數(shù)據(jù)實(shí)例，而對(duì)于小梯度的數(shù)據(jù)實(shí)例進(jìn)行隨機(jī)采樣。為了補(bǔ)償對(duì)數(shù)據(jù)分布的影響，在計(jì)算信息增益時(shí)，GOSS對(duì)于小梯度數(shù)據(jù)實(shí)例引入了一個(gè)常數(shù)乘數(shù)。如下圖算法所示。GOSS首先根據(jù)梯度絕對(duì)值對(duì)數(shù)據(jù)實(shí)例排序，然后選擇前面a100%的數(shù)據(jù)。接著從剩下的數(shù)據(jù)中隨機(jī)采樣b100%的實(shí)例。上面完成后，GOSS在計(jì)算信息增益時(shí)，利用一個(gè)常熟因子（1-a）/b 來放大采樣的小梯度數(shù)據(jù)。這樣，我們就可以更加關(guān)注訓(xùn)練不足的實(shí)例，而不會(huì)太改變?cè)紨?shù)據(jù)的分布。

3.2 理論分析

公式較多。對(duì)于GBDT，信息增益通常是通過分割后的方差衡量的。

4 EFB-Exclusive Feature Bundling

高維數(shù)據(jù)通常是稀疏的。在一個(gè)稀疏的特征空間，許多特征是互斥的，即他們不會(huì)同時(shí)取得零值。我們可以把排除在外的特征打包成一個(gè)特征。通過設(shè)計(jì)一個(gè)仔細(xì)小心的特征掃描算法，我們可以將不同特征打包后，形成一樣的特征直方圖。這樣特征直方圖創(chuàng)建的計(jì)算復(fù)雜度從O(#data * #feature) 下降到 O(#data * #bundle)。這樣在不損害準(zhǔn)確性的情況下，提供GBDT訓(xùn)練速度。

有兩個(gè)事情需要考慮，一是哪些特征要被打包在一起，二是如何構(gòu)建這些打包。第一件事是NP-hard的，在多項(xiàng)式時(shí)間內(nèi)找不到一個(gè)準(zhǔn)確的解決方法。

EFB組合了許多稀疏特征，如one-hot 編碼特征、不明顯的除外特征。

5 實(shí)驗(yàn)結(jié)果

所有實(shí)驗(yàn)采用多線程，線程數(shù)量是16。
XGBoost：xgb_exa(pre-sorted algorithm) and xgb_his (histogram-based algorithm)。
EFB (called lgb_baselline)。
Lgb_baseline: LightGBM without GOSS and EFB。

從下別表格2可以看出來LightGBM是最快的算法，GOSS可以提高2倍的速度，EFB是一個(gè)非常有效的算法，可以提升直方圖算法中稀疏屬性的利用，速度提升也很明顯。

總結(jié)

以上是生活随笔為你收集整理的《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》论文笔记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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