【机器学习】GBDT梯度提升树

梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT）属于Boosting家族。

在解决回归问题时，如果损失函数是均方误差损失函数则求解残差为(真实值-预测值)。但是当损失函数是其他的时候，我们用损失函数的负梯度在当前模型的值，将它作为残差的估计。对于平方损失函数，它就是所说的残差；对于一般损失函数，它是残差的近似。

对于二分类问题，提升树（注意是提升树）算法只需将adaboost算法中的基分类器限制为二类分类树即可。在损失函数是指数损失函数的时候，残差是(真实值-预测值)。不是指数损失的话，就变成GBDT，用损失函数的负梯度在当前模型的值作为残差的近似值，这是利用最速下降法的近似方法。

gbdt二分类算法流程

提升树利用加法模型与前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的，但对一般损失函数而言，往往每一步优化并不是十分容易，针对这一问题，Freidman提出了梯度提升算法，这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值作为提升树算法中的残差的近似值，拟合一个回归树，即：

则GBDT算法的一般流程是：

  • gbdt 的算法的流程？

  • gbdt 如何选择特征 ？

CART 生成的过程其实就是一个选择特征的过程。假设目前总共有 M 个特征。第一步需要从中选择出一个特征 j，做为二叉树的第一个节点。然后对特征 j 的值选择一个切分点 m。 一个样本的特征 j 的值如果小于m，则分为一类，如果大于m，则分为另外一类。如此便构建了CART 树的一个节点。其他节点的生成过程和这个是一样的。现在的问题是在每轮迭代的时候，如何选择这个特征 j,以及如何选择特征 j 的切分点 m：

  • 原始的gbdt的做法非常的暴力，首先遍历每个特征，然后对每个特征遍历它所有可能的切分点，找到最优特征 m 的最优切分点 j。
  • 如何衡量我们找到的特征 m和切分点 j 是最优的呢？先遍历训练样本的所有的特征，对于特征 j，我们遍历特征 j 所有特征值的切分点 c。找到可以让下面这个式子最小的特征 j 以及切分点c。

  • gbdt 如何用于分类？

         首先明确一点，gbdt 无论用于分类还是回归一直都是使用的CART 回归树。不会因为任务是分类任务就选用分类树，这里面的核心是因为gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的。残差相减是有意义的。

        如果选用的弱分类器是分类树，类别相减是没有意义的。上一轮输出的是样本 x 属于 A类，本一轮训练输出的是样本 x 属于 B类。 A 和 B 很多时候甚至都没有比较的意义，A 类减B类是没有意义的。

        我们具体到分类这个任务上面来，我们假设样本 X 总共有K类。来了一个样本 x，我们需要使用gbdt来判断 x 属于样本的哪一类。

                                  图 gbdt 多分类算法流程

         第一步，在训练的时候，是针对样本 X 每个可能的类都训练一个分类回归树。举例说明，目前样本有三类，也就是 K = 3。样本 x 属于第二类。那么针对该样本 x 的分类结果，其实我们可以用一个 三维向量 [0,1,0] 来表示。0表示样本不属于该类，1表示样本属于该类。由于样本已经属于第二类了，所以第二类对应的向量维度为1，其他位置为0。

       针对样本有三类的情况，我们实质上是在每轮的训练的时候是同时训练三颗树。第一颗树针对样本x的第一类，输入为（x,0）。第二颗树输入针对样本 x 的第二类，输入为（x,1）。第三颗树针对样本 x 的第三类，输入为（x，0）。

        在这里每颗树的训练过程其实就是CATR TREE 的生成过程。在此处我们参照之前的生成树的程序即可解出三颗树，以及三颗树对 x 类别的预测值f1(x),f2(x),f3(x)。那么在此类训练中，我们仿照多分类的逻辑回归 ，使用softmax 来产生概率，则属于类别 1 的概率

