An Introduction to Variational Methods for Graphical Models

by Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola and Lawrence K. Saul

This paper describes in details the variational methods for graphical models. There are basically two important applications of variational methods (here it refers to variational bounds): one for Bayesian models where the posterior probability is hard to evaluate and therefore is a replacement for the slow MCMC methods; the other for graphical models where too many dependencies (edges in the graph) give rise to a difficult inference problem. Here the authors describe two styles of variational bounds. No matter which is employed, the ultimate objective is the same: to simplify the graph by eliminating some edges since the bound usually provides an easier way of computation.

The first bound is to exploit the Fenchel-Legendre transform of a convex/concave function. Generally speaking, a convex (concave) function has a natural upper (lower) bound, which is the tangent hyperplane at each point on the graph of the function. The so-called Fenchel-Legendre transform (or variational transform, as referred to in the paper) of a function is

\hat{f}(z) = \min_x z^\top x - f(x)

which is the intercept of the the function f where the tangent is z. Therefore

f(x) \geq \langle z, x \rangle + \hat{f}(z),

which is a lower bound for the function and z is the variational parameter. There are two examples in the paper:

• The QMR-DT is a disease-symptom bipartite Bayesian belief net. Due to the ``explaining away'' problem (a``v'' shape structure, when the child is not given the parental nodes are independent but when the child is given, they become dependent and the sum over these variables will be difficult since they are coupled), we have to simplify the probability \Pr(f_i=1 \mid d ) = 1 - \exp\left( -\sum_{j \in \mathrm{pa}(i)} \theta_{i,j} d_j - \theta_{i, 0}\right) with an upper bound.
• The Boltzmann machine can also be solved with this method.They derive a lower bound as for logistic function, which can delink all neighbours of a single r.v. but an upper bound, though easy to compute and decouple the r.v. with its neighbors, connects all its neighbors.
  

The second bound is to exploit the Jensen's inequality,

\log \Pr(x) = \log \left( \sum_z \Pr(x, z) \right) = \log \left( \sum_z q(z) \cdot \frac{\Pr(x, z)}{q(z)} \right) \geq \sum_z q(z) \log \frac{\Pr(x, z)}{q(z)},

which resembles the standard derivation of EM. Since x is observed, we usually introduce a variational parameter for q(z \mid \lambda) and maximize the lower bound by selecting a proper \lambda. The paper illustrates the idea with several mode examples:

• Boltzmann machine. Now we may put all the observed r.v.s to x and all latent r.v.s. The proposed q(z) is a decomposed binomial distribution and the parameter, i.e. the moment isthe variational parameter.
  
• Neural network, here referring to sigmoid belief network. Just like Boltzmann machine (the difference is one is MRF while the other is a belief netowrk).
  
• Factorial hidden Markov model. Since the posteror distribution of the hidden variables couples, the proposed q(z) is a decoupled prior with adjustable parameters (variational parameters).
  
• Hidden Markov decision tree.

This idea has relationships with other known models:

• Helmholtz machine: it uses two set of parameter for the generative model and recognition model instead of computing the posterior probability with Bayes' theorem.
• Sampling method: they compare Gibbs sampler and variational methods. Gibbs sampler is said to pass messages of samples (conditioned on all other variables) while variational bounds pass statistics themselves (or the parameters). Not sure, I think the global variational method is closer to this point.
• Bayesian methods: they are actually referring to the global variational method. Not clear why it is not mentioned here. Maybe it not their work -,-b

Variational Inference for Dirichlet Process Mixtures

by David M. Blei and Michael I. Jordan

This is the first DP paper I read. I heard about DP a long time ago but I haven't taken time for it until recent. This paper shows how to use (global) variational inference for the DP mixtures of exponential family.

The thing about DP is quite peculiar. The formal definition of DP would not yield us a model which could be computed. However, several related processes are employed, e.g. Chinese restaurant process and stick breaking process. In this paper the latter is adopted. One difficulty in understanding DP is the posterior distribution. For a mixture, we have several experts whose parameters comes from a common space, which is endowed with a prior H. The GP simly works on this space. GP is a stochastic meansure, which means that given a measurable set (event), it has a stochastic measure (probability). For DP, it refers to given a measurable finite partition, the probability of all events in this partition is Dirichlet distributed (with the parameter αH). Therefore, the posterior distribution of the GP is still something like this, added with several delta functions.

To solve this problem, the proposed solution can be interpreted as global variational approximation or mean field Gibbs sampling. To see why, we have to use the stick breaking process. This is a process, first we generate v_j from a Beta(1, α) distribution. The approximate uses a truncated version (let T be the stopping time). With this we can compute the mixing proportion π. We also generate ηj from H. The observation x_i is generated by taking π as the parameter of a multinomial distribution to select an index for η_j.

With this model, they propose a factorial posterior and with the idea of global variational method we can maximize the variational bound coordinate by coordinate (each coordinate is one parameter in the approximate posterior). This resembles the Gibbs sampling procedure. The difference is we use the mean (the parameter is usually the mean, first order moment) instead of do a sampling. They comapre the two in later experiments.

DiscLDA: Discriminative Learning for Dimensionality Reduction and Classification

by Simon Lacoste-Julien, Fei Sha and Michael I. Jordan

I decided to read this paper since LDA has been encountered several times recently. This LDA does not stand for Linear Discriminant Analysis, which refers to a linear classifier or sometimes the famous Fisher discriminant criterion. This term might originates from the paper published in JMLR 2003 (see below, I haven't verified this) and refers to Latent Dirichlet Allocation, which is designed for NLP modeling. It's a Bayesian generative model.

As we can see in the figure, the word w depends on the topic z, which is a r.v. of multinomial distribution. The prior for z is naturally a r.v. theta of Dirichlet distribution, whose hyperparameter is alpha. The parameter beta is simply a table of parameters for each topic. After we integrate out the latent r.v.s, z and theta, by maximizing the likelihood of the marginal distribution, i.e. empirical Bayesian method, the parameters alpha and beta could be estimated (with standard EM algorithm). To get the posterior distribution of z, we have to use variational approximation.

The LDA model could be used in unsupervised learning where the topic provides a dimensionality reduction/semantic hashing function. It could also be used in classification, where z is the corresponding label.

This paper provides additional information for the topics. These labels are side supervised information.

As you might see in thr figure, the label y comes into the model and the model becomes tougher. So the resulting inference is solved with MCMC methods. The improvement of the model demonstrates how the side information could help build a better model. Not sure about the core part. But it looks worth trying...

Several References
David M. Blei, Andrew Y. Ng and Michael I. Jordan: Latent Dirichlet Allocation, JMLR 2003