静心学习hsy / GBDT / boosting方法(Adaboost,GBDT)

0 0

   

boosting方法(Adaboost,GBDT)

2015-11-25  静心学习h...

概述

提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效.在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类性能.

对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多.提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器.大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器.

这样,对提升方法来说,有两个问题需要回答:

一,在每一轮如何改变训练数据的权值或概率分布.

二,如何将弱分类器组合成一个强分类器.

关于第1个问题,Adaboost的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值.这样一来,那些没有得到正确分类的数据,由于其权重的加大而受到后一轮的更大关注.于是,分类问题被一系列的弱分类器"分而治之".至于第2个问题,即弱分类器的组合,Adaboost采取加权多数表决的方法.具体地,加大分类误差率小的弱分类器的权值,使其在表决中起较大作用,减小分类误差大的弱分类器的权重,使其在表决中起较小的作用.

提升方法Adaboost算法

假定给定一个二类分类的训练数据集

T={(x1,y1),(x2,y2),...,(xN,yN)}

其中,每个样本点由实例与标记组成.实例 xiχRn ,类标记 yiY={1,+1} ,X是实例空间,Y是标记集合.Adaboost利用如下算法,从训练数据中学习一系列弱分类器或基本分类器,并将这些弱分类器线性组合成为一个强分类器.

Adaboost算法流程

输入:训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)} ,其中, xiχRn ; yiY={1,+1} ;弱学习算法;

输出:最终分类器G(x).

(1)初始化训练数据的权值分布

D1=(w11,...,w1i,...,w1N),w1i=1N,i=1,2,..,N

(2)对m=1,2,...,M

(a)使用具有权值分布 Dm 的训练数据集学习,得到基本分类器

Gm(x){1,+1}

(b)计算 Gm(x) 在训练数据集上的分类误差率

em=P(Gm(xi)yi)=i=1NwmiI(Gm(xi)yi)

(c)计算 Gm(x) 的系数

am=12log1emem

这里的对数是自然对数

(d)更新训练数据集的权值分布

wm+1,i=wmiZmexp(amyiGm(xi)),i=1,2,....,N

Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N)

这里, Zm 是规范化因子

Zm=i=1Nwmiexp(amyiGm(xi))

它使 Dm 成为一个概率分布.

(3)构建基本分类器的线性组合

f(x)=m=1MamGm(x)

得到最终分类器

G(x)=sign(f(x))=sign(m=1MamGm(x))

Adaboost算法的说明

步骤(1)  假设训练数据集具有均匀的权值分布,即每个训练样本在基本分类器的学习中作用相同,这一假设保证第1步能够在原始数据上学习基本分类器 G1(x)

步骤(2)  Adaboost反复学习基本分类器,在每一轮m=1,2,...,M顺次地执行下列操作:

            (a)使用当前分布 Dm 加权的训练数据集,学习基本分类器 Gm(x) .

            (b)计算基本分类器 Gm(x) 在加权训练数据集上的分类误差率:

em=P(Gm(xi)yi)=i=1NwmiI(Gm(xi)yi)

  这里, wmi 表示第m轮中第i个实例的权值, i=1Nwmi=1 .这表明, Gm(x) 在加权的训练数据集上的分类误差率是被 Gm(x) 误分类样本的权值之和,由此可以看出数据权值分布 Dm 与基本分类器 Gm(x) 的分类误差率的关系.

(c)计算基本分类器 Gm(x) 的系数 am . am 表示 Gm(x) 在最终分类器中的重要性.当 em12 时, am0 ,并且 am 随着

em 的减小而增大,所以分类误差率越小的基本分类器在最终分类器中的作用越大.

(d)更新训练数据的权值分布为下一轮作准备.

