The Design and Analysis of Benchmark Experiments

Torsten Hothorn, Friedrich Leisch, Achim Zeileis, Kurt Hornik

Description

The Design and Analysis of Benchmark
Experiments
Torsten Hothorn Friedrich Leisch Achim Zeileis
Friedrich-Alexander-Universitat Technische Universitat Wien Wirtschaftsuniversitat Wien
Erlangen-Nurnberg
Kurt Hornik
Wirtschaftsuniversitat Wien
Abstract
The assessment of the performance of learners by means of benchmark experiments is an
established exercise. In practice, benchmark studies are a tool to compare the performance of
several competing algorithms for a certain learning problem. Cross-validation or resampling
techniques are commonly used to derive point estimates of the performances which are com-
pared to identify algorithms with good properties. For several benchmarking problems, test
procedures taking the variability of those point estimates into account have been suggested.
Most of the recently proposed inference procedures are based on special variance estimators
for the cross-validated performance.
We introduce a theoretical framework for inference problems in benchmark experiments
and show that standard statistical test procedures can be used to test for di erences in the
performances. The theory is based on well de ned distributions of performance measures
which can be compared with established tests. To demonstrate the usefulness in practice,
the theoretical results are applied to regression and classi cation benchmark studies based on
arti cial and real world data.
Keywords: model comparison, performance, hypothesis testing, cross-validation, bootstrap ...

Sujets

• Testudo
• Bootstrap Protocol
• North American A-5 Vigilante
• Direction générale de la Police nationale
• Sport aérien
• The Designers Republic

Informations

• Publié par: Misheg
• Nombre de lectures: 20
• Langue: English

Extrait

TheDesignandAnalysisofBenchmark Experiments TorstenHothornFriedrichLeischAchimZeileis Friedrich-Alexander-Universita ¨ tTechnischeUniversita ¨ tWienWirtschaftsuniversita ¨ tWien Erlangen-Nu ¨ rnberg KurtHornik Wirtschaftsuniversita ¨ tWien Abstract Theassessmentoftheperformanceoflearnersbymeansofbenchmarkexperimentsisan establishedexercise.Inpractice,benchmarkstudiesareatooltocomparetheperformanceof severalcompetingalgorithmsforacertainlearningproblem.Cross-validationorresampling techniquesarecommonlyusedtoderivepointestimatesoftheperformanceswhicharecom- paredtoidentifyalgorithmswithgoodproperties.Forseveralbenchmarkingproblems,test procedurestakingthevariabilityofthosepointestimatesintoaccounthavebeensuggested. Mostoftherecentlyproposedinferenceproceduresarebasedonspecialvarianceestimators forthecross-validatedperformance. Weintroduceatheoreticalframeworkforinferenceproblemsinbenchmarkexperiments andshowthatstandardstatisticaltestprocedurescanbeusedtotestfordifferencesinthe performances.Thetheoryisbasedonwelldefineddistributionsofperformancemeasures whichcanbecomparedwithestablishedtests.Todemonstratetheusefulnessinpractice, thetheoreticalresultsareappliedtoregressionandclassificationbenchmarkstudiesbasedon artificialandrealworlddata. Keywords:modelcomparison,performance,hypothesistesting,cross-validation,bootstrap. 1.Introduction Instatisticallearningwerefertoabenchmarkstudyastoanempiricalexperimentwiththeaim ofcomparinglearnersoralgorithmswithrespecttoacertainperformancemeasure.Thequality ofseveralcandidatealgorithmsisusuallyassessedbypointestimatesoftheirperformanceson somedatasetorsomedatageneratingprocessofinterest.Althoughnowadayscommonlyusedin theabovesense,theterm“benchmarking”hasitsrootingeology.Patterson(1992)describesthe originalmeaninginlandsurveyingasfollows: Abenchmarkinthiscontextisamark,whichwasmountedonarock,abuildingor awall.Itwasareferencemarktodefinethepositionortheheightintopographic surveyingortodeterminethetimefordislocation. Inanalogytotheoriginalmeaning,wemeasureperformancesinalandscapeoflearningalgo- rithmswhilestandingonareferencepoint,thedatageneratingprocessofinterest,inbenchmark experiments.Butincontrasttogeologicalmeasurementsofheightsordistancesthestatistical measurementsofperformancearenotsufficientlydescribedbypointestimatesastheyarein- fluencedbyvarioussourcesofvariability.Hence,wehavetotakethisstochasticnatureofthe measurementsintoaccountwhenmakingdecisionsabouttheshapeofouralgorithmlandscape, thatis,decidingwhichlearnerperformsbestonagivendatageneratingprocess. ThisisapreprintofanarticlepublishedinJournalofComputationalandGraphicalStatistics, Volume14,Number3,Pages675–699.Copyright c 2005AmericanStatisticalAssociation, InstituteofMathematicalStatistics,andInterfaceFoundationofNorthAmerica

