Sequential Monte Carlo Methods & Particle Filters Resources

Objectives

This ugly webpage presents a list of references, codes and videos available for SMC/particle filters.
It is by no means exhaustive and obviously biased towards my work.

This is a preliminary version, a few references and links need to be added.

References

Textbooks

*
G. Kitagawa & W. Gersch, Smoothness Priors Analysis of Time Series, Lecture Notes in Statistics, Springer, 1996.
- The first book I am aware of discussing particle filters, nice applications to spectral analysis, changepoints etc.

* A.D., N. De Freitas & N.J. Gordon (editors), SMC Methods in Practice, Springer-Verlag, 2001.
- Large collection of chapters on the subject, a bit outdated now but good to start with.

* P. Del Moral, Feynman-Kac Formulae: Generalogical and Interacting Particle Approximations, Springer-Verlag, 2004.
- Everything you want to know about the theory behind SMC, also includes nice non-standard applications.

* O. Cappe, E. Moulines & T. Ryden, Inference in Hidden Markov Models, Springer-Verlag, 2005.
-
A comprehensive treatment of hidden Markov models which includes a few chapters on SMC methods.

Basic Introduction to SMC for state-space models

* A.D., N. De Freitas and N.J. Gordon, An introduction to Sequential Monte Carlo Methods, in SMC in Practice, 2001 Ps
- Simple introduction to basic SMC for state-space models.

Early papers

* N.J. Gordon, D. Salmond and A.F.M. Smith, Novel approach to nonlinear/non-Gaussian Bayesian state estimation, IEE Proc. F, 1993 Pdf
- The seminal paper introducing SMC for filtering.

* G. Kitagawa, Monte Carlo filter and smoother for non-Gaussian nonlinear state-space models, JCGS, 1996
- Journal version of A Monte Carlo Filtering and Smoothing Method for Non-Gaussian Nonlinear State Space Models published in 1993 in the Proceedings of the 2nd U.S.-Japan Joint Seminar on Statistical Time Series Analysis, pp. 110-131. This 1993 paper introduced particle filters at the same time as Gordon, Salmond & Smith but it has been unfairly forgotten.

* J.S. Liu and R. Chen, Sequential Monte Carlo methods for dynamic systems, JASA, 1998 Pdf
- This paper shows that SMC goes far beyond state-space models and are applicable to any sequence of distributions of increasing dimension.

* M.K. Pitt and N. Shephard, Filtering via Simulation: Auxiliary Particle Filter, JASA, 1999 Pdf
- This paper introduces the popular auxiliary particle filter and perfect adaptation.

* J. Carpenter, P. Clifford and P. Fearnhead, An Improved Particle Filter for Non-linear Problems, IEE Proc. F, 1999 Pdf  
- This paper presents an improved version of auxiliary particle filters and stratified resampling.

* A.D., S.J. Godsill and C. Andrieu, On Sequential Monte Carlo sampling methods for Bayesian filtering, Stat. Comp., 2000 Pdf  
- This paper presents the "optimal" importance distribution, ways to approximate it, smoothing and Rao-Blackwellization.

Tutorials papers

*  S. Arulampalam, S. Maskell, N.J. Gordon & T. Clapp, A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking, IEEE Trans. Sig. Proc., 2002 Pdf
- Popular tutorial but a bit outdated now, e.g. does not include resample-move, smoothing or Rao-Blackwellisation. Could be a good start to understand SMC in a state-space model context though.

* O. Cappe, S.J. Godsill & E. Moulines, An Overview of Existing Methods and Recent Advances in SMC, Proc. IEEE, 2007 Pdf
- This paper also discusses resample move, some smoothing techniques and Rao-Blackwellisation.

* D. Creal, A Survey of Sequential Monte Carlo Methods for Economics and Finance, Econometric Reviews, to appear Pdf
- Tutorial introducing SMC and its applications in an economics and finance context.

* P. Del Moral, F. Patras, & S. Rubenthaler, A Mean Field Theory of Nonlinear Filtering, in the Oxford Handbook of Nonlinear Filtering, Oxford University Press, 2011 Pdf
- A more theoretically oriented tutorial that presents some of the main results in the area.

