Boosting原理及应用

BoostingPrinciplesandApplicationsPhilpeng2011.9.291Agenda•背景•Boosting原理•Boosting应用•参考文献•Q&A2Agenda•背景•Boosting原理•Boosting应用•参考文献•Q&A3背景(1)•故事：–某男到医院就诊，医生亲切地问了一些该男的症状，最后得出结论：–血淋淋的故事告诉我们：•需要一个好的诊断器：根据病人的一系列症状，得出病人患的是什么病。4医生说我怀孕了。。。背景(2)•实际上，这是一个分类问题。•分类问题很常见：–博客男女–OCR–情感分类–查询意图识别–锚文本噪音识别–排序学习5背景(3)•文本分类算法：–NaïveBayes–DecisionTree–KNN–ANN–SVM–ME–...6背景(4)•然而，事实是残酷的。•直接寻找一个强分类器很困难。7背景(5)•弱+…+弱≈强–古语有云：三个臭皮匠，顶个诸葛亮。–Findingmanyroughrulesofthumbcanbealoteasierandmoreeffectivethanfindingasingle,highlypredictionrule.•启发：–整合多个弱分类器，成为一个强大的分类器。–这时候，集合分类器(Boosting,Bagging等)出现了。8Agenda•背景•Boosting原理•Boosting应用•参考文献•Q&A9Boosting原理•Boosting由来•Boosting思想•AdaBoost算法及分析•Boostingvs.Bagging10Boosting由来(1)•Kearns&Valiant(1984)–PAC学习模型–提出问题：•强学习算法：存在一个多项式时间的学习算法以识别一组概念，且识别的正确率很高。•弱学习算法：识别一组概念的正确率仅比随机猜测略好。•弱学习器与强学习器的等价问题。如果两者等价，只需找到一个比随机猜测略好的学习算法，就可以将其提升为强学习算法。11Boosting由来(2)•Kearns&Valiant(1989)–证明了弱学习器和强学习器的等价问题。•Schapire(1989)–第一个提出了一个可证明的多项式时间的Boosting算法。•Schapire,etc.(1993)–第一次把Boosting算法思想用于实际应用：OCR。•Freund&Schapire(1995)–AdaBoost算法。12Boosting思想(1)•基本思想：–先赋予每个训练样本相同的概率。–然后进行T次迭代，每次迭代后，对分类错误的样本加大权重(重采样)，使得在下一次的迭代中更加关注这些样本。13带权的训练样本集分类器Ct训练调整权重Boosting思想(2)14C1C3C2α1C1+α2C2+α3C3AdaBoost算法及分析•BaseSetting•AdaBoost算法•AdaBoost特性分析•AdaBoost多元分类15BaseSetting•二元分类问题•训练数据:–(x1,y1),…,(xm,ym)•wherexi∈X,yi∈Y={-1,+1}•Dt(i):样本xi在第t次迭代的权重–D1(i)=1/m•ht(X)：弱学习器Ct训练得到的判别函数–ht:X-{-1,+1}•εt：ht(X)的错误率16基本思路•1.训练一系列弱学习器h1,h2,…,hT。•2.在训练过程中，注重那些分类错误的样本。•3.把训练出来的一系列弱学习器组合起来，每个弱学习器ht(X)都有一个相应的权重αt:17))(()(1TtttxhsignxHAdaBoost算法18AdaBoost算法(2)•弱学习器Ct的权重αt由第t次迭代决定•训练样本的分布权重Dt(i)在每一次迭代都会更新•弱学习器Ct的选择：–如果某次迭代的训练误差大于1/2，则抛弃，算法停止19AdaBoost算法(3)•算法在每次迭代都会更新样本的分布权重，在下一次迭代前会进行一次训练样本的重采样。•如何进行重采样？–可根据概率分布Dt(i)来采样。–“轮盘赌”算法是其中一种比较简单、高效的方法。20AdaBoost算法(4)•“轮盘赌”算法–使用一个[0~1]随机数生成器–举例：如果随机数生成器生成0.525，则恭喜你，获得“康师傅冰红茶”一瓶；若生成0.91，则能获得宝马一部。21谢谢光临康师傅冰红茶宝马iPad分别记“谢谢光临”、“康师傅冰红茶”、“iPad”、“宝马”为A、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.0AdaBoost特性分析(1)•特性1：–训练误差的上界，随着迭代次数的增加，会逐渐下降。•特性2：–adaboost算法即使训练次数很多，也不会出现过度拟合(overfitting)的问题。22AdaBoost特性分析(2)•训练误差上界的下降特性•Step1:对分布函数解递归23))(()()()(:1xfsignxHxhxfletTtttTttTtittiTZxhymiD11))(exp(1)(TttxfyZemii1)(1AdaBoost特性分析(3)•训练误差上界的下降特性(cont.)•Step2:24mixyfmHerrortrainingtsexyfyxH1)(011)(_..10)()(ifyi!=H(xi)elsettittTmixfyZZiDemii)(11)(AdaBoost特性分析(4)•训练误差上界的下降特性(cont.)•Step3:25iititttxhyiDZ))(exp()()1(2)1()()()(:)(:ttttxhyitxhyitttititititeeeiDeiDAdaBoost特性分析(5)•训练误差上界的下降特性(cont.)•where•随着迭代次数的增加，实际上训练误差上界在下降。26tttHerrortraining)1(2)(_)2exp(4122tttttt21AdaBoost特性分析(6)•不会出现过度拟合现象–随着模型训练误差的下降，实际上，模型的泛化误差（测试误差）在上升。27AdaBoost特性分析(6)•不会出现过度拟合现象(cont.)•当训练误差降低后，Boosting继续增大边距，从而增大了最小边距，使分类的可靠性增加。28d2d1xhyyxinmttt),(argAdaBoost多元分类•AdaBoost.M1–投票机制–见文件：boosting_src.zip•AdaBoost.M2•AdaBoost.MH29Boostingvs.Bagging(1)•Bagging30Boostingvs.Bagging(2)•Boosting31Boostingvs.Bagging(3)•训练集：–Bagging：随机选择，各轮训练集相互独立–Boosting：各轮训练集并不独立，它的选择与前轮的学习结果有关•判别函数：–Bagging：没有权重；可以并行生成–Boosting：有权重；只能顺序生成•很多实验与实践证明：–Boosting比Bagging效果更好！！！32Agenda•背景•Boosting原理•Boosting应用•参考文献•Q&A33Boosting应用•文本分类–AdaBoost(weaklearner:NB,C4.5等)•排序学习–RankBoost34文本分类(1)•文本分类–给定某篇文档，判别其所属类别–文档可能是某些网页，也可能是短文本(query，微博等)–应用很广35文本分类(2)•AdaBoost(weaklearner:NB)•假设检索模型使用VSM36训练语料预处理(中文分词，去停用词等)特征选择(使用卡方、类别特征域等），特征向量表示使用AdaBoost训练模型模型测试语料预处理(中文分词，去停用词等)特征向量表示类别排序学习(1)•排序问题37排序学习(2)•排序模型38排序学习(3)•根据训练样本的形式及损失函数分类：–Pointwiseapproach•Prank•McRank–Pairwiseapproach•RankBoost•RankingSVM•RankNet–Listwiseapproach•ListNet•ListMLE39排序学习(4)•RankBoost算法40Agenda•背景•Boosting原理•Boosting应用•参考文献•Q&A41参考文献•[1]RichardO.Duda,etc.PatternClassification.•[2]BingLiu.WebDataMining.•[3]TomM.Mitchell.MachineLearning.•[4]YoavFreund,RobertE.Schapire.AshortIntroductiontoBoosting.•[5]DongLehong.SurveyofBoosting.•[6]LiHang.LearningtoRank.42Agenda•背景•Boosting原理•Boosting应用•参考文献•Q&A43Q&A？Thankyou!44