算法选择问题-抽象模型

providedbyPurdueE-Viewmetadata,citationandsimilarpapersat broughttoyoubyprovidedbyPurdueE-PurduePurduee-DepartmentofComputerScienceTechnical

DepartmentofComputerJohnR.PurdueUniversity,Report74-Rice,JohnR.,"TheAlgorithmSelectionProblem—AbstractModels"(1974).DepartmentofComputerScienceTechnicalReports.Paper68.ThisdocumenthasbeenmadeavailablethroughPurduee-Pubs,aserviceofthePurdueUniversityLibraries.Pleasecontactepubs@foradditionalinformation.＼＼THEALGORITHMSELECTIONPROBLEM-ABSTRACTJohnR,ComputerScienceDepart亚ntPurdueUniversityWestLafayette,Indiana CSD-TR1 Theproblemofselectinganeffectiveorgoodorbestalgorithmarisesinawidevarietyofsituations, Thecontextofthesesituationsoftenobscuresthecommonfeaturesofthisselectionproblemandthepurposeofthisreportistoformulateabstractmodelsappropriateforconsideringit, Withintheframeworkestablishedbythesemodelswepresentavarietyofqueationsthatcan(andusuallyshould)beaskedinanyspecificapplication,1Itshouldbemadeclearthatwedonotbelievetha七theaemodelswillleaddirectly(bysimplespecialization)tosuperiorselectionprocedures,Thiswill alwaysrequireexploitationofthespecificnatureofthesitua­tionathand. Evenso, wedobelievethatthesemodelswillclarifytheconsiderationofthisproblemand,inparticular,showthatsomeapproachesusedarebasedonnaiveass皿ptionsabou亡theselectionassumption,Thisisthefirstofa'seriesofreportswhichconsiderthefollow土ngAbetract沁ConcreteNumericalAnalysis-SelectionofQuadratureAlgorithmsOperatingSystems-SelectionofSchedulingAlgorithmsArtificialIntelligence-LearningAlgorithmsApproximationTheoryforSelectionProceduresComputationofSelectionProceduresThethreeconcreteexampleswhichthereadercanusetointerprettheabstractionsinthisreportmaybesummarizedasfollows: Oneisgivenafunctionf(x),,aninterval[a,b]andtolerancee> OneistoselectanalgorithmtoJbf(x)dxwhichisefficient(usesfewevaluationsoff(x))andreliableanestimatewithinthespecifiedo: Oneisgivenanenvironmentforalargecomputeroperation, Informationknownj;ncludesthemixofjobsbetweenbatch,interactiveandsemi-interactive,somebasiccharacteristicsoftheseclassesofjobsandthecharacteristicsofthecomputeroperation. Oneistoselectanalgorithmtoscheduletheexecutionofthesejobswhichpro-duce(a)highbatchthroughput,(b)goodresponsetointeractivejobs,(c)goodservicetosemi-inte0activejobsand(d)highpriorityArtificial互t斗上拉竺：OneisgivenadescriptionofthegameTic-Tac- Oneistoselectanalgorithmtoplaythegamewhicheffective,i,e,neverlosesandwinswheneveranopponent'smistake

Aselectionprocedureisinvariablyobtainedbyassigningvalues22parametersingeneral"form". Moreprecisely,theselectionprocedure isanalgorithmandaspecificclassischosenwithfreeparametersandtheseparametersarethenchosensoastosatisfy(aswellastheycan)theobjectivesoftheselectionproblem. Classicalformsincludethingslikepolynomials(withcoefficientsasparameters)andlinearmappings(withmatrixcoefficientsorweightsasparameters). Otherrelevantformsaredecisiontrees(withsize,shapeandindividualdecisionelementsaaparameters)andprogram•(withvariousprogramelementsasparameters).ThemodelspresentedhereareprimarilyaimedatalgorithmproblemswiththefollowingthreeProblemS巴竺．：Thesetofproble画involvedisverylargeandquite Thissetisofhighdimensioninthesenaethatthereareanumberofindependentcharacteristicsoftheproblemswhichareimportan七forthealgor扛血selectionandperformance. Thereiausuallyconsiderablyun-cer七aintyabouttheaecharacteristic•andtheir3 :Thesetofalgorithmsthatneedstobe3islargeanddiverse. Ideallytheremaybemillionsofalgorithmsandprac­ticallytheremaybedozensofthem. Incountingalgorithmswedonotdistinguishbetweentwowhichareidenticalexceptforthevalueofsomenumericparameter. Againthissetisofhighdim巳nsionsandthereisuncertaintyabouttheinfluence.ofalgorithmcharacteristics.PerfomanceMeasure: Thecriteriatomeasuretheperformanceofaparticularalgorithmforaparticularproblemarecomplexandhardtocom­pare(e.g.onewantsfastexecution,highaccuracyandsimplicity). thereisconsiderableuncertaintyinassigningandinterpretingtheseTHEBASICMODEL. WedescribethebasicabstractmodelbythediagraminFigure1. Theitemeinthismodelaredefinedbelowindetail soastobecompletelyclearaboutthenatureofthemodel.xE