2TheDesignandAnalysisofBenchmarkExperiments Theassessmentofthequalityofanalgorithmwithrespecttoacertainperformancemeasure, forexamplemisclassificationormeansquarederrorinsupervisedclassificationandregression, hasbeenaddressedinmanyresearchpapersofthelastthreedecades.Theestimationofthe generalisationerrorbymeansofsomeformofcross-validationstartedwiththepioneeringwork ofStone(1974)andmajorimprovementswerepublishedbyEfron(1983,1986)andEfronand Tibshirani(1997);foranoverviewwerefertoSchiavoandHand(2000).Thetopicisstilla matterofcurrentinterest,asindicatedbyrecentempirical(WolpertandMacready1999;Bylander 2002),algorithmic(BlockeelandStruyf2002)andtheoretical(DudoitandvanderLaan2005) investigations. However,themajorgoalofbenchmarkexperimentsisnotonlytheperformanceassessmentof differentcandidatealgorithmsbuttheidentificationofthebestamongthem.Thecomparisonof algorithmswithrespecttopointestimatesofperformancemeasures,forexamplecomputedvia cross-validation,isanestablishedexercise,atleastamongstatisticiansinfluencedbythe“algo- rithmicmodellingculture”(Breiman2001b).Infact,manyofthepopularbenchmarkproblems firstcameupinthestatisticalliterature,suchastheOzoneandBostonHousingproblems(by BreimanandFriedman1985).Friedman(1991)contributedthestandardartificialregressionprob- lems.OtherwellknowndatasetslikethePimaindiandiabetesdataortheforensicglassproblem playamajorroleintextbooksinthisfield(e.g.,Ripley1996).Furtherexamplesarerecentbench- markstudies(asforexampleMeyer,Leisch,andHornik2003),orresearchpapersillustratingthe gainsofrefinementstothebaggingprocedure(Breiman2001a;HothornandLausen2003). However,theproblemofidentifyingasuperioralgorithmisstructurallydifferentfromtheper- formanceassessmenttask,althoughwenoticethatasymptoticargumentsindicatethatcross- validationisabletoselectthebestalgorithmwhenprovidedwithinfinitivelylargelearningsamples (DudoitandvanderLaan2005)becausethevariabilitytendstozero.Anyway,thecomparison ofrawpointestimatesinfinitesamplesituationsdoesnottaketheirvariabilityintoaccount,thus leadingtouncertaindecisionswithoutcontrollinganyerrorprobability. Whilemanysolutionstotheinstabilityproblemsuggestedinthelastyearsareextremelysuc- cessfulinreducingthevarianceofalgorithmsbyturningweakintostronglearners,especially ensemblemethodslikeboosting(FreundandSchapire1996),bagging(Breiman1996a)orrandom forests(Breiman2001a),thevariabilityofperformancemeasuresandassociatedtestprocedures hasreceivedlessattention.Thetaxonomyofinferenceproblemsinthespecialcaseofsupervised classificationproblemsdevelopedbyDietterich(1998)ishelpfultodistinguishbetweenseveral problemclassesandapproaches.Foradatageneratingprocessunderstudy,wemayeitherwant toselectthebestoutofasetofcandidatealgorithmsortochooseoneoutofasetofpredefined fittedmodels(“classifiers”).Dietterich(1998)distinguishesbetweensituationswherewearefaced withlargeorsmalllearningsamples.Standardstatisticaltestproceduresareavailableforcompar- ingtheperformanceoffittedmodelswhenanindependenttestsampleisavailable(questions3and 4inDietterich1998)andsomebenchmarkstudiesrestrictthemselvestothoseapplications(Bauer andKohavi1999).Theproblemwhethersomeoutofasetofcandidatealgorithmsoutperformall othersinalarge(question7)andsmallsamplesituation(question8)iscommonlyaddressedby thederivationofspecialvarianceestimatorsandassociatedtests.Estimatesofthevariabilityof thenaivebootstrapestimatorofmisclassificationerroraregiveninEfronandTibshirani(1997). Someproceduresforsolvingquestion8suchasthe5 × 2cvtestaregivenbyDietterich(1998), furtherinvestigatedbyAlpaydin(1999)andappliedinabenchmarkstudyonensemblemethods (Dietterich2000).Pizarro,Guerrero,andGalindo(2002)suggesttousesomeclassicalmultiple testproceduresforsolvingthisproblem.Mixedmodelsareappliedforthecomparisonofalgo- rithmsacrossbenchmarkproblems(forexampleLim,Loh,andShih2000;KimandLoh2003).A basicproblemcommontotheseapproachesisthatthecorrelationbetweeninternalperformance estimates,suchasthosecalculatedforeachfoldink-foldcross-validation,violatestheassumption ofindependence.Thisfactiseitherignoredwhenthedistributionofnewlysuggestedteststatistics underthenullhypothesisofequalperformancesisinvestigated(forexampleinDietterich1998; Alpaydin1999;VehtariandLampinen2002)orspecialvarianceestimatorstakingthiscorrelation intoaccountarederived(NadeauandBengio2003). Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

