文章目錄

• lightGBM 簡(jiǎn)介
• 直方圖算法(Histogram algorithm)
• • 基本思想
  • 直方圖做差
  • 帶深度限制的 Leaf-wise 算法
• 單邊梯度采樣算法(GOSS)
• 互斥特征捆綁算法(EFB)
• • 1，解決哪些特征應(yīng)該綁在一起
  • 2，解決怎么把特征綁為一捆
• LightGBM的工程優(yōu)化
• • 1，原生支持類別特征
  • 2，高效并行
  • • 特征并行
    • 數(shù)據(jù)并行
    • 投票并行
  • 3，Cache命中率優(yōu)化
• LightGBM的優(yōu)缺點(diǎn)
• • 缺點(diǎn)
• 參考文章

lightGBM 簡(jiǎn)介

GBDT是個(gè)經(jīng)典的模型，主要是利用弱分類器（決策樹）迭代訓(xùn)練以得到最優(yōu)模型，該模型具有訓(xùn)練效果好、不易過擬合等優(yōu)點(diǎn)，常被用于多分類、點(diǎn)擊率預(yù)測(cè)、搜索排序等任務(wù)。

在LightGBM提出之前，還有個(gè)GBDT的高效實(shí)現(xiàn)：XGBoost。XGBoost是屬于boosting家族，也是GBDT算法的一個(gè)工程實(shí)現(xiàn)。 在模型的訓(xùn)練過程中是聚焦殘差，在目標(biāo)函數(shù)中使用了二階泰勒展開并加入了正則，在決策樹的生成過程中采用近似分割的方式（可以理解為分桶的思路），選出一些候選的分裂點(diǎn)，然后再遍歷這些較少的分裂點(diǎn)，計(jì)算按照這些候選分裂點(diǎn)位分裂后的全部樣本的目標(biāo)函數(shù)增益，找到最大的那個(gè)增益對(duì)應(yīng)的特征和候選分裂點(diǎn)位，從而進(jìn)行分裂。這樣一層一層的完成建樹過程， XGBoost訓(xùn)練的時(shí)候，是通過加法的方式進(jìn)行訓(xùn)練，也就是每一次通過聚焦殘差訓(xùn)練一棵樹出來， 最后的預(yù)測(cè)結(jié)果是所有樹的加和表示。

對(duì)于上面的過程，不難發(fā)現(xiàn)時(shí)間復(fù)雜度和空間復(fù)雜度比較高：

首先就是空間消耗很大，因?yàn)轭A(yù)排序的話既需要保存數(shù)據(jù)的特征值， 還得保存特征排序后的索引，畢竟這樣后續(xù)計(jì)算分割點(diǎn)的時(shí)候快一些，但是這樣就需要消耗訓(xùn)練數(shù)據(jù)兩倍的內(nèi)存。

其次， 時(shí)間上也有很大的開銷，在遍歷每一個(gè)分割點(diǎn)的時(shí)候，都需要進(jìn)行分裂增益的計(jì)算，消耗的代價(jià)大。

總的來說，XGBoost尋找最優(yōu)分裂點(diǎn)的復(fù)雜度由下面三個(gè)因素構(gòu)成：
$$特征數(shù)量\times 分裂點(diǎn)的數(shù)量\times 樣本的數(shù)量$$
LightGBM（Light Gradient Boosting Machine）也是一個(gè)實(shí)現(xiàn)GBDT算法的框架，支持高效率的并行訓(xùn)練，并且具有更快的訓(xùn)練速度、更低的內(nèi)存消耗、更好的準(zhǔn)確率、支持分布式可以快速處理海量數(shù)據(jù)等優(yōu)點(diǎn)。它主要對(duì)上面的三個(gè)因素分別優(yōu)化，下面提到的1，直方圖算法就是為了減少分裂點(diǎn)的數(shù)量， 2，單邊梯度抽樣算法就是為了減少樣本的數(shù)量，3， 互斥特征捆綁算法就是為了減少特征的數(shù)量。 并且后面兩個(gè)是Lightgbm的亮點(diǎn)所在。

直方圖算法(Histogram algorithm)

基本思想

直方圖算法的基本思想是：先把連續(xù)的浮點(diǎn)特征值離散化成 k 個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為 k 的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積計(jì)數(shù)，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。如下圖所示：

