Course on Computational Statistics and Monte Carlo methods

Sequential Monte Carlo Methods

* Check the more recent SMC & Particle Filters Resources 2012

* Videolecture: Tutorial SMC Methods at NIPS 2009 (with Nando De Freitas)
* Slides of the NIPS tutorial slides1 slides2

Objectives

To provide an introduction to SMC methods and their applications.

Handouts

Lecture 1 - Introduction & Motivation

Lecture 2 - Importance Sampling & Sequential Importance Sampling

Matlab code for linear Gaussian example: Kalman + prior and locally optimal proposal SIS code

Additional reading:
- Kong, Liu & Wong, Sequential imputation and Bayesian missing data problems, JASA, 1994 Pdf file

Lecture 3 - Sequential Importance Sampling Resampling

Additional reading:
- Doucet, De Freitas and Gordon, An introduction to Sequential Monte Carlo, in SMC in Practice, 2001 Ps file here
- Gordon, Salmond & Smith, Novel approach to nonlinear non-Gaussian Bayesian state estimation, IEE, 1993 Pdf file

Matlab code for linear Gaussian example: Kalman + prior and locally optimal proposal SMC code

Lecture 4 - Advanced Sequential Monte Carlo methods

Additional reading:

Tutorial covering all these advanced methods and more.
- A.D. and A. Johansen, Particle filtering and smoothing: Fifteen years later, in Handbook of Nonlinear Filtering (eds. D. Crisan et B. Rozovsky), Oxford University Press, 2011 Pdf (Updated version)

Or if you prefer reading the original papers....
Auxiliary particle filters
- M.K. Pitt and N. Shephard, Filtering via Simulation: Auxiliary Particle Filter, JASA, 1999 Pdf
- A. Johansen and A. Doucet, A Note on Auxiliary Particle Filters, Stat. Proba. Letters, 2008. Pdf
Resample move
- W. Gilks and C. Berzuini, Following a moving target: Monte Carlo inference for dynamic Bayesian models, JRSS B, 2001 Pdf file here
Fixed lag sampling
- A. Doucet et al., Efficient Block Sampling Strategies for Sequential Monte Carlo", (with M. Briers & S. Senecal), JCGS, 2006. Pdf
Variance reduction
- C. Andrieu and A. Doucet, Particle Filtering for Partially Observed Gaussian State Space Models, JRSS B, 2002. Pdf
- R. Chen and J. Liu, Mixture Kalman filters, JRSSB, 2000. Pdf
- A. Doucet, S.J. Godsill and C. Andrieu, On Sequential Monte Carlo sampling methods for Bayesian filtering, (section IV) Stat. Comp., 2000 Pdf

Lecture 5 - Sequential Parameter Estimation for State-Space models: Bayesian and ML approaches

Tutorial discussing almost all the SMC-based methods for offline and sequential parameter estimation.
- 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
- C. Andrieu, A.D. & R. Holenstein, Particle Markov chain Monte Carlo methods (with discussion), JRSS B, 2010 Pdf

Bayesian approaches
* C. Andrieu, N. De Freitas and A. Doucet, Sequential MCMC for Bayesian Model Selection, Proc. IEEE Workshop HOS, 1999 Pdf
* P. Fearnhead, MCMC, sufficient statistics and particle filters, JCGS, 2002 Pdf
* G. Storvik, Particle filters for state-space models with the presence of unknown static parameters, IEEE Trans. Signal Processing, 2002 Pdf

Non-Bayesian approaches
* C. Andrieu, A. Doucet and V.B. Tadic, Online EM for parameter estimation in nonlinear-non Gaussian state-space models, Proc. IEEE CDC, 2005 Pdf
* G. Poyadjis, A. Doucet and S.S. Singh, Particle Approximations of the Score and Observed Information Matrix in State-Space Models with Application to Parameter Estimation, Biometrika, to appear 2010. Pdf (Extended version of Maximum Likelihood Parameter Estimation using Particle Methods, Joint Statistical Meeting, 2005 Pdf)
* P. Del Moral, A. Doucet & S.S. Singh, Forward Smoothing using Sequential Monte Carlo, technical report, Cambridge University, 2009 Pdf
Application of recursive maximum likelihood
* C. Caron, R. Gottardo and A. Doucet, On-line Changepoint Detection and Parameter Estimation for Genome Wide Transcript Analysis, Technical report 2008 Pdf
* R. Martinez-Cantin, J. Castellanos and N. de Freitas. Analysis of Particle Methods for Simultaneous Robot Localization and Mapping and a New Algorithm: Marginal-SLAM. International Conference on Robotics and Automation Pdf

