LightGBM詳解

• LightGBM原理
• • GOSS
  • EFB
  • 直方圖算法
  • • 問題一：如何將特征值映射到bin中？
    • 問題二：如何構(gòu)建直方圖
  • 直方圖作差加速
  • leaf-wise分裂策略
• LightGBM加速的原因
• LightGBM的優(yōu)劣點
• • 優(yōu)點
  • 劣處
• LightGBM的參數(shù)

??盡管XGBoost和pGBRT等對GBDT有所改善，但是LightGBM認為在數(shù)據(jù)量大、特征多的時候，XGBoost和pGBRT等的有效性和可拓展性仍然不被滿足。一個最主要的原因是對于每一個特征，都需要遍歷所有的數(shù)據(jù)樣例，來估計所有可能分裂點的信息增益（這里叫增益比較恰當），正因如此，非常耗時。
??
??故LightGBM提出了兩個改進思路，GOSS（Gradient-based One-Side Sampling，基于梯度的單邊采樣）和EFB（Exclusive Feature Bundling，互斥特征捆綁）。
???? GOSS： 每個樣本在計算信息增益過程中，有不同的梯度，由信息增益的定義可知，梯度大的樣本會貢獻較大的梯度。因此排除很大比例的梯度小的數(shù)據(jù)樣例，用剩下的數(shù)據(jù)樣本估計信息增益，證明梯度大的樣本更重要。
???? EFB：捆綁互斥的特征來減少特征數(shù)，盡管這是個NP問題，但一個貪心算法仍然能獲得一個好的近似分數(shù)。因此，可以在不損失準確率的前提下，降低特征的個數(shù)。
??LightGBM可以認為是GBDT加入了GOSS和EFB的改善。在大量公開數(shù)據(jù)集的實驗表明，LightGBM比GBDT快20多倍，并且準確率相當。
??
??GBDT+pre-sorted：通過忽略特征中的零值（稀疏性導致），來降低訓練成本；
??GBDT+Histogram-based：無有效的稀疏優(yōu)化方法，因為無論特征是否為0，都需要找到條件的箱值。
??

LightGBM原理

GOSS

