算法選擇問(wèn)題-抽象模型

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務(wù)problemtobe AlgorithmapaceorA?Memberof過(guò)',algor扛hmapplicabletoproblemsfromS?Mappingfrom夕to矣n?n-dimenaionalrealvectorspaceofperformance Mappingfrom過(guò)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務(wù)(comparedtochoosingm立Ilp(B(x),x)II

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

-//p(A,x)/55BestSelectionfromaSubclassofMa過(guò)堅(jiān) Oneistorestrict亡mappingS tobeofacertainformorfromacertainsubclass＄飛。＊ mappingfrom夕to過(guò)．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過(guò)堅(jiān)sandProblems.Oneistochoosejustonealgorithmfromasubclass9cjtoapplyeverymemberofasubclass9l,立Choosethatselectionmappings~(x)fromYe,whichminimizes七h(yuǎn)eperformancedegradationforallmembersof令＊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七h(yuǎn)ecurrent七h(yuǎn)eoryofapproximationhasnothingrelevanttoapplyexceptbythefaintestanalogies,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七h(yuǎn)ere·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七h(yuǎn)egame. 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＊場(chǎng)(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鄉(xiāng) whatmfeaturesarethebestforpredictionoftheperformanceofalgorithmAE? Withthepreviousnotationwewishto

neF?

場(chǎng)夕(f)so＊d（過(guò)。 fE夕AE過(guò) x,YE場(chǎng)

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

m刁SE夕

X,YE場(chǎng)

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七h(yuǎn)athavebeenstudiedforoneortwocenturiesthenoneshouldnotbesurprisedbythedifficultiesanduncertaintiesforproblemsthathavejustappearedinthepastoneortwoALTERNATEDEFINIT 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七h(yuǎn)e 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七h(yuǎn)ecriteriaofaccuracy,reliability,andcareofuse, Indifferentsituationstheweightgiventoeachofthesemightvaryfromalmostzerotoalmost100%,AmodelforthisversionoftheselectionproblemisshowninthediagramofFigure4,XE

f(x)ef(x)eFE應(yīng)

I

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