Particle filters

incorporating Interacting Particle Systems, Sequential Monte Carlo and a profusion of other simultaneous-discovery names


A field of study concerning certain kinds of stochastic processes. The easiest entry point is IMO to think about randomised generalisation of state filter models. This has nothing to to with filters for particular matter as seen in respirators.

There is too much confusing and unhelpful terminology here, and I am only at the fringe of this field so I will not attempt to typologize. Let us clear up the main stumbling block though: somehow the field has coalesced under the banner of interacting particle systems which is an awful unsearchable name which could mean anything, and indeed does in other disciplines. Wikipedia disambiguates this problem with the gritty but clearer name Mean Field Particle Methods. In practical applications we talk about particle filters.s

Easy to explain with an example such as A scalable particle filter in scala. There is a lot more too this, and I will only touch upon it here. These are classically considered coursins to the linear Gaussian Kalman filter applicable to more challenging models at the cost of using Mote Carlo approximations. That will do as a starting point.

Theoretical framing

There is a mathematically rich theory about how it all works. The notoriously abstruse Del Moral (2004); Doucet, Freitas, and Gordon (2001a) are universally commended for unifying and making consistent the diffusion processes and Feynman-Kac formulae and “propagation of chaos”. I will get around to them eventually.

I am especially interested in jump-process (as opposed to diffusion) approaches. For those I should apparently consult Graham and Méléard (1997); Grünbaum (1971); Méléard (1996); Shiga and Tanaka (1985).

Miscellaneous practical introductions

Tooling

  • particles

    • state-space models may be defined as python objects, in a basic form of probabilistic programming.
    • Bootstrap filter, guided filter, auxiliary particle filter.
    • Kalman filter and smoother.
    • Baum-Welch filter and smoother (for hidden Markov models).
    • Sequential quasi-Monte Carlo (and related tools: Hilbert ordering, RQMC sampling).
    • smoothing: on-line and off-line, O(N^2) and O(N) versions of standard algorithms (FFBS, two-filter)
    • SMC samplers: IBIS (data-tempering) and SMC tempering. Static models may be defined as Python objects.
    • Bayesian inference for state-space models: several PMCMC (particle MCMC algorithms are implemented), such as PMMH and Particle Gibbs. Also SMC^2.
  • Johansen’s page, with C++ software
  • Dirk Eddelbuettel lab has RCppSMC for R integration of the Johansen stuff. Documentation is not great – it only consists of black-box toy problems without any hint of how you would construct, e.g. a likelihood function, so I can’t evaluate how easy this would be to use, as opp plain C++

Aldous, David. 2013. “Interacting Particle Systems as Stochastic Social Dynamics.” Bernoulli 19 (4): 1122–49. https://doi.org/10.3150/12-BEJSP04.

Andrews, Donald W. K. 1994. “Empirical Process Methods in Econometrics.” In Handbook of Econometrics, edited by Robert F. Engle and Daniel L. McFadden, 4:2247–94. Elsevier. http://dido.econ.yale.edu/P/cp/p08b/p0887.pdf.

Andrieu, Christophe, Arnaud Doucet, and Roman Holenstein. 2010. “Particle Markov Chain Monte Carlo Methods.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 72 (3): 269–342. https://doi.org/10.1111/j.1467-9868.2009.00736.x.

Arulampalam, M. S., S. Maskell, N. Gordon, and T. Clapp. 2002. “A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking.” IEEE Transactions on Signal Processing 50 (2): 174–88. https://doi.org/10.1109/78.978374.

Bretó, Carles, Daihai He, Edward L. Ionides, and Aaron A. King. 2009. “Time Series Analysis via Mechanistic Models.” The Annals of Applied Statistics 3 (1): 319–48. https://doi.org/10.1214/08-AOAS201.

Cappe, O., S. J. Godsill, and E. Moulines. 2007. “An Overview of Existing Methods and Recent Advances in Sequential Monte Carlo.” Proceedings of the IEEE 95 (5): 899–924. https://doi.org/10.1109/JPROC.2007.893250.

Cérou, F., P. Del Moral, T. Furon, and A. Guyader. 2011. “Sequential Monte Carlo for Rare Event Estimation.” Statistics and Computing 22 (3): 795–808. https://doi.org/10.1007/s11222-011-9231-6.

