LightGBM是微軟亞洲研究院（MSRA）于2017年提出的boosting框架，論文的標(biāo)題為A Highly Efficient Gradient Boosting Decision Tree，其基本原理與XGBoost一樣，使用基于學(xué)習(xí)算法的決策樹(shù)，只是在框架上做了優(yōu)化（主要是訓(xùn)練速度的優(yōu)化）。在Kaggle 比賽中，應(yīng)用最為廣泛的就是XGBoost和LightGBM，因此大概了解背后的原理是十分必要的，這篇文章就帶領(lǐng)大家閱讀一下提出此方法的原文。

速看 Taifeng Wang 分享LightGBM的視頻

在論文摘要中作者提到，GBDT 是一種非常流行的機(jī)器學(xué)習(xí)算法，有很多有效的實(shí)現(xiàn)，雖然在這些實(shí)現(xiàn)中采用了許多工程優(yōu)化方法，但在特征維數(shù)高、數(shù)據(jù)量大的情況下，其效率和可擴(kuò)展性仍不能令人滿意。一個(gè)主要的原因是，對(duì)于每個(gè)特征，需要掃描所有的數(shù)據(jù)實(shí)例來(lái)估計(jì)所有可能的分割點(diǎn)的信息增益，這是非常耗時(shí)的。

為了解決這個(gè)問(wèn)題，作者提出了兩種新的技術(shù)：

在多個(gè)公共數(shù)據(jù)集上的實(shí)驗(yàn)表明，LightGBM 可以將傳統(tǒng) GBDT 的訓(xùn)練速度提高20倍以上，同時(shí)達(dá)到幾乎相同的精度。

LightGBM是基于XGB進(jìn)行改進(jìn)的，這是它主要的比較對(duì)象，所以我們先說(shuō)一下XGB有哪些優(yōu)缺點(diǎn)。

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

XGB缺點(diǎn)：

LightGBM就針對(duì)以上缺點(diǎn)進(jìn)行了改進(jìn)，原文的解釋如下。

1. LightGBM使用基于histogram算法代替了pre-sorted算法構(gòu)建的數(shù)據(jù)結(jié)構(gòu)。利用histogram后，會(huì)有很多好處。例如histogram做差，提高了cache命中率（因?yàn)槭褂昧薼eaf-wise）。

2. LightGBM采用GOSS來(lái)做數(shù)據(jù)采樣，提高了訓(xùn)練速度。類似于Adaboost在數(shù)據(jù)訓(xùn)練時(shí)賦予樣本權(quán)重。

3. 采用EFB算法來(lái)預(yù)處理稀疏數(shù)據(jù)，解決了histogram算法對(duì)稀疏數(shù)據(jù)的處理時(shí)間復(fù)雜度差于pre-sorted的問(wèn)題

先對(duì)特征值進(jìn)行裝箱處理（對(duì)每個(gè)特征的取值做個(gè)分段函數(shù)，將所有樣本在該特征上的取值劃分到某一段bin中）。最終把特征取值從連續(xù)值轉(zhuǎn)化成了離散值。遍歷數(shù)據(jù)時(shí)，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。

（直方圖算法偽代碼）

我們來(lái)看看直方圖算法是如何優(yōu)化的。在處理連續(xù)特征的時(shí)候，如果想要快速找到最佳的分裂節(jié)點(diǎn)有兩種，一是像之前說(shuō)到的那樣對(duì)特征值采用pre-sorted的方式得到最佳的分裂特征值，二是直方圖算法先將特征值做裝箱處理。裝箱處理是特征工程中常見(jiàn)的處理方式之一了，如[0,0.3)—>0，[0.3,0.7)—->1等。MSRA論文中提到的直方圖優(yōu)化的流程圖：

• 最外面的 for 循環(huán)表示的意思是對(duì)當(dāng)前模型下所有的葉子節(jié)點(diǎn)處理，GBDT會(huì)訓(xùn)練多個(gè)樹(shù)模型，這個(gè)舉例表示其中任何一個(gè)模型。

• 第二個(gè) for 循環(huán)開(kāi)始對(duì)某個(gè)葉子進(jìn)行分裂處理，這一步就開(kāi)始遍歷所有的特征。

