第8章集成学习理论ppt课件.ppt

1,主要内容,1. 集成学习的概念2. Adaboost3. 应用：人脸识别,2,1.集成学习,3,在机器学习中，直接建立一个高性能的分类器是很困难的。但是，如果能找到一系列性能较差的分类器，并把它们集成起来的话，也许就能得到更好的分类器。日常生活中，所谓的民主决策，便是部分的利用了这种想法。譬如选总统，每个人都以自己的考虑，投下自己的一票，但最后由多数人选出的总统，似乎应该好于由一个人指定的总统。,【集成学习：动机】,4,集成学习，就是一种把输入送入多个学习器，再通过某种办法把学习的结果集成起来的办法。这每一个学习器，也就相应的被称为“弱学习器”。集成学习最早也叫做“Committee Voting Method”，也就是因为它和投票的过程相似。,【集成学习：动机】,5,弱学习机（weak learner): 对一定分布的训练样本给出假设（仅仅强于随机猜测）强学习机（strong learner): 根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost perfect expert)弱学习机 强学习机,弱学习机和强学习机,6,【集成学习：图示】,7,Boosting思想源于三个臭皮匠，胜过诸葛亮Finding many rough rules of thumb can be a lot easier and more effective than finding a single, highly prediction rule.,【理论背景】,8,Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于Valiant提出的PAC ( Probably Approximately Correct)学习模型（1984）提出问题（Valiant和Kearns，1984）:强学习算法: 准确率很高的学习算法弱学习算法: 准确率不高,仅比随机猜测略好是否可以将弱学习算法提升为强学习算法,【理论来源】,9,同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题（1988） ,即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法? 如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。,【理论来源】,10,YES,【理论来源】,11,Boosting由来(1),Kearns & Valiant (1984) PAC学习模型提出问题：强学习算法：存在一个多项式时间的学习算法以识别一组概念，且识别的正确率很高。弱学习算法：识别一组概念的正确率仅比随机猜测略好。弱学习器与强学习器的等价问题。如果两者等价，只需找到一个比随机猜测略好的学习算法，就可以将其提升为强学习算法。,12,Boosting由来(2),Kearns & Valiant (1989)证明了弱学习器和强学习器的等价问题。Schapire (1989)第一个提出了一个可证明的多项式时间的Boosting算法。Schapire, etc. (1993)第一次把Boosting算法思想用于实际应用：OCR。Freund & Schapire，ICML,1996AdaBoost算法。,13,我们一般选定加权平均的方法来构造集成学习的最终学习器。但是里面的每一个Classifier i怎样做呢？有一些研究，是针对每个学习器都不同构的情况，比如识别一个人，一个学习器考虑脸，另一个考虑步态，另一个考虑指纹。这种研究通常称为Information Fusion，不在我们今天讨论的范畴。我们今天讨论的，是用同样的学习算法来构造不同的弱学习器的方法。,【集成学习：如何构造？】,14,办法就是改变训练集。通常的学习算法，根据训练集的不同，会给出不同的学习器。这时就可以通过改变训练集来构造不同的学习器。然后再把它们集成起来。,【集成学习：如何构造？】,15,在原来的训练集上随机采样，可以得到新的训练集。,【随机采样】,16,采样时，我们可以给训练集里的每个元素不同的权。权值可以通过上一次训练的结果来确定。,【带权的采样】,17,通过给训练数据赋以不同的权，实际上使得每个学习器关注训练集中的某一部分，这也符合我们最初民主投票的想法。直观上，每个学习器关注训练集中的某一部分，很多个训练集应该可以覆盖训练集中的大部分，只要巧妙的选择加权平均的权，就可以得到更好的学习效果。,【带权的采样:讨论】,18,【用多个学习器覆盖样本空间】,19,集成学习实际上代表了一种与传统不同的思维理念。传统的机器学习一般都自认为是单模型的，对于模型的分析总是在整体上完成。Rosenblatt：PerceptronRumelhart: BPVapnik: SVM但是，所有这些模型其实都可以看作是一种加权平均的多模型。,【集成学习：评述】,20,所以，当然应该考虑研究一般的多模型。实际上，从90年代开始，对集成学习的研究取得了一系列突破进展。在算法上，集成学习的典型代表AdaBoost算法，已经成为与SVM并立的方法。而且，集成学习比SVM更为一般，可能可以有更广阔的前景。,【集成学习：评述】,21,泛化：generalization泛化能力越强，处理新数据的能力越好,【泛化能力】,泛化能力是机器学习关注的基本问题之一提高泛化能力是永远的追求,22,集成学习（Ensemble Learning）是一种机器学习范式，它使用多个（通常是同质的）学习器来解决同一个问题,集成学习中使用的多个学习器称为个体学习器当个体学习器均为决策树时，称为“决策树集成”当个体学习器均为神经网络时，称为“神经网络集成” ,【集成学习】,23,由于集成学习技术可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点，并被国际权威 T.G. Dietterich 称为当前机器学习四大研究方向之首T.G. Dietterich, AIMag97,问题：对20维超立方体空间中的区域分类左图中纵轴为错误率从上到下的四条线分别表示：平均神经网络错误率最好神经网络错误率两种神经网络集成的错误率令人惊奇的是，集成的错误率比最好的个体还低,L.K. Hansen & P. Salamon, TPAMI90,【集成学习的重要性】,24,集成学习技术已经在行星探测、地震波分析、Web信息过滤、生物特征识别、计算机辅助医疗诊断等众多领域得到了广泛的应用,只要能用到机器学习的地方，就能用到集成学习,【集成学习的应用】,25,【如何构建好的集成】,26,既然多个个体的集成比单个个体更好，那么是不是个体越多越好?,更多的个体意味着： 在预测时需要更大的计算开销，因为要计算更多的个体预测 更大的存储开销，因为有更多的个体需要保存,个体的增加将使得个体间的差异越来越难以获得,【个体越多越好吗？】,27,分类器设计的重采样技术也被称为“自适应的权值重置和组合（arcing, adaptive reweighting and combining）；这类方法的主要思想是利用同一个训练样本集合构造多个分类器，然后以某种方式将这些分类器组合成一个分类器；主要方法包括：bagging算法和boosting算法,【分类设计的重采样技术】,28,从大小为n的原始数据集D中独立随机地抽取n个数据(n=n)，形成一个自助数据集；重复上述过程，产生出多个独立的自助数据集；利用每个自助数据集训练出一个“分量分类器”；最终的分类结果由这些“分量分类器”各自的判别结果投票决定。,基本思想：对训练集有放回地抽取训练样例，从而为每一个基本分类器都构造出一个跟训练集相当大小但各不相同的训练集，从而训练出不同的基本分类器；该算法是基于对训练集进行处理的集成方法中最简单、最直观的一种。,【Bagging算法】,29,boosting算法同样是利用训练样本集合构造多个分量分类器，它只要求这个分量分类器是一个弱分类器准确率比平均性能好即可。2类问题，3个分量分类器的训练算法：在数量为n的原始样本集D中随机选取n1个样本构成D1，利用D1训练出一个分类器C1；在样本集D-D1中选择被C1正确分类和错误分类的样本各一半组成样本集D2，用D2训练出一个分类器C2；将样本集D-D1-D2中所有C1和C2分类结果不同的样本组成样本集D3，训练出一个分类器C3；,【Boosting算法】,30,对新的样本x进行分类，如果C1和C2判别结果相同，则将x判别为此类别，否则以C3的结果作为x的类别；,原始样本集,分量分类器,组合分类器,【Boosting的分类算法】,31,Boosting算法：首先给每一个训练样例赋予相同的权重，然后训练第一个基本分类器并用它来对训练集进行测试，对于那些分类错误的测试样例提高其权重（实际算法中是降低分类正确的样例的权重），然后用调整后的带权训练集训练第二个基本分类器，然后重复这个过程直到最后得到一个足够好的学习器。,【Boosting算法步骤】,32,【Bagging算法和Boosting算法比较】,33,Step1: 原始训练集输入，带有原始分布Step2: 给出训练集中各样本的权重Step3: 将改变分布后的训练集输入已知的弱学习机，弱学习机对每个样本给出假设Step4: 对此次的弱学习机给出权重Step5: 转到Step2, 直到循环到达一定次数或者某度量标准符合要求Step6: 将弱学习机按其相应的权重加权组合形成强学习机,【Boosting算法流程描述】,34,样本的权重没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/N每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大， 使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。弱学习机的权重准确率越高的弱学习机权重越高循环控制：损失函数达到最小在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。,【Boosting算法核心思想】,35,【简单问题演示(Boosting训练过程) 】,36,要求事先知道弱学习算法学习正确率的下限解决方案：Adaboost,【Boosting算法存在问题】,37,训练集:Bagging:随机选择,各轮训练集相互独立Boosting:各轮训练集并不独立,它的选择与前轮的学习结果有关预测函数:Bagging:没有权重;可以并行生成Boosting:有权重;只能顺序生成,Bagging 和boosting的区别,【总结】,38,在大多数应用中，准确率比运算速度更为重要，因为计算机的性价比提高很快。 bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化。-OverfitBagging和boosting方法的要求： 最基本的是分类方法的不稳定性。即：训练集的小变动能够使得分类模型显著变动。,【总结】,39,2.AdaBoost,40,adaboost的实现过程示例：,图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。,【A case study】,41,第一步：,根据分类的正确率，得到一个新的样本分布D2，一个子分类器h1其中划圈的样本表示被分错的。在右边的图中，比较大的“+”表示对该样本做了加权。,【A case study】,42,第二步：,根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2,【A case study】,43,第三步：,得到一个子分类器h3,【A case study】,44,整合所有子分类器：,因此可以得到整合的结果，从结果中看，即使简单的分类器，组合起来也能获得很好的分类效果。,【A case study】,45,Adaboost Base Setting,二元分类问题训练数据:(x1, y1), , (xm, ym)where xiX, yiY=-1, +1Dt(i): 样本xi 在第t次迭代的权重D1(i)=1/mht(X)：弱学习器Ct训练得到的判别函数ht:X-1, +1t：ht(X)的错误率,46,Adaboost 基本思路,1. 训练一系列弱学习器h1, h2, , hT。2. 在训练过程中，注重那些分类错误的样本。3. 把训练出来的一系列弱学习器组合起来，每个弱学习器ht(X)都有一个相应的权重,47,AdaBoost算法,48,为什么每次迭代都要把分错的点的权值变大呢？这样有什么好处呢？不这样不行吗? 注意到算法最后的表到式为这里面的a 表示的权值，是由得到的。而a是关于误差的表达式，到这里就可以得到比较清晰的答案了，所有的一切都指向了误差。提高错误点的权值，当下一次分类器再次分错了这些点之后，会提高整体的错误率，这样就导致 a 变的很小，最终导致这个分类器在整个混合分类器的权值变低。也就是说，这个算法让优秀的分类器占整体的权值更高，而差的分类器权值更低。,AdaBoost算法,49,AdaBoost算法(2),弱学习器Ct的权重t由第t次迭代决定训练样本的分布权重Dt (i)在每一次迭代都会更新弱学习器Ct的选择：如果某次迭代的训练误差大于1/2，则抛弃，算法停止,50,AdaBoost算法(3),算法在每次迭代都会更新样本的分布权重，在下一次迭代前会进行一次训练样本的重采样。如何进行重采样？可根据概率分布Dt(i)来采样。,50,51,Adaboost算法重点样本权重,思想：提高分错样本的权重 采用什么样的函数形式？,52,Adaboost算法重点弱学习机权重,思想：错误率越低，该学习机的权重应该越大采用什么样的函数形式？,53,OverviewThe AdaBoost AlgorithmHow and why AdaBoost works?AdaBoost for Face Detection,【 Outline 】,54,AdaBoost,Adaptive,A learning algorithm,Building a strong classifier from a lot of weaker ones,Boosting,【 Introduction 】,55,.,weak classifiers,slightly better than random,strong classifier,【 AdaBoost Concept 】,56,Weaker Classifiers,.,weak classifiers,slightly better than random,strong classifier,Each weak classifier learns by considering one simple featureT most beneficial features for classification should be selectedHow todefine features?select beneficial features?train weak classifiers?manage (weight) training samples?associate weight to each weak classifier?,57,The Strong Classifiers,.,weak classifiers,slightly better than random,strong classifier,How good the strong one will be?,58,The AdaBoost Algorithm,Given:,Initialization:,For :,Find classifier which minimizes error wrt Dt ,i.e.,Weight classifier:,Update distribution:,59,The AdaBoost Algorithm,Given:,Initialization:,For :,Find classifier which minimizes error wrt Dt ,i.e.,Weight classifier:,Update distribution:,Output final classifier:,60,Boosting illustration,Weak Classifier 1,61,Boosting illustration,WeightsIncreased,62,Boosting illustration,Weak Classifier 2,63,Boosting illustration,WeightsIncreased,64,Boosting illustration,Weak Classifier 3,65,Boosting illustration,Final classifier is a combination of weak classifiers,66,How and why AdaBoost works?,67,The AdaBoost Algorithm,Given:,Initialization:,For :,Find classifier which minimizes error wrt Dt ,i.e.,Weight classifier:,Update distribution:,Output final classifier:,What goal the AdaBoost wants to reach?,68,The AdaBoost Algorithm,Given:,Initialization:,For :,Find classifier which minimizes error wrt Dt ,i.e.,Weight classifier:,Update distribution:,Output final classifier:,What goal the AdaBoost wants to reach?,69,Goal,Minimize exponential loss,Final classifier:,70,Goal,Minimize exponential loss,Final classifier:,Maximize the margin yH(x),71,算法样本权重,思想：提高分错样本的权重 反映了strong learner对样本的假设是否正确采用什么样的函数形式？,72,算法弱学习机权重,思想：错误率越低，该学习机的权重应该越大 为学习机的错误概率采用什么样的函数形式？ 和指数函数遥相呼应：,73,理论分析-最优化,如何求弱学习机的权重？ 最基本的损失函数表达形式为了便于计算，采用以下的目标函数Boosting的循环过程就是沿着损失函数的负梯度方向进行最优化的过程。通过调整样本的分布Dt和选择弱学习机的权重at来达到这个目的。（迭代）,74,Goal,Final classifier:,Minimize,Define,with,Then,75,Final classifier:,Minimize,Define,with,Then,Set,0,76,Final classifier:,Minimize,Define,with,Then,0,77,with,Final classifier:,Minimize,Define,Then,0,78,with,Final classifier:,Minimize,Define,Then,0,79,AdaBoost特性分析(1),特性1：训练误差的上界，随着迭代次数的增加，会逐渐下降。特性2：adaboost算法即使训练次数很多，也不会出现过度拟合(over fitting)的问题。,80,AdaBoost特性分析(2),训练误差上界的下降特性Step1: 对分布函数解递归,81,AdaBoost特性分析(3),训练误差上界的下降特性 (cont.)Step2:,if yi != H(xi),else,82,AdaBoost特性分析(4),训练误差上界的下降特性 (cont.)Step3:,83,AdaBoost特性分析(5),训练误差上界的下降特性 (cont.)where随着迭代次数的增加，实际上训练误差上界在下降。,84,怎么使 尽量小看到 是关于 的函数，要使 最小显然需要研究 ！在原始的AdaBoost算法中采用贪婪算法，每次的 都是最小的保证 收敛到满意的结果。在原始AdaBoost算法中h值域是-1，1，问题是怎么找到最佳的,85,86,这时候,87,88,AdaBoost特性分析(6),不会出现过度拟合现象随着模型训练误差的下降，实际上，模型的泛化误差（测试误差）在上升。,89,AdaBoost特性分析(6),不会出现过度拟合现象 (cont.)当训练误差降低后，Boosting继续增大边距，从而增大了最小边距，使分类的可靠性增加。,90,总结,AdaBoost的核心思想“关注”被错分的样本，“器重”性能好的弱分类器怎么实现 （1）不同的训练集调整样本权重 （2）“关注”增加错分样本权重 （3）“器重”好的分类器权重大 （4）样本权重间接影响分类器权重,91,对于Boosting算法，存在两个问题：如何调整训练集，使得在训练集上训练弱分类器得以进行。如何将训练得到的各个弱分类器联合起来形成强分类器。针 对 以 上 两 个 问 题 ，AdaBoost算 法 进 行 了 调整：使用加权后选取的训练数据代替随机选取的训练数据，这样将训练的焦点集中在比较难分的训练数据上。将弱分类器联合起来时，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。,92,AdaBoost forFace Detection,93,The Task ofFace Detection,Many slides adapted from P. Viola,94,Basic Idea,Slide a window across image and evaluate a face model at every location.,95,Challenges,Slide a window across image and evaluate a face model at every location.Sliding window detector must evaluate tens of thousands of location/scale combinations.Faces are rare: 010 per imageFor computational efficiency, we should try to spend as little time as possible on the non-face windowsA megapixel image has 106 pixels and a comparable number of candidate face locationsTo avoid having a false positive in every image image, our false positive rate has to be less than 106,96,The Viola/Jones Face Detector,A seminal approach to real-time object detectionTraining is slow, but detection is very fastKey ideasIntegral images for fast feature evaluationBoosting for feature selectionAttentional cascade for fast rejection of non-face windows,P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. CVPR 2001.,P. Viola and M. Jones. Robust real-time face detection. IJCV 57(2), 2004.,