提升树与梯度提升树算法-阿里云开发者社区

开发者社区> 人工智能> 正文

提升树与梯度提升树算法

简介: 我们对Boosting家族的Adaboost算法做了总结,本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)做一个总结。

我们对Boosting家族的Adaboost算法做了总结,本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)做一个总结。GBDT有很多简称,有GBT(Gradient Boosting Tree), GTB(Gradient Tree Boosting ), GBRT(Gradient Boosting Regression Tree), MART(Multiple Additive Regression Tree),其实都是指的同一种算法,本文统一简称GBDT。GBDT在BAT大厂中也有广泛的应用,假如要选择3个最重要的机器学习算法的话,个人认为GBDT应该占一席之地。
我们先来看看提升树:
提升树模型实际是将多个决策树简单的叠加起来,用数学模型可表示为

$$ f_M(x) = \sum_{m=1}^M T(x;\Theta_m) $$

其中,$T(x;\Theta_m)$表示决策树,$\Theta_m$ 表示决策树的参数;$M$ 为树的个数。
针对样本$D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$,提升树模型的训练就是,选择决策树的参数$\Theta=\{\Theta_1,\Theta_2,...,\Theta_M\}$以最小化损失函数 $\sum L(y_i,f_M(x_i))$,即

$$ \arg \min_\Theta \sum_{i=1}^N L(y_i,f_M(x_i)) = \arg \min_\Theta \sum_{i=1}^N L\left(y_i, \sum_{m=1}^M T(x;\Theta_m)\right) $$

这里,损失函数用来反应“样本标签 $y_i$ ”与提升树的输出 $f_M(x_i)$ 之间的差别,这里可以选择平方误差损失函数:

$$ L(y, f(x))=\left( y-f(x) \right)^2 $$

提升树模型也可以表示为迭代过程

$$ f_m(x)=f_{m-1}(x)+T(x;\Theta_m),~ m=1,2,...,M $$

因此,提升树的训练也可以按照迭代的过程来完成,在 $m$次迭代中,生成一个新的决策树$T(x;\Theta_m)$
具体而言,首先初始化提升树 $f_0(x)=0$,第 $m$ 步确定第 $m$ 个决策树$T(x;\Theta_m)$,即选择合适的决策树参数 $\Theta_m$,使损失函数最小,即

$$ \hat{\Theta}_m = \arg \min_{\Theta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i;\Theta_m)) $$

对于上式的求解,即为提升树的关键所在。如果采用平方损失函数,则有

$$ \begin{eqnarray*} L(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m)) &=& \left[\,y_i - f_{m-1}(x_i) - T(x_i;\Theta_m)\right]^2 \\ &=& \left[\,r_{m,i} - T(x_i;\Theta_m)\right]^2 \end{eqnarray*} $$

这里, $r_{m,i}=y_i-f_{m-1}(x_i)$ 表示模型$f_{m-1}(x)$拟合数据 $(x_i,y_i)$ 的残差。
就变成了选择合适的决策树参数$\Theta_m$,使得决策树的输出 $T(x_i;\Theta_m)$与 残差 $r_{m,i}$ 的误差尽可能小。因此,可以使用 $\{(x_i,r_{m,i})\}_{i=1,2,...,N}$来作为决策树$T(x;\Theta_m)$的样本集,按照常规的决策树生成过程获得参数的最优值$\hat{\Theta}_m$。
综上,我们可以得到提升树算法如下:

image


上面我们讲了提升树,在某些时候不方便求残差,梯度提升树则是用损失函数的负梯度方向值来近似拟合残差,下面来看看具体细节:

image
image

二元GBDT分类算法
对于二分类问题,比较常用的损失函数为

$$ L(y,f(x))=\log (1+\exp (-y \cdot f(x))) \tag{12} $$

其中 $y∈{−1,+1}$,此时的负梯度误差为

$$ r_{m,i} = -\left[ \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1}(x)} = \frac{y_i}{1+\exp (y_i f_{m-1}(x_i))} $$

对于生成决策树,其叶子节点的输出值为

