編者按:說(shuō)到Kaggle神器,不少人會(huì)想到XGBoost。一周前,我們?cè)凇皬腒aggle歷史數(shù)據(jù)看機(jī)器學(xué)習(xí)競(jìng)賽趨勢(shì)”介紹過(guò)它的“霸主地位”:自提出后,這種算法在機(jī)器學(xué)習(xí)競(jìng)賽中被迅速普及,并被多數(shù)奪冠模型視為訓(xùn)練速度、最終性能提升的利器。那么,你知道XGBoost背后的數(shù)學(xué)原理是什么嗎?
好奇的李雷和韓梅梅
李雷和韓梅梅是形影不離的好朋友,一天,他們一起去山里摘蘋果。按照計(jì)劃,他們打算去摘山谷底部的那棵大蘋果樹(shù)。雖然韓梅梅聰明而富有冒險(xiǎn)精神,而李雷有些謹(jǐn)慎和遲鈍,但他們中會(huì)爬樹(shù)的只有李雷。那么他們的路徑是什么呢?
如上圖所示,李雷和韓梅梅所在的位置是a點(diǎn),他們的目標(biāo)蘋果樹(shù)位于g點(diǎn)。山里環(huán)境復(fù)雜,要怎么做才能確定自己到了山谷底部呢?他們有兩種方法。
1.由韓梅梅計(jì)算“a”點(diǎn)的斜率,如果斜率為正,則繼續(xù)朝這個(gè)方向前進(jìn);如果為負(fù),朝反方向前進(jìn)。
斜率給出了前進(jìn)的方向,但沒(méi)有說(shuō)明他們需要朝這個(gè)方向移動(dòng)多少。為此,韓梅梅決定走幾步臺(tái)階,算一下斜率,確保自己不會(huì)到達(dá)錯(cuò)誤位置,最終錯(cuò)過(guò)大蘋果樹(shù)。但是這種方法有風(fēng)險(xiǎn),控制臺(tái)階多少的是學(xué)習(xí)率,這是個(gè)需要人為把控的值:如果學(xué)習(xí)率過(guò)大,李雷和韓梅梅很可能會(huì)在g點(diǎn)兩側(cè)來(lái)回奔走;如果學(xué)習(xí)率過(guò)小,可能天黑了他們都未必摘得到蘋果。
聽(tīng)到可能會(huì)走錯(cuò)路,李雷不樂(lè)意了,他不想繞遠(yuǎn)路,也不愿意錯(cuò)過(guò)回家吃飯的時(shí)間??吹胶糜堰@么為難,韓梅梅提出了第二種方法。
2.在第一種方法的基礎(chǔ)上,每走過(guò)特定數(shù)量的臺(tái)階,都由韓梅梅去計(jì)算每一個(gè)臺(tái)階的損失函數(shù)值,并從中找出局部最小值,以免錯(cuò)過(guò)全局最小值。每次韓梅梅找到局部最小值,她就發(fā)個(gè)信號(hào),這樣李雷就永遠(yuǎn)不會(huì)走錯(cuò)路了。但這種方法對(duì)女孩子不公平,可憐的韓梅梅需要探索她附近的所有點(diǎn)并計(jì)算所有這些點(diǎn)的函數(shù)值。
XGBoost的優(yōu)點(diǎn)在于它能同時(shí)解決以上兩種方案的缺陷。
梯度提升(Gradient Boosting)
很多梯度提升實(shí)現(xiàn)都會(huì)采用方法1來(lái)計(jì)算目標(biāo)函數(shù)的最小值。在每次迭代中,我們利用損失函數(shù)的梯度訓(xùn)練基學(xué)習(xí)器,然后用預(yù)測(cè)結(jié)果乘上一個(gè)常數(shù),將其與前一次迭代的值相加,更新模型。
它背后的思路就是在損失函數(shù)上執(zhí)行梯度下降,然后用基學(xué)習(xí)器對(duì)其進(jìn)行擬合。當(dāng)梯度為負(fù)時(shí),我們稱它為偽殘差,因?yàn)樗鼈円廊荒荛g接幫助我們最小化目標(biāo)函數(shù)。
XGBoost
XGBoost是陳天奇在華盛頓大學(xué)求學(xué)期間提出的成果。它是一個(gè)整體加法模型,由幾個(gè)基學(xué)習(xí)器共同構(gòu)成。
那么,我們?cè)撊绾卧诿看蔚羞x擇一個(gè)函數(shù)?這里可以用一種最小化整體損失的方法。
在上述梯度提升算法中,我們通過(guò)將基學(xué)習(xí)器擬合到相對(duì)于先前迭代值的損失函數(shù)的負(fù)梯度,在每次迭代時(shí)獲得ft(xi)。而在XGBoost中,我們只探索幾個(gè)基學(xué)習(xí)器或函數(shù),選擇其中一個(gè)計(jì)算最小值,也就是韓梅梅的方法2。
如前所述,這種方法有兩個(gè)問(wèn)題:
探索不同的基學(xué)習(xí)器;
計(jì)算所有基學(xué)習(xí)器的損失函數(shù)值。
XGBoost在計(jì)算基學(xué)習(xí)器ft(xi)最小值的,使用的方法是泰勒級(jí)數(shù)逼近。比起計(jì)算精確值,計(jì)算近似值可以大大減輕韓梅梅的工作量。
雖然上面只展開(kāi)到二階導(dǎo)數(shù),但這種近似程度就足夠了。對(duì)于任意ft(xi),第一項(xiàng)C都是常數(shù)。gi是前一次迭代中損失的一階導(dǎo)數(shù),hi是其二階導(dǎo)數(shù)。韓梅梅可以在探索其他基學(xué)習(xí)器前直接計(jì)算gi和hi,這就成了一個(gè)簡(jiǎn)單的乘法問(wèn)題,計(jì)算負(fù)擔(dān)大大減輕了,不是嗎?
解決了損失函數(shù)值的問(wèn)題,我們還要探索不同的基學(xué)習(xí)器。
假設(shè)韓梅梅更新了一個(gè)具有K個(gè)葉子節(jié)點(diǎn)的基學(xué)習(xí)器ft。設(shè)Ij是屬于節(jié)點(diǎn)j的實(shí)例集合,wj是該節(jié)點(diǎn)的預(yù)測(cè)。因此,對(duì)于Ij中的實(shí)例i,我們有ft(xi)=wj。所以我們?cè)谏鲜街杏么敕ǜ铝薒(t)的表達(dá)式。更新后,我們就能針對(duì)每個(gè)葉子節(jié)點(diǎn)的權(quán)重采用損失函數(shù)的導(dǎo)數(shù),以獲得最優(yōu)權(quán)重。
以上就是對(duì)于具有K個(gè)葉子節(jié)點(diǎn)的基學(xué)習(xí)器的最佳損失。考慮到這樣的節(jié)點(diǎn)會(huì)有上百個(gè),一個(gè)個(gè)探索它們是不現(xiàn)實(shí)的。
所以讓我們來(lái)看韓梅梅的情況。她現(xiàn)在已經(jīng)知道如何使用泰勒展開(kāi)來(lái)降低損失計(jì)算量,也知道了什么是葉子節(jié)點(diǎn)中的最佳權(quán)重。唯一值得關(guān)注的是如何探索所有不同的樹(shù)結(jié)構(gòu)。
XGBoost不會(huì)探索所有可能的樹(shù)結(jié)構(gòu),它只是貪婪地構(gòu)建一棵樹(shù),選擇導(dǎo)致最大損失的方法,減少分叉。在上圖中,樹(shù)從節(jié)點(diǎn)I開(kāi)始,根據(jù)標(biāo)準(zhǔn),節(jié)點(diǎn)分為左右分叉。所以我們的實(shí)例一部分被放進(jìn)了左側(cè)的葉子節(jié)點(diǎn),剩下的則去了右側(cè)的葉子節(jié)點(diǎn)?,F(xiàn)在,我們就可以計(jì)算損失值并選擇導(dǎo)致?lián)p失減少最大的分叉。
解決了上述問(wèn)題后,現(xiàn)在韓梅梅就只剩下一個(gè)問(wèn)題:如何選擇分叉標(biāo)準(zhǔn)?XGBoost使用不同的技巧來(lái)提出不同的分割點(diǎn),比如直方圖。對(duì)于這部分,建議去看論文,本文不再作解釋。
XGBoost要點(diǎn)
雖然梯度提升遵循負(fù)梯度來(lái)優(yōu)化損失函數(shù),但XGBoost計(jì)算每個(gè)基學(xué)習(xí)器損失函數(shù)值用的是泰勒展開(kāi)。
XGBoost不會(huì)探索所有可能的樹(shù)結(jié)構(gòu),而是貪婪地構(gòu)建一棵樹(shù)。
XGBoost的正則項(xiàng)會(huì)懲罰具有多個(gè)葉子節(jié)點(diǎn)的樹(shù)結(jié)構(gòu)。
關(guān)于選擇分叉標(biāo)準(zhǔn),強(qiáng)烈建議閱讀論文:arxiv.org/pdf/1603.02754.pdf
-
梯度
+關(guān)注
關(guān)注
0文章
30瀏覽量
10300 -
機(jī)器學(xué)習(xí)
+關(guān)注
關(guān)注
66文章
8324瀏覽量
132192
原文標(biāo)題:計(jì)算:XGBoost背后的數(shù)學(xué)之美
文章出處:【微信號(hào):jqr_AI,微信公眾號(hào):論智】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論