XGBoost 在進(jìn)行預(yù)排序時(shí)只考慮非零值進(jìn)行加速，而 LightGBM 也采用類似策略：只用非零特征構(gòu)建直方圖。這種離散化分桶思路其實(shí)有很多優(yōu)點(diǎn)的， 首先最明顯就是內(nèi)存消耗的降低，XGBoost 需要用32位的浮點(diǎn)數(shù)去存儲(chǔ)特征值， 并用32位的整型去存儲(chǔ)索引：

而Lightgbm的直方圖算法不僅不需要額外存儲(chǔ)預(yù)排序的結(jié)果，而且可以只保存特征離散化后的值，而這個(gè)值一般用8位整型存儲(chǔ)就足夠了，即內(nèi)存消耗從32+32變?yōu)榱?，降低為原來的1/8。

同時(shí)，計(jì)數(shù)復(fù)雜度也大幅度降低，XGBoost的預(yù)排序算法每遍歷一個(gè)特征值就需要計(jì)算一次分裂的增益，而Lightgbm直方圖算法只需要計(jì)算k次（k可以認(rèn)為是常數(shù)）：

時(shí)間復(fù)雜度從：
$$O((特征取值個(gè)數(shù)?1)\times 特征個(gè)數(shù))$$
變?yōu)?#xff1a;
$$O((分桶數(shù)?1)\times 特征個(gè)數(shù))$$
其中，特征取值個(gè)遠(yuǎn)大于分桶樹。

直方圖做差

實(shí)際上，直方圖算法還可以進(jìn)一步加速。一般情況下，構(gòu)造直方圖需要遍歷該葉子上的所有數(shù)據(jù)才行。但是對(duì)于二叉樹而言，一個(gè)葉子節(jié)點(diǎn)的直方圖可以直接由父節(jié)點(diǎn)的直方圖和兄弟節(jié)點(diǎn)的直方圖做差得到：

通過該方法，只需要遍歷直方圖的k個(gè)捅，速度提升了一倍。

舉個(gè)例子，假設(shè)有15個(gè)訓(xùn)練樣本，2個(gè)特征$x_1,x_2$, 然后我先對(duì)這兩個(gè)特征進(jìn)行分桶:

把$x_1$根據(jù)取值分成4個(gè)桶，每個(gè)桶里面的樣本個(gè)數(shù)分別是5, 4, 4, 3。

把$x_2$根據(jù)取值也分成4個(gè)桶，每個(gè)桶里面的樣本個(gè)數(shù)分別是4, 4, 5, 3。

然后我遍歷特征，每個(gè)特征我遍歷候選分割點(diǎn)(分桶后)，發(fā)現(xiàn)在$x_1$的第一個(gè)候選點(diǎn)那收益比較大，則第一個(gè)候選點(diǎn)進(jìn)行分裂成兩個(gè)節(jié)點(diǎn)。如下圖所示 :

可以看到，直方圖算法可以起到的作用就是可以減小分割點(diǎn)的數(shù)量， 加快計(jì)算。直方圖算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會(huì)對(duì)結(jié)果產(chǎn)生影響。但在實(shí)際的數(shù)據(jù)集上表明，離散化的分裂點(diǎn)對(duì)最終的精度影響并不大，甚至?xí)靡恍Ｔ蛟谟跊Q策樹本身就是一個(gè)弱學(xué)習(xí)器，分割點(diǎn)是不是精確并不是太重要，采用直方圖算法會(huì)起到正則化的效果，有效地防止模型的過擬合（分桶的數(shù)量決定了正則化的程度，分桶數(shù)越少懲罰越嚴(yán)重，欠擬合風(fēng)險(xiǎn)越高）。

XGBoost 使用的近似分割算法其實(shí)也有類似直方圖算法的思想，但是他的分桶策略基于Weight Quantile Sketch算法，也就是基于二階導(dǎo)的值 hi 來選擇劃分點(diǎn)。可以理解為所有樣本都共享二階導(dǎo) hi 構(gòu)成的直方圖，一旦數(shù)據(jù)被分割，數(shù)據(jù)的分布就變了，導(dǎo)致 hi 的計(jì)算結(jié)果也發(fā)生變化，因此每次分裂都得重新構(gòu)建直方圖。

而對(duì) lightgbm 而言，每個(gè)特征都有一個(gè)直方圖，分裂后還能通過直方圖做差來進(jìn)行加速，因此速度要快于 XGBoost。

帶深度限制的 Leaf-wise 算法

