Xgboost

在最近的 Kaggle 競賽中，利用 Xgboost 的隊(duì)伍經(jīng)常能問鼎冠軍，那么問題來了，Xgboost 為什么這么強(qiáng)呢？

算法釋義

Xgboost 是一種帶有正則化項(xiàng)，并利用損失函數(shù)泰勒展開式中二階導(dǎo)數(shù)信息優(yōu)化求解并增加一些計(jì)算優(yōu)化的梯度提升樹。Xgboost 的目標(biāo)函數(shù)定義為：
Obj = \sum_{i=1}^N l(y_i, \sum_{t=1}^Tf_t(x_i)) + \sum_{t=1}^TΩ(f_t(x))

其中 l 為損失函數(shù)， Ω(ft(x)) 是用于懲罰 ft(x) 模型復(fù)雜度的正則化項(xiàng)。根據(jù)上述目標(biāo)函數(shù)可以得到 Xgboost 在每一輪前向分步算法中的目標(biāo)函數(shù)為：
\begin{align} & Obj^{(t)} = \sum_{i=1}^N l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + Ω(f_t(x)) + constant\\ &聯(lián)想二級(jí)泰勒展開式：\\ &f(x_0 + x) = f(x_0) + f'(x_0)x + \frac 1 2 f''(x_0)x^2 \\ & 令其中\(zhòng), f(x) = l(y_i, \hat y_i^{(t-1)})， x_0 = \hat y_i^{(t-1)}，x = f_t(x_i)： \\ & 再令：g_i = l'(y_i, \hat y_i^{(t-1)}), h_i = l''(y_i, \hat y_i^{(t-1)})，并去除常數(shù)項(xiàng)： \\ & Obj^{(t)} = \sum_{i=1}^N \left(g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i) \right) + Ω(f_t(x)) \\ \end{align}

從而每一步的目標(biāo)函數(shù)可以用損失函數(shù)的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)來表示，這樣每一輪需要求解的 ft(x) 為：
f_t(x) = arg \min_{f_t(x)} Obj^{(t)}

那么如何使目標(biāo)函數(shù)最小化呢？

算法求解

Xgboost 每生成一顆樹的方式和其他決策樹的方式類似，采用一種貪心策略。
我們知道一顆決策樹可以表示為：
f_t(x) = w_{q(x)}

其中 q(x) 把 x 映射到?jīng)Q策樹中的一個(gè)節(jié)點(diǎn)，wq 把每一個(gè)結(jié)點(diǎn)映射一個(gè)值，即 ft(x) 的取值。
\begin{align} & 令I(lǐng)_j表示結(jié)點(diǎn)j,即： I_j = \{i| q(x_i) = j\} \\ & 然后取正則化項(xiàng)：\\ & Ω(f_t(x)) = γT + \frac 1 2 λ \sum_{j=1}^T w_j^2 \\ & 其中\(zhòng),T\,為葉節(jié)點(diǎn)個(gè)數(shù) \\ & 目標(biāo)函數(shù)Obj^{(t)}可以化為： \\ & Obj^{(t)} = \sum_{j=1}^T \left(w_j\sum_{i \in I_j} g_i + \frac 1 2 w_j^2 \sum_{i \in I_j} h_i \right) + Ω(f_t(x)) \\ & 即：\\ &Obj^{(t)} = \sum_{j=1}^T \left(w_j\sum_{i \in I_j} g_i + \frac 1 2 w_j^2 \left(λ + \sum_{i \in I_j} h_i \right) \right) + γT \\ \end{align}

我們知道上述目標(biāo)函數(shù)中有權(quán)重 w 以及樹的節(jié)點(diǎn)數(shù)量 T 兩組變量，首先上式可以拆分為 T 個(gè)獨(dú)立的二次函數(shù)最小化問題，每個(gè)子問題中只有 w 權(quán)重這一組變量，首先求解權(quán)重 w。

權(quán)重求解

因?yàn)槎魏瘮?shù)最小化問題有解析解，所以直接求解：
\begin{align} & w_j^* = - \frac {\sum_{i \in I_j} g_i} {λ + \sum_{i \in I_j} h_i} \\ & 令 G_j = \sum_{i \in I_j} g_i， H_j = \sum_{i \in I_j} h_i，則 \\ & w_j^* = - \frac {G_j} { H_j + λ } \\ & 那么在最優(yōu)解 w_j^*的情況下子問題和母問題的目標(biāo)函數(shù)分別為： \\ & Obj_j = - \frac {G_j^2} {2(H_j + λ)} \\ & Obj = - \frac 1 2 \sum_{j=1}^T \frac {G_j^2} {H_j + λ} + γT \\ \end{align}

樹的生成

解決了權(quán)重求解的問題，如何解決結(jié)點(diǎn)數(shù)量問題呢？也就是說怎么樣對(duì)結(jié)點(diǎn)進(jìn)行劃分呢？這里一般在每個(gè)節(jié)點(diǎn)上采用貪心策略進(jìn)行劃分。通過比較劃分前和劃分后目標(biāo)函數(shù)的減少量來選擇最優(yōu)劃分屬性和劃分點(diǎn)，具體地：
Gain = \frac 1 2 \left( \frac {G_L^2} {H_L + λ} + \frac {G_R^2} {H_R + λ} - \frac {(G_L + G_R)^2} {(H_L + H_R) + λ} \right) - γ

減少樹的權(quán)重

使用 Xgboost 沒生成一棵決策樹時(shí)，更新 y(t)(x) 時(shí)：
\hat y_i^{(t)} = \hat y_i^{(t-1)} + ε f_t(x_i)

一般采用較小的 ε 值，例如 0.1，這樣可以防止在某一輪“學(xué)得太好”，并且為未來的迭代提供“學(xué)習(xí)空間”，可以有效地防止過擬合。

參考資料

《Xgboost PPT》，陳天奇

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容