介绍GBDT (gradient boosting decision tree)的定义、训练过程、优缺点和常见的问题。

Boosting、bagging和stacking是集成学习的三种主要方法。不同于bagging方法，boosting方法通过分步迭代（stage-wise）的方式来构建模型，在迭代的每一步构建的弱学习器都是为了弥补已有模型的不足，通过弱学习器提升为 强学习器的算法。Boosting族算法的著名代表是AdaBoost 和GBDT。

定义

由于GBDT的学习过程是通过多轮迭代，每次都在上一轮训练结果的残差（如果是回归问题，使用平方误差作为loss function）的基础上进行学习（基函数的线性组合），来对数据进行分类或者回归。训练的过程是通过不断降低偏差来提高最后分类器的精度。

理解GBDT要分为两步，第一步是理解什么叫做用决策树去拟合当前模型的残差，第二步是理解为什么以及如何用损失函数的负梯度去替代当前模型的残差。

GBDT 是一种 boosting 算法。Boosting 方法训练基分类器时采用串行方式，各个基分类器之间有依赖。它的基本思路是将基分类器层层叠加，每一层在训练的时候，对前一层基分类器分错的样本，给予更高的权重。测试时，根据各层分类器的结果加权得到最后的结果。

Bagging与Boosting的串行训练方式不同，Bagging方法在训练过程中，各基分类器之间无强依赖，可以进行并行训练。

GDBT 处理分类问题

GBDT在解决分类问题时有两种办法，一个是选择指数损失函数作为损失函数，此时GBDT退化为AdaBoost算法，另一个是选择类似于逻辑回归的对数似然损失函数。（逻辑回归使用的是对数似然函数）

使用平方损失函数时候，GBDT算法的每一步在生成决策树只是拟合前面模型的残差，（y- y^）残差是梯度的一个特例。 而当损失函数是其他的形式时候，下一次迭代是使用的负梯度值。 对于一般损失函数，为了使其取得最小值，通过梯度下降算法，每次朝着损失函数的负梯度方向逐步移动，最终使得损失函数极小的方法（此方法要求损失函数可导）。

总的来说，第一颗树是由基尼系数决定的，之后所有的树的决策全是由残差来决定。

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

训练过程

How Gradient Boosting Works

Gradient boosting involves three elements:

  • A loss function to be optimized.
  • A weak learner to make predictions.
  • An additive model to add weak learners to minimize the loss function.

loss function

The loss function used depends on the type of problem being solved. It must be differentiable, but many standard loss functions are supported and you can define your own. For example, regression may use a squared error and classification may use logarithmic loss. A benefit of the gradient boosting framework is that a new boosting algorithm does not have to be derived for each loss function that may want to be used, instead, it is a generic enough framework that any differentiable loss function can be used.

log loss主要用来衡量二分类，cross entroy主要用来衡量多分类，前者是后者在二分类下的特例 交叉熵公式 (cross entroy) $- \sum _ { i = 1 } ^ { K } p _ { i } \log q _ { i }$ 其中 $p_i$ 表示真实的分布， $q_i$ 表示预测分布, $K$ 表示分类数; 当 $K =2$ 交叉熵退化成 log loss: $- [ y \log \hat { y } + (1-y)log(1 -\hat{y}) ]$

cross entroy与logloss主要用来衡量分类算法性能，因为cross entroy意义是衡量真实分布p和预测分布q的分布差异程度；mse主要用来衡量回归算法性能；

weak learner

弱分类器一般选择 CART （分类回归树） Classification And Regression Tree(CART)是决策树的一种，并且是非常重要的决策树，

Decision trees are used as the weak learner in gradient boosting. Specifically regression trees are used that output real values for splits and whose output can be added together, allowing subsequent models outputs to be added and “correct” the residuals in the predictions.

It is common to constrain the weak learners in specific ways, such as a maximum number of layers, nodes, splits or leaf nodes. This is to ensure that the learners remain weak, but can still be constructed in a greedy manner.

additive model

Trees are added one at a time, and existing trees in the model are not changed. A gradient descent procedure is used to minimize the loss when adding trees.

