link管理
链接快照平台
- 输入网页链接，自动生成快照
- 标签化管理网页链接
相关文章推荐
|
长情的自行车 · 回家-小红帽直播最新地址· 1 月前 · |
|
|
不爱学习的柠檬 · 基层党支部名称的规范写法是怎样的？ - ...· 2 月前 · |
|
|
骑白马的硬币 · 乾隆通宝_版别列表_钱币版别数据库_微拍堂· 4 月前 · |
|
|
暗恋学妹的煎鸡蛋 · vue3中清空对象数组的最优方法 - CSDN文库· 4 月前 · |
|
|
任性的墨镜 · 私立澄空学园高等学校 - 萌娘百科 ...· 5 月前 · |
网上有很多关于GBDT和Xgboost的文章，但是我在读的时候感觉对于提升树、GBDT和Xgboost之间的关系，以及他们和残差、梯度的关系，所以自己整理了一下，涉及的知识点比较多。Xgboost证明部分主要来源于论文，这里加入了自己的理解，以及对几者关系的说明。
在看本篇博文之前可以先看下提升树的相关内容，这样理解起来会思路更清晰。
提升树、GBDT和Xgboost的简单介绍如下：
①提升树基于残差，每一次迭代当前模型都在尽可能拟合残差；
②GBDT基于一阶导数（梯度下降法优化）；
③Xgboost基于GBDT的思想，使用了一阶和二阶导数信息（牛顿法优化，牛顿法：可参见
[优化方法] 梯度下降法、最小二乘法、牛顿法、拟牛顿法、共轭梯度法
）。
提升树、GBDT、Xgboost关系如下 （最开始的时候总是搞不懂，网上很多资料把最原始的GBDT和Xgboost都混在一起讲了）：
①提升树的思想是基于加法模型，不断拟合残差。
②GBDT和Xgboost都是基于提升树的思想。
③GBDT的全称是Gradient Boosting Decision Tree，之所以有Gradient是因为GBDT中引入了梯度作为提升树中“残差”的近似值（提升树的每次迭代都是为了使当前模型拟合残差，就是使求得的增量模型尽可能等于残差）。
④Xgboost可以说是GBDT的一种，因为其也是基于Gradient和Boosting思想，但是和原始GBDT的不同是：Xgboost中引入了二阶导数和正则化，除此之外，Xgboost的作者陈天奇博士在工程实现方面做了大量的优化策略。
一、GDBT
提升树（Boosting Tree）主要采用加法模型，主要思想是不断拟合残差（《统计学习方法》有详述）。GBDT利用了提升树的思想，是提升树的一种，其是利用梯度下降法拟合残差。
GBDT（Gradient Boosting Decision Tree）是梯度提升树，Gradient主要体现在：使用损失函数的负梯度在当前模型的值作为回归问题提升树算法的残差近似值。负梯度为：
\begin{aligned} -[\frac{\partial L(y_i, F_{m-1}(x_i)}{\partial F_{m-1}(x_i)}] \end{aligned}
−
[
∂
F
m
−
1
(
x
i
)
∂
L
(
y
i
,
F
m
−
1
(
x
i
)
]
注意：GBDT中目标函数仅仅使用了损失函数，没有加入正则化等。
为什么已经有了基于残差的回归树，还提出基于负梯度来替代残差的替代提升树？
《统计学习方法》中给出的解释是：当损失函数是平方损失和对数损失时，每一步的优化是很简单的，但是对于一般的损失函数而言，往往每一步的优化不是那么容易，使用负梯度代替残差。kaggle blog给出的解释是：
Although we can minimize this function directly,
gradient descent will let us minimize more complicated loss functions
that we can’t minimize directly.
2、梯度和残差的关系
当损失函数是平方函数时，
\begin{aligned} \theta^{(t)} = \theta^{(t-1)} - \eta \frac{\partial J}{\partial \theta^{(t-1)}} \end{aligned}
θ
(
t
)
=
θ
(
t
−
1
)
−
η
∂
θ
(
t
−
1
)
∂
J
为了最优化
F
(
x
)
=
∑
t
=
0
T
f
t
(
x
)
。因为梯度下降对应目标函数下降最快的位置，所以最好的优化情况便是每次的增量等于负梯度乘以学习率。所以在下面GBDT算法中我们可以看到，算法每次迭代的目的都是为了拟合梯度。
注意： 这里要讲明白一点：我们优化的当前模型（增量模型），其目标值是负梯度，也就是说，我们不是使用负梯度去拟合残差。而是在GBDT中，我们用负梯度的值近似充当残差的值，然后使用当前模型去拟合负梯度的值（在这个模型优化的过程中，负梯度的值就是真实的y，从下面的算法流程中也可以看到这一点）。
4、算法流程
定义GBDT的加法模型：
\begin{aligned} F(x;w)=\sum_{t=0}^Tf_t(x;w_t) = \sum_0^{T}\alpha_th^{(t)}(x;w_t) \end{aligned}
F
(
x
;
w
)
=
t
=
0
∑
T
f
t
(
x
;
w
t
)
=
0
∑
T
α
t
h
(
t
)
(
x
;
w
t
)
由上面的公式我们可以知道，最优的情况，
\hat{h}^{(t)}(x_i) =-[ \frac{\partial L(y_i, F^{(t-1)}(x_i))}{\partial F^{(t-1)}(x_i)}],i=1,2,..,N
h
^
(
t
)
(
x
i
)
=
−
[
∂
F
(
t
−
1
)
(
x
i
)
∂
L
(
y
i
,
F
(
t
−
1
)
(
x
i
)
)
]
,
i
=
1
,
2
,
.
.
,
N
2.2
拟合第
\rho^*=\mathop{\arg\min}_{\rho}\sum_{i=1}^NL(h^{(t)}(x_i),F^{(t-1)}(x_i) + \rho h^{(t)}(x_i, w^*)
ρ
∗
=
ar
g
min
ρ
i
=
1
∑
N
L
(
h
(
t
)
(
x
i
)
,
F
(
t
−
1
)
(
x
i
)
+
ρ
h
(
t
)
(
x
i
,
w
∗
)
2.4
令
\begin{aligned} Obj^{(t)} = \sum_{i=1}^{n}L(y_i, F_{t-1}(x_i) +f_{t}(x_i) )+ \Omega (f_t(x_i)) + 常数 \end{aligned}
O
b
j
(
t
)
=
i
=
1
∑
n
L
(
y
i
,
F
t
−
1
(
x
i
)
+
f
t
(
x
i
)
)
+
Ω
(
f
t
(
x
i
)
)
+
常
数
此时最优化目标函数
\begin{aligned} Obj^{(t)} = \sum_{i=1}^{n}[L(y_i, F_{t-1}(x_i)) +L'(y_i, F_{t-1}(x_i)) f_{t}(x_i) +\frac{1}{2}L''(y_i, F_{t-1}(x_i))f_t(x_i)^2]+ \Omega (f_t(x_i)) + 常数 \end{aligned}
O
b
j
(
t
)
=
i
=
1
∑
n
[
L
(
y
i
,
F
t
−
1
(
x
i
)
)
+
L
′
(
y
i
,
F
t
−
1
(
x
i
)
)
f
t
(
x
i
)
+
2
1
L
′
′
(
y
i
,
F
t
−
1
(
x
i
)
)
f
t
(
x
i
)
2
]
+
Ω
(
f
t
(
x
i
)
)
+
常
数
我们记
\begin{aligned} Obj^{(t)} = \sum_{i=1}^{n}[g_i f_{t}(x_i) +h_if_t(x_i)^2]+ \Omega (f_t(x_i)) \end{aligned}
O
b
j
(
t
)
=
i
=
1
∑
n
[
g
i
f
t
(
x
i
)
+
h
i
f
t
(
x
i
)
2
]
+
Ω
(
f
t
(
x
i
)
)
由于
\begin{aligned} \Omega (f_t(x_i)) = \gamma T + \frac{1}{2} \lambda \sum_{j=1}^Tw_j^2 \end{aligned}
Ω
(
f
t
(
x
i
)
)
=
γ
T
+
2
1
λ