【機(jī)器學(xué)習(xí)基礎(chǔ)】結(jié)合論文理解XGBoost推導(dǎo)過(guò)程
前言
XGBoost是一個(gè)可擴(kuò)展的提升樹(shù)模型，論文“XGBoost: A Scalable Tree Boosting System”發(fā)表在2016年的KDD會(huì)議上。文章包括了XGBoost的原理以及對(duì)其的優(yōu)化。本文主要分享XGBoost的推導(dǎo)過(guò)程，包含論文內(nèi)容2.1-2.2部分，這里假設(shè)你已掌握決策樹(shù)、GBDT的相關(guān)知識(shí)。
本文約2.7k字，預(yù)計(jì)閱讀10分鐘。
XGBoost原理
XGBoost最關(guān)鍵的思想就是采用二階導(dǎo)來(lái)近似取代一般損失函數(shù)。整個(gè)推導(dǎo)過(guò)程分為以下幾個(gè)步驟（問(wèn)題）：
目標(biāo)函數(shù)的構(gòu)造； 目標(biāo)函數(shù)難以優(yōu)化，如何近似？ 將樹(shù)的結(jié)構(gòu)（參數(shù)化，因?yàn)槟Ｐ偷膶W(xué)習(xí)參數(shù)在樹(shù)中）融入到目標(biāo)函數(shù)； 如何構(gòu)造最優(yōu)（局部）二叉樹(shù)？采用貪心算法；
目標(biāo)函數(shù)定義
首先我們假設(shè)一個(gè)數(shù)據(jù)集中包含個(gè)樣本以及每個(gè)樣本有個(gè)特征，因此數(shù)據(jù)集可以定義為：
對(duì)于提升樹(shù)模型來(lái)說(shuō)，我們假設(shè)共有個(gè)疊加函數(shù)（additive functions，即決策樹(shù)），那么整個(gè)模型可以表示為：
其中：
：表示模型對(duì)樣本的預(yù)測(cè)值； ：模型函數(shù)； ：表示單個(gè)樣本； ：表示第決策樹(shù)； ；表示決策樹(shù)的空間集合；
我們要學(xué)習(xí)上述集成模型函數(shù)（也稱加法模型），則需要最小化正則化后的損失函數(shù)（即目標(biāo)函數(shù)，正則化是對(duì)復(fù)雜決策樹(shù)的懲罰）：
表示第個(gè)決策樹(shù)的復(fù)雜度，這里我們先不去參數(shù)化和。
梯度提升算法
問(wèn)題1： 對(duì)于上述的目標(biāo)函數(shù)，其實(shí)很難在歐氏空間中使用傳統(tǒng)的優(yōu)化方法。
因此，提升樹(shù)模型采用前向分步的學(xué)習(xí)方法。假設(shè)表示在第次迭代時(shí)對(duì)第個(gè)樣本的預(yù)測(cè)，那么我們可以將目標(biāo)函數(shù)轉(zhuǎn)化為以下形式（這里假設(shè)你已掌握提升樹(shù)算法的知識(shí)）：
其中，表示第次迭代時(shí)，集成模型對(duì)樣本的預(yù)測(cè)，表示第個(gè)決策樹(shù)。為常數(shù)，所以我們只需要學(xué)習(xí)，當(dāng)然對(duì)于決策樹(shù)復(fù)雜度的刻畫(huà)，前的決策樹(shù)的復(fù)雜度此時(shí)為常數(shù)，所以目標(biāo)函數(shù)并沒(méi)有包括。
【注】：為一個(gè)常數(shù)，我們當(dāng)然盡可能希望其與真實(shí)值更近，為兩者之間的一個(gè)「殘差」，希望盡可能的趨于0，所以這就是為什么后面我們可以將看成。
問(wèn)題2： 此時(shí)，目標(biāo)函數(shù)變得更為簡(jiǎn)單，但是仍然無(wú)法描述損失函數(shù)，因?yàn)椴⒉恢榔漕愋?，一般的?fù)雜函數(shù)也很難刻畫(huà)。
所以，我們需要一個(gè)近似函數(shù)來(lái)表示損失函數(shù)。論文中提到，采用在一般設(shè)定下，二階近似法（Second-order approximation）可用于快速優(yōu)化目標(biāo)。論文這里引用了一篇參考文獻(xiàn)，其實(shí)就是通過(guò)泰勒公式用函數(shù)在某點(diǎn)的信息描述其附近取值。
首先可以了解微分（微分是函數(shù)在一點(diǎn)附近的最佳線性近似）來(lái)近似表示一般函數(shù)【從幾何的角度講，就是在某點(diǎn)的切線來(lái)近似于原函數(shù)附近的曲線，二階近似則是采用拋物線】：
為高階無(wú)窮小，所以：
所以附近的值可以用上述線性近似來(lái)表示，「而GBDT就是采用線性近似（微分）來(lái)描述一般的損失函數(shù)?！?/strong> 對(duì)于XGBoost來(lái)說(shuō)，采用二階近似（二階泰勒公式）來(lái)描述損失函數(shù)：
那么如何應(yīng)用在我們定義的損失函數(shù)？其實(shí)可以對(duì)應(yīng)于，對(duì)應(yīng)于，所以可以得到近似的損失函數(shù)：
我們令，因此近似目標(biāo)函數(shù)化簡(jiǎn)為
并且為一個(gè)常數(shù)，所以可以去掉：
【注】：一階導(dǎo)和二階導(dǎo)是已知的，因此需要學(xué)習(xí)的參數(shù)包含在中。
問(wèn)題3：如何參數(shù)化【將需要學(xué)習(xí)的參數(shù)在目標(biāo)函數(shù)中顯示】表示和決策樹(shù)的復(fù)雜度？
對(duì)于，文章給出定義：
其中表示表示單個(gè)樹(shù)的結(jié)構(gòu)，即樣本對(duì)應(yīng)的葉子結(jié)點(diǎn)的索引。表示葉子結(jié)點(diǎn)的值?！灸硞€(gè)樣本的預(yù)測(cè)值對(duì)應(yīng)于某個(gè)葉子結(jié)點(diǎn)的值，這樣就能描述清楚決策樹(shù)上對(duì)應(yīng)每個(gè)樣本的預(yù)測(cè)值】。但是下標(biāo)依舊帶有參數(shù)，所以最終作者用：
表示「決策樹(shù)中分配到第個(gè)葉子結(jié)點(diǎn)中的樣本集合」，這樣，所有的葉子結(jié)點(diǎn)集合就能描述整個(gè)決策樹(shù)。
而決策樹(shù)的復(fù)雜度與葉子結(jié)點(diǎn)的數(shù)量和葉子結(jié)點(diǎn)的值（學(xué)習(xí)參數(shù)）相關(guān)，所以一般表示為：
所以，我們將目標(biāo)函數(shù)表示為：
可以看到，這其實(shí)是關(guān)于的一個(gè)二次函數(shù)，我們可以使用中學(xué)的知識(shí)，最優(yōu)解為，即：
計(jì)算對(duì)應(yīng)的目標(biāo)函數(shù)為：
以上便是XGBoost的梯度提升算法的推導(dǎo)過(guò)程。
尋找分割點(diǎn)（決策樹(shù)構(gòu)造）
上述近似目標(biāo)函數(shù)可以作為一個(gè)決策樹(shù)的評(píng)價(jià)分?jǐn)?shù)，但是我們之前對(duì)于最小化目標(biāo)函數(shù)來(lái)優(yōu)化決策樹(shù)的值是「假定決策樹(shù)的結(jié)構(gòu)是已知的」。簡(jiǎn)單來(lái)說(shuō)，就是目前我們可以做到給定一個(gè)決策樹(shù)的結(jié)構(gòu)，我們可以將它的葉子結(jié)點(diǎn)的值進(jìn)行優(yōu)化，并且可以達(dá)到一個(gè)評(píng)價(jià)它性能的分?jǐn)?shù)。
問(wèn)題4：如何構(gòu)造決策樹(shù)？
最簡(jiǎn)單的方法是將所有決策樹(shù)的結(jié)構(gòu)全部羅列出來(lái)，然后優(yōu)化，計(jì)算他們的目標(biāo)函數(shù)值，進(jìn)行比較，選擇最小目標(biāo)函數(shù)值的決策樹(shù)。但是如果決策樹(shù)深度過(guò)深，那么所有決策樹(shù)的數(shù)量太多，很難完成上述步驟。
所以，文章采用了一種貪心算法（greedy algorithm）的策略，從單個(gè)葉子結(jié)點(diǎn)開(kāi)始，迭代的增加分治進(jìn)行比較。
假設(shè)，當(dāng)前有樣本，目前決策樹(shù)為：
其目標(biāo)函數(shù)值可以表示為：
我們對(duì)右下葉子結(jié)點(diǎn)增加新的分支：
此時(shí)目標(biāo)函數(shù)值為：
我們將兩者相減，得到：
如果，則說(shuō)明可以進(jìn)行分支，所以我們可以推導(dǎo)出，
其中與指代分割葉子結(jié)點(diǎn)后的新的左右葉子結(jié)點(diǎn)。通過(guò)以上分割方法，就可以分步的找到基于貪心的局部最優(yōu)決策樹(shù)。
總結(jié)
上述是我結(jié)合論文的2.1和2.2部分內(nèi)容進(jìn)行總結(jié)、解釋與擴(kuò)展，并不包括后續(xù)的各種優(yōu)化方法。
往期精彩回顧
本站qq群704220115，加入微信群請(qǐng)掃碼：