第8章 集成学习理论

主要内容1.集成学习的概念2.Adaboost3.应用：人脸识别11.集成学习2在机器学习中，直接建立一个高性能的分类器是很困难的。但是，如果能找到一系列性能较差的分类器，并把它们集成起来的话，也许就能得到更好的分类器。日常生活中，所谓的民主决策，便是部分的利用了这种想法。譬如选总统，每个人都以自己的考虑，投下自己的一票，但最后由多数人选出的总统，似乎应该好于由一个人指定的总统。【集成学习：动机】3集成学习，就是一种把输入送入多个学习器，再通过某种办法把学习的结果集成起来的办法。这每一个学习器，也就相应的被称为“弱学习器”。集成学习最早也叫做“CommitteeVotingMethod”，也就是因为它和投票的过程相似。【集成学习：动机】4弱学习机（weaklearner):对一定分布的训练样本给出假设（仅仅强于随机猜测）强学习机（stronglearner):根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almostperfectexpert)弱学习机强学习机Boosting弱学习机和强学习机5ClassifierensembleΣαihi(x)hn(x)h2(x)h1(x)InputvectorClassifier1Classifier2……ClassifierNCombineClassifiersOutputx【集成学习：图示】6Boosting思想源于三个臭皮匠，胜过诸葛亮

Findingmanyroughrulesofthumbcanbealoteasierandmoreeffectivethanfindingasingle,highlypredictionrule.【理论背景】7Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于Valiant提出的PAC(ProbablyApproximatelyCorrect)学习模型（1984）提出问题（Valiant和Kearns，1984）:强学习算法:准确率很高的学习算法弱学习算法:准确率不高,仅比随机猜测略好是否可以将弱学习算法提升为强学习算法【理论来源】8

同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题（1988）,即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法?如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。【理论来源】9YES【理论来源】10Boosting由来(1)Kearns&Valiant(1984)

PAC学习模型提出问题：强学习算法：存在一个多项式时间的学习算法以识别一组概念，且识别的正确率很高。弱学习算法：识别一组概念的正确率仅比随机猜测略好。弱学习器与强学习器的等价问题。如果两者等价，只需找到一个比随机猜测略好的学习算法，就可以将其提升为强学习算法。11Boosting由来(2)Kearns&Valiant(1989)证明了弱学习器和强学习器的等价问题。Schapire(1989)第一个提出了一个可证明的多项式时间的Boosting算法。Schapire,etc.(1993)第一次把Boosting算法思想用于实际应用：OCR。Freund&Schapire，ICML,1996AdaBoost算法。12我们一般选定加权平均的方法来构造集成学习的最终学习器。但是里面的每一个Classifieri怎样做呢？有一些研究，是针对每个学习器都不同构的情况，比如识别一个人，一个学习器考虑脸，另一个考虑步态，另一个考虑指纹。这种研究通常称为InformationFusion，不在我们今天讨论的范畴。我们今天讨论的，是用同样的学习算法来构造不同的弱学习器的方法。【集成学习：如何构造？】13办法就是改变训练集。通常的学习算法，根据训练集的不同，会给出不同的学习器。这时就可以通过改变训练集来构造不同的学习器。然后再把它们集成起来。【集成学习：如何构造？】14在原来的训练集上随机采样，可以得到新的训练集。【随机采样】15采样时，我们可以给训练集里的每个元素不同的权。权值可以通过上一次训练的结果来确定。【带权的采样】16通过给训练数据赋以不同的权，实际上使得每个学习器关注训练集中的某一部分，这也符合我们最初民主投票的想法。直观上，每个学习器关注训练集中的某一部分，很多个训练集应该可以覆盖训练集中的大部分，只要巧妙的选择加权平均的权，就可以得到更好的学习效果。【带权的采样:讨论】17【用多个学习器覆盖样本空间】18集成学习实际上代表了一种与传统不同的思维理念。传统的机器学习一般都自认为是单模型的，对于模型的分析总是在整体上完成。Rosenblatt：PerceptronRumelhart:BPVapnik:SVM但是，所有这些模型其实都可以看作是一种加权平均的多模型。【集成学习：评述】19所以，当然应该考虑研究一般的多模型。实际上，从90年代开始，对集成学习的研究取得了一系列突破进展。在算法上，集成学习的典型代表AdaBoost算法，已经成为与SVM并立的方法。而且，集成学习比SVM更为一般，可能可以有更广阔的前景。【集成学习：评述】20泛化：generalization泛化能力越强，处理新数据的能力越好【泛化能力】泛化能力是机器学习关注的基本问题之一提高泛化能力是永远的追求21集成学习（EnsembleLearning）是一种机器学习范式，它使用多个（通常是同质的）学习器来解决同一个问题

