GBM & GBDT详解

作者: 柠檬有点萌 | 来源:发表于2021-08-13 18:15 被阅读0次

在理解GBDT之前，我们需要知道什么是GBM，GBM的全称是Gradient Boosting Machines，它是1999年被Jerome Friedman在他的论文中提出来的，从名字中我们可以知道这个算法的关键词：G(Gradient)、B(Boosting)。

一、GBM的概念

为了理解GBM，首先我们需要知道什么是B(Boosting)：
Boosting是集成方法中的一种，集成方法的主要思想是利用一定的手段学习出多个基学习器，而且这多个基学习器要求是弱学习器，然后将多个基学习器进行组合。boosting方法通过分步迭代（stage-wise）的方式来构建模型，每一步迭代构建的弱学习器都是为了弥补已有模型的不足。

G(Gradient)是指用来最小化损失函数的方法，传统的Boosting模型，如Adaboost，最小化损失函数的方式是，每次迭代后，通过更新样本权重分布（分对的样本权重变小，分错的样本权重变大），让后一个基学习器更加关注分错的样本，这样一轮轮的迭代下去，从而达到使损失函数最小化的目标。Adaboost的损失函数是指数损失函数，所以比较好用数学推导的方式去计算每一次迭代时让损失函数达到最小值的最优解，但是其它的损失函数可能不那么容易优化，为了找到一种通用的最优化损失函数的方法，Gradient Boosting被提出来了，Gradient Boosting是指每一步迭代，都是用损失函数的负梯度来拟合弱学习器，以达到使损失函数最小化的目的，GBM 在损失函数的选择上有更大的灵活性。这和梯度下降法的思想是一样的，通过找到使损失函数下降最快的方向，一步一步逼近最小值点，大家可以参考我的另外一篇文章：‘梯度下降和牛顿法’。

二、GBM详解

我们用 $F_{M}(x)$ 来表示我们的总模型，其中第m步后的模型，可以用上一轮迭代之后的模型 $F_{m-1}(x)$ 加上本轮学习的基学习器 $h_{m}(x)$ 然后再乘以一个 $γ_{m}$ 表示， $γ_{m}$ 和梯度下降中的步长意义是一样的，表示这一步应该走多远：
$F_{m}(x)=F_{m-1}(x)+γ_{m}h_{m}(x)$
让我们来看看GBM的训练步骤（以下图片来自维基百科）

GBM训练步骤

首先初始化一个常数值 $γ$ ，该值是通过最小化损失函数 $\mathop{\arg\min} _{\gamma}\sum_{i=1}^{n}L(y_{i},\gamma)$ 求得的(上图中的第1步)；
得到一个初始值之后，因为GBM的每一步迭代都是用损失函数的负梯度来拟合弱学习器，以达到使损失函数最小化的目的，所有有了初始值之后，我们可以求得每一个样本的负梯度值，该负梯度值也叫做伪残差(上图中的2.1步)；
然后用负梯度值作为基学习器的目标 $y$ 值，用这个 $y$ 值去训练基学习器(上图中的2.2步)；
基学习器训练出来之后，我们再来求 $γ_{m}$ ，这个问题是一个一维最优化问题，通过使当前模型 $F_{m}(x)$ 的损失函数最小来求得 $γ_{m}$ (上图中的2.3步)
$\gamma_{m}=\mathop{\arg\min} _{\gamma}\sum_{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i}))$
新的模型可以用 $F_{m}(x)=F_{m-1}(x)+γ_{m}h_{m}(x)$ 表示，有了新的模型之后，又可以求出每个样本损失函数的负梯度值，然后循环训练基学习器，直到满足终止条件。

三、GBDT

GBM中最常用的基学习器是CART回归树，该类GBM算法也叫GBDT。

为什么要选择决策树做基学习器呢，因为决策树有很多优点：

决策树可以看做是if-then规则集，容易理解和解释
决策树不需要做太多的特征工程，并且它不要求任何先验假设
决策树可以很好的处理缺失值
决策树具有相当好的鲁棒性，采用避免过分拟合的方法之后尤其如此
已开发的构建决策树技术不需要昂贵的计算代价，即使训练集非常大，也可以快速建立模型

