[机器学习]XGBoost（2）——目标函数（公式详解）
前置知识详见[机器学习]XGBoost（1）——前置知识
知识回顾
在学习目标函数之前，先来回顾一下加法模型和前向分步算法的知识
注意：
- 在前向分步算法中，通常使用 t 来表示当前的步骤或迭代次数。
- 用 M 表示回归树的总数
- 用 T 表示叶子节点的总数。
加法模型
加法模型是将多个基学习器的预测结果相加来得到最终的预测。这里每个基学习器都是一棵回归树 f m ( x i ) = T ( θ ; x i ) = W q ( x i ) f_m(x_i) =T(\theta; x_i) = W_q(x_i) fm(xi)=T(θ;xi)=Wq(xi)。每个基学习器都试图纠正前一个基学习器的残差，这种逐步改进的方法使得模型能够逐渐逼近最优解。
y ^ i ( M ) = ∑ m = 1 M f m ( x i ) = y ^ i ( M − 1 ) + f M ( x i ) \hat{y}_i^{(M)} = \sum_{m=1}^{M} f_m(x_i) = \hat{y}_i^{(M-1)} + f_M(x_i) y^i(M)=m=1∑Mfm(xi)=y^i(M−1)+fM(xi)
其中， y ^ i ( M ) \hat{y}_i^{(M)} y^i(M) 是有 M 个基学习器的加法模型， f m ( x i ) f_m(x_i) fm(xi) 是第 m 个基学习器。
前向分步算法
前向分步算法是一种贪婪算法，每一步的目标是找到并添加一个新的基学习器，使得这个基学习器在当前模型的基础上进行优化 O b j ( t ) Obj(t) Obj(t)。在第 t 步，我们添加一个新的基学习器，使得目标函数得到最小化。
y
^
i
(
t
)
=
y
^
i
(
t
−
1
)
+
f
t
(
x
i
)
=
y
^
i
(
t
−
1
)
+
T
(
θ
;
x
i
)
=
y
^
i
(
t
−
1
)
+
W
q
(
x
i
)
\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i) = \hat{y}_i^{(t-1)} + T(\theta; x_i) = \hat{y}_i^{(t-1)} + W_q(x_i)
y^i(t)=y^i(t−1)+ft(xi)=y^i(t−1)+T(θ;xi)=y^i(t−1)+Wq(xi)
在实际应用中，我们从 t=1 开始，逐步构建模型，直到 t=M，此时
y
^
i
(
t
)
\hat{y}_i^{(t)}
y^i(t) 就变成了
y
^
i
(
M
)
\hat{y}_i^{(M)}
y^i(M)
目标函数
XGBoost的目标函数由两部分组成：损失函数（Loss Function）和正则化项（Regularization Term）。
- 损失函数衡量模型预测值与真实值之间的差异。
- 正则化项用于防止过拟合，它惩罚模型的复杂度，包括树的深度、叶子节点的数量以及叶子节点的权重。
目标函数公式如下所示：
O
b
j
(
t
)
=
∑
i
=
1
N
L
(
y
^
i
(
t
)
,
y
i
)
+
∑
m
=
1
t
Ω
(
f
m
)
Obj^{(t)} = \sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) + \sum_{m=1}^{t}\Omega(f_m)
Obj(t)=i=1∑NL(y^i(t),yi)+m=1∑tΩ(fm)
其中：
- O b j ( t ) Obj^{(t)} Obj(t)：表示在第 t 步的整体目标函数值。
- N N N：表示样本数量，即数据集中的样本总数。
- L ( y ^ i ( t ) , y i ) L(\hat{y}_i^{(t)}, y_i) L(y^i(t),yi)：表示损失函数，用于衡量第 t 步模型对第 i 个样本的预测值 y ^ i ( t ) \hat{y}_i^{(t)} y^i(t) 与真实值 y i y_i yi 之间的差异。
- t t t：表示在第 t t t 步添加的树。
- Ω ( f m ) \Omega(f_m) Ω(fm)：表示第 m m m 棵树的正则化项。
在第 t t t 步，我们可以忽略前 t − 1 t−1 t−1 棵树的正则化项，因为 ∑ m = 1 t − 1 Ω ( f m ) \sum_{m=1}^{t-1} \Omega(f_m) ∑m=1t−1Ω(fm) 已知，是一个常量，所以在优化过程中可以忽略。
因此目标函数公式可以改写成这样：
O
b
j
(
t
)
=
∑
i
=
1
N
L
(
y
^
i
(
t
)
,
y
i
)
+
∑
m
=
1
t
−
1
Ω
(
f
m
)
+
Ω
(
f
t
)
=
∑
i
=
1
N
L
(
y
^
i
(
t
)
,
y
i
)
+
Ω
(
f
t
)
Obj^{(t)} = \sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) + \sum_{m=1}^{t-1}\Omega(f_m) + \Omega(f_t)\\ =\sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) + \Omega(f_t)
Obj(t)=i=1∑NL(y^i(t),yi)+m=1∑t−1Ω(fm)+Ω(ft)=i=1∑NL(y^i(t),yi)+Ω(ft)
而第 t 棵树的正则化项
Ω
(
f
t
)
\Omega(f_t)
Ω(ft)的公式如下：
Ω
(
f
t
)
=
γ
T
t
+
1
2
λ
∑
j
=
1
T
t
∥
w
j
∥
2
\Omega(f_t) = \gamma T_t + \frac{1}{2} \lambda \sum_{j=1}^{T_t} \|w_j\|^2
Ω(ft)=γTt+21λj=1∑Tt∥wj∥2
其中，
T
t
T_t
Tt 是第 t 棵树叶子节点个数，
γ
\gamma
γ 和
λ
\lambda
λ 是超参数，可以控制惩罚力度。
- γ \gamma γ控制叶子节点数量和树的深度，叶子节点数量越多，说明树的深度越深，容易出现过拟合，此时通过 γ \gamma γ惩罚
- λ \lambda λ控制节点平均目标值，当 ∥ w j ∥ 2 \|w_j\|^2 ∥wj∥2较大时，说明这一颗树在整个模型中值的占比比较大，也容易出现过拟合，此时通过 λ \lambda λ惩罚
优化目标
在XGBoost的前向分步算法中，第 t t t 步的目标是找到一个新的基学习器 f t ( x ) f_t(x) ft(x)，使得目标函数 O b j ( t ) Obj^{(t)} Obj(t) 最小化。
a r g m i n ( O b j ( t ) ) = a r g m i n ( ∑ i = 1 N L ( y ^ i ( t ) , y i ) + Ω ( f t ) ) = a r g m i n ( ∑ i = 1 N L ( y ^ i ( t ) , y i ) + γ T t + 1 2 λ ∑ j = 1 T t ∥ w j ∥ 2 ) argmin(Obj^{(t)}) = argmin( \sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) + \Omega(f_t))\\= argmin( \sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) + \gamma T_t + \frac{1}{2} \lambda \sum_{j=1}^{T_t} \|w_j\|^2) argmin(Obj(t))=argmin(i=1∑NL(y^i(t),yi)+Ω(ft))=argmin(i=1∑NL(y^i(t),yi)+γTt+21λj=1∑Tt∥wj∥2)
如何优化损失？
思路：将大目标拆解成很多个小目标逐个击破
-
∑ i = 1 N L ( y ^ i ( t ) , y i ) \sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) ∑i=1NL(y^i(t),yi)是按样本顺序遍历每个样本的损失，总损失是所有样本损失的累和
-
由于每个叶子节点平均的目标值 W 只能影响它自己的叶子节点，因此将样本顺序遍历转化成按节点顺序遍历，将损失函数分解并针对每个决策树的叶子节点进行优化。
O b j ( t ) = ∑ i = 1 N L ( y ^ i ( t ) , y i ) + γ T t + 1 2 λ ∑ j = 1 T t ∥ w j ∥ 2 = ∑ j = 1 T t ∑ i ∈ I j L ( y ^ i ( t ) , y i ) + γ T t + 1 2 λ ∑ j = 1 T t ∥ w j ∥ 2 = γ T t + ∑ j = 1 T t [ ( ∑ i ∈ I j L ( y ^ i ( t ) , y i ) ) + 1 2 λ ∥ w j ∥ 2 ] Obj^{(t)}= \sum_{i=1}^{N} L(\hat{y}_i^{(t)}, y_i) + \gamma T_t + \frac{1}{2} \lambda \sum_{j=1}^{T_t} \|w_j\|^2\\ = \sum_{j=1}^{{T_t}} \sum_{i \in I_j} L(\hat{y}_i^{(t)}, y_i) + \gamma {T_t} + \frac{1}{2} \lambda \sum_{j=1}^{T_t} \|w_j\|^2\\ =\gamma {T_t} +\sum_{j=1}^{{T_t}}[ (\sum_{i \in I_j} L(\hat{y}_i^{(t)}, y_i) )+ \frac{1}{2} \lambda \|w_j\|^2] Obj(t)=i=1∑NL(y^i(t),yi)+γTt+21λj=1∑Tt∥wj∥2=j=1∑Tti∈Ij∑L(y^i(t),yi)+γTt+21λj=1∑Tt∥wj∥2=γTt+j=1∑Tt[(i∈Ij∑L(y^i(t),yi))+21λ∥wj∥2]
然后将 y ^ i ( t ) = y ^ i ( t − 1 ) + W q ( x i ) \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + W_q(x_i) y^i(t)=y^i(t−1)+Wq(xi)代入，得到：
O b j ( t ) = γ T t + ∑ j = 1 T t [ ( ∑ i ∈ I j L ( y ^ i ( t − 1 ) + W j , y i ) ) + 1 2 λ ∥ w j ∥ 2 ] Obj^{(t)}=\gamma {T_t} +\sum_{j=1}^{{T_t}}[ (\sum_{i \in I_j} L(\hat{y}_i^{(t-1)} + W_j, y_i) )+ \frac{1}{2} \lambda \|w_j\|^2] Obj(t)=γTt+j=1∑Tt[(i∈Ij∑L(y^i(t−1)+Wj,yi))+21λ∥wj∥2] 因为节点已经确定了，所以 y ^ i ( t − 1 ) + W q ( x i ) \hat{y}_i^{(t-1)} + W_q(x_i) y^i(t−1)+Wq(xi)中的 W q ( x i ) W_q(x_i) Wq(xi)就是 W j W_j Wj -
转化后，总的损失等于每个节点损失的累加，把求所有样本上损失的累和的最小值问题转化为求每个节点上损失的最小值问题，此时问题简单了，因为每个节点上损失的最小值问题只有一个变量W
而现在的问题是：损失函数不会提前给出，因为不同的任务场景对应的损失函数不同，那么如何解决？
思路：找一种方法，能够无视具体的损失函数，将式子分解成含 W 的形式 --> 泰勒展开
泰勒展开可以将一个函数展开成多项式，以此来近似表示这个函数。阶数越高表示的越精确
-
对于任意可微分的损失函数 L，我们可以使用泰勒展开来近似它：
L ( y i , y ^ i ( t − 1 ) + W j ) ≈ L ( y i , y ^ i ( t − 1 ) ) + g i W j + 0.5 ∗ h i W j 2 L(y_i, \hat y_i^{(t-1)} + W_j) ≈ L(y_i, \hat y_i^{(t-1)}) + g_i W_j + 0.5 * h_i W_j^2 L(yi,y^i(t−1)+Wj)≈L(yi,y^i(t−1))+giWj+0.5∗hiWj2其中， g i g_i gi 是第 i i i 个样本的损失函数关于预测值的一阶导数（梯度）， h i h_i hi 是第 i i i 个样本的二阶导数（Hessian）。
-
应用到每个叶子节点，我们得到：
∑ i ∈ I j L ( y i , y ^ i ( t − 1 ) + W j ) ≈ ∑ i ∈ I j [ L ( y i , y ^ i ( t − 1 ) ) + g i W j + 0.5 ∗ h i W j 2 ] ∑_{i ∈ I_j} L(y_i, \hat y_i^{(t-1)} + W_j) ≈ ∑_{i ∈ I_j} [L(y_i, \hat y_i^{(t-1)}) + g_i W_j + 0.5 * h_i W_j^2] i∈Ij∑L(yi,y^i(t−1)+Wj)≈i∈Ij∑[L(yi,y^i(t−1))+giWj+0.5∗hiWj2] -
整合正则化项，我们得到每个叶子节点的优化目标：
∑ i ∈ I j L ( y i , y ^ i ( t − 1 ) ) + G j W j + 0.5 ∗ ( H j + λ ) W j 2 + γ ∑_{i ∈ I_j} L(y_i, \hat y_i^{(t-1)}) + G_j W_j + 0.5 * (H_j + λ) W_j^2 + γ i∈Ij∑L(yi,y^i(t−1))+GjWj+0.5∗(Hj+λ)Wj2+γ其中， G j = ∑ i ∈ I j g i G_j = ∑_{i ∈ I_j}g_i Gj=∑i∈Ijgi 是节点 j 上所有样本梯度的和， H j = ∑ i ∈ I j h i H_j = ∑_{i ∈ I_j}h_i Hj=∑i∈Ijhi是Hessian的和。 ∑ i ∈ I j L ( y i , y ^ i ( t − 1 ) ) ∑_{i ∈ I_j} L(y_i, \hat y_i^{(t-1)}) ∑i∈IjL(yi,y^i(t−1))是一个常量，因此可以省略
目标函数的最终形态：
O b j ( t ) = γ T t + ∑ j = 1 T t [ ( W j G j + 1 2 ∥ w j ∥ 2 ( λ + H j ) ] Obj^{(t)} =\gamma {T_t} +\sum_{j=1}^{T_t}[ ( W_jG_j + \frac{1}{2} \|w_j\|^2(\lambda + H_j)] Obj(t)=γTt+j=1∑Tt[(WjGj+21∥wj∥2(λ+Hj)] -
求解最优 W j W_j Wj：
对上述表达式关于 W j W_j Wj求导，并令导数等于0：
G j + ( H j + λ ) W j = 0 G_j + (H_j + λ) W_j = 0 Gj+(Hj+λ)Wj=0
解这个方程得到：
W j ∗ = − G j H j + λ W_j ^* = -\frac{G_j} {H_j + λ} Wj∗=−Hj+λGj
目标函数的最小化：
O b j ( t ) ∗ = m i n O b j ( t ) ≈ γ T t − 0.5 ∗ ∑ j = 1 T t G j 2 H j + λ Obj^{(t)*} = min Obj^{(t)}≈ γ{T_t}- 0.5 * ∑_{j=1}^{T_t} \frac{G_j^2}{ H_j + λ} Obj(t)∗=minObj(t)≈γTt−0.5∗j=1∑TtHj+λGj2
因此，拿到一个数据集之后，可以先计算每个节点的一阶梯度和二阶梯度，再计算 H j H_j Hj 和 G j G_j Gj，然后就可以根据公式把每个叶子节点的值计算出来，也可以计算出最小值