直方圖算法，不僅有趣也很有效率。這還沒有結(jié)束，在直方圖算法之上，LightGBM進(jìn)行進(jìn)一步的優(yōu)化。首先它拋棄了大多數(shù)GBDT工具使用的按層生長 (level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。

XGBoost 采用 Level-wise 的增長策略，該策略遍歷一次數(shù)據(jù)可以同時(shí)分裂同一層的所有葉節(jié)點(diǎn)，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過擬合。過程如下圖所示：

但實(shí)際上Level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，實(shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂，因此帶來了很多沒必要的計(jì)算開銷。

LightGBM采用Leaf-wise的增長策略，該策略每次從當(dāng)前所有葉子中，找到分裂增益最大的一個(gè)葉子，然后分裂，如此循環(huán)。

因此同Level-wise相比，Leaf-wise的優(yōu)點(diǎn)是：在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度；Leaf-wise的缺點(diǎn)是：可能會(huì)長出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM會(huì)在Leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過擬合。

單邊梯度采樣算法(GOSS)

我們觀察到GBDT中每個(gè)數(shù)據(jù)都有不同的梯度值，即梯度小的樣本，訓(xùn)練誤差也比較小，說明數(shù)據(jù)已經(jīng)被模型學(xué)習(xí)得很好了，直接想法就是丟掉這部分梯度小的數(shù)據(jù)。然而這樣做會(huì)改變數(shù)據(jù)的分布，將會(huì)影響訓(xùn)練模型的精確度，為了避免此問題，提出了單邊梯度抽樣算法。

單邊梯度抽樣算法(Gradient-based One-Side Sampling)是從減少樣本的角度出發(fā)， 排除大部分權(quán)重小的樣本，僅用梯度大的樣本和少數(shù)梯度小的樣本計(jì)算信息增益，它是一種在減少數(shù)據(jù)和保證精度上平衡的算法。

具體來說，GOSS在進(jìn)行數(shù)據(jù)采樣的時(shí)候只保留了梯度較大的樣本，對(duì)于梯度較小的樣本，如果全部丟棄會(huì)影響數(shù)據(jù)的總體分布，因此需要對(duì)梯度小的樣本進(jìn)行采樣。GOSS首先將要進(jìn)行分裂的特征的所有取值按照絕對(duì)值大小降序排序，僅僅保存絕對(duì)值最大的 $a?100\%$ 個(gè)數(shù)據(jù)。然后在剩下的較小梯度數(shù)據(jù)中隨機(jī)選擇 $b?100\%$個(gè)數(shù)據(jù)。既然小梯度的樣本數(shù)量比較少，那么可以給與樣本更大的權(quán)重$\frac{1?a}{b}$，這樣算法一方面會(huì)更關(guān)注訓(xùn)練不足的樣本，另一方面不至于過多的改變?cè)紨?shù)據(jù)集的分布。

算法流程如下：

舉個(gè)例子，假設(shè) $a=\frac{1}{4}，b=\frac{1}{4}$，對(duì)于下面的數(shù)據(jù)：

對(duì)一階導(dǎo)降序排序，得到：

然后選擇 8*1/4=2 個(gè)梯度大的樣本，再從剩下的 8 - 2=6 個(gè)小梯度樣本中隨機(jī)采樣出 8*1/4=2 個(gè)，例如選出了2號(hào)和4號(hào)樣本：

可以發(fā)現(xiàn)上面選擇到的數(shù)據(jù)分布在不同的桶內(nèi)：

對(duì)于采樣得到的2號(hào)和4號(hào)樣本，還需要乘上一個(gè)權(quán)重系數(shù)$\frac{1?a}{b}=3$，減少分布的變化，對(duì)于6號(hào)和7號(hào)樣本則無需此操作。具體而言，這個(gè)系數(shù)是乘在樣本個(gè)數(shù)、一階導(dǎo)數(shù)和二階導(dǎo)上的：

梯度小的樣本乘上相應(yīng)的權(quán)重之后，可以發(fā)現(xiàn)樣本個(gè)數(shù) $N_i$ 的總個(gè)數(shù)依然是8個(gè)， 雖然6個(gè)梯度小的樣本中去掉了4個(gè)，留下了兩個(gè)。 但是這2個(gè)樣本在梯度上和個(gè)數(shù)上都進(jìn)行了3倍的放大，所以可以防止采樣對(duì)原數(shù)數(shù)據(jù)分布造成太大的影響， 這也就是論文里面說的將更多的注意力放在訓(xùn)練不足的樣本上的原因。

通過這樣的方式，在不過分降低精度的同時(shí)，減少了用于訓(xùn)練的樣本數(shù)量，使得訓(xùn)練速度得到了加快。

互斥特征捆綁算法(EFB)

