资源描述:
《editor15732new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、JournalofMachineLearningResearch?(?)1–20Submitted12/2006;Published?/?AdaBoostisConsistentPeterL.Bartlettbartlett@stat.berkeley.eduDepartmentofStatisticsandComputerScienceDivisionUniversityofCaliforniaBerkeley,CA94720-3860,USAMikhailTraskinmtraskin@stat.berkeley.eduDepartmen
2、tofStatisticsUniversityofCaliforniaBerkeley,CA94720-3860,USAEditor:?AbstractTherisk,orprobabilityoferror,oftheclassifierproducedbytheAdaBoostalgorithmisinvesti-gated.Inparticular,weconsiderthestoppingstrategytobeusedinAdaBoosttoachieveuniversal1−εconsistency.Weshowthatprovid
3、edAdaBoostisstoppedafterniterations—forsamplesizenandε∈(0,1)—thesequenceofrisksoftheclassifiersitproducesapproachestheBayesrisk.Keywords:boosting,adaboost,consistency1.IntroductionBoostingalgorithmsareanimportantrecentdevelopmentinclassification.Thesealgorithmsbelongtoagroupo
4、fvotingmethods(see,forexample,Schapire,1990;Freund,1995;FreundandSchapire,1996,1997;Breiman,1996,1998),thatproduceaclassifierasalinearcombinationofbaseorweakclassifiers.Whileempiricalstudiesshowthatboostingisoneofthebestofftheshelfclassifica-tionalgorithms(seeBreiman,1998)theor
5、eticalresultsdonotgiveacompleteexplanationoftheireffectiveness.ThefirstformulationsofboostingbySchapire(1990);Freund(1995);FreundandSchapire(1996,1997)consideredboostingasaniterativealgorithmthatisrunforafixednumberofiterationsandateveryiterationitchoosesoneofthebaseclassifiers
6、,assignsaweighttoitandeventuallyoutputstheclassifierthatistheweightedmajorityvoteofthechosenclassifiers.LaterBreiman(1997,1998,2000)pointedoutthatboostingisagradientdescenttypealgorithm(seealsoFriedmanetal.,2000;Masonetal.,2000).ExperimentalresultsbyDruckerandCortes(1996);Qui
7、nlan(1996);Breiman(1998);BauerandKohavi(1999);Dietterich(2000)showedthatboostingisaveryeffectivemethod,thatoftenleadstoalowtesterror.Itwasalsonotedthatboostingcontinuestodecreasetesterrorlongafterthesampleerrorbecomeszero:thoughitkeepsaddingmoreweakclassifierstothelinearcombi
8、nationofclassifiers,thegeneralizationerror,perhapssurprisingly,usuallydoesnotincrea