本文為通過(guò)文末的學(xué)習(xí)內(nèi)容學(xué)習(xí)后記錄的部分學(xué)習(xí)摘要

LightGBM的提出

常用的機(jī)器學(xué)習(xí)算法，例如神經(jīng)網(wǎng)絡(luò)等算法，都可以以mini-batch（小批量數(shù)據(jù)）的方式訓(xùn)練，訓(xùn)練數(shù)據(jù)的大小不會(huì)受到內(nèi)存限制。而GBDT在每一次迭代的時(shí)候，都需要遍歷整個(gè)訓(xùn)練數(shù)據(jù)多次。如果把整個(gè)訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會(huì)限制訓(xùn)練數(shù)據(jù)的大??；如果不裝進(jìn)內(nèi)存，反復(fù)地讀寫(xiě)訓(xùn)練數(shù)據(jù)又會(huì)消耗非常大的時(shí)間。尤其面對(duì)工業(yè)級(jí)海量的數(shù)據(jù)，普通的GBDT算法是不能滿足其需求的。
為了解決GBDT在海量數(shù)據(jù)遇到的問(wèn)題，讓GBDT可以更好更快地用于工業(yè)實(shí)踐，專家們提出了LightGBM算法。

首先說(shuō)說(shuō)XGBoost

pre-sorted算法

XGBoost在樹(shù)的構(gòu)建過(guò)程中使用的是pre-sorted算法，它能夠更精確的找到數(shù)據(jù)分隔點(diǎn)。
其主要流程如下：

• 首先，對(duì)所有特征按數(shù)值進(jìn)行預(yù)排序。
• 其次，在每次的樣本分割時(shí)，用O(data)的代價(jià)找到每個(gè)特征的最優(yōu)分割點(diǎn)。
• 最后，找到最后的特征以及分割點(diǎn)，將數(shù)據(jù)分裂成左右兩個(gè)子節(jié)點(diǎn)。

這種pre-sorting算法能夠準(zhǔn)確找到分裂點(diǎn)，但是在空間和時(shí)間上有很大的開(kāi)銷。由于需要對(duì)特征進(jìn)行預(yù)排序并且需要保存排序后的索引值（為了后續(xù)快速的計(jì)算分裂點(diǎn)），因此內(nèi)存需要訓(xùn)練數(shù)據(jù)的兩倍。其次，在遍歷每一個(gè)分割點(diǎn)的時(shí)候，都需要進(jìn)行分裂增益的計(jì)算，消耗的代價(jià)大。

level-wise策略

XGBoost采用的是按層生長(zhǎng)level-wise生長(zhǎng)策略，同時(shí)分裂同一層的所有葉子（相當(dāng)于一顆滿二叉樹(shù)），從而進(jìn)行多線程優(yōu)化，不容易過(guò)擬合；但不加區(qū)分的對(duì)待同一層的葉子，帶來(lái)了很多沒(méi)必要的開(kāi)銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂。

LightGBM的優(yōu)勢(shì)

Histogram（直方圖）算法

Histogram algorithm即直方圖算法，它的思想也很簡(jiǎn)單，首先將連續(xù)的浮點(diǎn)數(shù)據(jù)轉(zhuǎn)換為bin數(shù)據(jù)，具體過(guò)程是首先確定對(duì)于每一個(gè)特征需要多少的桶bin，然后均分，將屬于該桶的樣本數(shù)據(jù)更新為bin的值，最后用直方圖表示。

直方圖算法有幾個(gè)需要注意的地方：

• 使用bin替代原始數(shù)據(jù)相當(dāng)于增加了正則化；
• 使用bin意味著很多數(shù)據(jù)的細(xì)節(jié)特征被放棄了，相似的數(shù)據(jù)可能被劃分到相同的桶中，這樣的數(shù)據(jù)之間的差異就消失了；
• bin數(shù)量選擇決定了正則化的程度，bin越少懲罰越嚴(yán)重，欠擬合風(fēng)險(xiǎn)越高。

image

• 構(gòu)建直方圖時(shí)不需要對(duì)數(shù)據(jù)進(jìn)行排序（比XGBoost快），因?yàn)轭A(yù)先設(shè)定了bin的范圍；
• 直方圖除了保存劃分閾值和當(dāng)前bin內(nèi)樣本數(shù)以外還保存了當(dāng)前bin內(nèi)所有樣本的一階梯度和（一階梯度和的平方的均值等價(jià)于均方損失）；
• 閾值的選取是按照直方圖從小到大遍歷，使用了上面的一階梯度和，目的是得到劃分之后△loss最大的特征及閾值。

