2 Markov chain Monte Carlo

In the previous chapter, we reviewed different types of ML algorithms and software implementation. Now, we will focus on a popular class of ML algorithms known as Markov chain Monte Carlo. Any probabilistic model that explains a part of reality exists in a high-dimensional parameter space because it is described by high dimensional model parameters. Markov chain Monte Carlo (MCMC) is a methodology of sampling from high-dimensional parameter spaces to approximate the posterior distribution p(θ|x). Originally developed by physicists, this method became popular in the Bayesian statistics community because it allows one to estimate high dimensional posterior distributions using sampling. The basic idea behind MCMC is to construct a Markov chain whose stationary distribution is equal to the target posterior p(θ|x). In other words, if we perform a random walk across the parameter space, the fraction of time we spend in a particular state θ is proportional to p(θ|x).

2.1 Introduction to Markov chain Monte Carlo

2.1.1 Posterior distribution of coin flips

2.1.2 Markov chain for page rank

2.2 Estimating pi

2.3 Binomial tree model

2.4 Self-avoiding random walk

2.5 Gibbs sampling

2.6 Metropolis-Hastings sampling

2.7 Importance sampling

2.8 Exercises

Summary