PaperlayerView exact revision on arXiv

Source-linked AI summary

On optimality of kernels for approximate Bayesian computation using sequential Monte Carlo

Sarah Filippi, Chris Barnes, Julien Cornebise, Michael P. H. Stumpf

arXiv:1106.6280v4stat.CO

TL;DR

Complex models can make likelihood evaluation impractical, and kernel choice in ABC SMC remains a pressing concern. The paper analyzes perturbation kernels and their optimality for this setting. It finds that locally adapted kernels tend to perform best for complicated posterior shapes, with Fisher-information-based kernels particularly efficient where applicable.

  • Problem

    Likelihood evaluation is often impractical for complex biological models, while kernel choice in ABC SMC remains a pressing concern affecting computational efficiency.

    Source: §1 · pp. 1, 3

  • Method

    The paper analyzes ABC SMC perturbation kernels using optimality criteria based on Kullback-Leibler divergence and compares their performance across illustrative and molecular-biology problems.

    Source: §1 · pp. 2–3

  • Results

    For non-Gaussian, multimodal, or ridge-shaped posteriors, locally conditioned kernels outperform a straightforward multivariate normal kernel, while component-wise perturbation tends to perform poorly.

    Source: §7 · p. 20

  • Takeaways & Limitations

    The authors recommend multivariate kernels with OLCM as a generally effective, relatively easy-to-implement choice, and suggest Fisher-information-driven kernels where applicable.

    Source: §7 · p. 20

    The M-nearest-neighbours kernel is sensitive to M: too small a value risks overly local perturbations that may not converge to the posterior as ε goes to 0.

    Source: §7 · p. 20

Abstract

from arXiv · show

Approximate Bayesian computation (ABC) has gained popularity over the past few years for the analysis of complex models arising in population genetic, epidemiology and system biology. Sequential Monte Carlo (SMC) approaches have become work horses in ABC. Here we discuss how to construct the perturbation kernels that are required in ABC SMC approaches, in order to construct a set of distributions that start out from a suitably defined prior and converge towards the unknown posterior. We derive optimality criteria for different kernels, which are based on the Kullback-Leibler divergence between a distribution and the distribution of the perturbed particles. We will show that for many complicated posterior distributions, locally adapted kernels tend to show the best performance. In cases where it is possible to estimate the Fisher information we can construct particularly efficient perturbation kernels. We find that the added moderate cost of adapting kernel functions is easily regained in terms of the higher acceptance rate. We demonstrate the computational efficiency gains in a range of toy-examples which illustrate some of the challenges faced in real-world applications of ABC, before turning to two demanding parameter inference problem in molecular biology, which highlight the huge increases in efficiency that can be gained from choice of optimal models. We conclude with a general discussion of rational choice of perturbation kernels in ABC SMC settings.

1 Introduction

Complex biological models and data make likelihood evaluation impractical, motivating ABC’s use of simulated-data comparisons to approximate posterior distributions. This paper focuses on perturbation-kernel choice in ABC SMC, which affects computational efficiency as particles move toward the posterior.

1 Introduction

  • ABC approximates posterior distributions by comparing observed and simulated data when direct likelihood evaluation is too complicated or numerically demanding.The approach may compare summary statistics instead of raw data when the data are intricate, although insufficient summaries can create problems.Source: §1 · pp. 1–2
  • ABC rejection often wastes samples in parameter regions that cannot produce simulations resembling the observed data, motivating more efficient schemes such as ABC SMC.The authors focus on sequential importance sampling because they describe it as flexible, applicable, and increasingly popular in applications.Source: §1 · p. 2
  • ABC SMC builds intermediate distributions from a prior toward the unknown approximate posterior by perturbing particles and accepting simulated data.The paper focuses on the Toni et al. (2009) and Beaumont et al. (2009) implementation.Source: §1 · p. 2
  • Kernel choice and the tolerance schedule both affect ABC SMC complexity, while increasing parameter dimension makes convergence and parameter-space exploration harder to balance.The paper concentrates on perturbation-kernel selection.Source: §1 · p. 2
  • The paper characterizes kernel performance and develops optimality results, then evaluates computational efficiency in illustrative problems and two molecular-biology inference problems.The introduction identifies expensive simulations, including dynamical systems, as settings where kernel choice strongly affects efficiency.Source: §1 · p. 3

2 The ABC SMC algorithm

ABC SMC advances from a permissive initial tolerance toward a target posterior by reusing and perturbing accepted particles. Its efficiency depends on tolerance scheduling and kernel choice, with adaptive thresholds and kernels each involving trade-offs.

