《第8章 集成学习理论》由会员分享，可在线阅读，更多相关《第8章 集成学习理论（96页珍藏版）》请在金锄头文库上搜索。
1、1,主要内容,1. 集成学习的概念 2. Adaboost 3. 应用：人脸识别,2,1.集成学习,3,在机器学习中，直接建立一个高性能的分类器是很困难的。 但是，如果能找到一系列性能较差的分类器，并把它们集成起来的话，也许就能得到更好的分类器。 日常生活中，所谓的民主决策，便是部分的利用了这种想法。 譬如选总统，每个人都以自己的考虑，投下自己的一票，但最后由多数人选出的总统，似乎应该好于由一个人指定的总统。,【集成学习：动机】,4,集成学习，就是一种把输入送入多个学习器，再通过某种办法把学习的结果集成起来的办法。 这每一个学习器，也就相应的被称为“弱学习器”。 集成学习最早也叫做“Commi
2、ttee 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 effectiv
3、e than finding a single, highly prediction rule.,【理论背景】,8,Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于Valiant提出的PAC ( Probably Approximately Correct)学习模型（1984） 提出问题（Valiant和Kearns，1984）: 强学习算法: 准确率很高的学习算法 弱学习算法: 准确率不高,仅比随机猜测略好 是否可以将弱学习算法提升为强学习算法,【理论来源】,9,同时,Valiant和Kearns首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题（1988）
4、,即任意给定仅比随机猜测略好的弱学习算法,是否可以将其提升为强学习算法? 如果二者等价,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法,而不必寻找很难获得的强学习算法。,【理论来源】,10,YES,【理论来源】,11,Boosting由来(1),Kearns 可以并行生成 Boosting:有权重;只能顺序生成,Bagging 和boosting的区别,【总结】,38,在大多数应用中，准确率比运算速度更为重要，因为计算机的性价比提高很快。 bagging和boosting都可以有效地提高分类的准确性。 在大多数数据集中，boosting的准确性比bagging高。 在有些
5、数据集中，boosting会引起退化。-Overfit Bagging和boosting方法的要求： 最基本的是分类方法的不稳定性。即：训练集的小变动能够使得分类模型显著变动。,【总结】,39,2.AdaBoost,40,adaboost的实现过程示例：,图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。,【A case study】,41,第一步：,根据分类的正确率，得到一个新的样本分布D2，一个子分类器h1 其中划圈的样本表示被分错的。在右边的图中，比较大的“+”表示对该样本做了加权。,【A case study】,42,第二步：,根据分
6、类的正确率，得到一个新的样本分布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, +1 Dt(i): 样本xi 在第t次迭代的权重 D1(i)=1/m ht(X)：弱学习器Ct训练得到的判别函数 ht:X-1, +1 t：ht(
7、X)的错误率,46,Adaboost 基本思路,1. 训练一系列弱学习器h1, h2, , hT。 2. 在训练过程中，注重那些分类错误的样本。 3. 把训练出来的一系列弱学习器组合起来，每个弱学习器ht(X)都有一个相应的权重,47,AdaBoost算法,48,为什么每次迭代都要把分错的点的权值变大呢？这样有什么好处呢？不这样不行吗? 注意到算法最后的表到式为 这里面的a 表示的权值，是由 得到的。而a是关于误差的表达式，到这里就可以得到比较清晰的答案了，所有的一切都指向了误差。提高错误点的权值，当下一次分类器再次分错了这些点之后，会提高整体的错误率，这样就导致 a 变的很小，最终导致这个分
8、类器在整个混合分类器的权值变低。也就是说，这个算法让优秀的分类器占整体的权值更高，而差的分类器权值更低。,AdaBoost算法,49,AdaBoost算法(2),弱学习器Ct的权重t由第t次迭代决定 训练样本的分布权重Dt (i)在每一次迭代都会更新 弱学习器Ct的选择： 如果某次迭代的训练误差大于1/2，则抛弃，算法停止,50,AdaBoost算法(3),算法在每次迭代都会更新样本的分布权重，在下一次迭代前会进行一次训练样本的重采样。如何进行重采样？ 可根据概率分布Dt(i)来采样。,50,51,Adaboost算法重点样本权重,思想：提高分错样本的权重 采用什么样的函数形式？,52,Ada
9、boost算法重点弱学习机权重,思想：错误率越低，该学习机的权重应该越大 采用什么样的函数形式？,53,Overview The AdaBoost Algorithm How 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
10、,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 feature T most beneficial features for classification should be selected How to define
11、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:,I
12、nitialization:,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 illus
13、tration,Weak Classifier 1,61,Boosting illustration,Weights Increased,62,Boosting illustration,Weak Classifier 2,63,Boosting illustration,Weights Increased,64,Boosting illustration,Weak Classifier 3,65,Boosting illustration,Final classifier is a combination of weak classifiers,66,How and why AdaBoost
14、 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 minim
15、izes 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对样
16、本的假设是否正确 采用什么样的函数形式？,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 cl
