Importance Sampling

Choosing which part plays the distribution

Look back at the sum from the last module. A Monte Carlo estimate needs samples from , and sometimes that is impossible. Importance sampling asks a different question. Can we move the work into a different distribution , which is easy to sample, and correct the answer with a factor for each sample?

The book makes the point that there is no unique split of a sum into a distribution and a function. The same product can be written in many ways. Predict the best place for the proposal , then check.

Pick a guess.

The task in the demo is the tail probability under the standard normal , so is the indicator of . This worked task is added here and is not in the book. Equation 17.8 below is the identity behind the method. Only the proposal changes, and the value does not.

Read it from left to right. The right side multiplies and divides by , so the product is unchanged. Averaging over with the ratio in place of gives the same answer. Try three proposals in the demo below. The area under the product is the same in every case, because only the proposal changes.

The log scale makes the tail visible. The integrand is zero below 3, and at 3 the target is already small. A proposal that puts its mass over keeps the weight small and smooth there. A proposal far from the tail gives a weight that is huge where the proposal is thin and zero where it is not needed.

The importance sampling estimator

The naive estimator draws from and averages :

Draw samples from instead, and average the weighted values. The result is the importance sampling estimator:

Both estimators have the same expected value, because the ratio cancels the change of distribution on average:

Pick a guess.

The two estimators differ in their variance, not their mean. The demo runs both on the same tail probability. The naive estimator often sees nothing at all, because the event is rare, while the importance estimator puts many of its draws where the answer lives.

The standard error of each estimator is the square root of its variance divided by . The naive estimator has per-sample variance . The importance estimator depends on the proposal, and the readout reports its ratio exactly. Both error bars come from the samples, so they wobble from one draw to the next.

Variance and the best proposal

For the importance estimator the variance is

The variance is set by the spread of . The estimator is good when this ratio is nearly constant. The best proposal makes it constant:

Here is the normalising constant, which makes sum or integrate to 1. When does not change sign, a sample from gives zero variance. The book adds that this is no help in practice, because building already requires knowing the answer. The book also notes that better proposals put more weight where the integrand is larger, and that other choices of q can still reduce the variance somewhat even when is out of reach.

The formula for the variance of the weighted indicator is worked out here and is not printed in the book. The demo uses it in closed form, so the numbers are exact. The curve has its lowest value near the tail, and it rises steeply when the proposal is too far away or too narrow.

Biased importance sampling

Often the normalising constant of is unknown, so we only have , which equals up to a constant and is not a probability. The same is true of the proposal. The book's remedy is the biased estimator, which divides by the sum of the weights, so the unknown constants cancel:

Equation 17.14 uses normalised and . Equations 17.15 and 17.16 write the same estimator with unnormalised forms, the last one with both and . Each weight is a ratio, so an unknown constant in or multiplies every weight by the same factor, and the division by the sum of the weights removes that factor.

The estimator is biased for any finite , but the bias disappears as grows, which is why the book calls it asymptotically unbiased. The demo below uses a small discrete example added here. The target is = 1, 4, 6, 4, 1 on the states 1 to 5, and the proposal is uniform. The chart plots both estimates against the number of samples n.

The unnormalised estimate does not settle at the true value. It settles at the target's total mass times the true value, which is here, because 16 is the total mass of the unnormalised target. Without knowing that total, the unnormalised estimate is useless. The normalised one does not need it.

When the weights run wild

The proposal is usually chosen to be a simple distribution, so that it is easy to sample from. Simplicity can make it match or poorly, and then the estimate can be much worse than a good choice. When is thin where is large, the weights become enormous there, and most samples land where the weights are small. The book describes the result as typical underestimation, with rare large overestimates that compensate on average.

This happens more often in high dimensions, where the joint probabilities have a huge dynamic range. The book names several places where importance sampling still helps. It speeds up training of neural language models with a large vocabulary, estimates partition functions (section 18.7), and estimates the log-likelihood of directed models such as the variational autoencoder (section 20.10.3). It can also focus the gradient on hard examples, which dominate the cost of a classifier.

The estimates form a row of dots. Most runs return zero, because no sample falls in the tail. A few runs land far above the truth. An average of many runs is reliable only when the variance is finite, and the readout shows when it is not.

• Importance sampling rewrites a sum as an average under a proposal and corrects it with the weight (17.8 to 17.10).
• Both estimators are unbiased, and the choice of proposal only changes the variance (17.11 and 17.12).
• The best proposal is proportional to (17.13), which is not usable in practice, but it shows where the proposal should put its mass.
• When the normalising constants are unknown, the biased estimator (17.14 to 17.16) divides by the sum of the weights, so the constants cancel.
• A proposal with thin tails can make the variance infinite, so the estimate can be wrong on most runs and far off on a few.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 17.2 (pages 592–595), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.