AI Glossary / Probabilistic machine learning / Advanced
Annealed importance sampling
Definition
Annealed importance sampling, or AIS, estimates quantities associated with a difficult probability distribution by moving through a sequence of intermediate distributions and accumulating importance weights. It combines Markov transitions with importance sampling. A prominent use is estimating a ratio of normalizing constants, where the starting distribution is tractable and the final distribution is known only up to normalization.
What it means
Jumping directly from an easy distribution to a very different target can produce highly uneven importance weights. AIS creates a sequence of smaller changes, allowing transitions along the way to move states toward regions relevant to the target.
The intermediate steps do not remove the need for weights. A run's final state is not automatically an exact, unweighted target sample. Instead, the trajectory and its weight together support estimation. The method's usefulness depends on the chosen sequence, transition quality, overlap, and available computation, rather than the word annealed guaranteeing accurate results.
How it works
Using forward indexing, define unnormalized functions f_0 through f_K and normalized distributions p_k = f_k/Z_k. Draw the initial state from p_0. At stage k, multiply the accumulated weight by f_k(x_previous)/f_(k−1)(x_previous), then apply a transition preserving p_k. Repeat across the sequence and across independently initialized runs.
A common bridge uses geometric interpolation between the starting and final functions. Under the appropriate support, initialization, and invariance conditions, the expected AIS weight is Z_K/Z_0. Intermediate transitions need not reach equilibrium for this identity, although poor movement can greatly worsen efficiency.
Average weights to estimate the ratio. Weighted estimates of other quantities and logarithms of estimated constants have different finite-sample bias properties; they should not inherit an unbiasedness claim automatically.
Three practical examples
- A researcher evaluates a probabilistic model whose partition function is intractable. AIS estimates that constant relative to a tractable reference, with repeated runs used to investigate variability.
- A Bayesian analyst studies a posterior through a sequence linking a prior-based reference to the likelihood-weighted target. The analyst carefully retains normalization factors needed for an evidence calculation.
- A simulation team compares intermediate schedules on a small problem with a known answer before applying the method to a larger one. It checks weight concentration as well as elapsed time.
Think of it this way
Think of crossing a river using stepping stones, while keeping a careful account of how each crossing changes the representation of the destination. More useful stones can make the crossing easier, but the accounting remains essential. Simply arriving somewhere on the far bank does not mean that arrival locations have the required probability distribution.
Worked example
Consider an original two-state example with states A and B. Set f_0 = (1,1), f_1 = (1,2), and f_2 = (1,4). The normalizing constants are respectively two, three, and five, so the desired ratio is Z_2/Z_0 = 2.5.
Start from p_0, which selects each state with probability one half. For the intermediate transition, draw a fresh state from p_1 = (1/3,2/3). This is an idealized valid transition preserving p_1. A final identity transition preserves p_2 and is sufficient for this teaching example.
The first weight multiplier is one if the initial state is A and two if it is B. The second multiplier is one if the intermediate state is A and two if it is B. Therefore the four possible paths have probabilities and weights: A to A, probability 1/6 and weight one; A to B, probability 1/3 and weight two; B to A, probability 1/6 and weight two; B to B, probability 1/3 and weight four.
The expected weight is 1/6 + 2/3 + 1/3 + 4/3 = 2.5, exactly the desired ratio. Yet the final state is B with probability 2/3, not the target probability 4/5. The weighting is therefore doing essential work. One observed path, or even a small average of paths, need not yield 2.5. This finite example verifies the identity without claiming that real intermediate distributions are easy to sample exactly.
Illustrative case study
Fictional model-evaluation company BridgeScore uses AIS to compare probabilistic models. An initial report presents the logarithm of an estimated normalizing constant as an unbiased estimate of the log constant. A reviewer identifies that taking a logarithm changes the estimator's properties.
The team revises the report, records the starting constant and schedule, and checks the calculation on a small enumerated model. It also examines whether a few unusually large weights dominate the estimate. This fictional scenario illustrates methodological review; it reports no real deployment and does not imply that repeated runs reveal every missed region of a difficult target.
Common misconceptions and mistakes
AIS is not merely simulated annealing followed by an unweighted average. Its weights correct for the constructed sampling procedure. Dropping them generally changes the estimator.
Another mistake is evaluating an incremental ratio at the wrong state relative to the transition order. Index conventions vary across references, so implementations should follow one complete derivation. A transition that approximately preserves an intermediate distribution is also not automatically equivalent to one that preserves it exactly. Finally, a large run count or apparently stable estimate does not rule out rare, influential weights that have not yet appeared.
Business use
AIS can support specialist evaluation of probabilistic models when normalization is a computational obstacle. Document the reference distribution, its known constant, support assumptions, schedule, transition kernels, and randomization. Evaluate sensitivity to additional computation and compare against exact or stronger reference calculations on tractable cases. Keep claims about model quality separate from uncertainty in the numerical estimate used to assess it, especially when small score differences influence model selection.
People also ask
Must each intermediate Markov chain fully converge?
No. Validity relies on the required invariant kernels and other assumptions, though better mixing can improve efficiency.
Is the log of an unbiased positive estimate unbiased?
Generally no; the logarithm is nonlinear.
Is resampling mandatory?
No. Classical AIS runs accumulate weights without requiring particle resampling at intermediate stages.
Check your understanding
Why is the target ratio 2.5 in the example?
Answer: The final unnormalized mass sums to five and the starting mass to two.
Why are final states alone insufficient?
Answer: Their distribution in the example differs from the target.
What does averaging many valid weights estimate?
Answer: The ratio of normalizing constants, subject to the method's conditions.
Related terms
- Importance sampling
- Simulated annealing
- Sequential Monte Carlo
- normalizing constant
- partition function
- invariant distribution
- Markov transition
- marginal likelihood
Learn next
Study ordinary importance sampling and normalizing-constant ratios before implementing AIS. Then examine how bridge schedules and transition kernels affect weight variability, and distinguish estimating a constant from estimating its logarithm.
More in Probabilistic machine learning
- Advantage actor-critic - Advantage actor-critic is a reinforcement-learning approach in which an actor learns a policy and a critic helps estimate whether an action performed better...
- Alpha divergence - Alpha divergence is a parameterized family of measures for comparing probability distributions. Changing alpha changes how discrepancies are penalized.
- Amortized variational inference - Amortized variational inference learns a shared function that maps observations or other relevant context to parameters of approximate posterior distributions.
- ARD kernel - An ARD kernel is a covariance function with separate relevance-related parameters for different input dimensions.
- Asymptotic normality of the maximum likelihood estimator - Asymptotic normality of the maximum likelihood estimator is a large-sample result stating that, under suitable conditions, the estimator's centered and...
- Automatic differentiation variational inference - Automatic differentiation variational inference, or ADVI, is a method for automating approximate Bayesian inference in differentiable probabilistic models.
Sources
Neal, Annealed Importance Sampling, revised technical report, 1998: https://arxiv.org/pdf/physics/9803008
Previous: Anisotropy Next: Anomaly