你知道XGBoost背后的數(shù)學(xué)原理是什么嗎？

編者按：說(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