并且我们我们可以针对类别 1 求出残差；类别 2 求出残差；类别 3 求出残差

        然后开始第二轮训练，针对第一类 输入为, 针对第二类输入为，针对第三类输入为，继续训练出三颗树。一直迭代M轮。每轮构建 3颗树。

        所以当K =3。我们其实应该有三个式子

当训练完毕以后，新来一个样本 x1 ，我们需要预测该样本的类别的时候，便可以有这三个式子产生三个值，f1(x),f2(x),f3(x)。样本属于某个类别c的概率为

  • gbdt 通过什么方式减少误差 ？

和boosting系列一样，每次迭代都减小误差。

  • gbdt的效果相比于传统的LR，SVM效果为什么好一些 ？

1) 可以灵活处理各种类型的数据，包括连续值和离散值。而LR只能处理离散值。

2) 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。

  • gbdt 如何加速训练？

由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

  • gbdt的参数有哪些，如何调参 ？

首先，我们来看boosting框架相关的重要参数。由于GradientBoostingClassifier和GradientBoostingRegressor的参数绝大部分相同，我们下面会一起来讲，不同点会单独指出。

1) n_estimators: 也就是弱学习器的最大迭代次数，或者说最大的弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。默认是100。在实际调参的过程中，我们常常将n_estimators和下面介绍的参数learning_rate一起考虑。

2) learning_rate: 即每个弱学习器的权重缩减系数νν，也称作步长，在原理篇的正则化章节我们也讲到了，加上了正则化项，我们的强学习器的迭代公式为。ν的取值范围为0<ν≤1。对于同样的训练集拟合效果，较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参。一般来说，可以从一个小一点的ν开始调参，默认是1。

   3) subsample: 即我们在原理篇的正则化章节讲到的子采样，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间，默认是1.0，即不使用子采样。

  4) init: 即我们的初始化的时候的弱学习器，拟合对应原理篇里面的f0(x)，如果不输入，则用训练集样本来做样本集的初始化分类回归预测。否则用init参数提供的学习器做初始化分类回归预测。一般用在我们对数据有先验知识，或者之前做过一些拟合的时候，如果没有的话就不用管这个参数了。

  5) loss: 即我们GBDT算法中的损失函数。分类模型和回归模型的损失函数是不一样的。

对于分类模型，有对数似然损失函数"deviance"和指数损失函数"exponential"两者输入选择。默认是对数似然损失函数"deviance"。在原理篇中对这些分类损失函数有详细的介绍。一般来说，推荐使用默认的"deviance"。它对二元分离和多元分类各自都有比较好的优化。而指数损失函数等于把我们带到了Adaboost算法。

对于回归模型，有均方差"ls", 绝对损失"lad", Huber损失"huber"和分位数损失“quantile”。默认是均方差"ls"。一般来说，如果数据的噪音点不多，用默认的均方差"ls"比较好。如果是噪音点较多，则推荐用抗噪音的损失函数"huber"。而如果我们需要对训练集进行分段预测的时候，则采用“quantile”。

     6) alpha：这个参数只有GradientBoostingRegressor有，当我们使用Huber损失"huber"和分位数损失“quantile”时，需要指定分位数的值。默认是0.9，如果噪音点较多，可以适当降低这个分位数的值。

  • GBDT和随机森林的相同点：

  1. 都是由多棵树组成
  2. 最终的结果都是由多棵树一起决定

  • GBDT和随机森林的不同点：

  1. 组成随机森林的树可以是分类树，也可以是回归树；而GBDT只由回归树组成
  2. 组成随机森林的树可以并行生成；而GBDT只能是串行生成
  3. 对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来
  4. 随机森林对异常值不敏感，GBDT对异常值非常敏感
  5. 随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成
  6. 随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能

  • gbdt的优缺点 ？

GBDT主要的优点有：

  1. 可以灵活处理各种类型的数据，包括连续值和离散值。
  2. 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。
  3. 使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

