资源预览需要最新版本的Flash Player支持。
您尚未安装或版本过低,建议您
1MachineLearningResearchFourCurrentDirectionsThomasG.Dietterich■Machinelearningresearchhasbeenmakinggreatprogressinmanydirections.Thisarticlesummarizesfourofthesedirectionsanddiscussessomecurrentopenproblems.Thefourdirectionsare1theimprovementofclassificationaccuracybylearningensemblesofclassifiers,2methodsforscalingupsupervisedlearningalgorithms,3reinforcementlearning,and4thelearningofcomplexstochasticmodels.Thelastfiveyearshaveseenanexplosioninmachinelearningresearch.ThisexplosionhasmanycausesFirst,separateresearchcommunitiesinsymbolicmachinelearning,computationlearningtheory,neuralnetworks,statistics,andpatternrecognitionhavediscoveredoneanotherandbeguntoworktogether.Second,machinelearningtechniquesarebeingappliedtonewkindsofproblem,includingknowledgediscoveryindatabases,languageprocessing,robotcontrol,andcombinatorialoptimization,aswellastomoretraditionalproblemssuchasspeechrecognition,facerecognition,handwritingrecognition,medicaldataanalysis,andgameplaying.Inthisarticle,Iselectedfourtopicswithinmachinelearningwheretherehasbeenalotofrecentactivity.ThepurposeofthearticleistodescribetheresultsintheseareastoabroaderAIaudienceandtosketchsomeoftheopenresearchproblems.Thetopicareasare1ensemblesofclassifiers,2methodsforscalingupsupervisedlearningalgorithms,3reinforcementlearning,and4thelearningofcomplexstochasticmodels.Thereadershouldbecautionedthatthisarticleisnotacomprehensivereviewofeachofthesetopics.Rather,mygoalistoprovidearepresentativesampleoftheresearchineachofthesefourareas.Ineachoftheareas,therearemanyotherpapersthatdescriberelevantwork.IapologizetothoseauthorswhoseworkIwasunabletoincludeinthearticle.EnsemblesofClassifiersThefirsttopicconcernsmethodsforimprovingaccuracyinsupervisedlearning.Ibeginbyintroducingsomenotation.Insupervisedlearning,alearningprogramisgiventrainingexamplesoftheform{x1,y1,,xm,ym}forsomeunknownfunctionyfx.Thexivaluesaretypicallyvectorsoftheformwhosecomponentsarediscreteorrealvalued,suchasheight,weight,color,andage.ThesearealsocalledthefeatureofXi,IusethenotationXijto.referto2thejthfeatureofXi.Insomesituations,Idroptheisubscriptwhenitisimpliedbythecontext.Theyvaluesaretypicallydrawnfromadiscretesetofclasses{1,,k}inthecaseofclassificationorfromthereallineinthecaseofregression.Inthisarticle,Ifocusprimarilyonclassification.Thetrainingexamplesmightbecorruptedbysomerandomnoise.GivenasetSoftrainingexamples,alearningalgorithmoutputsaclassifier.Theclassifierisahypothesisaboutthetruefunctionf.Givennewxvalues,itpredictsthecorrespondingyvalues.Idenoteclassifiersbyh1,，hi.Anensembleofclassifierisasetofclassifierswhoseindividualdecisionsarecombinedinsomewaytypicallybyweightedorunweightedvotingtoclassifynewexamples.Oneofthemostactiveareasofresearchinsupervisedlearninghasbeenthestudyofmethodsforconstructinggoodensemblesofclassifiers.Themaindiscoveryisthatensemblesareoftenmuchmoreaccuratethantheindividualclassifiersthatmakethemup.AnensemblecanbeemoreaccuratethanitscomponentclassifiersonlyiftheindividualclassifiersdisagreewithoneanotherHansenandSalamon1990.Toseewhy,imaginethatwehaveanensembleofthreeclassifiers{h1,h2,h3},andconsideranewcasex.Ifthethreeclassifiersareidentical,thenwhenh1xiswrong,h2xandh3xarealsowrong.However,iftheerrorsmadebytheclassifiersareuncorrelated,thenwhenh1xiswrong,h2xandh3xmightbecorrect,sothatamajorityvotecorrectlyclassifiesx.Moreprecisely,iftheerrorratesofLhypotheseshiareallequaltopL/2andiftheerrorsareindependent,thentheprobabilitythatbinomialdistributionwheremorethanL/2hypothesesarewrong.Figure1showsthisareaforasimulatedensembleof21hypotheses,eachhavinganerrorrateof0.3.Theareaunderthecurvefor11ormorehypothesesbeingsimultaneouslywrongis0.026,whichismuchlessthantheerrorrateoftheindividualhypotheses.Ofcourse,iftheindividualhypothesesmakeuncorrelatederrorsatratesexceeding0.5,thentheerrorrateofthevotedensembleincreasesasaresultofthevoting.Hence,thekeytosuccessfulensemblemethodsistoconstructindividualclassifierswitherrorratesbelow0.5whoseerrorsareatleastsomewhatuncorrelated.MethodsforConstructingEnsemblesManymethodsforconstructingensembleshavebeendeveloped.Somemethodsaregeneral,andtheycanbeappliedtoanylearningalgorithm.Othermethodsarespecifictoparticularalgorithms.Ibeginbyreviewingthegeneraltechniques.SubsamplingtheTrainingExamplesThefirstmethodmanipulatesthetrainingexamplestogeneratemultiple3hypotheses.Thelearningalgorithmisrunseveraltimes,eachtimewithadifferentsubsetofthetrainingexamples.Thistechniqueworksespeciallywellforunstablelearningalgorithmsalgorithmswhoseoutputclassifierundergoesmajorchangesinresponsetosmallchangesinthetrainingdata.Decisiontree,neuralnetwork,andrulelearningalgorithmsareallunstable.Linearregression,nearestneighbor,andlinearthresholdalgorithmsaregenerallystable.Themoststraightforwardwayofmanipulatingthetrainingsetiscalledbagging.Oneachrun,baggingpresentsthelearningalgorithmwithatrainingsetthatconsistofasampleofmtrainingexamplesdrawnrandomlywithreplacementfromtheoriginaltrainingsetofmitems.Suchatrainingsetiscalledabootstrapreplicateoftheoriginaltrainingset,andthetechniqueiscalledbootstrapaggregationBreiman1996a.Eachbootstrapreplicatecontains,ontheaverage,63.2percentoftheoriginalset,withseveraltrainingexamplesappearingmultipletimes.Anothertrainingsetsamplingmethodistoconstructthetrainingsetsbyleavingoutdisjointsubsets.Then,10overlappingtrainingsetscanbedividedrandomlyinto10disjointsubsets.Then,10overlappingtrainingsetscanbeconstructedbydroppingoutadifferentisusedtoconstructtrainingsetsfortenfoldcrossvalidationso,ensemblesconstructedinthiswayaresometimescalledcrossvalidatedcommitteesParmanto,Munro,andDoyle1996.ThethirdmethodformanipulatingthetrainingsetisillustratedbytheADABOOSTalgorithm,developedbyFreundandSchapire1996,1995andshowninfigure2.Likebagging,ADABOOSTmanipulatesthetrainingexamplestogeneratemultiplehypotheses.ADABOOSTmaintainsaprobabilitydistributionpixoverthetrainingexamples.Ineachiterationi,itdrawsatrainingsetofsizembysamplingwithreplacementaccordingtotheprobabilitydistributionpix.Thelearningalgorithmisthenappliedtoproduceaclassifierhi.Theerrorrate￡iofthisclassifieronthetrainingexamplesweightedaccordingtopixiscomputedandusedtoadjusttheprobabilitydistributiononthetrainingexamples.Infigure2,notethattheprobabilitydistributionisobtainedbynormalizingasetofweightswiioverthetrainingexamples.Theeffectofthechangeinweightsistoplacemoreweightonexamplesthatweremisclassifiedbyhiandlessweightonexamplesthatwerecorrectlyclassified.Insubsequentiterations,therefore,ADABOOSTconstructsprogressivelymoredifficultlearningproblems.Thefinalclassifier,hiisconstructsbyaweightedvoteoftheindividualclassifiers.Eachclassifierisweightedaccordingtoitsaccuracyforthedistributionpithatitwastrainedon.Inline4oftheADABOOSTalgorithmfigure2,thebaselearningalgorithmLearniscalledwiththeprobabilitydistributionpi.IfthelearningalgorithmLearncanusethisprobabilitydistributiondirectly,4thenthisproceduregenerallygivesbetterresults.Forexample,Quinlan1996developedaversionofthedecisiontreelearningprogramc4.5thatworkswithaweightedtrainingsample.Hisexperimentsshowedthatitworkedextremelywell.OnecanalsoimagineversionsofbackpropagationthatscaledthecomputedoutputerrorfortrainingexampleXi,Yibytheweightpii.Errorsforimportanttrainingexampleswouldcauselargergradientdescentstepsthanerrorsforunimportantlowweightexamples.However,ifthealgorithmcannotusetheprobabilitydistributionpidirectly,thenatrainingsamplecanbeconstructedbydrawingarandomsamplewithreplacementinproportiontotheprobabilitiespi.ThisproceduremakesADABOOSTmorestochastic,butexperimentshaveshownthatitisstilleffective.Figure3comparestheperformanceofc4.5toc4.5withADABOOST.M1usingrandomsampling.Onepointisplottedforeachof27testdomainstakenfromtheIrvinerepositoryofmachinelearningdatabasesMerzandMurphy1996.Wecanseethatmostpointslieabovethelineyx,whichindicatesthattheerrorrateofADABOOSTislessthantheerrorrateofc4.5.Figure4comparestheperformanceofbaggingwithc4.5toc4.5alone.Again,weseethatbaggingproducessizablereductionsintheerrorrateofc4.5formanyproblems.Finally,figure5comparesbaggingwithboostingbothusingc4.5astheunderlyingalgorithm.Theresultsshowthatthetwotechniquesarecomparable,althoughboostingappearstostillhaveanadvantageoverbagging.Wecanseethatmostpointslieabovethelineyx,whichindicatesthattheerrorrateofADABOOSTislessthantheerrorrateofc4.5.Figure4comparestheperformanceofbaggingwithc4.5toc4.5alone.Again,weseethatbaggingproducessizablereductionsintheerrorrateofc4.5formanyproblems.Finally,figure5comparesbaggingwithboostingbothusingc4.5astheunderlyingalgorithm.Theresultsshowthatthetwotechniquesarecomparable,althoughboostingappearstostillhaveanadvantageoverbagging.ManipulatingtheInputFeaturesAsecondgeneraltechniqueforgeneratingmultipleclassifiersistomanipulatethesetofinputfeaturesavailabletothelearningalgorithm.Forexample,inaprojecttoidentifyvolcanoesonVenus,Cherkauer1996trainedensembleof32neuralnetworks.The32networkswerebasedon8differentsubsetsofthe119availableinputfeaturesand4differentnetworksizes.TheinputfeaturessubsetswereselectedbyhandtogroupfeaturesthatwerebasedondifferentimageprocessingoperationssuchasprincipalcomponentanalysisandthefastFouriertransform.Theresultingensembleclassifierwasabletomatchtheperformanceofhumanexpertsinidentifyingvolcanoes.TumerandGhosh1996appliedasimilartechniquetoasonardatasetwith25inputfeatures.However,theyfound
个人主页