赞
踩
Boosting、Bagging和Stacking是集成学习(Ensemble Learning)的三种主要方法。
Boosting是一族可将弱学习器提升为强学习器的算法,不同于Bagging、Stacking方法,Boosting训练过程为串联方式,弱学习器的训练是有顺序的,每个弱学习器都会在前一个学习器的基础上进行学习,最终综合所有学习器的预测值产生最终的预测结果。
我们之前详细介绍过提升方法中的AdaBoost算法。今天,我们继续来了解下另一种提升方法—梯度提升树GBDT。
GBDT(Gradient Boosting Decision Tree),全名叫梯度提升决策树,是一种迭代的决策树算法,它通过构造一组弱的学习器(树),并把多颗决策树的结果累加起来作为最终的预测输出。该算法将决策树与集成思想进行了有效的结合。
GBDT的原理很简单:
残差(预测值与真实值之间的误差)
。注意:实际上每个决策树拟合的都是负梯度,只是当损失函数是均方损失时,负梯度刚好是残差,所以其实残差只是负梯度的一种特例而已,我们后面会详细说明。
下图是一个非常简单的帮助理解的示例,我们用GBDT去预测年龄:
梯度下降法,我们都比较熟悉。不妨思考这样一个问题,梯度下降法中,为什么在负梯度方向函数值下降最快?
我们目标就是证明负梯度方向函数值下降最快。
假设我们现在处于函数
f
(
x
)
f(x)
f(x)的一个点上,这个点的坐标为
x
⃗
=
(
x
1
,
x
2
,
.
.
.
,
x
n
)
\vec{x}=(x_1,x_2,...,x_n)
x
=(x1,x2,...,xn),此时函数值为
f
(
x
⃗
)
f(\vec{x})
f(x
)。
让我们假设一个下降的方向,这个方向是随机的,我们设这个方向是 l ⃗ = ( l 1 , l 2 , . . . , l n ) \vec{l}=(l_1,l_2,...,l_n) l =(l1,l2,...,ln),那么我们沿着 l ⃗ \vec{l} l 下降的意思就是,我们下一步将来到 f ( x ⃗ + l ⃗ ) 。 f(\vec{x}+\vec{l}) 。 f(x +l )。
根据多元函数的一阶泰勒展开公式
,我们有:
f
(
x
⃗
+
l
⃗
)
=
f
(
x
⃗
)
+
∑
k
=
1
n
∂
f
∂
x
k
l
k
+
o
(
∣
∣
x
∣
∣
n
)
f(\vec{x}+\vec{l})=f(\vec{x})+\sum_{k=1}^n \frac{\partial f}{\partial x_k}l_k + o(||x||^n)
f(x
+l
)=f(x
)+k=1∑n∂xk∂flk+o(∣∣x∣∣n)
f
(
x
⃗
+
l
⃗
)
−
f
(
x
⃗
)
f(\vec{x}+\vec{l})-f(\vec{x})
f(x
+l
)−f(x
)就是移动后函数值的变化量,也就是说,只要这个值小于零,我们的函数值就在变小。而只要我们可以证明当
l
⃗
\vec{l}
l
取到梯度的负方向时这个值小于零且绝对值最大,那么我们就证明了我们的目标。
而
f
(
x
⃗
+
l
⃗
)
−
f
(
x
⃗
)
=
∑
k
=
1
n
∂
f
∂
x
k
l
k
+
o
(
∣
∣
x
∣
∣
n
)
自变量变化值极小的时候
(
∣
∣
l
⃗
∣
∣
极小
)
,我们可以忽略
o
(
∣
∣
x
∣
∣
n
)
而f(\vec{x}+\vec{l})-f(\vec{x})=\sum_{k=1}^n \frac{\partial f}{\partial x_k}l_k + o(||x||^n)\\ 自变量变化值极小的时候(||\vec{l}|| 极小),我们可以忽略o(||x||^n)
而f(x
+l
)−f(x
)=k=1∑n∂xk∂flk+o(∣∣x∣∣n)自变量变化值极小的时候(∣∣l
∣∣极小),我们可以忽略o(∣∣x∣∣n)
我们现在仅剩的问题就是如何找到一个方向,使得
∑
k
=
1
n
∂
f
∂
x
k
l
k
\sum_{k=1}^n \frac{\partial f}{\partial x_k}l_k
∑k=1n∂xk∂flk小于零且绝对值最大。
在梯度下降法中,我们经常用 θ 表示参数。 f ( x ⃗ + l ⃗ ) = f ( x ⃗ ) + ∑ k = 1 n ∂ f ∂ x k l k + o ( ∣ ∣ x ∣ ∣ n ) 可以表示为: f ( θ k + 1 ) ≈ f ( θ k ) + ∂ f ( θ k ) ∂ θ k ( θ k + 1 − θ k ) = f ( θ k ) + ∂ f ( θ k ) ∂ θ k ∇ θ 当 ∇ θ = − g r a d f ⃗ = − ∂ f ( θ k ) ∂ θ k 时,下降最快 因此,参数迭代公式 θ k + 1 = θ k + η ∇ θ = θ k − η ∂ f ( θ k ) ∂ θ k 在梯度下降法中,我们经常用\theta表示参数。\\ f(\vec{x}+\vec{l})=f(\vec{x}) + \sum_{k=1}^n \frac{\partial f}{\partial x_k}l_k + o(||x||^n)\\ 可以表示为:f(\theta_{k+1}) \approx f(\theta_{k})+\frac{\partial f(\theta_k)}{\partial \theta_k}(\theta_{k+1}-\theta_k)\\ =f(\theta_{k})+\frac{\partial f(\theta_k)}{\partial \theta_k}\nabla\theta\\ 当\nabla\theta=-\vec{grad_f}=-\frac{\partial f(\theta_k)}{\partial \theta_k}时,下降最快 \\ 因此,参数迭代公式\theta_{k+1}=\theta_k + \eta \nabla\theta =\theta_k - \eta\frac{\partial f(\theta_k)}{\partial \theta_k} 在梯度下降法中,我们经常用θ表示参数。f(x +l )=f(x )+k=1∑n∂xk∂flk+o(∣∣x∣∣n)可以表示为:f(θk+1)≈f(θk)+∂θk∂f(θk)(θk+1−θk)=f(θk)+∂θk∂f(θk)∇θ当∇θ=−gradf =−∂θk∂f(θk)时,下降最快因此,参数迭代公式θk+1=θk+η∇θ=θk−η∂θk∂f(θk)
补充以下泰勒展开公式:
我们利用一阶泰勒展开公式,对损失函数进行泰勒展开:
在优化
L
(
y
,
F
t
(
x
)
)
L(y,F_t(x))
L(y,Ft(x))的时候:
函数更新公式:
F
t
(
x
)
=
F
t
−
1
(
x
)
−
a
t
∂
L
(
y
,
F
t
−
1
(
x
)
)
∂
F
t
−
1
(
x
)
即
T
t
(
x
)
=
−
a
t
∂
L
(
y
,
F
t
−
1
(
x
)
)
∂
F
t
−
1
(
x
)
所以需要当前的学习器来学习负梯度,这里和
G
B
D
T
中差了一个
a
。
函数更新公式:F_t(x)=F_{t-1}(x)-a_t\frac{\partial L(y,F_{t-1}(x))}{\partial F_{t-1}(x)}\\ 即T_t(x)=-a_t\frac{\partial L(y,F_{t-1}(x))}{\partial F_{t-1}(x)}\\ 所以需要当前的学习器来学习负梯度,这里和GBDT中差了一个a。
函数更新公式:Ft(x)=Ft−1(x)−at∂Ft−1(x)∂L(y,Ft−1(x))即Tt(x)=−at∂Ft−1(x)∂L(y,Ft−1(x))所以需要当前的学习器来学习负梯度,这里和GBDT中差了一个a。
当我们的损失函数为平方损失时候,
L
(
y
,
f
(
x
)
)
=
(
y
−
f
(
x
)
)
2
L(y,f(x))=(y-f(x))^2
L(y,f(x))=(y−f(x))2,此时学习器要学习的负梯度为:
G
B
D
T
中忽略
a
t
,
那么
T
t
(
x
)
=
−
∂
L
(
y
,
F
t
−
1
(
x
)
)
∂
F
t
−
1
(
x
)
这里为了求导方便,损失函数加上
1
2
=
−
∂
1
2
(
y
−
f
(
x
)
)
2
∂
f
(
x
)
f
(
x
)
=
f
t
−
1
(
x
)
=
y
−
f
t
−
1
(
x
)
GBDT中忽略a_t,那么T_t(x)=-\frac{\partial L(y,F_{t-1}(x))}{\partial F_{t-1}(x)}\\ 这里为了求导方便,损失函数加上\frac{1}{2} \\ =-\frac{\partial \frac{1}{2}(y-f(x))^2}{\partial f(x)}_{f(x)=f_{t-1}(x)}\\ =y-f_{t-1}(x)
GBDT中忽略at,那么Tt(x)=−∂Ft−1(x)∂L(y,Ft−1(x))这里为了求导方便,损失函数加上21=−∂f(x)∂21(y−f(x))2f(x)=ft−1(x)=y−ft−1(x)
而
y
−
f
t
−
1
(
x
)
y-f_{t-1}(x)
y−ft−1(x)刚好是残差,因此每个决策树拟合的都是负梯度,只是当损失函数是均方损失时,负梯度刚好是残差,所以其实残差只是负梯度的一种特例而已。
我们已经通过一阶泰勒展开
证明了负梯度方向是下降最快的方向。
我们熟悉的梯度下降法是在参数空间
中优化。对于最终的最优解
θ
∗
\theta^*
θ∗,是由初始值
θ
0
\theta_0
θ0经过T次迭代之后得到的。
设 θ 0 = − ∂ L ( θ ) ∂ θ 0 ,那么 θ ∗ 表示为 θ ∗ = ∑ t = 0 T a t ∗ [ − ∂ L ( θ ) ∂ θ ] θ = θ t − 1 [ − ∂ L ( θ ) ∂ θ ] θ = θ t − 1 表示 θ 在 θ t − 1 处泰勒展开式的一阶导数 设\theta_0= -\frac{\partial L(\theta)}{\partial \theta_0},那么\theta^*表示为 \\ \theta^*=\sum_{t=0}^T a_t * [-\frac{\partial L(\theta)}{\partial \theta}]_{\theta=\theta_{t-1}} \\ [-\frac{\partial L(\theta)}{\partial \theta}]_{\theta=\theta_{t-1}}表示\theta在\theta_{t-1}处泰勒展开式的一阶导数 设θ0=−∂θ0∂L(θ),那么θ∗表示为θ∗=t=0∑Tat∗[−∂θ∂L(θ)]θ=θt−1[−∂θ∂L(θ)]θ=θt−1表示θ在θt−1处泰勒展开式的一阶导数
在函数空间中
,我们也可以借鉴梯度下降的思想,进行最优函数的搜索。对于模型的损失函数
L
(
y
,
F
(
x
)
)
L(y,F(x))
L(y,F(x)),为了能求出最优的函数
F
∗
(
x
)
F^*(x)
F∗(x),我们首先也设置初始值
F
0
(
x
)
=
f
0
(
x
)
F_0(x)=f_0(x)
F0(x)=f0(x)。
以函数
F
(
x
)
F(x)
F(x)为一个整体,与梯度下降法的更新过程一致,假设经过T次迭代得到最优函数
F
∗
(
x
)
F^*(x)
F∗(x)
F
∗
(
x
)
=
∑
t
=
0
T
f
t
(
x
)
其中
,
f
t
(
x
)
=
a
t
[
−
∂
L
(
y
,
F
(
x
)
)
∂
F
(
x
)
]
F
(
x
)
=
F
t
−
1
(
x
)
F^*(x)=\sum_{t=0}^Tf_t(x) \\ 其中,f_t(x)=a_t[-\frac{\partial L(y,F(x))}{\partial F(x)}]_{F(x)=F_{t-1}(x)}
F∗(x)=t=0∑Tft(x)其中,ft(x)=at[−∂F(x)∂L(y,F(x))]F(x)=Ft−1(x)
可以看到,这里的梯度变量是一个函数,是在函数空间上求解,而我们以前梯度下降算法是在多维参数空间中的负梯度方向,变量是参数
。
更新函数通过当前函数的负梯度方向来修正模型,使模型更优,最后累加的模型为近似最优函数
。梯度提升和梯度下降的区别和联系:
两者都是在每一轮迭代中,利用损失函数相对于模型的负梯度方向的信息来对当前模型进行更新
只不过在梯度下降中,模型是以参数化形式表示,从而模型的更新等价于参数的更新。
而在梯度提升中,模型并不需要进行参数化表示,而是直接定义在函数空间中,从而大大扩展了可以使用的模型种类。
梯度提升Gradient Boosting是Boosting中的一大类算法,它的思想借鉴于梯度下降法,其基本原理是根据当前模型损失函数的负梯度信息来训练新加入的弱分类器
,然后将训练好的弱分类器以累加的形式结合到现有模型中。采用决策树(通常为CART树)作为弱分类器的Gradient Boosting算法被称为GBDT。
平方误差损失函数
和指数损失函数时
,每一步优化是很简单的。提升树算法中残差的近似值
,拟合一个梯度提升模型。Gradient Boosting是Boosting中的一大类算法,其中包括:GBDT(Gradient Boosting Decision Tree)、XGBoost(eXtreme Gradient Boosting)、LightGBM (Light Gradient Boosting Machine)和CatBoost(Categorical Boosting)等。
XGBoost原理可以参考知乎文章(写的相当细致):深入理解XGBoost
回归树可以利用集成学习中的Boosting框架改良升级得到提升树,提升树再经过梯度提升算法改造就可以得到GBDT算法,GBDT再进一步可以升级为XGBoost、LightGBM或者CatBoost。
当我们采用的基学习器是决策树时,那么梯度提升算法就具体到了梯度提升决策树。
GBDT算法又叫MART(Multiple Additive Regression),是一种迭代的决策树算法。
GBDT算法可以看成是 M M M棵树组成的加法模型:
回归问题的提升树算法
我们在初识GBDT
中就是使用下面的算法,所用损失函数为均方差损失。
GBDT梯度提升算法
平方误差损失函数
和指数损失函数时
,每一步优化是很简单的。《统计学习方法》中的所写梯度提升算法如下图:
上图中一棵树T(x)换成了公式表达,书中解释如下:
对于GBDT回归模型,sklearn中实现了四种损失函数
《统计学习方法》中例8.2给出一个求解回归问题的提升树模型案例。
一个更加复杂的回归问题的案例:GBDT算法原理以及实例理解
GBDT做二分类案例详解:【完善版】深入理解GBDT二分类算法
GBDT做多分类案例详解:深入理解GBDT多分类算法
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。