Ensemble Methods Foundations and Algorithms读书笔记

【实例简介】
Ensemble Methods Foundations and Algorithms的读书笔记，介绍boosting,bagging，adaboost等理论
4.5.1代数方法 42 4.5.2行为知识空间法 42 4.5.3决策模板法…… 42 46相关方法 4.6.1误差校止输出代码 4.6.2动态分类器选择.… 43 46.3混合专家 ..43 4.7进一步阅读 43 多样性 5.1集成多样性 5.2误差分解 5.2.1歧义误差分解 5.2.2偏差、方差、协方差分解 44 5.3多样性度量方法… 45 5.3.1 PAIRWISE度量法 45 5.3.2非 PAIRWISE度量法 45 5.5.3归纳和可视化 45 5.3.4多样性度量方法的局限性 54信息理论的多样性 54.1信息论和集成方法 5.4.2互信息的多样性 垂,垂垂垂 45 54.3多信息的多样性… 45 544估计方法 45 5.5多样性的产生 45 8 2 Boosting 21 Boosting过程 提升( boosting一词表示可以将一系列的弱学习算法转化为强学习算法。从直觉 上来说,弱学习算法是指比随杋猜测稍强的学习算法,强学习算法是指性能非常完美的 学习算法。 Boosting算法起初是为了回答 Kearns和 Valiant于1989年提出的弱可学习和强 可学习是否是等价的问题。弱学习和强学习之间的关系问题是非常重要的基础问题,因 为如果弱学习和强学习足等价的,那么弱学习就可以转化为强学习,在实际应用中得到 弱学习器是非常容易的而得到强学习器却比较难。 Schapire于1990年证明弱学习可以转 化为强学习。 Boosting过程非常,以二分类为例,预测样本将被分为正样本和负样本。训练样本 空间为x,其中的样本是依分布D独立同分布产生的,分类函数为f。假设空间x由x1, x℃2,x3成,每个部分占1/3,用随机猜测的分类器对样本进行分类,错误率为50%。 我们想获得准确的分类结果(分类误差率为0)但是很不幸,手头只有弱分类器,它只 能在x1,x2上有准确的分类结果,在x3上的分类结果是错的,这样分类误差率就为 1/3。将这个弱分类器定义为h1。显然h1并不能满足需求。 Boosting的思想是通过h1校准分类误差。可以从D中产生新的分布D,在新的分布 h1错误分类的误差率变大(此处的分类误差率是带权重的),因为此时的x3上的样 本权重变大了。接着可以在D上训练分类器h2,假设此时的h2依然是弱分类器,它只 能在x1,x3上正确分类,在x2上分类错误。以一种合适的方式将h1和h2组合起来,组 合分类器在x1上能正确分类,在x2和x3上可能有错分情况。根据h1和h2组合效果,可 以从D中产生新的分布D,在D分布上h1和h2组合起来的分类误差率亦会变大,继续 训练一个分类器h3,其在x2和x3上分类效果很好。这时将h1,h2和h3组合起来就得到 了非常完美的分类器,因为在x1,x2,x3上组合分类器能够完全正确分类 简单的说, Boosting方法就是训练一系列分类器,并将它们组合起来进行预测,后 一个分类器更关注前一个分类器分错了的样木。图2.1概述了一般的 Boosting过程。 输入:样本分布:D 基本的学习算法:8 学习分类器的个数:T 训练过程: 1D1=D 2fort=1,…,T ht=￡(①t) D )≠f(x) 5 D+1= Adjust_ Distribution (Dt,Et) 6 end 寸O一台 输出:H(x)= Combine_ Outputs({h1(x),…,h(x)}) 图2.1一般的 过程 22 Adaboost算法 8图2.1所介绍的一般化的 boosting过程并不是真正的算法,因为它没有详细介绍实现过程 如 Adjust_ distribution和 Combine_outputs等。 Adaboost算法 是 最有影响力的算法,可以将其作为一个示例进行讲解,算法过程见图 输入:数据集D=(x1,y1),(x2y2),…( Mm, y)} 基本的学习算法足 习分类器的个数T 训练过程: 1D1(x)=2.%初始化目标值的权重分布 2fort=1,…,T: 3ht=足(D,Dt);%训练集D在分布D1下训练分类器ht 4E=Px~D:(hx(x)≠f(x);%计算h的分类误差率 5 if Et>0.5 then break =}hn():%计算h2的权重 t+1(x)=De()y exp(-atif h t (x)=f(x) Dr(x)exp(-atf(x)ht(x) exp(at)ifht(x)≠f(x) %更新分布,Z是归一化因子,其使D+1满足概率分布的性质 8 end 输出:H(x)=sign(∑t=1ath1(x) 图2.2 Adaboost算法 考虐二分类问题,类别集合为{+1,-1}。 Adaboost 通过指数损 失函数最小化达到训练模型的目的 lexp(h( D)=Ex-pe/x)h(x) (2.1) 使用加权组合将弱分类器组合起来 H() 指数损失函数简单简洁的计算特征是这里采取它为损失函数的原因之一,同时它还 和最小化分类误差的目标向一致,并且通过它和对数似然函数之间的关系证明此处采用 指数损失函数是合理的。当通过H最小化指数损失函数时,指数损尖函数关于每个x的 偏导数为零 de-f(r)h(x) f(xe-f(H)=-e-H()PC(x)=1x)+ePC(x)=-11x)=0 aH( (2.3) 求解式(2.3)得到 (x)==In (2.4) 2P((x)=-1|x) 因此有 sign(H(x)=sign(In 1,P(f(x)=1|x) P(f(x)=1|x)>P(f(x) P(f(x)=-1x 1,P(f(x)=1|x)<P((x)=-1|x) argmaxP(f(x)=yIx,yE[+1, -1 从上式可以看出sign(H(x)等价于贝叶斯误差率(贝叶斯错误率是应用贝叶斯分类 规则的分类器的错误率。贝叶斯分类规则的一个性质是在最小化分类错误率上是最优 的,所以在分类问题屮,贝叶斯错误率是一个分类器对某个类别所能达到的最低的分 类错误率。)。注意这里忽略∫P(f(x)=11x)=P(f(x)=-1x)的情况。以上的公式 推导过程表明,当指数损失函数最小时,分类误差率也是最小的,所以指数损失函数可 以代替不可微分分类误差率,作为目标函数。 at和hz(x)的组合起来组成了H。刚开始时,在原始分布上训练弱分类器得到h1 在Dt上训练ht(x)后,权重α可以通过最小化αh(x)的指数损失确定 4 lax(ah1D)=ExDe-(xa4]=E2xDe-a(f(x)=h2(x)+e“I((x)≠h1(x) (f(x)=h2(x)+e“PxD2(f(x)≠h2(x) ea(1-∈t 其中,∈t=Px~D(h2(x)≠f(x)。为了获得最优化的ar,将lxp(anhD)对at求导, 并使其等于0 a(1-∈tc)+ et Et=0 解得到 1 =-n (2.8) 这就是图2.2中第六行的公式 一旦这些分类器训练完成,并且得到了每个分类器相应的权重,将这些训练好的分 类器组合起来作为Ht-1。接着 Adaboost算法调节样本分布,准备下一次训练,基本学习 算法将输出一个弱分类器ht;它将对被Ht-1误分的样本进行最大可能的正确分类。再次 考虑指数损失函数,理想的分类器ht对被H-1误分的样本进行正确分类时,必须最小化 如下指数损失函数 p(H2-1+h2|D)=Exe-(1()+(2)]=E Aple-f(r)Ht-1(xe-f(x)ht(x) (2.9) 将e-∫(x)h(x)泰勒展开,式(2,9)可以近似为 a(t1t)Ep2c()0(1(x)h2 f(x)ht(x) 2 f(r)lt-1(x) 1-f(xh(x)+ 2.10) 其屮f(x)2=1,h1(x)2 因此理想的分类器ht为 (x)=arghminp(H-1+h2|D)=argminBxD|le-(n-()(1-f(x)h(x)+ argh maxEx-ple /xHt-i()f(x)ht(x) argh maXEx-D Exple(xH-1(x)if(x)ht(x) 2.11 其屮ExDe(x)=1对为常数。 将Dt表示为 f(x)Ht1(x) Dt(x) (2.12) 寸O一台 根据数学期望的定义,式(2.11)等价于 t-1 s h, (x)=arghmaxEx-D lEx-D[e-f(xHt1e/f(x)h(x)=argh maxExxD [f(xhi(x) 由丁f(x)h2(x)=1-2(f(x)≠h2(x),所以分类器h2(x)为 ht(x)=arghminExon f(x)+h(x) 可以看到理想分类器h:(x)在分布D:下使分类误差最小。因此在Dt分布下学习弱分 类器,而且在Dt分布下弱分类器h+(x)的分类误差率要小于0.5。 Dt和Dt+1有如下关系 t+1(x)=、0(x)e-f(x)(x)D(x)erx)t=1((rh1(x) x~|e-(x)1( e f()h(x) =D e-f(xaihi()x-Dle-f(x)Ht-1(x) Ex~De-f(x)Hn(x」 2.15 式(2.15)就是图2的第7行更新分布的公式。 需要注意的是,图2.2描述的 Adaboost算法要求基本的学习算法能够学习不同的样 本分布问题。在每次迭代训练中根据之前组合分类器的分类误差率对训练数据重加权 以达到调整其分布的目的。如果基本的学习算法无法学习加权后的训练样本,则可以采 用重采样技术对原始样本进行处理,即在每次训练中根据期望的分布对样本进行采样。 如果学习算法既可以学习重加权数据也可以学习重采样数据,通常来说这两种处理 训练样本的方式不会对训练出的分类器性能有什么影响。但是重采样技术可以重新计算 Boosting[Kohavi and Wolpert,1996。在 Adaboost每次计算过程中都进行一次有效校验(图 2.2中的第5行),这种校验能够确保当前学习得到的基木分类器比随机猜测的效果要 好。当只有少量的弱分类器时,这种校验可能带来一些事与愿违的结果, Adaboost的达 代过程可能提前结束,所以也就不会进行T次迭代计算。在多分类问题时这种情况经常 发生。当采用重采样方法时,无法通过有效验证的分类器可以被丢弃,同时产生一个新 的数据样木,在新的数据样木上重新训练基木分类器,此时 Adaboost可以避免过早迭代 结束。 23例子 通过观察 Adaboost的行为,有利对其直观认识。以二维空间上人工构造的数据集 为例,图形见图2.3(a)。该数据集仪有四个样木,如下 (+10),y1=+1 (-1,0),y1=+1 (0,+1),y1=-1 (0,-1),y1 y=f(z2)是样本的标签。这是一个XOR问题。从图中可以看出,无法用一条直线 将止负样本分开,换句话说线性分类器无法将这两类样本分廾 -1 -1 -1 1 8 (a) The Xor data (b) 1st round (c)2nd round (d)3rd round 图2.3XOR问题上的 Adaboost 假设有一个基准的学习算法,它对八个基函数h到h2进行求值,如图24所示,这抛 个基准学习算法的输出结果是分类误差最小的那个基函数。如果有多于一个基函数的分 类误差一样且最小,则可从中随机选取一个。可以看出这八个基涵数没有一个能够将止 负样本分开。 下面将会看到 Adaboost算法是如何运算的 1首先在原始的数据集上训练基准学习算法。囚为h2,h3,h5;h2都其有最小的分 类误差率为0.25,假设基准学习算法的输出分类器h2。在2上只有样本z1会被误分,所 以分类误差率是=025,h2的权重a2=0.5×ln3≈0.55。图2.3(b)展示出了分类关 系,阴影区域被分为负类(-1),同时在图中显示出了分类权重0.55和0.5。 +1,vf(x1>-0.5), h,x ∫-1,f(x1>-0.5) 1. otherwise h2(x) +1, otherwise h3(x)= +1,if(x1>+0.5) h4(x)= 1,f(x1>+0.5) 1, otherwise +l, otherwise h5(x)= +1,if(x2>-0.5) h6(x) 1,if(x2>-0.5) 1. otherwise +1, otherwise h7(x) +1if(x2>+0.5) 1,if(x2>+0.5) 1. otherwise +1, otherwise x1,x2分别为数据第一维和额第二维特征 图24基准学习器中用到的八个基函数 2z1的权重被加大,然后再次执行基准学习算法,这一次h3,h,hg有最小的学习 误差为0.80,假设此时选择h3作为此次学习生成的分类器,图2.3(c)展示组合分类 器h2,h3,以及它们的权重,根据它们的组合权重,用较深的颜色区分出负类区域。 3z2当前权重被加大,再次训练,只有h5,hg的分类误差最小为1.10,从中选出hs 作为此次训练产生的分类器。图2.3(d)显示了h2,h3,h5组合情况。 结果三次计算之后,观察图2.3中分类权重标记标记的区域,从中可以看出z1,z2 的分类权重标记为“+”,幻3,κ4的标记为“”,这就意味着所有的样本都能够准确分 类。所以通过将并不完美的线性分类器组合起来, Adaboost产生了一个准确的(分类误 差率为0)非线性分类器 寸O一台 抛图25()单决策树的决策边界,(b)Ax的决策边界,()使用Ahm组合 的十棵决策树的分类边界 为了进一步理解 Adaboost算法,在三个相同的高斯数据集上使用单决策树, Adaboost,以及用 Adaboost组合起来的十个决策树,它们的决策边界如图2.5。可以看到 与单决策树相比, Adaboost的决策边界更加多变,这使得分类误差率从单决策树的949 降低到提升组合方法的8.3% 在UCI机器学习库的40个数据集上对 Adaboost算法进行评价,通过重加权方式在 50个弱分类器上进行训练,weka实现了 Adaboost. m1算法。基本上所有的学习算法都可 以当作基准学习算法,如决策树,神经网络等。此处釆用三种基准的学习算法:决策树 桩,经过剪枝的]48决策树和未剪枝的j48决策树(weka实现了(4.5决策树)。在图 2.6中画出了对比结果,从中可以看出, Adaboost通常都能超越基准学习算法,只有极 少数的 Adaboost算法的性能比基准算法查。 未 AdaBoost with Decision Stump Ada bo ost with pruned decision lre 0.6 另04 Ada Boost with Unprimed D)ecision.6 图2.6在40个uCI数据集上 Adaboost算法与各个基准算法的对比图,每个点代表 个数据集上两种算法的预测误差,对角线表两种预测算法有相同的预测误差。 24相关理论分析 2.4.1初始状态分析 和 证明,如过 的基本学习算法的分类误差为E1,E2,…,∈r, 小最终的组合分类器上界c为 e=ExI(x)≠f(x≤2m1V2(1-E≤ (2.16) yt=0.5-∈t,可以看出 Adaboost以指数两级减少分类误差。这就意味看为便分类误差小 于∈,迭代计算的步数T的上界为 1 T≤|lr (2.17) 其中假设y≥1≥y2…≥yr 8 但是在实际计算中所有的估计都是基于训练数据D的,即ED=Ex~D[H(x)≠f(x),所 以Ep表示的是训练误差,实际上更应该关注泛化误差E 和 证明 泛化误差的上界为 ∈≤ED+0 (2.18)8 d是基准学习方法的vC维,m是训练样本的个数,T是训练迭代次数,为了隐藏对数项 和常数项用0()代替O( 2.4.2对间隔的解释 式(2.18)表明,为了达到理想的泛化能力,需要控制基本学习器的复杂度和迭代 计算的次数。如果不对基准学习器的复杂度和迭代计算的次数加以控制 Adaboost可能导 致过拟合。 然而,实际研究发现Ada3oost通常来说不会过拟合,也就是说结果多次迭代计算 (例如1000次),即使训练误差达到零后测试误差还会继续减小。如图2.7所示 画出了典型的 算法的性能,从中可以看到在结果次达代计算后 的训练误差达到了,而泛化误差还在继续减小,这种现象看似与奥卜姆剃刀原理相 背,奥卡姆剃刀原理认为,如果有一个复杂模型和一个简单模型,它们能很好的解决我们的 问题,则选择简单的模型。所以硏究 不容易过拟合问题就变成了重要的理论问题,引 起了很多人的关注。 20 ta111 ng testing s rounds 15 optimal 1000 rounds 0.5 1000 (5 number of learning rounds margin a 图27(a)训练误差和测试误差,(b) Adaboost算法在UCI的 letter数据集上的泛 化误差的间隔分布 Schapire et al.198用基于分类间隔的方式解释了 Adaboost。通常来说在二分类中, 則f(x)∈{-1,+1},样本x在分类器h上的边界,即样本x距离分类器h的间隔定义为 f(x)h(x),同理组合分类器H(x)=∑=1ath2(x)的边界是f(x)H(x)=E=1atf(x)h2(x), 组合方法的归一化边界是 f(x)H(x)=2 1 atf(r)ht(r (2.19) at是基木学习算法的权重。 在边界概念的基础上, Schapire et al.198证明,在训练数据集D上,以至少1-8的 概率给定边界阈值θ>0,则组合方法的泛化误差∈D=Px-(H(x)≠f(x)可以写成 ED≤Px~D(H(x)f(x)≤6)+0 +In 70 寸O一台 (1-∈)1+++0 (2.20) d,m,T,0()和式(218)中的意义相同,∈t是h的训练误差。式(2.20)说明当其 它变量都固定时,在训练集上的边界越人,泛化误差越小。这样 Schapire et al.19得出,, 器 Adaboost不容易过拟合原因,是由于即使在训练误差达到0后,组合分类器的边界还是可以增大 图27(b)展示了在不同学习次数时 Adaboost的边界分布。 【实例截图】
【核心代码】