目录
前言
机器学习相关内容现在非常流行，为了走得更远，非常需要我们有一个坚实的基础，因此，现在，开始好好复习一些经典算法，并做好算法总结。
本文介绍Boosting家族中另一个重要的算法–梯度提升树(Gradient Boosting Decision Tree，简称GBDT)。GBDT有很多简称，比如GBT（Gradient Boosting Tree），GTB（Gradient Tree Boosting）， GBRT（Gradient Boosting Regression Tree），MART（Multiple Additive Regression Tree），其实都是指的同一种算法，本文统一简称GBDT。
1. GBDT概述
GBDT也是集成学习Boosting家族的成员，但是和传统的Adaboost有很大的不同。回顾一下Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮一轮地迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。
在GBDT的迭代中，假设前一轮迭代得到的强学习器是:
f
t
−
1
(
x
)
f_{t-1}(x)
ft−1(x)，损失函数是
L
(
y
,
f
t
−
1
(
x
)
)
L(y,f_{t-1}(x))
L(y,ft−1(x))，本轮迭代的目标是找到一棵CART回归树模型的弱学习器
h
t
(
x
)
h_t(x)
ht(x)，让本轮的损失
L
(
y
,
f
t
(
x
)
=
L
(
y
,
f
t
−
1
(
x
)
+
h
t
(
x
)
)
L(y,ft(x)=L(y,f_{t−1}(x)+h_t(x))
L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到的决策树，要使样本的损失尽量变得更小。
GBDT的思想可以用一个通俗的例子来解释，假如有个人30岁，我们首先用20岁去拟合，发现损失是10岁，这时我们再用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下去，每一轮迭代，拟合的岁数误差都会减小。
从上面的例子来看这个思想还是蛮简单的，但是有个问题是这个损失的拟合不好度量，损失函数各种各样，怎么找到一种通用的拟合方法呢？
2. GBDT的负梯度拟合
前面我们介绍了GBDT的基本思路，但是没有解决损失函数拟合方法的问题。针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一棵CART回归树。第t轮的第i个样本的损失函数的负梯度表示为
r
t
i
=
−
∂
L
(
y
i
，
f
(
x
i
)
)
∂
f
(
x
i
)
f
(
x
)
=
f
t
−
1
(
x
)
r_{ti}=-{\frac{\partial L{(y_i，f(x_i))}}{\partial f(x_i)}}_{f(x)=f_{t-1}(x)}
rti=−∂f(xi)∂L(yi，f(xi))f(x)=ft−1(x)
利用
(
x
i
,
r
t
i
)
(
i
=
1
,
2
,
.
.
m
)
(x_i,r_{ti})(i=1,2,..m)
(xi,rti)(i=1,2,..m),我们可以拟合一棵CART回归树，得到第t棵回归树，其对应的叶子节点区域
R
t
j
,
j
=
1
,
2
,
.
.
,
j
R_{tj},j=1,2,..,j
Rtj,j=1,2,..,j，其中J为叶子节点的个数。
针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的输出值
c
t
j
c_{tj}
ctj，如下所示：
c
t
j
=
a
r
g
m
i
n
c
∑
x
i
∈
R
t
j
L
(
y
i
,
f
t
−
1
(
x
i
)
+
c
)
c_{tj}=argmin_c \sum_{x_i \in R_{tj} }L(y_i,f_{t-1}(x_i)+c)
ctj=argmincxi∈Rtj∑L(yi,ft−1(xi)+c)
（注意：这里的c可以理解为用来拟合之前的GBDT个体学习器学习后所剩下的残差，因此与权重系数无关。比如某个样本要拟合数字10，之前的几个GBDT学习器已经拟合到了9.5。那么我们现在要找到一个c，使当前的GBDT包含这个样本的节点的误差最小。那么这个值c在考虑节点其它样本误差的同时希望能够尽量地接近0.5，减少误差。）
这样就得到了本轮的决策树拟合函数，如下所示：
h
t
(
x
)
=
∑
j
=
1
J
c
t
j
I
(
x
∈
R
t
j
)
h_t(x)=\sum_{j=1}^Jc_{tj}I(x \in R_{tj})
ht(x)=∑j=1JctjI(x∈Rtj)
从而得到本轮最终的强学习器，表达式如下所示：
f
t
(
x
)
=
f
t
−
1
(
x
)
+
∑
j
=
1
J
c
t
j
I
(
x
∈
R
t
j
)
f_t(x)=f_{t-1}(x)+\sum_{j=1}^Jc_{tj}I(x \in R_{tj})
ft(x)=ft−1(x)+∑j=1JctjI(x∈Rtj)
通过损失函数的负梯度来拟合，找到了一种通用的拟合损失误差的方法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类和回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
3. GBDT回归算法
接下来，我们总结一下GBDT的回归算法。
因为，分类算法的输出是不连续的类别值，需要一些处理才能使用负梯度，我们在下一节讲。
输入是训练集样本
T
=
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
(
x
3
,
y
3
)
,
.
.
.
(
x
m
,
y
m
)
T={(x_1,y_1),(x_2,y_2),(x_3,y_3),...(x_m,y_m)}
T=(x1,y1),(x2,y2),(x3,y3),...(xm,ym)，最大迭代次数T，损失函数L。
输出是强学习器f(x)。
1) 初始化弱学习器
f
0
(
x
)
=
a
r
g
m
i
n
c
∑
i
=
1
m
L
(
y
i
,
c
)
f_0(x)=argmin_c \sum_{i=1}^mL(y_i,c)
f0(x)=argminci=1∑mL(yi,c)
2) 对于迭代轮数t=1,2,…,T有：
a) 对于样本i=1,2,…,m，计算负梯度
r
t
i
=
−
∂
L
(
y
i
，
f
(
x
i
)
)
∂
f
(
x
i
)
f
(
x
)
=
f
t
−
1
(
x
)
r_{ti}=-{\frac{\partial L{(y_i，f(x_i))}}{\partial f(x_i)}}_{f(x)=f_{t-1}(x)}
rti=−∂f(xi)∂L(yi，f(xi))f(x)=ft−1(x)
b) 利用
(
x
i
,
r
t
i
)
(
i
=
1
,
2
,
.
.
m
)
(x_i,r_{ti})(i=1,2,..m)
(xi,rti)(i=1,2,..m),我们可以拟合一棵CART回归树，得到第t棵回归树，其对应的叶子节点区域
R
t
j
,
j
=
1
,
2
,
.
.
,
j
R_{tj},j=1,2,..,j
Rtj,j=1,2,..,j，其中J为回归树的叶子节点的个数。
c) 对于叶子区域j=1,2,…,J，计算最佳拟合值
f
t
(
x
)
=
f
t
−
1
(
x
)
+
∑
j
=
1
J
c
t
j
I
(
x
∈
R
t
j
)
f_t(x)=f_{t-1}(x)+\sum_{j=1}^Jc_{tj}I(x \in R_{tj})
ft(x)=ft−1(x)+∑j=1JctjI(x∈Rtj)
d) 更新强学习器
f
t
(
x
)
=
f
t
−
1
(
x
)
+
∑
j
=
1
J
c
t
j
I
(
x
∈
R
t
j
)
f_t(x)=f_{t-1}(x)+\sum_{j=1}^Jc_{tj}I(x \in R_{tj})
ft(x)=ft−1(x)+∑j=1JctjI(x∈Rtj)
3) 得到强学习器f(x)的表达式：
f
(
x
)
=
f
T
(
x
)
=
f
0
(
x
)
+
∑
t
=
1
T
∑
j
=
1
J
c
t
j
I
(
x
∈
R
t
j
)
f(x)=f_T(x)=f_0(x)+\sum_{t=1}^T\sum_{j=1}^Jc_{tj}I(x \in R_{tj})
f(x)=fT(x)=f0(x)+t=1∑Tj=1∑JctjI(x∈Rtj)
4. GBDT分类算法
接下来介绍GBDT分类算法，GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致无法直接从输出类别去拟合类别输出的误差。
要解决这个问题有两种方法，一种是用指数损失函数，此时GBDT退化为Adaboost算法；另一种是使用类似于Logistic回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论使用对数似然损失函数的GBDT分类算法。对于对数似然损失函数，又有二元分类和多元分类的区别。
4.1 二元GBDT分类算法
对于二元GBDT，如果使用类似于Logistic回归的对数似然损失函数，则损失函数为：
L
(
y
,
f
(
x
)
)
=
l
o
g
(
1
+
e
x
p
(
−
y
f
(
x
)
)
)
L(y,f(x))=log(1+exp(-yf(x)))
L(y,f(x))=log(1+exp(−yf(x)))
其中y∈{-1,+1}。则此时的负梯度误差为
r
t
i
=
−
∂
L
(
y
i
，
f
(
x
i
)
)
∂
f
(
x
i
)
f
(
x
)
=
f
t
−
1
(
x
)
=
y
i
/
(
1
+
e
x
p
(
y
i
f
(
x
i
)
)
)
r_{ti}=-{\frac{\partial L{(y_i，f(x_i))}}{\partial f(x_i)}}_{f(x)=f_{t-1}(x)}=y_i/(1+exp(y_if(x_i)))
rti=−∂f(xi)∂L(yi，f(xi))f(x)=ft−1(x)=yi/(1+exp(yif(xi)))
对于生成的决策树，各个叶子节点的最佳残差拟合值为
c
t
j
=
a
r
g
m
i
n
∑
x
i
∈
R
t
j
l
o
g
(
1
+
e
x
p
(
−
y
i
(
f
t
−
1
(
x
i
)
+
c
)
)
)
c_{tj}=argmin \sum_{x_i\in R_{tj}}log(1+exp(-y_i(f_{t-1}(x_i)+c)))
ctj=argminxi∈Rtj∑log(1+exp(−yi(ft−1(xi)+c)))
由于上式比较难优化，一般使用近似值代替
c
t
j
=
∑
x
i
∈
R
i
j
r
t
i
/
∑
x
i
∈
R
t
j
∣
r
t
i
∣
(
1
−
∣
r
t
i
∣
)
c_{tj}=\sum_{x_i \in R_{ij}}r_{ti}/\sum_{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|)
ctj=∑xi∈Rijrti/∑xi∈Rtj∣rti∣(1−∣rti∣)
除了负梯度计算和叶子节点的最佳残差拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。
4.2 多元GBDT分类算法
多元GBDT要比二元GBDT复杂一些，对应的是多元Logistic回归和二元Logistic回归的复杂度差别。假设类别数为K，则此时的对数似然损失函数为：
L
(
y
,
f
(
x
)
)
=
−
∑
k
=
1
K
y
k
l
o
g
p
k
(
x
)
L(y,f(x))=-\sum_{k=1}^Ky_klogp_k(x)
L(y,f(x))=−∑k=1Kyklogpk(x)
如果样本输出类别为k，则
y
k
=
1
y_k=1
yk=1。第k类的概率
p
k
(
x
)
p_k(x)
pk(x)的表达式为：
p
k
(
x
)
=
e
x
p
(
f
k
(
x
)
)
/
∑
l
=
1
K
e
x
p
(
f
l
(
x
)
)
p_k(x)=exp(f_k(x))/\sum_{l=1}^Kexp(f_l(x))
pk(x)=exp(fk(x))/∑l=1Kexp(fl(x))
结合上面两式，可以计算出第t轮的第i个样本对应类别
l
l
l的负梯度误差为
r
t
i
l
=
−
[
∂
L
(
y
i
,
f
(
x
i
)
)
∂
f
(
x
i
)
]
f
k
(
x
)
=
f
l
,
t
−
1
,
x
=
y
i
l
−
p
l
,
t
−
1
(
x
i
)
r_{til}=-[\frac{\partial L(y_i,f(x_i))}{ \partial f(x_i)}]_{f_{k}(x)=f_{l,{t-1},x}}=y_{il}-p_{l,t-1}(x_i)
rtil=−[∂f(xi)∂L(yi,f(xi))]fk(x)=fl,t−1,x=yil−pl,t−1(xi)
观察上式可以看出，其实这里的误差就是样本i对应类别
l
l
l的真实概率和t-1轮预测概率的差值。
对于生成的决策树，各个叶子节点的最佳负梯度拟合值为
c
t
j
l
=
a
r
g
m
i
n
∑
i
=
0
m
∑
k
=
1
K
L
(
y
k
,
f
t
−
1
,
l
(
x
)
+
∑
j
=
0
J
c
j
l
I
(
x
i
∈
R
t
j
)
)
c_{tjl}=argmin\sum_{i=0}^m\sum_{k=1}^KL(y_k,f_{t-1,l(x)}+\sum_{j=0}^Jc_{jl}I(x_i \in R_{tj}))
ctjl=argmin∑i=0m∑k=1KL(yk,ft−1,l(x)+∑j=0JcjlI(xi∈Rtj))
由于上式比较难优化，一般使用近似值代替
c
t
j
l
=
K
−
1
K
∑
x
I
∈
R
t
j
l
r
t
j
l
∑
x
i
∈
R
t
i
l
∣
r
[
t
i
l
∣
(
1
−
∣
r
t
i
l
∣
)
c_{tjl}=\frac{K-1}{K}\frac{\sum_{x_I \in R_{tjl}}r_{tjl}}{\sum_{x_i \in R_{til}}|r_[til|(1-|r_{til}|)}
ctjl=KK−1∑xi∈Rtil∣r[til∣(1−∣rtil∣)∑xI∈Rtjlrtjl
除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。
5. GBDT常用损失函数
这里我们再总结一下常用的GBDT损失函数。
对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种：
a) 如果是指数损失函数，则损失函数表达式为
L
(
y
,
f
(
x
)
)
=
e
x
p
(
−
y
f
(
x
)
)
L(y,f(x))=exp(-yf(x))
L(y,f(x))=exp(−yf(x))
其负梯度计算和叶子节点的最佳负梯度拟合参见Adaboost原理篇。
b) 如果是对数损失函数，分为二元分类和多元分类两种，参见前面4.1节和4.2节。
对于回归算法，常用损失函数有如下4种：
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
b) 绝对损失，这个损失函数也很常见
L
(
y
,
f
(
x
)
)
=
∣
y
−
f
(
x
)
∣
L(y,f(x))=|y-f(x)|
L(y,f(x))=∣y−f(x)∣
对应负梯度误差为：
s
i
g
n
(
y
i
−
f
(
x
i
)
)
sign(y_i-f(x_i))
sign(yi−f(xi))
c) Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下：
L
(
y
,
f
(
x
)
)
=
{
0.5
∗
(
y
−
f
(
x
)
)
2
if
∣
y
−
f
(
x
)
∣
≤
δ
δ
(
∣
y
−
f
(
x
)
∣
−
0.5
∗
δ
)
if
∣
y
−
f
(
x
)
∣
>
δ
L(y,f(x))=\begin{cases} 0.5*(y-f(x))^2 &\text{if} |y-f(x)| \leq \delta \\ \delta (|y-f(x)|-0.5*\delta) &\text{if} |y-f(x)| > \delta \end{cases}
L(y,f(x))={0.5∗(y−f(x))2δ(∣y−f(x)∣−0.5∗δ)if∣y−f(x)∣≤δif∣y−f(x)∣>δ
对应的负梯度误差为：
r
(
y
i
,
f
(
x
i
)
)
=
{
y
i
−
f
(
x
i
)
if
∣
y
−
f
(
x
)
∣
≤
δ
δ
s
i
g
n
(
y
i
−
f
(
x
I
)
)
if
∣
y
−
f
(
x
)
∣
>
δ
r(y_i,f(x_i))=\begin{cases} y_i-f(x_i) &\text{if} |y-f(x)| \leq \delta \\ \delta sign(y_i-f(x_I)) &\text{if} |y-f(x)| > \delta \end{cases}
r(yi,f(xi))={yi−f(xi)δsign(yi−f(xI))if∣y−f(x)∣≤δif∣y−f(x)∣>δ
d) 分位数损失，它对应的是分位数回归的损失函数，表达式为:
L
(
y
,
f
(
x
)
)
=
∑
y
≥
f
(
x
)
θ
∣
y
−
f
(
x
)
∣
+
∑
y
<
f
(
x
)
(
1
−
θ
)
∣
y
−
f
(
x
)
∣
L(y,f(x))=\sum_{y \ge f(x)}\theta|y-f(x)|+\sum_{y<f(x)}(1-\theta)|y-f(x)|
L(y,f(x))=y≥f(x)∑θ∣y−f(x)∣+y<f(x)∑(1−θ)∣y−f(x)∣
其中θ为分位数，需要在回归前指定，对应的负梯度误差为：
r
(
y
i
,
f
(
x
i
)
)
=
{
θ
if
y
i
≥
f
(
x
i
)
θ
−
1
if
y
i
<
f
(
x
i
)
r(y_i,f(x_i))=\begin{cases} \theta &\text{if } y_i \geq f(x_i) \\ \theta -1 &\text {if } y_i<f(x_i) \end{cases}
r(yi,f(xi))={θθ−1if yi≥f(xi)if yi<f(xi)
对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响。
6. GBDT的正则化
和Adaboost一样，GBDT也需要进行正则化，防止过拟合。GBDT的正则化主要有三种方式。
1，类似Adaboost的正则化项，即步长（learning rate）。定义为
ν
ν
ν，对前面弱学习器的迭代
f
k
(
x
)
=
f
k
−
1
(
x
)
+
h
k
(
x
)
f_k(x)=f_{k-1}(x)+h_k(x)
fk(x)=fk−1(x)+hk(x)
如果加上正则化项，则有
f
k
(
x
)
=
f
k
−
1
(
x
)
+
v
h
k
(
x
)
f_k(x)=f_{k-1}(x)+vh_k(x)
fk(x)=fk−1(x)+vhk(x)
ν的取值范围是0<ν≤1。对于同样的训练集学习效果，较小的ν意味着需要更多的弱学习器迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
2， 按照比例进行子采样（subsample），使用该子训练样本来做模型拟合，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是有放回抽样，而这里使用的是无放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低，推荐在[0.5, 0.8]之间。
使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。GBDT的并行以及后来出现的xgBoost的并行主要是针对单棵树特征处理和选择的并行（特征排序），以及在模型完成后进行预测时的并行。
3) 对于弱学习器即CART回归树进行正则化剪枝。
7. GBDT小结
GDBT本身并不复杂，不过要吃透的话需要对集成学习的原理，决策树原理和各种损失函数有一定的了解。由于GBDT的卓越性能，只要是研究机器学习都应该掌握这个算法，包括背后的原理和应用调参方法。目前GBDT的算法比较好的库是xgboost。当然scikit-learn也可以。
最后总结一下GBDT的优缺点。
GBDT的主要优点有：
- 可以灵活处理各种类型的数据，包括连续值和离散值；
- 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
- 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如Huber损失函数和分位数（Quantile）损失函数。
GBDT的主要缺点是：
- 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
问题一：Adaboost和GBDT的区别是什么？
答：Adaboost和GBDT不一样的地方最明显的就是损失函数了。Adaboost的目标是找到一个可以使当前损失函数最小的弱分类器，具体的数学解就是偏导数等于零的解。而GBDT不同的地方是让偏导数等于零这个解不是对所有的损失函数都有效的，在Adaboost里面做分类的时候，指数函数做损失函数，这个解是可求的，但是换成一般函数怎么办呢？然后就在损失函数梯度提升树（GBDT）原理那里做一阶泰勒展开，因为展开后的方程变成了一个常数加上一阶梯度和新的弱分类器的乘积，所以梯度和弱分类器的乘积越小，损失函数就越小，因此要拿逆梯度来拟合新的弱分类器，这时候可以把弱分类器分类作为步长，让损失函数沿着梯度做逆梯度下降。至于一些正则化项的存在很大程度是为了限制步长和弱分类器的复杂度，限制弱分类器的复杂度很好理解，限制步长就是因为在逆梯度方向一步不能迈的太大。
问题二：GBDT如何减少异常点的影响？
答：主要用到了以下3种方法：1) 使用健壮的损失函数，比如Huber损失函数和分位数（Quantile）损失函数；2) 增加正则化项；3) 采用无放回的子采样。
另外，对于异常点的鲁棒性，随机森林要比GBDT好的多。主要原因是GBDT的模型在迭代过程中较远的异常点残差往往会比正常点大，导致最终建立的模型出现偏差。一般的经验是，异常点少的样本集GBDT表现更加优秀，而异常点多的样本集，随机森林表现更好。
