A Split-Merge Markov Chain Monte Carlo Procedure for the Dirichlet Process Mixture Model

Sonia Jain, Dept. of Statistics, University of Toronto
Radford M. Neal, Dept. of Statistics and Dept. of Computer Science, University of Toronto

We propose a split-merge Markov chain algorithm to address the problem of inefficient sampling for conjugate Dirichlet process mixture models. Traditional Markov chain Monte Carlo methods for Bayesian mixture models, such as Gibbs sampling, can become trapped in isolated modes corresponding to an inappropriate clustering of data points. This article describes a Metropolis-Hastings procedure that can escape such local modes by splitting or merging mixture components. Our Metropolis-Hastings algorithm employs a new technique in which an appropriate proposal for splitting or merging components is obtained by using a restricted Gibbs sampling scan. We demonstrate empirically that our method outperforms the Gibbs sampler in situations where two or more components are similar in structure.

Technical Report No. 2003, Dept. of Statistics, University of Toronto (July 2000), 32 pages: postscript, pdf.

Associated references: A revised version of this technical report was published as the following paper:
Jain, S. and Neal, R. M. (2004) ``A Split-Merge Markov Chain Monte Carlo Procedure for the Dirichlet Process Mixture Model'', Journal of Computational and Graphical Statistics, vol. 13, pp. 158-182: abstract, associated references.

More recent work along these lines for nonconjugate models is reported in the following technical report:
Jain, S. and Neal, R. M. (2005) ``Splitting and merging components of a nonconjugate Dirichlet process mixture model'', Technical Report No. 0507, Dept. of Statistics (August 2005), 37 pages: abstract, postscript, pdf, associated references.

The following earlier papers of Radford Neal are related:
Neal, R. M. (1998) ``Markov chain sampling methods for Dirichlet process mixture models'', Technical Report No. 9815, Dept. of Statistics, University of toronto, 17 pages: abstract, postscript, pdf, associated reference, associated software.

Neal, R. M. (1991) ``Bayesian mixture modeling by Monte Carlo simulation'', Technical Report CRG-TR-91-2, Dept. of Computer Science, University of Toronto, 23 pages: abstract, postscript, pdf, associated references.