??AdaBoost中每個樣本有權重，但是GBDT中每個樣本沒有權重，因此AdaBoost中的抽樣方法不能直接在GBDT中應用。但是GBDT的每個樣本含有的梯度對數(shù)據(jù)抽樣具有有用的信息。樣本的梯度小，那么它的訓練誤差就小，總是訓練的很好。一個直接的方法就是丟棄這些梯度小的樣本，但是會導致數(shù)據(jù)分布變化，會損壞學習器的精度。為了避免這個問題，提出GOSS。
??正如上所述，GOSS為了避免數(shù)據(jù)分布改變的問題，其目的是選擇梯度大的樣本，對于梯度小的樣本，采用下采樣的方式，但在下采樣過程中，僅僅隨機地排除梯度小的樣本，而僅僅隨機排除，達到的效果比隨機均勻下采樣更好（疑問，梯度大小的判斷標準是什么？）。
??GOSS先根據(jù)所有樣本的梯度絕對值進行排序，選取前$a?100\%$個樣本（稱為集合$A$），在剩下的$(1?a)?100\%$個樣本（稱為集合$A^c$）中，隨機抽取$b?100\%$個樣本（稱為集合$B$，$B$的大小為$b?|A^c|$）（則一共隨機選取的梯度小的樣本占比$b?(1?a)?100\%$）生成一個小梯度樣本集。在小梯度樣本計算信息增益時，乘以一個常數(shù)系數(shù)$\frac{1?a}{b}$。這樣，只需要更多的關注訓練不足的樣本，而沒有較多的改變原始數(shù)據(jù)分布。
??
??GBDT的分裂準則：令$O$為決策樹的一個分裂節(jié)點上的訓練數(shù)據(jù)，在這個分裂節(jié)點上，特征$j$在點$d$上分裂的方差增益為：
$$V_{j|O}(d)=\frac{1}{n_O}?\frac{{\left({\sum }_{\left\{x_i\in O:x_{ij}\le d\right\}}{g}_i\right)}^2}{n_{l|O}^j(d)}+\frac{{\left({\sum }_{\left\{x_i\in O:x_{ij}>d\right\}}{g}_i\right)}^2}{n_{r|O}^j(d)}?$$$$\text{?where?}{n}_O=\sum I\left[x_i\in O\right],n_{l|O}^j(d)=\sum I\left[x_i\in O:x_{ij}\le d\right]\text{?and?}{n}_{r|O}^j(d)=\sum I\left[x_i\in O:x_{ij}>d\right]$$
??對于特征$j$，決策樹算法選擇最優(yōu)的分裂點$d_j^{?}=argma{x}_d{V}_j(d)$，然后計算最大的增益$V_j(d_j^{?})$，然后根據(jù)特征$j^{?}$在點$d_{j^{?}}$處將數(shù)據(jù)分裂為左右子節(jié)點。
??對于GOSS，在$A\cup B$集合上，通過估計方差增益${\tilde{V}}_j(d)$來劃分數(shù)據(jù)，$${\tilde{V}}_j(d)=\frac{1}{n}\left(\frac{{\left({\sum }_{x_i\in A_i}{g}_i+\frac{1?\alpha }{b}{\sum }_{x_i\in B_l}{g}_i\right)}^2}{n_i^j(d)}+\frac{{\left({\sum }_{x_i\in A_r}{g}_i+\frac{1?a}{b}{\sum }_{x_i\in B_r}{g}_i\right)}^2}{n_r^j(d)}\right)$$$$\text{?where?}{A}_l=\{x_i\in A：x_{ij}\le d\},A_r=\{x_i\in A:x_{ij}>d\},B_l=\{x_i\in B：x_{ij}\le d\},B_r=\{x_i\in B：x_{ij}>d\}$$
??同時$\frac{1?a}{b}$被用來歸一化數(shù)據(jù)集$B$的梯度之和。
??因此，通過GOSS，我們只需要在較小數(shù)據(jù)集上計算${\tilde{V}}_j(d)$來決定分裂點即可，而不需要在完整數(shù)據(jù)集計算。這樣做的優(yōu)點是（1）大幅降低計算成本；（2）不會損失多少訓練準確性；（3）比隨機抽樣本表現(xiàn)更好。

??令$\epsilon (d)=|{\tilde{V}}_j(d)?V_j(d)|$作為GOSS的近似誤差，${\bar{g}}_l^j(d)=\frac{{\sum }_{x_i\in {\left(A\cup A^c\right)}_l}|g_i|}{n_l^j(d)}$，${\bar{g}}_r^j(d)=\frac{{\sum }_{x_i\in {\left(A\cup A^c\right)}_r}|g_i|}{n_r^j(d)}$，則$$\mathcal{E}(d)\le C_{a,b}^2\ln 1/\delta ?\max \left\{\frac{1}{n_l^j(d)},\frac{1}{n_r^j(d)}\right\}+2D{C}_{a,b}\sqrt{\frac{\ln 1/\delta }{n}},(1)$$$$\text{?where?}{C}_{a,b}=\frac{1?a}{\sqrt{b}}\underset{x_i\in A^c}{\max }\left|g_i\right|,\text{?and?}D=\max \left({\bar{g}}_l^j(d),{\bar{g}}_r^j(d)\right)$$
??基于此，有如下結(jié)論：（1）GOSS的漸近近似幾率為$O(\frac{1}{n_l^j(d)}+\frac{1}{n_r^j(d)}+\frac{1}{\surd n})$，如果分裂不平衡（例如$n_l^j(d)\ge O(\surd n)$或者$n_r^j(d)\ge O(\surd n)$），則近似幾率取決于式（1）的第二項（當n->∞，第二項趨向于0），這意味著當樣本數(shù)量很大時，近似幾率相當準確。（2）當$a=0$時，GOSS退化為隨機采樣算法，當$a=1$時，GOSS算法變?yōu)椴扇≌麄€樣本的算法。