TorstenHothorn,FriedrichLeisch,AchimZeileis,KurtHornik3 Inthispaper,weintroduceasoundandflexibletheoreticalframeworkforthecomparisonofcan- didatealgorithmsandalgorithmselectionforarbitrarylearningproblems.Theapproachtothe inferenceprobleminbenchmarkstudiespresentedhereisfundamentallydifferentfromthepro- cedurescitedabove:Weshowhowonecansamplefromawelldefineddistributionofacertain performancemeasure,conditionalonadatageneratingprocess,inanindependentway.Conse- quently,standardstatisticaltestprocedurescanbeusedtotestmanyhypothesesofinterestin benchmarkstudiesandnospecialpurposeproceduresarenecessary.Thedefinitionofappropriate samplingproceduresmakesspecial“aposteriori”adjustmentstovarianceestimatorsunnecessary. Moreover,norestrictionsoradditionalassumptions,neithertothecandidatealgorithms(likelin- earityinvariableselection,seeGeorge2000,foranoverview)nortothedatageneratingprocess arerequired. ThroughoutthepaperweassumethatalearningsampleofnobservationsL= { z 1 ,...,z n } is givenandasetofcandidatealgorithmsaspotentialproblemsolversisavailable.Eachofthose candidatesisatwostepalgorithma:Inthefirststepamodelisfittedbasedonalearningsample Lyieldingafunctiona( ∙| L)which,inasecondstep,canbeusedtocomputecertainobjectsof interest.Forexample,inasupervisedlearningproblem,thoseobjectsofinterestarepredictions oftheresponsebasedoninputvariablesor,inunsupervisedsituationslikedensityestimation, a( ∙| L)mayreturnanestimateddensity. Whenwesearchforthebestsolution,thecandidatesneedtobecomparedbysomeproblemspecific performancemeasure.Suchameasuredependsonthealgorithmandthelearningsampledrawn fromsomedatageneratingprocess:Thefunctionp(a,L)assessestheperformanceofthefunction a( ∙| L),thatistheperformanceofalgorithmabasedonlearningsampleL.SinceLisarandom learningsample,p(a,L)isarandomvariablewhosevariabilityisinducedbythevariabilityof learningsamplesfollowingthesamedatageneratingprocessas L . Itisthereforenaturaltocomparethedistributionoftheperformancemeasureswhenweneedto decidewhetheranyofthecandidatealgorithmsperformssuperiortoalltheothers.Theideais todrawindependentrandomsamplesfromthedistributionoftheperformancemeasureforan algorithmabyevaluatingp(a, L ),wherethelearningsample L followsaproperlydefineddata generatingprocesswhichreflectsourknowledgeabouttheworld.Byusingappropriateandwell investigatedstatisticaltestproceduresweareabletotesthypothesesaboutthedistributionsofthe performancemeasuresofasetofcandidatesand,consequently,weareinthepositiontocontrol theerrorprobabilityoffalselydeclaringanyofthecandidatesasthewinner. WederivethetheoreticalbasisofourproposalinSection2andfocusonthespecialcaseof regressionandclassificationproblemsinSection3.Onceappropriaterandomsamplesfromthe performancedistributionhavebeendrawn,theestablishedstatisticaltestandanalysisprocedures canbeappliedandweshortlyreviewthemostinterestingoftheminSection4.Especially,we focusontestsforsomeinferenceproblemswhichareaddressedintheapplicationspresentedin Section5. 2.Comparingperformancemeasures Inthissectionweintroduceageneralframeworkforthecomparisonofcandidatealgorithms. Independentsamplesfromthedistributionsoftheperformancemeasuresaredrawnconditionally onthedatageneratingprocessofinterest.Weshowhowstandardstatisticaltestprocedurescan beusedinbenchmarkstudies,forexampleinordertotestthehypothesisofequalperformances. SupposethatBindependentandidenticallydistributedlearningsampleshavebeendrawnfrom somedatageneratingprocessDGP  L 1 =z 1 1 ,...,z n 1 ∼ DGP, .  L B =z 1 B ,...,z n B ∼ DGP, Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

