之前我们介绍过 Gradient Boosting 方法利用损失函数的负梯度(伪残差)作为拟合对象的方式,当其中的基函数采用决策树的话,就得到了梯度提升决策树 (Gradient Boosting Decision Tree, GBDT)。

  GBDT 的思想可以用一个通俗的例子解释,可以用打高尔夫球的例子形象解释,当然这也只限于回归任务,分类任务的话会退化为 Adaboost。接下来我们从回归和分类的任务上分别予以介绍。

1. GBDT 回归算法

  当我们采用的基学习器是决策树时,那么梯度提升就具象到了梯度提升决策树。先还是从一些假设开始,数据集记作:

  其中 $x_i \in \mathcal{X} \subseteq \mathcal{R}^n$,$\mathcal{X}$ 为输入空间,$y_i \in \mathcal{Y} \subseteq \mathcal{R}$,$\mathcal{Y}$ 为输出空间,损失函数为 $L(y, f(x))$,我们的目标是得到最终的回归树 $\hat { f } ( x )$。

  1)首先初始化第一个集成学习器(同时是基学习器):

  2)对于迭代轮数(基学习器个数) $t = 1,2 , \dots , M$:

   a)对每一个样本 $ i = 1,2 , \dots , m$,计算损失函数的负梯度:

   b)对 $i=1,2, \dots m$,利用 $\left(x_{i}, r_{t i}\right)$ 拟合出一颗 CART 回归树,得到第 $t$ 颗回归树,其对应的叶子节点区域为 $R_{t j}$, $j=1,2, \dots, J$,其中 $J$ 为回归树 $t$ 的叶子节点的个数。

   c)对于 $J$ 个叶子节点区域 $j=1,2, \dots, J$,计算出最佳拟合值:

   d)更新强学习器(集成学习器):

  3)得到强学习器 $f(x)$ 的表达式:

2. GBDT 分类算法

  GBDT 分类算法跟回归算法在思想上是没有什么差别的,主要因为分类算法的输出结果不是连续值,类别值在一定程度上表示不了大小差距,很难从输出类别结果中去拟合输出误差。对于这样的问题,可以采用两种方法来解决:

  1. 一个采用指数损失函数,这样 GBDT 就退化成了 Adaboost,能够解决分类的问题;
  2. 使用类似于逻辑回归的对数似然损失函数,如此可以通过结果的概率值与真实概率值的差距当做残差来拟合;

2.1 GBDT 二分类算法

  对于二元 GBDT,如果用类似于逻辑回归的对数似然损失函数,则损失函数为

  其中 $y \in \{ - 1 , + 1 \}$,则此时的负梯度误差为

  对于生成的决策树,各个叶子节点的最佳残差拟合值为

  由于上式比较难优化,我们一般使用近似值代替:

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

2.2 GBDT 多分类算法

  多元 GBDT 要比二元 GBDT 复杂一些,在于多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为 $K$,则对数似然损失函数为:

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

  结合上两式,可以计算出第 $t$ 轮的第 $i$ 个样本对应类别 $l$ 的负梯度为

  观察上式可以看出,这里的误差就是样本 $i$ 对应类别 $l$ 的真实概率和 $t-1$ 轮预测概率的差值。

  对于生成的决策树,各个叶子节点的最佳伪残差拟合值为

  由于上式比较难优化,我们一般使用近似值代替

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

3. GBDT 常见损失函数

  这里对 GBDT 常见损失函数做一个总结,对分类和回归任务分别整理。

3.1 分类任务的损失函数

  对于分类算法,其损失函数一般有对数损失函数和指数损失函数两种:

  1)如果是指数损失函数,则损失函数表达式为

  其负梯度计算和叶子节点的最佳负梯度拟合可以参看 Adaboost

  2)如果是对数损失函数,分为二元分类和多元分类两种,参看上两小节内容。

3.2 回归任务的损失函数

  1)均方差,这个是最常见的回归损失函数:

  2)绝对损失,这个损失函数也很常见

  对应的负梯度误差为:

  3)Huber 损失,它是均方差和绝对损失的折中产物,对于远离中心的异常点,采用绝对损失,而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下:

  对应的负梯度误差为:

  4)分位数损失,它对应的是分位数回归的损失函数,表达式为

  其中 $\theta$ 为分位数,需要我们在回归前指定。对应的负梯度误差为:

  对于 Huber 损失和分位数损失,主要用于健壮回归,也就是减少异常点对损失函数的影响。

4. GBDT 的正则化

  和 Adaboost 一样,我们也需要对 GBDT 进行正则化,防止过拟合。GBDT 的正则化主要有三种方式。

  1)第一种是和 Adaboost 类似的正则化项,即步长(learning rate)。定义为 $\nu$,对于前面的弱学习器的迭代

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

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

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

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

  3)第三种是对于基学习器即 CART 回归树进行正则化剪枝,可以参考之前对决策剪枝的介绍

