引言https://blog.csdn.net/ShowMeAI/article/details/123406621 之前ShowMeAI對強(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一樣是對GBDT的優(yōu)化和高效實(shí)現(xiàn),，原理有一些相似之處，但它很多方面比XGBoost有著更為優(yōu)秀的表現(xiàn),。官方給出的這個(gè)工具庫模型的優(yōu)勢如下：
下圖是一組實(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ù)多次,。
面對工業(yè)級海量的數(shù)據(jù),，普通的GBDT算法無法滿足需求,。LightGBM提出的主要原因之一，就是為了解決上述大數(shù)據(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針對其中的一部分進(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生長方式XGBoost采用Level-wise的增長策略：基于層進(jìn)行生長,，直到達(dá)到停止條件。這種增長策略方便并行計(jì)算每一層的分裂節(jié)點(diǎn)，提高了訓(xùn)練速度,，但同時(shí)也因?yàn)楣?jié)點(diǎn)增益過小增加了很多不必要的分裂,，增加了計(jì)算量。
3）對cache優(yōu)化不友好在預(yù)排序后,，特征對梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣,，無法對cache進(jìn)行優(yōu)化,。同時(shí)，在每一層長樹的時(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ì)算量優(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.決策樹生長策略1）樹生長策略調(diào)整直方圖算法之上，LightGBM進(jìn)行進(jìn)一步的優(yōu)化,。它沒有使用大多數(shù)GBDT工具使用的按層生長（Level-wise）的決策樹生長策略,，而使用了帶有深度限制的按葉子生長（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（按層生長）策略生長的,，能夠同時(shí)分裂同一層的葉子,，從而進(jìn)行多線程優(yōu)化，不容易過擬合,。 但不加區(qū)分的對待同一層的葉子,，帶來了很多沒必要的開銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低,，沒必要進(jìn)行搜索和分裂,。 3）LightGBM：Leaf-wiseLightGBM采用Leaf-wise（按葉子生長）生長策略，每次從當(dāng)前所有葉子中找到分裂增益最大（一般也是數(shù)據(jù)量最大）的一個(gè)葉子,，然后分裂,，如此循環(huán)。
同Level-wise相比,，在分裂次數(shù)相同的情況下,，Leaf-wise可以降低更多的誤差，得到更好的精度,。Leaf-wise的缺點(diǎn)是可能會(huì)長出比較深的決策樹,，產(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)化了對類別型特征的支持,，可以直接輸入類別特征，不需要額外的編碼或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中加入了很多對這個(gè)方法的約束和正則化,。
求解類別型特征的最優(yōu)切分的具體流程如下： ① 離散特征建立直方圖的過程 統(tǒng)計(jì)該特征下每一種離散值出現(xiàn)的次數(shù),，并從高到低排序，并過濾掉出現(xiàn)次數(shù)較少的特征值,。然后為每一個(gè)特征值,，建立一個(gè)bin容器，對于在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í)上例中只是為了便于理解,，只針對了學(xué)習(xí)一棵樹且是回歸問題的情況。這時(shí)候一階導(dǎo)數(shù)是Y,，二階導(dǎo)數(shù)是1）,，
③ 對于連續(xù)特征,，劃分閾值只有一個(gè),。對于離散值可能會(huì)有多個(gè)劃分閾值，每一個(gè)劃分閾值對應(yīng)著一個(gè)bin容器編號,。 當(dāng)使用離散特征進(jìn)行分裂時(shí),，只要數(shù)據(jù)樣本對應(yīng)的bin容器編號在這些閾值對應(yīng)的bin集合之中，這條數(shù)據(jù)就加入分裂后的左子樹,，否則加入分裂后的右子樹,。 8.并行支持與優(yōu)化LightGBM原生支持并行學(xué)習(xí)，目前支持「特征并行」和「數(shù)據(jù)并行」的兩種,，LightGBM針對這兩種并行方法都做了優(yōu)化,。
1）特征并行LightGBM在特征并行算法中,，通過在本地保存全部數(shù)據(jù)避免對數(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ù)級別。在數(shù)據(jù)量很大的時(shí)候,，使用投票并行可以得到非常好的加速效果,。
9.網(wǎng)絡(luò)通信優(yōu)化XGBoost由于采用Pre-sorted算法，直接通信代價(jià)比較大,；LightGBM采用的histogram算法通信代價(jià)小,，通過使用集合通信算法，能夠?qū)崿F(xiàn)并行計(jì)算的線性加速,。 10.參考資料 |
|
|
