A Monte Carlo algorithm which updates a population of samples with a nested update. The easiest entry point is IMO to think about random-sample generalisation of state filter models via importance sampling. These are classically considered cousins to the linear Gaussian Kalman filter, applicable to more challenging models at the cost of using Monte Carlo approximations.
This has nothing to do with filters for particulate 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 theoretical basis 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 and also abstruse Mean Field Particle Methods. In practical applications we talk about particle filters, or sequential Monte Carlo, or bootstrap filters, or iterated importance sampling and these all mean confusingly similar things.
Introductions
- Pierre Jacob’s Particle methods for statistics reading list
- The lineage and reasoning is well explained by Cappe, Godsill, and Moulines (2007).
- Chopin and Papaspiliopoulos (2020)
Darko Jurić, Object Tracking: Particle Filter with Ease
Easy to explain with an example such as this particle filter in scala.
Feynman-Kac formulae
See Feynman-Kac.
System Identification in
Do not know the parameters governing the system dynamics and need to learn those too? See System identification with particle fitlers.
Relation to Ensemble Kalman filters
Yes.
Various extensions of Kalman filters as per Katzfuss, Stroud, and Wikle (2016).
Particle flow
Introduced to me by my colleague Adrian Bishop Profile.
Bunch and Godsill (2014); Daum, Huang, and Noushin (2010); Daum and Huang (2010); Daum and Huang (2009); Daum and Huang (2008); Daum and Huang (2013)
Non-Gaussian evolution
Jump process
I am interested in jump-process SMC (to be defined). For those I should apparently consult Graham and Méléard (1997);Grünbaum (1971);Méléard (1996);Shiga and Tanaka (1985).
On weird graphs
Christian Andersson Naesseth, Lindsten, and Schön (2014)
Rao-Blackwellized particle filter
Particles which represent marginalised densities (Murphy 2012, 23.6).
Tooling
Some MCMC toolkits incorporate SMC too.
- particles is a python library for teaching DIY particle filtering, to accompany the book Chopin and Papaspiliopoulos (2020).
- Johansen’s page, with C++ software
- Dirk Eddelbuettel’s lab created 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++.
- most probabilistic programming languages include a particle filter example.
References
Aldous, David. 2013. “Interacting Particle Systems as Stochastic Social Dynamics.” Bernoulli 19 (4): 1122–49.
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.
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.
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.
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.
Bunch, Pete, and Simon Godsill. 2014. “Approximations of the Optimal Importance Density Using Gaussian Particle Flow Importance Sampling.” arXiv.
Cappe, Olivier, Simon J. Godsill, and Eric Moulines. 2007. “An Overview of Existing Methods and Recent Advances in Sequential Monte Carlo.” Proceedings of the IEEE 95 (5): 899–924.
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.
Cérou, Frédéric, and Arnaud Guyader. 2016. “Fluctuation Analysis of Adaptive Multilevel Splitting.” The Annals of Applied Probability 26 (6): 3319–80.
Chen, Bin, and Yongmiao Hong. 2012. “Testing for the Markov Property in Time Series.” Econometric Theory 28 (01): 130–78.
Chopin, Nicolas, and Omiros Papaspiliopoulos. 2020. An Introduction to Sequential Monte Carlo. Springer Series in Statistics. Springer International Publishing.
Corenflos, Adrien, James Thornton, George Deligiannidis, and Arnaud Doucet. 2021. “Differentiable Particle Filtering via Entropy-Regularized Optimal Transport.” arXiv:2102.07850 [Cs, Stat], June.
Crisan, Dan, and Joaquín Míguez. 2014. “Particle-Kernel Estimation of the Filter Density in State-Space Models.” Bernoulli 20 (4): 1879–929.
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.
Daum, Fred, and Jim Huang. 2008. “Particle Flow for Nonlinear Filters with Log-Homotopy.” In Signal and Data Processing of Small Targets 2008, 6969:414–25. SPIE.
———. 2009. “Nonlinear Filters with Particle Flow.” In Signal and Data Processing of Small Targets 2009, 7445:315–23. SPIE.
———. 2010. “Generalized Particle Flow for Nonlinear Filters.” In Signal and Data Processing of Small Targets 2010, 7698:209–20. SPIE.
———. 2013. “Particle Flow with Non-Zero Diffusion for Nonlinear Filters.” In Signal Processing, Sensor Fusion, and Target Recognition XXII, 8745:226–38. SPIE.
Daum, Fred, Jim Huang, and Arjang Noushin. 2010. “Exact Particle Flow for Nonlinear Filters.” In Signal Processing, Sensor Fusion, and Target Recognition XIX, 7697:92–110. SPIE.
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.
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.
———. 2011. “An Adaptive Sequential Monte Carlo Method for Approximate Bayesian Computation.” Statistics and Computing 22 (5): 1009–20.
Del Moral, Pierre, Peng Hu, and Liming Wu. 2011. On the Concentration Properties of Interacting Particle Processes. Vol. 3. Now Publishers.
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, Volume 337. Berlin, Heidelberg: Springer.
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.
Devlin, Lee, Paul Horridge, Peter L Green, and Simon Maskell. 2021. “The No-U-Turn Sampler as a Proposal Distribution in a Sequential Monte Carlo Sampler with a Near-Optimal L-Kernel,” 5.
Doucet, Arnaud, Nando de Freitas, and Neil Gordon. 2001a. “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.
Doucet, Arnaud, Nando Freitas, and Neil Gordon. 2001b. Sequential Monte Carlo Methods in Practice. New York, NY: Springer New York.
Doucet, Arnaud, Simon Godsill, and Christophe Andrieu. 2000. “On Sequential Monte Carlo Sampling Methods for Bayesian Filtering.” Statistics and Computing 10 (3): 197–208.
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.” arXiv:1304.5768 [Stat], April.
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.
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.
Eddelbuettel, Dirk, and Romain François. 2011. “Rcpp: Seamless R and C++ Integration.” Journal of Statistical Software 40 (8).
Evensen, Geir. 2009. Data Assimilation - The Ensemble Kalman Filter. Berlin; Heidelberg: Springer.
Fearnhead, Paul, and Hans R. Künsch. 2018. “Particle Filters and Data Assimilation.” Annual Review of Statistics and Its Application 5 (1): 421–49.
Garbuno-Inigo, Alfredo, Franca Hoffmann, Wuchen Li, and Andrew M. Stuart. 2020. “Interacting Langevin Diffusions: Gradient Structure and Ensemble Kalman Sampler.” SIAM Journal on Applied Dynamical Systems 19 (1): 412–41.
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.
Graham, Carl, and Sylvie Méléard. 1997. “Stochastic Particle Approximations for Generalized Boltzmann Models and Convergence Estimates.” The Annals of Probability 25 (1): 115–32.
Grünbaum, F. Alberto. 1971. “Propagation of Chaos for the Boltzmann Equation.” Archive for Rational Mechanics and Analysis 42 (5): 323–45.
Gu, Shixiang, Zoubin Ghahramani, and Richard E Turner. 2015. “Neural Adaptive Sequential Monte Carlo.” In Advances in Neural Information Processing Systems 28, edited by C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, 2629–37. Curran Associates, Inc.
Gunawan, David, Khue-Dung Dang, Matias Quiroz, Robert Kohn, and Minh-Ngoc Tran. 2018. “Subsampling Sequential Monte Carlo for Static Bayesian Models,” May.
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.
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.
Ionides, Edward L., Anindya Bhadra, Yves Atchadé, and Aaron King. 2011. “Iterated Filtering.” The Annals of Statistics 39 (3): 1776–1802.
Johansen, Adam M. 2009. “SMCTC: Sequential Monte Carlo in C++.” Journal of Statistical Software 30 (6).
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.
Jonschkowski, Rico, Divyam Rastogi, and Oliver Brock. 2018. “Differentiable Particle Filters: End-to-End Learning with Algorithmic Priors.” arXiv:1805.11122 [Cs, Stat], May.
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.
Kappen, H. J., and H. C. Ruiz. 2016. “Adaptive Importance Sampling for Control and Inference.” Journal of Statistical Physics 162 (5): 1244–66.
Katzfuss, Matthias, Jonathan R. Stroud, and Christopher K. Wikle. 2016. “Understanding the Ensemble Kalman Filter.” The American Statistician 70 (4): 350–57.
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.
Kim, Jin W., and Prashant G. Mehta. 2019. “An Optimal Control Derivation of Nonlinear Smoothing Equations,” April.
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.
Lai, Jinlin, Justin Domke, and Daniel Sheldon. 2022. “Variational Marginal Particle Filters.” In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 875–95. PMLR.
Lee, Anthony, and Nick Whiteley. 2016. “Variance Estimation in the Particle Filter.” arXiv:1509.00394 [Stat], June.
Léonard, Christian. 2014. “A Survey of the Schrödinger Problem and Some of Its Connections with Optimal Transport.” Discrete & Continuous Dynamical Systems - A 34 (4): 1533.
Liu, Qiang, and Dilin Wang. 2019. “Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm.” In Advances In Neural Information Processing Systems.
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.
Mandel, Jan. 2009. “A Brief Tutorial on the Ensemble Kalman Filter.” arXiv:0901.3725 [Physics], January.
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.
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.
Murphy, Kevin P. 2012. Machine learning: a probabilistic perspective. 1 edition. Adaptive computation and machine learning series. Cambridge, MA: MIT Press.
Naesseth, Christian A., Fredrik Lindsten, and Thomas B. Schön. 2022. “Elements of Sequential Monte Carlo.” arXiv:1903.04797 [Cs, Stat], March.
Naesseth, Christian Andersson, Fredrik Lindsten, and Thomas B Schön. 2014. “Sequential Monte Carlo for Graphical Models.” In Advances in Neural Information Processing Systems. Vol. 27. Curran Associates, Inc.
Neal, Radford M. 1998. “Annealed Importance Sampling.” arXiv.
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–1748 Vol.2.
Reich, Sebastian. 2019. “Data Assimilation: The Schrödinger Perspective.” Acta Numerica 28 (May): 635–711.
Reich, Sebastian, and Simon Weissmann. 2019. “Fokker-Planck Particle Systems for Bayesian Inference: Computational Approaches,” November.
Reshef, Yakir A., David N. Reshef, Pardis C. Sabeti, and Michael Mitzenmacher. 2014. “Theoretical Foundations of Equitability and the Maximal Information Coefficient.” arXiv:1408.4908 [Cs, Math, q-Bio, Stat], August.
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.
Robinson, P. M. 1983. “Nonparametric Estimators for Time Series.” Journal of Time Series Analysis 4 (3): 185–207.
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).
Salomone, Robert, Leah F. South, Christopher C. Drovandi, and Dirk P. Kroese. 2018. “Unbiased and Consistent Nested Sampling via Sequential Monte Carlo,” May.
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.
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–65.
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–89.
Taghvaei, Amirhossein, and Prashant G. Mehta. 2021. “An Optimal Transport Formulation of the Ensemble Kalman Filter.” IEEE Transactions on Automatic Control 66 (7): 3052–67.
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.
Virrion, Benjamin. 2020. “Deep Importance Sampling.” arXiv:2007.02692 [q-Fin], July.
No comments yet. Why not leave one?