??GOSS的泛化性能。令泛化誤差為${\epsilon }_{gen}^{GOSS}(d)=|{\tilde{V}}_j(d)?V_{?}(d)|$（為抽樣的訓練樣本方差增益與真實的方差增益之差）$\le |{\tilde{V}}_j(d)?V_j(d)|+|V_j(d)?V_{?}(d)|?{\epsilon }_{GOSS}(d)+{\epsilon }_{gen}(d)$，則采樣可提高基學習器的多樣性（潛在改善泛化表現(xiàn)）。

??以上說的是GOSS的樣本采樣的方式（不同于平常的隨機抽樣）。下面闡述EFB的特征采樣方式（不同于一般的特征抽樣方法）。

EFB

??實際應用過程中，盡管有大量的特征，但是很多特征都是相當稀疏的，這提供了一個幾乎無損的方法來減少有效特征的數(shù)量的可能性。將互斥的特征捆綁為一個特征，設計一個有效的算法，將優(yōu)化捆綁問題作為圖著色問題，使用貪心算法，近似求解。對特征捆綁，可將復雜度從$O(data?feature)$降到$O(data?bundle)$，其中$bundle$遠遠小于$feature$，這就是加速的原因。
??這涉及兩個問題，（1）如何確定哪些特征應該被捆綁？（2）如何去構(gòu)造這些捆綁？
??對于第一個問題，是一個$NP?hard$，即在多項式時間內(nèi)，無法找到一個精確方式。因此找到一個近似算法。$a$、將最優(yōu)的捆綁問題轉(zhuǎn)化為圖著色問題（特征為點，如果任何兩個特征之間不互斥，則添加邊）；$b$、用貪心的算法可產(chǎn)生合理的捆綁（一個常數(shù)逼近比率）；$c$、因為有少部分特征，不是$100\%$互斥，若允許小的沖突，可以得到更小度量的特征綁定和提高計算效率（選擇合適小的沖突比率，能平衡準確率和效率）。
??貪心算法：（1）構(gòu)建帶權重的邊，該權重依賴于所以特征之間的總沖突；（2）根據(jù)特征度降序排序特征；（3）檢查每個特征（排序列表中的），然后指派特征到一個存在的捆綁（包含小的沖突）或創(chuàng)建一個新的捆綁。其時間復雜度為$O(featur{e}^2)$。特征數(shù)多時，時間復雜度較高，仍然不可接受，故可提出一個更高效的無圖有序策略以進一步提升效率，依靠非零值的數(shù)量排序（和度排序非常相似），非零值呢個導致更高概率的沖突。
??對于第二個問題，為了降低訓練復雜度，需要在同一個捆綁中，將特征進行整合。關鍵是確保原始特征能從特征捆綁中區(qū)分出來。由于基于直方圖的算法將特征值以離散箱的形式存儲而不是連續(xù)值存儲，因此可以利用不同箱中的排他特征來構(gòu)建特征捆綁。通過增加偏移估計，可以實現(xiàn)的這樣的特征捆綁，達到減少特征的目的。
??EFB可以捆綁很多互斥特征至更稀疏的特征，對于零值特征可以避免不必要的計算。通過用表標記非零值來直接忽視零值特征以優(yōu)化基礎的直方圖算法，可使直方圖構(gòu)建成本從$O(data)$降至$O(non\_zero\_data)$，但值得注意的是，在整個樹的生長過程中，用表標記的方法需要額外的內(nèi)存和計算成本。

直方圖算法