*  A.D. & A.M. Johansen - A Tutorial on Particle Filtering and Smoothing: 15 Years Later, in the Oxford Handbook of Nonlinear Filtering, Oxford University Press, 2011 Pdf  
- This paper shows that most SMC algorithms including auxiliary particle filters, resample-move, block sampling etc. can be reinterpreted within a simple and unifying framework.

*  N. Kantas, A.D., S.S. Singh and J.M. Maciejowski, An overview of sequential Monte Carlo methods for parameter estimation in general state-space models, in Proceedings IFAC System Identification (SySid) Meeting, 2009  Pdf
- The previous tutorials do not discuss the crucial parameter estimation issue, this paper does and proposes a few illustrative numerical examples.

Fighting degeneracy: Using MCMC steps & look-ahead strategies

A well-known problem with SMC approximations is that they suffer from the degeneracy problem, i.e. as time increases the approximations of the "earlier" marginal distributions collapse. You can try to mitigate (but not eliminate) this problem using either some MCMC moves as suggested by Gilks & Berzuini or by using lookahead strategies of which my favourite is block sampling.

*  W. Gilks & C. Berzuini, Following a moving target: Monte Carlo inference for dynamic Bayesian models, JRSS B, 2001
- This paper proposes to move the particles using MCMC moves with the appropriate invariant distribution so as to introduce diversity among particles.

* A.D., M. Briers & S. Senecal, Efficient Block Sampling Strategies for SMC, JCGS, 2006 Pdf  
- This pape shows how it is possible to potentially drastically reduce the number of resampling steps, hence the degeneracy, by sampling blocks of state variables. Can be thought of as a block version of auxiliary particle filters.

* M. Lin, R. Chen & J.S. Liu, Lookahead Strategies for SMC, technical report, 2009 Pdf
- This paper reviews various lookahead strategies to mitigate degeneracy.

Reducing the Variance using Rao-Blackwellized Particle Filters

Whenever you can compute an integral analytically, then do it and avoid Monte Carlo. An obvious principle one can put in practice for a wide range of state-space models of interest.

* C. Andrieu & A.D., Particle Filtering for Partially Observed Gaussian State Space Models, JRSS B, 2002. Pdf
- This paper shows how the Kalman filter can be use to compute the prior of a latent process, particularly useful for dynamic probit and tobit models.

* R. Chen & J. Liu, Mixture Kalman filters, JRSS B, 2000. Pdf
-
This paper shows that for conditionally linear Gausian models which includes switching state-space models, it is possible to devise a particle filter which is a mixture of Kalman filters.

A.D., S.J. Godsill & C. Andrieu, On Sequential Monte Carlo sampling methods for Bayesian filtering, (section IV) Stat. Comp., 2000 Pdf
- Section IV of this paper presents the same material as Chen & Liu (2000).

* K.P. Murphy, A.D., N. De Freitas & S. Russell, Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks, in Proc. Uncertainty in Artificial Intelligence, 2000. Pdf  
- This paper uses Rao-Blackwellization techniques to do efficient inference in high dimensional dynamic Bayes nets.

* P. Fearnhead, P. & P. Clifford (2003). On-line inference for hidden Markov models via particle filters. JRSS B, 2003.
- This paper shows that for discrete-valued latent processes, standard particle filters is inefficient and proposes an alternative approach that bypasses the sampling step. Demonstrate its use for switching state-space models.

* T. Schon, F. Gustafsson & P. Nordlund. Marginalized particle filters for mixed linear/nonlinear state-space models. IEEE Trans. Sig. Proc., 2005. Pdf
- This paper proposes some generalizations of the Rao-Blackwellized particle filters.


 SMC Smoothing

In the context of state-space models, it is often of interest to perform smoothing. Standard SMC approximations do provide an estimate of  the joint smoothing distributions but it is poor because of the degeneracy problem aforementioned. Specific smoothing procedures have been proposed to address this.

