LightGBM

摘要

Gradient Boosting Decision Tree (GBDT)非常流行卻鮮有實(shí)現(xiàn)情萤，只有像XGBoost和pGBRT定踱。盡管這些實(shí)現(xiàn)中采用了許多工程優(yōu)化劳吠，當(dāng)特征維度較高和數(shù)據(jù)量巨大的時(shí)候懒闷，其仍然存在效率和可擴(kuò)展性的問題村刨。一個(gè)主要原因就是對(duì)于每一個(gè)特征的每一個(gè)可能分裂點(diǎn)告抄，都需要遍歷全部數(shù)據(jù)計(jì)算信息增益，這一過程非常耗時(shí)嵌牺。針對(duì)這一問題打洼，本文提出兩種新方法：Gradient-based One-Side Sampling (GOSS) 和Exclusive Feature Bundling (EFB)（基于梯度的one-side采樣和互斥的特征捆綁）。在GOSS中逆粹，我們排除大量梯度較小的數(shù)據(jù)實(shí)例募疮，只用剩下的來(lái)估計(jì)信息增益，我們證明僻弹，由于梯度大的實(shí)例在計(jì)算信息增益中扮演重要角色阿浓，GOSS可以用更小的數(shù)據(jù)量對(duì)信息增益進(jìn)行相當(dāng)準(zhǔn)確的估計(jì)。對(duì)于EFB蹋绽，我們捆綁互斥的特征（互斥特征：例如特征間很少同時(shí)非零搔扁。），來(lái)降低特征的個(gè)數(shù)蟋字。我們證明找到最優(yōu)的捆綁特征是NP難的稿蹲，但貪心算法能夠?qū)崿F(xiàn)相當(dāng)好的近似，從而在不影響分割點(diǎn)確定精度的前提下鹊奖，有效地減少了特征的數(shù)量苛聘。（犧牲一點(diǎn)分割準(zhǔn)確率降低特征數(shù)量），這一算法命名為L(zhǎng)ightGBM忠聚。在多個(gè)公共數(shù)據(jù)集上的實(shí)驗(yàn)表明设哗，LightGBM加速傳統(tǒng)GBDT訓(xùn)練過程20倍以上，同時(shí)能夠?qū)崿F(xiàn)相同的精度两蟀。

1. introduction

GBDT因?yàn)槠涓咝酝摇?zhǔn)確性、可解釋性赂毯，成為了廣泛使用的機(jī)器學(xué)習(xí)算法战虏。GBDT在許多機(jī)器學(xué)習(xí)任務(wù)上取得了目前最好的效果拣宰，例如多分類，點(diǎn)擊率預(yù)測(cè)烦感，排序巡社。但最近幾年隨著大數(shù)據(jù)的爆發(fā)（特征量和數(shù)據(jù)量），GBDT面臨新的挑戰(zhàn)手趣，特別是準(zhǔn)確率和效率的平衡晌该。

傳統(tǒng)的GBDT實(shí)現(xiàn)需要對(duì)每個(gè)特征掃描所有的數(shù)據(jù)樣本來(lái)評(píng)估所有可能分割點(diǎn)的信息增益。因此他們的計(jì)算復(fù)雜度與特征的數(shù)量和樣本數(shù)量成正比绿渣。這使得當(dāng)遇到大數(shù)據(jù)量時(shí)朝群，這些實(shí)現(xiàn)非常耗時(shí)。

為了解決這個(gè)問題中符，一個(gè)直接的思想是降低數(shù)據(jù)樣本的數(shù)量和特征的數(shù)量〗郑現(xiàn)在有工作根據(jù)根據(jù)樣本權(quán)重采樣來(lái)加速boosting的訓(xùn)練過程，由于GBDT中沒有樣本權(quán)重不能使用舟茶。在這篇論文中谭期，我們提出了兩種新穎的技術(shù)來(lái)實(shí)現(xiàn)此目標(biāo)。

