GBDT

在前几年的机器学习竞赛以及工作中，人们使用着各种传统算法进行调参取得性能的提升，突然有一天杀出了一种名为GBDT的算法，改变了当前的格局，该算法在不同的场景中总是能够产生很好的效果，本文就让我们来了解一下GBDT。

GBDT（Gradient Boost Decision Tree），中文名称可以直译为“梯度提升决策树”。要想弄明白GBDT具体是什么我们就要弄明白这里面的两个词语DT（Decision Tree）和GB（Gradient Boost）。

DT：CART回归树

这里需要注意的是我们使用的决策树是CART回归树，无论是我们要处理回归问题还是分类问题，我们都需要使用CART回归树，主要是因为我们的GBDT算法每次迭代要拟合的是梯度值，这是一个连续值，因此我们需要使用CART回归树。

对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

关于CART回归树的生成方式具体可以参考我们之前的文章：

GB：梯度提升

我们本文中提到的GBDT其实是提升树（Boosting Tree）的一种改进算法，我们先来看一下BT是怎样进行工作的。

Boosting Tree的流程

（1）初始化 $f_0(x)=0$

（2）对m=1,2,…,M

（a）计算残差

$r_{mi}=y_i-f_{m-1}(x_i),i=1,2,...,N$

（b）拟合残差 $r_{mi}$ 学习一个回归树，得到 $h_m(x)$

（c）更新 $f_m(x)=f_{m-1}+h_m(x)$

（3）得到回归问题提升树

$f_M(x)=\sum_{m=1}^Mh_m(x)$

对于上面的流程中残差又代表着什么呢？

假设我们前一轮迭代得到的强学习器是：

$f_{t-1}(x)$

损失函数是：

$L(y,f_{t-1}(x))$

我们本轮迭代的目标是找到一个弱学习器：

$h_t(x)$

使得本轮的损失函数最小化：

$L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))$

此时的损失采用平方损失函数时：

$L(y,f_{t-1}(x)+h_t(x))$

$y-f_{t-1}(x)-h_t(x))^2$

$r-h_t(x))^2$

此时有残差：

$r=y-f_{t-1}(x)$

举个例子来表示一下残差：

假设小明有100元，第一次我们用80元去拟合，此时的残差就是20元，第二次我们用10元去拟合剩下的残差（损失：即20元），此时的残差是10元，依次类推我们每一次都去拟合剩下的残差，对于提升树来说我们把每一次拟合的钱数加起来就是模型最终的输出结果了。

我们可以发现当我们使用损失函数为平方损失的提升树的时候，每一步的迭代过程是很简单的，但是对于其他的损失函数来说就不能很好的进行每一步的优化了，针对这一问题，Freidman提出了梯度提升（Gradient Boosting）算法，利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

负梯度的表达形式如下：

$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

GBDT回归算法的流程

输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ ， $x_i\in X \subseteq R^n$ ， $y_i\in Y \subseteq R$ ；损失函数 $L (y, f (x))$ ；

输出：回归树 $\hat{f}(x)$

（1）初始化弱学习器：

$f_0(x)=arg\underset{c}{min}\sum_{i=1}^NL(y_i,c)$

（2）对m=1,2,…,M

（a）对i=1,2,…,N，计算负梯度（残差）：

$r_{mi}=-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

（b）将a中得到的残差作为新样本的真实值，拟合一个回归树，得到第m棵树的叶子结点区域 $R_{mj}$ ， $j = 1, 2, . . ., J$ 。其中 $J$ 为回归树的叶子结点的个数。

（c）对 $j = 1, 2, . . ., J$ ，计算最佳拟合值：

$c_{mj}=arg\underset{c}{min}\sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$

（d）更新强学习器

$f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$ （I为指示函数）

（3）得到最终的学习器

$\hat{f}(x)=f_M(x)=\sum_{m=1}^{M}\sum_{j=1}^{J}c_{mj}I(x\in R_{mj})$

GBDT分类算法

从思想上看，GBDT分类算法和回归算法没有区别，但是对于分类来说我们的样本输出不是连续的值，而是离散的类别，这也导致我们无法直接从输出类别去拟合类别输出的误差。

解决这个问题的办法主要有两种，一种是利用指数损失函数，此时的GBDT也就退化成了Adaboost算法；另一种就是使用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失，下面就让我们看一下在对数似然损失函数下的二分类和多分类的GBDT算法。

GBDT二分类算法

我们使用类似于逻辑回归的对数似然函数时，损失函数为：

$L (y, f (x)) = l o g (1 + e x p (- y f (x)))$ ， $y\in\{-1,+1\}$

则此时的负梯度误差为：

$r_{mi}=-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}=\frac{y_i}{(1+exp(y_if(x_i)))}$

对于生成的决策树，我们各个叶子结点的最佳负梯度拟合值为：

$c_{mj}=arg\underset{c}{min}\sum_{x_i\in R_{mj}}log(1+exp(-y_i(f_{m-1}(x_i)+c)))$

由于上式难以优化，我们一般使用近似值代替：

$c_{mj}=\frac{\sum_{x_i\in R_{mj}}r_{mi}}{\sum_{x_i\in R_{mj}}|r_{mi}|(1-|r_{mi}|)}$

出了负梯度计算和叶子结点的最佳负梯度拟合的线性搜索，GBDT二元分类和GBDT回归算法过程相同。

GBDT多分类算法

假设类别为K，则此时我们的对数似然损失函数为：

$L(y,f(x))=-\sum_{k=1}^ky_klog(p_k(x))$

其中如果样本输出类别为k，则 $y_k=1$ 。第k类的概率 $p_k(x)$ 的表达式为：

$p_k(x)=\frac{exp(f_k(x))}{\sum_{l=1}^kexp(f_l(x))}$

集合上两式，我们可以计算出第t轮的第i个样本对应类别l的负梯度误差为：

$r_{mil}=-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{l,m-1}(x)}=y_{il}-p_{l,m-1}(x_i)$

根据上式我们就能够知道，这里得到的负梯度的误差其实就是真实概率和t-1轮预测概率的差值。

对于生成的决策树，我们各个叶子结点的最佳负梯度拟合值为：

$c_{mjl}=arg\underset{c_{jl}}{min}\sum_{i=0}^{m}\sum_{k=1}^kL(y_k,f_{m-1,l}(x)+\sum_{j=1}^{J}c_{jl}I(x_i\in R_{mjl}))$

同理我们使用近似值代替：

$c_{mjl}=\frac{K-1}{K}\frac{\sum_{x_i\in R_{mjl}}r_{mil}}{\sum_{x_i\in R_{mjl}}|r_{mil}|(1-|r_{mil}|)}$

除了负梯度计算和叶子节点的最佳负梯度拟合的线性搜索，GBDT多分类和GBDT二分类以及GBDT回归算法过程相同。

GBDT的过拟合

为了防止过拟合问题的产生，我们也需要对GBDT采取一些措施，主要的方式有以下的三种：

剪枝

剪枝是树模型中常用的防止过拟合的方法，在GBDT中同样适用。

定义步长

我们把步长定义为v，对于前面的弱学习器的迭代：

$f_k(x)=f_{k-1}(x)+h_k(x)$

如果我们加上了正则化项，则有：

$f_k(x)=f_{k-1}(x)+vh_k(x)$

v的取值范围为(0,1]，对于同样的训练集学习效果，较小的v意味着我们需要更多的弱学习器的迭代次数，通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

子采样比例

我们还可以通过子采样比例的方式来防止过拟合，取值为(0,1]，这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。

使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。