高維度的數(shù)據(jù)往往是稀疏的，這種稀疏性啟發(fā)我們?cè)O(shè)計(jì)一種無損的方法來減少特征的維度。通常被捆綁的特征都是互斥的（即特征不會(huì)同時(shí)為非零值，像one-hot），這樣兩個(gè)特征捆綁起來才不會(huì)丟失信息。如果兩個(gè)特征并不是完全互斥（部分情況下兩個(gè)特征都是非零值），可以用一個(gè)指標(biāo)對(duì)特征不互斥程度進(jìn)行衡量，稱之為沖突比率，當(dāng)這個(gè)值較小時(shí)，我們可以選擇把不完全互斥的兩個(gè)特征捆綁，而不影響最后的精度。

舉個(gè)例子說明特征捆綁在做什么：

上圖中原始數(shù)據(jù)的形式很類似于one-hot編碼，可以將上面的4個(gè)特征捆綁到一起，達(dá)到減少特征維度的作用。上面的例子比較特殊，被捆綁的特征都是互斥的（即特征不會(huì)同時(shí)為非零值，像one-hot），這樣兩個(gè)特征捆綁起來才不會(huì)丟失信息。實(shí)際情況下，很多特征之間存在沖突(存在某個(gè)樣本的兩個(gè)特征同時(shí)不為零)，可以用一個(gè)指標(biāo)對(duì)特征不互斥程度進(jìn)行衡量，稱之為沖突比率，當(dāng)這個(gè)值較小時(shí)，我們可以選擇把不完全互斥的兩個(gè)特征捆綁，而不影響最后的精度。這樣，構(gòu)建直方圖時(shí)的時(shí)間復(fù)雜度就從：
$$O(數(shù)據(jù)數(shù)量\times 特征數(shù)量)$$
變?yōu)?#xff1a;
$$O(數(shù)據(jù)數(shù)量\times 捆綁特征數(shù)量)$$
顯然捆綁特征數(shù)量遠(yuǎn)少于特征數(shù)量，可以達(dá)到加速的效果。

說到這里，會(huì)遇到兩個(gè)問題：

怎么判定哪些特征應(yīng)該綁在一起（build bundled）？

怎么把特征綁為一個(gè)（merge feature）？

1，解決哪些特征應(yīng)該綁在一起

LightGBM的EFB算法將這個(gè)問題轉(zhuǎn)化為圖著色的問題來求解，將所有的特征視為圖的各個(gè)頂點(diǎn)，將不是相互獨(dú)立的特征用一條邊連接起來，邊的權(quán)重就是兩個(gè)相連接的特征的總沖突值，這樣需要綁定的特征就是在圖著色問題中要涂上同一種顏色的那些點(diǎn)（特征）。舉個(gè)例子：

此外，我們注意到通常有很多特征，盡管不是100％相互排斥，但也很少同時(shí)取非零值。上面這個(gè)過程的時(shí)間復(fù)雜度其實(shí)是$O(特征{數(shù)}^2)$的，因?yàn)橐闅v特征，每個(gè)特征還要遍歷所有的簇， 在特征不多的情況下還行，但是如果特征維度很大，就不好使了。 所以為了改善效率，可以不建立圖，而是將特征按照非零值個(gè)數(shù)進(jìn)行排序，因?yàn)楦嗟姆橇阒档奶卣鲿?huì)導(dǎo)致更多的沖突，所以跳過了上面的第一步，直接排序然后第三步分簇。

EFB 算法流程如下：

算法允許兩兩特征并不完全互斥來增加特征捆綁的數(shù)量，通過設(shè)置最大沖突比率 $\gamma$ 來平衡算法的精度和效率。

這樣哪些特征捆綁的問題就解決了。

2，解決怎么把特征綁為一捆

特征合并算法，其關(guān)鍵在于原始特征能從合并的特征中分離出來。綁定幾個(gè)特征在同一個(gè)bundle里需要保證綁定前的原始特征的值可以在bundle中識(shí)別，考慮到直方圖算法將連續(xù)的值保存為離散的bins，我們可以使得不同特征的值分到bundle中的不同桶中，這可以通過在特征值中加一個(gè)偏置常量來解決。比如，我們?cè)赽undle中綁定了兩個(gè)特征A和B，A特征的原始取值為區(qū)間 [0,10)，B特征的原始取值為區(qū)間[0,20)，我們可以在B特征的取值上加一個(gè)偏置常量101010，將其取值范圍變?yōu)閇10,30)，綁定后的特征取值范圍為 [0,30)，這樣就可以放心的融合特征A和B了。

