Expected error analysis for model selection

ExpectedErrorAnalysisforModelSelectionTobiasScheer1andThorstenJoachims2July13,19991OttovonGuerickeUniversity,FIN/IWS,Universitatsplatz2,39106Magdeburg,Germany,[e-mail][phone]UniversitaetDortmund,LSVIII/ComputerScience,44221Dortmund,[e-mail]tagoodhypothesislanguage(ormodel)fromacollectionofpossiblemodels,onehastoassessthegeneralizationperformanceofthehypothesiswhichisre-turnedbyalearnerthatisboundtousesomeparticularmodel.Thispaperdealswithanewandveryecientwayofassessingthisgeneralizationperformance.Wepresentanewanalysiswhichcharacterizestheexpectedgeneralizationerrorofthehypothesiswithleasttrainingerrorintermsofthedistributionoferrorratesofthehypothesesinthemodel.Thisdistributioncanbeestimatedveryecientlyfromthedatawhichim-mediatelyleadstoanecientmodelselectionalgorithm.Theanalysispredictslearningcurveswithaveryhighprecisionandthuscontributestoabetterunderstandingofwhyandwhenover-ttingoccurs.Wepresentempiricalstudies(controlledexperimentsonBooleandecisiontreesandalarge-scaletextcategorizationproblem)whichshowthatthemodelselectionalgorithmleadstoerrorrateswhichareoftenaslowasthoseobtainedby10-foldcrossvalidation(sometimesevensuperior).However,thealgorithmismuchmoreecient(becausethelearnerdoesnothavetobeinvokedatall)andthussolvesmodelselectionproblemswithasmanyasthousandrelevantattributesand12,000examples.AshortversionofthispaperappearedattheInternationalConferenceonMachineLearn-ing,1999.11IntroductionInthesettingofclassicationlearningwhichwestudyinthispaper,thetaskofalearneristoapproximateajointdistributiononinstancesandclasslabelsaswellaspossible.Ahypothesisisamappingfrominstancestoclasslabels;the(generalization,ortrue)errorrateofahypothesishisthechanceofdrawingapairofaninstancexandaclasslabely(whendrawingaccordingtothesoughttargetdistribution)suchthatthehypothesisconjecturesaclasslabelh(x)whichisdistinctfromthe\correctclasslabely.Thiserrorrate(alsoreferredtoasthezero-oneloss)isthequantitywhichwewishtominimize.Unfortunately,however,wecannotdeterminetheerrorratebecausethetargetdistributionisnotknowntothelearner.Instead,thelearnerisabletoperceiveasample(i.e.,asetofpairs(xi;yi)ofxedsize)whichisdrawnaccordingtothetargetdistributionandwhichallowsustodenetheempiricalerrorrateofahypothesiswhichisthefrequencyofmisclassicationswithrespecttothesample.Thelearnerisprovidedasampleandisconstrainedtoamodel{asetofpotentiallyavailablehypotheses{andcanminimizetheempiricalerrorratewithinthatmodel.Onecanthinkofthemodelasaparametricschemeforahypothesiswhileanindividualhypothesisisafullyparameterizedmodel.Amodelmight,forinstance,consistofalldecisiontreesofdepththree,orofallback-propagationnetworkswithacertainxedarchitecture.Forthelatterexample,theback-propagationalgorithmwouldbealearnerthatminimizestheempiricalerrorratewithinthatmodel.Thechoiceofthemodeltowhichweconstrainthelearnerhasaverystrongimpactontheerrorrateofthehypothesisthatthelearnerwilldeliver.Forexample,ifwerestrictourlearnertodecisiontreesofdepthonethen,formostlearningproblems,wecanexpecteventhebesthypothesisinthatmodeltoincurbothahighempiricalerrorrateandahightrueerrorrate.Ontheotherhand,fromourunderstandingofPAC-andVC-styleerrorboundsweknowthatalowempiricalerrorratedoesnotimplythatthetrueerrorrateisalsolowwhenthemodelisverylarge(orcomplex,respectively).Whenweconsiderverymanydistincthypotheses,thechancethatatleastoneofthemhappenstoincuralowempiricalerrorrate(althoughitstrueerrorrateishigh)growsrapidly.Therefore,intheworstcase,theerrorrateofevenanapparentlygoodhypothesismightbelarge.Theproblemofselectingamodelthatwillleadtoalowerrorrateoftheresultinghypothesisisreferredtoasmodelselectionanditisintimatelyrelatedtotheproblemofestimatingtheerrorrateofahypothesis.Forourback-propagationexample,onepossiblemodelselectionproblemwouldbetodeterminethenumberofhiddenunitsthatleadstooptimalgeneralization.Fordecisiontrees,possiblemodelselectionproblemswouldbetodeterminethesubsetoftheavailableattributes,orthedepthorstructureofatreethatimposesanoptimalgeneralizationperformance.Threedistinctclassesofapproachestothemodelselectionproblemscanbedistinguished:(Foramoredetaileddiscussionoftheseapproaches,wereferthereadertoSection6.1.)Hold-outtesting,orcrossvalidationalgorithms(e.g.,Mosier,1951;Toussaint,1974;Kohavi&John,1997)useindependentsamplesthathavenotbeenusedfortrainingtocomparetheapparentlybesthypothesesofeachconsideredmodel.Crossvalidationhasproventobeaverygeneralandreliablemodelselectionalgorithmbutrequiresrepeatedinvocationsofthelearnerforeachmodelwhichmay,forlarge-scaleapplications,requireaprohibitivelylargeamountofcomputation.Bycontrast,complexitypenalizationalgorithms(e.g.,Cunetal.,1989;Mingers,1989;Vapnik,1998)trytoestimatethetrueerrorratebasedononlytheempiricalerrorrateandsomecomplexitymeasureofthemodel.Unfortunately,thisinformationdoesnotsucetoactuallydeterminethegeneralizationerrorrateandtherefore2complexitypenalizationalgorithmshavetoconjecturehowtheerrorratemightgrowwiththemode