Lecture 11: Markov Chain Monte Carlo
- Monte Carlo sampling
- Gibbs sampling
- Gibbs sampling from mixture model
- Gibbs sampling for Gaussian processes classification
- Metropolis-Hastings algorithm
- Why do MCMC methods work?
- How to apply MCMC
Lecrerc and Laplace
1777 Lecrerc:
If we drop a needle onto a lined piece of paper, he asked how likely is it to cross one of the lines? If the needle is shorter than the gap between the lines, then xxx
18xx Laplace:
An implication is that then we can estimate ... by sampling.
General MC procedure
Approximating integrals over P(x) through summing using the samples
Estimator
$$ \int f(x) P(x) dx \approx \frac{1}{S} \sum_{s=1}^{S} f(x^{(s)})$$
such that $x^{(s)} ~ P(x)$.
E.g. we can approximate pi by counting the times a sample in a unit square falls into a unit circle.
The "counting" is essentially an indicator function $I( (x^2+y^2)<1)$
Main points:
- Monte Carlo approximations expectations with a sample average
- Rejection sampling (not in this lecture) draws samples from complex distributions
- Importance sampling (not in this lecture) applies MC to "any" sum/integral
But these MC methods do not scale up!
Sampling idea
Assume we have a pseudo-random number generator from an uniform distribution on (0,1).
Transform z such that f(z)=y
$p(y) = p(z) |dz/dy|$
Integrate this equation, using that p(z)=1
$z = h(y) = \int py dy $
which is the CDF.
You can then find y by the inverse of h:
$y = h^{-1}(z)$
MCMC
- Discovered by physicists working on the atomic bomb in 1953 (Metropolis 1953).
- Hastings extension in 1970
- Gibbs sampling independently invented in 1984 (Geman and Geman 1984)
- Only after 1990s more known in statistical community
Only now popular due to increase in computing power.
We need MCMC when we do not have conjucate priors. E.g. in Gaussian process classification, where Gaussian process prior x probit likelihood != Gaussian processes posterior.
Gibbs sampling
If we have access to conditional densities of our parameters such as $p(\theta_1|\theta_2, \theta_3, ..., \theta_N, \mathbf{D})$.
This allows sequential sampling; we first sample $\theta_1$, then 2, etc.
The parameters are not necessarily independent (although independence is convenient because it makes expressions simpler).
Mixture model
When we include more latents, and then a weight vector over those latents, which parameters do we want to learn?
$z_nk$, $\mathbf{\mu_k}$, $\matbf{\Sigma}$, $\pi_k$.
To run Bayesian inference we need priors over all those.
We assume covariance matrix I for now.
GP classification
- Compute posterior over latent $f_n$
- using posterior to perform GP regression to predict function values at test points
- pushing the predicted latent function values through the squashing function (e.g. sigmoid) to produce predictive posteriors
Challenge: it's hard to sample from latent functions. We use a trick, namely introducing a set of auxiliary variables y to rearrange the integral ranges of the probit likelihood. This is just to make sampling easier.
Largely didn't follow this. REVIEW.
Metropolis
REVIEW.
Why does MCMC work?
Ran out of time; review.
If detailed balance condition is satisfied, you are guaranteed to reach a stationary distribution.