因为基学习器是决策树，所有GBDT在GBM算法的基础上做了一点修改，以更好的发挥决策树的优点。
因为是树模型，所以 $h_{m}(x)$ 可以用 $\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$ 表示，其中 $J_{m}$ 是第m个基决策树的叶子节点数， $b_{jm}$ 是每个叶子节点的值，那么原先的 $F_{m}(x)=F_{m-1}(x)+γ_{m}h_{m}(x)$ 就可以写成
$F_{m}(x)=F_{m-1}(x)+γ_{m}\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$ ，
把 $γ_{m}$ 放到求和里面去，就变成了
$F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}}γ_{jm}1_{R_{jm}}(x)$

我们来看看GBDT的训练步骤：

初始化一个常数值 $F_{0}(x)=\mathop{\arg\min} _{\gamma}\sum_{i=1}^{N}L(y_{i},\gamma)$
For $m$ = 1 to M
2.1 求出每个样本的负梯度值
$r_{im}=-\left [ \frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})} \right ]_{F(x)=F_{m-1}(x)}$
2.2 用 $\left \{ (x_{i},r_{im})\right \}_{i=1}^{n}$ 去拟合一个决策树,得到一个新的基学习器
$\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$
2.3 通过最小化损失函数 $L$ ,求得每个叶子节点对应的最优的 $γ_{jm}$
$\gamma_{jm}=\mathop{\arg\min} _{\gamma}\sum_{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma)$
2.4 更新后的模型
$F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}}γ_{jm}1_{R_{jm}}(x)$
2.5 循环直到满足终止条件。

大家可能会有一个疑问，按照上面的步骤，好像(2.1)和(2.2)没什么作用，其实(2.1)和(2.2)是用来确定树结构的，训练后树的每个叶子节点的值通过(2.3)的方式确定，有几个叶子节点，就有几个 $γ$ 值，这样每一步迭代就有多个参数可以调节来进一步改善拟合的质量，使损失函数最小化。

四、GBDT应用

不管是分类问题，还是回归问题，GBDT使用的决策树都是CART回归树，为什么回归树可以解决分类问题呢，因为GBDT基学习器拟合的是负梯度值，负梯度是一个实数，所以基学习器解决的其实是一个回归问题。

1、回归

回归问题最常见的损失函数有误差平方和、绝对误差等损失函数。

如果损失函数是误差平方和： $L(y,F(x))=(y-F(x))^{2}/2$
此时我们把它叫做LS_TreeBoost，具体实现如下：

初始化一个常数值 $F_{0}(x)= \vec{y}$ ，即 $y$ 的均值；
For $m$ = 1 to M
2.1 求出每个样本的负梯度值
$r_{im}=y_{i}-F_{m-1}(x_{i})$ 即每一步迭代基学习器都是在拟合实际值和已有模型值的残差

2.2 用 $\left \{ (x_{i},r_{im})\right \}_{i=1}^{n}$ 去拟合一个决策树,得到一个新的基学习器
$\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$
2.3 通过最小化损失函数 $L$ ,求得每个叶子节点对应的最优的每个叶子节点的值
$\gamma _{jm}=mean_{x_{i}\in R_{jm}}\left \{ y_{i}-F_{m-1}(x_{i}) \right \}$
2.4 更新后的模型
$F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}}γ_{jm}1_{R_{jm}}(x)$
2.5 循环直到满足终止条件。

如果损失函数是绝对误差： $L(y,F(x))=|y-F(x)|$
此时我们把它叫做LAD_TreeBoost，具体实现如下：

初始化一个常数值 $F_{0}(x)=median\left \{ y_{i} \right \}_{1}^n$ ，即 $y$ 的中位数
For $m$ = 1 to M
2.1 求出每个样本的负梯度值
$r_{im}=sign(y_{i}-F_{m-1}(x_{i}))$ 这意味着是用当前残差的符号去拟合基分类器

2.2 用 $\left \{ (x_{i},r_{im})\right \}_{i=1}^{n}$ 去拟合一个决策树,得到一个新的基学习器
$\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$
2.3 通过最小化损失函数 $L$ ,求得每个叶子节点对应的最优值
$\gamma _{jm}=median_{x_{i}\in R_{jm}}\left \{ y_{i}-F_{m-1}(x_{i}) \right \}$
2.4 更新后的模型
$F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}}γ_{jm}1_{R_{jm}}(x)$
2.5 循环直到满足终止条件。

2、二分类

分类问题最常见的损失函数有对数损失函数和指数损失函数。

