What are machine learning applications of Gibbs sampling and MCMC?

Hi Jacob. There are so many applications of Gibbs sampling and MCMC that I don't know where to begin. I would say most kind of graphical models are inferred using MCMC, often Gibbs-Sampling. Examples include LDA (latent Dirichlet allocation, not the other kind), all kinds of mixture models (I think Gibbs sampling for mixtures of Gaussians is explained in Bishop's book), many non parametric methods such as the hierarchical Dirichlet process, nested Chinese restaurant process, Indian buffet process, recently "Tree-Structured Stick Breaking for Hierarchical Data". I would recommend to look at work of Michael Jordan and Zoubin Ghahramani for some applications. A sampling method that is often used is slice sampling, which is in a way an extension of Gibbs sampling.

I would be careful in using Boltzmann machines. I worked quite a lot with those an ran into all kinds of trouble. There are many papers out there on learning (restricted) Boltzmann machines and a couple on inference in (restricted) Boltzmann machines but most methods used there are just adaptions of known methods from statistics and evaluation is often quite hard.

Indeed, as Andreas said, gibbs sampling is useful for far too many things to list here. Usually, it is used to learn or perform inference in graphical models. An important thing to keep in mind is that almost anything in machine learning (except some margin-based techniques) can be formulated equivalently in a graphical model. This might incur a penalty in terms of inference cost, but doing so usually open up new possibilities. The use of these techniques is getting progressively more prevalent in ML. I suggest you also check out Andrew Mccallum's, Eric Xing's, Yeh Whye Teh's, and Hal Daume's works for more examples of interesting application of graphical models in machine learning.