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.
  

The Infinite Hidden Markov Model

by Matthew J. Beal, Zobin Ghahramani and Carl Edward Rasmussen

This paper extends HMM with DP. In HMM, the transition matrix and the emission probability are all multinomial distributed. The Bayesian adds a Dirichlet prior for them and now we try Dirichlet instead. Their construction is from Chinese restaurant process (CRP). The generation procedure is: first it may go to any existing states (including itself) or asking an oracle (DP); if it asks the oracle, the oracle may tell it go to an existing state or send it a new state (DP). Finally it generate a sample using a DP (may generate those it has already generates or new). Therefore it is a hierarchical DP.

The learning procedure requires five hyperparameters. The posterior has to be approximated with Gibbs sampling. The Learning of hyperparameter is rather vague, not sure why they introduce another prior for the hyperparameters (maybe we can only use sampling -,-b). The model has only been tested on simulated data though. I really doubt about its applicability in practice.

Deterministic Annealing for Semi-supervised Kernel Machines

by Vikas Sindhwani, S. Sathiya Keerthi and Olivier Chapelle

I am surprised that another similar paper on S³VM in the same conference (c.f. the continuation method). The homotopy method does the same thing as the continuation. Find a simple, easy-to-optimize function to start with and end up with the original complex, full-of-local-minima target function. In the continuation setting, convolution with a Gaussian whose variance is diminishing is employed to mollify the target function.

Here, the key idea is the following optimization

might be solved by an annealing in MCMC category. Then we reformulate the S³VM target function as this, by introducing a probability for predicting labels for the unlabelled samples.

Then we have to deal with the optimization with a fixed T(temperature in annealing) and p, which is a convex optimization problem.

They also analyze the corresponding loss function for different Ts. As we can see, the initial loss functions are convex and as the temperature goes down, they are deformed into non-convex ones.