Neal (2000) Markov Chain Sampling Methods for Dirichlet Process Mixture Models

Summary

Neal reviews the existing Markov chain Monte Carlo methods for the posterior of a Dirichlet process mixture (DPM) model and adds two new classes designed for the hard case — non-conjugate priors, where the standard Gibbs sampler requires an intractable integral over the base measure. The first uses Metropolis-Hastings updates of the component indicators (optionally supplemented with partial Gibbs); the second — the widely-used "Algorithm 8" — augments the state with temporary auxiliary components drawn from the base measure $G_0$, so that a new cluster can be proposed by ordinary Gibbs sampling without any integration. Both are simple to implement and more efficient than prior non-conjugate methods.

Key Claims

• Why non-conjugacy is hard. Marginalizing $G$ gives a Pólya-urn/CRP Gibbs sampler in which reassigning observation $i$ to a new component needs $\int f(y_i\mid\theta)\,G_0(d\theta)$ — analytic only under conjugacy. Non-conjugate models (common and often more appropriate) previously required awkward numerical integration (West-Müller-Escobar) or the MacEachern-Müller (1998) "no gaps" auxiliary scheme.
• Algorithm 8 (auxiliary-variable Gibbs). Temporarily introduce $m$ auxiliary components with parameters drawn i.i.d. from $G_0$ (a singleton observation keeps its current parameter as one of them). Then Gibbs-sample $c_i$ over the union of the $k^-$ existing components and the $m$ auxiliary ones, with probabilities $$P(c_i=c\mid\cdots)\propto\begin{cases}\dfrac{n_{-i,c}}{n-1+\alpha}\,F(y_i,\theta_c) & \text{existing }c\\[2mm]\dfrac{\alpha/m}{n-1+\alpha}\,F(y_i,\theta_c) & \text{auxiliary }c\end{cases}$$ then discard unused parameters. No integral over $G_0$ is required; increasing $m$ trades computation for better mixing. For $m=1$ it closely resembles MacEachern-Müller's "no gaps" (Algorithm 4) but mixes better.
• Metropolis-Hastings indicator updates. Propose changing $c_i$ (to an existing or freshly-drawn component) and accept by the M-H ratio; optionally interleave partial Gibbs updates of the shared components. Avoids the base-measure integral entirely and is trivial to code.
• A unifying taxonomy. The paper organizes the whole family — conjugate Gibbs over parameters (Algorithm 1/2), Gibbs over indicators (Algorithm 2/3), MacEachern-Müller no-gaps (4), M-H methods (5–7), and auxiliary-variable Gibbs (8) — clarifying which apply under conjugacy vs. non-conjugacy and how they mix.
• Efficiency. On standard examples the new non-conjugate methods (especially Algorithm 8 with modest $m$) are simpler and mix faster than previous approaches, making general DPM inference routine.

Concepts Introduced or Extended

• Dirichlet Process Mixture

Entities Mentioned

• Radford M. Neal

Quotes

"This article reviews Markov chain methods for sampling from the posterior distribution of a Dirichlet process mixture model and presents two new classes of methods."

"These methods are simple to implement and are more efficient than previous ways of handling general Dirichlet process mixture models with non-conjugate priors."

My Take

This is the paper that made Dirichlet-process mixtures practical for the models people actually want to fit — the ones where the base measure is not conjugate to the kernel, so the tidy Escobar-West collapse doesn't apply. Algorithm 8's trick is beautifully simple: you can't integrate over "a new cluster's parameters," so instead sample a few candidate new clusters from the prior and let ordinary Gibbs choose among them, with $m$ a dial between cost and mixing. It sits directly downstream of Sethuraman's (1994) stick-breaking (which makes the DP concrete) and Antoniak's (1974) CRP cluster structure (which the samplers traverse), and it is the reference every applied DPM paper cites for "how we did the MCMC." For the wiki it completes the computational leg of the DPM concept: Sethuraman gives the object, Neal gives the algorithm.