BESTCUT: A Graph Algorithm for Coreference Resolution

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 275–283, Sydney, July 2006. c⃝2006 Association for Computational Linguistics BESTCUT: A Graph Algorithm for Coreference Resolution Cristina Nicolae and Gabriel Nicolae Human Language Technology Research Institute Department of Computer Science University of Texas at Dallas Richardson, TX 75083-0688 {cristina, gabriel}@hlt.utdallas.edu Abstract In this paper we describe a coreference resolution method that employs a classi- fication and a clusterization phase. In a novel way, the clusterization is produced as a graph cutting algorithm, in which nodes of the graph correspond to the men- tions of the text, whereas the edges of the graph constitute the confidences derived from the coreference classification. In ex- periments, the graph cutting algorithm for coreference resolution, called BESTCUT, achieves state-of-the-art performance. 1 Introduction Recent coreference resolution algorithms tackle the problem of identifying coreferent mentions of the same entity in text as a two step procedure: (1) a classification phase that decides whether pairs of noun phrases corefer or not; and (2) a clusteriza- tion phase that groups together all mentions that refer to the same entity. An entity is an object or a set of objects in the real world, while a men- tion is a textual reference to an entity1. Most of the previous coreference resolution methods have similar classification phases, implemented either as decision trees (Soon et al., 2001) or as maxi- mum entropy classifiers (Luo et al., 2004). More- over, these methods employ similar feature sets. The clusterization phase is different across current approaches. For example, there are several linking decisions for clusterization. (Soon et al., 2001) ad- vocate the link-first decision, which links a men- tion to its closest candidate referent, while (Ng and Cardie, 2002) consider instead the link-best deci- sion, which links a mention to its most confident 1This definition was introduced in (NIST, 2003). candidate referent. Both these clustering decisions are locally optimized. In contrast, globally opti- mized clustering decisions were reported in (Luo et al., 2004) and (DaumeIII and Marcu, 2005a), where all clustering possibilities are considered by searching on a Bell tree representation or by us- ing the Learning as Search Optimization (LaSO) framework (DaumeIII and Marcu, 2005b) respec- tively, but the first search is partial and driven by heuristics and the second one only looks back in text. We argue that a more adequate clusterization phase for coreference resolution can be obtained by using a graph representation. In this paper we describe a novel representa- tion of the coreference space as an undirected edge-weighted graph in which the nodes repre- sent all the mentions from a text, whereas the edges between nodes constitute the confidence values derived from the coreference classification phase. In order to detect the entities referred in the text, we need to partition the graph such that all nodes in each subgraph refer to the same entity. We have devised a graph partitioning method for coreference resolution, called BESTCUT, which is inspired from the well-known graph-partitioning algorithm Min-Cut …

Content truncated to 500 words