基于Boosting的多分类器融合算法

Boosting*1111150001boosting,:AdaBoostMultipleClassifiersCombinationAlgorithmBasedonBoostingLINLei1WANGXiaolong1LIUJiafeng1(1DepartmentofComputerScienceandEngineering,HarbinInstituteofTechnologyHarbin,150001,P.R.China)Abstract:Invariousapplicationareasofpatternrecognition,combiningmultipleclassifiersisregardedasanewmethodforachievingasubstantialgaininperformanceofsystem.Thispaperpresentsaboostingmethodforcombiningmultipleclassifiers.ThiscombinationmethodisexperimentallytestedononlinehandwrittenChinesecharacterrecognitionsystemandtheresultscomparewithothercombiningmethod.Theireffectivenessisconsidered.Keywords:AdaBoostalgorithm;Combination;handwrittenChinesecharacterrecognition1,AdaBoost[6]BoostingKearnsandValiant[1,2]PAC[3]boosting[4,5],*NO.69973015863NO.2001AA1140411SchapireFreundboostingAdaBoost[6],boosting[7,8],AdaboostAdaBoostAdaBoostAdaBoostAdaBoost2AdaboostAdaBoostAdaBoost.M2[6]1AdaBoost()()mmyxyx,,,,11KixXAdaBoosttiyTi{}k,KY,1=t,,1K=()iDtt(e):tD[1,0]:×Xht→Y()[]iyixtDihPtte≠=~Adaboostthtβ/1log1tDHTAdaBoost:[6][9](){}()()∑∏=−≤≠ittiiiiZxfymyxHimexp1:1(1)()()∑=tttxhx)/1(logβ()ixHf1e1()1≥−iixfyiy≠tD()()()∑=iititttxhyiDZβ(2)12tβ/1logthtZ2()()mmyxyx,,,,11KXxi∈,∈iy{}kY,,1K=()miDt/1=For:1.Tt,,1K=()iDt2.:th[]1,0→×YX3.th()()()()∑+−=iitiitttyxhyxhiDe,,1214.tttee−=1β5.()()()(()yxhyxhttttitiitZiDiD,,1211−++=β)tZ1+tD()()yxhxHttt,1log∑=β1Adaboost3--2(),(e)()(E1)Adaboost1e23e3ID247575552001Recogn.Adaboost2(E1AdaboostE2)3AdaBoost35Adaboost[610]()[]+≠=mTdOyxHPesystem~3esystem()[]yxHP≠mdVCVC[11]T3()[]yxHP≠3mTd~O4606366697275151015202530354045505560%32Adaboost4.75%8.19%Adaboost-Table1.Recogn.()1e52.35%2e62.80%3e64.09%Table2.Recogn.()E172.28%E267.53%5AdaBoostAdaBoostAdaBoostT5AdaBoost35[1]MichaelKearnsandLeslieG.Valiant.LearningBooleanformulaeorfiniteautomataisashardasfactoring.TechnicalReportTR-14-88,HarvardUniversityAikenComputationLaboratory,August1988.[2]MichaelKearnsandLeslieG.Valiant.CryptographiclimitationsonlearningBooleanformulaeandfiniteautomata.JournaloftheAssociationforComputingMachinery,41(1):67-95,January1994.[3]L.G.Valiant.Atheoryofthelearnable.CommunicationsoftheACM,27(11):1134-1142,November1984.[4]RobertE.Schapire.Thestrengthofweaklearnability.MachineLearning,5(2):197-227,1990.[5]YoavFreund.Boostingaweaklearningalgorithmbymajority.InformationandComputation,121(2):256-285,1995.[6]Freund,Y.andSchapire,R.E.Adecisiontheoreticgeneralizationofon-linelearningandanapplicationtoboosting,JournalofComputerandSystemScience,55(1):119-139,1997.[7]Breiman,L.Bias,Variance,andarcingclassifiers.TechnicalReport460,StatisticsDepartment,UniversityofCaliforniaatBerkeley,1996.[8]Freund,Y.andSchapire,R.E.,Experimentswithanewboostingalgorithm.InMachineLearning:ProceedingsofThirteenthInternationalConference,148-156,1996.[9]Schapire,R.E.andYoramSinger,Improvedboostingalgorithmsusingconfidence-ratedpredictions,InProceedingsoftheEleventhAnnualConferenceonComputationalLearningTheory,80-91,1998.[10]EricB.BaumandDavidHaussler,Whatsizenetgivesvalidgeneralization?NeuralComputation,1(1):151-160,1989.[11]AnselmBlumer,AndrzejEhrenfeucht,DavidHausslerandManfredK.Warmuth,LearnabilityandtheVapnik-Chervonenkisdimension.JournaloftheAssociationforComputingMachinery,36(4):929-965,October1989.6