XGBoost算法的原理推导
本节重点阐述 XGBoost 的算法原理和推导过程。既然 XGBoost 整体上仍属于 GBDT 算法系统，那么 XGBoost 也一定是由多个基模型组成的一个加性模型，所以 XGBoost 可表示为：
y
^
i
=
∑
k
=
1
K
f
k
(
x
i
)
(12-1)
\hat{y}_i = \sum_{k=1}^{K} f_k(x_i) \tag{12-1}
y^i=k=1∑Kfk(xi)(12-1)
根据前向分步算法，假设第 t 次迭代的基模型为 f t ( x ) f_t(x) ft(x)，有：
y ^ i ( t ) = ∑ k = 1 t − 1 f k ( x i ) + f t ( x i ) (12-2) \hat{y}_i^{(t)} = \sum_{k=1}^{t-1} f_k(x_i) + f_t(x_i) \tag{12-2} y^i(t)=k=1∑t−1fk(xi)+ft(xi)(12-2)
下面推导 XGBoost 损失函数。损失函数基本形式由经验损失项和正则化项构成：
L
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
)
+
∑
i
=
1
t
Ω
(
f
i
)
(12-3)
L = \sum_{i=1}^{n} l(y_i, \hat{y}_i) + \sum_{i=1}^{t} \Omega(f_i) \tag{12-3}
L=i=1∑nl(yi,y^i)+i=1∑tΩ(fi)(12-3)
其中 ∑ i = 1 n l ( y i , y ^ i ) \sum_{i=1}^{n} l(y_i, \hat{y}_i) ∑i=1nl(yi,y^i) 为经验损失项，表示训练数据预测值与真实值之间的损失； ∑ i = 1 t Ω ( f i ) \sum_{i=1}^{t} \Omega(f_i) ∑i=1tΩ(fi) 为正则化项，表示全部 t 棵树的复杂度之和，这也是 XGBoost 控制模型过拟合的方法。
根据前向分步算法，以第 t 步模型为例，假设模型对第 i 个样本
x
i
x_i
xi 的预测值为：
y
^
i
(
t
)
=
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
(12-4)
\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i) \tag{12-4}
y^i(t)=y^i(t−1)+ft(xi)(12-4)
其中
y
^
i
(
t
−
1
)
\hat{y}_i^{(t-1)}
y^i(t−1) 是由第
t
−
1
t-1
t−1 步的模型给出的预测值，其作为一个已知常量存在，
f
t
(
x
i
)
f_t(x_i)
ft(xi) 为第 t 步树模型的预测值。因而式(12-3)的目标函数可以改写为：
L
(
t
)
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
(
t
)
)
+
∑
i
=
1
t
Ω
(
f
i
)
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
)
+
∑
i
=
1
t
Ω
(
f
i
)
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
)
+
Ω
(
f
t
)
+
Constant
(12-5)
\begin{aligned} L^{(t)} &= \sum_{i=1}^{n} l(y_i, \hat{y}_i^{(t)}) + \sum_{i=1}^{t} \Omega(f_i) \\ &= \sum_{i=1}^{n} l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \sum_{i=1}^{t} \Omega(f_i) \\ &= \sum_{i=1}^{n} l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) + \Omega(f_t) + \text{Constant} \tag{12-5} \end{aligned}
L(t)=i=1∑nl(yi,y^i(t))+i=1∑tΩ(fi)=i=1∑nl(yi,y^i(t−1)+ft(xi))+i=1∑tΩ(fi)=i=1∑nl(yi,y^i(t−1)+ft(xi))+Ω(ft)+Constant(12-5)
式(12-5)对正则化项进行了拆分，因为前
t
−
1
t-1
t−1棵树的结构已经确定，所以前
t
−
1
t-1
t−1棵树的复杂度之和也可以表示为常数：
∑
i
=
1
t
Ω
(
f
i
)
=
Ω
(
f
t
)
+
∑
i
=
1
t
−
1
Ω
(
f
i
)
=
Ω
(
f
t
)
+
Constant
(12-6)
\begin{aligned} \sum_{i=1}^{t} \Omega(f_i) &= \Omega(f_t) + \sum_{i=1}^{t-1} \Omega(f_i) \\ &= \Omega(f_t) + \text{Constant} \tag{12-6} \end{aligned}
i=1∑tΩ(fi)=Ω(ft)+i=1∑t−1Ω(fi)=Ω(ft)+Constant(12-6)
然后针对式(12-5)前半部分
l
(
y
i
,
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
)
l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right)
l(yi,y^i(t−1)+ft(xi))，使用二阶泰勒展开式，这里需要用到函数的二阶导数信息，相应的损失函数经验损失项可以改写为：
l
(
y
i
,
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
)
=
l
(
y
i
,
y
^
i
(
t
−
1
)
)
+
g
i
f
t
(
x
i
)
+
1
2
h
i
f
t
2
(
x
i
)
(12-7)
l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) = l\left(y_i, \hat{y}_i^{(t-1)}\right) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \tag{12-7}
l(yi,y^i(t−1)+ft(xi))=l(yi,y^i(t−1))+gift(xi)+21hift2(xi)(12-7)
其中 g i g_i gi 为损失函数一阶导数， h i h_i hi 为损失函数二阶导数，需要注意的是，这里是针对 y ^ i ( t − 1 ) \hat{y}_i^{(t-1)} y^i(t−1) 进行求导。
XGBoost 相较于 GBDT 的一个最大的特点是用到了损失函数的二阶导数信息，所以当自定义或者选择 XGBoost 损失函数时，需要其二阶可导。以平方损失函数为例：
l
(
y
i
,
y
^
i
(
t
−
1
)
)
=
(
y
i
−
y
^
i
(
t
−
1
)
)
2
(12-8)
l\left(y_i, \hat{y}_i^{(t-1)}\right) = \left(y_i - \hat{y}_i^{(t-1)}\right)^2 \tag{12-8}
l(yi,y^i(t−1))=(yi−y^i(t−1))2(12-8)
对应的一阶导数和二阶导数分别为：
g
i
=
∂
l
(
y
i
,
y
^
i
(
t
−
1
)
)
∂
y
^
i
(
t
−
1
)
=
−
2
(
y
i
−
y
^
i
(
t
−
1
)
)
(12-9)
g_i = \frac{\partial l\left(y_i, \hat{y}_i^{(t-1)}\right)}{\partial \hat{y}_i^{(t-1)}} = -2\left(y_i - \hat{y}_i^{(t-1)}\right) \tag{12-9}
gi=∂y^i(t−1)∂l(yi,y^i(t−1))=−2(yi−y^i(t−1))(12-9)
h i = ∂ 2 l ( y i , y ^ i ( t − 1 ) ) ∂ ( y ^ i ( t − 1 ) ) 2 = 2 (12-10) h_i = \frac{\partial^2 l\left(y_i, \hat{y}_i^{(t-1)}\right)}{\partial \left(\hat{y}_i^{(t-1)}\right)^2} = 2 \tag{12-10} hi=∂(y^i(t−1))2∂2l(yi,y^i(t−1))=2(12-10)
将式(12-7)的损失函数二阶泰勒展开式代入式(12-5)，可得损失函数的近似表达式：
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
)
+
C
o
n
s
t
a
n
t
(12-11)
L^{(t)} \approx \sum_{i=1}^{n} \left[l\left(y_i, \hat{y}_i^{(t-1)}\right) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)\right] + \Omega(f_t) + Constant \tag{12-11}
L(t)≈i=1∑n[l(yi,y^i(t−1))+gift(xi)+21hift2(xi)]+Ω(ft)+Constant(12-11)
去掉相关常数项，式(12-11)简化后的损失函数表达式为：
L
(
t
)
≈
∑
i
=
1
n
[
g
i
f
t
(
x
i
)
+
1
2
h
i
f
t
2
(
x
i
)
]
+
Ω
(
f
t
)
(12-12)
L^{(t)} \approx \sum_{i=1}^{n} \left[g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)\right] + \Omega(f_t) \tag{12-12}
L(t)≈i=1∑n[gift(xi)+21hift2(xi)]+Ω(ft)(12-12)
由式(12-12)可知，只需要求出损失函数每一步的一阶导数和二阶导数值，并对目标函数进行优化求解，就可以得到前向分步中每一步的模型 f ( x ) f(x) f(x)，最后根据加性模型得到 XGBoost 模型。
然而关于 XGBoost 的推导并没有到此结束。为了计算 XGBoost 决策树结点分裂条件，我们还需要进一步的推导。
我们对决策树做以下定义。假设一棵决策树是由叶子节点的权重
w
w
w 和样本实例到叶子节点的映射关系
q
q
q 构成，这种映射关系可以理解为决策树的分支结构。所以一棵树的数学表达可以定义为：
f
t
(
x
)
=
w
q
(
x
)
(12-13)
f_t(x) = w_{q(x)} \tag{12-13}
ft(x)=wq(x)(12-13)
然后定义决策树复杂度的正则化项。模型复杂度
Ω
\Omega
Ω 可由单棵决策树的叶子节点数
T
T
T 和叶子权重
w
w
w 决定，即损失函数的复杂度由决策树的所有叶子节点数和叶子权重所决定。所以，模型的复杂度可以表示为：
Ω
(
f
t
)
=
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
(12-14)
\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 \tag{12-14}
Ω(ft)=γT+21λj=1∑Twj2(12-14)
下面对决策树所有叶子节点重新进行归组。将属于第 j 个叶子节点的所有样本
x
i
x_i
xi 划人一个叶子节点的样本集合中，即
I
j
=
{
i
∣
q
(
x
i
)
=
j
}
I_j = \{i | q(x_i) = j\}
Ij={i∣q(xi)=j}，因而 XGBoost 的损失函数式(12-12)可以改写为：
L
(
t
)
≈
∑
i
=
1
n
[
g
i
f
t
(
x
i
)
+
1
2
h
i
f
t
2
(
x
i
)
]
+
Ω
(
f
t
)
=
∑
i
=
1
n
[
g
i
w
q
(
x
i
)
+
1
2
h
i
w
q
(
x
i
)
2
]
+
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
=
∑
j
=
1
T
[
(
∑
i
∈
I
j
g
i
)
w
j
+
1
2
(
∑
i
∈
I
j
h
i
+
λ
)
w
j
2
]
+
γ
T
(12-15)
\begin{aligned} L^{(t)} &\approx \sum_{i=1}^{n} \left[g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)\right] + \Omega(f_t) \\ &= \sum_{i=1}^{n} \left[g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2\right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2 \\ &= \sum_{j=1}^{T} \left[\left(\sum_{i \in I_j} g_i\right) w_j + \frac{1}{2} \left(\sum_{i \in I_j} h_i + \lambda\right) w_j^2\right] + \gamma T \tag{12-15} \end{aligned}
L(t)≈i=1∑n[gift(xi)+21hift2(xi)]+Ω(ft)=i=1∑n[giwq(xi)+21hiwq(xi)2]+γT+21λj=1∑Twj2=j=1∑T
i∈Ij∑gi
wj+21
i∈Ij∑hi+λ
wj2
+γT(12-15)
定义 G j = ∑ i ∈ I j g i G_j = \sum_{i \in I_j} g_i Gj=∑i∈Ijgi， H j = ∑ i ∈ I j h i H_j = \sum_{i \in I_j} h_i Hj=∑i∈Ijhi，其中 G j G_j Gj 可以理解为叶子节点 j 所包含样本的一阶偏导数累加之和， H j H_j Hj 可以理解为叶子节点 j 所包含样本的二阶偏导数累加之和， G j G_j Gj 和 H j H_j Hj均为常量。
将
G
j
G_j
Gj 和
H
j
H_j
Hj 代入式(12-15)，损失函数又可以变换为：
L
(
t
)
=
∑
j
=
1
T
[
G
j
w
j
+
1
2
(
H
j
+
λ
)
w
j
2
]
+
γ
T
(12-16)
L^{(t)} = \sum_{j=1}^{T} \left[G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2\right] + \gamma T \tag{12-16}
L(t)=j=1∑T[Gjwj+21(Hj+λ)wj2]+γT(12-16)
对于每个叶子节点
j
j
j，将其从目标函数中单独取出：
G
j
w
j
+
1
2
(
H
j
+
λ
)
w
j
2
(12-17)
G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2 \tag{12-17}
Gjwj+21(Hj+λ)wj2(12-17)
由前述推导可知，
G
j
G_j
Gj 和
H
j
H_j
Hj 相对于第
t
t
t 棵树来说是可以计算出来的。所以式(12-17)是一个只包含一个变量叶子节点权重
w
j
w_j
wj 的一元二次函数，可根据最值公式求其最值点。当相互独立的每棵树的叶子节点都达到最优值时，整个损失函数也相应地达到最优。在树结构固定的情况下，对式(12-17)求导并令其为 0，可得最优点和最优值为：
w
j
∗
=
−
G
j
H
j
+
λ
(12-18)
w_j^* = -\frac{G_j}{H_j + \lambda} \tag{12-18}
wj∗=−Hj+λGj(12-18)
L = − 1 2 ∑ j = 1 T G j 2 H j + λ + γ T (12-19) L = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T \tag{12-19} L=−21j=1∑THj+λGj2+γT(12-19)
假设决策树模型在某个结点进行了特征分裂，分裂前的损失函数为：
L
b
e
f
o
r
e
=
−
1
2
[
(
G
L
+
G
R
)
2
H
L
+
H
R
+
λ
]
+
γ
(12-20)
L_{before} = -\frac{1}{2} \left[\frac{(G_L + G_R)^2}{H_L + H_R + \lambda}\right] + \gamma \tag{12-20}
Lbefore=−21[HL+HR+λ(GL+GR)2]+γ(12-20)
分裂后的损失函数为：
L
a
f
t
e
r
=
−
1
2
[
G
L
2
H
L
+
λ
+
G
R
2
H
R
+
λ
]
+
2
γ
(12-21)
L_{after} = -\frac{1}{2} \left[\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda}\right] + 2\gamma \tag{12-21}
Lafter=−21[HL+λGL2+HR+λGR2]+2γ(12-21)
那么，分裂后的信息增益为：
G
a
i
n
=
1
2
[
G
L
2
H
L
+
λ
+
G
R
2
H
R
+
λ
−
(
G
L
+
G
R
)
2
H
L
+
H
R
+
λ
]
−
γ
(12-22)
Gain = \frac{1}{2} \left[\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda}\right] - \gamma \tag{12-22}
Gain=21[HL+λGL2+HR+λGR2−HL+HR+λ(GL+GR)2]−γ(12-22)
如果增益 G a i n > 0 Gain > 0 Gain>0，即分裂为两个叶子节点后，目标函数下降了，则考虑此次分裂的结果。实际处理时需要遍历所有特征寻找最优分裂特征。
以上就是 XGBoost 相对完整的数学推导过程，核心是通过损失函数展开到二阶导数来进一步逼近真实损失。
以下是本文部分公式的详细解析博文：
公式（12-1）加法模型表达式
公式（12-2）t轮迭代中对样本i的预测值
公式（12-3）损失函数
公式（12-5）正则化项拆分的目标函数
公式（12-7）损失函数经验损失项二阶泰勒展开式
公式（12-13）树的叶子节点权重w和映射关系q
公式（12-14）决策树复杂度的正则化项
公式（12-15）目标函数分解成叶子节点的形式
公式（12-22）计算信息增益（Gain）的公式
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
39
0- 0
已为社区贡献270条内容
所有评论(0)