Gradient-based One-Side Sampling (GOSS)：盡管對(duì)于GBDT數(shù)據(jù)實(shí)例沒有直接的權(quán)重吧凉，我們注意到帶有不同梯度的數(shù)據(jù)樣本在信息增益的計(jì)算中發(fā)揮著不同的作用隧出。根據(jù)信息增益的定義，擁有更大梯度的樣例將對(duì)信息增益貢獻(xiàn)更大阀捅。因此在下采樣時(shí)胀瞪，為了維持信息增益精度，我們應(yīng)該盡量保留具有較大梯度的樣本（大于預(yù)設(shè)置的閾值饲鄙，或者在top百分位中）凄诞，同時(shí)隨機(jī)去除梯度小的樣本。我們證明忍级，在相同的采樣率下帆谍，該采樣機(jī)制將比均勻隨機(jī)采樣有更高的精度。尤其當(dāng)信息增益有較大的范圍時(shí)轴咱。

Exclusive Feature Bundling (EFB)：通常在真實(shí)應(yīng)用中汛蝙，盡管特征數(shù)量非常多，但對(duì)應(yīng)的特征空間是格外稀疏的朴肺。這為我們?cè)O(shè)計(jì)一種近乎無(wú)損的方法來(lái)減少有效特征的數(shù)量提供了可能性窖剑。尤其在稀疏特征空間中，許多特征是互斥的：他們幾乎不會(huì)同時(shí)為非零戈稿。我們可以捆綁這些互斥特征西土。為此，我們?cè)O(shè)計(jì)了一個(gè)有效的算法鞍盗，將最優(yōu)的捆綁問題簡(jiǎn)化為圖的著色問題(將特征作為頂點(diǎn)需了，在不是互斥的兩個(gè)特征間添加邊)跳昼，使用貪婪算法求解。

論文內(nèi)容組織：第二章回顧GBDT算法和相關(guān)工作援所；第三章介紹GOSS和EFB庐舟；第四章展示實(shí)驗(yàn)結(jié)果欣除；第五章總結(jié)

2. Preliminaries

2.1 GBDT及其復(fù)雜度分析

GBDT是決策樹的一種集成模型住拭。在每輪迭代中，GBDT學(xué)習(xí)決策樹來(lái)擬合損失函數(shù)的負(fù)梯度（近似殘差）历帚。

GBDT的主要時(shí)間花費(fèi)在學(xué)習(xí)決策樹滔岳，而學(xué)習(xí)決策樹大部分時(shí)間消耗在于尋找最優(yōu)劃分點(diǎn)。廣泛采用的尋找劃分點(diǎn)方法使用預(yù)排序算法挽牢，在預(yù)排序的特征值上列舉所有可能的劃分點(diǎn)谱煤。該算法比較簡(jiǎn)單可以找到最有劃分點(diǎn)，但是其訓(xùn)練時(shí)間和內(nèi)存消耗是較高的禽拔。另一種流行的算法是基于直方圖的算法刘离。該算法不通過預(yù)排序特征值來(lái)尋找劃分點(diǎn)，它將連續(xù)特征值分桶到不同離散bin中睹栖，使用這些bin在訓(xùn)練過程中來(lái)構(gòu)造特征直方圖硫惕。由于基于直方圖的算法在時(shí)間和內(nèi)存上的效率更高，我們將采用這種方法野来。

histogram-based算法通過特征直方圖尋找最優(yōu)切分點(diǎn)恼除，其建直方圖消耗

2.2 相關(guān)工作

3. Gradient-based One-Side Sampling

在該章節(jié)，我們提出了一種新穎的采樣方法聊浅，它可以在降低樣本數(shù)量和保持學(xué)得的決策樹精度間取得好的平衡餐抢。

3.1 算法描述

AdaBoost中，樣本權(quán)重是數(shù)據(jù)實(shí)例重要性的指標(biāo)狗超。然而在GBDT中沒有原始的樣本權(quán)重弹澎，因此不能直接應(yīng)用Adaboost提出的采樣方法。幸運(yùn)的是努咐，我們注意到GBDT中每個(gè)樣本的梯度在樣本采樣時(shí)提供了非常有用的信息苦蒿。即如果樣本擁有一個(gè)小的梯度，該樣例的訓(xùn)練誤差也是小的渗稍，已經(jīng)被訓(xùn)練好的佩迟。一種直接的想法就是丟掉小梯度的樣本团滥。然而這樣做將會(huì)改變數(shù)據(jù)分布，將會(huì)損害所學(xué)得得模型得精度报强。為了避免這個(gè)問題灸姊，我們提出了一種名為GOSS得采樣方法。