如果损失函数为对数损失： $L(y,F(x))=\log(1+\exp(-2yF(x))$ ，
其中， $y \in \{ -1, 1 \} ，F(x)=\frac{1}{2} \log \frac{p}{1-p}$
此时我们把它叫做 $\ L_{2}$ _TreeBoost，具体实现如下：

初始化一个常数值 $F_{0}(x)=\frac{1}{2} \log \frac{1+\vec{y}}{1-\vec{y}}$ ，其中 $\vec{y}$ 是 $y$ 的均值；
For $m$ = 1 to M
2.1 求出每个样本的负梯度值
$r_{im}=2y_{i}/(1+\exp(2y_{i}F_{m-1}(x_{i})))$
2.2 用 $\left \{ (x_{i},r_{im})\right \}_{i=1}^{n}$ 去拟合一个决策树,得到一个新的基学习器
$\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$
2.3 通过最小化损失函数 $L$ ,求得每个叶子节点对应的最优的每个叶子节点的值
$\gamma _{jm}= \frac{\sum _{x_{i}\in R_{jm}} r_{im} }{\sum _{x_{i}\in R_{jm}} |r_{im}|(2- |r_{im}|) }$
2.4 更新后的模型
$F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}}γ_{jm}1_{R_{jm}}(x)$
2.5 循环直到满足终止条件。

最后应用的时候，还需要通过sigmoid函数，将输出结果转换成概率p，转换公式如下：
$p=\frac{1}{1+\exp(-2F_{M}(x))}$

上式是作者论文中关于 $L_{2}$ _TreeBoost的算法流程图，在2.1中，其实我们无法一眼看出这个负梯度值究竟是什么。
现在我们将 $y$ 改为 $y \in \{ 0, 1 \}$ ，损失函数为 $L(y,F(x))=-(y\log(p)+(1-y)\log(1-p))$ ，其中 $p=\frac{1}{1+e^{-F(x)}}$
算法流程如下：

初始化一个常数值 $F_{0}(x)= \log(\frac{\sum_{i=1}^{n}y_{i}}{\sum_{i=1}^{n}(1-y_{i})})$ ；
For $m$ = 1 to M
2.1 求出每个样本的负梯度值
$r_{im}=-\left [ \frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})} \right ]_{F(x)=F_{m-1}(x)}=y_{i}-\frac{1}{1+e^{(-F_{m-1}(x_{i}))}}$ 　　可以看出，负梯度值就是实际值和预测概率的残差
2.2 用 $\left \{ (x_{i},r_{im})\right \}_{i=1}^{n}$ 去拟合一个决策树,得到一个新的基学习器
$\sum_{j=1}^{J_{m}}b_{jm}1_{R_{jm}}(x)$
2.3 通过最小化损失函数 $L$ ,求得每个叶子节点对应的最优的每个叶子节点的值
$\gamma _{jm}= \frac{\sum _{x_{i}\in R_{jm}} r_{im} }{\sum _{x_{i}\in R_{jm}} (y_{i}-r_{im})(1- y_{i}+r_{im}) }$
2.4 更新后的模型
$F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}}γ_{jm}1_{R_{jm}}(x)$
2.5 循环直到满足终止条件。

五、GBDT分类推导

现在我们以分类问题，损失函数为对数损失函数，来推导初始化值、负梯度、叶子节点的值的由来。

已知：
$y \in \{ 0, 1 \}$ ，
损失函数为 $L(y,F(x))=-(y\log(p)+(1-y)\log(1-p))$ ，其中 $p=\frac{1}{1+e^{-F(x)}}$

1、负梯度值推导