• 依次往下看，對(duì)于當(dāng)前這個(gè)特征新建一個(gè)直方圖H，之后是第三個(gè) for 循環(huán)，這個(gè) for 循環(huán)是遍歷所有的樣本來(lái)構(gòu)建直方圖（裝箱操作），直方圖的每個(gè) bin 中包含了一定的樣本，在此計(jì)算每個(gè) bin 中的樣本的梯度之和并對(duì) bin 中的樣本記數(shù)。

• 最后一個(gè) for 循環(huán)開(kāi)始遍歷所有的 bin，為了找到適合分裂的最佳 bin，具體解釋如下：

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

• 最明顯就是內(nèi)存消耗的降低

• 計(jì)算效率得到提高，pre-sorte的exact greedy對(duì)每個(gè)特征都需要遍歷一遍數(shù)據(jù)，并計(jì)算增益，復(fù)雜度為O(#feature×#data)。而直方圖算法在建立完直方圖后，只需要對(duì)每個(gè)特征遍歷直方圖即可，復(fù)雜度為O(#feature×#bins)。

• 提高緩存命中率，因?yàn)樗L問(wèn)梯度是連續(xù)的（直方圖）。

• 在數(shù)據(jù)并行的時(shí)候，直方圖算法可以大幅降低通信代價(jià)。（數(shù)據(jù)并行、特征并行在本文后面講解）

缺點(diǎn)：

• 由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會(huì)對(duì)結(jié)果產(chǎn)生影響。但在不同的數(shù)據(jù)集上的結(jié)果表明，離散化的分割點(diǎn)對(duì)最終的精度影響并不是很大，甚至有時(shí)候會(huì)更好一點(diǎn)。

• 預(yù)處理能夠忽略零值特征，減少訓(xùn)練代價(jià)；而直方圖不能對(duì)稀疏進(jìn)行優(yōu)化，只是計(jì)算累加值（累加梯度和樣本數(shù)）。但是，LightGBM 對(duì)稀疏進(jìn)行了優(yōu)化：只用非零特征構(gòu)建直方圖。

建立直方圖的復(fù)雜度為O(#feature×#data)，如果能降低特征數(shù)或者降低樣本數(shù)，訓(xùn)練的時(shí)間會(huì)大大減少。以往的降低樣本數(shù)的方法中，要么不能直接用在GBDT上，要么會(huì)損失精度。而降低特征數(shù)的直接想法是去除弱的特征（通常用PCA完成），然而，這些方法往往都假設(shè)特征是有冗余的，然而通常特征是精心設(shè)計(jì)的，去除它們中的任何一個(gè)可能會(huì)影響訓(xùn)練精度。因此LightGBM提出了GOSS算法和EFB算法。

在AdaBoost中，權(quán)重向量w反映了樣本的重要性。而在GBDT中，沒(méi)有這樣的權(quán)重來(lái)反映樣本的重要程度。但是梯度是一個(gè)很好的指標(biāo)，如果一個(gè)樣本的梯度很小，說(shuō)明該樣本的訓(xùn)練誤差很小，或者說(shuō)該樣本已經(jīng)得到了很好的訓(xùn)練(well-trained)。

要減少樣本數(shù)，一個(gè)直接的想法是拋棄那些梯度很小的樣本，但是這樣訓(xùn)練集的分布會(huì)被改變，可能會(huì)使得模型準(zhǔn)確率下降。LightGBM提出 Gradient-based One-Side Sampling (GOSS)來(lái)解決這個(gè)問(wèn)題。

（GOSS偽代碼）

算法分析

1. 根據(jù)梯度的絕對(duì)值將樣本進(jìn)行降序排序

2. 選擇前a×100%的樣本，這些樣本稱為A

3. 剩下的數(shù)據(jù)(1?a)×100% 的數(shù)據(jù)中，隨機(jī)抽取b×100%的數(shù)據(jù)，這些樣本稱為B

4. 在計(jì)算增益的時(shí)候，放大樣本B中的梯度(1?a)/b 倍

5. 關(guān)于g，在具體的實(shí)現(xiàn)中是一階梯度和二階梯度的乘積

使用GOSS進(jìn)行采樣，使得訓(xùn)練算法更加關(guān)注沒(méi)有充分訓(xùn)練(under-trained)的樣本，并且只會(huì)稍微的改變?cè)械臄?shù)據(jù)分布。設(shè)O為決策樹(shù)固定節(jié)點(diǎn)上的訓(xùn)練數(shù)據(jù)集，在點(diǎn)d處的劃分特征j的方差增益定義為：