GBDT的主要缺点有：

  1. 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

  • GBDT如何正则化

  • gbdt 如何构建特征 ？

         其实说gbdt 能够构建特征并非很准确，gbdt 本身是不能产生特征的，但是我们可以利用gbdt去产生特征的组合。在CTR预估中，工业界一般会采用逻辑回归去进行处理,在我的上一篇博文当中已经说过，逻辑回归本身是适合处理线性可分的数据，如果我们想让逻辑回归处理非线性的数据，其中一种方式便是组合不同特征，增强逻辑回归对非线性分布的拟合能力。

        长久以来，我们都是通过人工的先验知识或者实验来获得有效的组合特征，但是很多时候，使用人工经验知识来组合特征过于耗费人力，造成了机器学习当中一个很奇特的现象：有多少人工就有多少智能。关键是这样通过人工去组合特征并不一定能够提升模型的效果。所以我们的从业者或者学界一直都有一个趋势便是通过算法自动，高效的寻找到有效的特征组合。Facebook 在2014年 发表的一篇论文便是这种尝试下的产物，利用gbdt去产生有效的特征组合，以便用于逻辑回归的训练，提升模型最终的效果。

               图 ：用GBDT 构造特征

 如图所示，我们 使用 GBDT 生成了两棵树，两颗树一共有五个叶子节点。我们将样本 X 输入到两颗树当中去，样本X 落在了第一棵树的第二个叶子节点，第二颗树的第一个叶子节点，于是我们便可以依次构建一个五纬的特征向量，每一个纬度代表了一个叶子节点，样本落在这个叶子节点上面的话那么值为1，没有落在该叶子节点的话，那么值为 0.

        于是对于该样本，我们可以得到一个向量[0,1,0,1,0] 作为该样本的组合特征，和原来的特征一起输入到逻辑回归当中进行训练。实验证明这样会得到比较显著的效果提升。

  • GBDT的“梯度提升”体现在那个阶段

在构建cart树时使用了损失函数的负梯度，而不是所谓的残差=真值-预测值；实际上是一种更宽广的概念，但是在平方损失的情况下，上面等式是成立的。另外使用损失函数的梯度可以保证损失函数最小值。所以GBDT的梯度提升体现在构建cart树的所需的负梯度阶段，其利用最速下降的近似方法。

  • GBDT如何做特征选择

  • GBDT那些部分可以并行（即加速训练）

  1. 计算每个样本的负梯度； 
  2. 分裂挑选最佳特征及其分割点时，对特征计算相应的误差及均值时； 
  3. 更新每个样本的负梯度时； 
  4. 最后预测过程中，每个样本将之前的所有树的结果累加的时候。

  • GBDT与RF的区别

相同点： 

  1. GBDT与RF都是采用多棵树组合作为最终结果；这是两者共同点。 

不同点： 

  1. RF的树可以是回归树也可以是分类树，而GBDT只能是回归树。 
  2. RF中树是独立的，相互之间不影响，可以并行；而GBDT树之间有依赖，是串行。 
  3. RF最终的结果是有多棵树表决决定，而GBDT是有多棵树叠加组合最终的结果。 
  4. RF对异常值不敏感，原因是多棵树表决，而GBDT对异常值比较敏感，原因是当前的错误会延续给下一棵树。 
  5. RF是通过减少模型的方差来提高性能，而GBDT是减少模型的偏差来提高性能的。（原理之前分析过） 
  6. RF不需要进行数据预处理，即特征归一化。而GBDT则需要进行特征归一化

  • GBDT如何解决分类？

（因为不管是处理回归还是处理分类，都是用的CART回归树，参考4里很详细！）

一些题目?

For example, you should be able to describe the differences and commonalities between gradient boosted trees and random forests. 

So random forests and boosted trees are really the same models; the difference arises from how we train them.

参考：

1、梯度提升树(GBDT)原理小结

2、机器学习算法中 GBDT 和 XGBOOST 的区别有哪些？ - wepon的回答 

3、GBDT+LR算法解析及Python实现

4、机器学习算法GBDT的面试要点总结-上篇（写的都超棒！）

版权声明：本文为weixin_31866177原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。