4PROBLEM 4n＼ Schematicdiagramofthebasicmodelforthealgorithmselectionproblem. Theobjectiveistodetermine soastohavehighalgorithmDefinitionsforthebasic夕・Problemapaceorx•Memberof务problemtobe AlgorithmapaceorA•Memberof过',algor扛hmapplicabletoproblemsfromS•Mappingfrom夕to矣n•n-dimenaionalrealvectorspaceofperformance Mappingfrom过x夕to5iindete五iningperformanceIIII=Normon劣nprovidiJlgonenumber七oevaluateanperformanceonaparticularForcompletenesswenowstate Qivenall theotheritemsintheabove Theremustbe, ofcourse,'somecri七eriaforthisselectionandwepresentfourprimaryonesbelow:BestSelection. Choosethatselectionmappin B(x)whichgivesmaximumperformanceforeachalgorithm:JJp(B(x),x)II之11p(A,x)| for BestSelectionforaSubclassof Oneistochooseonealgorithmtoapplytoeverymemberofasubclass名CthatselectionmappingS{x) degradationformembersof务(comparedtochoosingm立Ilp(B(x),x)II

-llp(A。),x)111三ma_:<_llfr(B(x),x)xEfor

-//p(A,x)/55BestSelectionfromaSubclassofMa过坚 Oneistorestrict亡mappingS tobeofacertainformorfromacertainsubclass＄飞。＊ mappingfrom夕to过．ChoosethatselectionmappingS 夕0whichminimizestheperformancedegradationfor membersofmax[llp(B(x),xl'II-IIP(S*(x),x)lll三max[llp(B(x),x)II-IIP(S(x),x)lllforallSE＊BestSelectionfromaSubclassofMa过坚sandProblems.Oneistochoosejustonealgorithmfromasubclass9cjtoapplyeverymemberofasubclass9l,立Choosethatselectionmappings~(x)fromYe,whichminimizes七heperformancedegradationforallmembersof令＊max_[llp(B(x),xII-llp(s"(x),x)lllminmax[llp(B(x),x)II-llp(S(x),x)lll 6Thesefourcriteriadonotexhaustthemeaningfulcriteriabuttheydoillustratetheprincipalideas. Therearefivemainstepstotheanalysisandsolutionof'thealgorithmselectionproblemasfollows6江 Determinationofthesubclassesofandmappingstobe还声（Exis七 Doesabestselectionmapping Isthereauniquebestselectionmapping? Whatpropertiescharacterizethebestselectionmappingandservetoidentifyit? WhatmethodscanbeusedtoactuallythebestselectionThereaderfamiliarwiththetheoryofapproximationoffunctions observethatthisframeworkisfa口iliarandthatwemayputthatclassicaltheorywithinthis Thespace夕isafunctionandthealgorithmspacef¥maybeidentifiedwithasubspaceof夕algorithmentersaathemeansofevaluatingelementsof mappingp(A,x) Ilx(t)-A(t)夕wherethenormistakenon夕．Thustheperformancemeasurespace劣1andthenormmappingisTherearetworemarksneededaboutthisobservation. First,thebodyofsignificantmaterielinapproximationtheoryislarge, Itwouldrequire,nodoubt,from2000to4000pagestopresentareasonablycom-pleteandconciseexpositionoftheresultscurrentlyknown, impliesthatthereisaveryrichbodyofmaterialwaitingtobeappliedtothealgorithmselectionproblem,eitherdirectlyorbyanalogy, andmoreimportant,thealgorithmselectionproblemisanessentialexten-7sionandgeneralizationofapproximationtheory.Wewillseeconcreteexamplesofthisproblemwhere七hecurrent七heoryofapproximationhasnothingrelevanttoapplyexceptbythefaintestanalogies,7Wenextpresenttwoconcreteexamplestoillustratethis (AQuadratureproblem). Givenf(x)Ec-[O,l]and E>0, f。x(t)dxwithinEbyacompositeNewton-Cotesformulaofdegreekandwith儿pointswithaminimumnumberofevaluationsof We 夕＝c4[0,1]x 12(whereIdenotesthepositiveintegers)na1intheperformancemeasurespaceWechoosetwo各＝｛x(t)Ix(t)hasatmos七1inflection linearfunctionof x(O),x(l/3),x(2/3)andThusS(x)wouldhavethegeneralformwith10parame七rfdcserer\il!ehtes0Ossss11 rfdcserer\il!ehtes0Ossss11 (upahrtxs。丿丿（（)ot(Ea0sch/-s（、丿)ot(Ea0sch/-s（、丿（ (Asgameplayingproblem). Weare todeviseanalgorichmforplayingTic-Tac-Toe. Theproblemspaeisthesetofpartialgamesof Whilethisnumberislarge,thereareinfactonly28distinctreasonablegamesif oneeliminatesblunders,symmetriesandboardrotations,Theapace mayberepresentedasaspaceoflargetablesofresponsesforeachsituation. However,werestrictourselectiontoadecisiontreethatinvolvesonlytheexistenceofimmediatewinningpositionsandvacant7 ThealgorithmformmaythenberepresentedasshowninFigure7Thereare30parameters inthisformoftheselectionmappingtakeonthevalues"yes"or Only15oftheseare addition七here·are16parametersa,whichtakeononeofthefollowingfivePlaythewinningBlocktheopponent'sPlayinthecenterPlayinacorner(firstfreeoneclockwisefromupper Playinaside(firstfreeoneclockwisefromDoIhaveawinningposition Doesopponenthavea IsthecenterIsacornerS5:r心 TheformoftheselectionmappingfortheTic-Tac-Toe EachSij扭a"yes"or"no"andeachaiisoneoffivemoves.8Anexaminationofthisgameshowsthatwehavebeenoverlyelaborate8Thuswemayassigns11•"yes"and\z•"no"andthenaiMove1i1,2,...,8iscertainlycalledfor.However,itisstillofinteresttoreflectuponhowonewouldcomputethisifonehadnoaprioriinfor~mationabout七hegame. Anexaminationofvariousinstancesofthealgorithmselectionproblemshowsthatthereisanotheringredientalmostalwayspresent. Itissometimesexplicitandsometimesno七andwecallthisselectionbasedonfeaturesoftheproblem. modelisdescribedbythediagrsminFigure3.f(x)E夕

