MCMCMC: Efficient Inference by Approximate Sampling

Conditional random fields and other graphical models have achieved state of the art results in a variety of NLP and IE tasks including coref- erence and relation extraction. Increasingly, practitioners are using models with more com- plex structure—higher tree-width, larger fan- out, more features, and more data—rendering even approximate inference methods such as MCMC inefficient. In this paper we pro- pose an alternative MCMC sampling scheme in which transition probabilities are approx- imated by sampling from the set of relevant factors. We demonstrate that our method con- verges more quickly than a traditional MCMC sampler for both marginal and MAP inference. In an author coreference task with over 5 mil- lion mentions, we achieve a 13 times speedup over regular MCMC inference.