??LIghtGBM選擇了基于Histogram的決策樹算法，相比于XGBoost采用預排序處理分裂節(jié)點，LightGBM的Histogram算法在內(nèi)存消耗和計算代價上都有很多優(yōu)勢。
??直方圖算法的原理：對于連續(xù)特征，先將連續(xù)的浮點特征值離散化為k整數(shù)，同時構(gòu)造成一個寬度為k的直方圖（bins）；對于分類特征，每一種取值放入一個bin，且當取值的個數(shù)大于max bin數(shù)時，忽略那些很少出現(xiàn)的category值。在遍歷數(shù)據(jù)的時候，根據(jù)離散化后的值作為索引，在直方圖中累積統(tǒng)計量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點（在XGBoost中需要遍歷所有離散化的值，而LightGBM通過建立直方圖只需要遍歷k個直方圖的值）。
??因此，在節(jié)點分裂的時候，不需要按照預排序算法那樣對每個特征計算#data遍，僅需要計算#bins遍，大大加快了訓練速度。
??直方圖優(yōu)化算法需要在訓練前預先將特征值轉(zhuǎn)化為bin value，也就是對每個特征的取值做個分段函數(shù)，將所有樣本在該特征上劃分到某一段（bin）中，最終把特征值從連續(xù)值轉(zhuǎn)化成了離散值。值得注意的是，特征值對應的bin value在整個訓練過程中是不會改變的。
??直方圖優(yōu)化算法過程：
??（1）對每個特征，為其創(chuàng)建一個直方圖，這個直方圖存儲兩類信息，分別是每個bin中樣本的梯度之和，以及每個bin中樣本數(shù)量。
??（2）對于每個特征，遍歷所有的樣本，累積上述的兩類統(tǒng)計值到樣本所屬的bin中，即直方圖的每個bin中包含了一定的樣本，在此計算每個bin中的樣本梯度之和并對bin中的樣本計數(shù)。
??（3）對于某個葉節(jié)點，遍歷所有的bin，分別以當前bin作為分割點，累加其左邊的bin至當前bin的梯度和以及樣本數(shù)量，并與父節(jié)點上的總梯度和以及總樣本數(shù)量相減，得到右邊所有bin的梯度和以及樣本數(shù)量，并以此計算增益，在遍歷過程中，取最大的增益，以此時的特征和bin的特征值作為分裂節(jié)點的特征和分裂特征取值。
??（4）對所有的葉節(jié)點，重復上述操作，遍歷所有的特征，找到增益最大的特征及其劃分值，以此來分裂該葉節(jié)點。
??從以上分析可知，有如下兩個問題：

問題一：如何將特征值映射到bin中？

??由于LightGBM可以處理類別特征，因此對連續(xù)特征和類別特征的處理方式是不一樣的。
??（1）對于連續(xù)特征，可以得到數(shù)值型特征取值（負數(shù)，0，正數(shù)）的各個bin的切分點。
??（2）對于離散特征（LightGBM支持類別特征，采用many vs many方式，不需要做One-Hot編碼），先對特征取值出現(xiàn)的次數(shù)排序（從大到小），忽略一些出現(xiàn)次數(shù)很少的特征取值，為每一個特征值建立一個bin容器，對于在bin容器內(nèi)出現(xiàn)次數(shù)較少的特征值直接過濾掉，不建立bin容器。

問題二：如何構(gòu)建直方圖

??對于離散特征或者連續(xù)特征，每一個劃分閾值對應著一個bin容器編號，根據(jù)不同的bin容器，構(gòu)建直方圖，累加一階和二階梯度還有count。
??

直方圖作差加速

??對于Histogram算法，有一個技巧就是直方圖作差加速：一個葉節(jié)點的直方圖（梯度之和以及樣本數(shù)量）可以由它的父節(jié)點的直方圖與它兄弟的直方圖作差得到。利用這個方法，LightGBM可以在構(gòu)造一個葉節(jié)點（含有較少數(shù)據(jù)）的直方圖后，可使用非常微小的代價就可以得到它兄弟葉節(jié)點（含有較多數(shù)據(jù)）的直方圖。
??因為構(gòu)建兄弟葉節(jié)點的直方圖是作差得到的，時間復雜度僅為$O(bins)$，幾乎可以忽略，比起不作差得到的兄弟節(jié)點的直方圖，速可以提升一倍。

leaf-wise分裂策略