AEAE

PE99IIpII=ALGORITHM diagramofthemodelwithselectionbasedonfeaturesoftheproblem.Theadditionaldefinitionsforthismodel夕＝Featurespaceidentifiedwith劣mheretosuggestit issimplerandof1叩erdimensionthan夕．F•Mappingfrom少to夕whichassociatesfeatureswithNotethattheselectionmappingnowdependsonlyonthefeaturesf(x)butyettheperformancemappingstilldependsontheproblemx, Theintroduc­tionoffeaturesmaybeviewedasawaytosystematizethein七roductionproblemsubclassesinthebasicThepreviousstatementofthealgorithmselectionproblemandthe forselectionarestill validforthisnewmodelaswellasthefivestepsintheanalysisandsolutionoftheproblem. Thedeter­minationofthefeaturestobeusedisfrequentlypartoftheprocess,oftenoneofthemostimportantparts. Onemayviewthefeaturesasanattempttointroduceanapproximatecoordinatesystemin9. thoseproblemswiththesamefeatur七swouldhavethesameperformanceforanyalgorithmbeingconsidered. Sincethisidealisrarelyachieved,wemayposeaeveralspecificquestionsaboutthedeterminationof-BestFeatur七sfoo_a;Prtieular杜 Giv,analgorithmAandthedimensionmof夕，whatmfeaturesarethebestforthepredic-tion•oftheperformanceofA. Let_.仪f)denotetheequivalenceclassofall thoseproblamsx,yE夕的thatF(x)•F(y) Wethenwishtodeterminethe＊场(f)＊

