XGBoost原理和公式推导

XGBoost的模型： y i ^ = ∑ k = 1 K f k ( x i ) \hat{y_i}=\sum_{k=1}^{K}f_k(x_i) yi​^​=k=1∑K​fk​(xi​)
其中 f k ∈ F f_k \in F fk​∈F， F = f ( x ) = w q ( x ) F=f(x)=w_{q(x)} F=f(x)=wq(x)​，每个 f k f_{k} fk​ 对应于一个独立的树结构 $q$ 和叶子权重 $w$。 w i w_{i} wi​代表第 $i$ 个结点的分数， w q ( x ) w_{q(x)} wq(x)​是对样本 $x$ 的打分，即模型预测值。

目标（损失）函数：
L = ∑ i = 1 n l ( y i ^ , y i ) + ∑ k = 1 T Ω ( f k ) L=\sum_{i=1}^{n}l(\hat{y_i},y_i)+\sum_{k=1}^{T}\Omega (f_k) L=i=1∑n​l(yi​^​,yi​)+k=1∑T​Ω(fk​)其中， Ω ( f ) = γ T + λ 2 ∥ w ∥ 2 \Omega (f)=\gamma T+\frac{\lambda}{2} {\left\| w \right\|}^2 Ω(f)=γT+2λ​∥w∥2，T是树中叶子节点的个数，该项中包含了两个部分，一个是叶子结点的总数，一个是叶子结点得到的 L 2 L_2 L2​ 正则化项。这个额外的正则化项能够平滑每个叶节点的学习权重来避免过拟合。目标函数中前一项为损失函数，后一项为正则化项，表示所有树的复杂度之和。

类似于GBDT算法，XGBoost同样使用加法模型，第 $t$ 步的预测值为： y ^ i ( t ) = y ^ i ( t − 1 ) + f t ( x i ) \hat{y}_i^{(t)}=\hat{y}_i^{(t-1)}+f_t(x_i) y^​i(t)​=y^​i(t−1)​+ft​(xi​)
第 $t$步的损失为：
L ( t ) = ∑ i = 1 n l ( y i , y ^ i ( t − 1 ) + f t ( x i ) ) + Ω ( f t ) L^{(t)}=\sum_{i=1}^{n}l(y_i,\hat{y}_i^{(t-1)}+f_t(x_i))+\Omega(f_t) L(t)=i=1∑n​l(yi​,y^​i(t−1)​+ft​(xi​))+Ω(ft​)
对损失函数使用二阶泰勒近似展开，类似于：
f ( x + Δ x ) ≃ f ( x ) + f ′ ( x ) Δ x + f ′ ′ ( x ) Δ x 2 f(x+\Delta x) \simeq f(x)+f'(x) \Delta x + f''(x) \Delta x^2 f(x+Δx)≃f(x)+f′(x)Δx+f′′(x)Δx2
损失函数变换为：
L ( t ) ≃ ∑ i = 1 n [ l ( y i , y ^ i ( t − 1 ) ) + g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ] + Ω ( f t ) L^{(t)} \simeq \sum_{i=1}^{n}[l(y_i,\hat{y}_i^{(t-1)})+g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t) L(t)≃i=1∑n​[l(yi​,y^​i(t−1)​)+gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)
其中， g i = ∂ y ^ ( t − 1 ) l ( y i , y ^ ( t − 1 ) ) , h i = ∂ y ^ ( t − 1 ) 2 l ( y i , y ^ ( t − 1 ) ) g_i= \partial_{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)}),h_i= \partial^2_{\hat{y}^{(t-1)}}l(y_i,\hat{y}^{(t-1)}) gi​=∂y^​(t−1)​l(yi​,y^​(t−1)),hi​=∂y^​(t−1)2​l(yi​,y^​(t−1))。

移除常数项：
L ^ ( t ) = ∑ i = 1 n ( g i f t ( x i ) + 1 2 h i f t 2 ( x i ) ) + Ω ( f t ) \hat{L}^{(t)}=\sum_{i=1}^{n}(g_if_t(x_i)+ \frac{1}{2}h_i f_t^2(x_i))+\Omega(f_t) L^(t)=i=1∑n​(gi​ft​(xi​)+21​hi​ft2​(xi​))+Ω(ft​)

定义 I j = { i ∣ q ( x i ) = j } I_j=\left \{ i|q(x_i) =j\right \} Ij​={i∣q(xi​)=j} 表示叶子节点$j$中的样本集合。
L ^ ( t ) = ∑ j = 1 T [ ( ∑ i ∈ I j g i ) w j + 1 2 ( ∑ i ∈ I j h i + λ ) w j 2 ] + γ T \hat{L}^{(t)}=\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 L^(t)=j=1∑T​[(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​+λ)wj2​]+γT
对 $w$求导得叶子节点 $j$ 最优 w j ∗ w_j^* wj∗​：
∑ i ∈ I j g i + w j ( ∑ i ∈ I j h i + λ ) = 0 \sum_{i\in I_j}g_i+w_j(\sum_{i \in I_j}h_i+\lambda) = 0 i∈Ij​∑​gi​+wj​(i∈Ij​∑​hi​+λ)=0
w j ∗ = − ∑ i ∈ I j g i ∑ i ∈ I j h i + λ w_j^*=-\frac{\sum_{i \in I_j}g_i}{\sum_{i \in I_j}h_i+\lambda} wj∗​=−∑i∈Ij​​hi​+λ∑i∈Ij​​gi​​
带入目标函数求得损失的最优值：
L ^ t ( q ) = − 1 2 ∑ j = 1 T ( ∑ i ∈ I j g i ) 2 ∑ i ∈ I j h i + λ + γ T \hat{L}^{{t}}(q)=-\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i \in I_j}g_i)^2}{\sum_{i \in I_j}h_i+\lambda}+\gamma T L^t(q)=−21​j=1∑T​∑i∈Ij​​hi​+λ(∑i∈Ij​​gi​)2​+γT
划分节点后的损失减少为：
L s p l i t = 1 2 ( ( ∑ i ∈ I L g i ) 2 ∑ i ∈ I L h i + λ + ( ∑ i ∈ I R g i ) 2 ∑ i ∈ I R h i + λ − ( ∑ i ∈ I g i ) 2 ∑ i ∈ I h i + λ ) L_{split}=\frac{1}{2}(\frac{(\sum_{i \in I_L}g_i)^2}{\sum_{i \in I_L}h_i+\lambda} + \frac{(\sum_{i \in I_R}g_i)^2}{\sum_{i \in I_R}h_i+\lambda} - \frac{(\sum_{i \in I}g_i)^2}{\sum_{i \in I}h_i+\lambda}) Lsplit​=21​(∑i∈IL​​hi​+λ(∑i∈IL​​gi​)2​+∑i∈IR​​hi​+λ(∑i∈IR​​gi​)2​−∑i∈I​hi​+λ(∑i∈I​gi​)2​)
其中， I = I l + I R I=I_l+I_R I=Il​+IR​。

论文原文：
Chen, T., & Guestrin, C. (2016, August). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining (pp. 785-794).

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！