4TheDesignandAnalysisofBenchmarkExperiments whereeachofthelearningsamplesL b (b=1,...,B)consistsofnobservations.Furthermorewe assumethatthereareK>1potentialcandidatealgorithmsa k (k=1,...,K)availableforthe solutionoftheunderlyingproblem.Foreachalgorithma k thefunctiona k ( ∙| L b )isbasedonthe observationsfromthelearningsampleL b .Hence,itisarandomvariabledependingonL b andhas itselfadistribution A k onthefunctionspaceofa k whichdependsonthedatageneratingprocess oftheL b : a k ( ∙| L b ) ∼A k (DGP),k=1,...,K. Foralgorithmsa k withdeterministicfittingprocedure(forexamplehistogramsorlinearmodels) thefunctiona k ( ∙| L b )isfixedwhereasforalgorithmsinvolvingnon-deterministicfittingorwhere thefittingisbasedonthechoiceofstartingvaluesorhyperparameters(forexampleneural networksorrandomforests)itisarandomvariable.Notethata k ( ∙| L b )isapredictionfunction thatmustnotdependonhyperparametersanymore:Thefittingprocedureincorporatesboth tuningaswellasthefinalmodelfittingitself. AssketchedinSection1,theperformanceofthecandidatealgorithma k whenprovidedwiththe learningsampleL b ismeasuredbyascalarfunctionp: p kb =p(a k , L b ) ∼P k = P k (DGP). Therandomvariablep kb followsadistributionfunction P k whichagaindependsonthedata generatingprocessDGP.Foralgorithmswithnon-deterministicfittingprocedurethisimplies thatitmaybeappropriatetointegratewithrespecttoitsdistribution A k whenevaluatingits performance. TheKdifferentrandomsamples { p k1 ,...,p kB } withBindependentandidenticallydistributed observationsaredrawnfromthedistributions P k (DGP)foralgorithmsa k (k=1,...,K).These performancedistributionscanbecomparedbybothexploratorydataanalysistoolsaswellas formalinferenceprocedures.Thenullhypothesisofinterestformostproblemsistheequalityof thecandidatealgorithmswithrespecttothedistributionoftheirperformancemeasureandcan beformulatedbywriting H 0 : P 1 = ∙∙∙ = P K . Inparticular,thishypothesisimpliestheequalityoflocationandvariabilityoftheperformances. Inordertospecifyanappropriatetestprocedureforthehypothesisaboveoneneedstodefinean alternativetotestagainst.Thealternativedependsontheoptimalitycriterionofinterest,which weassessusingascalarfunctionalφ:Analgorithma k isbetterthananalgorithma k 0 withrespect toaperformancemeasurepandafunctionalφiffφ( P k )<φ( P k 0 ).Theoptimalitycriterionmost commonlyusedisbasedonsomelocationparametersuchastheexpectationφ( P k )=E( P k )or themedianoftheperformancedistribution,thatis,theaverageexpectedloss.Inthiscaseweare interestedindetectingdifferencesinmeanperformances: H 0 :E( P 1 )= ∙∙∙ =E( P K )vs.H 1 : ∃ i,j ∈{ 1,...,K } :E( P i ) 6 =E( P j ). Otheralternativesmaybederivedfromoptimalitycriteriafocusingonthevariabilityoftheper- formancemeasures.Underanycircumstances,theinferenceisconditionalonthedatagenerating processofinterest.Examplesforappropriatechoicesofsamplingproceduresforthespecialcase ofsupervisedlearningproblemsaregiveninthenextsection. 3.Regressionandclassification Inthissectionweshowhowthegeneralframeworkfortestingtheequalityofalgorithmsderived intheprevioussectioncanbeappliedtothespecialbutimportantcaseofsupervisedstatistical learningproblems.Moreover,wefocusonapplicationsthatcommonlyoccurinpracticalsituations. Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

TorstenHothorn,FriedrichLeisch,AchimZeileis,KurtHornik5 3.1.Comparingpredictors Insupervisedlearningproblems,theobservationszinthelearningsampleareoftheformz=(y,x) whereydenotestheresponsevariableandxdescribesavectorofinputvariables.Theaimofthe learningtaskistoconstructpredictorswhich,basedoninputvariablesonly,provideuswith informationabouttheunknownresponsevariable.Consequently,thefunctionconstructedby eachoftheKcandidatealgorithmsisoftheformyˆ=a k (x | L b ).Inclassificationproblemsyˆmay bethepredictedclassforobservationswithinputxorthevectoroftheestimatedconditionalclass probabilities.Insurvivalanalysistheconditionalsurvivalcurveforobservationswithinputstatus xisofspecialinterest.Thediscrepancybetweenthetrueresponseyandthepredictedvalueyˆfor onesingleobservationismeasuredbyascalarlossfunctionL(y,yˆ). Theperformancemeasurepisdefinedbysomefunctionalµofthedistributionofthelossfunction andthedistributionofp kb dependsonthedatageneratingprocessDGPonly: ���


p kb =p(a k ,L b )=µLy,a k x | L b ∼P k (DGP). Consequently,therandomnessofz=(y,x)andtherandomnessinducedbyalgorithmsa k with non-deterministicfittingareremovedbyappropriateintegrationwithrespecttotheassociated distributionfunctions. Again,theexpectationisacommonchoiceforthefunctionalµunderquadraticlossL(y,yˆ)= (y − yˆ) 2 andtheperformancemeasureisgivenbythesocalledconditionalrisk ��

��

2 p kb =E a k E z=(y,x) Ly,a k x | L b =E a k E z=(y,x) y − a k x | L b ,(1) wherez=(y,x)isdrawnfromthesamedistributionastheobservationsinalearningsampleL. Otherconceivablechoicesofµarethemedian,correspondingtoabsoluteloss,oreventhesupre- mumortheoreticalquantilesofthelossfunctions. 3.2.Specialproblems Thedistributionsoftheperformancemeasure P k (DGP)foralgorithmsa k (k=1,...,K)depend onthedatageneratingprocessDGP.Consequently,thewaywedrawrandomsamplesfrom P k (DGP)isdeterminedbytheknowledgeaboutthedatageneratingprocessavailabletous.In supervisedlearningproblems,onecandistinguishtwosituations: • Eitherthedatageneratingprocessisknown,whichisthecaseinsimulationexperiments withartificiallygenerateddataorincaseswherewearepracticallyabletodrawinfinitively manysamples(e.g.,networkdata), • ortheinformationaboutthedatageneratingprocessisdeterminedbyafinitelearning sampleL.InthiscasetheempiricaldistributionfunctionofLtypicallyrepresentsthe completeknowledgeaboutthedatageneratingprocessweareprovidedwith. Inthefollowingweshowhowrandomsamplesfromthedistributionoftheperformancemeasure P k (DGP)foralgorithma k canbedrawninthreebasicproblems:Thedatageneratingprocessis known(simulation),alearningsampleaswellasatestsampleareavailable(competition)orone singlelearningsampleisprovidedonly(realworld).Specialchoicesofthefunctionalµappropriate ineachofthethreeproblemswillbediscussed. Thesimulationproblem Artificialdataaregeneratedfromsomedistributionfunction Z ,whereeachobservationz i (i= 1,...,n)inalearningsampleisdistributedaccordingto Z .ThelearningsampleLconsistsof nindependentobservationsfrom Z whichwedenotebyL ∼Z n .Inthissituationthedata generatingprocessDGP= Z n isused.ThereforeweareabletodrawasetofBindependent learningsamplesfrom Z n :L 1 ,...,L B ∼Z n .Weassesstheperformanceofeachalgorithma k Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

6TheDesignandAnalysisofBenchmarkExperiments onalllearningsamplesL b (b=1,...,B)yieldingarandomsampleofBobservationsfromthe performancedistribution P k ( Z n )bycalculating ���


p kb =p(a k ,L b )=µLy,a k x | L b ,b=1,...,B. Theassociatedhypothesisundertestisconsequently H 0 : P 1 ( Z n )= ∙∙∙ = P K ( Z n ). Ifwearenotabletocalculateµanalyticallywecanapproximateituptoanydesiredaccuracy bydrawingatestsampleT ∼Z m ofmindependentobservationsfrom Z wheremislargeand calculating ���


pˆ kb =pˆ(a k ,L b )=µ T Ly,a k x | L b . Hereµ T denotestheempiricalanalogueofµforthetestobservationsz=(y,x) ∈ T.Whenµis definedastheexpectationwithrespecttotestsampleszasin(1)(weassumeadeterministica k forthesakeofsimplicityhere),thisreducestothemeanofthelossfunctionevaluatedforeach observationinthelearningsample X

�� pˆ kb =pˆ(a k ,L b )=m − 1 Ly,a k x | L b . z=(y,x) ∈ T Analogously,thesupremumwouldbereplacedbythemaximumandtheoreticalquantilesbytheir empiricalcounterpart. Thecompetitionproblem Inmostpracticalapplicationsnopreciseknowledgeaboutthedatageneratingprocessisavailable butinsteadweareprovidedwithonelearningsampleL ∼Z n ofnobservationsfromsome distributionfunction Z .Theempiricaldistributionfunction Z ˆ n coversallknowledgethatwe haveaboutthedatageneratingprocess.Therefore,wemimicthedatageneratingprocessby usingtheempiricaldistributionfunctionofthelearningsample:DGP= Z ˆ n .Nowweareableto drawindependentandidenticallydistributedrandomsamplesfromthisemulateddatagenerating process.Inacompletelynon-parametricsetting,thenon-parametricorBayesianbootstrapcan beappliedhereor,iftherestrictiontocertainparametricfamiliesisappropriate,theparametric bootstrapcanbeusedtodrawsamplesfromthedatageneratingprocess.Foranoverviewofthose issueswerefertoEfronandTibshirani(1993). Undersomecircumstances,anadditionaltestsampleT ∼Z m ofmobservationsisgiven,for exampleinmachinelearningcompetitions.Inthissituation,theperformanceneedstobeassessed withrespecttoTonly.Again,wewouldliketodrawarandomsampleofBobservationsfrom P ˆ k ( Z ˆ n ),whichinthissetupispossiblebybootstrappingL 1 ,...,L B ∼Z ˆ n ,where P ˆ denotesthe distributionfunctionoftheperformancemeasureevaluatedusingT,thatis,theperformance measureiscomputedby ���


pˆ kb =pˆ(a k ,L b )=µ T Ly,a k x | L b whereµ T isagaintheempiricalanalogueofµforallz=(y,x) ∈ T.Thehypothesisweare interestedinis H 0 : P ˆ 1 ( Z ˆ n )= ∙∙∙ = P ˆ K ( Z ˆ n ), where P ˆ k correspondstotheperformancemeasureµ T .Sincetheperformancemeasureisdefined intermsofonesingletestsampleT,itshouldbenotedthatwemayfavouralgorithmsthatperform wellonthatparticulartestsampleTbutworseonothertestsamplesjustbychance. Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

