机器学习十大算法：AdaBoost

Chapter7AdaBoostZhi-HuaZhouandYangYuContents7.1Introduction...........................................................1277.2TheAlgorithm.........................................................1287.2.1Notations.......................................................1287.2.2AGeneralBoostingProcedure..................................1297.2.3TheAdaBoostAlgorithm.......................................1307.3IllustrativeExamples...................................................1337.3.1SolvingXORProblem..........................................1337.3.2PerformanceonRealData......................................1347.4RealApplication.......................................................1367.5AdvancedTopics.......................................................1387.5.1TheoreticalIssues...............................................1387.5.2MulticlassAdaBoost............................................1427.5.3OtherAdvancedTopics.........................................1457.6SoftwareImplementations..............................................1457.7Exercises..............................................................146References..................................................................1477.1IntroductionGeneralizationability,whichcharacterizeshowwelltheresultlearnedfromagiventrainingdatasetcanbeappliedtounseennewdata,isthemostcentralconceptinmachinelearning.Researchershavedevotedtremendouseffortstothepursuitoftech-niquesthatcouldleadtoalearningsystemwithstronggeneralizationability.Oneofthemostsuccessfulparadigmsisensemblelearning[32].Incontrasttoordinarymachinelearningapproacheswhichtrytogenerateonelearnerfromtrainingdata,ensemblemethodstrytoconstructasetofbaselearnersandcombinethem.Baselearnersareusuallygeneratedfromtrainingdatabyabaselearningalgorithmwhichcanbeadecisiontree,aneuralnetwork,orotherkindsofmachinelearningalgorithms.Justlike“manyhandsmakelightwork,”thegeneralizationabilityofanensembleisusuallysignificantlybetterthanthatofasinglelearner.Actually,ensemblemeth-odsareappealingmainlybecausetheyareabletoboostweaklearners,whichare127©2009byTaylor&FrancisGroup,LLC128AdaBoostslightlybetterthanrandomguess,tostronglearners,whichcanmakeveryaccuratepredictions.So,“baselearners”arealsoreferredas“weaklearners.”AdaBoost[9,10]isoneofthemostinfluentialensemblemethods.IttookbirthfromtheanswertoaninterestingquestionposedbyKearnsandValiantin1988.Thatis,whethertwocomplexityclasses,weaklylearnableandstronglylearnableprob-lems,areequal.Iftheanswertothequestionispositive,aweaklearnerthatperformsjustslightlybetterthanrandomguesscanbe“boosted”intoanarbitrarilyaccuratestronglearner.Obviously,suchaquestionisofgreatimportancetomachinelearning.Schapire[21]foundthattheanswertothequestionis“yes,”andgaveaproofbyconstruction,whichisthefirstboostingalgorithm.Animportantpracticaldeficiencyofthisalgorithmistherequirementthattheerrorboundofthebaselearnersbeknownaheadoftime,whichisusuallyunknowninpractice.FreundandSchapire[9]thenpro-posedanadaptiveboostingalgorithm,namedAdaBoost,whichdoesnotrequirethoseunavailableinformation.ItisevidentthatAdaBoostwasbornwiththeoreticalsignif-icance,whichhasgivenrisetoabundantresearchontheoreticalaspectsofensemblemethodsincommunitiesofmachinelearningandstatistics.ItisworthmentioningthatfortheirAdaBoostpaper[9],SchapireandFreundwontheGodelPrize,whichisoneofthemostprestigiousawardsintheoreticalcomputerscience,intheyear2003.AdaBoostanditsvariantshavebeenappliedtodiversedomainswithgreatsuccess,owingtotheirsolidtheoreticalfoundation,accurateprediction,andgreatsimplicity(Schapiresaiditneedsonly“just10linesofcode”).Forexample,ViolaandJones[27]combinedAdaBoostwithacascadeprocessforfacedetection.Theyregardedrectan-gularfeaturesasweaklearners,andbyusingAdaBoosttoweighttheweaklearners,theygotveryintuitivefeaturesforfacedetection.Inordertogethighaccuracyaswellashighefficiency,theyusedacascadeprocess(whichisbeyondthescopeofthischap-ter).Asaresult,theyreportedaverystrongfacedetector:Ona466MHzmachine,facedetectionona384×288imagecostsonly0.067second,whichis15timesfasterthanstate-of-the-artfacedetectorsatthattimebutwithcomparableaccuracy.Thisfacedetectorhasbeenrecognizedasoneofthemostexcitingbreakthroughsincomputervision(inparticular,facedetection)duringthepastdecade.Itisnotstrangethat“boost-ing”hasbecomeabuzzwordincomputervisionandmanyotherapplicationareas.Intherestofthischapter,wewillintroducethealgorithmandimplementations,andgivesomeillustrationsonhowthealgorithmworks.Forreaderswhoareeagertoknowmore,wewillintroducesometheoreticalresultsandextensionsasadvancedtopics.7.2TheAlgorithm7.2.1NotationsWefirstintroducesomenotationsthatwillbeusedintherestofthechapter.LetXdenotetheinstancespace,orinotherwords,featurespace.LetYdenotethesetoflabelsthatexpresstheunderlyingconceptswhicharetobelearned.Forexample,we©2009byTaylor&FrancisGroup,LLC7.2TheAlgorithm129letY={−1,+1}forbinaryclassification.AtrainingsetDconsistsofminstanceswhoseassociatedlabelsareobserved,i.e.,D={(xi,yi)}(i∈{1,...,m}),whilethelabelofatestinstanceisunknownandthustobe