2 The ABC SMC algorithm

  • ABC accepts a particle when simulated and observed data are within the tolerance, repeating until N particles are accepted as a posterior sample.The basic scheme samples parameters from the prior and simulates data from the generative model.Source: §2 · p. 3
  • ABC SMC constructs successive approximate posterior distributions by tightening the tolerance and perturbing particles accepted at the previous stage.The algorithm begins with an ABC sample at a sufficiently large tolerance, then repeats the process using particles from the preceding stage.Source: §2 · p. 3
  • The paper distinguishes its ABC SMC implementation from SMC samplers, which require forward and backward kernels and reduce algorithmic complexity from O(N^2) to O(N).The authors note that data simulation can dominate the O(N^2) term in applications of interest.Source: §2 · pp. 3–4
  • Adaptive tolerance selection can improve ABC SMC efficiency, but some quantile choices may prevent convergence to the target posterior.The adaptive threshold is selected as an α-quantile of simulated-to-observed data distances.Source: §2 · p. 5
  • Local kernels tend to yield higher acceptance when successive tolerances are close, whereas permissive kernels explore more broadly at lower acceptance.Kernel choice also affects the algorithm’s computational complexity.Source: §2 · p. 5

3 Properties of optimal kernels

The section defines kernel quality through how closely the accepted joint proposal matches the target and how often proposals are accepted. Its optimality criterion formalizes that trade-off, with finite-population and convergence qualifications.

3 Properties of optimal kernels

  • An efficient perturbation kernel balances resemblance between the joint proposal and target distributions, measured by KL divergence, with a high average acceptance probability.The criterion’s log-acceptance term strongly penalizes very low acceptance probabilities.Source: §3 · pp. 5–6
  • The criterion refines existing kernel-selection criteria and frames the choice as a trade-off between proposal-target resemblance and acceptance rate.The authors state that the maximization can be carried out in practice for random-walk kernels.Source: §3 · p. 6
  • For finite populations, replacing the ideal previous-stage distribution with the weighted empirical particle distribution yields the exact optimality criterion for population size N.The simplified derivation omits resampling, which in practice samples with replacement from the previous particle population.Source: §3 · p. 6
  • Convergence theory requires kernels with support larger than the target and tails that decay slowly enough to ensure finite-variance importance weights.These conditions support asymptotic unbiasedness and normality, respectively.Source: §3 · p. 6
  • Whether optimal kernels satisfy all convergence conditions is outside the paper’s scope; Gaussian kernels have unbounded support, while the chosen asymmetric KL direction facilitates but does not guarantee finite variance.The authors say this KL direction favors proposals that cover the target.Source: §3 · p. 6

4 Optimal choice of random walk kernels

The section compares parametric perturbation kernels for ABC SMC and develops covariance choices intended to improve particle proposals. It moves from component-wise and population-wide kernels to locally adapted and Fisher-information-based alternatives.

4.1 Component-wise perturbation kernel

  • Component-wise kernels perturb parameter coordinates independently; adaptive Gaussian widths use the previous population, with twice its component variance optimal under the stated equal-threshold criterion.Uniform and component-wise normal kernels differ in support: bounded versus unbounded.Source: §4.1 · p. 7

4.2 Multivariate normal perturbation kernels

  • For highly correlated parameters, a multivariate normal kernel using the previous population’s covariance reflects parameter correlations and is reported to yield fewer rejected proposals than component-wise alternatives.The optimal covariance is derived within the multivariate Gaussian family; when successive thresholds are equal, it can be approximated by twice the previous population’s empirical covariance.Source: §4.2 · pp. 8–9

4.3 Local perturbation kernels

  • For nonlinear parameter correlations, global covariance may capture little local structure, motivating particle-specific multivariate normal kernels with local covariance matrices.The section considers three local perturbation kernels.Source: §4.3 · p. 9

4.3.1 The multivariate normal kernel with M nearest neighbours

  • A nearest-neighbour kernel perturbs each particle using the empirical covariance of its M nearest neighbours, but choosing M trades off exploration against the advantage over the global kernel.M is typically fixed in advance; mixtures over M are described as computationally too expensive.Source: §4.3.1 · p. 9

4.3.2 The multivariate normal kernel with optimal local covariance matrix

  • The optimal local covariance combines covariance among nearby weighted particles with a bias term for the difference between their mean and the particle being perturbed.The resulting particle-specific kernel is called the multivariate normal kernel with OLCM, or optimal local covariance matrix.Source: §4.3.2 · p. 10

4.3.3 Perturbation kernel based on the Fisher information for model defined by ordinary or stochastic differential equations

  • For ODE and SDE models, the Fisher information matrix can inform local covariance, but the inverse-FIM kernel can have excessively large covariance or explore only a parameter’s immediate neighbourhood.The proposed variants scale the inverse-FIM matrix to control its determinant, matching either the previous population covariance determinant or a local empirical covariance determinant; FIM approximation is described for ODEs and SDEs.Source: §4.3.3 · pp. 10–11

