A smart-dumb/dumb-smart algorithm for efficient split-merge MCMC
Wei Wang, Stuart Russell · Uncertainty in Artificial Intelligence · 2015
Split-merge moves are a standard component of MCMC algorithms for tasks such as multi-target 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 split move that proposes plausible splits of heterogeneous clusters with a 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 better scaling to large data sets.