A fully-parallel alternative to MCMC

该博士学位旨在解决与位于达累斯伯里的IBM研究实验室相关的应用程序相关的复杂问题。具体地说，目的是开发技术来实现最先进的贝叶斯技术，以充分利用现代和下一代多核体系结构和系统(如多核CPU、GPU、至强PHI和超级计算集群)的计算能力。在贝叶斯推理中，马尔可夫链蒙特卡罗(MCMC)通常用于估计后验分布。利用MCMC可以刻画分布特征，估计不能直接计算的后验分布特征，如随机样本、后验均值等。由于MCMC具有较高的计算代价，许多研究人员将注意力集中在改进MCMC上。以前的研究涉及到局部梯度信息的使用和算法的进步。改进的MCMC可以有效地解决大多数可以用统计模型进行数据推理的问题。然而，MCMC的一个缺点是它不能利用并行处理体系结构，限制了它为下一代问题提供解决方案的能力。这发生在MCMC通过本质上使用单个马尔可夫链的演化来传递不确定性的时候。序贯蒙特卡罗(SMC)采样器是MCMC的一种替代方法，用于动态模型的在线推理。这两种技术都可以用来解决相同的问题，不同的是，SMC采样器通过使用一组样本的多样性来减少不确定性。在SMC采样器中，每个样品都可以独立处理，从而解决了MCMC不能管理并行过程的弱点。尽管如此，在SMC采样器的过程中，需要在特定的时间进行重采样。不可能以可伸缩的方式实现并行重采样步骤。为了做到这一点，在之前的研究中，研究人员将重采样操作重新定义为分而治之的算法。最近的研究表明，通过考虑数据局部性和流水线，并适当使用中间件(如MPI和OpenMP)，可以利用核的数量来加快重采样算法的运行速度。本研究的主要目的是开发一个充分利用多核体系结构的SMC采样器的实现。具体地说，其目的是使用上述实现来解决相关问题，并暗示这些实现可以显著优于MCMC。该研究项目与一个名为“大假设”的大型研究项目密切相关，并将借鉴之前与高性能计算、大数据和贝叶斯统计相关的工作。

This PhD aims to solve complex problems related to applications relevant to the IBM Research laboratory at Daresbury. Specifically, the aim is to develop techniques for implementing state-of-the-art Bayesian techniques in ways that 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).In Bayesian inference, Markov-Chain Monte Carlo (MCMC) is commonly used for estimating the posterior distribution. With MCMC one can characterise the distribution, and estimate features of posterior distributions that cannot be directly calculated, such as random samples, posterior means, etc. Many researchers have focused on improving MCMC, as they have high computational cost. Previous research involves the use of local gradient information and algorithmic advances. The improved MCMC can effectively solve a majority of problems that can be posed as inferences involving data using statistical models. Nevertheless, one drawback of MCMC is that it cannot exploit parallel processing architectures, limiting its ability to provide solutions to next-generation problems. This happens as MCMC conveys uncertainty by essentially using the evolution of a single Markov Chain. Therefore, MCMC is not ideal for sequential design.Sequential Monte Carlo (SMC) samplers is an alternative to MCMC that is designed for online inference in dynamic models. Both of these techniques can be used to solve the same problems, with the difference that SMC samplers reduce uncertainty by using the diversity of a set of samples. In SMC samplers, each sample can be processed independently, thus solving MCMC's weakness of not managing parallel processes. Nonetheless, in the process of SMC samplers, it is necessary to perform resampling at a particular time. It is impossible to implement parallel resampling steps in a scalable fashion. In order to do so, in previous studies, researchers have redefined the resampling operation as a divide-and-conquer algorithm. Recent studies indicate that it is possible to leverage the number of cores in order to have faster operation of the resampling algorithm, by taking into consideration data locality and pipelining and by making appropriate use of middleware (e.g., MPI and OpenMP).The main scope of this research is to develop implementations of an SMC sampler that fully exploit multicore architectures. Specifically, the aim is to use the aforementioned implementations to solve relevant problems, with the hint that these implementations can dramatically outperform MCMC.This research project is linked closely to a large research project, called "Big Hypotheses", and will pull on previous work related to high-performance computing, Big Data and Bayesian statistics.