A Smart-Dumb/Dumb-Smart Algorithm for Efficient Split-Merge MCMC

Wei WANG UPMC, Stuart Russell
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:526-535, 2015.

Abstract

Split-merge moves are a standard component of MCMC algorithms for tasks such as multitarget tracking and fitting mixture models with unknown numbers of components. Achieving rapid mixing for split-merge MCMC has been notoriously difficult, and state-of-the-art methods do not scale well. We explore the reasons for this and propose a new split-merge kernel consisting of two sub-kernels: one combines a “smart” split move that proposes plausible splits of heterogeneous clusters with a “dumb” merge move that proposes merging random pairs of clusters; the other combines a dumb split move with a smart merge move. We show that the resulting smart-dumb/dumb-smart (SDDS) algorithm outperforms previous methods. Experiments with entity-mention models and Dirichlet process mixture models demonstrate much faster convergence and much better scaling to large data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-upmc15a, title = {A Smart-Dumb/Dumb-Smart Algorithm for Efficient Split-Merge {MCMC}}, author = {UPMC, Wei WANG and Russell, Stuart}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {526--535}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/upmc15a/upmc15a.pdf}, url = {https://proceedings.mlr.press/r13/upmc15a.html}, abstract = {Split-merge moves are a standard component of MCMC algorithms for tasks such as multitarget tracking and fitting mixture models with unknown numbers of components. Achieving rapid mixing for split-merge MCMC has been notoriously difficult, and state-of-the-art methods do not scale well. We explore the reasons for this and propose a new split-merge kernel consisting of two sub-kernels: one combines a “smart” split move that proposes plausible splits of heterogeneous clusters with a “dumb” merge move that proposes merging random pairs of clusters; the other combines a dumb split move with a smart merge move. We show that the resulting smart-dumb/dumb-smart (SDDS) algorithm outperforms previous methods. Experiments with entity-mention models and Dirichlet process mixture models demonstrate much faster convergence and much better scaling to large data sets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Smart-Dumb/Dumb-Smart Algorithm for Efficient Split-Merge MCMC %A Wei WANG UPMC %A Stuart Russell %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-upmc15a %I PMLR %P 526--535 %U https://proceedings.mlr.press/r13/upmc15a.html %V R13 %X Split-merge moves are a standard component of MCMC algorithms for tasks such as multitarget tracking and fitting mixture models with unknown numbers of components. Achieving rapid mixing for split-merge MCMC has been notoriously difficult, and state-of-the-art methods do not scale well. We explore the reasons for this and propose a new split-merge kernel consisting of two sub-kernels: one combines a “smart” split move that proposes plausible splits of heterogeneous clusters with a “dumb” merge move that proposes merging random pairs of clusters; the other combines a dumb split move with a smart merge move. We show that the resulting smart-dumb/dumb-smart (SDDS) algorithm outperforms previous methods. Experiments with entity-mention models and Dirichlet process mixture models demonstrate much faster convergence and much better scaling to large data sets. %Z Reissued by PMLR on 04 October 2026.
APA
UPMC, W.W. & Russell, S.. (2015). A Smart-Dumb/Dumb-Smart Algorithm for Efficient Split-Merge MCMC. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:526-535 Available from https://proceedings.mlr.press/r13/upmc15a.html. Reissued by PMLR on 04 October 2026.

Related Material