Boosting原理及应用ppt课件.ppt

《Boosting原理及应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、BoostingPrinciplesandApplicationsPhilpeng2011.9.291Agenda背景Boosting原理Boosting应用参考文献Q&A2Agenda背景Boosting原理Boosting应用参考文献Q&A3背景(1)故事：某男到医院就诊，医生亲切地问了一些该男的症状，最后得出结论：血淋淋的故事告诉我们：需要一个好的诊断器：根据病人的一系列症状，得出病人患的是什么病。医生说我怀孕了。。。4背景(2)实际上，这是一个分类问题。分类问题很常见：博客男女OCR情感分类查询意图识别锚文本噪音识别排序学习5背景(3)文本分类算法：NaïveBaye

2、sDecisionTreeKNNANNSVMME...6背景(4)然而，事实是残酷的。直接寻找一个强分类器很困难。7背景(5)弱+…+弱≈强古语有云：三个臭皮匠，顶个诸葛亮。Findingmanyroughrulesofthumbcanbealoteasierandmoreeffectivethanfindingasingle,highlypredictionrule.启发：整合多个弱分类器，成为一个强大的分类器。这时候，集合分类器(Boosting,Bagging等)出现了。8Agenda背景Boosting原理Boosting应用参考文献Q&A9Boosting原理Boo

3、sting由来Boosting思想AdaBoost算法及分析Boostingvs.Bagging10Boosting由来(1)Kearns&Valiant(1984)PAC学习模型提出问题：强学习算法：存在一个多项式时间的学习算法以识别一组概念，且识别的正确率很高。弱学习算法：识别一组概念的正确率仅比随机猜测略好。弱学习器与强学习器的等价问题。如果两者等价，只需找到一个比随机猜测略好的学习算法，就可以将其提升为强学习算法。11Boosting由来(2)Kearns&Valiant(1989)证明了弱学习器和强学习器的等价问题。Schapire(1989)第一个提出了一个可证明

4、的多项式时间的Boosting算法。Schapire,etc.(1993)第一次把Boosting算法思想用于实际应用：OCR。Freund&Schapire(1995)AdaBoost算法。12Boosting思想(1)基本思想：先赋予每个训练样本相同的概率。然后进行T次迭代，每次迭代后，对分类错误的样本加大权重(重采样)，使得在下一次的迭代中更加关注这些样本。带权的训练样本集分类器Ct训练调整权重13Boosting思想(2)C1C3C2α1C1+α2C2+α3C314AdaBoost算法及分析BaseSettingAdaBoost算法AdaBoost特性分析AdaBoo

5、st多元分类15BaseSetting二元分类问题训练数据:(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)的错误率16基本思路1.训练一系列弱学习器h1,h2,…,hT。2.在训练过程中，注重那些分类错误的样本。3.把训练出来的一系列弱学习器组合起来，每个弱学习器ht(X)都有一个相应的权重αt:17AdaBoost算法18AdaBoost算法(2)弱学习器Ct的权重αt由第t次迭代决定训练样本的分布权重D

6、t(i)在每一次迭代都会更新弱学习器Ct的选择：如果某次迭代的训练误差大于1/2，则抛弃，算法停止19AdaBoost算法(3)算法在每次迭代都会更新样本的分布权重，在下一次迭代前会进行一次训练样本的重采样。如何进行重采样？可根据概率分布Dt(i)来采样。“轮盘赌”算法是其中一种比较简单、高效的方法。20AdaBoost算法(4)“轮盘赌”算法使用一个[0~1]随机数生成器举例：如果随机数生成器生成0.525，则恭喜你，获得“康师傅冰红茶”一瓶；若生成0.91，则能获得宝马一部。谢谢光临康师傅冰红茶宝马iPad分别记“谢谢光临”、“康师傅冰红茶”、“iPad”、“宝马”为A、

7、B、C、D，它们的分布概率各是Pr(A)=0.4,Pr(B)=0.3,Pr(C)=0.2,Pr(D)=0.1,奖项分布概率累积概率A0.40.4B0.30.7C0.20.9D0.11.021AdaBoost特性分析(1)特性1：训练误差的上界，随着迭代次数的增加，会逐渐下降。特性2：adaboost算法即使训练次数很多，也不会出现过度拟合(overfitting)的问题。22AdaBoost特性分析(2)训练误差上界的下降特性Step1:对分布函数解递归23AdaBoost特性分析(3)训练误差上界的下