Divide-and-Conquer with Sequential Monte Carlo

Abstract

We propose a novel class of Sequential Monte Carlo (SMC) algorithms, appropriate for inference in probabilistic graphical models. This class of algorithms adopts a divide-and-conquer approach based upon an auxiliary tree-structured decomposition of the model of interest, turning the overall inferential task into a collection of recursively solved sub-problems. The proposed method is applicable to a broad class of probabilistic graphical models, including models with loops. Unlike a standard SMC sampler, the proposed Divide-and-Conquer SMC employs multiple independent populations of weighted particles, which are resampled, merged, and propagated as the method progresses. We illustrate empirically that this approach can outperform standard methods in terms of the accuracy of the posterior expectation and marginal likelihood approximations. Divide-and-Conquer SMC also opens up novel parallel implementation options and the possibility of concentrating the computational effort on the most challenging sub-problems. We demonstrate its performance on a Markov random field and on a hierarchical logistic regression problem.

References in corpus (6)

• On adaptive resampling strategies for sequential Monte Carlo methods
• A General Algorithm for Approximate Inference and its Application to Hybrid Bayes Nets
• Bayesian Agglomerative Clustering with Coalescents
• Sequential Monte Carlo for Graphical Models
• Expectation Particle Belief Propagation
• Forest resampling for distributed sequential Monte Carlo

Cited by in corpus (8)

• Inference Networks for Sequential Monte Carlo in Graphical Models
• Probabilistic learning of nonlinear dynamical systems using sequential Monte Carlo
• A Survey of Bayesian Statistical Approaches for Big Data
• Bayesian modelling and quantification of Raman spectroscopy
• On embedded hidden Markov models and particle Markov chain Monte Carlo methods
• The divide-and-conquer sequential Monte Carlo algorithm: theoretical properties and limit theorems
• Combining chains of Bayesian models with Markov melding
• Tree-based Particle Smoothing Algorithms in a Hidden Markov Model