Monte Carlo MCMC: Efficient Inference by Approximate Sampling

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1104–1113, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Monte Carlo MCMC: Efficient Inference by Approximate Sampling Sameer Singh University of Massachusetts 140 Governor’s Drive Amherst MA sameer@cs.umass.edu Michael Wick University of Massachsetts 140 Governor’s Drive Amherst, MA mwick@cs.umass.edu Andrew McCallum University of Massachusetts 140 Governor’s Drive Amherst MA mccallum@cs.umass.edu Abstract Conditional random fields and other graphi- cal models have achieved state of the art re- sults in a variety of tasks such as coreference, relation extraction, data integration, and pars- ing. Increasingly, practitioners are using mod- els with more complex 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 propose an alternative MCMC sam- pling scheme in which transition probabilities are approximated by sampling from the set of relevant factors. We demonstrate that our method converges more quickly than a tradi- tional MCMC sampler for both marginal and MAP inference. In an author coreference task with over 5 million mentions, we achieve a 13 times speedup over regular MCMC inference. 1 Introduction Conditional random fields and other graphical mod- els are at the forefront of many natural language processing (NLP) and information extraction (IE) tasks because they provide a framework for discrim- inative modeling while succinctly representing de- pendencies among many related output variables. Previously, most applications of graphical models were limited to structures where exact inference is possible, for example linear-chain CRFs (Lafferty et al., 2001). More recently, there has been a de- sire to include more factors, longer range depen- dencies, and more sophisticated features; these in- clude skip-chain CRFs for named entity recogni- tion (Sutton and McCallum, 2004), probabilistic DBs (Wick et al., 2010), higher-order models for dependency parsing (Carreras, 2007), entity-wise models for coreference (Culotta et al., 2007; Wick et al., 2009), and global models of relations (Hoff- mann et al., 2011). The increasing sophistication of these individual NLP components compounded with the community’s desire to model these tasks jointly across cross-document considerations has resulted in graphical models for which inference is compu- tationally intractable. Even popular approximate in- ference techniques such as loopy belief propagation and Markov chain Monte Carlo (MCMC) may be prohibitively slow. MCMC algorithms such as Metropolis-Hastings are usually efficient for graphical models because the only factors needed to score a proposal are those touching the changed variables. However, MCMC is slowed in situations where a) the model exhibits variables that have a high-degree (neighbor many factors), b) proposals modify a substantial subset of the variables to satisfy domain constraints (such as transitivity in coreference), or c) evaluating a single factor is expensive, for example when features are based on string-similarity. For example, the seem- ingly innocuous proposal changing the entity type of a single entity requires examining all its mentions, i.e. scoring a linear number of factors (in the num- ber of mentions of that …

Content truncated to 500 words