Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 793–803, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Large-Scale Cross-Document Coreference Using Distributed Inference and Hierarchical Models Sameer Singh§ Amarnag Subramanya† Fernando Pereira† Andrew McCallum§ § Department of Computer Science, University of Massachusetts, Amherst MA 01002 † Google Research, Mountain View CA 94043 sameer@cs.umass.edu, asubram@google.com, pereira@google.com, mccallum@cs.umass.edu Abstract Cross-document coreference, the task of grouping all the mentions of each entity in a document collection, arises in information ex- traction and automated knowledge base con- struction. For large collections, it is clearly impractical to consider all possible groupings of mentions into distinct entities. To solve the problem we propose two ideas: (a) a dis- tributed inference technique that uses paral- lelism to enable large scale processing, and (b) a hierarchical model of coreference that represents uncertainty over multiple granular- ities of entities to facilitate more effective ap- proximate inference. To evaluate these ideas, we constructed a labeled corpus of 1.5 million disambiguated mentions in Web pages by se- lecting link anchors referring to Wikipedia en- tities. We show that the combination of the hierarchical model with distributed inference quickly obtains high accuracy (with error re- duction of 38%) on this large dataset, demon- strating the scalability of our approach. 1 Introduction Given a collection of mentions of entities extracted from a body of text, coreference or entity resolu- tion consists of clustering the mentions such that two mentions belong to the same cluster if and only if they refer to the same entity. Solutions to this problem are important in semantic analysis and knowledge discovery tasks (Blume, 2005; Mayfield et al., 2009). While significant progress has been made in within-document coreference (Ng, 2005; Culotta et al., 2007; Haghighi and Klein, 2007; Bengston and Roth, 2008; Haghighi and Klein, 2009; Haghighi and Klein, 2010), the larger prob- lem of cross-document coreference has not received as much attention. Unlike inference in other language processing tasks that scales linearly in the size of the corpus, the hypothesis space for coreference grows super- exponentially with the number of mentions. Conse- quently, most of the current approaches are devel- oped on small datasets containing a few thousand mentions. We believe that cross-document coref- erence resolution is most useful when applied to a very large set of documents, such as all the news ar- ticles published during the last 20 years. Such a cor- pus would have billions of mentions. In this paper we propose a model and inference algorithms that can scale the cross-document coreference problem to corpora of that size. Much of the previous work in cross-document coreference (Bagga and Baldwin, 1998; Ravin and Kazi, 1999; Gooi and Allan, 2004; Pedersen et al., 2006; Rao et al., 2010) groups mentions into entities with some form of greedy clustering using a pair- wise mention similarity or distance function based on mention text, context, and document-level statis- tics. Such methods have not been shown to scale up, and they cannot exploit …

Content truncated to 500 words