2008-09 Program on Sequential Monte Carlo Methods

Introduction

This 12 month SAMSI program developed new approaches to scientific/statistical computing using innovative Sequential Monte Carlo (SMC) methods. The program addressed  fundamental challenges in developing effective sequential and adaptive simulation methods for computations underlying inference and decision analysis. The research blended conceptual innovation in new and emerging methods with evaluation in substantial applied contexts drawn from areas such as control, communications and robotics engineering, financial and macro-economics, among others. Researchers from statistics, computer science, information engineering and applied mathematics were involved, and the program promoted the opportunity for both methodological and theoretical research. The interdisciplinary aspects of the program wee substantial, as was the attractiveness for students and postdocs.

Organizing Committee:

Co-Chairs: Arnaud Doucet (British Columbia, Statistics and Computer Science) and Simon Godsill (Cambridge UK, Information Engineering).

Monica Bugallo (Stony Brook, Electrical and Computer Engineering), Petar Djuric (Stony Brook, Electrical and Computer Engineering), Michael Jordan (Berkeley, Statistics and Computer Science), Jun Liu (Harvard, Statistics), Gareth Roberts (Warwick, Statistics), Raquel Prado (Santa Cruz, Applied Mathematics and Statistics), Neil Shephard, (Oxford, Statistics and Econometrics), and Simon Tavare (Cambridge, Computational Biology). Local Scientific Coordinator: Mike West (Duke, Statistical Science); National Advisory Council Liaison: Richard Durrett (Cornell University); Directorate Liaison: James Berger (SAMSI)

Background

Monte Carlo (MC) methods are central to modern numerical modelling and computation in complex systems. Markov chain Monte Carlo (MCMC) methods provide enormous scope for realistic statistical modelling and have attracted much attention from disciplinary scientists as well as research statisticians. Many scientific problems are not, however, naturally posed in a form accessible to evaluation via MCMC, and many are inaccessible to such methods in any practical sense. For example, for real-time, fast data processing problems that inherently involve sequential analysis, MCMC methods are often not obviously appropriate at all due to their inherent "batch" nature. The recent emergence of sequential MC concepts and techniques has led to a swift uptake of basic forms of sequential methods across several areas, including communications engineering and signal processing, robotics, computer vision and financial time series. This adoption by practitioners reflects the need for new methods and the early successes and attractivenes of SMC methods. In such, probability distributions of interest are approximated by large clouds of random samples that evolve as data is processed using a combination of sequential importance sampling and resampling ideas. Variants of particle filtering, sequential importance sampling, sequential and adaptive Metropolis MC and stochastic search, and others have emerged and are becoming popular for solving variants of "filtering" problems; i.e. sequentially revising sequences of probability distributions for complex state-space models. Useful entree material and examples SMC methods can be found at the following SMC preprint site.

Many problems and existing simulation methods can be formulated for analysis via SMC: sequential and batch Bayesian inference, computation of p-values, inference in contingency tables, rare event probabilities, optimization, counting the number of objects with a certain property for combinatorial structures, computation of eigenvalues and eigenmeasures of positive operators, PDE's admitting a Feynman-Kac representation and so on. This research area is poised to explode, as witnessed by this major growth in adoption of the methods.

The SAMSI SMC program:

• Addressed methodological and theoretical problems of SMC methods, including synthesis of concepts underlying variants of SMC that have proven apparently successful across multiple fields, and the development of methodological and theoretical advances.
• Developed the methodological research -- with broad opportunities for test-bed examples, methods evaluation and refinement of generic approaches -- in the contexts of a number of important applied problems (e.g. data assimilation, inference for large state spaces, finance, tracking, continuous time models).

The program was an opportunity for exchange between communities; it helped to shape the future of stochastic computation and sequential methods, involved  statisticians, computer scientists and engineers as core participants as well as others working collaboratively in a range of applied fields.

Research Foci

Continuous time modeling and parameter estimation

Modeling and parameter estimation for continuous time stochastic processes might include exact simulation methods for inference in partially observed diffusions, jump diffusions and Levy processes. Both batch-based and on-line strategies will be studied, as will both parameter estimation and state estimation. This group had strong links to the Decision Theory and Finance Group, the Tracking Group and the Theory group, as continuous time models underly many of these applications, as well as applications in other areas including emerging studies in systems biology.

Tracking and large-scale dynamical systems

There is much interest in tracking and inference for large groups of objects, with applications in medical imaging, dynamic object tracking in robotic control in industrial, commercial and military areas, and tracking in media applications. Particular focus areas might be drawn from representations of many interacting objects using random fields, graphical models, and automated inference about group structures, types of interaction, intentionalities, etc.. Methodology of interest utilises combinations of techniques such as particle filtering, MCMC, SMC samplers. It also includes dynamic point process methods such as the Probability Hypothesis Density Filtering which is an example of the interest in cross-over research between core statistical methodology and applied probability.

Decision making, econometrics and finance

SMC methods are under-explored and appear to have a gret deal of potential in problems of numerical solution of decision problems under uncertainty. Some areas might include: (i) applications in policy-oriented macro-economic modelling; and (ii) state and parameter estimation leading into prediction financial time series models, together with numerical approaches to the coupled portfolio decision problems.

Theory

Although many theoretical results have already been established for specific classes of SMC methods, these results are often unsatisfactory -- relying on practically unrealistic assumptions -- for the kinds of complex stochastic models that are being more and more used in emerging applications. There is a need to begin to make the link more forcefully between theoretical developments and more relevant practical models.

Population Monte Carlo

MCMC can easily get stuck for high dimensional multimodal distributions. This has led, in part, to the development of adaptive and population Monte Carlo algorithms, which can provide promising alternatives for these problems. Some of these methods are inherently SMC methods, and there is interest in developing new adaptive methods to sample from high dimensional distributions.

Description of Activities

Workshops: The Opening Workshop was held during September 7-10, 2008 at SAMSI. This workshop aimed to engage as large a part of the mathematics, scientific and engineering communities as possible, with representative sessions from all of the main program topics.

Smaller, informal mid-program workshops summarised progress and brought in additional visitors, and the Closing Workshop at the end of the program disseminated program results and charted a path for future research in the area.

Working Groups: Working groups met throughout the program to pursue particular research topics identified in the kickoff workshop (or subsequently chosen by the working group participants). The working groups consisted of SAMSI visitors, postdoctoral fellows, graduate students, and local faculty and scientists.

Working Groups

• Big Data and Distributed Computing
• Continuous Time Modeling
• Model Assessment
• Population Monte Carlo
• Particle Learning
• Theory
• Tracking

Course: Sequential Monte Carlo Methods