1、概述
LightGBM是微軟于2017年提出的boosting框架拭卿，其基本原理與XGBoost一樣杖狼，使用基于學(xué)習(xí)算法的決策樹(shù)，只是在框架上做了一優(yōu)化（重點(diǎn)在模型的訓(xùn)練速度的優(yōu)化）颈畸。我在參加 Kaggle 比賽的過(guò)程中發(fā)現(xiàn)，除了 XGBoost没讲，表現(xiàn)較好的且使用較為廣泛的 GBM 模型就是 LightGBM 眯娱。因此我認(rèn)為大概了解背后的原理是必要的。
在論文摘要中作者提到爬凑，GBDT 是一種非常流行的機(jī)器學(xué)習(xí)算法徙缴，有很多有效的實(shí)現(xiàn)，雖然在這些實(shí)現(xiàn)中采用了許多工程優(yōu)化方法嘁信，但在特征維數(shù)高于样、數(shù)據(jù)量大的情況下疏叨，其效率和可擴(kuò)展性仍不能令人滿(mǎn)意。一個(gè)主要的原因是穿剖，對(duì)于每個(gè)特征蚤蔓，需要掃描所有的數(shù)據(jù)實(shí)例來(lái)估計(jì)所有可能的分割點(diǎn)的信息增益，這是非常耗時(shí)的糊余。
為了解決這個(gè)問(wèn)題秀又，作者提出了兩種新的技術(shù)：
- 1、GOSS(Gradient based One Side Sampling)：移除梯度較小的數(shù)據(jù)實(shí)例贬芥，只使用其余的數(shù)據(jù)估計(jì)信息增益涮坐。由于梯度較大的數(shù)據(jù)實(shí)例在信息增益的計(jì)算中起著更重要的作用，所以GOSS可以在較小的數(shù)據(jù)量下獲得相當(dāng)準(zhǔn)確的信息增益估計(jì)誓军。
- 2、EFB(Exclusive Feature Bundling)：bundle 不會(huì)同時(shí)為零的特征（互斥）疲扎，達(dá)到減少特征數(shù)量的目的昵时。尋找互斥特征的最優(yōu) bundle 是 NP-Hard 的，但是貪心算法可以獲得很好的近似比（因此可以有效地減少特征的數(shù)量椒丧，而不會(huì)對(duì)分割點(diǎn)的確定造成很大的影響）壹甥。
在多個(gè)公共數(shù)據(jù)集上的實(shí)驗(yàn)表明，LightGBM 可以將傳統(tǒng) GBDT 的訓(xùn)練速度提高20倍以上壶熏，同時(shí)達(dá)到幾乎相同的精度句柠。
2、LightGBM 輕量級(jí)提升學(xué)習(xí)方法
2.1棒假、基于直方圖的排序算法
傳統(tǒng)的 GDBT 方法的主要計(jì)算開(kāi)銷(xiāo)是各 Decision Tree 的學(xué)習(xí)過(guò)程溯职，而學(xué)習(xí)過(guò)程的主要開(kāi)銷(xiāo)是最優(yōu)劃分點(diǎn)的尋找。
最流行的方法是 Pre-sorted 方法帽哑，也就是預(yù)先將所有特征進(jìn)行排序谜酒，然后對(duì)所有數(shù)據(jù)，遍歷所有可能的劃分點(diǎn)妻枕，這樣就可以找到最優(yōu)劃分點(diǎn)僻族。但是這種算法的計(jì)算開(kāi)銷(xiāo)和空間占用都很大。
另一種算法便是基于直方圖的算法屡谐。該算法將連續(xù)的特征值進(jìn)行離散化分桶述么，然后用桶中的特征值數(shù)量來(lái)構(gòu)建直方圖。然后根據(jù)直方圖的離散值愕掏，遍歷尋找最優(yōu)的分割點(diǎn)度秘。相比 Pre-sorted 算法，基于直方圖的算法在時(shí)間和空間開(kāi)銷(xiāo)上都較小亭珍。
算法流程如下：
看起來(lái)很復(fù)雜的樣子敷钾，拆解開(kāi)來(lái)實(shí)際上就是：設(shè)置一個(gè)最大深度枝哄，然后遍歷每一層，在每一層中遍歷各個(gè)葉子節(jié)點(diǎn)阻荒，然后對(duì)每個(gè)結(jié)點(diǎn)中的數(shù)據(jù)挠锥，遍歷所有特征，根據(jù)當(dāng)前特征的分桶規(guī)則將當(dāng)前結(jié)點(diǎn)中的所有數(shù)據(jù)進(jìn)行分桶侨赡，并實(shí)時(shí)更新各桶中的數(shù)據(jù)量以及梯度之和蓖租，以供后續(xù)尋找最優(yōu)劃分點(diǎn)使用。
想象這樣一個(gè)例子羊壹，某個(gè)結(jié)點(diǎn)上的數(shù)據(jù)點(diǎn)為蓖宦，也就是說(shuō)在第一維特征上，前兩個(gè)樣本點(diǎn)是屬于 bin1 的油猫，后兩個(gè)樣本點(diǎn)是屬于 bin 2 的稠茂，在第二維特征上，而第二和第三個(gè)樣本點(diǎn)是屬于 bin 1 的情妖，第一和第四個(gè)樣本點(diǎn)是屬于 bin 2 的睬关，現(xiàn)在這個(gè)結(jié)點(diǎn)保存了兩個(gè)直方圖（對(duì)于兩個(gè)維度），而我們需要考慮兩個(gè)劃分點(diǎn)（即第一維上 bin 1和 bin 2中間的劃分點(diǎn)以及第二維上 bin 1和 bin 2中間的劃分點(diǎn)）毡证，假設(shè)按第一維來(lái)劃分增益較多电爹，則我們將結(jié)點(diǎn)劃分為
和
兩個(gè)子結(jié)點(diǎn)，此時(shí)產(chǎn)生左結(jié)點(diǎn)的兩個(gè)直方圖料睛，第一維特征的直方圖很簡(jiǎn)單丐箩，只需要將 bin 2 的部分清零即可，第二維的直方圖則需要根據(jù)結(jié)點(diǎn)中樣本的第二維特征（實(shí)際上第二維特征就等于其在第二維上所屬的 bin 的序號(hào)）進(jìn)行更新恤煞，實(shí)際上就是按照上圖所示的算法建立直方圖屎勘，然后右結(jié)點(diǎn)的兩個(gè)直方圖可由父親結(jié)點(diǎn)和左子結(jié)點(diǎn)做差得出。
不難看出阱州，上述算法中挑秉，建立直方圖的計(jì)算復(fù)雜度是，通過(guò)直方圖找到最佳劃分點(diǎn)的復(fù)雜度為
苔货。由于
通常比
大得多犀概，因此總的復(fù)雜度是
量級(jí)的。也就是說(shuō)夜惭，想降低復(fù)雜度姻灶，要減少所用的數(shù)據(jù)量或者所用特征數(shù)量。
相比之下诈茧，Pre-sorted 算法尋找最優(yōu)劃分的復(fù)雜度為产喉。也就是說(shuō)，直方圖算法減小了尋找最優(yōu)劃分點(diǎn)的計(jì)算開(kāi)銷(xiāo)。
實(shí)際上曾沈，基于直方圖的算法還可以進(jìn)一步節(jié)約計(jì)算開(kāi)銷(xiāo)这嚣，LightGBM 的直方圖可以做差加速。所謂做差加速塞俱，即一個(gè)葉子的直方圖可以由它的父親結(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到姐帚。構(gòu)造的直方圖本來(lái)需要遍歷該葉子結(jié)點(diǎn)上所有數(shù)據(jù)，但是直方圖做差僅需遍歷直方圖的個(gè)桶即可（即直方圖區(qū)間）障涯，速度上可以提升一倍罐旗。
此外，直方圖算法不僅不需要額外存儲(chǔ)預(yù)排序的結(jié)果唯蝶，而且可以只保存特征離散化后的值九秀，而這個(gè)值一般用 8 位整型存儲(chǔ)就足夠了，內(nèi)存消耗可以降低為原來(lái)的粘我。
基于直方圖的算法的時(shí)間復(fù)雜度為鼓蜒，為了進(jìn)一步提高算法的運(yùn)行效率。需要減少所需的樣本數(shù)量或者特征數(shù)量征字，而 LightGBM 提出的 GOSS 和 EFB 就是用來(lái)做這兩件事的友酱。接下來(lái)我們看一下這兩個(gè)算法的具體流程和原理。
2.2柔纵、GOSS采樣策略
既然要對(duì)樣本進(jìn)行采樣，就要樹(shù)立規(guī)則來(lái)判斷各樣本對(duì)模型的重要程度锤躁，或者說(shuō)對(duì)損失函數(shù)的貢獻(xiàn)程度搁料。一種隱形的采樣方法在 AdaBoost 中有所運(yùn)用，即通過(guò)給樣本賦予不同的權(quán)重來(lái)表示其重要性系羞，權(quán)重大的樣本會(huì)在分類(lèi)器的訓(xùn)練過(guò)程中得到重點(diǎn)關(guān)注郭计。
作者提出了類(lèi)似的權(quán)重概念，來(lái)定義樣本的重要性椒振。樣本的梯度越小昭伸，則樣本的訓(xùn)練誤差越小，表示樣本訓(xùn)練得越好澎迎，其對(duì)于模型表現(xiàn)的提高的重要性就越小庐杨，因此賦予較小的權(quán)重，而大梯度的樣本則賦予較大權(quán)重夹供。
要想減少樣本數(shù)量灵份，我們只需要移除梯度較小的這部分樣本即可。但此時(shí)會(huì)產(chǎn)生一個(gè)問(wèn)題哮洽，那就是破壞原始的數(shù)據(jù)分布填渠。
為解決這個(gè)問(wèn)題，lightGBM 采用了 one-side 采樣的方式來(lái)適配：保留所有的大梯度樣本，對(duì)小梯度樣本進(jìn)行隨機(jī)采樣（只對(duì)小梯度樣本采樣氛什，因此名為 one-side）莺葫，同時(shí)為了保證分布的一致性，在計(jì)算信息增益的時(shí)候枪眉，將采樣的小梯度樣本乘以一個(gè)常量：，這里
表示大梯度樣本采樣比例瑰谜，
表示小梯度樣本的采樣比例（這里的百分比都是相對(duì)于全部樣本而言的）欺冀。
舉例來(lái)說(shuō)，100個(gè)樣本中萨脑，大梯度樣本有 20 個(gè)隐轩，小梯度樣本有 80 個(gè)，小梯度樣本量是大梯度樣本數(shù)據(jù)量的 4 倍渤早，則大樣本采樣比率 等于 0.2职车，假設(shè)小梯度樣本的采樣率為 40%，則
等于 0.4鹊杖，小梯度樣本的采樣數(shù)目等于 0.4 ×100 = 40 個(gè)悴灵，為了保證采樣前后樣本的分布保持一致，最后小梯度樣本采樣得到的數(shù)據(jù)在計(jì)算信息增益時(shí)需要乘以
积瞒。
整個(gè)算法流程如圖所示：
接下來(lái)文章進(jìn)一步給出了 GOSS 的理論證明，說(shuō)明了：
（1）GOSS 采樣可以得到和使用全部數(shù)據(jù)差不多的結(jié)果登下。
（2）GOSS 的泛化性能可能更好茫孔，因?yàn)椴蓸舆^(guò)程起到了防止過(guò)擬合的作用。
2.3被芳、EFB特征合并
高維數(shù)據(jù)通常是非常稀疏的缰贝，而且很多特征是互斥的（即兩個(gè)或多個(gè)特征列不會(huì)同時(shí)為0），lightGBM 對(duì)這類(lèi)數(shù)據(jù)采用了 EFB（exclusive feature bundling）的優(yōu)化策略畔濒，將這些互斥特征分組合并為個(gè)維度剩晴。通過(guò)這種方式，將特征的維度降下來(lái)侵状。
算法要解決的問(wèn)題有兩個(gè)：
- 1赞弥、哪些特征可以 bundle 在一起；
- 2趣兄、如何構(gòu)建 bundle嗤攻，實(shí)現(xiàn)特征降維。
對(duì)于第一個(gè)問(wèn)題诽俯，作者說(shuō)明了將特征劃分為最少數(shù)量的互斥特征 bundle 本質(zhì)上屬于 NP-Hard 問(wèn)題妇菱。因?yàn)槲覀兛梢杂?strong>圖著色問(wèn)題（Graph Coloring Problem）歸約到此問(wèn)題承粤。
圖著色問(wèn)題就是給定一張圖，用最少種類(lèi)的顏色對(duì)圖進(jìn)行著色闯团，使得任意相鄰的兩個(gè)頂點(diǎn)顏色不同辛臊。
創(chuàng)建一個(gè)圖，令圖中的節(jié)點(diǎn)
表示特征房交，將不互斥的特征用一條邊連接起來(lái)彻舰，邊的權(quán)重就是兩個(gè)相連接的特征的總沖突值，這樣一來(lái)候味，需要綁定的特征就是在圖著色問(wèn)題中要涂上同一種顏色的那些點(diǎn)（特征）刃唤。
即然此問(wèn)題是 NP-Hard 的，那么我們就找不到多項(xiàng)式的算法來(lái)得到精確解白群，因此論文中給出了一種貪心算法：
簡(jiǎn)單來(lái)說(shuō)尚胞，算法流程如下：
1、創(chuàng)建圖
帜慢，令圖中的節(jié)點(diǎn)
表示特征笼裳，邊權(quán)為特征間的沖突數(shù)。
2粱玲、將特征按照在圖中的度進(jìn)行降序排序躬柬。
3、遍歷排序后的特征抽减，對(duì)每個(gè)特征允青，遍歷現(xiàn)有的 bundle，若將當(dāng)前特征加入當(dāng)前 bundle 中后 bundle 的總沖突數(shù)不超過(guò)閾值
卵沉，則加入昧廷，否則檢查下一個(gè) bundle，若現(xiàn)有 bundle 均不滿(mǎn)足條件偎箫，則新開(kāi)一個(gè) bundle 并將當(dāng)前特征放入其中。
采用這種方法對(duì)于特征數(shù)目不大的數(shù)據(jù)性能還不錯(cuò)皆串，但是對(duì)于超大規(guī)模的特征將會(huì)出現(xiàn)性能瓶頸淹办。一個(gè)優(yōu)化的方向就是：按照非零值的個(gè)數(shù)進(jìn)行排序，通常非零值越多沖突就越大恶复，我們就把它排得更靠前怜森。
對(duì)于第二個(gè)問(wèn)題：應(yīng)該如何如何構(gòu)建bundle？關(guān)鍵在于構(gòu)建前的特征的值在構(gòu)建后的 bundle 中依然能夠被識(shí)別谤牡。
由于基于直方圖的方法存儲(chǔ)的是離散的 bin 而不是連續(xù)的數(shù)值副硅，因此我們將不同特征的 bin 值設(shè)定為不同的區(qū)間即可。例如翅萤，特征 A 的 bin 值為 [0,10)恐疲，特征 B 的 bin 值為 [0,20)，要想將兩個(gè)特征 bin 合并，我們可以將特征 B 的特征 bin 的值加上10培己，其取值區(qū)間將變?yōu)?[10,30)碳蛋。之后，將特征 A 和 B 合并省咨，使用范圍 [0,30] 的 bundle 來(lái)代替原來(lái)的特征 A 和 B 即可肃弟。
算法流程如下：
下面舉例說(shuō)明上述算法流程，設(shè) bundle 中有 2 個(gè)特征零蓉，
的 bin 為
和
笤受，
的 bin 為
和
，則第一個(gè)循環(huán)結(jié)束后敌蜂，我們可以得到
÷崾蓿現(xiàn)在假設(shè)我們有一個(gè)數(shù)據(jù)
，其原來(lái)的 bin 值為
紊册，即
落在第二個(gè) bin 中比肄，
落在第一個(gè) bin 中，經(jīng)過(guò)第二個(gè)循環(huán)后囊陡，其 bin 值更新為
芳绩，即
。
有了 EFB 方法撞反，數(shù)據(jù)的 shape 就可以由原來(lái)的 縮小為現(xiàn)在的
妥色，且
《羝可以看到嘹害，EFB 方法降低了數(shù)據(jù)特征規(guī)模，提高了模型的訓(xùn)練速度吮便。
2.4笔呀、Leaf-wise (Best-first) Tree Growth
在樹(shù)的生成方式上，lightGBM 與 XGBoost 有所區(qū)別髓需。
XGBoost 決策樹(shù)的生長(zhǎng)策略是 level-wise许师，即逐層對(duì)各層的每個(gè)結(jié)點(diǎn)進(jìn)行劃分，直至達(dá)到終止條件僚匆。它不加區(qū)分的對(duì)待同一層的葉子微渠，帶來(lái)了很多沒(méi)必要的開(kāi)銷(xiāo)，因?yàn)閷?shí)際上很多葉子的分裂增益較低咧擂，沒(méi)必要進(jìn)行搜索和分裂逞盆。
lightGBM 決策樹(shù)的生長(zhǎng)策略是 leaf-wise。與 level-wise 不同松申，leaf-wise 策略以降低模型損失最大化為目的云芦，對(duì)當(dāng)前葉子中切分增益最大的葉子進(jìn)行切分俯逾。這種方法可以降低更多的誤差，得到更好的精度焕数，但缺點(diǎn)是可能會(huì)長(zhǎng)出比較深的決策樹(shù)纱昧，產(chǎn)生過(guò)擬合。因此 LightGBM 在 leaf-wise 之上增加了一個(gè)最大深度的限制堡赔，在保證高效率的同時(shí)防止過(guò)擬合识脆。
2.5、直接支持類(lèi)別特征（即不需要做 one-hot 編碼）
大多數(shù)機(jī)器學(xué)習(xí)工具都無(wú)法直接支持類(lèi)別特征善已，一般需要把類(lèi)別特征灼捂，轉(zhuǎn)化到多維的 one-hot 編碼特征，降低了空間和時(shí)間的效率换团。而類(lèi)別特征的使用是在實(shí)踐中很常用的悉稠。基于這個(gè)考慮艘包，LightGBM 優(yōu)化了對(duì)類(lèi)別特征的支持的猛，可以直接輸入類(lèi)別特征，不需要額外的 one-hot 編碼展開(kāi)想虎。并在決策樹(shù)算法上增加了類(lèi)別特征的決策規(guī)則卦尊。
2.6、直接支持高效并行
LightGBM 還具有支持高效并行的優(yōu)點(diǎn)舌厨。LightGBM 原生支持并行學(xué)習(xí)岂却，目前支持特征并行和數(shù)據(jù)并行的兩種。
- 1裙椭、特征并行的主要思想是在不同機(jī)器在不同的特征集合上分別尋找最優(yōu)的分割點(diǎn)躏哩，然后在機(jī)器間同步最優(yōu)的分割點(diǎn)。
- 2揉燃、數(shù)據(jù)并行則是讓不同的機(jī)器先在本地構(gòu)造直方圖扫尺，然后進(jìn)行全局的合并，最后在合并的直方圖上面尋找最優(yōu)分割點(diǎn)炊汤。
LightGBM 針對(duì)這兩種并行方法都做了優(yōu)化正驻，在特征并行算法中，通過(guò)在本地保存全部數(shù)據(jù)避免對(duì)數(shù)據(jù)切分結(jié)果的通信婿崭；在數(shù)據(jù)并行中使用分散規(guī)約 (Reduce scatter)把直方圖合并的任務(wù)分?jǐn)偟讲煌臋C(jī)器，降低通信和計(jì)算肴颊，并利用直方圖做差氓栈，進(jìn)一步減少了一半的通信量。
Reference：
https://fuhailin.github.io/LightGBM/
