Divide-and-conquer with Sequential Monte Carlo. arXiv preprint

We develop a Sequential Monte Carlo (SMC) procedure for inference in proba-bilistic graphical models using the divide-and-conquer methodology. The method is based on an auxiliary tree-structured decomposition of the model of interest turning the overall inferential task into a collection of recursively solved sub-problems. Unlike a standard SMC sampler, the proposed method employs multi-ple independent populations of weighted particles, which are resampled, merged, and propagated as the method progresses. We illustrate empirically that this ap-proach can outperform standard methods in estimation accuracy. It also opens up novel parallel implementation options and the possibility of concentrating the computational effort on the most challenging sub-problems. The proposed method is applicable to a broad class of probabilistic graphical models. We demonstrate its performance on a Markov random field and on a hierarchical Bayesian model.