xgboost目標(biāo)函數(shù)推導(dǎo)

一說明

xgboost是boosting算法的其中一種哀澈，該算法思想就是不斷地添加樹滓窍，不斷地進(jìn)行特征分裂來生長一棵樹，每次添加一個(gè)樹了赌，其實(shí)是學(xué)習(xí)一個(gè)新函數(shù)墨榄，去擬合上次預(yù)測的殘差。具體的目標(biāo)函數(shù)如下：

$Obj{(t)} = \sum_{i=1}^nl(y_i, \hat{y_i}^{(t-1)} + f_t(x_i)) + Ω(f_t) + constant\tag {1}$

? 主要就是找到 $f_t$ 來優(yōu)化這一目標(biāo)函數(shù)勿她，通過一個(gè)簡單的例子來形象的理解該目標(biāo)函數(shù)袄秩。例如是小明真實(shí)有100個(gè)糖果，現(xiàn)在建立一個(gè)決策系統(tǒng)來預(yù)測小明有多少個(gè)糖逢并。首先建立一棵樹之剧，記為樹1，它的預(yù)測結(jié)果是90個(gè)砍聊，這時(shí)得到一個(gè)殘差背稼，這個(gè)殘差值就是100-90=10，此時(shí)和真實(shí)值差別是10玻蝌。為了提高精度蟹肘，可以在該決策系統(tǒng)中再添加一棵樹词疼，記為樹2。樹2就是為了彌補(bǔ)上一棵樹存在的殘差帘腹，假設(shè)它的預(yù)測結(jié)果是5贰盗，此時(shí)總體的殘差值是10-5=5，即和真實(shí)值相差為5阳欲。符號(hào)化表示：之前的結(jié)果10表示為輸出結(jié)果為 $\hat{y_1}$ ,即上一時(shí)刻的殘差值舵盈，樹2的值為 $f_2$ ,此時(shí)得到的值。接著可以再建立第三課樹胸完，記為樹3书释。假設(shè)它的預(yù)測值為3，此時(shí)總體的殘差值是5-3=2赊窥，即和真實(shí)值相差為2爆惧。符號(hào)化表示：上一時(shí)刻輸出結(jié)果5為 $\hat{y_2}$ ,即上一時(shí)刻的殘差值，樹3為 $f_3$ ,此時(shí)得到的值锨能。xgboost的目標(biāo)就是通過找到 $f_t$ 來優(yōu)化這一目標(biāo)函數(shù)扯再，使得最終結(jié)果足夠小。下面對(duì)該函數(shù)進(jìn)行推導(dǎo)化簡址遇。

二目標(biāo)函數(shù)化簡

1熄阻、預(yù)備知識(shí)，泰勒展開式倔约。主要使用泰勒展開式來近似原來的目標(biāo)函數(shù)

$f(x + \nabla{x}) = f(x) + f^{’}(x)\nabla{x} + \frac{1}{2}f^{''}(x)\nabla{x}\tag {2}$

2秃殉、推導(dǎo)過程：

$Obj{(t)} = \sum_{i=1}^n[l(y_i, \hat{y_i}^{(t-1)})+\partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)})*f_t(x_i) +\partial_{\hat{y}^{(t-1)}}^{2}l(y_i, \hat{y}^{(t-1)})*\frac{f_t(x_i)}{2} + Ω(f_t) + constant\tag {3}$ $\approx{ \sum_{i=1}^n[g_i*f_t(x_i) + h_i*\frac{f_t(x_i)}{2}] + Ω(f_t) + constant}\tag {4}$

$=\sum_{i=1}^n[g_i*w_{q(x_i)} + \frac{1}{2}h_i*w_{q(x_i)}^2] + \gamma{T} + \lambda{\sum_{j=1}^T\omega_j^{2}} \tag {5}$

$=\sum_{j=1}^T[(\sum_{i\in{I_j}}g_i) w_j+ \frac{1}{2}((\sum_{i\in{I_j}}h_i + \lambda) w_j^2)] + \gamma{T}\tag {6}$ $=\sum_{j=1}^T[G_jw_j + \frac{1}{2}{(H_j + \lambda)w_j^2}] + \gamma{T} \tag {7}$

