stone

AdaBoost和梯度提升树GBDT
一. 加法模型adaboost算法,随机森林,提升树这些模型都可以表示如如下的形式:, 0<v<=1,...
扫描右侧二维码阅读全文
03
2019/03

AdaBoost和梯度提升树GBDT

一. 加法模型

adaboost算法,随机森林,提升树这些模型都可以表示如如下的形式:

$$G(x) = \sum_{m=1}^{M}\omega_mg_m(x)$$

对于任意一个函数, 都可以用一个多项式函数来进行逼近,这个和泰勒展开有点像。
在不同的模型中,可以看做对这个公式的不同角度的解析和分析。

最容易看出的就是随机森林模型,对于adaboost和提升树模型,下面会进行讲解。

二. Adaboost

Adaboost是一种自适应的算法。其核心思想调整数据的权重分布。需要解决权重调整和基模型如何组合的问题。对于前一个分类器分类错误的结果,提高其权重,而正确的样本则降低其权重。而模型的整合,则对于错误率较高的模型赋予较高的权重,错误率较低的模型赋予较低的权重。

与随机森林不同,AdaBoost算法的目标主要是降低模型的偏差。

算法表示如下:

  1. 初始化权重参数,$W_1$
  2. 对于第i轮训练,m = 1,2,3,。。。

    1. 对于当前权重$W_m$,训练最优分类器$g_m$
      $$g_m:x\to\{+1,-1\}$$
    2. 计算当前分类器的误差和权重
      $$err_m = \sum_{i} w_{m,i} I(y_i \neq g_m(x_i))$$

$$\alpha_m=\frac{1}{2}log\frac{1-err_m}{err_m}$$

  1. 调整权重

$$w_{m+1,i}=\frac{w_{m,i}}{Z_m}exp(-y_iw_mx_i)$$

$Z_m$为归一化因子

  1. 重复步骤2,直到达到结束条件

Adaboost可以在每一轮的学习中降低训练误差,误差是以指数速率下降的。

三. 前向分步算法

前向分步算法可以看做对Adaboost的另一分析角度。 前向分步算法从前往后进行学习,每一轮的学习都只优化一个基学习器,逐步逼近最终目标。

其核心思想是优化下面的函数:

$$\min \sum_iL(y_i, G(x))$$

对于分类问题,使用指数误差,可以推导出Adaboost算法;对于回归问题,使用平方差误差, 可以推导出残差树; 对于更一般的损失函数,则可以推导出梯度提升树。

其基本算法思路如下:
1。 初始化$G_0(x)=0$
2。 优化损失函数,得到$g_m$
$$\min_{\alpha_m,g_m} \sum_{i}L(y_i, G_{m-1}(x)+\alpha_m g_m(x))$$
3。 更新$G_m(x) = G_{m-1}(x)+\alpha_m g_m(x)$
4。 得到模型

在指数损失函数的情况下, 可以通过求导得到:

$$\alpha_m=\frac{1}{2}log\frac{1-err_m}{err_m}$$
$$w_{m+1,i}=w_{m,i}exp(-y_iw_mx_i)$$

这就等价于Adaboost算法。 这套框架没有规定损失函数的形式和基学习器的形式,所以可以套不同东西出不同的算法。

四. 梯度提升树和负梯度拟合

对于梯度提升树来说, 涉及到树节点的值得加权求和, 因此用到的是回归树。

GBDT的模型可以表示为:

$$G_m(x_i) = \sum_{m} \sum_{j} c_{m,j} I(x_i \in R_j)$$

即为每一颗树所属节点的权重和。

4.1 平方差模型

在平方差损失函数的情况下,上面的加法模型可以等价于

$$\min \sum_{i} L(r,g_m(x))$$

即基于残差计算每一步的最优函数。

算法可以表示为:
1。 初始化$G_0(x) = 0$
2。 在第m轮训练中
a。 计算残差 $r_i = y_i-G_{m-1}(x)$
b。 根据残差学习最优决策树
c。 $G_m(x) = G_{m-1}(x)+g_m(x)$

