Metropolis-Hastings

Metropolis-Hastings algorithm is another sampling algorithm to sample from high dimensional, difficult to sample directly (due to intractable integrals) distributions or functions.

It’s an MCMC algorithm, just like Gibbs Sampling. It’s MC (Markov Chain) because to get the next sample, one only need to consider the current sample. It’s MC (Monte Carlo) because it generates random sample which we could use to compute integrals or numerical results, for example in the probability distribution setting, the integrals we may want to compute are the expected value, mode, median, etc.

The core of the algorithm lies in the distribution `Q(x -> x')`, which is used to suggest the next candidate of the Markov Chain given the current state/sample, and the acceptance probability alpha which is used to decide whether we accept the new sample, or stay with the current sample.

The acceptance probability alpha is found by this equation:

Where `P(x)` is the target distribution, namely the distribution we want to sample from.

When transition distribution `Q(x -> x')` is symmetric, `Q(x -> x') = Q(x' -> x)`, then the ratio will become 1, and the alpha will be just:

In this case, the Metropolis-Hastings would become just Metropolis. So, Metropolis algorithm is the special case of Metropolis-Hastings algorithm where the transition distribution is symmetric. Take Gaussian for example.

Let’s devour the code.

In the code, I ignore the min(1, x) term for the alpha calculation, and just calculate `P(x') / P(x),` because we only care about whether or not the ratio is bigger than some uniform random number `[0, 1]`, so when `P(x') / P(x) > 1`, it will then always satisfy the test just as `P(x') / P(x) = 1`, calculated from the `min(1, x)` term.

The first function I’m sampling for is a circle centered in `(1, 2)` with radius of `3`. Let’s see the result.

It indeed looks like a circle, doesn’t it?

For the second run of Metropolis-Hastings, I’m trying to sample from a Bivariate Normal distribution, exactly the same one I sampled in my Gibbs Sampling post.

The tail of the distribution looks off because the starting point of the Markov Chain I’ve chosen is `(0, 0)`. It should be discarded if we use burn-in (discard a first few samples) in our Metropolis-Hastings. Other than that, it yielded the same distribution shape as Gibbs Sampling. This is because Gibbs Sampling is derived from Metropolis-Hastings, with special case, i.e. the acceptance probability of Gibbs Sampling is 1, so it will always accept the sample drawn from the conditional distributions.

I’m curious about the performance of Metropolis-Hastings compared to Gibbs Sampling. So I profiled the two algorithms.

As we can see, Gibbs Sampling is really fast as it only need around 0.14 seconds, compared to Metropolis-Hastings 3.6 seconds. Sampling from conditional distribution is really fast, whereas sampling from full joint distribution is slow, as we can observe there when comparing call time of `p_x_given_y`, `p_y_given_x` and `pgauss`.

However, the main advantage of Metropolis-Hastings over Gibbs Sampling is that we don’t have to derive the conditional distributions analytically. We just need to know the joint distribution, and no need to derive anything analytically.