An Efficient Sequential Monte Carlo Algorithm for Coalescent Clustering

Part of Advances in Neural Information Processing Systems 21 (NIPS 2008)

Bibtex »Metadata »Paper »


Dilan Gorur, Yee Teh


We propose an efficient sequential Monte Carlo inference scheme for the recently proposed coalescent clustering model (Teh et al, 2008). Our algorithm has a quadratic runtime while those in (Teh et al, 2008) is cubic. In experiments, we were surprised to find that in addition to being more efficient, it is also a better sequential Monte Carlo sampler than the best in (Teh et al, 2008), when measured in terms of variance of estimated likelihood and effective sample size.