TorstenHothorn,FriedrichLeisch,AchimZeileis,KurtHornik7 Therealworldproblem Themostcommonsituationweareconfrontedwithindailyroutineistheexistenceofonesingle learningsampleL ∼Z n withnodedicatedindependenttestsamplebeingavailable.Again,we mimicthedatageneratingprocessbytheempiricaldistributionfunctionofthelearningsample: DGP= Z ˆ n .WeredrawBindependentlearningsamplesfromtheempiricaldistributionfunction bybootstrapping:L 1 ,...,L B ∼Z ˆ n .Thecorrespondingperformancemeasureiscomputedby pˆ kb =pˆ(a k ,L b )=µˆ � L � y,a k � x | L b


whereµˆisanappropriateempiricalversionofµ.Therearemanypossibilitiesofchoosingµˆand themostobviousonesaregiveninthefollowing. Ifnislarge,onecandividethelearningsampleintoasmallerlearningsampleandatestsample L= { L 0 ,T } andproceedwithµ T asinthecompetitionproblem.Ifnisnotlargeenoughforthis tobefeasible,thefollowingapproachisafirstnaivechoice:Inthesimulationproblem,themodels arefittedonsamplesfrom Z n andtheirperformanceisevaluatedonsamplesfrom Z .Here,the modelsaretrainedonsamplesfromtheempiricaldistributionfunction Z ˆ n andsowecouldwant toassesstheirperformanceon Z ˆ whichcorrespondstoemulatingµ T byusingthelearningsample L astestsample,i.e.,foreachmodelfittedonabootstrapsample,theoriginallearningsample L itselfisusedastestsampleT. Exceptforalgorithmsabletocompute‘honest’predictionsfortheobservationsinthelearning sample(forexamplebagging’sout-of-bagpredictions,Breiman1996b),thischoiceleadstooverfit- tingproblems.Thosecanbeaddressedbywellknowncross-validationstrategies.Thetestsample Tcanbedefinedintermsoftheout-of-bootstrapobservationswhenevaluatingµ T : • RW-OOB.ForeachbootstrapsampleL b (b=1,...,B)theout-of-bootstrapobservations L \ L b areusedastestsample. Notethatusingtheout-of-bootstrapobservationsastestsampleleadstonon-independentob- servationsoftheperformancemeasure,however,theircorrelationvanishesasntendstoinfinity. Anotherwayistochooseacross-validationestimatorofµ: • RW-CV.EachbootstrapsampleL b isdividedintokfoldsandtheperformancepˆ kb isdefined astheaverageoftheperformancemeasureoneachofthosefolds.Sinceitispossiblethat oneobservationfromtheoriginallearningsampleLispartofboththelearningfoldsandthe validationfoldduetosamplingn-out-of-nwithreplacement,thoseobservationsareremoved fromthevalidationfoldinordertopreventanybias.Suchbiasmaybeinducedforsome algorithmsthatperformbetteronobservationsthatarepartofbothlearningsampleand testsample. Commontoallchoicesinthissetupisthatonesinglelearningsampleprovidesallinformation. Therefore,wecannotcomputethetheoreticalperformancemeasuresandhencecannottesthy- pothesesabouttheseasthiswouldrequiremoreknowledgeaboutthedatageneratingprocess. Thestandardapproachistocomputesomeempiricalperformancemeasure,suchasthosesug- gestedhere,insteadtoapproximatethetheoreticalperformance.Foranyempiricalperformance measure,thehypothesisneedstobeformulatedby H 0 : P ˆ 1 ( Z ˆ n )= ∙∙∙ = P ˆ K ( Z ˆ n ), meaningthattheinferenceisconditionalontheperformancemeasureunderconsideration. 4.Testprocedures Asoutlinedintheprevioussections,theproblemofcomparingKalgorithmswithrespecttoany performancemeasurereducestotheproblemofcomparingKnumericdistributionfunctionsor Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