问题…...…...

问题集成学习中使用的多个学习器称为个体学习器当个体学习器均为决策树时，称为“决策树集成”当个体学习器均为神经网络时，称为“神经网络集成”…………【集成学习】22由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际权威T.G.Dietterich称为当前机器学习四大研究方向之首[T.G.Dietterich,AIMag97]问题：对20维超立方体空间中的区域分类左图中纵轴为错误率从上到下的四条线分别表示：平均神经网络错误率最好神经网络错误率两种神经网络集成的错误率令人惊奇的是，集成的错误率比最好的个体还低

[L.K.Hansen&P.Salamon,TPAMI90]【集成学习的重要性】23集成学习技术已经在行星探测、地震波分析、Web信息过滤、生物特征识别、计算机辅助医疗诊断等众多领域得到了广泛的应用只要能用到机器学习的地方，就能用到集成学习【集成学习的应用】24期望结果个体1(精度33.3%)个体2(精度33.3%)个体3(精度33.3%)集成(精度33.3%)投票个体必须有差异期望结果个体1(精度33.3%)个体2(精度33.3%)个体3(精度33.3%)集成(精度0%)投票个体精度不能太低个体学习器越精确、差异越大，集成越好【如何构建好的集成】25既然多个个体的集成比单个个体更好，那么是不是个体越多越好?更多的个体意味着：在预测时需要更大的计算开销，因为要计算更多的个体预测更大的存储开销，因为有更多的个体需要保存个体的增加将使得个体间的差异越来越难以获得【个体越多越好吗？】26分类器设计的重采样技术也被称为“自适应的权值重置和组合（arcing,adaptivereweightingandcombining）；这类方法的主要思想是利用同一个训练样本集合构造多个分类器，然后以某种方式将这些分类器组合成一个分类器；主要方法包括：bagging算法和boosting算法【分类设计的重采样技术】27从大小为n的原始数据集D中独立随机地抽取n’个数据(n’<=n)，形成一个自助数据集；重复上述过程，产生出多个独立的自助数据集；利用每个自助数据集训练出一个“分量分类器”；最终的分类结果由这些“分量分类器”各自的判别结果投票决定。基本思想：对训练集有放回地抽取训练样例，从而为每一个基本分类器都构造出一个跟训练集相当大小但各不相同的训练集，从而训练出不同的基本分类器；该算法是基于对训练集进行处理的集成方法中最简单、最直观的一种。【Bagging算法】28boosting算法同样是利用训练样本集合构造多个分量分类器，它只要求这个分量分类器是一个弱分类器—准确率比平均性能好即可。2类问题，3个分量分类器的训练算法：在数量为n的原始样本集D中随机选取n1个样本构成D1，利用D1训练出一个分类器C1；在样本集D-D1中选择被C1正确分类和错误分类的样本各一半组成样本集D2，用D2训练出一个分类器C2；将样本集D-D1-D2中所有C1和C2分类结果不同的样本组成样本集D3，训练出一个分类器C3；【Boosting算法】29对新的样本x进行分类，如果C1和C2判别结果相同，则将x判别为此类别，否则以C3的结果作为x的类别；原始样本集分量分类器组合分类器【Boosting的分类算法】30Boosting算法：首先给每一个训练样例赋予相同的权重，然后训练第一个基本分类器并用它来对训练集进行测试，对于那些分类错误的测试样例提高其权重（实际算法中是降低分类正确的样例的权重），然后用调整后的带权训练集训练第二个基本分类器，然后重复这个过程直到最后得到一个足够好的学习器。【Boosting算法步骤】31【Bagging算法和Boosting算法比较】32Step1:原始训练集输入，带有原始分布Step2:给出训练集中各样本的权重Step3:将改变分布后的训练集输入已知的弱学习机，弱学习机对每个样本给出假设Step4:对此次的弱学习机给出权重Step5:转到Step2,直到循环到达一定次数或者某度量标准符合要求Step6:将弱学习机按其相应的权重加权组合形成强学习机【Boosting算法流程描述】33样本的权重没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/N每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大，使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。弱学习机的权重准确率越高的弱学习机权重越高循环控制：损失函数达到最小在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。【Boosting算法核心思想】34【简单问题演示(Boosting训练过程)】35要求事先知道弱学习算法学习正确率的下限解决方案：Adaboost【Boosting算法存在问题】36训练集:Bagging:随机选择,各轮训练集相互独立Boosting:各轮训练集并不独立,它的选择与前轮的学习结果有关预测函数:Bagging:没有权重;可以并行生成Boosting:有权重;只能顺序生成Bagging和boosting的区别【总结】37在大多数应用中，准确率比运算速度更为重要，因为计算机的性价比提高很快。

bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化。---OverfitBagging和boosting方法的要求：最基本的是分类方法的不稳定性。即：训练集的小变动能够使得分类模型显著变动。【总结】382.AdaBoost39adaboost的实现过程示例：图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。【Acasestudy】40

第一步：根据分类的正确率，得到一个新的样本分布D2­，一个子分类器h1其中划圈的样本表示被分错的。在右边的图中，比较大的“+”表示对该样本做了加权。

【Acasestudy】41第二步：根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2【Acasestudy】42第三步：得到一个子分类器h3【Acasestudy】43整合所有子分类器：因此可以得到整合的结果，从结果中看，即使简单的分类器，组合起来也能获得很好的分类效果。【Acasestudy】44AdaboostBaseSetting二元分类问题训练数据:(x1,y1),…,(xm,ym)wherexi∈X,yi∈Y={-1,+1}Dt(i):样本xi在第t次迭代的权重D1(i)=1/mht(X)：弱学习器Ct训练得到的判别函数ht:X->{-1,+1}εt：ht(X)的错误率45Adaboost基本思路1.训练一系列弱学习器h1,h2,…,hT。2.在训练过程中，注重那些分类错误的样本。3.把训练出来的一系列弱学习器组合起来，每个弱学习器ht(X)都有一个相应的权重46AdaBoost算法47为什么每次迭代都要把分错的点的权值变大呢？这样有什么好处呢？不这样不行吗?注意到算法最后的表到式为这里面的a表示的权值，是由得到的。而a是关于误差的表达式，到这里就可以得到比较清晰的答案了，所有的一切都指向了误差。提高错误点的权值，当下一次分类器再次分错了这些点之后，会提高整体的错误率，这样就导致a变的很小，最终导致这个分类器在整个混合分类器的权值变低。也就是说，这个算法让优秀的分类器占整体的权值更高，而差的分类器权值更低。AdaBoost算法48AdaBoost算法(2)弱学习器Ct的权重αt由第t次迭代决定训练样本的分布权重Dt(i)在每一次迭代都会更新弱学习器Ct的选择：如果某次迭代的训练误差大于1/2，则抛弃，算法停止49AdaBoost算法(3)算法在每次迭代都会更新样本的分布权重，在下一次迭代前会进行一次训练样本的重采样。如何进行重采样？可根据概率分布Dt(i)来采样。5050Adaboost算法重点—样本权重思想：提高分错样本的权重

采用什么样的函数形式？

51Adaboost算法重点—弱学习机权重思想：错误率越低，该学习机的权重应该越大采用什么样的函数形式？52OverviewTheAdaBoostAlgorithmHowandwhyAdaBoostworks?AdaBoostforFaceDetection【Outline】53AdaBoostAdaptiveAlearningalgorithmBuildingastrongclassifierfromalotofweakeronesBoosting【Introduction】54...weakclassifiersslightlybetterthanrandomstrongclassifier【AdaBoostConcept】55WeakerClassifiers...weakclassifiersslightlybetterthanrandomstrongclassifierEachweakclassifierlearnsbyconsideringonesimplefeatureT

most

beneficialfeaturesforclassificationshouldbeselectedHowtodefinefeatures?selectbeneficialfeatures?trainweakclassifiers?manage(weight)trainingsamples?associateweighttoeachweakclassifier?56TheStrongClassifiers...weakclassifiersslightlybetterthanrandomstrongclassifierHowgoodthestrongonewillbe?57TheAdaBoostAlgorithmGiven:Initialization:For:Findclassifierwhichminimizeserrorwrt

Dt

,i.e.,

Weightclassifier:

Updatedistribution:

58TheAdaBoostAlgorithmGiven:Initialization:For:Findclassifierwhichminimizeserrorwrt

Dt

,i.e.,

Weightclassifier:

Updatedistribution:

Outputfinalclassifier:59BoostingillustrationWeakClassifier160BoostingillustrationWeightsIncreased61BoostingillustrationWeakClassifier262BoostingillustrationWeightsIncreased63BoostingillustrationWeakClassifier364BoostingillustrationFinalclassifierisacombinationofweakclassifiers65HowandwhyAdaBoostworks?66TheAdaBoostAlgorithmGiven:Initialization:For:Findclassifierwhichminimizeserrorwrt

Dt

,i.e.,

Weightclassifier:

Updatedistribution:

Outputfinalclassifier:WhatgoaltheAdaBoostwantstoreach?67T