5. 工程应用

5.1 Parameter Tuning

  调参的过程可以参考

6. 总结

GBDT 优点

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

GBDT 缺点

  1. 由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过自采样的 SGBT 来达到部分并行。
  • GBDT 需要看下如何做预测?直接采用加法模型的计算?是否有注意点?

7. 问答思考(Q & A)

7.1 比较 LR 和 GBDT,说说什么情景下 GBDT 不如 LR?

  先说说 LR 和 GBDT 的区别:

  • LR 是线性模型,可解释性强,很容易并行化,但学习能力有限,需要大量的人工特征工程
  • GBDT 是非线性模型,具有天然的特征组合优势,特征表达能力强,但是树与树之间无法并行训练,而且树模型很容易过拟合;

  当在高维稀疏特征的场景下,LR 的效果一般会比 GBDT 好!

  先看一个例子:

  假设一个二分类问题,label 为 0 和 1,特征有 100 维,如果有 1w 个样本,但其中只有 10 个正样本,而这些样本的第一个特征 $f_1$ 的值为全为 1,而其余 9990 条样本的 $f_1$ 特征都为 0(在高维稀疏的情况下这种情况很常见)。

  我们都知道在这种情况下,树模型很容易优化出一个使用 $f_1$ 特征作为重要分裂节点的树,因为这个结点直接能够将训练数据划分的很好,但是当测试的时候,却会发现效果很差,因为这个特征 $f_1$ 只是刚好偶然间跟 $y$ 拟合到了这个规律,这也是我们常说的过拟合。

  那么这种情况下,如果采用 LR 的话,应该也会出现类似过拟合的情况呀:$y = W_1\times f_1 + \dots + W_i\times f_i+\dots$,其中 $W_1$ 特别大以拟合这 10 个样本。

  🤔那么这种情况下为什么树模型会过拟合,LR 就不会呢?

  仔细想想发现,因为现在的模型普遍都会带着正则项,而 LR 等线性模型的正则项是对权重的惩罚,也就是 $W_1$ 一旦过大,惩罚就会很大,进一步压缩 $W_1$ 的值,使它不至于过大。但是,树模型则不一样,树模型的惩罚项通常为叶子节点数和深度等,而我们都知道,对于上面这种 case,树只需要一个节点就可以完美分割 9990 和 10 个样本,一个结点,最终产生的惩罚项极其之小。

  这也就是为什么在高维稀疏特征的时候,线性模型会比非线性模型好的原因了:带正则化的线性模型比较不容易对稀疏特征过拟合

7.2 RF 和 GBDT 的区别有哪些?哪个树可以更深?

  相同点:

  • 都是由多棵树组成,最终的结果都是由多棵树一起决定。

  不同点:

  • 集成学习:RF 属于 bagging 思想,而 GBDT 是 boosting 思想
  • 偏差-方差权衡:RF 不断的降低模型的方差,而 GBDT 不断的降低模型的偏差
  • 训练样本:RF 每次迭代的样本是从全部训练集中有放回抽样形成的,而 GBDT 每次使用全部样本
  • 并行性:RF 的树可以并行生成,而 GBDT 只能顺序生成(需要等上一棵树完全生成)
  • 最终结果:RF 最终是多棵树进行多数表决(回归问题是取平均),而 GBDT 是加权融合
  • 数据敏感性:RF 对异常值不敏感,而 GBDT 对异常值比较敏感
  • 泛化能力:RF 不易过拟合,而 GBDT 容易过拟合

  对于 RF 和 GBDT 哪个树可以比较深,可以从以下几个方面思考:

  • 对于机器学习来说,泛化误差可以理解为两部分,分别是偏差(bias)和方差(variance);
    • 偏差指的是算法的期望预测与真实预测之间的偏差程度,反应了模型本身的拟合能力;
    • 方差度量了同等大小的训练集的变动导致学习性能的变化,刻画了数据扰动所导致的影响。
    • 当模型越复杂时,拟合的程度就越高,模型的训练偏差就越小;但此时如果换一组数据可能模型的变化就会很大,即模型的方差很大,所以模型过于复杂的时候会导致过拟合。
  • 对于 RF 来说由于并行训练很多不同的分类器的目的就是降低这个方差(variance)。所以对于每个基学习器来说,目标就是如何降低这个偏差(bias),所以我们会采用深度很深甚至不剪枝的决策树。
  • 而对于 GBDT 来说由于利用的是残差逼近的方式,即在上一轮的基础上更加拟合原数据,所以可以保证偏差(bias),所以对于每个基分类器来说,问题就在于如何选择 variance 更小的分类器,即更简单的分类器,所以我们选择了深度很浅的决策树。

  当然,也可以直接从方差和偏差的分解,具体到均值和方差的计算角度来看,具体参考

References

  1. 图解GBDT的构造和预测过程