2018

Scaling-up Split-Merge MCMC with Locality Sensitive Sampling (LSS)

Luo, Chen, Shrivastava, Anshumali

Understand

Split-Merge MCMC (Monte Carlo Markov Chain) is one of the essential and popular variants of MCMC for problems when an MCMC state consists of an unknown number of components.

It is well known that state-of-the-art methods for split-merge MCMC do not scale well.
Strategies for rapid mixing requires smart and informative proposals to reduce the rejection rate.
However, all known smart proposals involve expensive operations to suggest informative transitions.

Built on

Similarity search in high dimensions via hashing
Gionis, Aristides, Indyk, Piotr, Motwani, Rajeev, et al · 1999
Earlier work this paper cites.
MRBAYES: Bayesian inference of phylogenetic trees
Huelsenbeck, John P, & Ronquist, Fredrik. 2001 · 2001
Earlier work this paper cites.
An introduction to MCMC for machine learning
Andrieu, Christophe, De Freitas, Nando, Doucet, Arnaud, & Jordan, Michael I. 2003 · 2003
Earlier work this paper cites.
A Markov chain approach to reconstruction of long haplotypes
Eronen, Lauri, Geerts, Floris, & Toivonen, Hannu. 2003 · 2004
Earlier work this paper cites.
A split-merge Markov chain Monte Carlo procedure for the Dirichlet process mixture model
Jain, Sonia, & Neal, Radford M. 2004 · 2004
Earlier work this paper cites.
Bayesian mixture model based clustering of replicated microarray data
Medvedovic, Mario, Yeung, Ka Yee, & Bumgarner, Roger Eugene. 2004 · 2004
Earlier work this paper cites.
Pattern recognition and machine learning
Nasrabadi, Nasser M. 2007 · 2007
Earlier work this paper cites.

Similar

Label embedding trees for large multi-class tasks
Bengio, Samy, Weston, Jason, & Grangier, David. 2010 · 2010
Cited alongside, same era.
Consistent weighted sampling
Manasse, Mark, McSherry, Frank, & Talwar, Kunal. 2010 · 2010
Cited alongside, same era.
Effective split-merge monte carlo methods for nonparametric models of sequential data
Hughes, Michael C, Fox, Emily, & Sudderth, Erik B. 2012 · 2012
Cited alongside, same era.
A split-merge MCMC algorithm for the hierarchical Dirichlet process
Original
Wang, Chong, & Blei, David M. 2012 · 2012
Cited alongside, same era.
Parallel sampling of DP mixture models using sub-cluster splits
Chang, Jason, & Fisher III, John W. 2013 · 2013
Cited alongside, same era.
Beyond Pairwise: Provably Fast Algorithms for Approximate k k -Way Similarity Search
Shrivastava, Anshumali, & Li, Ping. 2013 · 2013
Cited alongside, same era.
Mining of massive datasets
Leskovec, Jure, Rajaraman, Anand, & Ullman, Jeffrey David. 2014 · 2014
Cited alongside, same era.

Then

A Computational Model to Study the Concentrations of DNA, mRNA and Proteins in a Growing Cell
Sharma, Amit, & Adlakha, Neeru. 2015 · 2015
Later among the works it cites.
A Smart-Dumb/Dumb-Smart Algorithm for Efficient Split-Merge MCMC
Wang, Wei, & Russell, Stuart J. 2015 · 2015
Later among the works it cites.
Simple and efficient weighted minwise hashing
Shrivastava, Anshumali. 2016 · 2016
Later among the works it cites.
Hashing-based-estimators for kernel density in high dimensions
Charikar, Moses, & Siminelakis, Paris. 2017 · 2017
Later among the works it cites.
Linearized GMM kernels and normalized random fourier features
Li, Ping. 2017 · 2017
Later among the works it cites.
Arrays of (locality-sensitive) Count Estimators (ACE): High-Speed Anomaly Detection via Cache Lookups
Original
Luo, Chen, & Shrivastava, Anshumali. 2017 · 2017
Later among the works it cites.
A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models
Original
Spring, Ryan, & Shrivastava, Anshumali. 2017 · 2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…