Annealed importance sampling

By Radford M. Neal. 1998

Simulated annealing—moving from a tractable distribution to a distribution of interest via a sequence of intermediate distributions—has traditionally been used as an inexact method of handling isolated modes in Markov chain samplers. Here, it is shown how one can use the Markov chain transitions for such an annealing sequence to define an importance sampler. The Markov chain aspect allows this method to perform acceptably even for high-dimensional problems, where finding good importance sampling distributions would otherwise be very difficult, while the use of importance weights ensures that the estimates found converge to the correct values as the number of annealing runs increases. This annealed importance sampling procedure resembles the second half of the previously-studied tempered transitions, and can be seen as a generalization of a recently-proposed variant of sequential importance sampling. It is also related to thermodynamic integration methods for estimating ratios of normalizing constants. Annealed importance sampling is most attractive when isolated modes are present, or when estimates of normalizing constants are required, but it may also be more generally useful, since its independent sampling allows one to bypass some of the problems of assessing convergence and autocorrelation in Markov chain samplers.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Evaluating Lossy Compression Rates of Deep Generative Models (2020, methodology): “Annealed Importance Sampling (AIS) (Neal, 2001) is currently the most effective general-purpose method for estimating normalizing constants in high dimensions, and was used by Wu et al. (2016) to compare log-likelihoods of a variety of implicit generative models.”
Stochastic Normalizing Flows (2020, background): “While the potentials u λ ( y ) can be learned, a straightforward strategy is to interpolate them between the prior and target potentials: These potentials “guide” the sampling in each SNF layer, similar as in annealed importance sampling (Neal, 1998).”
Energy-Inspired Models: Learning with Sampler-Induced Distributions (2019, methodology): “Currently, most attempts to ﬁx the mismatch lie in designing better sampling algorithms ( e.g. , Hamiltonian Monte Carlo [53], annealed importance sampling [52]) or exploiting variational techniques [34, 15, 14] to reduce the inference approximation error.”
Generative Modeling by Estimating Gradients of the Data Distribution (2019, methodology): “1)—to produced samples, inspired by simulated annealing [30] and annealed importance sampling [37].”
Variational Walkback: Learning a Transition Operator as a Stochastic Recurrent Net (2017, background): “…can write the ratio of probabilities in this term as, p ( s 0 ) π T 1 ( s 0 ) π which is similar in shape (but arising in a different context) to the product of probability ratios computed for annealed importance sampling (Neal, 2001) and reverse annealed importance sampling (Burda et al., 2014).”
Learning Generative ConvNets via Multi-grid Modeling and Sampling (2017, background): “The approximation can be made more accurate using annealed importance sampling [32].”
Deep Unsupervised Learning using Nonequilibrium Thermodynamics (2015, methodology): “…networks and MCGSMs. Related ideas from physics include the Jarzynski equality [16] (known in machine learning as annealed importance sampling [30]), which uses a Markov chain which converts one distribution into another to compute the ratio of normalizing constants between the two…”
VAEBM: A Symbiosis between Variational Autoencoders and Energy-based Models (2020, methodology): “However, using AIS to estimate logZ in high-dimensional spaces is difficult.”
Wasserstein GAN (2017, background): “Variational Auto-Encoders (VAEs) [9] and Generative Adversarial Networks (GANs) [4] are well known examples of this approach.”
Adversarial Variational Bayes: Unifying Variational Autoencoders and Generative Adversarial Networks (2017, methodology): “Using AIS, we see that AVB without AC overestimates the true ELBO which degrades its performance.”
On the Quantitative Analysis of Decoder-Based Generative Models (2016, methodology): “In this paper, we propose to use annealed importance sampling (AIS; [18]) to estimate log-likelihoods of decoder-based generative models and to obtain approximate posterior samples.”
A Kernelized Stein Discrepancy for Goodness-of-fit Tests (2016, methodology): “We approximately evaluate the likelihood ratio using annealed importance sampling (AIS), which is one of the most widely used algorithm for approximating likelihood (Neal, 2001; Salakhutdinov & Murray, 2008).”
Kernel Sequential Monte Carlo (2015, methodology): “diﬀerence is in implementation: we take a stochastic approximation approach to adapting parametersinstead of an auxiliary random variable approach [1]. Furthermore, Annealed Importance Sampling (AIS) [22] is closely related to SMC samplers in general, with the notable diﬀerence that AIS does not use”
The Variational Gaussian Process (2015, background): “Although we haven’t found it necessary in practice, see Appendix E for scaling the size of variational data.”
Handbook of Markov Chain Monte Carlo (2011, neutral): “Such schemes include parallel tempering (Geyer, 1991; Earl and Deem, 2005), simulated tempering (Marinari and Parisi, 1992), tempered transitions (Neal, 1996b), and annealed importance sampling (Neal, 2001).”
Fisher Vectors Derived from Hybrid Gaussian-Laplacian Mixture Models for Image Annotation (2014, methodology): “Geometric means of distributions are used, for example, to perform smooth transition between distributions in a simulated annealing framework [30].”
Learning Energy-Based Models by Diffusion Recovery Likelihood (2020, background): “The strategy is based on annealed importance sampling [31].”
Accurate and conservative estimates of MRF log-likelihood using reverse annealing (2014, methodology): “Neal (2001) showed that the AIS weights correspond to the importance weights for f rev with q fwd as the proposal distribution.”
Sliced Score Matching: A Scalable Approach to Density and Score Estimation (2019, methodology): “For fast AIS evaluation on MNIST, we use shallow fully-connected networks with 3 hidden layers.”