Sampling and Monte Carlo Methods

Las Vegas and Monte Carlo

Some problems in machine learning are too hard to solve exactly. Randomness gives two ways to cope with that. The two labels name two kinds of randomized algorithm.

• Las Vegas algorithms always return the correct answer, or report that they failed. Their running time or memory use varies from run to run.
• Monte Carlo algorithms return an answer with a random error. For a fixed budget of time and memory, they give an approximate answer, and a bigger budget shrinks the typical error.

Think of a treasure hunt compared with an opinion poll. The hunt keeps digging until it finds the treasure, so the time is random but the find is certain. The poll asks a sample of people, so the answer is close but never exact, and asking more people makes it closer.

Predict which label fits each method, then press a button to check. These examples are written for this page and are not from the book.

Why sampling helps

The book gives three reasons to draw samples. Sampling can speed up a costly but tractable sum, such as the training cost averaged over a minibatch. It can approximate a sum or integral that cannot be computed, such as the gradient of the log partition function of an undirected model. And sometimes sampling is the goal itself, because we want a model that can produce samples from the training data.

All three rest on one move. A sum or integral over a distribution is an expectation. Here is the average of when the states are drawn from . For a discrete set of states, the sum is

For continuous states, the sum becomes an integral:

Read the first equation from left to right. Each state is a vector, says how likely it is, and gives a number for it. Weighting each value by its probability and adding up gives the true quantity .

The demo uses a loaded die with six faces, a toy example added here for illustration. Its exact sum is , which is 20.25. The die has only six states, so you could add up every term by hand. The same recipe works when the sum has so many terms that no one can add them, because it only needs samples. Press Roll again to see that the estimate wanders with the particular rolls.

The average of samples

Replace the expectation by an average of samples drawn from . This gives the Monte Carlo estimate of the true value :

Here is the -th sample, and is how many samples we drew. Each sample is a random state, so the estimate changes from run to run. Before you test it, predict what the average does as grows. For a standard normal , the true value of is 1, because and .

Pick a guess.

The estimate is unbiased, which means its average over many runs equals the truth. Take the expectation of each side of 17.3. Each sample has expectation , so the average has expectation as well:

The law of large numbers adds that the average converges to the truth as the samples grow. The samples must be independent and identically distributed (i.i.d.), and the spread of must be finite:

Move the slider and watch the purple line settle onto the dashed line. The gap is the error of one run. It does not disappear at once, but it keeps shrinking. A run that is far from the truth at 100 samples can still come back closer later, which is why the demo goes as far as 2000 samples.

Error shrinks with the square root of n

The estimate is a random variable, so its spread is measured by its variance. The estimate is a sum divided by , so its variance is divided by squared. Because the samples are independent, their variances add in the sum:

Each term is the variance of one sample, all equal, so the sum collapses to identical terms. The result is the key formula of Monte Carlo methods:

The standard deviation of the estimate, its standard error , is the square root of this. The name standard error and the symbol are added here, since the book describes the same quantity without naming it. It falls as , so each extra digit of accuracy costs a hundred times more samples. The variance of is the spread of the function over the distribution. The standard error uses it directly:

Predict how many times more samples halve the standard error.

The function under a standard normal has variance 2, so the theory line is . The purple points come from the same samples and wobble around the line. This is an honest check, because each point uses only the samples drawn up to that size.

Confidence intervals and the central limit theorem

The standard error also tells you how far to trust an estimate. The central limit theorem says that for large the average is close to a normal distribution with mean and variance . The book uses this to estimate confidence intervals around the estimate. In practice you estimate the spread from the samples, then take the estimate plus or minus standard errors for an interval that covers the truth about 95% of the time, if the approximation holds. The multiplier 1.96 and the 95% rule are added here. The book builds the interval from the normal distribution without fixing a multiplier.

The theorem is a statement about large samples. Small samples of a skewed function, such as , produce averages that are lopsided. The demo below lets you see how lopsided, and how the bell curve improves.

The skewness of an average of values of is , which is a result added here from the chi-squared distribution and is not printed in the book. A skewness of 0 means perfect symmetry. Look at the histogram, then check the coverage button.

When direct sampling is not possible

Everything so far assumed that we can draw samples from directly. The book warns that this is not always possible. When it fails, there are two routes, and the next two modules take them. Importance sampling draws from a simpler distribution and corrects with weights (section 17.2). Markov chain Monte Carlo builds a sequence of states whose long-run distribution is (section 17.3).

Match each situation to the right tool. The situations are written for this page.

A rule of thumb, added here and not printed in the book: if the distribution can be sampled by a known rule, use direct sampling. If the events you care about are rare, use importance sampling. If the distribution is only known up to an unknown normalising constant, use a Markov chain.

• A Monte Carlo estimate averages over samples from , which gives an unbiased estimate of the sum or integral .
• The law of large numbers says the estimate converges to as grows, for i.i.d. samples with finite variance.
• The variance of the estimate is , so the standard error falls as the square root of .
• The central limit theorem gives approximate confidence intervals for large , and the approximation can be poor for small samples of a skewed function.
• When direct sampling from is impossible, importance sampling and Markov chain methods take over.

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.1 (pages 590–592), 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.