Lecture 6 - Guest Lecturer: Christophe Andrieu - Adaptive Markov chain Monte Carlo methods

Lecture 7 - Sequential Monte Carlo Samplers

* P. Del Moral, A. Doucet & A. Jasra, Sequential Monte Carlo Samplers, JRSSB, 2006. Pdf

Lecture 8 - Guest Lecturer: Alexandre Chorin.

Final Projects

You will have to study a few papers on a specific SMC topic, write a report, implement some algorithms and make a presentation.
Potential projects are listed here. I am open to suggestions but you need to discuss it with me beforehand.

References

Basic Introduction to SMC for state-space models

* A. Doucet, N. De Freitas and N.J. Gordon, An introduction to Sequential Monte Carlo, Ps file here

"Standard" SMC papers

* J. Carpenter, P. Clifford and P. Fearnhead, An Improved Particle Filter for Non-linear Problems, Pdf file here
* A. Doucet, S.J. Godsill and C. Andrieu, On Sequential Monte Carlo sampling methods for Bayesian filtering, Stat. Comp., 2000 (reprinted 2005) Pdf file here
* M.K. Pitt and N. Shephard, Filtering via Simulation: Auxiliary Particle Filter, JASA, 1999 Pdf file here
* J.S. Liu and R. Chen, Sequential Monte Carlo methods for dynamic systems, JASA, 1998 Pdf file here

SMC papers for sequential static parameter estimation in state-space models

- Bayesian approaches

* C. Andrieu, N. De Freitas and A. Doucet, Sequential MCMC for Bayesian Model Selection, Proc. IEEE Workshop HOS, 1999 Pdf file here
* P. Fearnhead, MCMC, sufficient statistics and particle filters, JCGS, 2002 Pdf file here
* G. Storvik, Particle filters for state-space models with the presence of unknown static parameters, IEEE Trans. Signal Processing, 2002 Pdf file here

- Non-Bayesian approaches

* P. Del Moral, A. Doucet & S.S. Singh, Forward Smoothing using Sequential Monte Carlo, technical report, Cambridge University, 2009 Pdf
* G. Poyadjis, A. Doucet and S.S. Singh, Particle Approximations of the Score and Observed Information Matrix in State-Space Models with Application to Parameter Estimation, Biometrika, to appear 2010. Pdf
* C. Andrieu, A. Doucet and V.B. Tadic, Online EM for parameter estimation in nonlinear-non Gaussian state-space models, Proc. IEEE CDC, 2005 Pdf file here
* G. Poyadjis, A. Doucet and S.S. Singh, Maximum Likelihood Parameter Estimation using Particle Methods, Joint Statistical Meeting, 2005 Pdf here

SMC papers for off-line static parameter estimation in state-space models

* C. Andrieu, A.D. & R. Holenstein, Particle Markov chain Monte Carlo methods (with discussion), JRSS B, 2010 Pdf

Books discussing extensively SMC methods

* Del Moral, Feynman-Kac Formulae, Springer-Verlag, 2004 - All you want to know about the theory of SMC.
* Doucet, De Freitas & Gordon (eds), Sequential Monte Carlo in Practice, Springer-Verlag: 2001 - A collection of chapters on the subject.
* Cappe, Moulines & Ryden, Inference in Hidden Markov Models, Springer-Verlag, 2005 - Discuss at length the applications of SMC to state-space models
* Liu, Monte Carlo Methods in Scientific Computing, Springer-Verlag, 2001 - Discuss SMC and also MCMC.

Books discussing MCMC (for those not familiar with this class of methods)

* Robert & Casella, Monte Carlo Statistical Methods, 2004.