例如對(duì)于特征A和B在1和2的部分有重疊，則可以通過“右移”特征B來避免重疊：

通過EFB，許多有少量沖突的特征就被捆綁成了更少的密集特征，這個(gè)大大減少的特征的數(shù)量，對(duì)訓(xùn)練速度又帶來很大的提高。利用這種思路，可以通過對(duì)某些特征的取值重新編碼，將多個(gè)這樣互斥的特征捆綁成為一個(gè)新的特征。有趣的是，對(duì)于類別特征，如果轉(zhuǎn)換成onehot編碼，則這些onehot編碼后的多個(gè)特征相互之間是互斥的，從而可以被捆綁成為一個(gè)特征。因此，對(duì)于指定為類別型的特征，LightGBM可以直接將每個(gè)類別取值和一個(gè)bin關(guān)聯(lián)，從而自動(dòng)地處理它們，而無需預(yù)處理成onehot編碼。

具體的特征合并算法如下所示：

LightGBM的工程優(yōu)化

1，原生支持類別特征

LightGBM 是原生支持類別變量的模型，其他的大多數(shù)模型例如LR，SVM等都需要先將類別特征利用獨(dú)熱編碼轉(zhuǎn)化為多維0/1特征再輸入到模型。對(duì)于基于決策樹的算法而言，不推薦使用獨(dú)熱編碼，會(huì)存在下面的問題：

產(chǎn)生切分不平衡問題。獨(dú)熱編碼后，一種情況是0/1特征中1的占比特別少，即大部分都是0，無論這個(gè)特征多重要，乘以相應(yīng)的占比后增益也是特別的小；另一種情況是0/1特征中1的占比特別多，即大部分都是1，這樣的話這個(gè)特征的又沒有明顯的區(qū)分度。

影響決策樹學(xué)習(xí)。由于獨(dú)熱編碼后，特征空間維度大幅度增加，樣本將會(huì)被劃分到零散的小空間內(nèi)部。在這樣的小空間內(nèi)，會(huì)因?yàn)闃颖緮?shù)量不足，統(tǒng)計(jì)信息不夠準(zhǔn)確，導(dǎo)致學(xué)習(xí)效果變差。

LightGBM 原生支持類別特征，采用 many-vs-many(每次將若干個(gè)類作為正類，若干個(gè)其他類作為負(fù)類) 的切分方式將類別特征分為兩個(gè)子集，實(shí)現(xiàn)類別特征的最優(yōu)切分。

例如當(dāng)$X=A||X=C$時(shí)，放到左孩子，不符合條件的放到右孩子。數(shù)據(jù)會(huì)被切分到兩個(gè)比較大的空間，進(jìn)一步的學(xué)習(xí)也會(huì)更好。

具體而言，在枚舉類別變量的分割點(diǎn)之前，先把直方圖按照每個(gè)類別對(duì)應(yīng)的所有樣本的label計(jì)算均值($\frac{sum(y)}{count(y)}$)，然后進(jìn)行排序：

最后按照排序的結(jié)果依次枚舉最優(yōu)分割點(diǎn)。這個(gè)方法很容易過擬合，所以LightGBM里面還增加了很多對(duì)于這個(gè)方法的約束和正則化。 實(shí)驗(yàn)結(jié)果證明，這個(gè)方法可以使訓(xùn)練速度加速8倍。

2，高效并行

LightGBM支持三個(gè)角度的并行：特征并行，數(shù)據(jù)并行和投票并行。 下面我們一一來看看：

特征并行

特征并行的主要思想是：不同機(jī)器在不同的特征子集上分別尋找最優(yōu)的分割點(diǎn)，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)。XGBoost使用的就是這種特征并行方法。這種特征并行方法有個(gè)很大的缺點(diǎn)：就是對(duì)數(shù)據(jù)進(jìn)行垂直劃分，每臺(tái)機(jī)器所含數(shù)據(jù)不同，然后使用不同機(jī)器找到不同特征的最優(yōu)分裂點(diǎn)，劃分結(jié)果需要通過通信告知每臺(tái)機(jī)器，增加了額外的通信和同步上的復(fù)雜度。

LightGBM 則不進(jìn)行數(shù)據(jù)垂直劃分，而是在每臺(tái)機(jī)器上保存全部訓(xùn)練數(shù)據(jù)，在得到最佳劃分方案后可在本地執(zhí)行劃分而減少了不必要的通信。具體過程如下圖所示。

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