式(3):它是在(2)的基礎(chǔ)上推導(dǎo)出來，是將 $l(y_i, \hat{y_i}^{(t-1)})$ 看著（2）中的x, $f_t(x_i)$ 記為 $\nabla{x}$ (注：這里的變換是近似變換浸剩。后面式中的t,表示時(shí)刻钾军；i表示第i個(gè)樣本。將 $g_i = \partial_{\hat{y}^{(t-1)}}l(y_i, \hat{y}^{(t-1)}), h_i = \partial_{\hat{y}^{(t-1)}}^{2}l(y_i, \hat{y}^{(t-1)})$ 绢要；又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=l(y_i%2C%20%5Chat%7By_i%7D%5E%7B(t-1)%7D)" alt="l(y_i, \hat{y_i}^{(t-1)})" mathimg="1">是一個(gè)固定值吏恭，可以合并到后面的常數(shù)項(xiàng)中。式(3)變形為式(4)
式(5)：它是將 $f_t(x_i)$ z和后面的正則項(xiàng)目展開了重罪。
- 這里對(duì)于f的定義做一下細(xì)化樱哼，把樹拆分成結(jié)構(gòu)部分q和葉子權(quán)重部分w。下圖是一個(gè)具體的例子剿配。結(jié)構(gòu)函數(shù)q把輸入映射到葉子的索引號(hào)上面去搅幅，即第幾個(gè)葉子；而w給定了每個(gè)索引號(hào)對(duì)應(yīng)的葉子分?jǐn)?shù)是什么呼胚。通俗的理解就是樣本x落到那個(gè)葉子結(jié)點(diǎn)上盏筐，取該結(jié)點(diǎn)的值。
  
  image
- 正則化項(xiàng)目選擇了數(shù)據(jù)樹的葉子個(gè)數(shù)砸讳，以及葉子權(quán)值大小平方琢融。為了防止樹在訓(xùn)練過程中過度復(fù)雜界牡。當(dāng)然這不是唯一的一種定義方式，不過這一定義方式學(xué)習(xí)出的樹效果一般都比較不錯(cuò)漾抬。下圖還給出了正則化項(xiàng)目計(jì)算的一個(gè)例子宿亡。
  
  image
式(6)主要的變換是將對(duì)樣本的遍歷，轉(zhuǎn)換為對(duì)樹的葉子結(jié)點(diǎn)的遍歷纳令。(理解部分：假設(shè)一共5個(gè)樣本挽荠，其中共有兩個(gè)樣本落在上圖樹中的leaf1,一個(gè)樣本落在leaf2中，還有兩個(gè)樣本落在leaf3中平绩。式(5)是直接統(tǒng)計(jì)各個(gè)樣本的值圈匆，式(6)則是直接遍歷葉子，遍歷leaf1時(shí)可以取得統(tǒng)計(jì)2個(gè)樣本的值捏雌，leaf2時(shí)可以取得統(tǒng)計(jì)1個(gè)樣本的值跃赚， leaf3時(shí)可以取得統(tǒng)計(jì)2個(gè)樣本的值，同樣可以訪問所有的樣本性湿。在葉子上遍歷更加方便計(jì)算)纬傲。式(6)中就是統(tǒng)計(jì)落在每個(gè)葉子結(jié)點(diǎn)中所有的樣本的一階導(dǎo)數(shù) $g_i$ 和該葉子結(jié)點(diǎn)權(quán)值w的乘積，同時(shí)二階導(dǎo)數(shù) $h_i$ 和該葉子結(jié)點(diǎn)權(quán)值w的乘積(每個(gè)樣本的 $g_i和h_i$ 都不一樣)肤频。
使式中 $G_j$ 表示當(dāng)前葉子結(jié)點(diǎn)所有樣本一階導(dǎo)數(shù)的和叹括，同理 $H_j$ 表示當(dāng)前樣本所有二階導(dǎo)數(shù)的和