??level-wise（XGBoost的）是指對每一層所有的節(jié)點做無差別分裂，盡管部分節(jié)點的增益比較小，依然會進行分裂，帶來了不必要的開銷（值得注意的是它容易多線程優(yōu)化，方便控制模型復雜度，不容易過擬合）。

??leaf-wise（LightGBM的）是指在當前所有葉節(jié)點中選擇分類增益最大的節(jié)點進行分裂，并進行最大深度限制，避免過擬合。

??在分裂次數(shù)相同的情況下，leaf-wise可以降低更多的誤差，得到更好的精度。但leaf-wise的缺點是可能會長出比較深的決策樹，容易過擬合，因此在leaf-wise之上增加了一個最大深度的限制，在保證高效的同時防止過擬合。

LightGBM加速的原因

??LightGBM的加速主要來自于GOSS+EFB，以及并行處理，并且不會損失準確率。
??GOSS加速的原因：根據(jù)梯度抽樣，用抽樣后的數(shù)據(jù)訓練樹。但速度并未如抽樣比例那樣，因為抽樣之前要對全樣本進行梯度計算，并對全樣本進行預測。值得注意的是，GOSS抽樣方式優(yōu)于隨機抽樣。
??EFB加速的原因：合并許多稀疏特征（包括One-Hot和隱式排他特征）為更少的特征（在捆綁過程中），基于直方圖算法，其也改善了內(nèi)存（許多先驗的孤立特征被捆綁在一起）。
??高效并行加速：（1）特征并行，在不同的機器上的不同特征集上分別尋找最優(yōu)的分割點，在機器間同步最優(yōu)的分割點，其通過本地保存全部數(shù)據(jù)避免對數(shù)據(jù)切分結(jié)果的通信；（2）數(shù)據(jù)并行：不同的機器先在本地構(gòu)造直方圖，然后進行全局合并，最后在合并的直方圖上尋找最優(yōu)分割點，其使用分散規(guī)約（Reduce scatter）把直方圖合并的任務分攤到不同的機器上，并利用直方圖作差，降低了通信量，減少了通信時間。
??LightGBM的GOSS和EFB改進能處理大量數(shù)據(jù)和大量特征，能顯著提高算力和降低內(nèi)存消耗。

LightGBM的優(yōu)劣點

優(yōu)點

??1、由于使用基于直方圖算法，效率高、內(nèi)存使用低（內(nèi)存消耗僅是預排序算法的1/8）；
??2、用直方圖算法的數(shù)據(jù)并行時，數(shù)據(jù)間通信代價低（值得注意的是，XGBoost也使用直方圖來降低通信代價）；
??3、計算上的優(yōu)勢是大幅減少了計算分割點增益的次數(shù)。對每個特征，預排序需要對每一個不同的特征值都計算一次分割增益，而直方圖算法只需要計算#bins次；
??4、cache-miss。預排序中，對梯度的訪問以及對于索引表的訪問，造成嚴重的cache-miss問題。但直方圖算法，在計算增益的時候，只需要對bin進行訪問，造成的cache-miss問題小的多。

劣處

??直方圖算法不能找到很精確的分割點，因為它訪問的是bins，但從實驗結(jié)果來看，直方圖算法的測試誤差效果甚至更好。因為決策樹對分割點的精確程度不太敏感，并且較“粗”的分割點也自帶正則化的效果，再加上boosting算法本身就是弱分類器的集成。

??后續(xù)工作：對于GOSS，需要優(yōu)化$a$和$b$的選擇；對于EFB，需要優(yōu)化處理更多的特征無論是否稀疏。

LightGBM的參數(shù)

