集成学习（4）boosting代表——gradient boosting与GBDT

1 从boosting到gradient boosting

（1）原理

从上一篇集成学习（3）boosting代表——Adaboost中我们从加法模型和前向分步算法的角度解释了Adaboost，可以说提升方法是一种利用加法模型与前向分歩算法实现学习的优化过程。在Adaboost中，分类问题的损失函数是指数损失函数，损失函数形式简单，每一步优化的计算（包括写出损失形式、求导求极值）也都比较简单，具体推导可见上一篇；对于回归问题，若采用平方误差损失函数，可得：

$L(y,F_{m}(x))=L(y,F_{m-1}(x)+T(x;\theta_m))=(y-F_{m-1}(x)-T(x;\theta_m))^2$

其中， $r=y-F_{m-1}(x)$ 是 $m-1$ 时的集成模型的残差，要使损失函数最小，求导可知要 $r-T(x;\theta_m)=0$ ，即需要 $T(x;\theta_m)$ 拟合上一步的残差 $r$ ，这个结论很好，如果我们不停的拟合残差，即一点点的降低loss，那不就会距离真值越来越近吗？这就是gradient boosting（梯度提升）的核心思想。

让我们回到boosting的基本思想来理解梯度提升（gradient boosting）：

boosting的思想是：先从初始训练集训练出一个弱学习器，再根据其表现对训练样本分布进行调整，使得此弱学习器预测错误的训练样本在接下来的训练中受到更多关注......

其重点在于如何调整样本分布使得错误样本更被关注，Adaboost中我们想到了使用对样本加权的方式来改变样本在下一轮训练中的重要性，gradient boosting采用什么方法呢？gradient boosting以当前的残差作为下一个弱学习器训练的目标，这样的处理可以认为使得误差大的样本受到了更多的关注，因此gradient boosting是一个一步一步向着目标前进的算法，每迈出一步时只关注当前距离目标的距离，就像我们的人生，勇敢地奔跑吧，看着山顶，不要回头，一定会离成功越来越近的！（鸡汤时刻）

喝完了鸡汤再来浇一盆冷水，上面我们关于残差啊、奔跑啊什么的讨论，似乎都是基于平方误差损失函数的，其形式非常简单，而对一般损失函数，降低loss往往并不是拟合 $y-F_{m-1}(x)$ 那么容易，怎么能做成一个更普适性的结论呢？针对这一问题，Freidman提出了gradient boosting，到这里gradient的概念才真正出现：

利用最速下降的近似方法，即利用损失函数的负梯度在当前模型的值，作为回归问题中提升树算法的残差的近似值（伪残差），拟合一个回归树。

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

为什么可以这样做呢？我们对损失函数 $L(y,F_{m-1}+T)$ 在 $F_{m-1}$ 处进行一阶泰勒展开：

$L(y,F_{m-1}+T)\approx L(y,F_{m-1})+\frac{\partial L(y,F_{m-1}+T)}{\partial F_{m-1}}T$

要让 $L(y,F_{m-1}+T)$ 最小化，在 $F_{m-1}$ 确定的情况下，只要让 $T$ 的方向与 $\frac{\partial L(y,F_{m-1}+T)}{\partial F_{m-1}}$ 相反即可，即我们上面所说的负梯度方向。

（2）gradient boosting流程

根据以上原理分析，可得gradient boosting算法的流程：

输入：训练集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ ，迭代轮数 $M$ ，损失函数 $L(y,F(x))$ ，弱学习器
输出：强学习器 $F_M(x)$

初始化模型为一个常数：

$f_0(x) =\arg\min_c \sum_{i=1}^N L(y_i,c)$

对于 $m=1,2，...,M:$

计算所有样本的伪残差：

$r_{mi}=-\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = F_{m-1}(x)} \;\;\; i=1,2,...,N$

使用新的训练数据 $\{(x_i,r_{mi})\}_{i=1}^N$ 训练一个弱学习器（如回归树） $h_m(x)$ ；

计算使当前损失函数取得极小值时的参数 $\gamma_m$ ：

