Abstract
雖然目前已經(jīng)有比較高效的GBDT實(shí)現(xiàn)，如XGBoost和pGBRT，但是在特征維度很高數(shù)據(jù)量很大的時(shí)候依然不夠快。一個(gè)主要的原因是，對(duì)于每個(gè)特征，他們都需要遍歷每一條數(shù)據(jù)，對(duì)每一個(gè)可能的分割點(diǎn)去計(jì)算信息增益。為了解決這個(gè)問題，本文提出了兩個(gè)新技術(shù)：Gradient-based One-Side Sampling(GOSS)和Exclusive Feature Bundling(EFB)。
有了GOSS，我們?nèi)サ袅撕艽笠徊糠痔荻群苄〉臄?shù)據(jù)，只使用剩下的去估計(jì)信息增益(這里不會(huì)受長尾的影響嗎？)。我們證明了，由于梯度大的數(shù)據(jù)在計(jì)算信息增益的時(shí)候更重要，所以GOSS在小很多的數(shù)據(jù)上仍然可以取得相當(dāng)準(zhǔn)確的估計(jì)值。
有了EFB，我們捆綁互斥的特征(i.e.，他們經(jīng)常同時(shí)取值為0)，以減少特征的數(shù)量。我們證明了，對(duì)互斥特征尋找最佳的捆綁方式是一個(gè)NP難問題，當(dāng)時(shí)貪婪算法可以取得相當(dāng)好的近似率(因此可以在不顯著影響分裂點(diǎn)選擇的準(zhǔn)確性的情況下，顯著地減少特征數(shù)量)。
我們叫這種帶有GOSS和EFB的新GBDT算法為LightGBM。我們?cè)诙鄠€(gè)公共數(shù)據(jù)集的實(shí)驗(yàn)顯示，Lightgbm在準(zhǔn)確率相近的情況下，比常規(guī)的GBDT快了近20倍。
2 準(zhǔn)備知識(shí)
2.1 GBDT and Its Complexity Analysis
GBDT是一個(gè)關(guān)于決策樹的集成模型。在每一次迭代，GBDT會(huì)根據(jù)負(fù)梯度（也稱殘差）來學(xué)習(xí)決策樹。
在訓(xùn)練GBDT中，最耗資源的是學(xué)習(xí)決策樹和尋找決策樹的最佳分割點(diǎn)。一個(gè)尋找分割點(diǎn)的最流行的算法是pre-sorted algorithm [8][9]，它在pre-sorted的特征值上枚舉所有可能的分割點(diǎn)。這個(gè)算法雖然簡(jiǎn)單也可行，但是不高效。另一個(gè)比較流行的算法是histogram-based algorithm [10][11][12]，它講連續(xù)的特征值編入到離散區(qū)域中，并在訓(xùn)練中用這些區(qū)域構(gòu)建特征直方圖。由于后者更高效，所以我們基于此開展我們的工作。
As shown in Alg. 1, the histogram-based algorithm finds the best split points based on the featurehistograms. It costsO(#data?#feature)for histogram building andO(#bin?#feature)forsplit point finding. Since #bin is usually much smaller than #data, histogram building will dominatethe computational complexity. If we can reduce #data or #feature, we will be able to substantiallyspeed up the training of GBDT.
2.2 Related Work
2.2.1
相關(guān)的GBDT實(shí)現(xiàn)有：
- XGBoost --> pre-sorted algorithm and histogram-based algorithm
- pGBDT --> histogram-based algorithm
- scikit-learn --> pre-sorted algorithm
- gbm in R --> pre-sorted algorithm
其中XGBoost是在這之中表現(xiàn)最好的，所以我們用它來作為baseline。
2.2.2 有幾個(gè)問題
如何減少數(shù)據(jù)量
常用的減少訓(xùn)練數(shù)據(jù)量的方式是down sample。例如在[5]中，權(quán)重小于閾值的數(shù)據(jù)會(huì)被過濾掉，SGB在每一輪迭代中用隨機(jī)的子集訓(xùn)練弱學(xué)習(xí)器；在[6]中，采樣率會(huì)在訓(xùn)練過程中動(dòng)態(tài)調(diào)整。但是，所有這些工作除了SGB外都是基于AdaBoost的，并且由于GBDT沒有數(shù)據(jù)實(shí)例的權(quán)重，所以不能直接運(yùn)用到GBDT上。雖然SGB可以應(yīng)用到GBDT，但是它這種做法對(duì)acc影響太大了。
如何減少特征
類似的，為了減少特征的數(shù)量，需要過濾若特征[22, 23, 7, 24]。這通常用PCA和projection pursuit來做。可是，這些方法高度依賴一個(gè)假設(shè)，那就是特征包含相當(dāng)多的冗余的信息。而這個(gè)假設(shè)在實(shí)踐中通常不成立（因?yàn)橥ǔＬ卣鞫急辉O(shè)計(jì)為具有獨(dú)特作用的，移除了哪個(gè)都可能對(duì)訓(xùn)練的acc有影響）
關(guān)于稀疏的數(shù)據(jù)
現(xiàn)實(shí)應(yīng)用中的大規(guī)模數(shù)據(jù)通常是相當(dāng)稀疏的。使用pre-sorted algorithm的GBDT可以通過忽略值為0的特征來降低訓(xùn)練的開銷。而使用histogram-based algorithm的GBDT沒有針對(duì)稀疏數(shù)據(jù)的優(yōu)化方案，因?yàn)閔istogram-based algorithm無論特征值是否為0，都需要檢索特征的bin值，所以它能夠有效地利用這種稀疏特性。
為了解決上面的這些問題，我們提出了兩個(gè)新的技術(shù)——GOSS和EFB。下面會(huì)詳細(xì)介紹。
3 Gradient-based One-Side Sampling
這里，我們介紹一種用于GBDT的新的抽樣方法，它在保證acc的情況下減少了數(shù)據(jù)量。
簡(jiǎn)而言之，GOSS保留了梯度較大的數(shù)據(jù)，而從梯度較小的數(shù)據(jù)中隨機(jī)抽樣。為了補(bǔ)償對(duì)數(shù)據(jù)分布的影響，在計(jì)算信息增益時(shí)，為梯度較小的數(shù)據(jù)引入一個(gè)常數(shù)。具體來說，GOSS根據(jù)每個(gè)數(shù)據(jù)實(shí)例的梯度排序，選擇topa \times 100\%的實(shí)例。然后從剩下的數(shù)據(jù)中隨機(jī)抽樣b \times 100\%的實(shí)例。然后，在計(jì)算信息增益的時(shí)候，GOSS會(huì)將梯度小的那部分?jǐn)?shù)據(jù)乘上\frac{1-a}，起放大的作用（a, b < 1）。詳情看Alg.2
4 Exclusive Feature Bundling
本節(jié)我們介紹一個(gè)新方法顯著地減少特征數(shù)量。
高維度的數(shù)據(jù)通常是非常稀疏的，特征空間的稀疏性讓我們可以設(shè)計(jì)一個(gè)幾乎無損的方法去減少特征的數(shù)量。具體來說，在稀疏的特征空間中，許多特征是互斥的，i.e.，他們從不同時(shí)取非零值。所以我們可以安全地將互斥特征捆綁到一個(gè)特征中（我們稱之為exclusive feature bundle）。通過仔細(xì)地設(shè)計(jì)特征掃描算法，我們可以像獨(dú)立特征一樣給feat bundles建立feature histograms。這樣做之后，histogram building的算法復(fù)雜度從O(\#data \times \#feature)變?yōu)?span id="u0z1t8os" class="math-inline">O(\#data \times \#bundle), \#bundle << \#feature。這樣，我們就可以在不降低acc的情況下顯著地提高GBDT的訓(xùn)練速度。
