提升树算法理论详解

Posted by mudux on March 1, 2020

  在之前总结了Boosting里面的AdaBoost算法,这里对Boosting里面另一个重要的算法梯度提升树(Gradient Boosting Decision Tree,简称GBDT)做一个总结。

1. 提升树

1.1 提升树模型

  提升树实际采用加法模型(即基函数的线性组合)与前向分步算法。以决策树为基函数的提升方法称为提升树(boosting tree)。对分类问题决策树是二叉分类树,对回归问题决策树是二叉回归树。提升树模型可以表示为决策树的加法模型:

  其中,$T(x;\Theta_m)$表示决策树;$\Theta_m$为决策树的参数;$M$为树的个数。

1.2 提升树算法

  提升树采用前向分步算法。首先确定初始提升树$f_0(x)=0$,第$m$步的模型是

  其中,$f_{m-1}(x)$是当前模型,通过经验风险最小化确定下一棵决策树的参数$\Theta_m$:

  由于树的线性组合可以很好地拟合数据,所以提升树是一个高功能的学习算法。
  针对不同问题的提升树学习算法,其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题,用指数损失函数的分类问题,以及用一般损失函数的一般决策问题。
  对于二类分类问题,提升树算法只需将AdaBoost的基分类器限制为二叉分类树即可。
  对回归问题,假设数据集为,$X$为输入空间,$y_i\in Y\subseteq R$,$Y$为输出空间。如果将输入空间$X$划分为$J$个互不相交的区域$R_1,R_2,\cdots,R_J$,并且在每个区域上确定输出的常量$c_j$,那么树可表示为:

  其中,参数表示树的区域划分和各区域上的常数。$J$是回归树的复杂度即叶结点的个数。
  回归问题提升树使用以下前向分步算法:

  在前向分步算法的第$m$步,给定当前模型$f_{m-1}(x)$,需求解

  得到$\widehat{\Theta}_m$,即第$m$棵树的参数。
  当采用平方误差损失函数时,

  其损失变为

  这里,

  是当前模型拟合数据的残差(residual)。所以,对回归问题的提升树算法来说,只需简单地拟合当前模型的残差。
  算法1.1 (回归问题的提升树算法)
  输入:训练数据集;
  输出:提升树$f_M(x)$。

  1. 初始化$f_0(x)=0$
  2. 对$m=1,2,\cdots,M$
    • 按式(1.5)计算残差

    • 拟合残差$r_{mi}$学习一个回归树,得到$T(x;\Theta_m)$
    • 更新$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$
  3. 得到回归问题提升树

2. 梯度提升

  提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时,每一步优化是很简单的。但对一般损失函数而言,往往每一步优化并不那么容易。

2.1 GBDT的负梯度拟合

  针对这一问题,Freidman提出了梯度提升(gradient boosting)算法,这是利用最速下降法的近似方法,其关键是利用损失函数的负梯度在当前模型的值

  作为回归问题提升树算法中的残差的近似值,拟合一个回归树。
  利用$(x_i, r_{ri}),\ i=1,2,\cdots,N$,可以拟合一棵CART回归树,得到第$t$棵回归树,其对应的叶结点区域$R_{tj},\ j=1,2,\cdots,J$。其中$J$为叶结点的个数。
  针对每一个叶子结点里的样本,求出使损失函数最小,也就是拟合叶子结点最好的输出值$c_{tj}$如下:

  这样就得到了本轮的决策树拟合函数如下:

  从而本轮最终得到的强学习器的表达式如下:

  通过损失函数的负梯度来拟合,我们找到了一种通用的拟合损失误差的办法,这样无论是分类问题还是回归问题,通过其损失函数的负梯度的拟合,就可以用GBDT来解决分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

2.2 GBDT回归算法

  下面总结下GBDT的回归算法。这里先不介绍分类算法,因为分类算法的输出是不连续的类别值,需要一些处理才能使用负梯度。
  输入:训练样本集,最大迭代次数$T$,损失函数$L$。
  输出:强学习器$f(x)$。

  1. 初始化弱学习器

  2. 对迭代次数$t=1,2,\cdots,T$有:
    • 对样本$i=1,2,\cdots,N$,计算负梯度

    • 利用$(x_i,r_{ti}),\ i=1,2,\cdots,N$,拟合一棵CART回归树,得到第$t$棵回归树,其对应的叶子结点区域为$R_{tj},j=1,2,\cdots,J$。其中$J$为回归树$t$的叶子结点的个数。
    • 对叶子区域$j=1,2,\cdots,J$,计算最佳拟合值

    • 更新学习器

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

2.3 GBDT分类算法

  GBDT的分类算法从思想上和GBDT的回归算法没有区别,但是由于样本输出不是连续值,而是离散的类别,导致无法直接从输出类别去拟合类别输出的误差。
  为了解决这个问题,主要有两个方法,一个是用指数损失函数,此时GBDT退化为AdaBoost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。这里仅讨论二元分类。
  对于二元GBDT,用类似于逻辑回归的对数似然损失函数,则损失函数为

  其中。此时的负梯度误差为

  对于生成的决策树,各个叶子结点的最佳负梯度拟合值为

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

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

2.4 GBDT常用损失函数

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

  • 指数损失函数
  • 对数损失函数
    见上节

对于回归算法,常用损失函数有如下4种:

  • 均方差
  • 绝对损失

    对应负梯度误差为:

  • Huber损失
    均方差和绝对损失的折衷产物,对于远离中心的异常点,采用绝对损失,而中心附近的点采用均方差。损失函数如下:

    对应的负梯度误差为:

  • 分位数损失

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

2.5 GBDT的正则化

  和AdaBoost一样,也需要对GBDT进行正则化,防止过拟合。GBDT的正则化有三种方式。
  第一种是和AdaBoost类似的正则化项,即步长(learning rate)。定义为$v$,对于前面的弱学习器的迭代

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

  $v$的取值范围为$0 \lt v \le 1$。对于同样的训练集学习效果,较小的$v$意味着需要更多的弱学习器的迭代次数。通常用步长和最大迭代次数一起来决定算法的拟合效果。
  第二种正则化的方式是通过子采样比例(subsample)。取值为(0,1]。这里的子采样和随机森林不一样,使用的是不放回抽样。如果取值为1,则全部样本都使用,等于没有使用子采样。如果取值小于1,则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差,即防止过拟合,但是会增加样本拟合的偏差,因此取值不能太低。推荐在[0.5, 0.8]之间。
  使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样,程序可以通过采样分发到不同的任务去做boosting的迭代过程,最后形成新树,从而减少弱学习器难以并行学习的弱点。
  第三种是对于弱学习器即CART回归树进行正则化剪枝。

3. GBDT小结

 GBDT主要的优点有:

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

 GBDT的主要缺点有:

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

4. Reference

1 梯度提升树(GBDT)原理小结
2 决策树(中)
3 统计学习方法第八章-李航