* A.D., S.J. Godsill & C. Andrieu, On Sequential Monte Carlo sampling methods for Bayesian filtering, Stat. Comp., 2000 Pdf  
- This paper describes an SMC implementation of forward filtering-backward smoothing to compute marginal smoothing distributions.

*  G. Kitagawa & S. Sato, Monte Carlo Smoothing and Self-organising State-Space Model. In SMC in Practice, 2001.
- This paper proposes to approximate fixed-interval marginal smoothing distributions by fixed-lag marginal smoothing distributions to reduce drastically the degeneracy problem.

* S.J. Godsill, A.D. & M. West, Monte Carlo Smoothing for Nonlinear Time Series, JASA, 2004 Pdf
- This paper describes SMC implementation of the forward filtering-backward sampling procedure to obtain samples approximately from the joint smoothing distribution, cost O(NT) per path for N particles and T data.

* P. Del Moral, A.D. & S.S. Singh, Forward Smoothing using SMC, Technical report Cambridge University TR 638, Sept. 2009, revised 2010 Pdf.
- This paper describes an SMC implementation of the forward filtering-backward smoothing to compute expectations of additive functionals that bypasses entirely the backward pass, presents theoretical results and applied it to on-line parameter estimation using on-line gradient and on-line EM. 

* M. Briers, A.D. & S. Maskell, Smoothing Algorithms for State-space Models, Ann. Instit. Stat. Math., 2010 Pdf
- This paper presents a generalized version of the two-filter smoothing formula which can be readily implemented using SMC methods to compute marginal smoothing distributions and sample approximately from the joint. Direct implementation has complexity O(N^2.T) and proposed rejection sampling yields O(N.T) to compute marginals, O(T) to sample approximately from the joint.

* P. Fearnhead, D. Wyncoll & J. Tawn, A Sequential Smoothing Algorithm with Linear Computational Cost, Biometrika, 2010 Pdf
- This paper describes an importance sampling procedure to reduce computational complexity of SMC implementation of direct implementation of generalized two-filter formula to O(N.T) to compute marginals.

* R. Douc, A. Garivier, E. Moulines & J. Olsson, On the Forward Filtering Backward Smoothing Particle Approximations of the Smoothing Distribution, Ann. Applied Proba, to appear Pdf
- This paper describes a rejection sampling method to implement forward filtering backward sampling, cost O(T) per path and presents various theoretical results.

SMC for on-line Bayesian static parameter estimation in state-space models

It is tempting to do on-line Bayesian static parameter estimation in state-space models using SMC and MCMC moves. Unfortunately, all these methods suffer from the path degeneracy problems so should be used cautiously.

* P. Fearnhead, MCMC, sufficient statistics and particle filters, JCGS, 2002 Pdf
-  This is a journal paper version of a chapter of the D.Phil of 
Fearnhead (1998) where it is proposed for the first time to use MCMC moves on static parameters to mitigate the degeneracy problem. The author clearly acknowledges that this does not entirely solve the problem; see the discussion.

* C. Andrieu, N. De Freitas and A.D., Sequential MCMC for Bayesian Model Selection, Proc. IEEE Workshop HOS, 1999 Pdf
- This paper presents an SMC algorithm for on-line Bayesian parameter estimation for autoregressive parameters with unknown order using
reversible jump MCMC moves. It is mentioned at the end that such methods are bound to suffer from the degeneracy problem.

* G. Storvik,
Particle filters for state-space models with the presence of unknown static parameters, IEEE Trans. Signal Processing, 2002 Pdf
- This paper proposes a more sophisticated version of Fearnhead's proposal.

* H.F. Lopes & R. S. Tsay, Particle Filters and Bayesian Inference in Financial Econometrics, J. Forecasting, 2010.
- This paper reviews at length the so-called particle learning, i.e. auxiliary particle filter with perfect adaption and MCMC moves for static parameters, for on-line Bayesian parameter estimation with detailed simulation results.

A pragmatic approach consists of adding an artificial dynamic noise on the static parameter (references to include.)

SMC for on-line and batch maximum likelihood inference of static parameter estimation in state-space models