??控制參數(shù)
??max_depth：樹的最大深度。當模型過擬合時，可以考慮首先降低max_depth。
??min_data_in_leaf：葉子可能具有的最小記錄數(shù)。默認是20，過擬合時使用。
??feature_fraction：例如為0.8時，意味著在每次迭代中隨機選擇80%的參數(shù)來構(gòu)建樹。boosting為random forest時使用。
??bagging_fraction：每次迭代時用的數(shù)據(jù)比例。用于加快訓練速度和緩解過擬合。
??early_stopping_round：如果一次驗證數(shù)據(jù)的一個度量在最近的early_stopping_round回合中沒有提高，模型將停止訓練。加速分析，減少過多迭代。
??lambda_l1：L1正則化，也稱reg_alpha，0~1。
??lambda_l2：L2正則化，也稱reg_lambda，0~1。
??main_gain_to_split：描述分裂的最小gain。控制樹有用的分裂。
??max_cat_group：在group邊界上找到分割點。當類別數(shù)量很多的時候，找分割點容易過擬合。
??cat_smooth：default=10，用于分類特征，降低噪聲在分類特征中的影響，尤其是對數(shù)據(jù)很少的類別。
??
??核心參數(shù)
??boosting：default=gbdt，還有rf，dart，doss。可選參數(shù)比XGBoost中多。
??num_thread：指定線程的個數(shù)，數(shù)字設置成CPU內(nèi)核數(shù)比線程數(shù)訓練更快，并行學習不應該設置成全部線程，這反而使得訓練速度不佳。
??application：學習目標和損失函數(shù)，default=regression。
????regression:
??????regression_l2：L2 loss, alias=regression, mean_squared_error, mse
??????regression_l1：L1 loss, alias=mean_absolute_error, mae
??????huber：Huber loss
??????fair：Fair loss
??????possion：Possion regression
??????quartile：Quartile regression
??????quartile_l2：類似于quartile，但使用了L2 loss
????binary: binary log loss classification application
????multi-class: classification
??????multiclass：softmax目標函數(shù)，應該設置好num_class
??????multiclassova：One-vs-All，二分類目標函數(shù)，應該設置好mun_class
????cross-entropy: application，取值為[0,1]
??????xentropy：目標函數(shù)為cross-entropy（同時有可選擇的線性權重）,alias=cross_entropy
??????xentlambda：替代參數(shù)化的cross-entropy，alias=cross_entropy_lambda
????lambdarank: lambdarank application
??????在lambdarank任務中標簽應該為int type，數(shù)值越大代表相關性越高（例如 0：bad，1：fair，2：good，3：perfect）
??????label_gain：可以用來設置int標簽的增益（權重）
??vaild：驗證集選用，支持多驗證集，以,分割
??learning_rate：梯度下降的步長，default=0.1，一般在0.05~0.2之間。
??num_leaves:default=31，這代表的是一棵樹上的葉子樹。
??device：default=cpu，options=cpu、gpu
????- 為樹學習選擇合適的設備，可以使用GPU來獲得更快的學習速度。GPU默認使用32位浮點數(shù)來求和，也可以設置gpu_use_dp=tree來啟用64位浮點數(shù)，但其訓練速度更低；
????- 建議使用較小的max_bin（例如63）來獲得更快的速度；
????參考相關指南構(gòu)建GPU版本。
??
??度量參數(shù)
??metric：default={l2 for regression}，{binary_logloss for binary classification}，{ndcg for lambdarank}
????l1: absolute loss, alias=mean_absolute_error, mae
????l2: square loss, alias=mean_squared_error, mse
????l2_root: root square loss, alias=root_mean_squared_error, rmse
????quantile: Quantile regression
????huber: Huber loss
????fair: Fair loss
????possion Poisson regression
????ndcg: NDCG
????map: MAP
????auc: AUC
????binary_logloss: log loss
????binary_error: 樣本: 0 的正確分類, 1 錯誤分類
????multi_logloss: mulit-class 損失日志分類
????multi_error: error rate for mulit-class 出錯率分類
????xentropy: cross-entropy (與可選的線性權重), alias=cross_entropy
????xentlambda: “intensity-weighted” 交叉熵, alias=cross_entropy_lambda
????kldiv: Kullback-Leibler divergence, alias=kullback_leibler
????支持多指標，使用,分隔

總結(jié)

以上是生活随笔為你收集整理的LightGBM详解--原理+技巧+参数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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