A Real-Time Fully-Parallel Alternative to MCMC

本文旨在研究序列蒙特卡罗(SMC)采样器作为马尔可夫链蒙特卡罗(MCMC)采样器在贝叶斯推理中的替代方法。MCMC是一种数值贝叶斯方法，允许高保真物理模型与数据相结合，在存在明显不确定性的情况下进行推断。对MCMC的改进历来侧重于算法的进步，例如，涉及使用局部梯度信息，以及从容易参考的问题逐渐转移到感兴趣的问题。特别是有了这些改进，MCMC是对大量问题的有效解决方案，这些问题可以被认为是涉及使用统计模型的数据的推断。在任何一个问题的背景下，定制的优化都可以用来开发可用的(并行)计算资源。然而，由于MCMC基本上使用单个马尔可夫链的演化来传达不确定性，因此这种优化必然是特定于问题的。因此，开发完全利用并行处理体系结构的通用MCMC实现的范围很小。因此，MCMC为下一代问题提供解决方案的能力是有限的。SMC采样器可以解决与MCMC相同的问题。与MCMC不同，SMC采样器使用样本总体的多样性来传递不确定性。对于SMC采样器的大部分操作，每个样品都是独立处理的。这使得SMC采样器的大部分并行化变得微不足道。但是，在SMC采样器中的特定点，需要执行“重采样”步骤。这一重采样步骤的教科书实现不可能以可扩展的方式并行化。然而，以前的研究已经证明，使用分而治之的策略来实现重采样操作是可能的。这个项目有两个关键目标：将SMC采样器应用于现实世界的问题，以及探索SMC采样器相对于MCMC采样器的理论差异。现实世界的问题将存在于国防和安全领域，在这种情况下，将运行效率与准确的估计结合起来是非常重要的。应用于这些问题的SMC采样器将充分利用现代和下一代多核体系结构和系统(如多核CPU、GPU、至强PHI和超级计算集群)的计算能力。理论研究的目标是进一步确定SMC采样器的独特数学特性，使其性能比MCMC采样器高出更多。这些研究将不限于，但将包括观察样本相关性，优化的L核，时间不可逆的建议，非马尔可夫建议，以及改变目标。为了实施这个项目，学生需要对数学思想进行推理，用软件实现算法，并运行模拟来评估算法的性能。这个项目属于EPSRC的数学科学主题及其统计和应用概率研究领域。

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.