而使用GOSS后，增益定義為：

一個(gè)有高維特征空間的數(shù)據(jù)往往是稀疏的，而稀疏的特征空間中，許多特征是互斥的。所謂互斥就是他們從來(lái)不會(huì)同時(shí)具有非0值（比如one-hot編碼后的類別特征）。

LightGBM利用這一點(diǎn)提出Exclusive Feature Bundling（EFB）算法來(lái)進(jìn)行互斥特征的合并，從而減少特征的數(shù)目。做法是先確定哪些互斥的特征可以合并（可以合并的特征放在一起，稱為bundle），然后將各個(gè)bundle合并為一個(gè)特征。

當(dāng)#bundle<<#feature時(shí)，直方圖構(gòu)建的復(fù)雜度從O(#data×#feature)變?yōu)?em>O(#data×#bundle)。這樣GBDT能在精度不損失的情況下進(jìn)一步提高訓(xùn)練速度。

有兩個(gè)問(wèn)題需要解決：

1. 如何判斷哪些特征應(yīng)該放在一個(gè)Bundle中？

2. 如何將bundle中的特征合并為一個(gè)新的特征？

對(duì)于第1個(gè)問(wèn)題，將特征劃分為最少數(shù)量的互斥bundle是NP-hard問(wèn)題（可以根據(jù)圖著色問(wèn)題來(lái)證明）。

首先通過(guò)將特征作為頂點(diǎn)并在每?jī)蓚€(gè)特征不互斥的情況下為每條特征添加邊，從而將最優(yōu)捆綁問(wèn)題簡(jiǎn)化為圖著色問(wèn)題。然后使用貪婪算法，該算法可以合理地產(chǎn)生圖形著色以得到良好的捆綁結(jié)果（具有恒定的近似比率）。

此外，我們注意到通常有很多特征，盡管不是100％互斥的，但也很少同時(shí)采用非零值。如果我們的算法可以允許一小部分沖突，那么我們可以獲得更少數(shù)量的特征束并進(jìn)一步提高計(jì)算效率。

（LightGBM構(gòu)建bundle的算法偽代碼）

算法分析

1. 構(gòu)造帶權(quán)圖G，邊的權(quán)重代表兩個(gè)特征之間沖突的數(shù)量

2. 對(duì)特征按度降序排序

3. 對(duì)排好序的特征進(jìn)行遍歷，對(duì)于當(dāng)前特征i，查看是否能加入已有的bundle（沖突要小），若不行，則新建一個(gè)bundle

