Metropolis-Hastings Algorithm for Sampling from a distribution
Let’s dive into Metropolis-Hastings algo :)
Metropolis-Hastings is a sampling technique in statistical learning, used especially when it is difficult to sample directly from a complex target distribution. Before moving forward with this algorithm, it’s crucial to understand the concept of markov chain which forms the basis of Metropolis-Hastings
What is a Markov Chain?
Markov chain is a stochastic process that experience transitions from one state to another. A key assumption of i-th order markov chain is that the current state would only depend on previous i states and not the history of past states. This is known as markov property.
Markov chains are often represented as transition matrices or kernels (for continuous state space) that describes the probability of moving from one state to another.
Why Metropolis- Hastings?
Most of the times in statistical sampling, while aiming to sample from a probability distribution p(x), we don’t know the exact form of p(x), rather we have a f(x), which is proportional to p(x), but lacks the normalization constant to make it a valid probability distribution because calculating normalization constant requires complex integration.
Metropolis-hastings solves this problems by constructing a first order markov chain that converges to desired distribution without the need of normalization constant.
Basic Idea of Metropolis — Hastings
The metropolis-hastings algorithm uses a markov chain to approximate p(x) by generating new candidates and then accepting or rejecting them on the basis of acceptance probability. We will discussing each step in detail below:
Step — 1: Proposal Distribution
The first step is to propose a new candidate sample based on the current sample. At each step in markov chain, we propose to move from x to x’ with transition probability q(x’|x) where q is the proposal distribution. Generally a normal distribution centered at current sample is used as proposal distribution.
Choosing an appropriate proposal distribution is crucial as it affect the rate of convergence of markov chain as well as exploration of state space by the algorithm.
Step — 2: Calculate the acceptance probability
When we have proposed the next sample point to be x’ , our next task would be whether to accept or reject the sample based on some formula. In the case when we accept the proposed x’, the new state is x’, otherwise it is x only.
An obvious acceptance probability that comes to our mind is
p(acceptance) = 1 if f(x’)≥f(x) ___________ (1)
Get Panghalchhavi’s stories in your inbox
Join Medium for free to get updates from this writer.
p(acceptance) = f(x’)/f(x) if f(x’)<f(x) ___________(2)
Eqn. 1 and 2 combined can be written as :
p(acceptance) = min(1,f(x’)/f(x))
In this case we allow our algorithm to move uphill definitely if x’ is more probable than x but when not, we allow it to move downhill to less probable regions or uphill sometimes, to explore the whole state space.
The above acceptance probability is given by Metropolis and hence, this algorithm called metropolis algorithm. But this works only when we choose our proposal distribution to be symmetric (i.e. q(x’|x) = q(x|x’)) which can lead to inefficient sampling in skewed distributions.
Hastings extended the algorithm for the use of asymmetric proposal distribution (i.e. q(x’|x) != q(x|x’)) by modifying the acceptance probability formula, which is given as:
p(acceptance) = min(1,α)
where α = (f(x’)/q(x’|x))/f(x)/q(x|x’)
And this is called Hasting’s correction. This account the fact that some region might be favoured or not favoured by the probability distribution itself. Metropolis algorithm along with Hasting’s correction is known to be Metropolis — Hasting sampling algorithm.
Step 1 and 2 are followed recursively to generate a sequence of samples as shown below
The Burn-in period
In the start of the algorithm, the samples may not represent the target distribution well due to random starting point. The burn-in period refers to the initial steps of the chain that are discarded to allow the chain to settle into the target distribution. After this period, the samples begin to more accurately reflect p(x). The length of burn — in period depends on the problem you are solving and how accurate approximation you want.
Conclusion
The Metropolis-Hastings algorithm is a powerful tool for sampling from complex distributions. By proposing new samples and accepting them based on a well-defined probability, it allows us to approximate the distribution we are interested in. Its flexibility and efficiency have made it a basis of various modern statistical techniques.
Whether you are working with Bayesian models or need to simulate data from a difficult distribution, the Metropolis-Hastings algorithm provides a robust framework to achieve your goal.
Reference:
[1] Kevin Murphy, Machine Learning: A Probabilistic Perspective, Chapter 24
[2]Advances in Geophysics, Volume 52, 2010, Pages 1–102
