Yuanlu Xu's Homepage

Marching with Humility, Humor and Curiosity.

Slides: [pptx]

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.