Hierarchical Dirichlet Processes

by Yee Whye Teh, Michael I. Jordan, Matthew J. Beal and David Blei

This paper is relevant to hierarchical modeling of MoE (hence related to HMoE). The DP extension for mixture model has been studied in this paper (with variational approximation methods) too. This paper only use Monte Carlo methods for inference (instead of approximation algorithms). They simply introduce one DP prior for parameters of the model that generates the data and another DP prior for the generation of groups. In one word,

G_0 \mid \gamma, H \sim \mathrm{DP}( \gamma, H ), G_j \mid \alpha_0, G_0 \sim \mathrm{DP}( \alpha_0, G_0), \theta_{ji} \sim G_j, x_{ji} \sim F(\theta_{ji}).

Their idea of DP is implemented with SBP (as in this paper). However, we can only observe x_i. For a learning problem we must find a proper settings for \gamma and \alpha_0. For inference, we must get the posterior distribution of two DPs. Please notice for a DP MoE, the base distribution of the DP is on the parameter space; now in HDP, the base distribution of the intermediate DP is a random measure, which is the top DP. Therefore the base distribution of the top DP is on the parameter space: the sampling from the top DP results in \sum_{k = 1}^K \frac{m_k}{m + \gamma}\delta_{\phi_k} + \frac{\gamma}{m + \gamma} H where m_k is the number of samples with \phi_k values and \phi_k are drawn from H, m=\sum_{k=1}^K m_k; the intermediate DP put these samples \theta_i in groups according to \sum_{t = 1}^T \frac{n_t}{i-1 + \alpha_0} \delta_{\psi_t} + \frac{\alpha_0}{i-1 + \alpha_0} G_0, where n_t is the number of samples in this group and T is the number of groups.

Now we come to the details:

• The SBP generates a set of v_i, \pi_i and \theta_i in the following way,

  v_i \sim \mathrm{Beta}(1, \alpha), \quad \pi_i = v_i \prod_{k = 1}^{i - 1}(1 - v_i), \quad \theta_i \sim G, \quad \Pr(\theta = \theta_i) = \pi_i

  This is equivalent to a DP whose parameter is \alpha and G. Then we may generate the data according to this.
• The HDP can be formulated as a variant of CRP, Chinese restaurant franchise: a customer chooses a dish (being served or not) and sits at a table (serving the dish or a new one). We can dormulate the generation as follows: a customer \theta_i comes into the restaurant and will sit at a table according to the intermediate DP and asks for a dish (if it is a new table) according to the top DP.
• For inference, we use SBP formulation and calculate the posterior of the hidden r.v.s. Ad we may see in the SBP formulation, we need an indicator (multinomial distribution) for one DP. The sampling is done with Gibbs sampler.
• It can be used for enhancing LDA (latent Dirichlet allocation) and HMM.
  

Hierarchical Mixtures of Experts and the EM Algorithm

by Michael I. Jordan and Robert A. Jacobs

This paper formulates HMoE, which can be regarded as a soft decision tree. Each leaf node is an expert, which is usually a GLIM and whose parameters are to be estimated. The internal nodes are soft partitions (something like a multinomial regression, the number of classes equals the number of children). Therefore each internal node actually corresponds to a hidden r.v. whose parameters (the coefficients for inner product) are to be estimated. On a whole the model is a Bayesian belief network (a poly-tree?). The training of this kind of model can be done with EM algorithm and the posterior of the hidden variables must be calculated (via belief propagation, a typical inference problem). This is an old paper, which was wrongly picked out -,-b

Mixture-of-Parents Maximum Entropy Markov Models

by David S. Rosenberg, Dan Klein and Ben Taskar

Like skip-chain CRF, the mixture-of-parent MEMM also aims at utilizing the long-range interactions for NER problems. Skip-chain CRF, though, is beautiful in theory. The inference on it cannot be easily carried out (there are loops). This paper adds directed edges to the same r.v.s but with the assumption that Pr( y | pa(y) ) is a mixture of Pr( y | y') where y' in pa(y) (please note that x is omitted in this formulation and here we refer to a single element). With this, the conditional probability Pr(y | x) can still be calculated with dynamic programming (now we have to sum over all parents as well and here we refer to a sequence).

The tricky part they employed is the mixing proportion of the parent is assumed to be known as equal for one r.v. Then they can get a convex optimization problem which can be solved just as MEMM. By computing the gradient, L-BFGS can be applied. They actually have another objective (log conditional margins instead of log joint conditional) which is non-convex but it is well-behaved in practice.

The Infinite Gaussian Mixture Model

by Carl Edward Rasmussen

This is an even earlier paper on DP. Rasmussen employs CRP though, a little different from the SBP. He first studies the finite mixture model. Then take the number of components to infinity and modify the mixing proportion correspondingly. The inference then is done by MCMC. I am not quite clear why he sets up such a complicated model -,-

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.