As all the SMC procedures for on-line Bayesian inference suffer from the degeneracy problem, me and my colleagues have tried for many years to develop alternative methods which bypass this problem. If you accept to be non-Bayesian about the parameter, this is possible. An earlier approach we considered consists of using a pseudo-likelihood, this yields an estimate which is not statistically efficient but you do not even need particle filters in this case. Eventually, we have come up with a forward-only implementation of the forward filtering-backward smoothing procedure: it is the key to obtain stable algorithms to perform on-line Maximum Likelihood (ML) static parameter estimation in state-space models. For off-line approaches, all the smoothing approaches described previously can be and have been used.

* C. Andrieu, A.D. & V.B. Tadic, Online EM for parameter estimation in nonlinear-non Gaussian state-space models, Proc. IEEE CDC, 2005 Pdf
- This paper describe a pseudo-likelihood approach originally proposed by Ryden for finite HMM, establish theoretical results, application to on-line parameter estimation where pseudo-likelihood is maximized using the on-line EM.

* J. Olsson, O. Cappe, R. Douc & E. Moulines, SMC Smoothing with Application to Parameter Estimation in Nonlinear State-Space Models, Bernoulli, 2008 Pdf
- This paper quantifies the bias introduced by the fixed-lag approximation of Kitagawa & Sato, presents numerical results and uses it for parameter estimation using off-line EM.

* P. Del Moral, A.D. & S.S. Singh, Forward Smoothing using SMC, Technical report Cambridge University TR 638, Sept. 2009, revised 2010 Pdf.
- This paper describes an SMC implementation of the forward filtering-backward smoothing to compute expectations of additive functionals that bypasses entirely the backward pass, presents theoretical results and applied it to on-line parameter estimation using on-line gradient and on-line EM. 