Cérou, Frédéric, and Arnaud Guyader. 2016. “Fluctuation Analysis of Adaptive Multilevel Splitting.” The Annals of Applied Probability 26 (6). Institute of Mathematical Statistics: 3319–80. https://doi.org/10.1214/16-AAP1177.

Chen, Bin, and Yongmiao Hong. 2012. “Testing for the Markov Property in Time Series.” Econometric Theory 28 (01): 130–78. https://doi.org/10.1017/S0266466611000065.

Crisan, Dan, and Joaquín Míguez. 2014. “Particle-Kernel Estimation of the Filter Density in State-Space Models.” Bernoulli 20 (4): 1879–1929. https://doi.org/10.3150/13-BEJ545.

Crisan, D, P Del Moral, and T Lyons. 1999. “Discrete Filtering Using Branching and Interacting Particle Systems.” Markov Processes and Related Fields 5 (3): 293–318.

Del Moral, Pierre. 2004. Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications. 2004 edition. Latheronwheel, Caithness: Springer.

Del Moral, Pierre, and Arnaud Doucet. 2009. “Particle Methods: An Introduction with Applications.” INRIA.

———. 2010. “Interacting Markov Chain Monte Carlo Methods for Solving Nonlinear Measure-Valued Equations.” The Annals of Applied Probability 20 (2): 593–639. https://doi.org/10.1214/09-AAP628.

Del Moral, Pierre, Arnaud Doucet, and Ajay Jasra. 2006. “Sequential Monte Carlo Samplers.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 68 (3): 411–36. https://doi.org/10.1111/j.1467-9868.2006.00553.x.

———. 2011. “An Adaptive Sequential Monte Carlo Method for Approximate Bayesian Computation.” Statistics and Computing 22 (5): 1009–20. https://doi.org/10.1007/s11222-011-9271-y.

Del Moral, Pierre, Peng Hu, and Liming Wu. 2011. “On the Concentration Properties of Interacting Particle Processes.” Foundations and Trends® in Machine Learning 3 (3-4): 225–389. https://doi.org/10.1561/2200000026.

Del Moral, Pierre, and Pascal Lezaud. 2006. “Branching and Interacting Particle Interpretations of Rare Event Probabilities.” In Stochastic Hybrid Systems, pp 277–323. Lecture Notes in Control and Information Science, Vol. 337. Berlin, Heidelberg: Springer. https://doi.org/10.1007/11587392_9.

Del Moral, Pierre, and Laurent Miclo. 2000. “Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering.” In Séminaire de Probabilités XXXIV, 1–145. Lecture Notes in Mathematics 1729. Springer. http://perso.math.univ-toulouse.fr/miclo/files/2012/04/branching.pdf.

Doucet, Arnaud, Nando Freitas, and Neil Gordon. 2001a. Sequential Monte Carlo Methods in Practice. New York, NY: Springer New York. http://public.eblib.com/choice/publicfullrecord.aspx?p=3087052.

Doucet, Arnaud, Nando de Freitas, and Neil Gordon. 2001b. “An Introduction to Sequential Monte Carlo Methods.” In Sequential Monte Carlo Methods in Practice, edited by Arnaud Doucet, Nando de Freitas, and Neil Gordon, 3–14. Statistics for Engineering and Information Science. Springer New York. http://link.springer.com/chapter/10.1007/978-1-4757-3437-9_1.

Doucet, Arnaud, Simon Godsill, and Christophe Andrieu. 2000. “On Sequential Monte Carlo Sampling Methods for Bayesian Filtering.” Statistics and Computing 10 (3): 197–208. https://doi.org/10.1023/A:1008935410038.

Doucet, Arnaud, Pierre E. Jacob, and Sylvain Rubenthaler. 2013. “Derivative-Free Estimation of the Score Vector and Observed Information Matrix with Application to State-Space Models,” April. http://arxiv.org/abs/1304.5768.

Doucet, Arnaud, and Adam M. Johansen. 2009. “A Tutorial on Particle Filtering and Smoothing: Fifteen Years Later.” In Handbook of Nonlinear Filtering, 12:656–704. http://www.warwick.ac.uk/fac/sci/statistics/staff/academic-research/johansen/publications/dj11.pdf.

Drovandi, Christopher C., Anthony N. Pettitt, and Roy A. McCutchan. 2016. “Exact and Approximate Bayesian Inference for Low Integer-Valued Time Series Models with Intractable Likelihoods.” Bayesian Analysis 11 (2): 325–52. https://doi.org/10.1214/15-BA950.

