adaboost is consistent

《adaboost is consistent》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、JournalofMachineLearningResearch8(2007)2347-2368Submitted12/06;Revised7/07;Published10/07AdaBoostisConsistentPeterL.BartlettBARTLETT@STAT.BERKELEY.EDUDepartmentofStatisticsandComputerScienceDivisionUniversityofCaliforniaBerkeley,CA94720-3860,USAMikhail

2、TraskinMTRASKIN@STAT.BERKELEY.EDUDepartmentofStatisticsUniversityofCaliforniaBerkeley,CA94720-3860,USAEditor:YoavFreundAbstractTherisk,orprobabilityoferror,oftheclassifierproducedbytheAdaBoostalgorithmisinvesti-gated.Inparticular,weconsiderthestoppingst

3、rategytobeusedinAdaBoosttoachieveuniversalconsistency.WeshowthatprovidedAdaBoostisstoppedaftern1eiterations—forsamplesizenande2(0;1)—thesequenceofrisksoftheclassifiersitproducesapproachestheBayesrisk.Keywords:boosting,adaboost,consistency1.Introduction

4、Boostingalgorithmsareanimportantrecentdevelopmentinclassification.Thesealgorithmsbelongtoagroupofvotingmethods(see,forexample,Schapire,1990;Freund,1995;FreundandSchapire,1996,1997;Breiman,1996,1998),thatproduceaclassifierasalinearcombinationofbaseorweakc

5、lassifiers.Whileempiricalstudiesshowthatboostingisoneofthebestofftheshelfclassifica-tionalgorithms(seeBreiman,1998)theoreticalresultsdonotgiveacompleteexplanationoftheireffectiveness.ThefirstformulationsofboostingbySchapire(1990),Freund(1995),andFreundand

6、Schapire(1996,1997)consideredboostingasaniterativealgorithmthatisrunforafixednumberofiterationsandateveryiterationitchoosesoneofthebaseclassifiers,assignsaweighttoitandeventuallyoutputstheclassifierthatistheweightedmajorityvoteofthechosenclassifiers.LaterB

7、reiman(1997,1998,2004)pointedoutthatboostingisagradientdescenttypealgorithm(seealsoFriedmanetal.,2000;Masonetal.,2000).ExperimentalresultsbyDruckerandCortes(1996),Quinlan(1996),Breiman(1998),BauerandKohavi(1999)andDietterich(2000)showedthatboostingisav

8、eryeffectivemethod,thatoftenleadstoalowtesterror.Itwasalsonotedthatboostingcontinuestodecreasetesterrorlongafterthesampleerrorbecomeszero:thoughitkeepsaddingmoreweakclassifierstothelinearcombinationofclassifiers,thegeneralizationerror,per