|
文章目录 概述 提升方法Adaboost算法 Adaboost算法流程 Adaboost算法的说明 Adaboost算法的解释 Adaboost算法的训练误差分析 提升树 提升树模型 提升树算法 一个例子 梯度提升决策树(Gradient boosting decision tree,GBDT) 回归 分类 概述 提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效.在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类性能. 对于分类问题而言,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比求精确的分类规则(强分类器)容易得多.提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后组合这些弱分类器,构成一个强分类器.大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器. 这样,对提升方法来说,有两个问题需要回答: 一,在每一轮如何改变训练数据的权值或概率分布. 二,如何将弱分类器组合成一个强分类器. 关于第1个问题,Adaboost的做法是,提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值.这样一来,那些没有得到正确分类的数据,由于其权重的加大而受到后一轮的更大关注.于是,分类问题被一系列的弱分类器"分而治之".至于第2个问题,即弱分类器的组合,Adaboost采取加权多数表决的方法.具体地,加大分类误差率小的弱分类器的权值,使其在表决中起较大作用,减小分类误差大的弱分类器的权重,使其在表决中起较小的作用. 提升方法Adaboost算法 假定给定一个二类分类的训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)} 其中,每个样本点由实例与标记组成.实例 xi∈χRn,类标记 yi∈Y={1,+1},X是实例空间,Y是标记集合.Adaboost利用如下算法,从训练数据中学习一系列弱分类器或基本分类器,并将这些弱分类器线性组合成为一个强分类器. Adaboost算法流程 输入:训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)},其中, xi∈χRn; yi∈Y={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)在最终分类器中的重要性.当 em≤12时, am≥0,并且 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算法最终分类器的训练误差界为 1N∑i=1NI(G(xi)≠yi)≤1N∑i=1Nexp(yif(xi))=∏mZm 证明 当 G(xi)≠yi时, yif(xi)<0,因而 exp(yif(xi))≥1.由此直接推导出前半部分 后半部分的证明要用到 Zm的定义,具体推导如下:  这一定理说明,可以在每一轮选取适当的 Gm使得 Zm最小,从而使训练误差下降最快. 对于二分类问题,有如下结果: 定理2 (二分类问题AdaBoost的训练误差界) ∏mZm=∏m=1M[2em(1em)√]=∏m=1M(14γ2m)√≤exp(2∑m=1Mγ2m) 这里, γm=12em. 证明 由 Zm的定义式以及 em=∑Gm(xi)≠yiwmi可得:  至于不等式 ∏m=1M(14γ2m)√≤exp(2∑m=1Mγ2m) 则可先由 ex和 1x√在x=0的泰勒展开式推出不等式 (14γ2m)√≤exp(2γ2m). 推论 如果存在 γ>0,对所有的m有 γm>γ,则 1N∑i=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Θm∑i=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).所以,对回归问题的提升树算法来说,只需简单地拟合当前模型的残差. 这样,算法是相当简单的,现将回归问题的提升树算法描述如下.  一个例子 对于年龄预测，简单起见训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：  现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图2所示结果：  在第一棵树分枝和图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) 不同的损失函数会有不同的梯度式子:  (从上面的讲解来看这个跟上面的提升树拟合残差很想,这不过这里换成梯度,拟合梯度,有的地方叫这里的梯度为伪残差) 分类 在分类问题中，有一个很重要的内容叫做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)，  对于Logistic变换后的结果，损失函数为：  其中，yk为输入的样本数据的估计值，当一个样本x属于类别k时，yk = 1，否则yk = 0。 将Logistic变换的式子带入损失函数，并且对其求导，可以得到损失函数的梯度：  上面说的比较抽象，下面举个例子： 假设输入数据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论文）  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) |
|
|
