Markov chain Monte Carlo is a general computing technique that has been widely used in physics,
chemistry, biology, statistics, and computer science. It simulates a Markov chain whose invariant
states follow a given (target) probability in a very high (say millions) dimensional state space.
Essentially, it generates fair samples from a probability which are used for many purposes.
A. System simulation. For many systems, their states are thought to follow some probability models.
e.g. in statistical physics, the microscopic states of a system follows a Gibbs model given
the macroscopic constraints. Sometimes, we have hard constraints and a uniform probability
on the set of valid states. The fair samples produced by MCMC will show us what states are
typical of the underlying system. E.g. the typical protein folding under certain conditions.
In computer vision, this is often called "synthesis" ---the visual apparance of the simulated
images, textures, and shapes is a way to verify the sufficiency of the underlying model. So
it also provides a tool for learning and model verification.
B. Scientific computing. In scientific computing, one often needs to compute the integral in very
high dimensional space. E.g. the expected (macroscopic) property of a system. This is often
done by Monte Carlo integration, i.e. estimating the expectation by empirical (sample) mean.
Another interesting problem is approximate counting. E.g. how many non-self-intersecting paths
are in a 2D n x n lattice? One may also estimate the value of pi if we can generate uniform
samples in a unit square.
In computer vision, Monte Carlo integration is used in learning and model estimation, and has
also been used in motion tracking etc.
C. Optimization and Bayesian inference. The objective is to compute the global optimum of some
Bayesian posterior probability. In vision, a Bayesian posterior is often quite "peaky"
or "very cold" if it is well formulated. This is why human vision has only one or a few of
interpretations (otherwise we are very confused). Thus simulating the posterior will yield
the plausible visual interpretation of the image. Very often the MCMC needs to go with an
simulated annealing procedure.
In the following, we prepare 7 lectures that are most related to vision research. This is
intended for a tutorial by Zhu, Tu and Delleart at ICCV05.
1. Introduction to Markov Chain Monte Carlo
(1) What is Markov chain Monte Carlo?
(2) Why using MCMC?
(3) Examples
(4) Computing with two categories of models in vision:
(5) Brief history of MCMC
2. MCMC Basics--Metropolis, Metropolis-Hastings, and Gibbs Sampling
(1) Markov Chains
(2) Inference and Estimation via Sampling
(3) The Gibbs Sampler
(4) Metropolis-Hastings
(5) Metropolis and Gibbs (revisited)
3. A variety of tricks for MCMC design
(1) Hit-and-run, random ray
(2) Generalized Gibbs sampler
(3) Simulated tempering
(4) Data augmentation
(5) Slice sampling
(6) Cluster sampling
(7) Metropolized Gibbs Sampler
4. Convergence and Exact sampling techniques
(1) Definitions and terminologies.
(2) Exact sampling techniques
(3) Convergence rate and bounds using eigen-based analysis.
(4) First hitting time analysis: ways to analyze the proposals.
5. Trans-dimensional MCMC
(1) Model Selection
(2) Reversible Jump MCMC
(3) Regression Example
(4) Rao-Blackwellized Sampling
(5) Polygonal Random Fields
6. Cluster sampling with SW-cut
(1) Graph partition and labeling
(2) Clustering with bottom-up edge probabilities
(3) Moving in the partition space
(4) Swendsen-Wang Cuts
(5) Examples
7. Data-driven MCMC: Integrating MCMC Search with Discriminative Computing
(1) Generative and discriminative models
(2) DDMCMC case study
(3) DDMCMC approaches for vision applications