上述的算法復(fù)雜度為O(#feature²)，當(dāng)特征數(shù)很大的時(shí)候，仍然效率不高?？梢赃M(jìn)一步優(yōu)化：不建立圖，直接按特征的非0值的個(gè)數(shù)進(jìn)行排序（這也是一種貪心，非0值越多，越可能沖突）。

對(duì)于第2個(gè)問(wèn)題，目前有了一個(gè)個(gè)的bundle，如何將bundle中的特征合并為一個(gè)新的特征呢？

關(guān)鍵是要確?？梢詮奶卣靼凶R(shí)別原始特征的值。由于基于直方圖的算法存儲(chǔ)離散的bins而不是特征的連續(xù)值，因此我們可以讓互斥特征駐留在不同的bins中來(lái)構(gòu)造特征包。

這可以通過(guò)對(duì)原始特征的值添加偏移來(lái)實(shí)現(xiàn)，從而將互斥的特征放在不同的bins中。例如，一個(gè)Bundle中有兩個(gè)特征A和B，特征A取值[0, 10)，特征B取值[0, 20)。然后，我們向特征B的值添加10的偏移量，以使經(jīng)過(guò)改進(jìn)的特征采用[10, 30)中的值。之后，可以安全地合并特征A和B，并使用范圍為[0, 30]的特征束替換原始特征A和B。即，Merge Exclusive Features（MEF）算法。

（Merge Exclusive Features算法偽代碼）

通過(guò)MEF算法，將許多互斥的稀疏特征轉(zhuǎn)化為稠密的特征，降低了特征的數(shù)量，提高了建直方圖的效率。

作者在文中使用五個(gè)不同的公開(kāi)數(shù)據(jù)集，來(lái)證明LightGBM算法的有效性。

建立了五個(gè)模型：不使用GOSS和EFB的XGBoost和LightGBM(稱為lgb_baselline)用作基準(zhǔn)。對(duì)于XGBoost使用兩個(gè)版本，即xgb_exa(pre-sorted算法)和xgb_his(Histogram算法)。對(duì)于xgb_his，lgb_baseline和LightGBM，使用leaf-wise tree growth strategy(補(bǔ)充材料里會(huì)介紹)。對(duì)于xgb_exa，僅支持layer-wise growth strategy(補(bǔ)充材料里會(huì)介紹)，因此對(duì)xgb_exa的參數(shù)進(jìn)行了調(diào)整，以使其能夠像其他樹(shù)一樣生長(zhǎng)類似的樹(shù)。

報(bào)告了總體訓(xùn)練時(shí)間成本、測(cè)試數(shù)據(jù)集的總體準(zhǔn)確性(SGB是具有隨機(jī)梯度增強(qiáng)功能的lgb_baseline，其采樣率與LightGBM相同)

表2 總體訓(xùn)練時(shí)間成本

表3 測(cè)試數(shù)據(jù)集的總體準(zhǔn)確性

從這些結(jié)果中，我們可以看到LightGBM是最快的，同時(shí)保持與基準(zhǔn)幾乎相同的準(zhǔn)確性。xgb_exa基于預(yù)排序算法，與基于直方圖的算法相比，速度相當(dāng)慢。通過(guò)與lgb_baseline進(jìn)行比較，LightGBM在Allstate，F(xiàn)light Delay，LETOR，KDD10和KDD12數(shù)據(jù)集上分別提高了21倍，6倍，1.6倍，14倍和13倍。

整體提速來(lái)自GOSS和EFB的結(jié)合，作者進(jìn)一步將分解貢獻(xiàn)，并分別討論GOSS和EFB的有效性。

通過(guò)比較表2中的LightGBM和EFB_only(不帶GOSS的LightGBM)，可以看到使用10％-20％的數(shù)據(jù)，GOSS可以將速度提高近2倍，證明了GOSS比隨機(jī)抽樣更為有效。

通過(guò)比較表2中的lgb_baseline與EFB_only(不帶GOSS的LightGBM)，可以看到EFB幫助大幅提高那些大規(guī)模數(shù)據(jù)集的速度?？梢宰⒁獾剑琹gb_baseline已針對(duì)稀疏特征進(jìn)行了優(yōu)化，EFB仍可以在很大程度上加快訓(xùn)練速度。這是因?yàn)镋FB將許多稀疏特征（ont-hot編碼特征和隱式互斥特征implicitly exclusive features）合并為更少的特征。

在本文中，作者提出了一種新穎的GBDT算法，稱為L(zhǎng)ightGBM，它包含兩種新穎的技術(shù)：基于梯度的單邊采樣(Gradient-based One-Side Sampling)和互斥特征捆綁(Exclusive Feature Bundling)，分別處理大量數(shù)據(jù)實(shí)例和大量特征。文中對(duì)這兩種技術(shù)進(jìn)行了理論分析和實(shí)驗(yàn)研究，實(shí)驗(yàn)結(jié)果與理論相符，表明在GOSS和EFB的幫助下，LightGBM在計(jì)算速度和內(nèi)存消耗方面顯著優(yōu)于XGBoost和SGB。在以后的工作中，作者將研究基于梯度的單邊采樣中a和b的最佳選擇，并繼續(xù)提高互斥特征捆綁的性能，以處理大量特征（無(wú)論稀疏與否）。

XGBoost中的樹(shù)是按層生長(zhǎng)的，稱為Level-wise tree growth，同一層的所有節(jié)點(diǎn)都做分裂，最后剪枝，如下圖所示：

