XGBoost全称 “Extreme Gradient Boosting“，被称为极端梯度提升法。它利用一连串的决策树，通过学习前一个决策树残差的方式，来不断逼近最终的预测结果，这里着重讲目标函数是如何构建的以及如何生成一棵新的树。
假设我们已经训练了
K
K
K棵树，那么其对于第
i
i
i个样本的预测结果为：
y
^
i
=
∑
k
=
1
K
f
k
(
x
i
)
hat y_i=sumlimits_{k=1}^Kf_k(x_i)
y^i=k=1∑Kfk(xi)
- 如果是回归问题，那么其最终的预测值就是 y ^ hat y y^
- 如果是分类问题，那么最终的结果
y
^
hat y
y^就是其预测值为对应分类的概率（
0
<
y
^
<
1
0
假设我们一共有
n
n
n条样本数据，我们可以构建一个统一的目标函数：
O
b
j
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
)
+
∑
k
=
1
K
Ω
(
f
k
)
Obj=sumlimits_{i=1}^nl(y_i,hat y_i)+sumlimits_{k=1}^KΩ(f_k)
Obj=i=1∑nl(yi,y^i)+k=1∑KΩ(fk)
- 其中 y i y_i yi是第 i i i个样本的真实值，如果是分类问题那就是1
- l ( y i , y ^ i ) l(y_i,hat y_i) l(yi,y^i)是损失函数，对于回归问题我们可以使用MSE，对于分类问题可以使用Cross entropy
- Ω ( f k ) Ω(f_k) Ω(fk)是对于每棵树的具体约束，防止单棵树过拟合，下面会具体讲
同样对于样本
i
i
i我们可以得到：
y
i
(
0
)
=
0
(
d
e
f
a
u
l
t
v
a
l
u
e
)
y
i
(
1
)
=
f
1
(
x
i
)
=
y
i
(
0
)
+
f
1
(
x
i
)
y
i
(
2
)
=
f
1
(
x
i
)
+
f
2
(
x
i
)
=
y
i
(
1
)
+
f
2
(
x
i
)
.
.
.
y
i
(
k
)
=
f
1
(
x
i
)
+
f
2
(
x
i
)
+
.
.
.
+
f
k
−
1
(
x
i
)
+
f
k
(
x
i
)
=
y
i
(
k
−
1
)
+
f
k
(
x
i
)
begin{aligned}y_i^{(0)}&=0quad(defaultquad value)\y_i^{(1)}=f_1(x_i)&=y_i^{(0)}+f_1(x_i)\y_i^{(2)}=f_1(x_i)+f_2(x_i)&=y_i^{(1)}+f_2(x_i)\&.\&.\&.\y_i^{(k)}=f_1(x_i)+f_2(x_i)+...+f_{k-1}(x_i)+f_k(x_i)&=y_{i}^{(k-1)}+f_k(x_i)end{aligned}
yi(0)yi(1)=f1(xi)yi(2)=f1(xi)+f2(xi)yi(k)=f1(xi)+f2(xi)+...+fk−1(xi)+fk(xi)=0(defaultvalue)=yi(0)+f1(xi)=yi(1)+f2(xi)...=yi(k−1)+fk(xi)
因此，我们可以得到：
O
b
j
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
)
+
∑
k
=
1
K
Ω
(
f
k
)
=
∑
i
=
1
n
(
y
i
,
y
^
i
(
k
−
1
)
+
f
K
(
x
i
)
)
+
∑
k
=
1
K
−
1
Ω
(
f
k
)
+
Ω
(
f
K
)
begin{aligned}Obj&=sumlimits_{i=1}^nl(y_i,hat y_i)+sumlimits_{k=1}^KΩ(f_k)\&=sumlimits_{i=1}^n(y_i,hat y_i^{(k-1)}+f_K(x_i))+sumlimits_{k=1}^{K-1}Ω(f_k)+Ω(f_K)end{aligned}
Obj=i=1∑nl(yi,y^i)+k=1∑KΩ(fk)=i=1∑n(yi,y^i(k−1)+fK(xi))+k=1∑K−1Ω(fk)+Ω(fK)
这里我们可以假设前
K
−
1
K-1
K−1棵树都已经构建完成，正要构建第
K
K
K棵树，因此
∑
k
=
1
K
−
1
Ω
(
f
k
)
sumlimits_{k=1}^{K-1}Ω(f_k)
k=1∑K−1Ω(fk)可以看为常数，因为目标函数是优化问题，往往跟常数项无关，因此我们可以不考虑，可以得到：
O
b
j
=
∑
i
=
1
n
(
y
i
,
y
^
i
(
k
−
1
)
+
f
K
(
x
i
)
)
+
Ω
(
f
K
)
Obj=sumlimits_{i=1}^n(y_i,hat y_i^{(k-1)}+f_K(x_i))+Ω(f_K)
Obj=i=1∑n(yi,y^i(k−1)+fK(xi))+Ω(fK)
在这里我们直接对目标函数进行优化比较困难，因此可以选择用泰勒展开去逼近的方法，泰勒公式如下：
f
(
x
+
Δ
x
)
=
f
(
x
)
+
f
′
(
x
)
Δ
x
+
1
2
f
′
′
(
x
)
Δ
x
2
+
.
.
.
+
f
(
n
)
(
x
)
n
!
Δ
x
n
+
R
n
(
x
)
f(x+Delta x)=f(x)+f^{'}(x)Delta x+frac12f^{''}(x)Delta x^2+...+frac{f^{(n)}(x)}{n!}Delta x^n+R_n(x)
f(x+Δx)=f(x)+f′(x)Δx+21f′′(x)Δx2+...+n!f(n)(x)Δxn+Rn(x)
其实泰勒展开到二阶项的时候对应的值已经非常逼近原来的值，即：
f
(
x
+
Δ
x
)
≈
f
(
x
)
+
f
′
(
x
)
Δ
x
+
1
2
f
′
′
(
x
)
Δ
x
2
f(x+Delta x)approx f(x)+f^{'}(x)Delta x+frac12f^{''}(x)Delta x^2
f(x+Δx)≈f(x)+f′(x)Δx+21f′′(x)Δx2
在这里我们可以将
y
^
i
(
k
−
1
)
hat y_i^{(k-1)}
y^i(k−1)看做是
x
x
x，
f
K
(
x
)
f_K(x)
fK(x)看做是
Δ
x
Delta x
Δx，那么
f
(
x
)
=
l
(
y
i
,
y
^
i
(
k
−
1
)
)
f(x)=l(y_i,hat y_i^{(k-1)})
f(x)=l(yi,y^i(k−1))，
f
(
x
+
Δ
x
)
=
l
(
y
i
,
y
^
i
(
k
−
1
)
)
+
f
K
(
x
i
)
f(x+Delta x)=l(y_i,hat y_i^{(k-1)})+f_K(x_i)
f(x+Δx)=l(yi,y^i(k−1))+fK(xi)，因此：
O
b
j
≈
∑
i
=
1
n
[
l
(
y
i
,
y
^
i
(
k
−
1
)
)
+
l
′
(
y
i
,
y
^
i
(
k
−
1
)
)
f
K
(
x
i
)
+
l
′
′
(
y
i
,
y
^
i
(
k
−
1
)
)
f
K
(
x
i
)
2
]
+
Ω
(
f
K
)
Objapprox sumlimits_{i=1}^n[l(y_i,hat y_i^{(k-1)})+l^{'}(y_i,hat y_i^{(k-1)})f_K(x_i)+l^{''}(y_i,hat y_i^{(k-1)})f_K(x_i)^2]+Ω(f_K)
Obj≈i=1∑n[l(yi,y^i(k−1))+l′(yi,y^i(k−1))fK(xi)+l′′(yi,y^i(k−1))fK(xi)2]+Ω(fK)
同样对于优化问题，在前
K
−
1
K-1
K−1棵决策树已经构建完成的情况下，
l
(
y
i
,
y
^
i
(
k
−
1
)
)
l(y_i,hat y_i^{(k-1)})
l(yi,y^i(k−1))可以看做是常数，对整体求解没有影响，因此我们可以将其忽略，同时我们设
g
i
=
l
′
(
y
i
,
y
^
i
(
k
−
1
)
)
g_i=l^{'}(y_i,hat y_i^{(k-1)})
gi=l′(yi,y^i(k−1))，
h
i
=
l
′
′
(
y
i
,
y
^
i
(
k
−
1
)
)
h_i=l^{''}(y_i,hat y_i^{(k-1)})
hi=l′′(yi,y^i(k−1))，我们可以得到：
O
b
j
≈
∑
i
=
1
n
[
g
i
f
K
(
x
i
)
+
1
2
h
i
f
K
2
(
x
i
)
]
+
Ω
(
f
K
)
Objapprox sumlimits_{i=1}^n[g_if_K(x_i)+frac{1}{2}h_if^2_K(x_i)]+Ω(f_K)
Obj≈i=1∑n[gifK(xi)+21hifK2(xi)]+Ω(fK)
我们设 q ( x i ) = j q(x_i)=j q(xi)=j为第 i i i个样本在当前决策树的第 j j j个叶子节点上， W ( q ( x i ) ) = W j W(q(x_i))=W_j W(q(xi))=Wj为第 i i i个样本在当前决策树上的值为 W j W_j Wj，同时对于同一棵决策树而言，落在同一个叶子节点上的值为一个集合，我们设落在某一个叶子节点 j j j上的样本点的集合为 I j I_j Ij，同时我们设当前决策树一共有 T T T个叶子结点。
对于决策树问题，我们对其进行的限制无非是有以下三种：
- 树的深度
- 叶子节点的个数
- 叶子节点的值
同样对于二叉树而言叶子节点的个数又可以反映出树的深度，因此我们可以对每一颗决策树进行如下约束：
Ω
(
f
k
)
=
γ
T
+
1
2
λ
∑
j
=
1
T
W
j
2
Ω(f_k)=gamma T+frac12lambdasumlimits_{j=1}^TW_j^2
Ω(fk)=γT+21λj=1∑TWj2
- 其中 γ 、 λ gamma、lambda γ、λ都是超参数，用于约束惩罚力度
因此可以得到：
O
b
j
=
∑
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
begin{aligned}Obj&=sumlimits_{i=1}^n[g_iW(q(x_i))+frac{1}{2}h_iW(q(x_i))^2]+gamma T+frac12lambdasumlimits_{j=1}^TW_j^2\&=sumlimits_{j=1}^T[sumlimits_{iin I_j}(g_i)W_j+frac12sumlimits_{iin I_j}(h_i+lambda)W_j^2]+gamma Tend{aligned}
Obj=i=1∑n[giW(q(xi))+21hiW(q(xi))2]+γT+21λj=1∑TWj2=j=1∑T[i∈Ij∑(gi)Wj+21i∈Ij∑(hi+λ)Wj2]+γT
我们的目的是使得该目标函数最小，我们设
G
j
=
∑
i
∈
I
j
(
g
i
)
G_j=sumlimits_{iin I_j}(g_i)
Gj=i∈Ij∑(gi)，
H
j
=
∑
i
∈
I
j
(
h
i
)
H_j=sumlimits_{iin I_j}(h_i)
Hj=i∈Ij∑(hi)
对于 G j W j + 1 2 H j W j 2 G_jW_j+frac12H_jW_j^2 GjWj+21HjWj2，由于 G j G_j Gj和 H j H_j Hj都可以看作是常数，因此就可以将其看做一个未知数为 W j W_j Wj的二次函数，可以得到，当 W j ∗ = − G j H j + λ W_j^*=-frac{G_j}{H_j+lambda} Wj∗=−Hj+λGj时， O b j Obj Obj取得最小值 O b j ∗ = − 1 2 ∑ j = 1 T G j 2 H j + λ + γ T Obj^*=-frac12sumlimits_{j=1}^Tfrac{G_j^2}{H_j+lambda}+gamma T Obj∗=−21j=1∑THj+λGj2+γT
这里有个大假设是我们已经知道树的形状（叶子结点的个数 T T T是个定值）
- 因此我们可以利用 O b j Obj Obj去构建决策树，而非简单利用信息熵或者基尼系数，即每分裂一个节点列举所有可能的分裂方式，选择使得 O b j Obj Obj最小的方式去分裂