Traditionally, gradient descent is used to minimize a set of parameters, such as the coefficients in a regression equation or weights in a neural network. After calculating error or loss, the weights are updated to minimize that error. Instead of parameters, we have weak learner sub-models or more specifically decision trees. After calculating the loss, to perform the gradient descent procedure, we must add a tree to the model that reduces the loss (i.e. follow the gradient). We do this by parameterizing the tree, then modify the parameters of the tree and move in the right direction by (reducing the residual loss. Generally this approach is called functional gradient descent or gradient descent with functions.

GBDT

学习过程：先使用一个初始值来学习一个决策树，叶子可以得到预测的值，以及残差，然后后面的决策树是基于前面的决策树的残差进行学习，直到残差为0. 对于测试样本的预测值，就是许多决策树预测值的累加。

GBDT通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度。

损失函数：二分 log loss ，多分 交叉熵loss，回归 平方损失 弱学习器（weak learner）： 加法模型： 使用梯度下降的方式去减少loss， 当增加一个新的树 A gradient descent procedure is used to minimize the loss when adding trees.

具体说这个弱学习器， GBDT 选择特征的过程就是 CART (分类回归树)选择特征的过程。选择特征是：遍历每个特征和每个特征的所有切分点，找到最优的特征和最优的切分点。多个CART TREE 生成过程中，选择最优特征切分较多的特征就是重要的特征。

目前GBDT 的算法比较好的库是 xgboost

优缺点

优点（相对于 LR or SVM）：

  • 预测阶段计算速度快，树于树之间可以并行计算

  • 在分布稠密的数据集上，泛化能力和表达能力都很好。

  • 即使是大量数据，也可以方便的处理，相对比SVM 来说。

缺点：

  • GBDT 在高纬稀疏的数据集上，表现不如神经网络
  • GBDT 在处理文本分类特征上，相对于其他模型模型优势不如其在处理数值特征上
  • 训练过程中需要串行训练，只能在决策树内部采用一些局部并行的方式提高训练速度

常见的问题

  • 为什么GBDT要把CART回归树树分成m棵二叉树去求（每棵树只有两个叶子节点），而不是求一棵二叉树，这棵树有m+1（最多有2m个叶子节点）层呢？ 这是为了解决过拟合问题，基学习器要具有简单、高偏差和低方差的特点，因此每棵CART回归树的深度不会很深。
  • 为什么第m次学习的目标，是前m-1棵树预测值的累加和的残差？ 一方面通过分步求解，一步步逼近目标值，比一步到位要简单；另一方面每一步的残差计算其实变相地增大了被分错的实例的权重，因为被分错的实例其残差较大，而已经分对的实例的残差趋近于0。这样后面的树就能越来越专注于前面被分错的实例了。 提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，残差的意义如公式：残差 = 真实值 - 预测值 。提升树即是整个迭代过程生成的回归树的累加。
  • AdaBoost 算法和 GBDT 算法的区别 Boosting族算法的著名代表是AdaBoost，AdaBoost算法通过给已有模型预测错误的样本更高的权重，使得先前的学习器做错的训练样本在后续受到更多的关注的方式来弥补已有模型的不足。与AdaBoost算法不同，梯度提升方法在迭代的每一步构建一个能够沿着梯度最陡的方向降低损失（steepest-descent）的学习器来弥补已有模型的不足。经典的AdaBoost算法只能处理采用指数损失函数的二分类学习任务2，而梯度提升方法通过设置不同的可微损失函数可以处理各类学习任务（多分类、回归、Ranking等），应用范围大大扩展。另一方面，AdaBoost算法对异常点（outlier）比较敏感，而梯度提升算法通过引入bagging思想、加入正则项等方法能够有效地抵御训练数据中的噪音，具有更好的健壮性。这也是为什么梯度提升算法（尤其是采用决策树作为弱学习器的GBDT算法）如此流行的原因，有种观点认为GBDT是性能最好的机器学习算法，这当然有点过于激进又固步自封的味道，但通常各类机器学习算法比赛的赢家们都非常青睐GBDT算法，由此可见该算法的实力不可小觑。
  • 损失函数：adaboost 使用的是指数损失函数的算法，而gbdt 可以使用不同的可微的损失函数进行分类和回归问题

adaboost 一般是用于分类，gbt 一般用于回归。

  • 为什么是低方差？ gbdt通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度，（此处是可以证明的）。通俗的理解，方差比较低就是模型表现的稳定与否。
  • 什么是NP 问题? NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
  • Bagging 算法? Bagging算法是这样做的：每个分类器都随机从原样本中做有放回的采样，然后分别在这些采样后的样本上训练分类器，然后再把这些分类器组合起来。简单的多数投票一般就可以。其代表算法是随机森林

AdaBoost

AdaBoost，是英文”Adaptive Boosting”（自适应增强）的缩写。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

具体说来，整个Adaboost 迭代算法就3步：

  • 初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
  • 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
  • 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树。

AdaBoost 的优点：

  • 作为分类器，分类精度比较高
  • 简单的二元分类器，构造简单，结果可理解
  • 不容易发生过拟合 缺点：
  • 对异常样本敏感，异常样本在迭代过程中可能获得较高的权重，影响最终的强学习器的预测准确率。

复习总结

  1. gbdt 的优点 a. 可以灵活的处理各类数据（连续性和离散型）， 使用稠密的数据更加，对于稀疏的数据，可能LR 这些模型更加好。 b. 继承了树模型的优点： 对于异常值和缺省值有很好的处理的效果。因为是在树节点分裂，那么异常值的影响是比较小的；单独把缺省值放到一边，最后处理，可以支持对缺省值的处理 c. 大量数据也可以方便处理（相对于 svm 而言），如果说支持数据量最大的，还是 LR 缺点： a. 如果噪声很多，那么是容易过拟合； 如果在不带噪声的数据集上，分类效果不如LR 或者 SVM；现实中的数据是有点噪声，那么使用 GBDT 还是可以的。 b. 无法并行（主要是指 决策树的建立过程）

  2. gbdt 的损失函数 如果是二分类一般使用log loss，多分类使用交叉熵损失函数，回归算法使用均方误差损失函数。

  3. gbdt 核心的知识点 a. 基学习器需要足够的简单，具有高偏差和低方差，这个是为了缓解过拟合的问题 b. 通过多个分类器的线性累加求最后的预测结果，变相的增加了被分错的样本的权重（分对实例的残差是0）

  4. adaboost 和gbd的区别 a. 首先两者都是boosting提升算法。区别在于实现方式，adaboost 是分配权重，adaboost在下一轮的循环中分错的样本得到加强，分对的分类器得到加强；gbdt 是通过梯度下降的方式实现的，定义一个loss，然后分错的loss 是比较大的，然后通过减少loss间接的重视分错的样本。 b. adaboost 对于异常值比较敏感，gbdt 每一个分类器都是弱分类器，并且可以加上正则项，抵御数据中噪声 c. adaboost 损失函数只能是 指数损失函数， gbdt 可以针对不同的问题，选择合适的损失函数 d. adaboost 一般用于分类，gbt 一般用于回归