wm+1,i={wmiZmeam,Gm(xi)=yiwmiZmeam,Gm(xi)yi

由此可知,被基本分类器 Gm(x) 误分类样本的权值得以扩大,而被正确分类样本的权值却得以缩小.两相比较,误分类样本的权值被放大 e2am=1emem 倍.因此,误分类样本在下一轮学习中起更大的作用.不改变所给的训练数据,而不断改变训练数据权值的分布,使得训练数据在基本分类器的学习中起不同的作用,这是Adaboost的一个特点.

步骤(3)  线性组合f(x)实现M个基本分类器的加权表决.系数 am 表示了基本分类器 Gm(x) 的重要性,这里,所有 am 之和并不为1.f(x)的符号决定实例的x的类,f(x)的绝对值表示分类的确信度.利用基本分类器的线性组合构建最终分类器是Adaboost的另一个特点.

Adaboost算法的解释

Adaboost算法还有另一个解释,即可以认为Adaboost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法的二类分类学习方法。

Adaboost算法的训练误差分析

Adaboost最基本的性质是它能在学习过程中不断减少训练误差,即在训练数据集上的分类误差率.关于这个问题有下面的定理:

定理1 (Adaboost的训练误差界) Adaboost算法最终分类器的训练误差界为

1Ni=1NI(G(xi)yi)1Ni=1Nexp(yif(xi))=mZm

证明G(xi)yi 时, yif(xi)<0 ,因而 exp(yif(xi))1 .由此直接推导出前半部分

后半部分的证明要用到 Zm 的定义,具体推导如下:

boost

这一定理说明,可以在每一轮选取适当的 Gm 使得 Zm 最小,从而使训练误差下降最快.

对于二分类问题,有如下结果:

定理2 (二分类问题AdaBoost的训练误差界)

mZm=m=1M[2em(1em)]=m=1M(14γ2m)exp(2m=1Mγ2m)

这里, γm=12em .

证明 Zm 的定义式以及 em=Gm(xi)yiwmi 可得:

boost1

至于不等式

m=1M(14γ2m)exp(2m=1Mγ2m)

则可先由 ex1x 在x=0的泰勒展开式推出不等式 (14γ2m)exp(2γ2m) .

推论 如果存在 γ>0 ,对所有的m有 γm>γ ,则

1Ni=1NI(G(xi)yi)exp(2Mγ2)

这表明在此条件下Adaboost的训练误差是以指数速率下降的.Adaboost算法不需要知道下界 γ .这正是Freund与Schapire设计Adaboost时所考虑的.与一些早期的算法不同,Adaboost具有适应性,即它能适应弱分类器各自的训练误差率.这也是它的名称(适应的提升)的由来,Ada是Adaptive的简写.

提升树

 提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。

提升树模型

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

fM(x)=m=1MT(x;Θm)

其中, T(x;Θm) 表示决策树; Θm 表示决策树的参数;M为树的个数.

提升树算法

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

fm(x)=fm1(x)+T(x;Θm)

其中, fm1(x) 为当前模型,通过经验风险极小化确定下一棵决策树的参数 Θm .

Θ^m=argminΘmi=1NL(yi,fm1(x)+T(x;Θm))

由于树的线性组合可以很好地拟合训练数据,即使数据中的输入与输出之间的关系很复杂也是如此,所以提升树是一个高功能的学习算法.

针对不同问题的提升树学习算法,其主要区别在于使用的损失函数不同.包括用平方误差损失函数的回归问题,用指数损失函数的分类问题,以及用一般损失函数的一般决策问题.

对于二类分类问题,提升树算法只需要将Adaboost算法的基本分类器限制为二类分类树即可,可以说这时的提升树算法是Adaboost算法的特殊情况,这里不再细述.下面叙述回归问题的提升树.

当采用平方误差损失函数时:

L(y,f(x))=(yf(x))2

其损失变为

i=1NL(yi,fm1(x)+T(x;Θm))=[yfm1(x)T(x;Θm)]2=[rT(x;Θm)]2

这里,

r=yfm1(x)

是当前模型拟合数据的残差(residual).所以,对回归问题的提升树算法来说,只需简单地拟合当前模型的残差.

这样,算法是相当简单的,现将回归问题的提升树算法描述如下.

boost2

一个例子

对于年龄预测,简单起见训练集只有4个人,A,B,C,D,他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生;C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练,会得到如下图1所示结果:

提升树

现在我们使用GBDT来做这件事,由于数据太少,我们限定叶子节点做多有两个,即每棵树都只有一个分枝,并且限定只学两棵树。我们会得到如下图2所示结果:

提升树1

在第一棵树分枝和图1一样,由于A,B年龄较为相近,C,D年龄较为相近,他们被分为两拨,每拨用平均年龄作为预测值。此时计算残差(残差的意思就是: A的预测值 + A的残差 = A的实际值), 所以A的残差就是16-15=1(注意,A的预测值是指前面所有树累加的和,这里前面只有一棵树所以直接是15,如果还有树则需要都累加起来作为A的预测 值)。进而得到A,B,C,D的残差分别为-1,1,-1,1。然后我们拿残差替代A,B,C,D的原值,到第二棵树去学习,如果我们的预测值和它们的残 差相等,则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的,第二棵树只有两个值1和-1,直接分成两个节点。此时 所有人的残差都是0,即每个人都得到了真实的预测值。

换句话说,现在A,B,C,D的预测值都和真实年龄一致了.:

A: 14岁高一学生,购物较少,经常问学长问题;预测年龄A = 15 – 1 = 14

B: 16岁高三学生;购物较少,经常被学弟问问题;预测年龄B = 15 + 1 = 16

C: 24岁应届毕业生;购物较多,经常问师兄问题;预测年龄C = 25 – 1 = 24

D: 26岁工作两年员工;购物较多,经常被师弟问问题;预测年龄D = 25 + 1 = 26

(此例子摘自http://blog.csdn.net/w28971023/article/details/8240756)

梯度提升决策树(Gradient boosting decision tree,GBDT)

回归

对于损失函数

L(y,f(x))=(yf(x))2

我们把f(x)换作z,那么损失函数L(z)就是一个关于z的函数,取什么样的z使损失函数最小,这是一个最简单的优化问题,通常我们通过梯度下降的方式来求解,也就是:

znew=zold+aL(z)z

这个式子是不是跟提升树的前向分布算法的式子很像:

fm(x)=fm1(x)+T(x;Θm)

所以,我们让 T(x;Θm) 去拟合梯度的话,算法也是在逐渐优化的.求极小值就是负梯度方向:

[L(yi,f(xi))f(xi)]f(xi)=fm1(xi)

不同的损失函数会有不同的梯度式子:

boost3

(从上面的讲解来看这个跟上面的提升树拟合残差很想,这不过这里换成梯度,拟合梯度,有的地方叫这里的梯度为伪残差)

分类

在分类问题中,有一个很重要的内容叫做Multi-Class Logistic,也就是多分类的Logistic问题,它适用于那些类别数>2的问题,并且在分类结果中,样本x不是一定只属于某一个类可以得到样本x分别属于多个类的概率(也可以说样本x的估计y符合某一个几何分布),这实际上是属于Generalized Linear Model中讨论的内容,这里就先不谈了,以后有机会再用一个专门的章节去做吧。这里就用一个结论:如果一个分类问题符合几何分布,那么就可以用Logistic变换来进行之后的运算。

假设对于一个样本x,它可能属于K个分类,其估计值分别为F1(x)…FK(x),Logistic变换如下,logistic变换是一个平滑且将数据规范化(使得向量的长度为1)的过程,结果为属于类别k的概率pk(x),

gbdt

对于Logistic变换后的结果,损失函数为:

gbdt1

其中,yk为输入的样本数据的估计值,当一个样本x属于类别k时,yk = 1,否则yk = 0。
将Logistic变换的式子带入损失函数,并且对其求导,可以得到损失函数的梯度:

gbdt2

上面说的比较抽象,下面举个例子:
假设输入数据x可能属于5个分类(分别为1,2,3,4,5),训练数据中,x属于类别3,则y = (0, 0, 1, 0, 0),假设模型估计得到的F(x) = (0, 0.3, 0.6, 0, 0),则经过Logistic变换后的数据p(x) = (0.16,0.21,0.29,0.16,0.16),y - p得到梯度g:(-0.16, -0.21, 0.71, -0.16, -0.16)。观察这里可以得到一个比较有意思的结论:
假设gk为样本当某一维(某一个分类)上的梯度:
gk>0时,越大表示其在这一维上的概率p(x)越应该提高,比如说上面的第三维的概率为0.29,就应该提高,属于应该往“正确的方向”前进
越小表示这个估计越“准确”
gk<0时,越小,负得越多表示在这一维上的概率应该降低,比如说第二维0.21就应该得到降低。属于应该朝着“错误的反方向”前进
越大,负得越少表示这个估计越“不错误 ”
总的来说,对于一个样本,最理想的梯度是越接近0的梯度。所以,我们要能够让函数的估计值能够使得梯度往反方向移动(>0的维度上,往负方向移动,<0的维度上,往正方向移动)最终使得梯度尽量=0),并且该算法在会严重关注那些梯度比较大的样本,跟Boost的意思类似。
得到梯度之后,就是如何让梯度减少了。这里是用的一个迭代+决策树的方法,当初始化的时候,随便给出一个估计函数F(x)(可以让F(x)是一个随机的值,也可以让F(x)=0),然后之后每迭代一步就根据当前每一个样本的梯度的情况,建立一棵决策树。就让函数往梯度的反方向前进,最终使得迭代N步后,梯度越小。
这里建立的决策树和普通的决策树不太一样,首先,这个决策树是一个叶子节点数J固定的,当生成了J个节点后,就不再生成新的节点了。
算法的流程如下:(参考自treeBoost论文)

gbdt3

     0. 表示给定一个初始值
1. 表示建立M棵决策树(迭代M次)
2. 表示对函数估计值F(x)进行Logistic变换
3. 表示对于K个分类进行下面的操作(其实这个for循环也可以理解为向量的操作,每一个样本点xi都对应了K种可能的分类yi,所以yi, F(xi), p(xi)都是一个K维的向量,这样或许容易理解一点)
4. 表示求得残差减少的梯度方向
5. 表示根据每一个样本点x,与其残差减少的梯度方向,得到一棵由J个叶子节点组成的决策树
6. 为当决策树建立完成后,通过这个公式,可以得到每一个叶子节点的增益(这个增益在预测的时候用的)
每个增益的组成其实也是一个K维的向量,表示如果在决策树预测的过程中,如果某一个样本点掉入了这个叶子节点,则其对应的K个分类的值是多少。比如说,GBDT得到了三棵决策树,一个样本点在预测的时候,也会掉入3个叶子节点上,其增益分别为(假设为3分类的问题):
(0.5, 0.8, 0.1),  (0.2, 0.6, 0.3),  (0.4, 0.3, 0.3),那么这样最终得到的分类为第二个,因为选择分类2的决策树是最多的。
7. 的意思为,将当前得到的决策树与之前的那些决策树合并起来,作为新的一个模型(跟6中所举的例子差不多)

(此小节摘自http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/1976562.html)

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多