Sequential Monte Carlo without likelihoods

Scott A. Sisson, Yanan Fan, Mark M. TanakaProceedings of the National Academy of Sciences 2007 · DOI

TL;DR

This paper introduces novel Sequential Monte Carlo (SMC) algorithms, ABC-SMC and ABC-PRC, for Bayesian inference when the likelihood function is intractable. These methods offer significant improvements in efficiency and accuracy over existing Markov Chain Monte Carlo (MCMC) approaches, particularly in exploring complex posterior distributions and avoiding "getting stuck" in low-density regions.

What Problem Does This Paper Address?

Bayesian statistics is a powerful framework for statistical inference, but it often relies on evaluating the likelihood function, which can be analytically intractable or computationally prohibitive in many real-world scenarios. This is particularly common in fields like genetics and epidemiology, where complex models are used to describe observed data. Existing methods for handling intractable likelihoods, such as Approximate Bayesian Computation (ABC) combined with MCMC, have made significant progress but suffer from a critical inefficiency: poor mixing of the Markov chain. This means the sampler can spend a disproportionate amount of time exploring regions of low posterior probability, requiring an impractically large number of iterations to obtain a representative sample. This paper aims to address this inefficiency by developing more effective sampling strategies.

Methods

The paper proposes two novel algorithms based on Sequential Monte Carlo (SMC):

  • ABC-SMC: This algorithm treats the sampling problem as a sequence of distributions, starting from a simple initial distribution and progressively transitioning to the target posterior distribution. At each step, particles (representing parameter values) are re-weighted based on how well they fit the current target distribution. A resampling step then favors particles with higher weights, effectively eliminating those that poorly represent the distribution. A standard MCMC step is also incorporated to maintain particle diversity.
  • ABC-PRC (Partial Rejection Control): This is a simplified version of ABC-SMC that aims to reduce implementation complexity. It largely ignores particle weights and uses a more direct approach to particle selection and MCMC steps, effectively removing particles with very low weights. This algorithm is designed to be more "black-box" and easier to use.

Both algorithms are designed to overcome the "stickiness" of MCMC methods by using a population-based approach and by progressively refining the sample, ensuring better exploration of the entire posterior distribution, including its tails.

Datasets

The paper uses a "toy example" involving a mixture of two Normal densities to illustrate the algorithms' behavior. For a real-world application, they re-analyze data from a study of tuberculosis isolates from San Francisco, originally collected in the early 1990s. This dataset involves 473 isolates genotyped using the IS6110 marker, grouped into 326 distinct genotypes. The analysis uses summary statistics derived from this data, specifically the number of distinct genotypes and gene diversity.

Key Insights and Ideas

  • Population-based sampling is key: Moving away from single-chain MCMC to a population of particles (SMC) allows for more robust exploration of complex posteriors.
  • Progressive refinement is efficient: Gradually transitioning from a simple distribution to the target posterior, with resampling and re-weighting, is more efficient than trying to sample directly from a complex target.
  • Avoiding "stuck" states: The SMC approach inherently avoids getting stuck in low-probability regions because particles that perform poorly are either down-weighted or eliminated, and the population as a whole continues to move towards the target.
  • ABC-PRC simplifies implementation: The ABC-PRC algorithm offers a significant reduction in implementation complexity by removing the need for explicit particle weight management and complex schedule specifications, making it more accessible to practitioners.
  • Improved tail exploration: The proposed methods demonstrate a superior ability to accurately represent the tails of the posterior distribution, an area where traditional ABC-MCMC struggles.

Key Results

  • Efficiency gains: Both ABC-SMC and ABC-PRC significantly outperform the original ABC-MCMC algorithm in terms of computational efficiency. For instance, in the tuberculosis analysis, ABC-SMC and ABC-PRC were over 20 times more efficient than MCMC in generating uncorrelated samples.
  • Improved posterior representation: The algorithms produce posterior densities that are indistinguishable from those obtained by MCMC but achieve this with far fewer computational resources, particularly in accurately capturing the tails of the distributions.
  • ABC-PRC's practical advantage: While ABC-PRC incurs a slight increase in computation for particle selection compared to ABC-SMC (with a simple schedule), it guarantees that all particles reach the target density, avoiding the risk of particle depletion.

Limitations and Future Work

  • Specification of schedules: The ABC-SMC algorithm requires specification of sequences for tolerances ($\epsilon_t$) and the number of datasets to generate at each step ($B_t$). While $B_t=1$ is a default, it doesn't guarantee sufficient distinct particles. Finding optimal schedules can be challenging, and dynamic, run-time determination of these schedules could increase computation.
  • Computational cost of ABC-PRC: While ABC-PRC simplifies implementation, it does have a slightly higher computational cost for particle selection compared to ABC-SMC with $B_t=1$.
  • Future work: The authors suggest that further research could focus on dynamic determination of schedules for ABC-SMC to avoid prior specification. The paper also highlights the potential for parallelization of these SMC-based algorithms, which could lead to even greater computational savings.

Summary updated

Abstract

Recent new methods in Bayesian simulation have provided ways of evaluating posterior distributions in the presence of analytically or computationally intractable likelihood functions. Despite representing a substantial methodological advance, existing methods based on rejection sampling or Markov chain Monte Carlo can be highly inefficient and accordingly require far more iterations than may be practical to implement. Here we propose a sequential Monte Carlo sampler that convincingly overcomes these inefficiencies. We demonstrate its implementation through an epidemiological study of the transmission rate of tuberculosis.
BibTeX
@inproceedings{sisson2007sequential,
  author = {Scott A. Sisson and Yanan Fan and Mark M. Tanaka},
  title = {{Sequential Monte Carlo without likelihoods}},
  booktitle = {Proceedings of the National Academy of Sciences},
  year = {2007},
  doi = {10.1073/pnas.0607208104},
}
Figure