超全!LightGBM算法框架前世今生!

2020-12-03 黃杰ed

簡介

最近微軟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 來生成樹,所以樹的深度與葉子數有關。以下是參考。

隨機減少特徵來加速,實踐中不會損失太多的精度。

直接輸入類別特徵,不需要啞變量,更快。

如果一個文件訓練多次,可以保存成二進位的文件,這樣訓練起來會更快。

比較小的學習率,更加多的迭代次數,一般會提高正確率。過擬合情況下,增加葉子節點數也能提高精度。或者用交叉驗證的方式,對比一些參數,找到更好的參數。訓練數據越多,訓練精度也有提升。

防止過擬合方法,第三、五點用的最多。

以下為相應參考資料。

參考文章及視頻

相關焦點

  • 30分鐘搞定數據競賽刷分奪冠神器LightGBM
    1,Histogram算法:直方圖算法。2,GOSS算法:基於梯度的單邊採樣算法。3,EFB算法:互斥特徵捆綁算法。那麼,Histogram算法,GOSS算法,和EFB算法分別從什麼角度對XGBoost進行性能優化呢?我們先概括性地從全局進行分析,然後再逐個加以介紹。
  • 劍指LightGBM和XGboost!斯坦福發表NGBoost算法
    Stanford ML Group 最近在他們的論文中發表了一個新算法,其實現被稱為 NGBoost。該算法利用自然梯度將不確定性估計引入到梯度增強中。本文試圖了解這個新算法,並與其他流行的 boosting 算法 LightGBM 和 XGboost 進行比較,以了解它在實踐中是如何工作的。
  • 了解算法的前世今生
    一、中國算法的前世中國古代數學是以創造算法特別是各種解方程的算法為主線。從線性方程組到高次多項式方程,乃至不定方程,中國古代數學家創造了一系列先進的算法(中國數學家稱之為「術」),他們用這些算法去求解相應類型的代數方程,從而解決導致這些方程的各種各樣的科學和實際問題。
  • 大戰三回合:XGBoost、LightGBM和Catboost一決高低
    Battle 中,根據訓練和預測的時間、預測得分和可解釋性等評測指標,讓三個算法一決高下!一言不合就 BattleGBDT 是機器學習中的一個非常流行並且有效的算法模型,2014 年陳天奇博士提出的 XGBoost 算法就是 GBDT 一個重要實現。
  • 案例實踐丨最優化算法的前世今生
    近期,大巖資本黃鉑博士結合生活實踐中的案例,深入淺出闡釋了最優化算法的前世今生所以通常在很多的優化問題中,這兩種任務可以組合起來出現在同一個問題框架下,這就是對於目標函數的定義。每一步都做到了最優化,但很遺憾的是,對於整個算法而言,它並不是非常好的算法。因為它的收斂速度是線性收斂,線性收斂對於最優化算法而言是一種比較慢的算法,但也是凸優化裡最自然的一個算法,最早被應用。第二個算法,共軛梯度法。與最速下降法相比較(看下圖),綠色的線是最速下降法的迭代,從最外層到中心點可能需要五步迭代,但是共軛梯度法可能只需兩步迭代(紅色線)。
  • 廖閱鵬:前世今生催眠曲,帶你夢回前世,總結今生!
    最近在最右上,看到了一則消息,許多人聽了廖閱鵬的前世今生催眠曲,都看到了自己的前世,我覺得很神奇,便趁著月黑風高之夜,孤身一人躲在被窩裡,悄悄的打開了喜馬拉雅收音機,點開了前世今生催眠曲,帶上耳機,準備一場穿越之旅。
  • 你相信前世今生嗎?
    你相信前世今生嗎?我不知道自己是不是真的相信,不過我想還是相信的成份多一些吧!那個網絡上流傳了很久的《前世今生催眠曲》我是最近才看到的,感覺很神奇,好多網友都說自己看到了前世!我也很想看一看自己的前世,記得在網易裡測過自己的前世,是一個嬪妃,也測過說是皇后,但我都當做是娛樂,只是這一次,我在心裡潛意識的希望我可以了解自己的前世。進行催眠最需要的是心靜,從昨天開始到今天,我試了很多次都沒能成功,因為我無法靜下心來。當聆聽著大師的指導和美妙的音樂時,我的頭腦中似乎有影像,但現實卻清晰地佔據著全部的心裡。漸漸地,模糊的影像也便消失了。
  • 土星宮位看出你的前世和今生
    今生的你不願意再重蹈覆轍,因而痛改前非,抱持著「執著」的態度。即使遭遇到困難和挫折也絕不輕言放棄,頗具使命感。今生的你個性上一反前世,耐心相當好。第二類型者,土星二宮前世的你,豐衣足食,生活無慮,偶爾奢侈一時,悠遊度日,倒不成問題。但是,長久下來,縱使有金山銀山,也有用盡的一日。老年之後經濟狀況就很不好了。縱便想重新修正,奈何時光不再。這一份感慨延續到今生。
  • 催眠:貪得無厭的前世,苦苦掙扎的今生
    ~01~今生她是一個18歲的小女孩,正面臨高考,發現自己內心有很多的悲苦擾亂她的心神無法安心讀書。所以她就突發奇想,想去看看她自己的前世,她認為或許看過了自己的前世,可以對今生的很多事情釋懷。因為是遠程催眠,為避免對她有什麼影響,所以就把她帶離前世。而前世她的離世,是在前線作戰時被敵軍發現後殺死的。
  • 科學看待前世今生/釋聖靜
    科學看待前世今生    作者:釋聖靜      從《物理》,以及《生物》《化學》,等綜合學科所新形成的《人類(磁場,所產生的同頻或者是逆向等物理作用,以及自然化學與生命化學所產生的化學作用,或異體同化,或同體異變,化分……      從潛意識和無意識,乃至於總是習慣性的想法,情緒,夢景,思想品德,等所形成了俗話說的,前世今生,來世……      其實前世,今生,來世,科學客觀而不失精確的定義:前世從當下此時的一念,往前無止的時間裡
  • 凡人修仙傳仙界篇——南宮婉的前世今生
    南宮婉身世之謎在凡人修仙傳仙界篇一千三百章《輪迴之爭》中,輪迴殿主意圖利用六道輪迴盤迴復南宮婉前世記憶,那麼我們猜想一下, 南宮婉的前世今生。首先我們要說一下南宮婉今生的身份,是下界失落界面「靈界」附屬的人界飛升修士,主要功夫是輪迴素女功,是韓立的道侶。韓立飛升之後南宮婉留在靈界,而在九元觀遇到南宮婉以如霜的身份現身,而且好像完全不認識韓立一般,但是這個人確實是南宮婉,而現在她正在恢復前世記憶,那麼問題來了。問題一:甘如霜的正式身份是什麼?
  • 「催眠音樂」——能讓人「感觸」前世今生?
    專業人士稱,所謂看到前世的說法玄乎其玄,不足為信   想回到過去,看看你的前世嗎?這樣一個近乎荒唐的問題近來卻在網絡上「熱」起來——它與一段名為「前世今生」的音頻有關。  近日,記者在百度貼吧的「洛陽五中」貼吧中,看到這樣一個名為「來探索一下自己的前世今生」的帖子。
  • 盤點動漫裡的前世戀人們:前世相戀,今生也要相愛
    人們常說前世的戀人,今生的緣分,還有就是前世500次的回眸,才換來今生的擦肩而過。這是人們對愛情的無限美好遐想,雖然沒有什麼科學根據,但是有些東西是科學也無法解釋的事,同時這會給人一絲希望和慰藉。如果世界上真的存在前世的戀人,說不定今生還可以互相找到對方,但是這個肯定是機率特別小的一件事情,因為很多人根本記不住前生發生了些什麼。今天我們來說說動漫裡的前世戀人。神無月的巫女《神無月的巫女》作為一部2004年上映的老番,相信很多小夥伴都沒看過,但就其畫風、人設、劇情、內涵,即使放到現在也毫不遜色於一般番劇。
  • 解讀狗牙 顯卡帝揭秘AA抗鋸齒前世今生
    顯卡帝揭秘AA抗鋸齒的前世今生顯卡帝揭秘AA抗鋸齒的前世今生    AA(Anti-Aliasing)抗鋸齒想必不少玩家在遊戲那麼今天顯卡帝就來為您詳細解讀AA抗鋸齒的前世今生,讓你開開心心對AA抗鋸齒弄個明白。
  • 催眠治療與前世今生
    那麼,說回到我現在的工作上,我是一個催眠治療師,也是一個系統整合療愈師,自然我是相信輪迴的,所以從世間的層面來說,前世今生,在我看來無疑是存在且真實不虛的。同時,我更相信的是「空性」,也就是出世間的角度來說,一切有為法,如夢幻泡影,如露亦如電,應作如是觀。 為什麼這樣說呢?
  • 奧比島七夕絕版搜集令 前世今生全解攻略
    導 讀 奧比島七夕絕版搜集令,前世今生全解攻略!不少玩家都在問奧比島七夕怎麼收集三世搜集令,集齊套裝。
  • 說說歷史上雮塵珠的前世今生
    說說歷史上雮塵珠的前世今生時間:2020-04-12 15:24   來源:今日頭條   責任編輯:毛青青 川北在線核心提示:原標題:說說歷史上雮塵珠的前世今生 最近熱播的電視劇鬼吹燈之怒睛湘西中頻繁出現一個物件兒-----雮塵珠. 今兒我們就來講講雮塵珠 的前世今生! 關於這雮塵珠的由來有兩種說法.
  • 催眠:前世今生—我與女兒的約定
    你相信——「前世今生」嗎?一個聽上去無比玄妙而又浪漫的詞,它究竟是不是真的存在?致力於此的人至今仍在不斷探究。但是在心理諮詢界,利用前世回溯治療有效的案例數不勝數,所以不論真實與否,單從療愈效果上來說,前世回溯治療被證實從根源上是有效的。
  • 前世今生來世輪迴的幾種可能
    今生只記得小時候玩過的玩具、被父母打、被鄰居的雞公跟著啄……,我們卻無法記得前世的任何事。所以,來分析一下,三生輪迴的幾種可能:1、如果人掛掉之後,會進入另外一個來世的輪迴世界,過奈何橋,喝孟婆湯,這一定是每個鬼都要強制喝的,不容選擇,這樣才符合今生記不得前世的事實。
  • 搞笑漫畫:催眠師「終極催眠術」看女孩前世今生!女孩前世居然…
    搞笑漫畫:催眠師「終極催眠術」看女孩前世今生!女孩前世居然…催眠可以說是一種很神奇的魔術,他和大部分的魔術一樣,都是給人一種心理暗示,而催眠是讓人進入到一種潛意識的睡眠當中,而對於這個男子來說,他就是一名傳說中的催眠師,而他也在為這個女孩子進行催眠。