End-to-End Coreference Resolution via Hypergraph Partitioning

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 143–151, Beijing, August 2010 End-to-End Coreference Resolution via Hypergraph Partitioning Jie Cai and Michael Strube Natural Language Processing Group Heidelberg Institute for Theoretical Studies gGmbH (jie.cai|michael.strube)@h-its.org Abstract We describe a novel approach to coref- erence resolution which implements a global decision via hypergraph partition- ing. In constrast to almost all previ- ous approaches, we do not rely on sep- arate classification and clustering steps, but perform coreference resolution glob- ally in one step. Our hypergraph-based global model implemented within an end- to-end coreference resolution system out- performs two strong baselines (Soon et al., 2001; Bengtson & Roth, 2008) using sys- tem mentions only. 1 Introduction Coreference resolution is the task of grouping mentions of entities into sets so that all mentions in one set refer to the same entity. Most recent approaches to coreference resolution divide this task into two steps: (1) a classification step which determines whether a pair of mentions is corefer- ent or which outputs a confidence value, and (2) a clustering step which groups mentions into enti- ties based on the output of step 1. The classification steps of most approaches vary in the choice of the classifier (e.g. decision tree classifiers (Soon et al., 2001), maximum en- tropy classification (Luo et al., 2004), SVM clas- sifiers (Rahman & Ng, 2009)) and the number of features used (Soon et al. (2001) employ a set of twelve simple but effective features while e.g., Ng & Cardie (2002) and Bengtson & Roth (2008) de- vise much richer feature sets). The clustering step exhibits much more varia- tion: Local variants utilize a closest-first decision (Soon et al., 2001), where a mention is resolved to its closest possible antecedent, or a best-first deci- sion (Ng & Cardie, 2002), where a mention is re- solved to its most confident antecedent (based on the confidence value returned by step 1). Global variants attempt to consider all possible cluster- ing possibilites by creating and searching a Bell tree (Luo et al., 2004), by learning the optimal search strategy itself (Daum´e III & Marcu, 2005), by building a graph representation and applying graph clustering techniques (Nicolae & Nicolae, 2006), or by employing integer linear program- ming (Klenner, 2007; Denis & Baldridge, 2009). Since these methods base their global clustering step on a local pairwise model, some global infor- mation which could have guided step 2 is already lost. The twin-candidate model (Yang et al., 2008) replaces the pairwise model by learning prefer- ences between two antecedent candidates in step 1 and applies tournament schemes instead of the clustering in step 2. There is little work which deviates from this two-step scheme. Culotta et al. (2007) introduce a first-order probabilistic model which implements features over sets of mentions and thus operates directly on entities. In this paper we describe a novel approach to coreference resolution which avoids the division into two steps and instead performs a global deci- sion in one step. We …

Content truncated to 500 words