第8章-集成学习理论.ppt

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