Histogram算法還可以進(jìn)一步加速。一個(gè)葉子節(jié)點(diǎn)的Histogram可以直接由父節(jié)點(diǎn)的Histogram和兄弟節(jié)點(diǎn)的Histogram做差得到。一般情況下，構(gòu)造Histogram需要遍歷該葉子上的所有數(shù)據(jù)，通過(guò)該方法，只需要遍歷Histogram的k個(gè)捅。速度提升了一倍。

當(dāng)然Histogram 算法也有一定的缺點(diǎn)，Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會(huì)對(duì)結(jié)果產(chǎn)生影響。但在實(shí)際的數(shù)據(jù)集上表明，離散化的分裂點(diǎn)對(duì)最終的精度影響并不大，甚至?xí)靡恍?。原因在于decision tree本身就是一個(gè)弱學(xué)習(xí)器，采用Histogram算法會(huì)起到正則化的效果，有效地防止模型的過(guò)擬合。

直方圖差加速

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

image

leaf-wise策略

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

image

XGBoost采用的是按層生長(zhǎng)level-wise生長(zhǎng)策略，帶來(lái)了很多沒(méi)必要的開(kāi)銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂，而LightGBM采用leaf-wise生長(zhǎng)策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個(gè)葉子，然后分裂，如此循環(huán)。因此同Level-wise相比，在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點(diǎn)是可能會(huì)長(zhǎng)出比較深的決策樹(shù)，產(chǎn)生過(guò)擬合。因此LightGBM在Leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過(guò)擬合。

支持類別特征

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

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

• 可能無(wú)法在這個(gè)類別特征上進(jìn)行切分（即浪費(fèi)了這個(gè)特征）。使用one-hot編碼的話，意味著在每一個(gè)決策節(jié)點(diǎn)上只能使用one vs rest（例如是不是狗，是不是貓等）的切分方式。當(dāng)類別值很多時(shí)，每個(gè)類別上的數(shù)據(jù)可能會(huì)比較少，這時(shí)候切分會(huì)產(chǎn)生不平衡，這意味著切分增益也會(huì)很?。ū容^直觀的理解是，不平衡的切分和不切分沒(méi)有區(qū)別）。
• 會(huì)影響決策樹(shù)的學(xué)習(xí)。因?yàn)榫退憧梢栽谶@個(gè)類別特征進(jìn)行切分，也會(huì)把數(shù)據(jù)切分到很多零碎的小空間上，如圖1左邊所示。而決策樹(shù)學(xué)習(xí)時(shí)利用的是統(tǒng)計(jì)信息，在這些數(shù)據(jù)量小的空間上，統(tǒng)計(jì)信息不準(zhǔn)確，學(xué)習(xí)會(huì)變差。但如果使用下圖右邊的分裂方式，數(shù)據(jù)會(huì)被切分到兩個(gè)比較大的空間，進(jìn)一步的學(xué)習(xí)也會(huì)更好。

下圖右邊葉子節(jié)點(diǎn)的含義是X=A或者X=C放到左孩子，其余放到右孩子。

image

LightGBM處理分類特征大致流程：

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

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

image

下圖是一個(gè)簡(jiǎn)單的對(duì)比實(shí)驗(yàn)，可以看到該最優(yōu)方法在AUC上提升了1.5個(gè)點(diǎn)，并且時(shí)間只多了20%。

image

下面具體來(lái)講下在代碼中如何求解類別特征的最優(yōu)切分的流程：