傳統(tǒng)的數(shù)據(jù)并行策略主要為水平劃分?jǐn)?shù)據(jù)，讓不同的機(jī)器先在本地構(gòu)造直方圖，然后進(jìn)行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)。這種數(shù)據(jù)劃分有一個(gè)很大的缺點(diǎn)：通訊開銷過大。如果使用點(diǎn)對(duì)點(diǎn)通信，一臺(tái)機(jī)器的通訊開銷大約為：
$$O(機(jī)器數(shù)量?特征數(shù)量?分桶數(shù)量)$$
如果使用集成的通信，則通訊開銷為：
$$O(2?特征數(shù)量?分桶數(shù)量)$$
LightGBM在數(shù)據(jù)并行中使用分散規(guī)約 (Reduce scatter) 把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算，并利用直方圖做差，進(jìn)一步減少了一半的通信量。具體過程如下圖所示：

投票并行

基于投票的數(shù)據(jù)并行進(jìn)一步優(yōu)化數(shù)據(jù)并行中的通信代價(jià)，使得通信代價(jià)為常數(shù)級(jí)別。具體而言，該方法只合并部分特征的直方圖從而達(dá)到降低通信量的目的，可以得到非常好的加速效果。具體過程如下圖所示。大致步驟為兩步：

本地找出 Top K 特征，并基于投票篩選出可能是最優(yōu)分割點(diǎn)的特征；

合并時(shí)只合并每個(gè)機(jī)器選出來的特征。

3，Cache命中率優(yōu)化

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

LightGBM 所使用直方圖算法對(duì) Cache 天生友好：

首先，所有的特征都采用相同的方式獲得梯度（區(qū)別于XGBoost的不同特征通過不同的索引獲得梯度），只需要對(duì)梯度進(jìn)行排序并可實(shí)現(xiàn)連續(xù)訪問，大大提高了緩存命中率；

其次，因?yàn)椴恍枰鎯?chǔ)行索引到葉子索引的數(shù)組，降低了存儲(chǔ)消耗，而且也不存在 Cache Miss的問題。

LightGBM的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

這部分主要總結(jié)下 LightGBM 相對(duì)于 XGBoost 的優(yōu)點(diǎn)，從內(nèi)存和速度兩方面進(jìn)行介紹。

(1) 速度更快：

• LightGBM 采用了直方圖算法將遍歷樣本轉(zhuǎn)變?yōu)楸闅v直方圖，極大的降低了時(shí)間復(fù)雜度；
• LightGBM 在訓(xùn)練過程中采用單邊梯度算法過濾掉梯度小的樣本，減少了大量的計(jì)算；
• LightGBM 采用了基于 Leaf-wise 算法的增長策略構(gòu)建樹，減少了很多不必要的計(jì)算量；
• LightGBM 采用優(yōu)化后的特征并行、數(shù)據(jù)并行方法加速計(jì)算，當(dāng)數(shù)據(jù)量非常大的時(shí)候還可以采用投票并行的策略；
• LightGBM 對(duì)緩存也進(jìn)行了優(yōu)化，增加了緩存命中率；

(2) 內(nèi)存更小：

• LightGBM 采用了直方圖算法將存儲(chǔ)特征值轉(zhuǎn)變?yōu)榇鎯?chǔ) bin 值，且不需要特征值到樣本的索引，降低了內(nèi)存消耗；
• LightGBM 在訓(xùn)練過程中采用互斥特征捆綁算法減少了特征數(shù)量，降低了內(nèi)存消耗。

缺點(diǎn)

• 可能會(huì)長出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM在Leaf-wise之上增加了一個(gè)最大深度限制，在保證高效率的同時(shí)防止過擬合；
• Boosting族是迭代算法，每一次迭代都根據(jù)上一次迭代的預(yù)測(cè)結(jié)果對(duì)樣本進(jìn)行權(quán)重調(diào)整，所以隨著迭代不斷進(jìn)行，誤差會(huì)越來越小，模型的偏差（bias）會(huì)不斷降低，所以會(huì)對(duì)噪點(diǎn)較為敏感；
• 在尋找最優(yōu)解時(shí)，依據(jù)的是最優(yōu)切分變量，沒有將最優(yōu)解是全部特征的綜合這一理念考慮進(jìn)去；

參考文章

深入理解LightGBM

白話機(jī)器學(xué)習(xí)算法理論+實(shí)戰(zhàn)番外篇之LightGBM

總結(jié)

以上是生活随笔為你收集整理的LightGBM 相关知识理解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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