Monte Carlo Markov Chain Methods

1. https://www.cs.ubc.ca/~arnaud/andrieu_defreitas_doucet_jordan_intromontecarlomachinelearning.pdf

• This idea of selecting a statistical sample to approximate a hard combinatorial problem by a much simpler problem is at the heart of modern Monte Carlo simulation.
• We should emphasize that in order to obtain the best results out of this class of algorithms, it is important that we do not treat them as black boxes, but instead try to incorporate as much domain specific knowledge as possible into their design
• MCMC algorithms typically require the design of proposal mechanisms to generate candidate hypotheses. Many existing machine learning algorithms can be adapted to become proposal mechanisms (de Freitas et al., 2001). This is often essential to obtain MCMC algorithms that converge quickly.

Where is its used in Bayesian inference & learning?

• Normalization
• Marginalisation
• Expectation

• To draw i.i.d samples from a "target" density \(p(x)\) defined on a high-dimensional space \(\mathcal{X}\). These N samples can be used to approximate the target density.
• Estimated integral is unbiased by strong law of large numbers - converges almost surely.

Goal: To sample from p(x) q(x) is a easier to sample from proposal distribution s.t p(x) ≤ Mq(x) for some finite M

1. Sample x_i from proposal distribution q(x).
2. Sample u from from U(0,1).
3. ACCEPT If uMq(x) < p(x); Else REJECT
4. Goto Step 1

https://www.youtube.com/watch?v=S3LAOZxGcnk

Importance weight

\begin{equation} w(x) = \frac{p(x)}{q(x)}h \end{equation}

Posterior Density Approximation

\begin{equation} \hat{p}_N(x) = \Sigma^N_{i=1} w(x_i)\delta_{x_i}(x) \end{equation}

\[ E(f(x)) = \int f(x)w(x)q(x)dx \approx \frac{1}{n} \sum_{i=1}^{n} f(x_i) w(x_i) \]

• Idea: Correct for the fact that you are sampling from a different proposal distribution q(x) instead of sampling from p(x). This correction using importance weights keeps the estimator unbiased.
• Often times q(x) is an approximate of p(x).
• Whether or not you can sample from p(x) we want to improve upon the variance of basic standard Monte Carlo sampling with an appropriate selection of q(x)

\[ \sigma^2(I_n) = \frac{1}{n}\sigma^2(f(x)(\frac{p(x)}{q(x)})) \leq \frac{1}{n} \sigma^2(f(x)) \]

Note: Not all q(x) reduce the variance. And the q(x) which minimizes the variance may not be feasible to sample from.

Here x_i s are sampled from the proposal distribution \(q(x)\).

• Sampling from space \(\mathcal{X}\) using a Markov Chain whose limiting distribution on its states is p(x), the target distribution.
• We assume that we cannot directly sample from p(x) but can calculate p(x) upto a normalization constant.
• The markov chain is designed in to spend more time in the higher probability regions of the space \(\mathcal{X}\).
• In order for the Markov Chain to have the capability to explore the entire state space, it needs to be irreducible.
• In order for the Markov Chain to not get stuck on cycles of states, it needs to be aperiodic.
• In order to make it aperiodic, add noise to the transition matrix.

• A sufficient but not necessary condition for the Markoc Chain to have a particular invariant(limiting) distribution p(x) is as follows,

\[ p(x_i) = \sum_{x_{i-1}} p(x_{i-1})T(x_i|x_{i-1}) \]

where p(x) is the invariant(target) distribution and T is a transition matrix. This could be seen as a eigenvalue equation with eigenvalue 1 and eigenvector p(x).

Using Perron-Frobenius form Linear Algebra, we can say

• The remaining eigenvalues have absolute value of to be less than 1.
• The second largest eigenvalue determines the rate of convergence of the chain. This should be as small as possible.

In case of continuous state space, \[ p(x_i) = \int p(x_{i-1})T(x_i|x_{i-1}) dx_{i-1} \]

where, K is the conditional density function and p is an eigenfunction.