A Real-Time Fully-Parallel Alternative to MCMC

Lead Research Organisation: University of Liverpool
Department Name: Electrical Engineering and Electronics

Abstract

This PhD aims to investigate Sequential Monte Carlo (SMC) samplers as an alternative to Markov chain Monte Carlo (MCMC) in the context of Bayesian inference.

MCMC is a numerical Bayesian method that allows high-fidelity physical models to be combined with data to make inferences in the presence of pronounced uncertainty. Improvements to MCMC have historically focused on algorithmic advances, involving, for example, the use of local gradient information and of gradually migrating from an easy reference problem to the problem of interest. Particularly with these improvements, MCMC is an effective solution to the vast number of problems that can be posed as inferences involving data using statistical models. In the context of any one problem, bespoke optimisation can be used to exploit the available (parallel) computational resources. However, because MCMC fundamentally uses the evolution of a single Markov- Chain to convey uncertainty, such optimisation is necessarily problem-specific. There is therefore little scope to develop a generic MCMC implementation that fully exploits parallel processing architectures. As a result, the ability of MCMC to provide solutions to next-generation problems is limited.

SMC samplers can solve the same problems as MCMC. In contrast to MCMC, SMC samplers use the diversity of a population of samples to convey uncertainty. For the majority of the operation of an SMC sampler, each sample is processed independently. This makes it trivial to parallelise the majority of the SMC sampler. However, at a specific point in the SMC sampler, it becomes necessary to perform a "resampling" step. A text-book implementation of this resampling step is impossible to parallelise in a scalable fashion. However, previous research has demonstrated that it is possible to implement the resampling operation using a divide-and-conquer strategy. In so doing, it becomes possible to parallelise the resampling step.

This project has two key objectives: to apply SMC samplers to real-world problems and to explore the theoretical differences of SMC samplers relative to MCMC. The real-world problems will exist in the sphere of defence and security, in which context combining runtime efficiency with accurate estimation is very important. The SMC samplers applied to these problems will fully exploit the computational power of modern and next generation many-core architectures and systems (such as multicore CPUs, GPUs, Xeon Phis and super-computing clusters). The goal of the theoretical investigations is to identify further unique mathematical characteristics of SMC samplers that allow them to outperform MCMC samplers by an even more significant margin. These investigations will not be limited to but will include looking at sample correlations, optimised l-kernels, time-irreversible proposals, non-markovian proposals, and changing targets.

To carry out the project, the student will need to reason about mathematical ideas, implement algorithms in software, and run simulations to assess algorithmic performance.

This project falls under EPSRC's Mathematical Sciences theme and its Statistics and Applied Probability research area.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/R512011/1 01/10/2017 30/09/2022
1946660 Studentship EP/R512011/1 01/10/2017 30/06/2022 Robert Moore