Monte carlo hidden Markov models

MonteCarloHiddenMarkovModelsSebastianThrunandJohnLangfordDecember1998CMU-CS-98-179SchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213AbstractWepresentalearningalgorithmforhiddenMarkovmodelswithcontinuousstateandobserva-tionspaces.Allnecessaryprobabilitydensityfunctionsareapproximatedusingsamples,alongwithdensitytreesgeneratedfromsuchsamples.AMonteCarloversionofBaum-Welch(EM)isemployedtolearnmodelsfromdata,justasinregularHMMlearning.Regularizationduringlearningisobtainedusinganexponentialshrinkingtechnique.Theshrinkagefactor,whichdeter-minestheeffectivecapacityofthelearningalgorithm,isannealeddownovermultipleiterationsofBaum-Welch,andearlystoppingisappliedtoselecttherightmodel.Weprovethatundermildassumptions,MonteCarloHiddenMarkovModelsconvergetoalocalmaximuminlikeli-hoodspace,justlikeconventionalHMMs.Inaddition,weprovideempiricalresultsobtainedinagesturerecognitiondomain,whichillustratetheappropriatenessoftheapproachinpractice.ThisresearchissponsoredinpartbyDARPAviaAFMSC(contractnumberF04701-97-C-0022),TACOM(con-tractnumberDAAE07-98-C-L032),andRomeLabs(contractnumberF30602-98-2-0137).Theviewsandconclusionscontainedinthisdocumentarethoseoftheauthorsandshouldnotbeinterpretedasnecessarilyrepresentingofficialpoliciesorendorsements,eitherexpressedorimplied,ofDARPA,AFMSC,TACOM,RomeLabs,ortheUnitedStatesGovernment.Keywords:annealing,any-timealgorithms,Baum-Welch,densitytrees,earlystopping,EM,hiddenMarkovmodels,machinelearning,maximumlikelihoodestimation,MonteCarlomethods,temporalsignalprocessingMonteCarloHiddenMarkovModels11IntroductionOverthelastdecadeorso,hiddenMarkovmodelshaveenjoyedanenormouspracticalsuccessinalargerangeoftemporalsignalprocessingdomains.HiddenMarkovmodelsareoftenthemethodofchoiceinareassuchasspeechrecognition[28,27,42],naturallanguageprocessing[5],robotics[34,23,48],biologicalsequenceanalysis[17,26,40],andtimeseriesanalysis[16,55].Theyarewell-suitedformodeling,filtering,classificationandpredictionoftimesequencesinarangeofpartiallyobservable,stochasticenvironments.Withfewexceptions,existingHMMalgorithmsassumethatboththestatespaceoftheenvi-ronmentanditsobservationspacearediscrete.Someresearchershavedevelopedalgorithmsthatsupportmorecompactfeature-basedstaterepresentations[15,46]whichareneverthelessdiscrete;othershavesuccessfullyproposedHMMmodelsthatcancopewithreal-valuedobservationspaces[29,19,48].Kalmanfilters[21,56]canbethoughtofasHMMswithcontinuousstateandactionspaces,whereboththestatetransitionandtheobservationdensitiesarelinear-Gaussianfunctions.Kalmanfiltersassumethattheuncertaintyinthestateestimationisalwaysnormallydistributed(andhenceunimodal),whichistoorestrictiveformanypracticalapplicationdomains(seee.g.,[4,18]).Incontrast,most“natural”statespacesandobservationspacesarecontinuous.Forexample,thestatespaceofthevocaltractofhumanbeings,whichplaysaprimaryroleinthegenerationofspeech,iscontinuous;yetHMMstrainedtomodelthespeech-generatingprocessaretypicallydiscrete.Robots,tonameasecondexample,alwaysoperateincontinuousspaces;hencetheirstatespacesareusuallybestmodeledbycontinuousstatespaces.Manypopularsensors(cam-eras,microphones,rangefinders)generatereal-valuedmeasurements,whicharebettermodeledusingcontinuousobservationspaces.Inpractice,however,real-valuedobservationspacesareusuallytruncatedintodiscreteonestoaccommodatethelimitationsofconventionalHMMs.Apopularapproachalongtheselinesistolearnacode-book(vectorquantizer),whichclustersreal-valuedobservationsintofinitelymanybins,andthusmapsreal-valuedsensormeasurementsintoadiscretespaceofmanageablesize[54].ThediscretenessofHMMsisinstarkcontrasttothecontinuousnatureofmanystateandobservationspaces.ExistingHMMalgorithmspossessaseconddeficiency,whichisfrequentlyaddressedintheAIliterature,butrarelyintheliteratureonHMMs:theydonotprovidemechanismsforadaptingtheircomputationalrequirementstotheavailableresources.Thisisunproblematicindomainswherecomputationcanbecarriedoutoff-line.However,trainedHMMsarefrequentlyemployedintime-criticaldomains,wheremeetingdeadlinesisessential.Any-timealgorithms[9,58]addressthisissue.Any-timealgorithmscangenerateanansweratanytime;however,thequalityofthesolutionincreaseswiththetimespentcomputingit.Anany-timeversionofHMMswouldenablethemtoadapttheircomputationalneedstowhatisavailable,thusprovidingmaximumflexibilityandaccuracyintime-criticaldomains.MarryingHMMswithany-timecomputationisthereforeadesirablegoal.ThispaperpresentsMonteCarloHiddenMarkovModels(MCHMMs).MCHMMsemployscontinuousstateandobservationspaces,andoncetrained,theycanbeusedinanany-timefashion.OurapproachemploysMonteCarlomethodsforapproximatingalarge,non-parametricclassofdensityfunctions.Tocombinemultipledensities(e.g.,withBayesrule),ittransformssamplesets2SebastianThrunandJohnLangfordintodensitytrees.Sincecontinuousstatespacesaresufficientlyrichtooverfitanydataset,ourapproachusesshrinkageasmechanismforregularization.Theshrinkagefactor,whichdeterminestheeffectivecapacityoftheHMM,isannealeddownovermultipleiterationsofEM,andearlystoppingisappliedtochoosetherightmodel.W