5 Numerical results

Across three toy posteriors, kernel performance depends on geometry: local covariance helps when global structure is inadequate, while Fisher-information-based proposals perform best on the banana example but depend on neighborhood size.

5 Numerical results

  • The toy comparisons use a shared threshold schedule to isolate kernel choice, although the authors advise adapting thresholds in practice.All simulations use Euclidean distance to compare simulated and observed data.Source: §5 · pp. 11–12

5.1 Ellipsoid shape

  • On the ellipsoid posterior, 50-neighbor and OLCM multivariate normal kernels achieve acceptance rates over twice those of component-wise kernels.The posterior’s strongly correlated parameters make full covariance estimates more effective than component-wise variances.Source: §5.1 · pp. 12–13, Figure 4 · p. 13

5.2 Ring shape

  • For the ring posterior, global-covariance and OLCM multivariate kernels perform similarly to component-wise kernels, while the 50-neighbor kernel yields higher acceptance.The whole-population correlation is weak, making a more local perturbation useful.Source: §5.2 · p. 13

5.3 Banana shape

  • On the banana posterior, the Fisher-information kernel using nearest neighbors has the highest acceptance, but acceptance falls as neighborhood size increases.Larger neighborhoods make the kernel less locally aware, and performance depends on the chosen neighbor count.Source: Figure 5 · p. 14, §5.3 · p. 15

6 Applications in Molecular Biology

In the molecular-biology applications, multivariate perturbation kernels reduce computational effort, but the best-performing choice differs between simulated repressilator data and real Hes1 data.

6 Applications in Molecular Biology

  • Both applications infer parameters from mRNA measurements using ABC SMC with 1,000 particles.The repressilator data are simulated with added Gaussian noise, whereas the Hes1 measurements are experimental real-time PCR data.Source: §6.1 · p. 17, §6.2 · p. 18

6.1 The Repressilator Model

  • The repressilator required up to 6 × 10^6 simulations with the uniform kernel, versus 1.6 × 10^5 with the second FIM-based multivariate normal kernel.Running time was proportional to simulation count, and kernel-adaptation costs were small compared with the time saved.Source: Figure 6 · p. 16, §6.1 · p. 17

6.2 The Hes1 model

  • For Hes1, multivariate normal kernels sped inference by up to fourfold; the 50-neighbor kernel performed best, while OLCM was similar and avoided choosing a neighbor count.FIM-based kernels performed poorly on these real data, possibly because the likelihood surface was not smooth enough for the FIM to help; the authors recommend OLCM for this model.Source: §6.2 · p. 18

7 Conclusion

The tested kernels reached essentially identical posterior distributions, while their efficiency varied with kernel choice. Locally adapted multivariate kernels performed well for complex posterior shapes, but Fisher-information kernels were not robust in the Hes1 example.

7 Conclusion

  • All tested kernels reached essentially identical posterior distributions, making acceptance rate an objective efficiency criterion when the ϵ schedule is fixed.The authors characterize their kernel analysis as rigorous but non-exhaustive, focusing on uniform and normal or multivariate-normal families.Source: §7 · p. 18
  • For non-Gaussian, multimodal, or ridged posteriors, locally conditioned kernels outperformed a straightforward multivariate normal kernel; component-wise perturbation also performed poorly.Correlated parameters should be taken into account when choosing a perturbation approach.Source: §7 · p. 20
  • When data simulation dominates ABC SMC’s O(N^2) algorithmic cost, higher acceptance can reduce computational cost; for equal acceptance, prefer the cheaper kernel.The passage identifies simulation cost as often exceeding the algorithmic complexity of ABC SMC.Source: §7 · p. 20
  • Multivariate OLCM kernels are recommended as a practical rule of thumb, while FIM kernels can explore neutral spaces efficiently but were costly and insufficiently robust on Hes1.The Hes1 limitation is especially relevant for complex biological models with real data and a non-smooth likelihood surface.Source: §7 · p. 20
  • M-nearest-neighbour kernels can repay their cost through higher acceptance, but their performance depends on M; too-small values risk preventing convergence as ϵ approaches zero.This tuning sensitivity makes them less user-friendly than OLCM.Source: §7 · p. 20
  • Recombination can be included when new-particle weights are calculable and is best suited to undersampled parameter spaces; optimization proposals offer no obvious advantage for distributional inference.The authors distinguish maximum-a-posteriori inference, where such proposals may be fruitful, from inference focused on the distribution as a whole.Source: §7 · pp. 20–21
  • Choosing the ϵ schedule is another route to faster ABC SMC, but gentle decreases can reduce particle diversity, so convergence and exploration must be balanced.The next threshold can be automated using the acceptance rate from the current intermediate distribution.Source: §7 · p. 21
Loading 1106.6280v4…