Level-wise過(guò)一次數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過(guò)擬合。但實(shí)際上Level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，帶來(lái)了很多沒(méi)必要的成本，實(shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂。

LightGBM采用的是Leaf-wise tree growth，如下圖所示：

Leaf-wise是一種更為高效的策略，每次從當(dāng)前所有葉子中，找到分裂增益最大的一個(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ò)擬合。

注：當(dāng)采用相同葉子節(jié)點(diǎn)時(shí)候，leaf-wise tree growth 策略比level-wise tree growth 策略，模型準(zhǔn)確率更高。

一個(gè)區(qū)間的范圍內(nèi)作為一個(gè)bin，簡(jiǎn)化為以分桶為粒度的直方圖來(lái)做，這樣一來(lái)，數(shù)據(jù)的表示更加簡(jiǎn)化，減少了內(nèi)存的使用，而且直方圖帶來(lái)了一定的正則化的效果，使得訓(xùn)練出的模型不容易o(hù)ver-fitting到training-data上面，從而具備更好的泛化性。

上圖是做過(guò)直方圖優(yōu)化之后的求解直方圖的算法細(xì)節(jié)。按照bin來(lái)索引histogram的，所以不需要按照每個(gè)特征來(lái)排序，也不需要一一地對(duì)比不同特征的值，大大地減少了運(yùn)算量。

當(dāng)用特征的bin來(lái)描述數(shù)據(jù)特征的時(shí)候，我們不需要像pre-sorted算法那樣去存儲(chǔ)每一個(gè)特征排序后對(duì)應(yīng)的數(shù)據(jù)的序列，也就是上圖最左邊的灰色方塊。

此外，使用bin來(lái)表示特征，一般bin的個(gè)數(shù)都是控制在比較小的范圍內(nèi)，這樣可以使用更少的Byte來(lái)存儲(chǔ)，原先的feature value可能是float，需要用4個(gè)Bytes來(lái)存儲(chǔ)。

總體上來(lái)說(shuō)，LightGBM內(nèi)存的使用量往往會(huì)降到XGBoost對(duì)應(yīng)sorted策略的八分之一

LightGBM使用了帶有深度性質(zhì)的leaf-wise生長(zhǎng)樹(shù)的方法，來(lái)提高模型的精度；這是一種比level-wise更高效的長(zhǎng)樹(shù)的方法，在葉子數(shù)量一樣的時(shí)候，leaf-wise可以降低更多的訓(xùn)練誤差，帶來(lái)更好的精度。

但單純地使用leaf-wise的生長(zhǎng)，可能會(huì)長(zhǎng)出比較深的樹(shù)，在小數(shù)據(jù)集上可能會(huì)造成過(guò)擬合，因此在leaf-wise的基礎(chǔ)之上，多加了深度的限制。

LightGBM還使用了直方圖做差的優(yōu)化，達(dá)到了兩倍的加速。

一個(gè)葉子節(jié)點(diǎn)的直方圖，可以由它的父親節(jié)點(diǎn)的直方圖減去它的兄弟節(jié)點(diǎn)的直方圖得到。

根據(jù)這一點(diǎn)，我們可以先計(jì)算數(shù)據(jù)量比較小的葉子節(jié)點(diǎn)上的直方圖，然后用直方圖做差，得到數(shù)據(jù)量較大的葉子節(jié)點(diǎn)上的直方圖，達(dá)到加速的效果。

Pre-sorted 的算法當(dāng)中，有兩個(gè)操作頻繁的地方，會(huì)造成cache-miss。

• 對(duì)梯度的訪問(wèn)，在計(jì)算增益的時(shí)候，需要利用梯度，但不同的特征訪問(wèn)梯度順序都是不一樣的，而且是隨機(jī)的。

• 對(duì)索引表的訪問(wèn)，pre-sorted使用一個(gè)行號(hào)和葉子節(jié)點(diǎn)號(hào)的索引表，所有的特征都要通過(guò)訪問(wèn)這個(gè)索引表，并且是隨機(jī)的。這帶來(lái)了非常大的系統(tǒng)性能的下降。

LightGBM使用直方圖算法是天然的cache friendly，首先，對(duì)梯度的訪問(wèn)，因?yàn)椴恍枰獙?duì)特征進(jìn)行排序，同時(shí)，所有的特征都采用同樣的方式進(jìn)行訪問(wèn)，所以只需要對(duì)梯度訪問(wèn)的順序進(jìn)行一個(gè)重新的排序，所有的特征都能連續(xù)地訪問(wèn)梯度。

