Source-linked AI summary
Adaptive approximate Bayesian computation for complex models
Maxime Lenormand, Franck Jabot, Guillaume Deffuant
TL;DR
Sequential ABC methods can suffer from duplicated particles and added model runs, while poorly chosen tolerance schedules reduce the benefits of importance sampling. APMC adaptively determines sequential steps and tolerance levels, and performs better across toy and social-model evaluations, using fewer simulations for comparable posterior quality.
Problem
Sequential methods face particle duplication and extra model runs, while tolerance schedules can reduce the potential computational benefit.
Method
APMC uses an adaptive sequence of tolerance levels and an automatically defined stopping criterion for its sequential steps.
Results
APMC requires 2–8 times fewer simulations than other algorithms for a given posterior quality in one comparison and 2–7 times fewer in another, while yielding good approximate posteriors quickly.
Takeaways & Limitations
APMC produced a unimodal approximate posterior for SimVillages and partly separated correlated parameter effects using census data, supporting confidence in its performance on other examples.
Takeaways & Limitations
APMC's computational gains depend on choosing a suitable decrease in tolerance values; overly sharp or shallow schedules can reduce the benefit of importance sampling.
Abstract
from arXiv · showhide
Approximate Bayesian computation (ABC) is a family of computational techniques in Bayesian statistics. These techniques allow to fi t a model to data without relying on the computation of the model likelihood. They instead require to simulate a large number of times the model to be fi tted. A number of re finements to the original rejection-based ABC scheme have been proposed, including the sequential improvement of posterior distributions. This technique allows to de- crease the number of model simulations required, but it still presents several shortcomings which are particu- larly problematic for costly to simulate complex models. We here provide a new algorithm to perform adaptive approximate Bayesian computation, which is shown to perform better on both a toy example and a complex social model.
The PMC algorithm
PMC sequentially generates particles under decreasing tolerances, reweights them to correct kernel-induced sampling bias, and stops when the final tolerance is reached.
- Tolerance schedule: PMC uses a decreasing tolerance sequence, with each accepted particle satisfying the corresponding tolerance level.The tolerance sequence is constrained between the initial and final targets.
- Sequential sampling: PMC derives each sequential sample from the previous weighted sample while accepting particles whose simulated distance to the data is below the current tolerance.The first sample uses regular ABC; later samples use a particle-filter procedure and a Gaussian kernel.
- Bias correction: Each newly generated particle receives a weight proportional to the inverse of its sampling importance, correcting bias introduced by the transition kernel.The proposal density is the weighted sum of probabilities of reaching the new particle from particles in the previous sample.
- Stopping: The algorithm stops when the sample at the target tolerance has been generated.The stopping rule is tied to reaching the final tolerance ϵT.
Limitations of the PMC algorithm
PMC’s main weakness is choosing its tolerance schedule: poor choices reduce computational gains, while MCMC-based alternatives can duplicate particles and require extra simulations.
- Limitations of the PMC algorithm: Choosing PMC’s decreasing tolerance sequence is difficult because overly sharp or shallow decreases can reduce the attainable computational benefit.The paper describes this sequence as central to obtaining an optimal gain in computing time.
- Alternative sequential methods: RSMC and SMC determine tolerances online from the previous sample, using a distance quantile or an effective-sample-size reduction.These methods also differ from PMC in using an MCMC kernel to move particles.
- Limitations of the RSMC and the SMC algorithms: MCMC rejection can duplicate particles, degrading posterior quality when the same initial particle is retained repeatedly.RSMC and SMC introduce additional procedures to limit duplication, but these procedures add complexity or computation.
- Limitations of the RSMC and the SMC algorithms: Running multiple MCMC trials or model simulations per particle reduces duplication or acceptance-ratio variance but increases model runs.These remedies undermine the computational benefit sought from sequential sampling.
Overview of the APMC algorithm
APMC adaptively constructs weighted sequential samples, selects each next tolerance from simulated distances, and stops when too few newly generated particles meet the current threshold.
- Overview of the APMC algorithm: APMC retains Nα = ⌊αN⌋ particles and generates additional particles whose distances and weights are combined with the previous sample.The retained particles form the next weighted sequential sample.
- Overview of the APMC algorithm: The next tolerance ϵt is set to the first α-quantile of the newly generated particles’ distances.This choice ensures that the tolerance does not increase and supplies enough retained particles for the next step.
- Overview of the APMC algorithm: The algorithm stops when the acceptance proportion pacc among newly generated particles falls below paccmin.The resulting sample is returned when the acceptance rate indicates that further simulations would only marginally change the posterior.
- Overview of the APMC algorithm: APMC avoids MCMC kernels and particle duplication, but its reweighting step costs O(N^2α) rather than O(Nα).The paper treats this extra computation as negligible relative to model-simulation cost.
Weights correcting the kernel sampling bias
APMC uses consistently scaled weights to combine particles generated at different iterations while correcting the bias from kernel sampling.
- Weights correcting the kernel sampling bias: APMC computes the probability density of each particle from weighted transition probabilities originating at the previous sample.This density supplies the denominator used in the particle-weight calculation.
- Weights correcting the kernel sampling bias: Consistent weight scaling allows particles from different iterations to be concatenated without introducing posterior bias.The resulting weighted particles follow the posterior restricted by ρ(x, y) < ϵt.
The stopping criterion
APMC stops when the proportion of newly generated particles meeting the previous tolerance falls below paccmin, a rule intended to make further simulations marginal. The paper evaluates this stopping criterion alongside comparisons using simulation count and L2 posterior distance.
- The stopping criterion: APMC stops when the accepted-particle proportion among newly generated particles falls below paccmin.The stopping rule is defined by Eq. 7.
- The stopping criterion: The stopping rule is intended to ensure that additional simulations would only marginally change the posterior distribution.
- Experimental setup: The study compares APMC with PMC, SMC, and RSMC on the toy example.
- Evaluation: The algorithm is evaluated using the number of simulations and the L2 distance between the exact posterior and the obtained particle histogram.The L2 distance is computed after dividing the support [−10, 10] into 300 equally sized bins.
- Experimental setup: The toy experiment uses N = 5000 particles, a target tolerance of 0.01, and 50 repetitions for each parameter setting.APMC explores nine α values and four paccmin values.
Particle duplication in SMC and RSMC
The comparisons examine particle duplication, computational cost, and posterior quality across ABC algorithms. APMC retains distinct particles and, in the reported toy and social-model experiments, achieves favorable simulation–accuracy trade-offs while producing a structured posterior for SimVillages.
- Particle duplication in SMC and RSMC: SMC loses distinct particles during its run, whereas APMC and PMC retain N distinct particles.For RSMC, the number of distinct particles is maintained at a reasonably high level, but this requires more model runs.
- Particle duplication in SMC and RSMC: The number of distinct SMC particles decreases for every tested α, and resampling oscillations do not offset the overall decline.
- Influence of parameters on APMC: APMC parameters trade posterior quality against simulation cost: smaller α and paccmin reduce L2 distance but increase model runs, with paccmin having the larger effect.
- Influence of parameters on APMC: 0.3 ≤ α ≤ 0.7 and 0.01 ≤ paccmin ≤ 0.05 provide a good toy-example compromise between model runs and posterior quality.
- Comparing performances: APMC requires between 2 and 8 times fewer simulations than the other three algorithms to reach a given posterior quality L2.Its Number of simulations × L2^2 criterion is also smaller.
Study of APMC result
APMC combines adaptive tolerance selection, a stopping criterion, and reweighting without particle duplication. In the complex SimVillages model, it achieves lower simulation cost for a given posterior quality than competing algorithms, while its performance depends on parameter settings.
- Posterior result: APMC produces a unimodal approximate posterior for SimVillages and partly separates the opposing effects of parameters θ1 and θ4.The available census data yield a posterior peak rather than a ridge.
- Parameter choice: Intermediate α and paccmin values produce similar results, with α = 0.5 and paccmin between 0.01 and 0.05 recommended depending on the desired convergence level.The recommendation is based on the complex-model results.
- Computational performance: 2–7 times fewer simulations are required by APMC to reach a given posterior quality L2 than by the other algorithms.The simulation-number gain increases progressively during the algorithm.
- Computational performance: The squared L2 distance times the number of simulations is smaller for APMC than for the other algorithms.Figure 5b compares this criterion across the algorithms.
- Scope: The reported performance should be confirmed on additional examples, including models with more parameters or multimodal posterior distributions.These settings are identified as future evaluation targets.
- Design rationale: APMC uses reweighting instead of an MCMC kernel and an interpretable stopping criterion that automatically sets the number of sequential steps.The reweighting corrects sampling bias without duplicating particles.
Appendix A: Description of the algorithms
The appendices describe rejection-based ABC and three sequential alternatives, then specify APMC’s adaptive particle-selection, weighting, proposal, and stopping procedures. The algorithms differ mainly in how they set tolerance levels, propose particles, and control sequential updates.
- ABC rejection sampler: Rejection-based ABC samples θ∗ from the prior, simulates x, and accepts θ∗ when ρ(S(x), S(y)) is below the tolerance.The accepted parameter values form the particle sample.
- PMC: PMC uses a supplied decreasing sequence of tolerance levels ϵ1 ≥ ... ≥ ϵT and weighted particles across sequential iterations.Its algorithm is described separately from adaptive tolerance methods.
- RSMC: RSMC initializes particles under ϵ1, sorts them by distance, and reduces the tolerance until reaching the target ϵT.The retained particles are replenished during the sequential procedure.
- SMC: SMC tracks particle weights and effective sample size while using resampling and proposal simulations over sequential iterations.Its inputs include N, M, α, an initial infinite tolerance, a target tolerance, and an ESS threshold.
- APMC: APMC retains Nα = ⌊αN⌋ particles, sets each new tolerance to an α-quantile of distances, and updates particle weights using a proposal distribution.New particles are generated from weighted retained particles with Gaussian perturbations.
- APMC: APMC continues until the acceptance proportion falls below paccmin, using this threshold as its stopping rule.The stopping condition is evaluated among the newly generated particles.
Appendix B: Proof that the algorithm stops
The stopping proof establishes that APMC’s decreasing tolerance sequence converges to a positive limit and that the acceptance proportion converges to zero under a finite-bound condition. Therefore, the algorithm stops for any chosen paccmin.
- Tolerance convergence: The tolerance sequence ϵt is positive, decreasing, bounded below by zero, and therefore converges to some ϵ∞ > 0.This establishes the limiting tolerance used in the stopping argument.
- Acceptance analysis: The N − Nα particles at each step are independent and identically distributed from the density defined by the algorithm.This distributional property is used to analyze the probability of zero accepted particles.
- Stopping guarantee: If Pmax < +∞, pacc(t) converges in probability to zero, ensuring that the algorithm stops for any chosen paccmin.The conclusion follows from the acceptance-probability bound in the proof.