Eddelbuettel, Dirk, and Romain François. 2011. “Rcpp: Seamless R and C++ Integration.” Journal of Statistical Software 40 (8). https://doi.org/10.18637/jss.v040.i08.

Evensen, Geir. 2009. Data Assimilation - the Ensemble Kalman Filter. Berlin; Heidelberg: Springer. http://link.springer.com/book/10.1007%2F978-3-642-03711-5.

Fearnhead, Paul, and Hans R. Künsch. 2018. “Particle Filters and Data Assimilation.” Annual Review of Statistics and Its Application 5 (1): 421–49. https://doi.org/10.1146/annurev-statistics-031017-100232.

Gland, Francçois Le, and Laurent Mevel. 2000. “Exponential Forgetting and Geometric Ergodicity in Hidden Markov Models.” Mathematics of Control, Signals and Systems 13 (1): 63–93. https://doi.org/10.1007/PL00009861.

Graham, Carl, and Sylvie Méléard. 1997. “Stochastic Particle Approximations for Generalized Boltzmann Models and Convergence Estimates.” The Annals of Probability 25 (1). Institute of Mathematical Statistics: 115–32. https://doi.org/10.1214/aop/1024404281.

Grünbaum, F. Alberto. 1971. “Propagation of Chaos for the Boltzmann Equation.” Archive for Rational Mechanics and Analysis 42 (5): 323–45. https://doi.org/10.1007/BF00250440.

Gunawan, David, Khue-Dung Dang, Matias Quiroz, Robert Kohn, and Minh-Ngoc Tran. 2018. “Subsampling Sequential Monte Carlo for Static Bayesian Models,” May. https://arxiv.org/abs/1805.03317v2.

Hong, Yongmiao, and Haitao Li. 2005. “Nonparametric Specification Testing for Continuous-Time Models with Applications to Term Structure of Interest Rates.” Review of Financial Studies 18 (1): 37–84. https://doi.org/10.1093/rfs/hhh006.

Hu, Xiao-Li, T.B. Schon, and L. Ljung. 2008. “A Basic Convergence Result for Particle Filtering.” IEEE Transactions on Signal Processing 56 (4): 1337–48. https://doi.org/10.1109/TSP.2007.911295.

Ionides, Edward L., Anindya Bhadra, Yves Atchadé, and Aaron King. 2011. “Iterated Filtering.” The Annals of Statistics 39 (3): 1776–1802. https://doi.org/10.1214/11-AOS886.

Johansen, Adam M. 2009. “SMCTC: Sequential Monte Carlo in C++.” Journal of Statistical Software 30 (6). https://doi.org/10.18637/jss.v030.i06.

Johansen, Adam M., Pierre Del Moral, and Arnaud Doucet. 2006. “Sequential Monte Carlo Samplers for Rare Events.” In Proceedings of the 6th International Workshop on Rare Event Simulation, 256–67. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.2888.

Kantas, Nikolas, Arnaud Doucet, Sumeetpal S. Singh, Jan Maciejowski, and Nicolas Chopin. 2015. “On Particle Methods for Parameter Estimation in State-Space Models.” Statistical Science 30 (3): 328–51. https://doi.org/10.1214/14-STS511.

Kawamoto, Kazuhiko. 2007. “Optical Flow–Driven Motion Model with Automatic Variance Adjustment for Adaptive Tracking.” In Computer Vision – ACCV 2007, edited by Yasushi Yagi, Sing Bing Kang, In So Kweon, and Hongbin Zha, 555–64. Lecture Notes in Computer Science 4843. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-76386-4_52.

Künsch, Hans R. 2005. “Recursive Monte Carlo Filters: Algorithms and Theoretical Analysis.” The Annals of Statistics 33 (5): 1983–2021.

———. 2013. “Particle Filters.” Bernoulli 19 (4): 1391–1403. https://doi.org/10.3150/12-BEJSP07.

Lee, Anthony, and Nick Whiteley. 2016. “Variance Estimation in the Particle Filter,” June. http://arxiv.org/abs/1509.00394.

Liu, Qiang, and Dilin Wang. 2019. “Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm.” In Advances in Neural Information Processing Systems. http://arxiv.org/abs/1608.04471.

