第八章：集成学习报告

集成学习朱辉星2016年11月8.1(1)个体与集成集成学习（ensemblelearning）：通过构建并结合多个学习器来完成学习任务。（也被成为：多分类器系统、基于委员会的学习）一般结构：先产生一组“个体学习器”（individuallearner），再用某种策略将他们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生C4.5决策树算法、BP神经网络算法8.1（2）同质•集成中只包含同种类型的个体学习器•个体学习器：基学习器•对应算法：基学习算法异质•集成中包含不同类型的个体学习器•个体学习器：由不同学习算法生成•个体学习器：组件学习器（或直接称个体学习器）8.1(3)集成学习优点：通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对“弱学习器”（weaklearner）尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也被直接成为弱学习器虽然从理论上来说使用弱学习器集成足以获得好的性能，但在实践中出于种种考虑，希望使用较少的个体学习器，人们常常会使用比较强的学习器。如何能获得比最好的单一学习器更好的性能呢？8.1（4）在二分类任务中：三个分类器在三个测试样本上的表现如下:分类器测试例1测试例2测试例3h1√√×h2×√√h3√×√集成√√√分类器测试例1测试例2测试例3h1√√×h2√√×h3√√×集成√√×分类器测试例1测试例2测试例3h1√××h2×√×h3××√集成×××a.集成提升性能b.集成不起作用c.集成起负作用集成学习的结果通过投票法产生8.1（5）a.每个分类器都只有66.6%的精度，但集成学习却达到了100%；b.三个分类器没有差别，集成后性能没有提高；c.每个分类器精度只有33.3%，集成学习结果变得更糟；以上例子显示要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太坏，并且要有“多样性”。即学习器间具有差异性。个体学习器至少不差于弱学习器8.1（6）考虑二分类问题：和真实函数，假定基分类器的错误率为，即对每个基分类器有假设集成通过简单投票法集合T个基分类器，若超过半数的基分类器正确，则集成分类就正确{1,1}yfih(()())iPhxfx⑴1()TiiHxsignhx⑵8.1（7）假设基分类器的错误率相互独立，则由Hoeffding不等式可知，集成的错误率为20(()())(1)TkTkkTPHxfxk21exp(12)2T⑶上式显示出：随着集成中个体分类器数目T的增大，集成的错误率将指数级下降，最终趋向于零。8.1（8）然而我们必须注意到，上面的分析有一个关键假设：及学习器的误差相互独立。在现实任务中，个体学习器是为解决同一个问题训练出来的，他们显然不可能相互独立。事实上，个体学习器的“准确性”和“多样性”本身就存在冲突。一般的，准确性提高之后，要增加多样性就需牺牲正确性。•如何产生“好而不同”的个体学习器集成研究核心8.1（9）根据个体学习器的生成方式，集成学习方法可分为两大类：①个体学习器间存在强依赖关系、必须串行生成的序列化方法②个体学习器间不存在强依赖关系、可同时生成的并行化方法代表：Boosting代表：Bagging和“随机森林”（Randomforest）8.2(1)BOOSTING(助推、推进)Boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制：然后基于调整后的样本分布来训练下一个基学习器再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注先从初始训练集训练出一个基学习器如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。8.2（2）ADABOOSTBoosting族算法最著名的代表：AdaBoost其中是真实函数基于“加性模型”，即基学习器的线性组合来最小化指数损失函数（exponentiallossfunction）1,1,iyf1()()TtttHxhx⑷()()exp(|)[]fxHxxDHDEe⑸8.2(3)若H(x)能令指数函数最小化，则考虑（5）式对H(x)的偏导令(6)式为零可解得：exp()()(|)(()1|)(()1|)()HxHxHDePfxxePfxxHx⑹1(()1|)()ln2(()1|)PfxxHxPfxx⑺8.2（4）因此，有1(()1|)(())ln2(()1)|PfxxsignHxsignPfxx1,(()1|)(()1|)1,(()1|)(()1|)PfxxPfxxPfxxPfxx{1,1}argmax(()|)yPfxyx⑻8.2（5）这意味着sign(H(x))达到了贝叶斯最优错误率。换言之，若指数损失函数最小化，则分类错误率也将最小化.在Adaboost算法中，第一个基分类器h1是通过直接将基学习算法用于初始数据分布而得；此后迭代地生成和，当基分类器基于分布产生后，该分类器的权重应使得最小化指数损失函数：thtthtDttth8.2（6）()()exp(|)tttfxhxtttxDhDEe(()())(()())tttxDttEefxhxefxhx(()())(()())ttttxDtxDtePfxhxePfxhx(1)ttttee其中：(()())txDtPhxfx⑼8.2（7）考虑指数损失函数的倒数：令(10)为零可解得：这恰是（Ⅰ）中算法分类器权重更新公式。exp(|)(1)tttttttthDee⑽11ln2ttt⑾8.2（8）AdaBoost算法在获得之后样本分布将进行调整，使下一轮的基学习器能纠正的一些错误。理想的能纠正的全部错误，即最小化1tHth1tHth1tH1()(()())exp1(|)[]ttfxHxhxttxDHhDEe1()()()()[]ttfxHxfxhxxDEee⑿8.2（9）注意到，式(12)可使用的泰勒展式近似为于是，理想的基学习器22()()1tfxhx()()tfxhxe122()()exp1()()(|)[(1())]2tfxHxtttxDfxhxHhDEefx1()()1[(1()())]2tfxHxxDtEefxhx⒀exp1()argmin(|)ttthhxHhD8.2（10）注意到是一个常数，令表示一个分布1()()1argmin1()()2tfxHxxDhEefxhx1()()argmax()()tfxHxxDhEefxhx11()()()()argmax()()ttfxHxxDfxHxhxDeEfxhxEe⒁1()()tfxHxxDEetD11()()()()()()ttfxHxtfxHxxDDxeDxEe⒂8.2（11）则根据数学期望的定义，这等价于令由f(x),h(x){-1,+1}，有11()()()()()argmax()()ttfxHxtxDfxHxhxDehxEfxhxEeargmax()()xDhEfxhx⒃()()12(()())fxhxfxhx⒄1,()()1,()()fxhxfxhx8.2（12）这恰是(Ⅰ)中算法第7行的样本分布更新公式()()1()()()()ttfxHxtfxHxxDDxeDxEe1()()()()()()()ttttfxHxfxhxfxHxxDDxeeEe1()()()()()()()ttttfxHxxDfxhxtfxHxxDEeDxeEe由(15)式得1()()()()tttfxHxfxhx1()()()tttfxHxhx()()tfxHx⒆8.2(13)输入：训练集D={(x1,y1),(x2,y2),…,(xm,ym)};基学习算法；训练轮数T过程：1()1.Dxm...1,2,...,_fortTdo(,);tthDD(()());ttxDtPhxfx...0.5......tifthenbreak11ln2ttt于是，由式(11)(19)，我们从基于迭代式优化指数损失函数的角度推导出了算法：1exp(),_()()()()exp(),_()()tttttttifhxfxDxDxifhxfxZ()exp(()())ttttDxfxhxZendfor输出：1()(())TtttHxsignhxⅠ1：2：3：4：5：6：7：8：8.2（14）Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法”（re-weighting）实施：对于无法接受带权样本的基学习算法，则可通过“重采样法”（re-sampling）来处理：在训练过程的每轮中，根据样本分布为每个训练样本重新赋予一个权重在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对学习器进行训练一般而言，这两种做法没有显著的优劣差异，需注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件（第5行），一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。在此时，初始设置的学习轮数也许远未达到，可能导致最终集成只包含很少的基学习器而性能不佳。8.2（15）若采用“重采样法”则可获得“重启动”机会一避免训练过程过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续预设的T轮完成。3个基学习器5个基学习器11个基学习器+好瓜—坏瓜Y含糖率X密度集成：红色基学习器：黑色Boosting能基于泛化性能相当弱的学习器构建出很强的集成8.3（1）BAGGING与随机森林由之前可知，欲得到泛化性能强的集成，集成中的个体学习器应该尽可能相互独立，虽然“独立”在现实中无法做到，但可以设法使基学习器尽可能具有较大的差异。这样。由于训练数据不同，我们获得基学习器可望具有比较大的差异，然而，我们同时还希望个体学习器不能太差。若每个子集完全不同，则每个基学习器只用到一小部分训练数据，甚至不足以进行有效学习，无法保证产生好的学习器，所以，我们考虑使用相互有交叠的采样子集。给定一个训练集，对训练样本进行采样，产生出若干不同的子集，再从每个数据子集中训练出一个基学习器8.3.1（1）BAGGINGBagging是并行式集成学习方法最著名的代表。基于自助采样法。初始训练集中约有63.2%的样本出现在采样集中。这样，我们可采样T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合。给定包含m个样本的数据集：①先随机取出一个样本放入采样集中；②再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中；③经过m次随机采样操作，得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的从未出现；Bagging的基本流程8.3.1（2）在对预测输出时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若预测时出现两个类收到同样的票数，则随机选择一个，也可进一步考察学习器投票的置信度来确定最终输出。输入：训练集D={(x1,y1),(x2,y2),…,(xm,ym)};基学习算法&训练轮数T过程：e