GOSS保留所有梯度較大得實(shí)例秉溉，在梯度小的實(shí)例中隨機(jī)采樣力惯。為了抵消數(shù)據(jù)分布的影響，在計(jì)算信息增益時(shí)召嘶，GOSS對(duì)小梯度樣例引入常量乘數(shù)父晶。GOSS首先根據(jù)樣例梯度的絕對(duì)值進(jìn)行排序，選取top

3.2 Theoretical Analysis

GBDT使用決策樹學(xué)習(xí)映射函數(shù)，該函數(shù)將輸入空間

image.png

image.png

image.png

Theorem 3.2

1. 數(shù)據(jù)量越大，誤差越小让蕾，精度越高
2. 隨機(jī)采樣是GOSS在
   
   時(shí)的一種特例浪规，多數(shù)情況下，GOSS優(yōu)于隨機(jī)采樣涕俗。

• GOSS的泛化性
  在GOSS近似準(zhǔn)確的情況下罗丰，GOSS的泛化性將近似于使用全量數(shù)據(jù)神帅；同時(shí)再姑，采樣會(huì)提高基學(xué)習(xí)器的多樣性，潛在的提升泛化性能找御。

4. Exclusive Feature Bundling

在這個(gè)章節(jié)元镀，我們提出一種新穎的方法來(lái)有效降低特征的數(shù)量。
高維數(shù)據(jù)通常是非常稀疏的霎桅。特征空間的稀疏性啟發(fā)我們?cè)O(shè)計(jì)一種無(wú)損的方法來(lái)降低特征的數(shù)量栖疑。尤其在稀疏特征空間中，許多特征互斥滔驶，即不同時(shí)取非零值遇革。我們可以捆綁互斥特征為單一特征。通過精心設(shè)計(jì)特征掃描算法揭糕，我們從捆綁特征中建立與單一特征相同的特征直方圖萝快。以這種方法，我們將建立直方圖的復(fù)雜度從

1. 怎么判斷哪些特征可以捆綁在一起
2. 怎樣構(gòu)建bundle吏口，即怎么把多個(gè)特征捆綁為單一特征
   Theorem 4.1 將特征劃分為最小數(shù)量的互斥包是NP-hard

proof: 我們引入圖著色問題奄容，由于圖著色問題是NP-hard，我們可以推斷以上結(jié)論
給定圖著色實(shí)例G=(V, E)产徊。以G的關(guān)聯(lián)矩陣的每一行為特征昂勒，得到我們問題的一個(gè)實(shí)例有|V|個(gè)特征。 很容易看到舟铜，在我們的問題中戈盈，一個(gè)獨(dú)特特征群與一組具有相同顏色的頂點(diǎn)相對(duì)應(yīng)，反之亦然深滚。

4.1 bunding

對(duì)于第一個(gè)問題奕谭，我們證明Theorem 4.1是NP-hard涣觉，即不可能在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)精確解。為了找到一個(gè)好的近似算法血柳，我們通過將特征視為頂點(diǎn)官册，在兩個(gè)不互斥的特征間添加邊，將最有綁定問題轉(zhuǎn)化為圖著色問題难捌。然后我們可以使用貪婪算法用于圖著色來(lái)進(jìn)行特征捆綁膝宁。我們注意到，有些特征盡管不是100%互斥的根吁，但幾乎不同時(shí)取非0值员淫。如果我們的算法運(yùn)行較小的沖突，我們可以得到更少數(shù)量的特征捆綁群击敌，并進(jìn)一步提升計(jì)算效率介返。通過簡(jiǎn)單的計(jì)算，隨即污染一小部分特征值將會(huì)影響訓(xùn)練精度沃斤，最多為：

1. 首先，我們構(gòu)建加權(quán)圖十厢，邊的權(quán)重對(duì)應(yīng)特征間的沖突等太。
2. 其次，我們以特征在圖中的度降序排列寿烟。
3. 最后澈驼，我們選取有序序列中的每一個(gè)特征，指派它到一個(gè)已存在的bundle中（有一個(gè)小的沖突筛武，由
   
   控制）缝其，或者創(chuàng)建一個(gè)新的nundle。時(shí)間復(fù)雜度為
   
   徘六，它僅在訓(xùn)練前處理一次内边。當(dāng)特征數(shù)量不是特別大時(shí)，該復(fù)雜度是可以接受的待锈，但是當(dāng)有數(shù)百萬(wàn)特征時(shí)也會(huì)有影響漠其，為了進(jìn)一步提高效率，我們提出一個(gè)更為高效不需要建立圖的排序策略：對(duì)特征的非零值數(shù)量進(jìn)行排序，由于更多的非零值通常導(dǎo)致更大可能的沖突和屎，因此它與采用度排序是類似的拴驮。

