《算法高级教程survey》由会员分享，可在线阅读，更多相关《算法高级教程survey（20页珍藏版）》请在金锄头文库上搜索。
1、On?LineAlgorithmsinMachineLearning AvrimBlum CarnegieMellonUniversity?PittsburghPA?Email?avrim?cs?cmu?edu Abstract?TheareasofOn?LineAlgorithmsandMachineLearningare bothconcernedwithproblemsofmakingdecisionsaboutthepresent basedonlyonknowledgeofthepast?Althoughtheseareasdi?erinterms oftheiremphasisan
2、dtheproblemstypicallystudied?thereareacollec? tionofresultsinComputationalLearningTheorythat?tnicelyintothe ?on?linealgorithms?framework?Thissurveyarticlediscussessomeofthe results?models?andopenproblemsfromComputationalLearningThe? orythatseemparticularlyinterestingfromthepointofviewofon?line algor
3、ithms? Theemphasisinthisarticleisondescribingsomeofthesimpler?morein? tuitiveresults?whoseproofscanbegivenintheirentirity?Pointerstothe literaturearegivenformoresophisticatedversionsofthesealgorithms? ?Introduction TheareasofOn?LineAlgorithmsandMachineLearningarebothconcernedwith problemsofmakingdec
4、isionsfromlimitedinformation?Althoughtheydi?erin termsoftheiremphasisandtheproblemstypicallystudied?thereareacollection ofresultsinComputationalLearningTheorythat?tnicelyintothe?on?lineal? gorithms?framework?Thissurveyarticlediscussessomeoftheresults?models? andopenproblemsfromComputationalLearningT
5、heorythatseemparticularly interestingfromthepointofviewofon?linealgorithms?Thisarticleisnotmeant tobecomprehensive?Itsgoalistogivethereaderasenseofsomeoftheinter? estingideasandproblemsinthisareathathavean?on?linealgorithms?feelto them? Webeginbydescribingtheproblemof?predictingfromexpertadvice?whic
6、h hasbeenstudiedextensivelyinthetheoreticalmachinelearningliterature?We presentsomeofthealgorithmsthathavebeendevelopedandthatachievequite tightboundsintermsofacompetitiveratiotypeofmeasure?Nextwebroaden ourdiscussiontoconsiderseveralstandardmodelsofon?linelearningfromexam? ples?andexaminesomeofthek
7、eyissuesinvolved?Wedescribeseveralinteresting algorithmsforon?linelearning?includingtheWinnowalgorithmandanalgo? rithmforlearningdecisionlists?anddiscussissuessuchasattribute?e?cient learningandthein?niteattributemodel?andlearningtargetfunctionsthat changeovertime?Finally?weendwithalistofimportantop
8、enproblemsinthe areaandadiscussionofhowideasfromComputationalLearningTheoryand On?LineAlgorithmsmightbefruitfullycombined? Toaidinthe?owofthetext?mostofthereferencesanddiscussionsofhistory areplacedinspecial?history?subsectionswithinthearticle? ?PredictingfromExpertAdvice Webeginwithasimple?intuitiv
9、eproblem?Alearningalgorithmisgiventhe taskeachdayofpredictingwhetherornotitwillrainthatday?Inorderto makethisprediction?thealgorithmisgivenasinputtheadviceofn?experts? Eachday?eachexpertpredictsyesorno?andthenthelearningalgorithmmust usethisinformationinordertomakeitsownprediction?thealgorithmisgive
10、n nootherinputbesidestheyes?nobitsproducedbytheexperts?Aftermaking itsprediction?thealgorithmisthentoldwhetherornot?infact?itrainedthat day?Supposewemakenoassumptionsaboutthequalityorindependenceof theexperts?sowecannothopetoachieveanyabsolutelevelofqualityinour predictions?Inthatcase?anaturalgoalin
11、steadistoperformnearlyaswellasthe bestexpertsofar?thatis?toguaranteethatatanytime?ouralgorithmhasnot performedmuchworsethanwhicheverexperthasmadethefewestmistakesto date?Inthelanguageofcompetitiveanalysis?thisisthegoalofbeingcompetitive withrespecttothebestsingleexpert? Wewillcallthesequenceofevents
12、inwhichthealgorithm?receivesthe predictionsoftheexperts?makesitsownprediction?andthen?istold thecorrectanswer?atrial?Formostofthisdiscussionwewillassumethat predictionsbelongtothesetf?g?thoughwewilllaterconsidermoregeneral sortsofpredictions?e?g?many?valuedandreal?valued? ?ASimpleAlgorithm Theproble
13、mdescribedaboveisabasicversionoftheproblemof?predictingfrom expertadvice?extensions?suchaswhenpredictionsareprobabilities?orwhen theyaremoregeneralsortsofsuggestions?aredescribedinSection?below? WenowdescribeasimplealgorithmcalledtheWeightedMajorityalgorithm? Thisalgorithmmaintainsalistofweightsw ?
14、?w n ?oneforeachexpert?and predictsbasedonaweightedmajorityvoteoftheexpertopinions? TheWeightedMajorityAlgorithm?simpleversion? ?Initializetheweightsw ? ?w n ofalltheexpertsto? ?Givenasetofpredictionsfx ? ?x n gbytheexperts?outputthepre? dictionwiththehighesttotalweight?Thatis?output?if X i?x i ? w
15、i ? X i?x i ? w i andoutput?otherwise? ?Whenthecorrectanswer?isreceived?penalizeeachmistakenexpert bymultiplyingitsweightby?Thatis?ifx i ?thenw i ?w i ?if x i ?thenw i isnotmodi?ed? Goto? Theorem?ThenumberofmistakesMmadebytheWeightedMajorityalgo? rithmdescribedaboveisnevermorethan?m?lgn?wheremisthen
16、umber ofmistakesmadebythebestexpertsofar? Proof?LetWdenotethetotalweightofalltheexperts?soinitiallyW?n?If thealgorithmmakesamistake?thismeansthatatleasthalfofthetotalweightof expertspredictedincorrectly?andthereforeinStep?thetotalweightisreduced byatleastafactorof?Thus?ifthealgorithmmakesMmistakes?wehave? W?n? M ? Ontheotherhand?ifthebestexperthasmademmistakes?thenitsweightis ? m andsoclearly? W? m ? Combining?and?y