$$ c_{m,j} = \arg \min_c \sum_{x_i\in R_{m,j}} \log (1+\exp (-y_i (f_{m-1}(x_i) + c))) $$

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

$$ c_{m,j} =\left. \sum_{x_i\in R_{m,j}} r_{m,i} \middle / \sum_{x_i\in R_{m,j}} |r_{m,i}|(1-|r_{m,i}|) \right. $$

多元GBDT分类算法
对于多分类问题,假设类别为$ K$,一般采用的损失函数为

$$ L(y,f(x)) = - \sum_{k=1}^K y_k log p_k(x) $$

其中,如果样本输出类别为 $k$ ,则 $y_k=1$ ;$p_k(x)$ 表示模型 $f(x)$判定 $x$属于第$k$ 类的概率,其表达式为

$$ p_k(x) = \frac{\exp (f_k(x))}{ \sum_{l=1}^K \exp(f_l(x))} $$

注意此处,对于多分类问题,回归树训练时,会为每一个类别训练一个决策树。
由此,我们可以计算出第 $m$ 轮的第$i$个样本对应类别$ l$的负梯度误差为

$$ r_{m,i,l} = -\left[ \frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{m-1,l}(x)} = y_{i,l} - p_{m,l}(x_i) $$

观察上式可以看出,其实这里的误差就是样本$i$对应类别$l$ 的真实概率和$m−1$ 轮预测概率的差值。
对于生成的决策树,对应第$l$类别的决策树的叶节点输出为

$$ c_{m,l,j} = \arg \min_c \sum_{x_i \in R_{m,l,j}} L(y_{i,l}, f_{m-1,l}(x_i) + c) $$

类似的,我们用近似值代替

$$ c_{m,l,j} = \frac{K-1}{K} \frac{\sum\limits_{x_i \in R_{m,l,j}}r_{m,i,l}}{ \sum\limits_{x_i \in R_{m,l,j}} |r_{m,i,l}|(1-|r_{m,i,l}|) } $$

GBDT 的正则化

  • 第一种是和Adaboost类似的正则化项,即使用步长(learning rate),定义为 αα 。常规的提升回归树的迭代为

$$ f_m(x) = f_{m-1}(x) + T(x;\Theta_m) $$

引入正则化后,其迭代过程为

$$ f_m(x) = f_{m-1}(x) + \alpha T(x;\Theta_m) $$

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

  • 第二种正则化的方式是通过子采样比例(subsample)。取值为(0,1]。注意这里的子采样和随机森林不一样,随机森林使用的是放回抽样,而这里是不放回抽样。如果取值为1,则全部样本都使用,等于没有使用子采样。如果取值小于1,则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差,即防止过拟合,但是会增加样本拟合的偏差,因此取值不能太低。推荐在[0.5, 0.8]之间。
    使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样,程序可以通过采样分发到不同的任务去做boosting的迭代过程,最后形成新树,从而减少弱学习器难以并行学习的弱点。
  • 第三种称为 Regularized Learning Objective,将树模型的复杂度作为正则项显式地加进优化目标里,这也是XGBoost实现的独到之处。其具体实现可以参考文献[7],在这里列出其加入正则化后的优化目标

$$ L_{r}(y,f(x)) = L(y,f(x)) + \sum_{m} \Omega(T(x;\Theta_m)) \\ \mathrm{where} ~~ \Omega(T(x;\Theta_m)) = \gamma T_{leaf} + \frac12 \lambda \| w \|^2 $$

其中,$L(y,f(x))$ 为常规的损失函数;$\Omega(T(x;\Theta_m))$表示决策树的复杂度,$T_{leaf}$为树叶节点个数,$w$ 为叶节点的固定输出值$c_m$组成的向量;$γ,λ$为相应的系数。

  • 最后还有一种就是类 似DeepLearning 的 Dropout ,其具体可以参考文献[8]。通俗地讲,每次新加一棵树,这棵树要拟合的并不是之前全部树ensemble后的残差,而是随机抽取的一些树ensemble。

摘自:https://www.cnblogs.com/zengzhen94/p/8744970.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章