* G. Poyiadjis, A.D. & S.S. Singh, Particle Approximations of the Score and Observed Information Matrix in State-Space Models with Application to Parameter Estimation, Biometrika, 2011 Pdf
- This paper describes an original approach to compute the score and OIM on-line that is more robust than the standard approach, it can be interpreted as a particular case of the forward smoothing (we didn't know at the time...) and we show how it can be used for on-line ML parameter estimation. 

* E.L. Ionides, A. Bhadra, Y. Atchade & A. King, Iterated Filtering, Annals of Statistics, 2011. Pdf
- This paper shows how can one can compute an approximation of the score vector using a perturbed state-space model and apply it to batch ML parameter estimation. It is especially useful in scenarios where one does not have access to the expression of the transition kernel of the latent process.

SMC for batch Bayesian static parameter estimation in state-space models

Obviously for batch joint Bayesian state and parameter estimation, you can use MCMC methods. However it can be difficult to design efficient algorithms. In the context where one can only simulate the latent process but does not have access to the transition prior, standard MCMC just fail. SMC can come to the rescue in these scenarios.

* Lee, D.S. & Chia, N.K.K, A particle algorithm for sequential Bayesian parameter estimation and model selection, IEEE Trans. Signal Proc., 2002.
- This paper proposes to use particle filters mixed with MCMC steps. MCMC steps are used to rejuvenate the whole state sequence and parameter so this is not an on-line algorithm as the complexity increases over time but can be used as an alternative to standard MCMC.

* C. Andrieu, A.D. & R. Holenstein, Particle Markov chain Monte Carlo methods (with discussion), JRSS B, 2010 Pdf
- This paper shows that it is possible to build high-dimensional proposal distributions for MCMC using SMC, it can be used to develop algorithms to sample from the joint posterior distribution of states and parameters. NB: Please don't skip the conditional SMC part, it is the nicest part of the paper.

* N. Whiteley, C. Andrieu & A.D., Efficient Bayesian Inference for Switching State-Space Models using Discrete Particle Markov Chain Monte Carlo methods, Technical report no. 1004 Department of Mathematics Bristol University 2010 Pdf
- This papre shows how the discrete particle filter of Fearnhead and Clifford (2003) can be used within MCMC, also presents a backward sampling procedure originally proposed by Whiteley in the discussion of the particle MCMC paper.

* N. Chopin, P. Jacob & O. Papaspiliopoulos. SMC^2: A SMC algorithm with particle MCMC updates. 2011 Available here.
- This paper substitutes to the MCMC used in the particle MCMC paper an SMC algorithm, you obtain a hierarchical SMC algorithm. This yields a powerful algorithm for sequential inference; this is not a truly on-line algorithm as the complexity increases over time.


SMC as an alternative/complement to MCMC

The idea of mixing SMC and MCMC to sample from a sequence of distributions all defined on the same space has appeared independently in various papers.

* G.E. Crooks,
Nonequilibrium Measurements of Free Energy Differences for Microscopically Reversible Markovian Systems, J. Stat. Phys., 1998. Pdf
- This paper presents a discrete-time version of the celebrated Jarzynski's equality in statistical physics (and slight generalization of it) showing that a sequence of non-homogeneous MCMC kernels "moving" towards a target can be reweighted using a clever importance sampling trick to obtain an unbiased estimate of normalizing constant and approximation of the target of interest.  Not quite SMC as no resampling is used.

* W. Gilks & C. Berzuini, Following a Moving Target: Monte Carlo Inference for Dynamic Bayesian Models, JRSS B, 2001
- This paper proposes to move the particles using MCMC moves with the appropriate invariant distribution so as to introduce diversity among particles. It was discussed in the framework of state-space models with static parameters. If you don't include any state, this gives you a method for sampling the sequence of posteriors of the parameter.

* R.M. Neal, Annealed Importance Sampling, Stat. Comp., 2001. Pdf
- This paper introduced independently 
a discrete-time version of the celebrated Jarzynski's equality in statistical physics and discusses carefully some applications to Bayesian inference with a sequence of annealed target distributions. Not quite SMC as no resampling is used. In this context, increasing the number of annealed auxiliary target distributions can prevent standard weights degeneracy.

* N. Chopin, A Sequential Particle Filter Method for Static Models, Biometrika, 2002.
- This paper details a careful application of the resample move algorithm for sampling from the sequence of posterior distributions of a static parameter.

* P. Del Moral, A.D. & A. Jasra, Sequential Monte Carlo Samplers, JRSS B, 2006. Pdf
- This paper discusses a framework generalizing annealed importance sampling and resample-move, discusses the potential benefits of resampling when the sequence of targets evolve quickly and scenarios where previous methods are not applicable.


Slides and Videolectures

* Slides by O. Cappe for EPFL workshop 2004.

* Video of my lectures at Machine Learning Summer School 2007.

* Video lectures: Tutorial at NIPS 2009 by A.D. & N. De Freitas

* Slides of P. Del Moral. for Machine Learning Sumeer School 2008.

* Video lectures at Machine Learning Sumeer School 2009 by S. Godsill.

* Video of my talk at French Statistical Meeting on particle MCMC (in french).

* Slides of my 8 hours course Statistical Mathematics summer school 2011 (to be posted). This is a much updated version of a course I gave in SAMSI in Fall 2008.

Code


* D. Creal: Matlab code and Ox code for all the examples in his recent tutorial paper (see above)

* N. De Freitas: Matlab code for Rao-Blackwellized particle filters and Unscented particle filter.

* P. Jacob: Python packages for 
particle Marginal Metropolis-Hastings and SMC^2.

* A.M. Johansen: C++ Sequential Monte Carlo template  link

* A. King, E.L. Ionides et al.: R package Statistical inference for partially observed models, includes bootstrap filter, iterated filtering and particle Marginal Metropolis-Hastings.

* A. Lee et al.: GPU code for particle filters and SMC samplers link and paper.

* D. Rasmussen: Matlab code for
particle Marginal Metropolis-Hastings implemented in this 2011 PLOS Comp. Biology paper.

* T. Schon: Matlab code for Rao-Blackwellised particle filter and EM for parameter estimation.

* D. Wilkinson: R code corresponding to the second edition of his cool book, includes
particle Marginal Metropolis-Hastings (chapter 10).