• 離散特征建立直方圖的過(guò)程：統(tǒng)計(jì)該特征下每一種離散值出現(xiàn)的次數(shù)，并從高到低排序，并過(guò)濾掉出現(xiàn)次數(shù)較少的特征值, 然后為每一個(gè)特征值，建立一個(gè)bin容器, 對(duì)于在bin容器內(nèi)出現(xiàn)次數(shù)較少的特征值直接過(guò)濾掉，不建立bin容器。
• 計(jì)算分裂閾值的過(guò)程：
  • 先看該特征下劃分出的bin容器的個(gè)數(shù)，如果bin容器的數(shù)量小于4，直接使用one vs other方式, 逐個(gè)掃描每一個(gè)bin容器，找出最佳分裂點(diǎn);
  • 對(duì)于bin容器較多的情況, 先進(jìn)行過(guò)濾，只讓子集合較大的bin容器參加劃分閾值計(jì)算, 對(duì)每一個(gè)符合條件的bin容器進(jìn)行公式計(jì)算(公式如下: 該bin容器下所有樣本的一階梯度之和/該bin容器下所有樣本的二階梯度之和 + 正則項(xiàng)(參數(shù)cat_smooth)，這里為什么不是label的均值呢？其實(shí)上例中只是為了便于理解，只針對(duì)了學(xué)習(xí)一棵樹(shù)且是回歸問(wèn)題的情況， 這時(shí)候一階導(dǎo)數(shù)是Y, 二階導(dǎo)數(shù)是1)，得到一個(gè)值，根據(jù)該值對(duì)bin容器從小到大進(jìn)行排序，然后分從左到右、從右到左進(jìn)行搜索，得到最優(yōu)分裂閾值。但是有一點(diǎn)，沒(méi)有搜索所有的bin容器，而是設(shè)定了一個(gè)搜索bin容器數(shù)量的上限值，程序中設(shè)定是32，即參數(shù)max_num_cat。LightGBM中對(duì)離散特征實(shí)行的是many vs many 策略，這32個(gè)bin中最優(yōu)劃分的閾值的左邊或者右邊所有的bin容器就是一個(gè)many集合，而其他的bin容器就是另一個(gè)many集合。
  • 對(duì)于連續(xù)特征，劃分閾值只有一個(gè)，對(duì)于離散值可能會(huì)有多個(gè)劃分閾值，每一個(gè)劃分閾值對(duì)應(yīng)著一個(gè)bin容器編號(hào)，當(dāng)使用離散特征進(jìn)行分裂時(shí)，只要數(shù)據(jù)樣本對(duì)應(yīng)的bin容器編號(hào)在這些閾值對(duì)應(yīng)的bin集合之中，這條數(shù)據(jù)就加入分裂后的左子樹(shù)，否則加入分裂后的右子樹(shù)。

Gradient-based One-Side Sampling（GOSS）

GOSS是一種在減少數(shù)據(jù)量和保證精度上平衡的算法。GOSS是通過(guò)區(qū)分不同梯度的實(shí)例，保留較大梯度實(shí)例同時(shí)對(duì)較小梯度隨機(jī)采樣的方式減少計(jì)算量，從而達(dá)到提升效率的目的。

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

GOSS保留所有的梯度較大的實(shí)例，在梯度小的實(shí)例上使用隨機(jī)采樣。為了抵消對(duì)數(shù)據(jù)分布的影響，計(jì)算信息增益的時(shí)候，GOSS對(duì)小梯度的數(shù)據(jù)引入常量乘數(shù)。GOSS首先根據(jù)數(shù)據(jù)的梯度絕對(duì)值排序，選取top a個(gè)實(shí)例。然后在剩余的數(shù)據(jù)中隨機(jī)采樣b個(gè)實(shí)例。接著計(jì)算信息增益時(shí)為采樣出的小梯度數(shù)據(jù)乘以(1-a)/b，這樣算法就會(huì)更關(guān)注訓(xùn)練不足的實(shí)例，而不會(huì)過(guò)多改變?cè)瓟?shù)據(jù)集的分布。

Exclusive Feature Bundling（EFB）

EFB是通過(guò)特征捆綁的方式減少特征維度（其實(shí)是降維技術(shù)）的方式，來(lái)提升計(jì)算效率。通常被捆綁的特征都是互斥的（一個(gè)特征值為零,一個(gè)特征值不為零），這樣兩個(gè)特征捆綁起來(lái)才不會(huì)丟失信息。如果兩個(gè)特征并不是完全互斥（部分情況下兩個(gè)特征都是非零值），可以用一個(gè)指標(biāo)對(duì)特征不互斥程度進(jìn)行衡量，稱之為沖突比率，當(dāng)這個(gè)值較小時(shí)，我們可以選擇把不完全互斥的兩個(gè)特征捆綁，而不影響最后的精度。

EBF的算法步驟如下：

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

高位的數(shù)據(jù)通常是稀疏的，這種稀疏性啟發(fā)我們?cè)O(shè)計(jì)一種無(wú)損地方法來(lái)減少特征的維度。特別的，稀疏特征空間中，許多特征是互斥的，例如他們從不同時(shí)為非零值。我們可以綁定互斥的特征為單一特征，通過(guò)仔細(xì)設(shè)計(jì)特征臊面算法，我們從特征捆綁中構(gòu)建了與單個(gè)特征相同的特征直方圖。這種方式的直方圖時(shí)間復(fù)雜度從O(data * feature)降到O(data * bundle)，由于bundle << feature，我們能夠極大地加速GBDT的訓(xùn)練過(guò)程而且減小損失精度。

學(xué)習(xí)內(nèi)容

機(jī)器學(xué)習(xí)算法之LightGBM