簡介
最近微軟DMTK團隊在 github上開源了性能超越其他 boosting decision tree工具 ! LIGHTGBM,三天之內star了1000+次,fork了200+次。知乎上有近幹人關注如何看待微軟開源的 Lightgbm? 問題,被評價為速度驚人」,「非常有啟發」,「支持分布式",「代碼清晰易慬",「佔用內存小"等。
lightgbm主要涉及分類、回歸、排序等。屬於監督學習算法。
通過調整模型參數w使得損失函數最小化,但一昧的最小化模型輸出和數據標度的差異,可能會使得模型過擬合,所以通暢加一些正則項來控制模型,比如下圖中的L1正則,從而將有監督的學習目標變成了損失函數和正則項的加和。
Boosting簡介
LightGBM屬於Boosting的一種。Boosting就是指用一系列的模型線性組合來完成模型任務。在Boosting學習中,逐步的確定每一個模型之間,每一個子模型疊加到複合模型當中來,在這個過程中保證損失函數隨著子模型的增加而逐漸減少。
Boosting有兩種,AdaBoost和Gradient Boost。
總的來說,Boosting方法都是在訓練好子模型後,統計現有的複合模型的擬合情況,從而調整接下來學習任務的一些setting,使得接下來,找到的子模型加入複合模型之後,符合降低整體loss的目標。
AdaBoost和Gradient Boosting特點
AdaBoost
根據當前的loss來改變樣本權重,比如這個樣本在學習中誤差比較大,則獲得一個大的權重,反之獲得更小的權重,從而控制後續子模型的產生。
Gradient Boosting
直接修改樣本label,新的樣本的label將變成原來的label和已知形成的模型預測值之間的殘差。
從兩者來看,gradient boosting 更傾向於降低訓練誤差的角度去完成算法乘積。
完整的模型是由很多「base learner」的子模型組成,學習中是一個個增加子模型,並希望loss能夠不斷減小。如果把複合函數f(x)看成自變量,我們希望改變這個複合函數使得loss下降,那麼沿著loss相對於f的梯度方向是一個合理的選擇。簡單來說,如果我們新加入的子模型使得f沿著loss相對於f的梯度方向變了,那麼我們就得到了我們希望要的子模型。
在實際問題中,比如我們定義的loss是平方誤差,也就是L2loss,那麼梯度方向就是估計值與樣本值之間的殘差,如下圖。我們新加入的子模型,就應該朝著這個殘差來學習,也就是下圖顯示的:$$f_m(x)$$
GBDT
了解了gradient boosting,接下來GBDT就好理解了。
也就是當gradient boosting中,每一個base learner(基礎學習器?)都是一個decision tree(決策樹)時,我們就把它叫做GBDT。
GBDT可以完成分類、回歸,排序(ranking)任務等。
Decision Tree
就是把數據的feature value劃分成很多不重疊的區域,一般來說我們都是指的二叉樹,樹種的葉子節點需要做分割。所以會包含分割點信息,有哪個為feature,然後這個為feature,我們用什麼將數據分為左邊和右邊兩個部分,從而不斷把樹長的更深。
而在葉子節點,包含了最重要的分類信息,也是純度最大的地方,歸類到同一個葉子節點的數據會被歸類到一起,生成葉子節點的數值。會用在這個節點上所有樣本的均值來作為這個節點的輸出。
決策樹是如何學習的
decision tree學習過程可以分為兩種。一種,叫做leaf-wise learning,也就是說學習過程中,我們需要不斷的尋找分類後收益最大的葉子節點,然後對其進行進一步的分裂,從而生長成樹,這種方法能夠更加快速有效的尋找模型,但是整個生長的過程都是順序的不方便加速。
也因此提出了另一種方法,Level-wise learning
也就是說樹的生長是按層去長的,不需要每次去挑選生長的節點,只需要按順序去長,這樣在每一個level中各個節點的分類可以並行的完成,有天然的並行性,但是這樣會產生很多沒必要的分類,也許會造成更大的計算代價。
decision tree偽代碼
在每一個需要分類的點,我們去尋找最佳的分類位置,也就是根據當前節點的數據,找到當前節點最佳的分裂需要用的最佳的特徵值進行分裂。尋找這個最佳特徵值的過程在下圖中右框裡。
遍歷所有特徵值和可能的取值,假設在某一點把數據分成兩部分後帶來的損失變化,通過逐一比較找到能讓我們獲得最大收益的點,確定哪一個leaf要進行分裂。也就是圖中的$$p_m:最大收益點$$
$$f_m:是哪一維度特徵$$
$$v_m:是指的這個維度特徵gain最高的value,大於這個值的放在左邊,小於這個值的放在右邊。$$
FindBestsplit是計算代價最大的地方,GBDT就是不斷增加新的decision tree來擬合之前的殘差,每個樹的學習都包含了整個decision tree的流程。
現有GBDT工具介紹
其中XGBoost性能相比其他更具要更好點,特別是速度上的優勢,其次提供了很好的接口,方便使用。
從上圖可以看到xgboost的訓練時間和最後的結果都比較優秀。
XGBoost特點介紹
XGBoost是一種基於預排序的方法,它會將每一個unique的feature value做計算,好處是能夠找到特定的feature value來做為分割點,不好的地方就是這種方法的計算和存儲代價都非常大。並且這樣找到的特別精確的分割點可能存在過擬合,另外它生長每顆樹的方法是按層生長,即level-wise learning。按層生長會帶來不少的時間好處,每一層可以都對所有數據做操作,但是會有一些不必要的運算,比如一些節點不需要分裂計算。
LightGBM
與XGBoost類似,他也是一個gradient boosting的框架,設計初衷是並行與高效。
它具有訓練速度快,內存使用少,處理了類別特徵,大大加快了訓練速度,也有更好的模型精度。
下面表格給出了lgb和xgb之間更加細緻的性能對比,包括樹的生長,方式,分裂。
lgb採用的是生長方法是leaf-wise learning,減少了計算量,當然這樣的算下下也需要控制樹的深度和每個葉節點的最小的數據量,從而減少over fit。分裂點,xgb採取的是預排序的方法,而lgb採取的是histogram算法,即將特徵值分為很多小桶,直接在這些桶上尋找分類,這樣帶來了存儲代價和計算代價等方面的縮小,從而得到更好的性能。
另外,數據結構的變化也使得細節處理方面效率有所不同,比如對緩存的利用,lgb更加高效。從而使得它右很好的加速性能,特別是類別特徵處理,也使得lgb在特定的數據集上有非常大的提升。
下圖是數據集上的實驗對比。
左邊對比了應用上的準確率、內存使用情況。其中Higgas、Expo都是分類數據,Yahoo LTR 和 MSLTR 都是排序數據。可以看到lgb在這些數據集上的表現都更好。
右邊是計算速度的對比,可見lgb完成相同的數據集速度要幾倍於xgb。
LightGBM的細節技術講解
Histogram optimization(直方圖優化)
在XGB中,採用了預排序的方法,計算過程中按照feature value排序,逐個數據樣本來進行當前 feature value 樣本的分裂收益,這樣算法能夠精確找到最佳分裂值,帶式代價非常大,也不具有好的推廣性。
在LGB中,將這些連續的或者精確的每一個 feature value 劃分到一系列的離散值,也就是所說的桶裡面,下圖即拿浮點型的特徵來舉例。
一個區間的值,會被作為一個桶,比如 [0,0.1) 為第零個桶......,有了分桶的信息,建立起來基於分桶的直方圖的統計,之後的計算都會基於這些以分桶為精度單位的直方圖來做。
這樣一來,數據的表達更為簡化,減少了數據的使用,而且直方圖帶來了一定的正則化的效果,使得我們的模型不容易 over fitting 有著更好的推廣性。下面是做過直方圖後尋找最佳分裂點的求解函數的偽代碼。
可以看到,這是按照 bin(桶) 來索引 直方圖的,所以不需要按照每個 feature 來排序,也不需要一一對比所有不同 feature 值,大大的減少了運算量。
存儲優化
當我們用 feature bin 來描述數據時,memory 的變化如下圖。
首先,我們不需要像XGB那樣,存儲預排序對應的data的序列,也就是灰色方格,因此這個代價就變成了0,另外用 bin 表示 feature 可以有效減少佔用的存儲空間(一般bin不會設置太多)。
帶有深度限制的 Leaf-wise learning
lgb採用了帶有深度限制的 leaf-wise 學習來提高模型精度。
leaf-wise 相對於 level-wise ,更加的高效,還可以降低更多的訓練誤差,得到更好的精度,但單純使用它來進行生長,可能會長出比較深的樹,在小數據集上可能造成過擬合,因此在 leaf-wise 上,多加了深度的限制。
直方圖做差
lgb還使用了直方圖做差的優化,可以觀察到一個葉子節點上的直方圖可以由它的 父節點直方圖減去兄弟節點的直方圖來得到,根據這點,我們可以構造出來計算數據量比較小的葉子節點直方圖,然後用直方圖做差得到中間較大的葉子節點的直方圖,達到加速的效果。
Increase cache hit chance(提高緩存命中率吧)
pre-sorted算法中有兩個操作頻繁的地方,會造成 cache missed 。對梯度的訪問,在計算gain時需要用到梯度,不同的 feature 訪問梯度的舒徐是不一樣的並且是隨機的。對於索引表的訪問,pre-sorted有個行號和葉節點號的索引表,可以防止數據切分的時候對所有的 feature 進行切分。訪問梯度也一樣,所有的 feature 都需要通過訪問索引表,所以都是隨機訪問,會帶來非常大的系統性能的下降。
而 lightgbm 使用的直方圖算法則是天然的 cache friendly。首先,對梯度的訪問,因為不需要對 feature 進行排序,同時所有的 feature 都用同樣的方式來訪問,所以只需要對梯度訪問的順序進行一個排序,所有的 feature 都能連續的訪問梯度。並且直方圖算法不需要數據 ID 到葉節點號的索引表,所以沒有佔用 cache 的問題,cache * 對速度的影響是很大的,尤其是數據量很大的時候,相比於隨機訪問,順序訪問速度可以快四倍以上。
支持直接輸入類別特徵
傳統對的機器學習算法不能直接輸入類別特徵,需要先離散化,這樣的空間或者時間效率都不高。lgb通過更改決策樹算法的決策規則,直接原生支持類別特徵,不許額外離散化。速度快了8倍以上。
並行學習支持
lgb原生支持多種並行的算法,適用不同的數據場景,當 feature 並行時,通常適用於小數據但是 feature 比較多的場景。data 並行適用數據量比較大但是 feature 量比較少的情景。Voting 則適用數據量大且 feature 也很多的場景。
Feature/Attribute Parallelization
通過垂直切分數據在不同機器上都用所有的數據樣本點,但是有不同的特徵,不同機器上尋找不同特徵上的最優分割點進行全局的同步,得到全局的最優分割點。
Data Parallelization
data並行通過水平切分數據,讓不同機器擁有不同的數據,並行的時候讓不同的機器首先用穩定的數據構造好直方圖,然後進行一個全局的直方圖合併,在合併好的全局直方圖上尋找最佳分割點。
基於投票的並行
是對於數據並行的優化,數據並行的瓶頸主要在於合併直方圖的時候,空間代價比較大,根據這一點,基於投票的方式,只和並部分特徵值的直方圖,達到了降低通信量的目的。
首先通過本地的數據找到本地的 top features ,然後利用投票篩選出可能是全局最優點的特徵,合併直方圖時只和並這些被選出來的特徵,由此減低了通信量。
以下是幾種並行算法的實驗對比
可以看到 voting 並行可以比其他幾種算法更快的達到收斂點,並且精度幾乎與原來一致。
以下是另外數據集的結果。
其他方面的特點
使用經驗
因為lgb採用的是 leaf-wise learning 來生成樹,所以樹的深度與葉子數有關。以下是參考。
隨機減少特徵來加速,實踐中不會損失太多的精度。
直接輸入類別特徵,不需要啞變量,更快。
如果一個文件訓練多次,可以保存成二進位的文件,這樣訓練起來會更快。
比較小的學習率,更加多的迭代次數,一般會提高正確率。過擬合情況下,增加葉子節點數也能提高精度。或者用交叉驗證的方式,對比一些參數,找到更好的參數。訓練數據越多,訓練精度也有提升。
防止過擬合方法,第三、五點用的最多。
以下為相應參考資料。
參考文章及視頻