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 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.
* 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).