On Sequential Monte Carlo Sampling Methods for Bay

OnSequentialMonteCarloSamplingMethodsforBayesianFilteringArnaudDoucet(correspondingauthor)-SimonGodsill-ChristopheAndrieuSignalProcessingGroup,DepartmentofEngineeringUniversityofCambridgeTrumpingtonStreet,CB21PZCambridge,UKEmail:[e-mail],wepresentanoverviewofmethodsforsequentialsimulationfromposteriordistributions.ThesemethodsareofparticularinterestinBayesianlteringfordiscretetimedynamicmodelsthataretypicallynonlinearandnon-Gaussian.Ageneralimportancesamplingframeworkisdevelopedthatuniesmanyofthemethodswhichhavebeenproposedoverthelastfewdecadesinseveraldierentscienticdisciplines.Novelextensionstotheexistingmethodsarealsoproposed.Weshowinparticularhowtoincorporatelocallinearisationmethodssimilartothosewhichhavepreviouslybeenemployedinthedetermin-isticlteringliterature;theseleadtoveryeectiveimportancedistributions.FurthermorewedescribeamethodwhichusesRao-Blackwellisationinordertotakeadvantageoftheanalyticstructurepresentinsomeimportantclassesofstate-spacemodels.Inanalsectionwedevelopalgorithmsforprediction,smoothingandevaluationofthelikelihoodindynamicmodels.1Keywords:Bayesianltering,nonlinearnon-Gaussianstatespacemodels,sequentialMonteCarlomethods,importancesampling,Rao-BlackwellisedestimatesI.IntroductionManyproblemsinappliedstatistics,statisticalsignalprocessing,timeseriesanalysisandeconometricscanbestatedinastatespaceformasfollows.AtransitionequationdescribesthepriordistributionofahiddenMarkovprocessfxk;k2g,theso-calledhiddenstateprocess,andanobservationequationdescribesthelikelihoodoftheobservationsfyk;k2g,kbeingadiscretetimeindex.WithinaBayesianframework,allrelevantinformationaboutfx0;x1;:::;xkggivenobservationsuptoandincludingtimekcanbeobtainedfromtheposteriordistributionp(x0;x1;:::;xkjy0;y1;:::;yk).Inmanyapplicationsweareinterestedinestimatingrecursivelyintimethisdistributionandparticularlyoneofitsmarginals,theso-calledlteringdistributionp(xkjy0;y1;:::;yk).Giventhelteringdistributiononecanthenroutinelyproceedtolteredpointestimatessuchastheposteriormodeormeanofthestate.ThisproblemisknownastheBayesianlteringproblemortheoptimallteringproblem.Practicalapplicationsincludetargettracking(Gordonetal.,1993),blinddeconvolutionofdigitalcommunicationschannels(Clappetal.,1999)(Liuetal.,1995),estimationofstochasticvolatility(Pittetal.,1999)anddigitalenhancementofspeechandaudiosignals(Godsilletal.,1998).Exceptinafewspecialcases,includinglinearGaussianstatespacemodels(Kalmanlter)andhiddennite-statespaceMarkovchains,itisimpossibletoevaluatethesedis-tributionsanalytically.Fromthemid1960's,agreatdealofattentionhasbeendevotedtoapproximatingtheselteringdistributions,seeforexample(Jazwinski,1970).Themostpopularalgorithms,theextendedKalmanlterandtheGaussiansumlter,relyonanalyt-icalapproximations(Andersonetal.,1979).Interestingworkintheautomaticcontroleldwascarriedoutduringthe1960'sand70'susingsequentialMonteCarlo(MC)integration2methods,see(Akashietal.,1975)(Handschinet.al,1969)(Handschin1970)(Zaritskiietal.,1975).PossiblyowingtotheseverecomputationallimitationsofthetimetheseMonteCarloalgorithmshavebeenlargelyneglecteduntilrecently.Inthelate80's,massiveincreasesincomputationalpowerallowedtherebirthofnumericalintegrationmethodsforBayesianltering(Kitagawa1987).CurrentresearchhasnowfocusedonMCintegrationmethods,whichhavethegreatadvantageofnotbeingsubjecttotheassumptionoflinearityorGaus-sianityinthemodel,andrelevantworkincludes(Muller1992)(West,1993)(Gordonetal.,1993)(Kongetal.,1994)(Liuetal.,1998).Themainobjectiveofthisarticleistoincludeinauniedframeworkmanyoldandmorerecentalgorithmsproposedindependentlyinanumberofappliedscienceareas.Both(Liuetal.,1998)and(Doucet,1997)(Doucet,1998)underlinethecentralr^oleofsequentialimportancesamplinginBayesianltering.However,contraryto(Liuetal.,1998)whichem-phasizestheuseofhybridschemescombiningelementsofimportancesamplingwithMarkovChainMonteCarlo(MCMC),wefocushereoncomputationallycheaperalternatives.WedescribealsohowitispossibletoimprovecurrentexistingmethodsviaRao-Blackwellisationforausefulclassofdynamicmodels.Finally,weshowhowtoextendthesemethodstocomputethepredictionandxed-intervalsmoothingdistributionsaswellasthelikelihood.Thepaperisorganisedasfollows.Insection2,webrieyreviewtheBayesianlteringproblemandclassicalBayesianimportancesamplingisproposedforitssolution.WethenpresentasequentialversionofthismethodwhichallowsustoobtainageneralrecursiveMClter:thesequentialimportancesampling(SIS)lter.Underacriterionofminimumconditionalvarianceoftheimportanceweights,weobtaintheoptimalimportancefunctionforthismethod.Unfortunately,fornumerousmodelsofappliedinteresttheoptimalimportancefunctionleadstonon-analyticimportanceweights,andhenceweproposeseveralsuboptimaldistributionsandshowhowtoobtainasspecialcasesmanyofthealgorithmspresentedintheliterature.Firstlyweconsiderlocallinearisationmethodsofeitherthestatespacemodel3ortheoptimalimportancefunction,givingsomeimportantexamples.Theselinearisationmethodsseemtobeaverypromisingwaytoproceedinproblemsofth