8TheDesignandAnalysisofBenchmarkExperiments certaincharacteristics,suchastheirexpectation.Alotofattentionhasbeenpaidtothisand similarproblemsinthestatisticalliteratureandsoarichtoolboxcanbeappliedhere.Wewill commentonappropriatetestproceduresforonlythemostimportanttestproblemscommonly addressedinbenchmarkexperimentsandrefertothestandardliteratureotherwise. 4.1.Experimentaldesigns AmatchedpairsordependentKsamplesdesignisthemostnaturalchoiceforthecomparisonof algorithmssincetheperformanceofallKalgorithmsisevaluatedusingthesamerandomsamples L 1 ,...,L B .Wethereforeusethisdesignforthederivationsintheprevioussectionsandthe experimentsinSection5andcomparethealgorithmsbasedonthesamesetoflearningsamples. TheapplicationofanindependentKsampledesignmaybemorecomfortablefromastatistical pointofview.Especiallythederivationofconfidenceintervalsforparameterslikethedifferenceof themisclassificationerrorsoftwoalgorithmsorthevisualisationoftheperformancedistributions isstraightforwardintheindependentKsamplessetup. 4.2.Analysis Asensibleteststatisticforcomparingtwoperformancedistributionswithrespecttotheirlocations inamatchedpairsdesignisformulatedintermsoftheaveraged ¯ ofthedifferencesd b =p 1b − p 2b (b=1,...,B)fortheobservationsp 1b andp 2b ofalgorithmsa 1 anda 2 .Underthenullhypothesis ofequalityoftheperformancedistributions,thestudentizedstatistic ¯√ d t=B r �
(2) (B − 1) − 1P d b − d ¯ 2 b isasymptoticallynormalandfollowsat-distributionwithB − 1degreesoffreedomwhenthe differencesaredrawnfromanormaldistribution.Theunconditionaldistributionofthisand othersimilarteststatisticsisderivedundersomeparametricassumption,suchassymmetryor normality,aboutthedistributionsoftheunderlyingobservations.However,wedoubtthatsuch parametricassumptionstoperformancedistributionsareeverappropriate.Thequestionwhether conditionalorunconditionaltestproceduresshouldbeappliedhassomephilosophicalaspectsand isoneofthecontroversialquestionsinrecentdiscussions(seeBerger2000;Berger,Lunneborg, Ernst,andLevine2002,forexample).Inthecompetitionandrealworldproblemshowever,the inferenceisconditionalonanobservedlearningsampleanyway,thusconditionaltestprocedures, wherethenulldistributionisdeterminedfromthedataactuallyseen,arenaturaltouseforthetest problemsaddressedhere.Sinceweareabletodrawasmanyrandomsamplesfromtheperformance distributionsundertestasrequired,theapplicationoftheasymptoticdistributionofthetest statisticsofthecorrespondingpermutationtestsispossibleincaseswherethedeterminationof theexactconditionaldistributionisdifficult. MaybethemostprominentproblemistotestwhetherK>2algorithmsperformequallywell againstthealternativethatatleastoneofthemoutperformsallothercandidates.Inadependent Ksamplesdesign,theteststatistic 2 !  PPP B − 1 pˆ kb − (BK) − 1 pˆ kb b,kbk t ? =  ! 2 (3) PPPP pˆ kb − K − 1 pˆ kb − B − 1 pˆ kb +(BK) − 1 pˆ kb k,bkbk,b canbeusedtoconstructapermutationtest,wherethedistributionoft ? isobtainedbypermuting thelabels1,...,KofthealgorithmsforeachsampleL b (b=1,...,B)independently(Pesarin 2001). Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

TorstenHothorn,FriedrichLeisch,AchimZeileis,KurtHornik9 OncetheglobalhypothesisofequalityofK>2performancescouldberejectedinadependent Ksamplesdesign,itisofspecialinteresttoidentifythealgorithmsthatcausedtherejection. Allpartialhypothesescanbetestedatlevelαfollowingtheclosedtestingprinciple,wherethe hierarchicalhypothesesformulatesubsetsoftheglobalhypothesisandcanbetestedatlevelα, foradescriptionseeHochbergandTamhane(1987).However,closedtestingproceduresarecom- putationallyexpensiveformorethanK=4algorithms.Inthiscase,onecanapplysimultaneous testproceduresorconfidenceintervalsdesignedfortheindependentKsamplescasetothealigned performancemeasures(Ha´jek,S ˇ ida´k,andSen1999). Itisimportanttonotethatoneisabletodetectverysmallperformancedifferenceswithveryhigh powerwhenthenumberoflearningsamplesBislarge.Therefore,practicalrelevanceinsteadof statistialsignificanceneedstobeassessed,forexamplebyshowingrelevantsuperioritybymeans ofconfidenceintervals.FurthercommentsonthoseissuescanbefoundinSection6. 5.Illustrationsandapplications AlthoughthetheoreticalframeworkpresentedinSections2and3coversawiderrangeofapplica- tions,werestrictourselvestoafewexamplesfromregressionandclassificationinordertoillustrate thebasicconcepts.AsoutlinedinSection3.2,thedegreeofknowledgeaboutthedatagenerating processavailabletotheinvestigatordetermineshowwellwecanapproximatethetheoreticalper- formancebyusingempiricalperformancemeasures.Forsimpleartificialdatageneratingprocesses fromaunivariateregressionrelationshipandatwo-classclassificationproblemwewillstudythe poweroftestsbasedontheempiricalperformancemeasuresforthesimulation,competitionand realworldproblems. Maybethemostinterestingquestionaddressedinbenchmarkingexperimentsis“Arethereany differencesbetweenstate–of–the–artalgorithmswithrespecttoacertainperformancemeasure?”. Fortherealworldproblemweinvestigatethisforsomeestablishedandrecentlysuggestedsuper- visedlearningalgorithmsbymeansofthreerealworldlearningsamplesfromtheUCIrepository (BlakeandMerz1998).AllcomputationswereperformedwithintheRsystemforstatistical computing(IhakaandGentleman1996;RDevelopmentCoreTeam2004),version1.9.1. 5.1.Nestedlinearmodels Inordertocomparethemeansquarederroroftwonestedlinearmodelsconsiderthedatagener- atingprocessfollowingaunivariateregressionequation y=β 1 x+β 2 x 2 +ε(4) wheretheinputxisdrawnfromauniformdistributionontheinterval[0,5]andtheerrorterms areindependentrealisationsfromastandardnormaldistribution.Wefixtheregressioncoefficient β 1 =2andthenumberofobservationsinalearningsampleton=150.Twopredictivemodels arecompared: • a 1 :asimplelinearregressiontakingxasinputandthereforenotincludingaquadraticterm dna • a 2 :asimplequadraticregressiontakingbothxandx 2 asinputs.Consequently,theregres- sioncoefficientβ 2 isestimated. Thediscrepancybetweenapredictedvalueyˆ=a k (x | L),k=1,2andtheresponseyismeasured bysquarederrorlossL(y,yˆ)=(y − yˆ) 2 . Basically,weareinterestedtocheckifalgorithma 1 performsbetterthanalgorithma 2 forvalues ofβ 2 varyinginarangebetween0and0.16.AsdescribedindetailinSection3.2,boththe performancemeasureandthesamplingfromtheperformancedistributiondependonthedegree Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica

