Seminars (MCM)

The particle Gibbs sampler is a systematic way of using a particle filter within Markov chain Monte Carlo (MCMC). This results in an off-the-shelf Markov kernel on the space of state trajectories, which can be used to simulate from the full joint smoothing distribution for a state space model in an MCMC scheme. We show that the PG Markov kernel is uniformly ergodic under rather general assumptions, that we will carefully review and discuss. In particular, we provide an explicit rate of convergence which reveals that: (i) for fixed number of data points, the convergence rate can be made arbitrarily good by increasing the number of particles, and (ii) under general mixing assumptions, the convergence rate can be kept constant by increasing the number of particles superlinearly with the number of observations. We illustrate the applicability of our result by studying in detail two common state space models with non-compact state spaces.

Keywords: Bayesian inference; Estimated likelihood; Metropolis-Hastings; Particle filtering.

Many physical systems can be successfully modelled by a deterministic dynamical system for which, however, the initial conditions may contain uncertainty. In the presence of chaos this can lead to undesirable growth of uncertainty over time. However, when noisy observations of the system are present these may be used to compensate for the uncertainty in the initial state. This scenario is naturally modelled by viewing the initial state as given by a probability distribution, and to then condition this probability distribution on the noisy observations, thereby reducing uncertainty. Filtering refers to the situation where the conditional distribution on the system state is updated sequentially, at the time of each observation. In this talk we investigate the asymptotic behaviour of this filtering distribution for large time. We focus on a class of dissipative systems that includes the Lorenz '63 and '96 models, and the Navier-Stokes equations on a 2D torus. We first st udy the behaviour of a variant on the 3DVAR filter, creating a unified analysis which subsumes the existing work in [1,2] which, itself, builds on [3]. The optimality property of the true filtering distribution is then used, when combined with this modified 3DVAR analysis, to provide general conditions on the observation of our wide class of chaotic dissipative systems which ensure that the filtering distributions concentrate around the true state of the underlying system in the long-time asymptotic regime.

[1] C.E.A. Brett, K.F. Lam, K.J.H. Law, D.S. McCormick, M.R. Scott and A.M. Stuart, ``Accuracy and stability of filters for dissipative PDEs.'' Physica D 245(2013).

[2] K.J.H. Law, A. Shukla and A.M. Stuart, ``Analysis of the 3DVAR Filter for the Partially Observed Lorenz '63 Model.'' Discrete and Continuous Dynamical Systems A, 34(2014).

[3] K. Hayden, E. Olsen and E.S. Titi, ``Discrete data assimilation in the Lorenz and 2D Navier-Stokes equations.'' Physica D 240(2011).

The potential benefits of parallel or distributed implementation motivates study of the interaction structure of particle filters. Can we do away with resampling, or at least re-structure it in such a way as to be more naturally suited to non-serial implementation? What role does resampling really play in endowing these algorithms with attractive properties? This talk will introduce some new algorithms in this context and discuss their theoretical properties.

Related Links: http://arxiv.org/abs/1309.2918

The computing time for Markov Chain Monte Carlo (MCMC) algorithms can be prohibitively large for datasets with many observations, especially when the data density for each observation is costly to evaluate. We propose a framework based on a Pseudo-marginal MCMC where the likelihood function is unbiasedly estimated from a random subset of the data, resulting in substantially fewer density evaluations. The subsets are selected using efficient sampling schemes, such as Probability Proportional-to-Size (PPS) sampling where the inclusion probability of an observation is proportional to an approximation of its contribution to the likelihood function. We illustrate the method on a large dataset of Swedish firms containing half a million observations.

For driving time prediction the relevant data are Global Positioning System (GPS) recordings from historical lights-and-sirens ambulance trips. Challenges include the typically large size of the road network and dataset (70,000 network links and 160,000 historical trips for Toronto); the lack of trips in the historical data that follow precisely the route of interest; and the strong temporal, weather, and other effects on driving time. We introduce a model of the travel time at the trip level, as well as a computationally efficient procedure for two-stage estimation in that model. For space-time forecasting of demand we develop integer time-series factor models and spatio-temporal mixture models, which capture the complex weekly and daily patterns in demand as well as changes in the spatial demand density over time.

Related Links: •http://people.orie.cornell.edu/woodard/publications.html - Links to Woodard's publications on ambulance fleet management

This paper deals with a parametrized family of partially-observed bivariate Markov chains. We establish that the limit of the normalized log-likelihood is maximized when the parameter belongs to the equivalence class of the true parameter, which is a key feature for obtaining consistency of the Maximum Likelihood Estimators in well-specified models. A novel aspect of this work is that geometric ergodicity of the Markov chain associated to the complete data, or exponential separation on measures are no more needed provided that the invariant distribution is assumed to be unique, regardless its rate of convergence to the equilibrium. The result is presented in a general framework including both fully dominated or partially dominated models as Hidden Markov models or Observation-Driven times series of counts.

