Open Collections

Entangled Monte Carlo

University of British Columbia

A recurrent problem in statistics is that of computing an expectation involving intractable integration. In particular, this problem arises in Bayesian statistics when computing an expectation with respect to a posterior distribution known only up to a normalizing constant. A common solution is to use Monte Carlo simulation to estimate the target expectation. Two of the most commonly adopted simulation methods are Markov Chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC) methods. However, these methods fail to scale up with the size of the inference problem. For MCMC, the problem takes the form of simulations that must be ran for a long time in order to obtain an accurate inference. For SMC, one may not be able to store enough particles to exhaustively explore the state space. We propose a novel scalable parallelization of Monte Carlo simulation, Entangled Monte Carlo simulation, that can scale up with the size of the inference problem. Instead of transmitting particles over the network, our proposed algorithm reconstructs the particles from the particle genealogy using the notion of stochastic maps borrowed from perfect simulation literature. We propose bounds on the expected time for particles to coalesce based on the coalescent model. Our empirical results also demonstrate the efficacy of our method on datasets from the field of phylogenetics.

Text

2013-08-29

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/44953

Statistics

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/