引言https://blog.csdn.net/ShowMeAI/article/details/123406621 之前ShowMeAI對(duì)強(qiáng)大的boosting模型工具XGBoost做了介紹（詳見ShowMeAI文章圖解機(jī)器學(xué)習(xí) | XGBoost模型詳解）。本篇我們來學(xué)習(xí)一下GBDT模型（詳見ShowMeAI文章 圖解機(jī)器學(xué)習(xí) | GBDT模型詳解）的另一個(gè)進(jìn)化版本：LightGBM。 LightGBM是微軟開發(fā)的boosting集成模型，和XGBoost一樣是對(duì)GBDT的優(yōu)化和高效實(shí)現(xiàn)，原理有一些相似之處，但它很多方面比XGBoost有著更為優(yōu)秀的表現(xiàn)。官方給出的這個(gè)工具庫(kù)模型的優(yōu)勢(shì)如下：
下圖是一組實(shí)驗(yàn)數(shù)據(jù)，在這份實(shí)驗(yàn)中，LightGBM比XGBoost快將近10倍，內(nèi)存占用率大約為XGBoost的1/6，準(zhǔn)確率也略有提升。
1.LightGBM動(dòng)機(jī)互聯(lián)網(wǎng)領(lǐng)域的算法應(yīng)用，通常背后都有海量的大數(shù)據(jù)。深度學(xué)習(xí)中一系列神經(jīng)網(wǎng)絡(luò)算法，都是以mini-batch的方式喂數(shù)據(jù)迭代訓(xùn)練的，總訓(xùn)練數(shù)據(jù)量不受內(nèi)存限制。 但我們用到的機(jī)器學(xué)習(xí)算法，比如GBDT（參考ShowMeAI文章 GBDT詳解）在每一次迭代的時(shí)候，都需要遍歷整個(gè)訓(xùn)練數(shù)據(jù)多次。
面對(duì)工業(yè)級(jí)海量的數(shù)據(jù)，普通的GBDT算法無法滿足需求。LightGBM提出的主要原因之一，就是為了解決上述大數(shù)據(jù)量級(jí)下的GBDT訓(xùn)練問題，以便工業(yè)實(shí)踐中能支撐大數(shù)據(jù)量并保證效率。 2.XGBoost優(yōu)缺點(diǎn)我們之前介紹過強(qiáng)大的XGBoost（詳見ShowMeAI文章圖解機(jī)器學(xué)習(xí) | XGBoost模型詳解），但XGBoost也依舊存在一些缺點(diǎn)，LightGBM針對(duì)其中的一部分進(jìn)行了調(diào)整優(yōu)化。XGB優(yōu)缺點(diǎn)歸納如下： 1）精確貪心算法輪迭代時(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ù)地讀寫訓(xùn)練數(shù)據(jù)又會(huì)消耗非常大的時(shí)間。 G a i n = 1 2 [ G L 2 H L + λ + G R 2 H R + λ ? ( G L + G R ) 2 H L + H R + λ ? γ ] Gain=\frac{1}{2}\left [ \frac{G_{L}^{2}}{H_{L}+\lambda} + \frac{G_{R}^{2}}{H_{R}+\lambda} - \frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda} - \gamma \right ] Gain=21[HL+λGL2+HR+λGR2?HL+HR+λ(GL+GR)2?γ]
2）Level-wise生長(zhǎng)方式XGBoost采用Level-wise的增長(zhǎng)策略：基于層進(jìn)行生長(zhǎng)，直到達(dá)到停止條件。這種增長(zhǎng)策略方便并行計(jì)算每一層的分裂節(jié)點(diǎn)，提高了訓(xùn)練速度，但同時(shí)也因?yàn)楣?jié)點(diǎn)增益過小增加了很多不必要的分裂，增加了計(jì)算量。
3）對(duì)cache優(yōu)化不友好在預(yù)排序后，特征對(duì)梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣，無法對(duì)cache進(jìn)行優(yōu)化。同時(shí)，在每一層長(zhǎng)樹的時(shí)候，需要隨機(jī)訪問一個(gè)行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會(huì)造成較大的cache miss。 3.LightGBM優(yōu)化點(diǎn)上個(gè)部分其實(shí)也是LightGBM作者們，構(gòu)建新算法時(shí)著重優(yōu)化的點(diǎn)。概括來說，LightGBM主要有以下特點(diǎn)：
4.決策樹算法1）XGBoost：Pre-sorted算法XGBoost使用的是Pre-sorted算法，能夠更精確的找到數(shù)據(jù)分隔點(diǎn)。
這種pre-sorting算法能夠準(zhǔn)確找到分裂點(diǎn)，但是在空間和時(shí)間上有很大的開銷。
2）LightGBM：直方圖算法LightGBM使用的是直方圖算法（histogram algorithm），占用的內(nèi)存更低，數(shù)據(jù)分割的復(fù)雜度更低。直方圖算法思想是：
（1）內(nèi)存優(yōu)化直方圖算法可以很大程度降低內(nèi)存消耗，它不僅不需要額外存儲(chǔ)預(yù)排序的結(jié)果，還可以只保存特征離散化后的值（一般用8位整型存儲(chǔ)就足夠了）。
如圖所示，用8位整型存儲(chǔ)，內(nèi)存消耗可以降低為原來的1/8。 （2）計(jì)算量?jī)?yōu)化應(yīng)用直方圖算法，計(jì)算代價(jià)也大幅降低，預(yù)排序算法每遍歷一個(gè)特征值就需要計(jì)算一次分裂的增益，而直方圖算法只需要計(jì)算k次（k可以認(rèn)為是常數(shù)），時(shí)間復(fù)雜度從O(#data*#feature)直接優(yōu)化到 O(k#*features)。 （3）注意點(diǎn)直方圖算法的理解和注意點(diǎn)如下：
（4）直方圖算法優(yōu)缺點(diǎn)
Histogram算法還可以進(jìn)一步加速。一個(gè)葉子節(jié)點(diǎn)的Histogram可以直接由父節(jié)點(diǎn)的Histogram和兄弟節(jié)點(diǎn)的Histogram做差得到。一般情況下，構(gòu)造Histogram需要遍歷該葉子上的所有數(shù)據(jù)，通過該方法，只需要遍歷Histogram的k個(gè)捅。速度提升了一倍。 5.決策樹生長(zhǎng)策略1）樹生長(zhǎng)策略調(diào)整直方圖算法之上，LightGBM進(jìn)行進(jìn)一步的優(yōu)化。它沒有使用大多數(shù)GBDT工具使用的按層生長(zhǎng)（Level-wise）的決策樹生長(zhǎng)策略，而使用了帶有深度限制的按葉子生長(zhǎng)（Leaf-wise）算法。 ( p m , f m , v m ) = arg ? min ? ( p , f , v ) L ( T m ? 1 ( X ) . split ? ( p , f , v ) , Y ) \left(p_{m}, f_{m}, v_{m}\right)=\arg \min _{(p, f, v)} L\left(T_{m-1}(X) . \operatorname{split}(p, f, v), Y\right) (pm,fm,vm)=arg(p,f,v)minL(Tm?1(X).split(p,f,v),Y) T m ( X ) = T m ? 1 ( X ) . split ? ( p m , f m , v m ) T_{m}(X)=T_{m-1}(X) . \operatorname{split}\left(p_{m}, f_{m}, v_{m}\right) Tm(X)=Tm?1(X).split(pm,fm,vm)
2）XGBoost：Level-wiseXGBoost采用的是Level-wise（按層生長(zhǎng)）策略生長(zhǎng)的，能夠同時(shí)分裂同一層的葉子，從而進(jìn)行多線程優(yōu)化，不容易過擬合。 但不加區(qū)分的對(duì)待同一層的葉子，帶來了很多沒必要的開銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。 3）LightGBM：Leaf-wiseLightGBM采用Leaf-wise（按葉子生長(zhǎng)）生長(zhǎng)策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個(gè)葉子，然后分裂，如此循環(huán)。
同Level-wise相比，在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點(diǎn)是可能會(huì)長(zhǎng)出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM在Leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過擬合。 6.直方圖差加速LightGBM另一個(gè)優(yōu)化是Histogram（直方圖）做差加速。整個(gè)構(gòu)建過程中可以觀察到：一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。
一般來說構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的k個(gè)桶。利用上述特征，LightGBM可以在構(gòu)造一個(gè)葉子的直方圖后，可以用非常微小的代價(jià)得到它兄弟葉子的直方圖，在速度上可以提升一倍。 7.類別型特征支持大多數(shù)機(jī)器學(xué)習(xí)工具都無法直接支持類別型特征，我們會(huì)先將其編碼再做后續(xù)建模，如果使用one-hot這種編碼方式還會(huì)降低空間和時(shí)間效率。 LightGBM優(yōu)化了對(duì)類別型特征的支持，可以直接輸入類別特征，不需要額外的編碼或one-hot 0/1展開。并在決策樹算法上增加了類別型特征的決策規(guī)則。 1）樹模型與one-hot編碼one-hot編碼是處理類別特征的一個(gè)通用方法，然而在樹模型中，這可能并不一定是一個(gè)好的方法，尤其當(dāng)類別特征中類別個(gè)數(shù)很多的情況下，主要的問題是： 問題1：可能無法在這個(gè)類別特征上進(jìn)行切分。 使用one-hot編碼的話，意味著在每一個(gè)決策節(jié)點(diǎn)上只能使用one vs rest（例如是不是男性，是不是一線城市等）的切分方式。當(dāng)類別值很多時(shí)，每個(gè)類別上的數(shù)據(jù)可能會(huì)比較少，這時(shí)候切分會(huì)產(chǎn)生不平衡，這意味著切分增益也會(huì)很小。 問題2：影響決策樹的學(xué)習(xí)。 就算可以在這個(gè)類別特征進(jìn)行切分，也會(huì)把數(shù)據(jù)切分到很多零碎的小空間上，如下左圖所示。而決策樹學(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ì)更好。
圈中的數(shù)值表示該結(jié)點(diǎn)內(nèi)的數(shù)據(jù)。右圖中葉子節(jié)點(diǎn) X=A || X=C 的含義是 X=A 或者 X=C 放到左孩子，其余放到右孩子。 2）LightGBM類別型特征處理方式LightGBM采用了Many vs Many的切分方式解決one-hot編碼帶來的問題，實(shí)現(xiàn)了類別特征的最優(yōu)切分。用LightGBM可以直接輸入類別特征，并產(chǎn)生上右圖的效果。 算法流程如圖所示：
從下圖可以看到，Sum(y)/Count(y)為類別的均值。當(dāng)然，這個(gè)方法很容易過擬合，所以在LightGBM中加入了很多對(duì)這個(gè)方法的約束和正則化。
求解類別型特征的最優(yōu)切分的具體流程如下： ① 離散特征建立直方圖的過程 統(tǒng)計(jì)該特征下每一種離散值出現(xiàn)的次數(shù)，并從高到低排序，并過濾掉出現(xiàn)次數(shù)較少的特征值。然后為每一個(gè)特征值，建立一個(gè)bin容器，對(duì)于在bin容器內(nèi)出現(xiàn)次數(shù)較少的特征值直接過濾掉，不建立bin容器。 ② 計(jì)算分裂閾值的過程
該 b i n 容 器 下 所 有 樣 本 的 一 階 梯 度 之 和 該 b i n 容 器 下 所 有 樣 本 的 二 階 梯 度 之 和 + 正 則 項(xiàng) （ 參 數(shù) c a t - s m o o t h ） \frac{該bin容器下所有樣本的一階梯度之和}{該bin容器下所有樣本的二階梯度之和} + 正則項(xiàng)（參數(shù) {cat \text{-} smooth}） 該bin容器下所有樣本的二階梯度之和該bin容器下所有樣本的一階梯度之和+正則項(xiàng)（參數(shù)cat-smooth） 這里為什么不是label的均值呢？其實(shí)上例中只是為了便于理解，只針對(duì)了學(xué)習(xí)一棵樹且是回歸問題的情況。這時(shí)候一階導(dǎo)數(shù)是Y，二階導(dǎo)數(shù)是1），
③ 對(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ù)就加入分裂后的左子樹，否則加入分裂后的右子樹。 8.并行支持與優(yōu)化LightGBM原生支持并行學(xué)習(xí)，目前支持「特征并行」和「數(shù)據(jù)并行」的兩種，LightGBM針對(duì)這兩種并行方法都做了優(yōu)化。
1）特征并行LightGBM在特征并行算法中，通過在本地保存全部數(shù)據(jù)避免對(duì)數(shù)據(jù)切分結(jié)果的通信。
2）數(shù)據(jù)并行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í)別。在數(shù)據(jù)量很大的時(shí)候，使用投票并行可以得到非常好的加速效果。
9.網(wǎng)絡(luò)通信優(yōu)化XGBoost由于采用Pre-sorted算法，直接通信代價(jià)比較大；LightGBM采用的histogram算法通信代價(jià)小，通過使用集合通信算法，能夠?qū)崿F(xiàn)并行計(jì)算的線性加速。 10.參考資料 |
|
|
