Markov chain Monte Carlo (MCMC) is a popular and successful general-purpose tool for Bayesian inference. However, MCMC cannot be practically applied to large data sets because of the prohibitive cost of evaluating every likelihood term at every iteration. Here we present Firefly Monte Carlo (FlyMC) an auxiliary variable MCMC algorithm that only queries the likelihoods of a potentially small subset of the data at each iteration yet simulates from the exact posterior distribution, in contrast to recent proposals that are approximate even in the asymptotic limit. FlyMC is compatible with a wide variety of modern MCMC algorithms, and only requires a lower bound on the per-datum likelihood factors. In experiments, we find that FlyMC generates samples from the posterior more than an order of magnitude faster than regular MCMC, opening up MCMC methods to larger datasets than were previously considered feasible. The Bayesian approach to probabilistic modeling is appealing for a several reasons: the generative framework allows one to separate out modeling assumptions from inference procedures, outputs include estimates of uncertainty that can be used for decision making and prediction, and it provides clear ways to perform model selection and complexity control. Unfortunately, the fully-Bayesian approach to modeling is often very computationally challenging. It is unusual for non-trivial models of real data to have closed-form posterior distributions. Instead, one uses approximate inference via Monte Carlo, variational approximations, Laplace approximations, or other tools. One of the persistent challenges to Bayesian computation is that coherent procedures for inference appear to require examination of all of the data in order to evaluate a new hypothesis regarding parameters or latent variables. For example, when performing Metropolis-Hastings (MH), it is necessary to evaluate the target posterior density for each proposed parameter update, and this posterior will usually contain a factor for each datum. Similarly, typical variational Bayesian procedures need to build local approximations for each of the data in order to update the approximation to any global parameters. In both cases, it may be necessary to perform these data-intensive computations many times as part of an iterative procedure. Recent methods have been proposed to partially overcome these difficulties. Stochastic and online variational approximation procedures (Hoffman et al., 2010 (Hoffman et al., , 2013 can use subsets of the data to make approximations to global parameters. As these procedures are optimizations, it is possible to build on convergence results from the stochastic optimization literature and achieve guarantees on the resulting approximation. For Markov chain Monte Carlo, the situation is somewhat murkier. Recent work has considered how subsets of data might be used to approximate the ideal transition operator for Metropolis-Hastings (MH) and related algorithms (Welling and Teh, 2011) . Korattikara et al. (2014) and Bardenet et al. (2014) have recently shown that such approximate MH moves can lead to stationary distributions which are approximate but that have bounded error, albeit under strong conditions of rapid mixing. In this paper, we present a Markov chain Monte Carlo algorithm, Firefly Monte Carlo (FlyMC), that is in line with these latter efforts to exploit subsets of data to construct transition operators.
REF present an auxiliary variable MCMC algorithm that queries the likelihoods of a small subset but achieves exact posterior distribution.
Firefly Monte Carlo: Exact MCMC with Subsets of Data
ArXiv
ArXiv
Computer Science Mathematics