and

ciatedequivalenced_(A) fE yE丘

IIP(A,x)-p(A,y)11三fE

IIP(A,x)-p(A,y)Theselectionofbestfeaturescorrespondstotheselectionofapproximatingsubspacesinapproximationtheo巧？andleadsonetoideas＊n-widthsandentropyoftheproblemspace

Roughlyspeaking, d_is江then·theeffectivedimensionof夕（fortheproblemathand)isprobably＊largerthanmand,conversely, d_issmallthentheeffectiveof夕扭closetoBestFeaturesforaClassof Givenaandthedimensionmof乡 whatmfeaturesarethebestforpredictionoftheperformanceofalgorithmAE? Withthepreviousnotationwewishto

neF•

场夕(f)so＊d（过。 fE夕AE过 x,YE场

IIP(A,x)-p(A,y)＜ Ilp(A,x)-p(A,y)fE歹AE.J:I x,yE场 BestFeaturesforaSubclassofSelectionMappings. Givenasubclass夕。ofselec己onmappingsfrom夕to.9Jf,whatmfeaturesare七hebestforpredi吐ionoftheperformanceofalgorithms? Withtheprevious notationwewishtodetermine and丘 so＊dm(夕。）＝ fE

m刁SE夕

X,YE场

Ilp(S(f),x)-p(S(f),y)I

Ilp(S(f),x)-p(S(f),Y)IfE

SE夕Thedetermina七ionofthebest(orevengood}featuresisoneofthemostimportant,yetnebulous,aspectsofthealgorithmselectionproblem.Manyproblemspaces夕areknownonlyinvaguetermsandhenceanexperimentalapproachisoftenusedtoevaluatetheperformanceofalgorithmsover夕．Thatis,onechoosesasamplefrom夕andrestrictsconsiderationstothissample. Anappropriatesampleisobviou吐ycrucialtothisapproachandif onehasagoodsetoffeaturesfor夕．thenonecanatleastforcethesampletoberepresentativewithrespecttothesefeatures. Notethatthedefinitionofbestfeatures-issuchthattheyaretheitemsofinfor-mationmostrelevanttotheperformanceofalgorithmsfortheproblematInsomewellunderstoodareas.ofcomputationthereisagenerallyagreedupon(if notexplicitlystated)setoffea七ures. Forexample,considertheproblemofsolvingalinearsystemAx•bofequations. Thefeaturesin-cludedescriptorslike: smallorder,sparse,band,diagonallydominant,positivedefinite,ill-conditioned,etc. Givenvaluesforthesefesturesanexperiencednumericalanalystcanselectanappropriatealgorithmthisproblemwithconsiderable Theselectionproblemforratureisalreadymuchmoredifficult andthesolutionofsimultaneoussystemsofnonlinearequationsisverypoorlyunderstood. Ifthissituationexistsforproblems七hathavebeenstudiedforoneortwocenturiesthenoneshouldnotbesurprisedbythedifficultiesanduncertaintiesforproblemsthathavejustappearedinthepastoneortwoALTERNATEDEFINIT Iheprecedingsectionswehaveuniformlytakenaminimaxapproachtothedefinitionofbestoroptimumselection. Thatis,wehaveminimizedtheeffectoftheworstcase.Itisreasonabletoignoretheperformancefortheworstcaseand,instead,con吐deroptimizingsomesortofaveragebehavior. Inthissectionweex-hibittheresultingmathematicalproblemscorrespondingtousingaleastsquaresorleastdeviationapproach(thesecorrespondtoL2andL1optimiza­tioninmathematicalterms). WehaveidentifiedsevenproblemslabelAthroughG. ProblemAisunaffectedbytheseconsiderationssoletuscon­sider红oblemB: BestSelectionforaSubclassofProblems. Weuse notationintroducedwiththeoriginalmathematicalstatementofthisprob­lemwhichMinimax rllp(B(x),x)II-

Ilp(A*,xll]l三 [|lp(B(x),x)|XE夕

-Ilp(A,x)IIfor AEThecorrespondingmathematicalstatementsfortheleastsquaresandleastdeviationapproachare:罕f_[IIP(B(x),x)II-forallAE

LeastDeviations匀 jjp(A•,xlllldx三岁ol11p(B(x),xlll-for AETheuseofintegralsintheseformulationsimpliesthatatopologyhasbeenintroducedintheproblemspace夕．Manycommonexample臼for夕aredis­creteinnatureandinthesecasesthetopologyintroducedreducestheintegralstosums. Thiatechnicalityisunlikelytocauserealdifficultiesandwecontinuetouseintegralsasthisgivestheneatestformulations.Notethattheonlydifferencebetweenthetwonewformulationsis (2or1)intheintegrand. Thuswemayavoidrepeatingthesefo亡mulationstwicebymakingthisavariable,sayr, whichhasvalues1or2,Notethatinapproximationtheoryit isshownthatminimaxisthelimitingcaseasr+mso thatall threeapproachescanbeexpressedinoneformula-tionwithrasaparameter.RecallthatProblemCistheBeatSelectionfromaSubclassofMa匹虫逞Thealternativemathematicalformulationofthisproblem』||p(B(x),x)I/-1/p(S。(x),x)I/rdx三占11/p(B(x),x)Ifor SE夕ThealternativeformulationforProblemDisidenticaltothisexceptthattheproblemsubcla的气replace夕asthedomainofintegration.Thenextthreeproblemsinvolvefeaturesandwechoosetouseacon­sistentapproachfor七he That weuseleastontheproblemspacewealsouseitonthefeaturespace夕and亡hespace立．Ifwed:(A，岁 fE

x,y

Ilp(A,x)-p(A,y)|

thenforProblem BestFeatureforaPar .the＊istofindthefeaturemappingF•andassociatedequivalenceclasses矿whichminimized:(A， m心・d:(A，豆·臣d:(A，岁Fo工ProblemFwed;(Wo·炉）一

J IIP(A,x)-p(A,y)11fE歹AE..Ql'ox,y邹 thentheobjectiveistodetermineF＊..and

岁

so沪。）＝d;（叱，矿）＝臣nd；心。，Asimilarapproachto yieldsasimilarexpressionexceptthattheintegralover isreplacedbyanintegraloverYa· manypracticalproblemsthereislittletoguideoneintheofaparticularformulationofthemathematicaloptimizationproblem,i.e.shouldwechooser=1, 2or00? Thesechoicesmightnotbeparticularlysignificantinthelargercontext,buttheyareverysignificantindeterminingthedifficultyoftheresultingmathematicaloptimizationproblem. Alessonlearnedfrompracticalapproximationtheorymightbeapplicableinthislarger Thislessonis,roughly,tha七thecrucialingredientsforsuccessareproperchoicesofthesubclasses夕0'%。and Oncethesearemadeproperlythenthemathematicaloptimhationshouldbemadeforthatvalueof thatgivestheleastdifficul七y. Iftheproblemiscompletelylinearthen 2(leastsquares)almostalwaysresultsintheleastmathematicaldiffi- Thesituationisvariablefornonlinearproblems. Notethattherearepracticalapproximationproblemswherethechoiceofriscrucialandnodoubttherearesimilarcasesforthealgorithmselectionproblem.Wearesayingthatthechoiceofrisimportantonlyinaninfrequentnumberofinstances.THEMODELWITHVARIABLEPERFOR四CECRITERIA. Wehaveaaaumedaofarthatthereissfixed口aytome88uretheperformanceofaparticularalgorithmforaparticularproblem. Thereare,however,manysituationswhereit isreasonabletoviewtheperformancecriteriaasinputtotheselectionproblem, Consider,forexample,theselectionofaprogramtosolveordinarydifferentialequationsand七hecriteriaofaccuracy,reliability,andcareofuse, Indifferentsituationstheweightgiventoeachofthesemightvaryfromalmostzerotoalmost100%,AmodelforthisversionoftheselectionproblemisshowninthediagramofFigure4,XE

f(x)ef(x)eFE应

I

四nPEIIPII= SchematicdiagramofthemodelwithselectionbasedonfeaturesandvariableperformanceTheadditionaldefinitionforthismodelgNormfunctionfrom矿x劣ntoRlwhichmeasurestheperformancep(A,x)withthecriteriaSomeofthemappingsnowhavechangeddomains,buttheirna七ureisthesame.Thechoiceof劣nforthecriteriaspaceisclearlyarbitrary(andperhapsunnecessarilyrestrictive)butit isn