Fundamentals and Recent Developments in Approximate Bayesian Computation

Jarno Lintusaari, Michael U. Gutmann, Ritabrata Dutta, Samuel Kaski, Jukka CoranderSystematic 2016 · DOI

TL;DR

This paper provides a comprehensive overview of Approximate Bayesian Computation (ABC), a powerful set of techniques for performing Bayesian inference on complex models where direct likelihood calculation is impossible. It explains the fundamental principles of ABC, reviews classical algorithms, and highlights recent advancements that improve both computational efficiency and statistical accuracy, making it a valuable tool for fields like phylogenetics and evolutionary biology.

What Problem Does This Paper Address?

Many scientific models, particularly in fields like phylogenetics and evolutionary biology, are incredibly detailed and realistic but are also "simulator-based." This means they can generate data for given parameter values, but it's impossible to analytically calculate the probability of observing specific data given those parameters (the likelihood function). This "likelihood-free" problem makes traditional Bayesian inference, which relies heavily on the likelihood, intractable. The paper addresses this by introducing and reviewing Approximate Bayesian Computation (ABC), a family of methods that bypasses direct likelihood calculation by comparing simulated data to observed data.

Methods

The paper systematically introduces ABC methods, starting with the foundational concepts:

  • Simulator-Based Models: These are models that map parameters and random variables to data. They are often implemented as computer programs.
  • The Core Idea of ABC: Instead of calculating $P(\text{data}|\text{parameters})$, ABC algorithms work by simulating data from the model for various parameter values and comparing these simulated datasets to the observed data.
  • Rejection Sampling ABC (Algorithm 1): This is the simplest form. It involves drawing parameter values from the prior, simulating data, and accepting the parameter value only if the simulated data exactly matches the observed data. This is often computationally infeasible due to the low probability of exact matches.
  • Rejection ABC with a Distance Threshold (Algorithm 2): To overcome the exact match problem, a distance function $d(\text{simulated data}, \text{observed data})$ is introduced. Parameter values are accepted if the distance is below a threshold $\epsilon$. This approximates the true posterior but introduces bias.
  • Summary Statistics: To make distance calculations more efficient and robust, data is often reduced to summary statistics. The choice of these statistics is crucial for the quality of inference.
  • Markov Chain Monte Carlo (MCMC) ABC: This approach adapts MCMC algorithms to the ABC framework by incorporating the distance criterion into the acceptance probability. It aims to improve proposal distributions over simple prior sampling.
  • Sequential Monte Carlo (SMC) ABC: This method iteratively refines proposal distributions and shrinks the distance threshold $\epsilon$ over time, aiming to move from a prior-like distribution towards the posterior.
  • Post-Sampling Correction Methods: These methods adjust samples obtained from ABC algorithms (often with a non-zero $\epsilon$) to better approximate the posterior distribution, typically by modeling the relationship between parameters and summary statistics or distances.
  • Bayesian Optimization for Likelihood-Free Inference (BOLFI): A more recent development that learns a probabilistic model of the distance function itself, allowing for efficient approximation of the likelihood and posterior without requiring further simulator runs once the model is learned.

Datasets

The paper uses a tuberculosis transmission model as a running example throughout the text to illustrate the concepts and algorithms. Synthetic data is generated from this model for evaluation purposes. No specific real-world datasets are analyzed in detail, but the methods are presented as applicable to various fields, including phylogenetics and evolutionary biology.

Key Insights and Ideas

  • The "Curse of Dimensionality" in ABC: Using too many summary statistics or a very small distance threshold $\epsilon$ can lead to extremely high computational costs due to low acceptance rates.
  • The Bias-Variance Trade-off: A fundamental challenge in ABC is balancing the bias introduced by using a non-zero distance threshold $\epsilon$ (which makes computation faster) against the Monte Carlo error (which decreases with more simulations).
  • The Importance of Summary Statistics: The choice of summary statistics is critical. They need to be informative about the parameters of interest. Poorly chosen statistics can lead to biased or inaccurate posteriors.
  • The "Locality" of Inference: Informative summary statistics can be parameter-dependent, meaning what's informative in one parameter region might not be in another. This suggests adaptive or locally-focused approaches are beneficial.
  • ABC as a General Framework: ABC is not a single algorithm but a family of methods that can be adapted to various problems, offering a principled way to handle uncertainty when likelihoods are intractable.

Key Results

  • The paper demonstrates that rejection ABC with a distance threshold can provide reasonable approximations of posteriors, but the accuracy depends heavily on the choice of $\epsilon$ and summary statistics.
  • MCMC ABC and SMC ABC can improve computational efficiency by generating more informative proposals than simple prior sampling, reducing rejection rates.
  • Post-sampling correction methods and BOLFI show promise in reducing bias and improving the accuracy of ABC approximations, often with significant computational speedups compared to basic ABC. For instance, BOLFI is shown to increase computational efficiency by orders of magnitude.
  • The paper illustrates how different summary statistics can lead to substantially different inferred posteriors, highlighting the need for careful selection.

Limitations and Future Work

  • Computational Cost: Despite advancements, ABC methods can still be computationally intensive, especially for high-dimensional parameter spaces or complex simulators.
  • Choice of Distance and Threshold: Selecting appropriate distance functions and thresholds remains a key challenge, often requiring empirical tuning and trade-offs.
  • High-Dimensional Inference: The paper acknowledges that applying ABC to high-dimensional inference problems is an important area of ongoing research.
  • Model Selection: While the paper focuses on parameter inference, ABC is also applicable to model selection, a topic briefly mentioned.
  • Validation: The paper emphasizes the importance of rigorous validation of ABC inferences, suggesting methods like checking posterior coverage and comparing with known parameter values for synthetic data.

The paper concludes by highlighting the active research field of ABC and its growing applicability to important biological questions, with ongoing work focusing on improving statistical and computational efficiency.

Summary updated

Abstract

Bayesian inference plays an important role in phylogenetics, evolutionary biology, and in many other branches of science. It provides a principled framework for dealing with uncertainty and quantifying how it changes in the light of new evidence. For many complex models and inference problems, however, only approximate quantitative answers are obtainable. Approximate Bayesian computation (ABC) refers to a family of algorithms for approximate inference that makes a minimal set of assumptions by only requiring that sampling from a model is possible. We explain here the fundamentals of ABC, review the classical algorithms, and highlight recent developments. [ABC; approximate Bayesian computation; Bayesian inference; likelihood-free inference; phylogenetics; simulator-based models; stochastic simulation models; tree-based models.]
BibTeX
@inproceedings{lintusaari2016fundamentals,
  author = {Jarno Lintusaari and Michael U. Gutmann and Ritabrata Dutta and Samuel Kaski and Jukka Corander},
  title = {{Fundamentals and Recent Developments in Approximate Bayesian Computation}},
  booktitle = {Systematic},
  year = {2016},
  doi = {10.1093/sysbio/syw077},
}
Figure