A Global Relaxation Labeling Approach to Coreference Resolution

Emili Sapena, Lluís Padró, Jordi TurmoCOLING 2010

TL;DR

This paper introduces a novel approach to coreference resolution by framing it as a global graph partitioning problem solved using relaxation labeling. By integrating classification and chain formation into a single, unified method, the authors achieve state-of-the-art results on the ACE dataset, outperforming traditional two-step systems.

What Problem Does This Paper Address?

Coreference resolution, the task of identifying mentions in text that refer to the same real-world entity, is a fundamental challenge in Natural Language Processing. Traditional systems typically tackle this in two stages: first, classifying whether pairs or groups of mentions are coreferential, and second, forming these classified mentions into coherent chains. This separation can lead to inconsistencies, as local decisions in the first stage might not globally optimize the final chain structure. The paper aims to overcome these limitations by developing a unified approach that considers all mentions and their relationships simultaneously, ensuring global consistency from the outset.

Methods

The core of the proposed method is a constraint-based graph partitioning approach solved by relaxation labeling.

  • Graph Representation: The problem is modeled as an undirected graph where each mention is a vertex. Edges connect pairs of mentions, and their weights are determined by a set of learned constraints.
  • Relaxation Labeling: This iterative algorithm is used to find an optimal assignment of labels (partitions/entities) to each vertex (mention). It works by iteratively updating the probability distribution of each mention belonging to a particular entity, considering the compatibility (edge weights) with other mentions.
  • Constraint Generation: Constraints are automatically generated using a decision tree (DT) learning algorithm (C4.5) on a training corpus. Feature functions capture various linguistic properties of mention pairs.
  • Pruning and Reordering: To improve efficiency and performance, two techniques are introduced:
  • Pruning: Limits the number of edges considered for each vertex, reducing computational complexity and mitigating the impact of weak, potentially misleading constraints.
  • Reordering: Arranges mentions in a specific order (named entities first, then nominals, then pronouns) before processing, which empirically improves precision.
  • Initial State: The paper explores both a well-informed initial state (designed to favor new chain creation) and a random initial state for the relaxation labeling process.

Datasets

The experiments were conducted on the ACE-phase02 corpus, which includes Broadcast News (BNEWS), Newswire (NWIRE), and Newspaper (NPAPER) sections. The corpus was divided into training and test sets. The authors used the true mentions provided by the ACE dataset for evaluation.

Key Insights and Ideas

  • Unified Approach: Combining classification and chain formation into a single global optimization step (relaxation labeling) is more effective than sequential processing, leading to better consistency and performance.
  • Global Consistency: Relaxation labeling inherently enforces global consistency by considering the entire set of mentions and constraints simultaneously, avoiding the propagation of local errors.
  • Flexibility of Constraints: The framework is highly flexible, allowing for the incorporation of constraints from various sources, including linguistically informed rules and automatically learned features.
  • Pruning and Reordering Benefits: Pruning effectively reduces noise from weak constraints and improves scalability, while reordering (especially placing named entities first) significantly boosts precision by leveraging more informative mentions early on.
  • Informed Initial State: A carefully designed initial state for the relaxation labeling process can accelerate convergence and lead to better solutions compared to a random initialization.

Key Results

The proposed Global Relaxation Labeling Approach achieved state-of-the-art results on the ACE-phase02 dataset.

  • The system significantly outperformed baselines based on separate classification and chain formation steps.
  • With pruning and reordering, the system achieved the best results reported for the dataset, reaching 69.7 with CEAF and 74.9 with B³.
  • The well-informed initial state consistently outperformed the random initial state.
  • The pruning technique reduced computational complexity from O(n³) to O(n²).

Limitations and Future Work

  • Computational Cost: While pruning reduces complexity, the core relaxation labeling approach can still be computationally intensive, especially for very long documents. The paper notes that ILP baselines were limited to documents shorter than 200 mentions due to computational cost.
  • Feature Engineering: The performance relies on the quality and selection of feature functions for constraint generation.
  • Future Work: The paper suggests that the flexibility of the constraint-based approach opens avenues for incorporating more sophisticated knowledge, such as anaphoricity filtering, directly into the constraints. The authors also highlight the potential for further exploration of different initial states and pruning strategies.

Summary updated

BibTeX
@inproceedings{sapena2010global,
  author = {Emili Sapena and Lluís Padró and Jordi Turmo},
  title = {{A Global Relaxation Labeling Approach to Coreference Resolution}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2010},
}
Figure