image.png

4.2 merge feature

對(duì)于第二個(gè)問題，我們需要好的方式來(lái)合并在同一個(gè)Bundle中的特征柴信，同時(shí)降低對(duì)應(yīng)的訓(xùn)練復(fù)雜度套啤。關(guān)鍵是確保原始特征值可以在特征bundle中區(qū)分。由于基于直方圖的算法存儲(chǔ)離散值而不是連續(xù)特征值随常，我們通過將互斥特征放在不同的箱中來(lái)構(gòu)建bundle潜沦。這可以通過將偏移量添加到特征原始值中實(shí)現(xiàn)。例如绪氛，假設(shè)我們?cè)赽undle中有兩個(gè)特征唆鸡，特征A取值[0,10)，特征B取值[0,20)枣察。我們添加偏移量10 到特征B中争占，使特征取值為[10,30)。之后我們可以合并特征A询件、B燃乍，使用取值為[0,30)的新特征代替A和B。
EFB可以捆綁許多互斥特征宛琅，將其轉(zhuǎn)化為稠密特征，來(lái)有效的避免對(duì)0特征值不必要的計(jì)算逗旁。事實(shí)上嘿辟，我們可以對(duì)每一個(gè)特征構(gòu)建對(duì)應(yīng)表記錄非零值來(lái)忽略0特征值，這樣也可以優(yōu)化基礎(chǔ)的直方圖算法片效。通過在表中掃描數(shù)據(jù)红伦，對(duì)一個(gè)特征建立直方圖的復(fù)雜度從

image.png

5. Experiments

主要是LightGBM在各大數(shù)據(jù)集上的表現(xiàn)蛮浑，及GOSS和EFB的有效性

6.優(yōu)缺點(diǎn)

6.1 內(nèi)存更小

XGBoost 使用預(yù)排序后需要記錄特征值及其對(duì)應(yīng)樣本的統(tǒng)計(jì)值的索引，而 LightGBM 使用了直方圖算法將特征值轉(zhuǎn)變?yōu)?bin 值只嚣，且不需要記錄特征到樣本的索引沮稚，將空間復(fù)雜度從 O(2*#data) 降低為 O(#bin) ，極大的減少了內(nèi)存消耗册舞；
LightGBM 采用了直方圖算法將存儲(chǔ)特征值轉(zhuǎn)變?yōu)榇鎯?chǔ) bin 值蕴掏，降低了內(nèi)存消耗；
LightGBM 在訓(xùn)練過程中采用互斥特征捆綁算法減少了特征數(shù)量，降低了內(nèi)存消耗盛杰。

6.2 速度更快

LightGBM 采用了直方圖算法將遍歷樣本轉(zhuǎn)變?yōu)楸闅v直方圖挽荡，極大的降低了時(shí)間復(fù)雜度；
LightGBM 在訓(xùn)練過程中采用單邊梯度算法過濾掉梯度小的樣本即供，減少了大量的計(jì)算徐伐；
LightGBM 采用了基于 Leaf-wise 算法的增長(zhǎng)策略構(gòu)建樹，減少了很多不必要的計(jì)算量募狂；
LightGBM 采用優(yōu)化后的特征并行办素、數(shù)據(jù)并行方法加速計(jì)算，當(dāng)數(shù)據(jù)量非常大的時(shí)候還可以采用投票并行的策略祸穷；
LightGBM 對(duì)緩存也進(jìn)行了優(yōu)化性穿，增加了 Cache hit 的命中率。

直方圖算法

這里額外補(bǔ)充下直方圖算法雷滚， 可以參照下面鏈接的講解需曾，很詳細(xì)：
Lightgbm 直方圖優(yōu)化算法深入理解

參考

• 『 論文閱讀』LightGBM原理-LightGBM: A Highly Efficient Gradient Boosting Decision Tree
• 終于有人把XGBoost 和 LightGBM 講明白了，項(xiàng)目中最主流的集成算法祈远！
• Lightgbm 直方圖優(yōu)化算法深入理解
• lgb直方圖算法源碼分析