此外，直方圖算法不需要數(shù)據(jù)id到葉子id的一個(gè)索引表，沒(méi)有cache-miss的問(wèn)題。事實(shí)上，在cache-miss這樣一個(gè)方面，對(duì)速度的影響是很大的，尤其在數(shù)據(jù)量很大的時(shí)候，MRSA研究人員進(jìn)行過(guò)測(cè)試，在數(shù)據(jù)量很多的時(shí)候，相比于隨機(jī)訪問(wèn)，順序訪問(wèn)的速度可以快4倍以上，這其中速度的差異基本上是由cache-miss帶來(lái)的。

傳統(tǒng)的機(jī)器學(xué)習(xí)工具一般不能直接輸入類別特征，需要預(yù)先做離散化，轉(zhuǎn)換為很多多維的0,1特征，這樣的做法無(wú)論在時(shí)間上還是空間上，效率都不高。

LightGBM通過(guò)更改決策樹(shù)算法的決策規(guī)則，直接原生支持類別特征，不需要額外的離散化。并且通過(guò)一些實(shí)驗(yàn)，MRSA研究人員驗(yàn)證了直接使用離散特征可以比使用0-1離散化后的特征，速度快到8倍以上 。

LightGBM原生支持多種并行算法：

• Feature Parallelizaton適用于小數(shù)據(jù)且特征比較多的場(chǎng)景；

• Data Parallelization適用于數(shù)據(jù)量比較大，但特征比較少的場(chǎng)景；

• Voting Parallelization適用于數(shù)據(jù)量比較大，特征也比較多的場(chǎng)景；

本小節(jié)主要根據(jù)LightGBM的官方文檔中提到的并行計(jì)算優(yōu)化進(jìn)行講解。在本小節(jié)中，工作的節(jié)點(diǎn)稱為worker。

特征并行主要是并行化決策樹(shù)中尋找最優(yōu)劃分點(diǎn)(Find Best Split)的過(guò)程，這部分最為耗時(shí)。

傳統(tǒng)算法

傳統(tǒng)算法的做法如下：

1. 垂直劃分?jǐn)?shù)據(jù)（對(duì)特征劃分），不同的worker有不同的特征集

2. 每個(gè)workers找到局部最佳的切分點(diǎn){feature, threshold}

3. workers使用點(diǎn)對(duì)點(diǎn)通信，找到全局最佳切分點(diǎn)

4. 具有全局最佳切分點(diǎn)的worker進(jìn)行節(jié)點(diǎn)分裂，然后廣播切分后的結(jié)果（左右子樹(shù)的instance indices）

5. 其它worker根據(jù)收到的instance indices也進(jìn)行劃分

傳統(tǒng)算法的缺點(diǎn)是：

1. 無(wú)法加速分裂的過(guò)程，該過(guò)程復(fù)雜度為O(#data)，當(dāng)數(shù)據(jù)量大的時(shí)候效率不高

2. 需要廣播劃分的結(jié)果（左右子樹(shù)的instance indices），1條數(shù)據(jù)1bit的話，大約需要花費(fèi)O(#data/8)

LightGBM中的特征并行

每個(gè)worker保存所有的數(shù)據(jù)集，這樣找到全局最佳切分點(diǎn)后各個(gè)worker都可以自行劃分，就不用進(jìn)行廣播劃分結(jié)果，減小了網(wǎng)絡(luò)通信量。過(guò)程如下：

1. 每個(gè)workers找到局部最佳的切分點(diǎn){feature, threshold}

2. workers使用點(diǎn)對(duì)點(diǎn)通信，找到全局最佳切分點(diǎn)

3. 每個(gè)worker根據(jù)全局全局最佳切分點(diǎn)進(jìn)行節(jié)點(diǎn)分裂

但是這樣仍然有缺點(diǎn)：

1. split過(guò)程的復(fù)雜度仍是O(#data)，當(dāng)數(shù)據(jù)量大的時(shí)候效率不高

2. 每個(gè)worker保存所有數(shù)據(jù)，存儲(chǔ)代價(jià)高

傳統(tǒng)算法

數(shù)據(jù)并行目標(biāo)是并行化整個(gè)決策學(xué)習(xí)的過(guò)程：

1. 水平切分?jǐn)?shù)據(jù)，不同的worker擁有部分?jǐn)?shù)據(jù)