$\gamma_m=arg\min_{\gamma_m}\sum_{i=1}^N L(y_i,F_{m-1}(x)+\gamma_mh_m(x))$

更新 $F_m(x)=F_{m-1}(x)+\gamma_mh_m(x)$ ；

得到强学习器 $F_M(x)$ 。

Gradient boosting是boosting中的一大类算法，其中包括：GBDT（Gradient Boosting Decision Tree）、XGBoost（eXtreme Gradient Boosting）、LightGBM （Light Gradient Boosting Machine）和CatBoost（Categorical Boosting）等，我们接下来主要讲一下非常常用且好用的GBDT。

2 从gradient boosting到GBDT

GBDT（Gradient Boosting Decision Tree，梯度提升树），顾名思义，它与gradient boosting的区别在于多了一个限定——“树”。所谓树自然是决策树，即GBDT限定弱学习器只能是CART回归树，因此每一步训练的弱学习器 $h_m(x)$ 的效果就是将全部样本点划分为了多个不重叠的区域（叶子结点），对损失函数我们没有限定，不过对回归和分类问题一般有一些常用的损失函数，以sklearn中GBDT的损失函数为例：梯度提升回归树有四种可选的损失函数，分别为：平方损失、绝对损失、huber损失、分位数损失；梯度提升分类树有两种可选的损失函数：指数损失、对数损失。（损失函数的介绍见附录）

（1）梯度提升回归树

由此我们可以改造一下gradient boosting算法的流程，得到GBDT回归的算法流程：

输入：训练集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ ，迭代轮数 $M$ ，损失函数 $L(y,F(x))$
输出：强学习器 $F_M(x)$

初始化模型为一个常数：

$f_0(x) =\arg\min_c \sum_{i=1}^N L(y_i,c)$

对于 $m=1,2，...,M:$

计算所有样本的伪残差：

$r_{mi}=-\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = F_{m-1}(x)} \;\;\; i=1,2,...,N$

使用新的训练数据 $\{(x_i,r_{mi})\}_{i=1}^N$ 训练一个CART回归树，其叶子结点为 $R_{mj},j=1,2,...,J$ ， $J$ 为叶子结点的数量；

对每个叶子结点 $j=1,2,...,J$ ，计算使当前损失函数取得极小值时的参数 $\gamma_{mj}$ ，这里的 $\gamma_{mj}$ 实际上就是每个叶子结点的取值（比如平方损失时 $\gamma_{mj}$ 是平均数，绝对损失时是中位数）：

$\gamma_{mj}=arg\min_{\gamma_{mj}}\sum_{x_i\in R_{mj}} L(y_i,F_{m-1}(x)+\gamma_{mj})$

更新 $F_m(x)=F_{m-1}(x)+\sum_{j=1}^J\gamma_{mj}I\{x_i\in R_{mj}\}$ ；

得到强学习器 $F_M(x)=f_0(x)+\sum_{m=1}^M\sum_{j=1}^J\gamma_{mj}I\{x_i\in R_{mj}\}$ 。

（2）梯度提升分类树

GBDT解决分类问题的思想与回归是一样的，都是一步步的逼近真实值，即一步步的降低loss，区别在于分类问题的真实值不是连续的，所以我们需要改变损失函数。当我们采用指数损失时，GBDT就变得跟Adaboost一样了，为什么呢？回想一下Adaboost更新样本分布的权重吧， $w_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_i\hat{y}_i )$ ，我们使用指数损失计算出来的 $r_{mi}$ 跟这个形式是一样的。

分类问题还可以使用对数损失，对于二分类来说，损失函数类似于logistic回归的损失函数：

$L(y, f(x)) = log(1+ exp(-yf(x)))\;\;\;\; y \in\{-1, +1\}$

别的方面跟回归树都是一样的，弱学习器也是CART回归树，我们据此再改造一下gradient boosting算法的流程，得到GBDT使用对数损失进行二分类的算法流程：

输入：训练集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ ，迭代轮数 $M$ ，损失函数 $L(y,F(x))=log(1+exp(-yf(x)))$
输出：强学习器 $F_M(x)$

初始化模型为一个常数：

