Sequential Monte Carlo

also “Particle Filters” and a profusion of other simultaneous-discovery names

A randomised generalisation of state filter models such as the Kalman Filter.

Easy to explain with an example:

A scalable particle filter in scala

EDIT: Apparently SMC is more general - it does not necessarily assume that the additional axes are assimilated in time, but can index any arbitrary dimension of your data, as long as you are approximating the right likelihood. Regardless…

  • Introduction to the particle Gibbs Sampler
  • Pierre Jacob’s Particle methods for statistics reading list
  • Johansen’s page, with C++ software
  • Dirk EdelBeuttel 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++
  • 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.

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.

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.

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. 2001. Sequential Monte Carlo Methods in Practice. New York, NY: Springer New York. http://public.eblib.com/choice/publicfullrecord.aspx?p=3087052.

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.

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.

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.

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.

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., 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.

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.