Visualizing the Metropolis Algorithm
Let’s say you’re doing some sort of Bayesian analysis. You’ll have a prior over your model parameters . You get some data , and you want to update on this data to get the posterior , the updated distribution of the model parameters given . Let’s wheel out Bayes’ theorem and work out how to calculate , which for convenience we’ll call :
If we can calculate by using some sort of loss function, computing the numerator is relatively straightforward. And once we have the numerator, we’ve specified our posterior up to the normalization constant .
Computing the normalization constant is trickier. is the probability of seeing this data in the model, which means we have to integrate over all possible values of :
In most cases1, this won’t have a closed-form solution, and deterministic numerical integration can scale poorly with increasing dimensionality.
Monte Carlo integration
Let’s assume we can’t easily compute this integral; we can turn to Monte Carlo methods to estimate it instead. If we can directly draw from the posterior distribution , we can simply compute the density of at a set of uniformly distributed values that cover a broad range of the parameter space for :
By the law of large numbers, our estimate will converge to the true distribution as goes to infinity. But this only works if we can directly draw from . Many Bayesian models use arbitrarily complex distributions over that we can’t easily sample.
Importance sampling
Luckily, we can use importance sampling to help us approximate , by sampling from a somewhat arbitrary distribution , and then correcting for the fact that we’re sampling from and not :
In theory, all we’ve done is divide and multiply by ; it shouldn’t really matter what is2. But now, instead of trying to draw samples from , we can draw them from , which can be some distribution that’s easy to sample from. We can think of this as sampling from , and correcting the sample by multiplying by its importance weight, given by:
Now, as before, we can use to create a random set of samples for Monte Carlo integration:
Importance sampling is a very useful tool, but starts to become ineffective for of dimensions. In an high-dimensional parameter space, if you try to ensure that has support everywhere that is large, won’t have enough probability mass to properly explore the space, and your realisations will be scattered too sparsely to be of any significance.
Markov chain Monte Carlo
Markov chain Monte Carlo (MCMC) involves creating a Markov process with a stationary distribution , and then running the simulation long enough to produce a chain that converges close enough to for our purposes.
One family of MCMC methods uses the Metropolis algorithm, which is incredibly simple to implement. It can be thought of as a random walk through the parameter space that’s weighted to converge to the target distribution. Here’s a simple visualization3 of the Markov chains the Metropolis algorithm produces when it’s run on the Rosenbrock function:
mountPoint
Try reducing the variance to 0.001 and choosing a relatively low number of iterations. The acceptance rate will approach 100%, and as it does, the chain will reduce to a random walk.
Now try setting the variance around 0.5, and increasing the number of iterations around 10,000. You’ll see that regions of probability space with greater density4 are more likely to be visited by the chain.
The Metropolis algorithm
The Metropolis algorithm is really simple to implement; it can be written in a few lines of code. Given a starting point , a single iteration of the algorithm looks like:
- Perturb with a proposal distribution to produce a proposal . For the Metropolis algorithm, this proposal distribution must be symmetric, so , for all , , and .
- Calculate the ratio of posterior densities: We can see that even if we can only calculate the unnormalized posterior, computing the ratio here will cause to cancel out, and we’ll get a properly normalized term.
- Set :
Here’s the Javascript implementation used on this page:
function metropolis(dist, startPoint, variance, iterations) {
let current = startPoint;
let chain = [current];
var oldLik = dist(...current);
// Perturbs a number using a normal distribution
const perturb = x => x + normalRandom(0, variance);
// Construct chain
for (var i=0; i < iterations; i++) {
const candidate = map(perturb, current);
const newLik = dist(...candidate);
const acceptProbability = newLik / oldLik;
if (Math.random() < acceptProbability) {
// Accept candidate
oldLik = newLik;
current = candidate;
}
chain.push(current);
}
return chain;
};
In this case, the proposal distribution is the normal distribution centered at 0 with a user-selected variance, and our “posterior distribution” is actually just the Rosenbrock function. We also don’t need to calculate , because Math.random()
always produces a value that’s less than .
Helping our intuition
Interestingly, just observing the algorithm operate in low dimensions gave me some intuition about its behaviour in higher dimensions.
Proposal distribution
The proposal distribution can greatly affect the convergence of the chain. If the proposal distribution tends to produce very small steps5, the chain will traverse the probability space very slowly.
In our visualization, we can sort of see that the start point is in a rather featureless region of probability density, which means if we take tiny steps, is very likely to be close to . The acceptance ratio will hover around , which means almost every proposal will be accepted, and the behaviour of the chain will be decided almost entirely by the proposal distribution.
If our proposal distribution makes very large steps, however, most of the proposals will be rejected. You can observe this behaviour by making the variance very large and noticing that the acceptance rate tends to drop. This means that you’re basically doing importance sampling, and you’ll need a prohibitive number of iterations to properly explore the probability space.
In practice, we generally target acceptance rates of around 30%.
Burn-in
A chain is likely to spend its initial states trying to find some region of high density, and this groping search is unlikely to approximate the target distribution. It’s standard practice to “burn-in” a chain by discarding the first, say, 50% of the chain, and only checking the remainder for convergence. This behaviour can be observed in our visualization if you set the variance to about 0.01; the first portion of the chain is generally spent wandering around the uninteresting portions of the probability space.
Results
Once we’re satisfied with the convergence of the chain, we can use it as an approximation for our target distribution. Here’s how the Metropolis algorithm approximates the Rosenbrock function:
mountPoint
At a low number of iterations, the chain doesn’t really explore much of the probability space, so we get a rather noisy look at a portion of the target distribution. If we increase the number of iterations to the hundred thousand range, we can see the familiar Rosenbrock arch shape emerge.
Increasing our iterations to the millions6 (hold down the Shift key while dragging!) will give a clearer picture of the function, with a lot of detail around the global maximum at the top right of the arch.
Why does it converge?
We’ve got an intuitive understanding of why the chain is more likely to explore regions of higher density, but we don’t have a proof- even an informal one- that the Markov chain will converge to the target distribution. Let’s take a look at one now.
The Metropolis algorithm aims to create a Markov chain with as its stationary distribution. Because we’ve selected our proposal distribution to be symmetric, our chain is irreducible and aperiodic by construction. For reasons that I won’t get into here, this means that it must have a unique stationary distribution. But why is this stationary distribution ?
For an unspecified point , the distribution of it having successor is given by integrating over all possible values of :
We’ve chosen to be symmetric:
so we can substitute this in to get
because of course .
This means that the probability density of the chain moving to , given that it’s at , is given by the density of the distribution !
Usually this is only feasible in simple Bayesian models, particularly those with conjugate priors.↩
Provided we didn’t introduce any singularities.↩
You can drag up and down on the text boxes to change the numbers. Holding Shift while dragging will increase the step size by 10x, while holding Control while dragging will reduce it by 10x.↩
In this case, the greatest density is around the top right of the bend.↩
Which happens in our visualization if the variance is very low↩
This can take a while. The algorithm itself runs on a web worker so that the page doesn’t lock up while it’s running, but the final graphing needs to happen on the UI thread and can freeze up the page for a short time.↩