$f_0(x) =\arg\min_c \sum_{i=1}^N log(1+e^{-yc})=\arg\min_c[ \sum_{y=1} log(1+e^{-c})+ \sum_{y=-1} log(1+e^{c})]$

求导求极小值，可得：

$f_0(x) =log\frac{P(y=1|x)}{1-P(y=1|x)}$

对于 $m=1,2，...,M:$

计算所有样本的伪残差：

$r_{mi}=-\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = F_{m-1}(x)}=\frac{y_i}{1+e^{y_if(x)}} \;\;\; i=1,2,...,N$

使用新的训练数据 $\{(x_i,r_{mi})\}_{i=1}^N$ 训练一个CART回归树，其叶子结点为 $R_{mj},j=1,2,...,J$ ， $J$ 为叶子结点的数量；

对每个叶子结点 $j=1,2,...,J$ ，计算使当前损失函数取得极小值时的参数 $\gamma_{mj}$ ：

$\gamma_{mj}=arg\min_{\gamma_{mj}}\sum_{x_i\in R_{mj}} log[1+e^{y_i(F_{m-1}(x)+\gamma_{mj})}]$

这个比较难最小化，近似为：

$\gamma_{mj} = \sum\limits_{x_i \in R_{mj}}r_{mi}\bigg / \sum\limits_{x_i \in R_{mj}}|r_{mi}|(1-|r_{mi}|)$

更新 $F_m(x)=F_{m-1}(x)+\sum_{j=1}^J\gamma_{mj}I\{x_i\in R_{mj}\}$ ；

得到强学习器 $F_M(x)=f_0(x)+\sum_{m=1}^M\sum_{j=1}^J\gamma_{mj}I\{x_i\in R_{mj}\}$ 。

这样就能得到模型拟合的类别标签数值，不过我们最终的目标是获得类别，所以我们将数值转化成类别的概率：

$P(y=1|x)=\frac{1}{1+e^{-F_M(x)}}$

$P(y= -1|x)=\frac{1}{1+e^{F_M(x)}}$

比较二者大小来确定类别即可。

（3）GBDT的正则化

GBDT中迭代次数 $M$ （决策树的个数）是一个天然的正则化参数。增大 $M$ 可以减小训练集的误差，但是 $M$ 太大会导致过拟合，通常通过测试集上的预测误差来选择M的最优值；
决策树的深度也是一个正则化参数，太深的决策树同样容易过拟合；
通过衰减率 $v$ 来进行正则化，也称为learning rate，相当于让每一棵树学习的慢一点，不要太激进，过犹不及嘛，这个方法其实在Adaboost中也在用：

经验上，使用较小的 $v$ 可以提高模型的泛化能力，但同样会需要更多的弱学习器的迭代次数，导致计算量上升，通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

随机梯度提升（Stochastic gradient boosting），让每次迭代的弱学习器都只是在不放回的随机抽样得到的训练集的子集上训练，设置一个采样比例 $f\in(0,1]$ ，选择小一些的采样比例能够增加模型的泛化能力，比例设置在在[0.5, 0.8]之间会产生比较好的结果。另外，随机抽样可以产生袋外数据，帮助我们验证模型的泛化能力。
对决策树进行剪枝，减少叶子结点数量和树的复杂度，这个跟我们在决策树中讲过的是一样的。

3 总结

GBDT预测能力强大，但想要得到很好的结果，平衡其拟合能力和泛化能力要比随机森林、Adaboost更难一些，需要耐心的调参，根据上面的内容我们也大概了解了一些重要的参数，比如迭代次数（树的数量）、衰减率、树的深度、采样比例等等，下面总结一下GBDT的优缺点吧：

优点：

在分布稠密的数据集上，泛化能力和表达能力都很好；
预测阶段计算快，树与树之间可以并行计算；
其他树模型共有的优点就不说了。

缺点：

GBDT在高维稀疏的数据集上效果不好，容易过拟合，这也是树模型的通病；
想达到很好的效果的话，需要仔细调参，训练时间长（串行训练）。

主要参考
《统计学习方法》——李航
Greedy function approximation: A gradient boosting machine. J.H. Friedman(1999).