TODO:

在这里有一个问题,为什么使用残差计算的时候,没有给基分类器加权重

4.2 一般损失函数

在更为一般的情况下,采用最速梯度下降来代替残差, 每一轮训练对损失函数的负梯度方向进行优化。

$$r_{m,i} = - [ \frac{\partial L(y,f(x))}{\partial f(x)}]_{f(x) = f_{m-1}(x)} $$

同时规定每个节点的最佳拟合量为:

$$c_{m,j} = arg\min_{c} \sum_{x \in R_j} L(y,f_{m-1}(x)+c)$$

算法可以表示为:
1。 初始化$G_0(x) = 0$
2。 在第m轮训练中
a。 计算残差
$$r_{m,i} = - [ \frac{\partial L(y,f(x))}{\partial f(x)}]_{f(x) = f_{m-1}(x)} $$
b。 根据残差学习最优决策树
c。 计算这颗树上每个节点的权重$c_{m,j}$
d。 则这个学习器为
$$G_m(x) = G_{m-1}(x)+ c_{m,j}I(x\in R_{j})$$

4.3 常用的损失函数

TODO 有点难,先放一下

五. 二分类,多分类

上面对GDBT的分析都是对回归问题的,对于分类问题,需要在上面进行一点调整。

在LR模型中,在二分类问题上,实际上式用线性模型去拟合$ln\frac{p}{1-p}$。

所以可以将上面的树模型表示为:

$$p(y=1|x) = \frac{1}{1+e^{-\sum_{m}T_m(x;\xi)}}$$

损失函数用交叉熵来表示:

$$loss(p,y) = ylogp+(1-y)log(1-p)$$

代入当前的学习器F(x),则:

$$loss(F,y) = log(1+e^{F(x)})+(1-y)F(x)$$

对其求F(x)的导数,得到

$$\frac{\partial L(F(x),y)}{\partial F(x)} = y-\frac{1}{1+e^{-F(x)}} = y - p$$

所以这和回归树是一样的形式,直接计算预测和标签之间的残差进行拟合就行。

对于更为复杂的多分类问题,则对于每一个类别的概率做softmax归一化:

$$P(y=a|x) = \frac{e^{F_a(x)}}{\sum_{k}e^{F_k(x)}}$$

一样对其求导后,可以得到其也是对标签的残差进行拟合,和二分类的情况很相似。

六. 正则化

在gdbt中,使用的正则化有以下几种:

6.1 步长

在每一步的学习,模型等于$$G_m(x) = G_{m-1}(x)+vg_m(x)$$, 0<v<=1, 越小的步长,意味着更多的分类器,可以避免过拟合。

6.2 子采样 随机梯度提升树

书上说是不放回采样,和随机森林不同,一般取值0。5到0。8, 过少的采样可能导致偏差较大。

个人理解, 采样一次,然后训练一堆GBDT,然后再采样一次,从零开始训练,最后组成森林。

6.3 CART剪枝

在生成树的过程中直接控制弱分类的精度

七. 优缺点

优点:

1。 可以灵活处理各种类型的数据和缺失值
2。 调参较少
3。 使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

缺点:

后面的分类器依赖于前面的分类器,必须依次计算,难以并行

八. sklearn参数

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

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

2) learning_rate: 即每个弱学习器的权重缩减系数ν,也称作步长,在原理篇的正则化章节我们也讲到了,加上了正则化项,我们的强学习器的迭代公式为fk(x)=fk−1(x)+νhk(x)。ν的取值范围为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几乎可以用在所有的回归问题上,性能较为优秀。

题外话

生成模型的代表就是朴素贝叶斯、k近邻法,决策树

判别模型虽然没有现实意义,但是在样本数据量小的时候它的效果比生成模型要好的多,而且判别模型消耗的资源、复杂度都要比生成模型小得多

Last modification:March 3rd, 2019 at 03:41 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment