Teh et, JASA2006

Citation

Y. Teh, M. Jordan, M. Beal, and D. Blei. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 2006

Online version

Mathew Beal's papers

Summary

This paper proposed a nonparametric Bayes approach to decide the number of mixture components in grouped data, the basic idea is:

Develop analogs for the Hierarchical Dirichlet process with representations of both a stick-breaking and a "Chinese restaurant franchise”.

Use MCMC algorithm for posterior inference under hierarchical Dirichlet process mixtures.

Methodology

A hierarchical Dirichlet process is a distribution over a set of random probability measures over $(\theta ;B)$ . The process defines a set of random probability measures $G_{j}$ , one for each group, and a global random probability measure $G_{0}$ . The global measure $G_{0}$ is distributed as a Dirichlet process with concentration parameter and base probability measure H:

$G_{0}|\gamma ,H\sim DP(\gamma ,H)$

and the random measures $G_{j}$ are conditionally independent given G0, with distributions given by a Dirichlet process with base probability measure $G_{0}$ :

$G_{j}|\alpha _{0},G_{0}\sim DP(\alpha _{0},G_{0})$ .

A hierarchical Dirichlet process can be used as the prior distribution over the factors for grouped data. For each j let $\theta _{j1},\theta _{j2},...$ be i.i.d. random variables distributed as $G_{j}$ . Each $\theta _{j}i$ is a factor corresponding to a single observation $x_{ji}$ . The likelihood is given by:

$\theta _{ji}|G_{j}\sim G_{j}$

$x_{ji}|\theta _{ji}\sim F(\theta _{ji})$ .

The hierarchical Dirichlet process can readily be extended to more than two levels. That is, the base measure H can itself be a draw from a DP, and the hierarchy can be extended for as many levels as are deemed useful.

The stick-breaking construction

Given that the global measure $G_{0}$ is distributed as a Dirichlet process, it can be expressed using a stick-breaking representation:

$G_{0}=\sum _{k=1}^{\infty }\beta _{k}\delta _{\phi _{k}},$

where $\phi _{k}\sim H$ independently and $\beta =(\beta _{k})_{k=1}^{\infty }\sim GEM(\gamma )$ are mutually independent. Since $G_{0}$ has support at the points $\phi =(\phi _{k})_{k=1}^{\infty }$ , each $G_{j}$ necessarily has support at these points as well, and can thus be written as:

$G_{j}=\sum _{k=1}^{\infty }\pi _{jk}\delta _{\phi _{k}}$

Let $\pi _{j}=((\pi _{jk})_{k=1}^{\infty })$ . Note that the weights $\pi _{j}$ are independent given $\beta$ (since the $G_{j}$ are independent given $G_{0}$ ). These weights $\pi _{j}$ are related to the global weights $\beta$ .

An equivalent representation of the hierarchical Dirichlet process mixture can be:

$\beta |\gamma \sim GEM(\gamma )$

$\pi _{j}|\alpha _{0},\beta \sim DP(\alpha _{0},\beta )$

$z_{j}i|\pi _{j}\sim \pi _{j}$

$\phi _{k}|H\sim H$

$x_{ji}|z_{ji},(\phi _{k})_{k=1}^{\infty }\sim F(\phi _{z_{ji}})$ .

After some derivations, the relation between weights and $\beta$ is:

${\frac {1}{1-\sum _{l=1}^{k-1}\pi _{jl}}}(\pi _{jk},\sum _{l=k+1}^{\infty }\pi _{jl})\sim Dir(\alpha _{0}\beta _{k},\alpha _{0}\sum _{l=k+1}^{\infty }\beta _{l})$ .

Chinese restaurant franchise

The restaurants correspond to groups and the customers correspond to the factors $\theta _{ji}$ . Let $\phi _{1},...,\phi _{K}$ denote K i.i.d. random variables distributed according to H; this is the global menu of dishes. Vairables $\psi _{jt}$ represent the table-specific choice of dishes; particular, $\psi _{jt}$ is the dish served at table t and restaurant j. Use notation $n_{jtk}$ to denote the number of maintain counts of customers and counts of tables. Then,

$\theta _{ji}|\theta _{j1},...,\theta _{j,i-1},\alpha _{0},G_{0}\sim \sum _{t=1}^{m_{j.}}{\frac {n_{jt.}}{i-1+\alpha _{0}}}\delta _{\psi _{jt}}+{\frac {\alpha _{0}}{i-1+\alpha _{0}}}G_{0}$ ,

$\psi _{jt}|\psi _{11},\psi _{12},...,\psi _{21},...,\psi _{j,t-1},\gamma ,H\sim \sum _{k=1}^{K}{\frac {m_{.k}}{m_{..}+\gamma }}\delta _{\phi _{k}}+{\frac {\gamma }{m_{..}+\gamma }}H$

MCMC algorithm for posterior sampling in the Chinese restaurant franchise

The Chinese restaurant franchise can yield a Gibbs sampling scheme for posterior sampling given observations x. Rather than dealing with the $\theta _{ji}$ 's and $\psi _{jt}$ 's, we shall sample their index variables $t_{ji}$ and $k_{j}t$ instead.

Sampling t. The prior probability that $t_{ji}$ takes on a particular previously used value t is proportional to $n_{jt.}^{-ji}$ , whereas the probability that it takes on a new value (say $t^{new}=m_{j.}+1$ ) is proportional to $\alpha _{0}$ . The likelihood due to $x_{ji}$ given $t_{ji}=t$ for some previously used t is $f_{k}^{-x_{ji}}(x_{j}i)$ , then

If the sampled value of $t_{j}i$ is $t^{new}$ , we obtain a sample of $k_{jt^{new}}$ by sampling from

If as a result of updating $t_{ji}$ some table t becomes unoccupied, i.e., $n_{jt.}=0$ , then the probability that this table will be reoccupied in the future will be zero, since this is always proportional to $n_{jt.}$ . As a result, we may delete the corresponding $k_{jt}$ from the data structure. If as a result of deleting $k_{jt}$ some mixture component k becomes unallocated, we delete this mixture component as well.

Sampling k. Since changing $k_{jt}$ actually changes the component membership of all data items in table t, the likelihood obtained by setting $k_{jt}=k$ is given by $f_{k}^{-x_{jt}}(x_{jt})$ , so that the conditional