We consider Bayesian inference for parameters governing nonlinear multivariate diffusion processes using data that may be incomplete, subject to measurement error and observed sparsely in time. We adopt a high frequency imputation approach to inference, by introducing additional time points between observations and working with the Euler-Maruyama approximation over the induced discretisation. We assume that interest lies in the marginal parameter posterior and sample this target via particle MCMC. A vanilla implementation based on a bootstrap filter is eschewed in favour of an auxiliary particle filter where the latent path is extended by sampling a discretisation of a conditioned diffusion. This conditioned diffusion should be carefully constructed to allow for nonlinear dynamics between observations.

Existing algorithms for approximate Bayesian computation (ABC) assume that it is feasible to simulate pseudo-data from the model at each iteration. However, the computational cost of these simulations can be prohibitive for high dimensional data. An important example is the Potts model, which is commonly used in image analysis. The dimension of the state vector in this model is equal to the size of the data, which can be millions of pixels. We introduce a preparatory computation step before model fitting to improve the scalability of ABC. The output of this precomputation can be reused across multiple datasets. We illustrate this method by estimating the smoothing parameter for satellite images, demonstrating that the pre-computation step can sufficiently reduce the average runtime required for model fitting to enable analysis in realistic, if not yet real, time.

Markov chain Monte Carlo is an inherently serial algorithm. Although the likelihood calculations for individual steps can sometimes be parallelized, the serial evolution of the process is widely viewed as incompatible with parallization, offering no speedup for sampling algorithms which require large numbers of iterations to converge to equilibrium. We provide a methodology for parallelizing Markov chain Monte Carlo across large numbers of independent, asynchronous processors. The method is originally motivated by sampling multimodal target distributions, where we see an exponential speed-up in running time. However we show that the approach is general purpose and applicable to all Markov chain Monte Carlo simulations, and demonstrate speed-ups proportional to the number of available processors on slowly mixing chains with unimodal target distributions. The approach is simple and easy to implement, and suggests additional directions for further research.

We link optimal filtering for hiddenMarkov models to the notion of duality forMarkov processes.We show that when the signal is dual to a process that has two components, one deterministic and one a pure death process, and with respect to functions that define changes of measure conjugate to the emission density, the filtering distributions evolve in the family of finite mixtures of such measures and the filter can be computed at a cost that is polynomial in the number of observations. Special cases of our framework include the Kalman filter, and computable filters for the Cox–Ingersoll–Ross process and the one-dimensional Wright– Fisher process, which have been investigated before in the literature. The dual we obtain for the Cox– Ingersoll–Ross process appears to be new in the literature.

Related Links: http://www.isi-web.org/images/bernoulli/BEJ1305-022.pdf - article

We develop a sequential Monte Carlo (SMC) algorithm for inference in general probabilistic graphical model. Via a sequential decomposition of the PGM we find a sequence of auxiliary distributions defined on a monotonically increasing sequence of probability spaces. By targeting these auxiliary distributions using purpose built SMC samplers we are able to approximate the full joint distribution defined by the graphical model. Our SMC sampler also provides an unbiased estimate of the partition function (normalization constant) and we show how it can be used within a particle Markov chain Monte Carlo framework. This allows for better approximations of the marginals and for unknown parameters to be estimated. The proposed inference algorithms can deal with an arbitrary graph structure and the domain of the random variables in the graph can be discrete or continuous.

Related Links: http://arxiv.org/pdf/1402.0330v1.pdf - Associated paper http://user.it.uu.se/~thosc112/index.html - Speaker (Thomas Schön) home page

We fill this gap and conduct a rigorous analysis of a new Gaussian mixture approximation to the solution of the filtering problem. In particular, we construct the corresponding approximating algorithm, deduce the L2-convergence rate and prove a central limit type theorem for the approximating system. In addition, we show a numerical example to illustrate some features of this algorithm. This is joint work with Dan Crisan (Imperial College London).

References: [1] D. Crisan, K. Li, “A central limit type theorem for Gaussian mixture approximations to the nonlinear filtering problem”, ArXiv1401:6592, (2014).

[2] D. Crisan, K. Li, “Generalised particle filters with Gaussian mixtures”, accepted by Stochastic Processes and their Applications, ArXiv1306:0255, (2013).

[3] D. Crisan, K. Li, “Generalised particle filters with Gaussian measures”, Proceedings of 19th European Signal Processing Conference, Barcelona, Spain, pp. 659-663, (2011).

Recursive maximum likelihood algorithm for state-space models (i.e., for continuous state hidden Markov models) is an iterative estimation method based on particle filter and stochastic gradient search. In this talk, resent results on its asymptotic properties are presented. These results are focused on the asymptotic bias and the asymptotic variance. They also involve diffusion approximation, almost-sure and mean-square convergence of the recursive maximum likelihood algorithm. Some auxiliary (yet, rather interesting) results on the asymptotic properties of the particle filter and the log-likelihood are presented in the talk, too.