01TheDesignandAnalysisofBenchmarkExperiments SimulationCompetitionRealWorld β 2 m=2000m=150OOBOOB-2nCV 0.0000.0000.0000.0720.0540.0590.054 0.0200.0290.2870.1860.1140.1740.109 0.0400.8350.6090.4510.2970.4990.279 0.0600.9970.7640.6830.5540.8400.523 0 0 . . 0 1 8 0 0 0 1 1 . . 0 0 0 0 0 00 0 . . 9 8 3 7 3 5 0 0 . . 9 8 1 3 2 3 0 0 . . 9 7 2 7 5 8 0 0 . . 9 9 9 7 7 3 0 0 . . 9 7 2 7 6 7 0.1201.0000.9710.9530.9841.0000.978 0.1401.0000.9880.9810.9961.0000.996 0.1601.0000.9970.9901.0001.0001.000 w Ta or b l l d e p 1 r : ob R le eg m r s es f s o i r on va e ry x i p n e g ri v m al e u n e t s s: of P t o h w e e r r eg o r f es t s h i e on te c s o t e s ffi fo ci r en t t he β 2 si o m f u t l h a e tio q n u , ad c r o a m ti p c e t t e it r i m o . n L a e n a d rn r i e n a g l samplesareofsizen=150. ofknowledgeavailableandwethereforedistinguishbetweenthreedifferentproblemsdiscussed above. Simulation ThedatageneratingprocessZ n isknownbyequation(4)andweareabletodrawasmanylearning samplesofn=150observationsaswewouldlike.Itis,inprinciple,possibletocalculatethemean squarederrorofthepredictivefunctionsa 1 ( ∙| L b )anda 2 ( ∙| L b )whenlearningsampleL b was observed.Consequently,weareabletoformulatethetestproblemintermsoftheperformance distributiondependingonthedatageneratingprocessinaone-sidedway: H 0 :E( P 1 ( Z n )) ≤ E( P 2 ( Z n ))vs.H 1 :E( P 1 ( Z n ))>E( P 2 ( Z n )).(5) However,closedformsolutionsareonlypossibleinverysimplecasesandwethereforeapproximate P k ( Z n )by P ˆ k ( Z n )usingalargetestsampleT,inourcasewithm=2000observations.Some algebrashowsthat,forβ 2 =0andmodela 1 ,thevarianceoftheperformanceapproximatedbya testsampleofsizemisV(p b1 )=m − 1 (350/3 ∙ (2 − β ˆ 1 ) 4 +25/2 ∙ (2 − β ˆ 1 ) 2 +2).Inordertostudy thegoodnessoftheapproximationwe,inaddition,chooseasmallertestsamplewithm=150. Notethatinthissetuptheinferenceisconditionalunderthetestsample. Competition WearefacedwithalearningsampleLwithn=150observations.Theperformanceofany algorithmistobemeasuredbyanadditionaltestsampleTconsistingofm=150observations. Again,theinferenceisconditionalundertheobservedtestsampleandwemay,justbychance, observeatestsamplefavouringaquadraticmodelevenifβ 2 =0.Thedatageneratingprocess isemulatedbytheempiricaldistributionfunctionDGP= Z ˆ n andweresamplebyusingthe non-parametricbootstrap. RealWorld Mostinterestingandmostcommonisthesituationwheretheknowledgeaboutthedatagenerating processiscompletelydescribedbyonesinglelearningsampleandthenon-parametricbootstrap isusedtoredrawlearningsamples.Severalperformancemeasuresarepossibleandweinvesti- gatethosebasedontheout-of-bootstrapobservations(RW-OOB)andcross-validation(RW-CV) suggestedinSection3.2.Forcross-validation,theperformancemeasureisobtainedfroma5-fold cross-validationestimator.Eachbootstrapsampleisdividedintofivefoldsandthemeansquared erroroneachofthesefoldsisaveraged.Observationswhichareelementsoftrainingandvali- dationfoldareremovedfromthelatter.Inaddition,wecomparetheout-of-bootstrapempirical Copyright c2005AmericanStatisticalAssociation,InstituteofMathematicalStatistics,andInterface FoundationofNorthAmerica