General Introduction
In this talk, we give an introduction about inference algorithms on graphical models, including belief propagation, mean field, Monte Carlo methods (MCMC, Data-Driven MCMC [1], Swendsen-Wang Cuts [2] and Compoiste Cluster Sampling [3]). Also a detailed illustration about graphical models and Monto Carlo basics is covered inside the tutorial.
Graphical Models
Markov Random Field
- Definition: random field, formulation, probabilistic interpretation.
- Application: MRF-based image segmentation.
Inference on Graphical Models
Belief Propagation
- Belief Propagation Basics: definition, algorithm, empirical studies.
- Generalized Belief Propagation: definition, algorithm.
Mean Field
- Mean Field Basics: definition, formulation, algorithm.
Monte Carlo Methods
- Monte Carlo Basics: Monte Carlo principle, sampling basics, rejection sampling, importance sampling.
- Markov chain Monte Carlo: definition, detailed balance, Metropolis-Hastings, Gibbs Sampling, extended MCMC sampling techniques.
- Data-Driven MCMC: formulation, 5 dynamics, data-driven methods (cue particles, k-partition particles).
- Swendsen-Wang Cuts: Swendsen-Wang algorithm, formulation, comparison, examples.
- Composite Cluster Sampling: formulation, candidacy graph, sampling composite cluster, example.
Reference
- [1] Image Segmentation by Data-Driven Markov Chain Monte Carlo. Z.W. Tu and S.C. Zhu, IEEE Trans on Pattern Analysis and Machine Intelligence (TPAMI), 24(5), 657-673, 2002.
- [2] Generalizing Swendsen-Wang to Sampling Arbitrary Posterior Probabilities. A. Barbu and S.C. Zhu. IEEE Trans. on Pattern Analysis and Machine Intelligence (TPAMI), 27(8), 1239-1253, 2005.
- [3] Layered Graph Matching with Composite Cluster Sampling. L. Lin, X.B. Liu and S.C. Zhu. IEEE Trans. on Pattern Analysis and Machine Intelligence (TPAMI), 32(8), 1426-1442, 2010.