Signal Processing - July 2017 - 61

Unfortunately, obtaining closed-form solutions to these types
applied naively, only few of the IS weights take relevant valof problems is infeasible in most practical applications, and
ues, while the rest are negligible. This phenomenon is widely
therefore, developing approximate inference techniques is of
known in the IS literature as weight degeneracy [7]. If the goal
utmost interest.
is to estimate the mean of the samples of a target distribuA methodology that comes to the rescue for solving most
tion, then the proposals must be adapted to parts of the space
difficult problems of inference is based on random drawing
where the posterior probability is large, while if the focus is
of samples. It was first applied systematically by the Italian
on a problem related to system reliability, then the probability
physicist Enrico Fermi when he studied neutron diffusion [6].
of rare events is better approximated by placing the proposals
However, no publication is available from him on this topic.
in the tails of the posterior. Locating the regions from which
Later, the methodology came to be known as Monte Carlo
samples should be drawn may not be easy, which suggests
(MC) sampling.
that the main challenge in implementing IS methods lies in
The MC methods we know today were created by Stanifinding good proposal densities. However, designing these
slaw Ulam, John von Neumann, and others [7]. Their efforts
proposals usually cannot be done a priori, and thus, adaptive
coincided with the development of the first general computer
procedures must be constructed and applied iteratively. The
and resulted in the Metropolis algorithm [8]. The next major
objective is that with passing iterations the quality of the samadvancement of MC methods came with a generalization of
ples improves, and the inference from them becomes more
the Metropolis algorithm proposed by Hastings in 1970 [9].
accurate. This leads us to the concept of adaptive IS (AIS).
All of these methods represent a family of simulation-based
AIS methods are endowed with the nice feature of being able
algorithms that aim at generating samples from a target
to learn from previously sampled values of the unknowns and,
probability distribution (often a posterior
consequently, to become more accurate. It
distribution in a Bayesian setting). The
The MC methods we know is important to note that the AIS algorithms
algorithms are based on constructing a
must remain simple, i.e., both the drawing
today were created by
Markov chain that has the desired disof samples and the computation of their
Stanislaw Ulam, John von
tribution as its equilibrium distribution,
weights should be easily managed.
Neumann, and others.
which is why they are referred to as MarIn this article, we first go over the basics
kov chain MC (MCMC) algorithms [10]
of IS and then proceed with explaining the
(a review of the history of MCMC sampling can be found
learning process that takes place in AIS and with presenting
in [7]). The most prominent MCMC algorithms remain the
several state-of-the-art methods. We discuss AIS estimators
Metropolis-Hastings (MH) and Gibbs sampling algorithms
and their convergence properties and then show numerical
[10]. Since the 1990s, MCMC-based methods have seen treresults on signal processing examples. The article also provides
mendous growth and success.
an outlook of the research in AIS. For a clearer presentation,
in Table 1 we display the notation used throughout the article.

Overview of importance sampling

An important alternative to MCMC sampling is the class of
importance sampling (IS) methods. The IS methods are elegant, theoretically sound, simple to understand, and widely
applicable [7]. Assume that the aim is to approximate a
given target probability distribution. The basic IS mechanism
consists of 1) drawing samples from simple proposal densities, 2) weighting the samples by accounting for the mismatch between the target and the proposal densities, and
3) performing the desired inference using the weighted samples. IS was first used in statistical physics for inference of
rare events and, in particular, for estimating the probability
of nuclear particles that penetrate shields [11]. Later, IS was
also used as a variance reduction technique based on simulating from a proposal density instead of the target
density [12]. The interest in IS techniques was running in
parallel to the emergence of Bayesian computational methods. The interest was not only driven by their simplicity but
also by their ability to estimate normalizing constants of the
target distribution, a feature not shared by MCMC methods
that turns out to be useful in many practical problems (e.g.,
model selection).
The performance of IS methods directly depends on the
choice of the proposal densities [7]. When the method is

Background (with examples)
Problem statement
Let us consider a generic inference problem in which a d xdimensional vector of unknown static real parameters,
x ! X 3 R d x, has a probability density function (pdf)
given by
ru (x) =

r (x)

(1)

where r (x) is a nonnormalized nonnegative target function,
and Z = # r (x) dx is a finite normalizing constant that may
X
be unknown. The goal is to compute some particular moment
of x, which can be defined as
I=

#X f (x) ru (x) dx,

(2)

where f (·) can be any function of x that is integrable with
respect to ru (x).
The previous mathematical formulation can be used to
represent different problems, including the estimation of rare
events [12] or Bayesian inference [7]. For instance, when estimating rare events, Z is perfectly known and the moment of

IEEE SIGNAL PROCESSING MAGAZINE

July 2017

Table of Contents for the Digital Edition of Signal Processing - July 2017