将 $p$ 值带入 $L$ 中，得
$L(y,F(x))=-(y\log(\frac{1}{1+e^{-F(x)}})+(1-y)\log(1-\frac{1}{1+e^{-F(x)}}))$
$=y\log(1+e^{-F(x)}) - (1-y)\log(\frac{e^{-F(x)}}{1+e^{-F(x)}}))$
$=y\log(1+e^{-F(x)}) - (1-y)(\log(e^{-F(x)})- \log(1+e^{-F(x)}) )$
$=y\log(1+e^{-F(x)}) - \log(e^{-F(x)}) + \log(1+e^{-F(x)}) + y(\log(e^{-F(x)}) -y \log(1+e^{-F(x)})$
$=-yF(x)+\log(1+e^{F(x)})$

对上式求导，并取负，则得到我们的负梯度值：
$-\left [ \frac{\partial L(y,F(x))}{\partial F(x)} \right ] =y - \frac{e^{F(x)}}{1+e^{F(x)}}=y - \frac{1}{1+e^{-F(x)}}$

2、初始化值推导
我们知道，初始化值的目标是： $F_{0}(x)=\mathop{\arg\min} _{\gamma}\sum_{i=1}^{n}L(y_{i},\gamma)$
对损失函数求导，并令导数=0，则可求出最优的 $F_{0}(x)$

导数的运算法则有： $(u+v)^{'}=u^{'}+v^{'}$
由上可知，每个样本的导数（梯度）为： $-y + \frac{1}{1+e^{-F(x)}}$
加总所有样本的导数，得到总体样本的导数为： $\sum_{i=1}^{n} (-y_{i} + \frac{1}{1+e^{-F(x)}})$
令导数=0，得 $\sum_{i=1}^{n} y_{i} = \sum_{i=1}^{n}(\frac{1}{1+e^{-F(x)}})$
又因为对所有的样本，初始化的 $F(x)$ 都是一样的，所有上式可以写成 $\sum_{i=1}^{n} y_{i} = n*(\frac{1}{1+e^{-F(x)}})$
从而可得到： $F(x)= \log(\frac{\sum_{i=1}^{n}y_{i}}{\sum_{i=1}^{n}(1-y_{i})})$

3、叶子节点值
我们知道，每个叶子节点对应的最优的 $\gamma_{jm}=\mathop{\arg\min} _{\gamma}\sum_{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma)$

上式没有闭式解，我们用近似值去替代它，这里用到二阶泰勒展开式去近似：
$L(y_{i},F_{m-1}(x_{i})+\gamma)≈L(y_{i},F_{m-1}(x_{i}))+\frac{\partial L(y_{i},F_{m-1}(x_{i}))}{\partial F_{m-1}(x_{i})}\gamma+\frac{1}{2}\frac{\partial^{2} L(y_{i},F_{m-1}(x_{i}))}{\partial F_{m-1}(x_{i})^{2}}\gamma^{2}$

由于 $F_{m-1}(x_{i})$ 已知，上面的一阶导、二阶导和 $L(y_{i},F_{m-1}(x_{i}))$ 是一个常数
其中：
$\frac{\partial L(y_{i},F_{m-1}(x_{i}))}{\partial F_{m-1}(x_{i})}=\frac{1}{1+e^{-F_{m-1}(x_{i})}}-y_{i}=-r_{im}$
$\frac{\partial^{2} L(y_{i},F_{m-1}(x_{i}))}{\partial F_{m-1}(x_{i})^{2}}=(\frac{1}{1+e^{-F_{m-1}(x_{i})}}-y_{i})^{'}=\frac{1}{1+e^{-F_{m-1}(x_{i})}}(1-\frac{1}{1+e^{-F_{m-1}(x_{i})}})=(y_{i}-r_{im})(1-y_{i}+r_{im})$

上式其实就是一个一元二次方程 $y=ax²+bx+c$ ，我们知道，一元二次方程取极值的地方就是 $x=-b/2a$ ；
当 $a$ >0时，为最小值，当 $a$ <0时，为最大值；
上式 $a$ 是一个大于0的值，所以当 $x=-b/2a$ 时取到最小值
带入上式得： $\gamma=\frac{r_{im}}{(y_{i}-r_{im})(1-y_{i}+r_{im})}$
最终： $\gamma _{jm}= \frac{\sum _{x_{i}\in R_{jm}} r_{im} }{\sum _{x_{i}\in R_{jm}} (y_{i}-r_{im})(1- y_{i}+r_{im}) }$

六、GBDT的正则化

在实际应用中，为了防止GBDT过拟合，我们一般有如下处理操作：

控制迭代次数M
通常使用验证数据集上的预测误差来选择最佳值的M
对每个基学习器取一个权重 $v$ ，则学习器变成
$F_{m}(x)=F_{m-1}(x)+v*γ_{m}h_{m}(x)，　0<v≤1$
经验表明，小的学习率（ $v<0.1$ ）比没有 $v$ ，能显著的提高模型的泛化能力，但是带来的问题是提高了计算时间
随机梯度下降
每次训练基学习器的时候，随机抽取样本而不是使用全部的样本进行训练，Friedman证明了对于中小型训练集 $0.5≤f≤0.8$ 会产生较好的效果，一般情况之下，我们设置 $f=0.5$
控制叶子节点的最小样本数
对树的复杂度进行惩罚