Adaptive Approximate Bayesian Computation Tolerance Selection

Umberto Simola, Jessica Cisewski-Kehe, Michael U. Gutmann, Jukka CoranderBayesian 2020 · DOI

Abstract

Approximate Bayesian Computation (ABC) methods are increasingly used for inference in situations in which the likelihood function is either computationally costly or intractable to evaluate. Extensions of the basic ABC rejection algorithm have improved the computational efficiency of the procedure and broadened its applicability. The ABC – Population Monte Carlo (ABC-PMC) approach has become a popular choice for approximate sampling from the posterior. ABC-PMC is a sequential sampler with an iteratively decreasing value of the tolerance, which specifies how close the simulated data need to be to the real data for acceptance. We propose a method for adaptively selecting a sequence of tolerances that improves the computational efficiency of the algorithm over other common techniques. In addition we define a stopping rule as a by-product of the adaptation procedure, which assists in automating termination of sampling. The proposed automatic ABC-PMC algorithm can be easily implemented and we present several examples demonstrating its benefits in terms of computational efficiency.

Introduction

In modern Bayesian statistics, researchers frequently encounter "intractable likelihoods"—scenarios where the complexity of the model makes calculating the probability of observed data given parameters computationally prohibitive. Approximate Bayesian Computation (ABC) has emerged as a vital tool for these cases, bypassing the likelihood evaluation by comparing simulated data to observed data. However, standard ABC methods often suffer from low computational efficiency.

The Population Monte Carlo (ABC-PMC) algorithm improves upon basic rejection sampling by using a sequence of decreasing tolerances, $\epsilon_1 > \epsilon_2 > \dots > \epsilon_T$. A critical challenge in ABC-PMC is the selection of this tolerance sequence. If the tolerance decreases too rapidly, the acceptance rate drops, leading to wasted simulations. Conversely, a conservative decrease results in slow convergence. Furthermore, rigid selection rules can cause the algorithm to become trapped in local modes of the parameter space. This paper introduces an adaptive approach, aABC-PMC, to automate tolerance selection and improve inference performance.

Methods

The primary innovation of the aABC-PMC algorithm is its adaptive quantile selection rule. Rather than relying on fixed heuristics, the algorithm monitors the evolution of the posterior distribution to determine how much the tolerance should shrink in each iteration.

Adaptive Quantile Selection

At each iteration $t$, the algorithm estimates the ratio between the current posterior approximation $\hat{\pi}_{\epsilon_t}(\theta)$ and the previous one $\hat{\pi}_{\epsilon_{t-1}}(\theta)$. The supremum of this ratio is defined as: $$\hat{c}_t = \sup_{\theta} \frac{\hat{\pi}_{\epsilon_t}(\theta)}{\hat{\pi}_{\epsilon_{t-1}}(\theta)}$$

The next quantile $q_t$, which determines the threshold for the subsequent tolerance $\epsilon_{t+1}$, is then set as $q_t = 1/\hat{c}_t$. This mechanism ensures that the tolerance shrinks aggressively when the posterior is changing rapidly (high learning phase) and more cautiously as the distribution stabilizes.

The adaptive tolerance selection mechanism: ratio estimation (left) and quantile selection (right).

Technical Implementation

To implement this rule effectively, the authors utilize the Kullback–Leibler Importance Estimation Procedure (KLIEP) for Ratio Estimation (REM). Unlike Kernel Density Estimation (KDE), which can be unreliable in high dimensions, KLIEP directly estimates the ratio of two distributions. This approach enhances the robustness of the $\hat{c}_t$ calculation.

Additionally, the adaptation process naturally provides an automatic stopping rule. As the algorithm converges, the ratio $\hat{c}_t$ approaches 1, causing $q_t$ to approach 1. The authors suggest terminating the sampler when $q_t > 0.99$, providing a principled way to conclude the inference process without manual intervention.

Experimental Evaluation

The aABC-PMC algorithm was evaluated against three benchmarks to test its efficiency, reliability, and real-world applicability.

  1. Gaussian Mixture Model: In this synthetic test, aABC-PMC demonstrated significant speedups, requiring only 81,230 draws compared to over 1.4 million draws for a standard manually-tuned ABC-PMC approach.
  2. Local Mode Model: This model is designed to trap algorithms in local optima. While fixed-quantile methods often failed, the adaptive exploration of aABC-PMC successfully identified the global optimum.
  3. Bacterial Infection Data: Using real-world data on Streptococcus pneumoniae colonizations, the algorithm processed a complex model with 116-dimensional summary statistics. aABC-PMC completed the task in approximately 3 days and 5 hours, outperforming the previous best-in-class ABC-SMC method by over a day.

Conclusion

The proposed aABC-PMC algorithm offers a robust and efficient framework for likelihood-free inference. By adaptively selecting tolerances based on information gain, it avoids the pitfalls of manual tuning and local optima. While challenges remain in extremely high-dimensional parameter spaces, the integration of automated stopping rules and efficient ratio estimation represents a significant advancement for practitioners using ABC methods. Future research may explore the application of this adaptive logic to other sequential ABC variants.

Citation: Simola, U., Cisewski-Kehe, J., Gutmann, M. U., and Corander, J. (2021). "Adaptive Approximate Bayesian Computation Tolerance Selection." Bayesian Analysis, 16(2), 397–423.

Summary updated

Abstract

Approximate Bayesian Computation (ABC) methods are increasingly used for inference in situations in which the likelihood function is either computationally costly or intractable to evaluate. Extensions of the basic ABC rejection algorithm have improved the computational efficiency of the procedure and broadened its applicability. The ABC – Population Monte Carlo (ABC-PMC) approach has become a popular choice for approximate sampling from the posterior. ABC-PMC is a sequential sampler with an iteratively decreasing value of the tolerance, which specifies how close the simulated data need to be to the real data for acceptance. We propose a method for adaptively selecting a sequence of tolerances that improves the computational efficiency of the algorithm over other common techniques. In addition we define a stopping rule as a by-product of the adaptation procedure, which assists in automating termination of sampling. The proposed automatic ABC-PMC algorithm can be easily implemented and we present several examples demonstrating its benefits in terms of computational efficiency.
BibTeX
@inproceedings{simola2020adaptive,
  author = {Umberto Simola and Jessica Cisewski-Kehe and Michael U. Gutmann and Jukka Corander},
  title = {{Adaptive Approximate Bayesian Computation Tolerance Selection}},
  booktitle = {Bayesian},
  year = {2020},
  doi = {10.1214/20-ba1211},
}
Figure