Maddison, Chris J., Dieterich Lawson, George Tucker, Nicolas Heess, Mohammad Norouzi, Andriy Mnih, Arnaud Doucet, and Yee Whye Teh. 2017. “Filtering Variational Objectives.” arXiv Preprint arXiv:1705.09279. https://arxiv.org/abs/1705.09279.

Mandel, Jan. 2009. “A Brief Tutorial on the Ensemble Kalman Filter,” January. http://arxiv.org/abs/0901.3725.

Matos, Joao Amaro de, and Marcelo Fernandes. 2007. “Testing the Markov Property with High Frequency Data.” Journal of Econometrics, Semiparametric methods in econometrics, 141 (1): 44–64. https://doi.org/10.1016/j.jeconom.2007.01.007.

Méléard, Sylvie. 1996. “Asymptotic Behaviour of Some Interacting Particle Systems; McKean-Vlasov and Boltzmann Models.” In Probabilistic Models for Nonlinear Partial Differential Equations: Lectures Given at the 1st Session of the Centro Internazionale Matematico Estivo (C.I.M.E.) Held in Montecatini Terme, Italy, May 22–30, 1995, edited by Carl Graham, Thomas G. Kurtz, Sylvie Méléard, Philip E. Protter, Mario Pulvirenti, Denis Talay, Denis Talay, and Luciano Tubaro, 1627:42–95. Lecture Notes in Mathematics. Berlin, Heidelberg: Springer. https://doi.org/10.1007/BFb0093177.

Noyer, J.C., P. Lanvin, and M. Benjelloun. 2004. “Model-Based Tracking of 3D Objects Based on a Sequential Monte-Carlo Method.” In Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, 2004, 2:1744–8 Vol.2. https://doi.org/10.1109/ACSSC.2004.1399459.

Reshef, Yakir A., David N. Reshef, Pardis C. Sabeti, and Michael Mitzenmacher. 2014. “Theoretical Foundations of Equitability and the Maximal Information Coefficient,” August. http://arxiv.org/abs/1408.4908.

Roberts, G. O., and O. Stramer. 2001. “On Inference for Partially Observed Nonlinear Diffusion Models Using the Metropolis–Hastings Algorithm.” Biometrika 88 (3): 603–21. https://doi.org/10.1093/biomet/88.3.603.

Robinson, P. M. 1983. “Nonparametric Estimators for Time Series.” Journal of Time Series Analysis 4 (3): 185–207. https://doi.org/10.1111/j.1467-9892.1983.tb00368.x.

Rubinstein, Reuven Y., and Dirk P. Kroese. 2016. Simulation and the Monte Carlo Method. 3 edition. Wiley Series in Probability and Statistics. Hoboken, New Jersey: Wiley.

Rubinstein, Reuven Y., Ad Ridder, and Radislav Vaisman. 2014. Fast Sequential Monte Carlo Methods for Counting and Optimization. Wiley Series in Probability and Statistics. Hoboken, New Jersey: Wiley.

Runge, Jakob, Reik V. Donner, and Jürgen Kurths. 2015. “Optimal Model-Free Prediction from Multivariate Time Series.” Physical Review E 91 (5). https://doi.org/10.1103/PhysRevE.91.052909.

Shiga, Tokuzo, and Hiroshi Tanaka. 1985. “Central Limit Theorem for a System of Markovian Particles with Mean Field Interactions.” Zeitschrift Für Wahrscheinlichkeitstheorie Und Verwandte Gebiete 69 (3): 439–59. https://doi.org/10.1007/BF00532743.

Sisson, S.A, Y. Fan, and Mark M Tanak. 2009. “Correction for Sisson et Al., Sequential Monte Carlo Without Likelihoods.” Proceedings of the National Academy of Sciences 106 (39): 16889–9. https://doi.org/10.1073/pnas.0908847106.

Sisson, S. A., Y. Fan, and Mark M. Tanaka. 2007. “Sequential Monte Carlo Without Likelihoods.” Proceedings of the National Academy of Sciences 104 (6): 1760–5. https://doi.org/10.1073/pnas.0607208104.

Vergé, Christelle, Cyrille Dubarry, Pierre Del Moral, and Eric Moulines. 2013. “On Parallel Implementation of Sequential Monte Carlo Methods: The Island Particle Model.” Statistics and Computing, November, 1–18. https://doi.org/10.1007/s11222-013-9429-x.