2. 每個(gè)worker根據(jù)本地?cái)?shù)據(jù)構(gòu)建局部直方圖

3. 合并所有的局部直方圖得到全部直方圖

4. 根據(jù)全局直方圖找到最優(yōu)切分點(diǎn)并進(jìn)行分裂

在第3步中，有兩種合并的方式：

• 采用點(diǎn)對(duì)點(diǎn)方式(point-to-point communication algorithm)進(jìn)行通訊，每個(gè)worker通訊量為O(#machine×#feature×#bin)

• 采用collective communication algorithm(如“All Reduce”)進(jìn)行通訊（相當(dāng)于有一個(gè)中心節(jié)點(diǎn)，通訊后在返回結(jié)果），每個(gè)worker的通訊量為O(2×#feature×#bin)

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

1. 使用“Reduce Scatter”將不同worker的不同特征的直方圖合并，然后workers在局部合并的直方圖中找到局部最優(yōu)劃分，最后同步全局最優(yōu)劃分。

2. 前面提到過(guò)，可以通過(guò)直方圖作差法得到兄弟節(jié)點(diǎn)的直方圖，因此只需要通信一個(gè)節(jié)點(diǎn)的直方圖。

LightGBM采用一種稱為PV-Tree的算法進(jìn)行投票并行(Voting Parallel)，其實(shí)這本質(zhì)上也是一種數(shù)據(jù)并行。PV-Tree和普通的決策樹(shù)差不多，只是在尋找最優(yōu)切分點(diǎn)上有所不同。

（算法偽代碼）

1. 水平切分?jǐn)?shù)據(jù)，不同的worker擁有部分?jǐn)?shù)據(jù)。

2. Local voting: 每個(gè)worker構(gòu)建直方圖，找到top-k個(gè)最優(yōu)的本地劃分特征

3. Global voting: 中心節(jié)點(diǎn)聚合得到最優(yōu)的top-2k個(gè)全局劃分特征（top-2k是看對(duì)各個(gè)worker選擇特征的個(gè)數(shù)進(jìn)行計(jì)數(shù)，取最多的2k個(gè)）

4. Best Attribute Identification：中心節(jié)點(diǎn)向worker收集這top-2k個(gè)特征的直方圖，并進(jìn)行合并，然后計(jì)算得到全局的最優(yōu)劃分

5. 中心節(jié)點(diǎn)將全局最優(yōu)劃分廣播給所有的worker，worker進(jìn)行本地劃分。

可以看出，PV-tree將原本需要#feature×#bin 變?yōu)榱?em style="box-sizing: border-box;">2k×#bin，通信開(kāi)銷得到降低。此外，可以證明，當(dāng)每個(gè)worker的數(shù)據(jù)足夠多的時(shí)候，top-2k個(gè)中包含全局最佳切分點(diǎn)的概率非常高。

(https://papers./paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf)

(http://papers./paper/6380-a-communication-efficient-parallel-algorithm-for-decision-tree)

    3. LightGBM之直方圖優(yōu)化理解

(https://www./2315.html)

    4. 如何玩轉(zhuǎn)LightGBM

(https://v.qq.com/x/page/k0362z6lqix.html)

    5. 細(xì)語(yǔ)呢喃：集成學(xué)習(xí)（四）LightGBM

(https://www./machine-learning-lightgbm/)

    6. LightGBM論文閱讀總結(jié).ipynb

(https://github.com/duboya/CTR-Prediction/blob/master/LightGBM%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB%E6%80%BB%E7%BB%93.ipynb)

    7. 趙大寳Github個(gè)人博客/LightGBM

(https://fuhailin./LightGBM/)