On?LineAlgorithmsinMachineLearning AvrimBlum CarnegieMellonUniversity?PittsburghPA?Email?avrim?cs?cmu?edu Abstract?TheareasofOn?LineAlgorithmsandMachineLearningare bothconcernedwithproblemsofmakingdecisionsaboutthepresent basedonlyonknowledgeofthepast?Althoughtheseareasdi?erinterms oftheiremphasisandtheproblemstypicallystudied?thereareacollec? tionofresultsinComputationalLearningTheorythat?tnicelyintothe ?on?linealgorithms?framework?Thissurveyarticlediscussessomeofthe results?models?andopenproblemsfromComputationalLearningThe? orythatseemparticularlyinterestingfromthepointofviewofon?line algorithms? Theemphasisinthisarticleisondescribingsomeofthesimpler?morein? tuitiveresults?whoseproofscanbegivenintheirentirity?Pointerstothe literaturearegivenformoresophisticatedversionsofthesealgorithms? ?Introduction TheareasofOn?LineAlgorithmsandMachineLearningarebothconcernedwith problemsofmakingdecisionsfromlimitedinformation?Althoughtheydi?erin termsoftheiremphasisandtheproblemstypicallystudied?thereareacollection ofresultsinComputationalLearningTheorythat?tnicelyintothe?on?lineal? gorithms?framework?Thissurveyarticlediscussessomeoftheresults?models? andopenproblemsfromComputationalLearningTheorythatseemparticularly interestingfromthepointofviewofon?linealgorithms?Thisarticleisnotmeant tobecomprehensive?Itsgoalistogivethereaderasenseofsomeoftheinter? estingideasandproblemsinthisareathathavean?on?linealgorithms?feelto them? Webeginbydescribingtheproblemof?predictingfromexpertadvice?which hasbeenstudiedextensivelyinthetheoreticalmachinelearningliterature?We presentsomeofthealgorithmsthathavebeendevelopedandthatachievequite tightboundsintermsofacompetitiveratiotypeofmeasure?Nextwebroaden ourdiscussiontoconsiderseveralstandardmodelsofon?linelearningfromexam? ples?andexaminesomeofthekeyissuesinvolved?Wedescribeseveralinteresting algorithmsforon?linelearning?includingtheWinnowalgorithmandanalgo? rithmforlearningdecisionlists?anddiscussissuessuchasattribute?e?cient learningandthein?niteattributemodel?andlearningtargetfunctionsthat changeovertime?Finally?weendwithalistofimportantopenproblemsinthe areaandadiscussionofhowideasfromComputationalLearningTheoryand On?LineAlgorithmsmightbefruitfullycombined? Toaidinthe?owofthetext?mostofthereferencesanddiscussionsofhistory areplacedinspecial?history?subsectionswithinthearticle? ?PredictingfromExpertAdvice Webeginwithasimple?intuitiveproblem?Alearningalgorithmisgiventhe taskeachdayofpredictingwhetherornotitwillrainthatday?Inorderto makethisprediction?thealgorithmisgivenasinputtheadviceofn?experts? Eachday?eachexpertpredictsyesorno?andthenthelearningalgorithmmust usethisinformationinordertomakeitsownprediction?thealgorithmisgiven nootherinputbesidestheyes?nobitsproducedbytheexperts?Aftermaking itsprediction?thealgorithmisthentoldwhetherornot?infact?itrainedthat day?Supposewemakenoassumptionsaboutthequalityorindependenceof theexperts?sowecannothopetoachieveanyabsolutelevelofqualityinour predictions?Inthatcase?anaturalgoalinsteadistoperformnearlyaswellasthe bestexpertsofar?thatis?toguaranteethatatanytime?ouralgorithmhasnot performedmuchworsethanwhicheverexperthasmadethefewestmistakesto date?Inthelanguageofcompetitiveanalysis?thisisthegoalofbeingcompetitive withrespecttothebestsingleexpert? Wewillcallthesequenceofeventsinwhichthealgorithm?receivesthe predictionsoftheexperts?makesitsownprediction?andthen?istold thecorrectanswer?atrial?Formostofthisdiscussionwewillassumethat predictionsbelongtothesetf?g?thoughwewilllaterconsidermoregeneral sortsofpredictions?e?g?many?valuedandreal?valued? ?ASimpleAlgorithm Theproblemdescribedaboveisabasicversionoftheproblemof?predictingfrom expertadvice?extensions?suchaswhenpredictionsareprobabilities?orwhen theyaremoregeneralsortsofsuggestions?aredescribedinSection?below? WenowdescribeasimplealgorithmcalledtheWeightedMajorityalgorithm? Thisalgorithmmaintainsalistofweightsw ? ?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 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?wheremisthenumber 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