Graph-Cut-Based Anaphoricity Determination for Coreference Resolution

Vincent NgNAACL 2009

TL;DR

This paper introduces a novel graph-cut-based approach to anaphoricity determination, a crucial step in coreference resolution. By effectively coordinating anaphoricity and coreference decisions, their method significantly improves coreference resolution performance, outperforming existing state-of-the-art approaches on standard benchmarks.

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. A key sub-problem is "anaphoricity determination": deciding whether a given noun phrase (mention) is anaphoric (i.e., refers to something previously mentioned) or not. Identifying non-anaphoric mentions early can significantly improve the efficiency and accuracy of coreference systems by allowing them to skip resolving these mentions.

Previous approaches to anaphoricity determination have had limitations. Some focus on specific types of non-anaphoric phrases, while others attempt to classify all mentions but struggle with either being too conservative (missing anaphoric mentions) or not effectively integrating this information into the coreference resolution process. This paper aims to bridge this gap by proposing a method that leverages the strengths of existing approaches while mitigating their weaknesses.

Methods

The paper proposes a graph-cut-based approach to anaphoricity determination. This method is designed to:

  1. Directly optimize the coreference evaluation metric: Similar to Ng (2004), their approach allows for direct tuning of parameters to maximize the desired performance measure.
  2. Coordinate anaphoricity and coreference decisions: Like Integer Linear Programming (ILP) approaches (Denis & Baldridge, 2007; Finkel & Manning, 2008), it exploits pairwise coreference probabilities to make more informed anaphoricity decisions.

The core of their method involves constructing a graph where nodes represent mentions and edges represent relationships. The problem of partitioning mentions into anaphoric and non-anaphoric sets is then framed as a minimum cut problem on this graph. The graph construction involves three steps:

  • Mimicking Ng and Cardie (2002a): Initial edge weights are based on an anaphoricity model ($P_A$), directly mapping to the classification of mentions as anaphoric or not.
  • Mimicking Ng (2004): Edge weights are adjusted using a sigmoid function to allow for a tunable threshold ($c$) that controls the conservativeness of the anaphoricity classification, similar to Ng's approach.
  • Incorporating coreference probabilities: Pairwise coreference probabilities ($P_c$) from a coreference model are incorporated as edge weights between mention nodes. This allows the graph cut to consider the similarity between mentions when deciding their anaphoricity, preventing similar (and likely coreferent) mentions from being classified differently. A second parameter ($c_2$) is introduced to tune the influence of these coreference probabilities.

The minimum cut algorithm then partitions the graph, effectively assigning mentions to either the "ANAPHORIC" or "NOT ANAPHORIC" set.

Datasets

The authors evaluate their approach on the ACE Phase II coreference corpus, which includes three sections: Broadcast News (BNEWS), Newspaper (NPAPER), and Newswire (NWIRE). For each section, they use the provided training data to train their anaphoricity ($P_A$) and coreference ($P_c$) models, and the test data for evaluation. Mentions are automatically extracted using an in-house NP chunker.

Key Insights and Ideas

  • The power of joint inference: The paper strongly suggests that anaphoricity determination and coreference resolution are not independent tasks. Effectively coordinating them, as their graph-cut approach does, leads to significant performance gains.
  • Graph cuts as a flexible framework: Framing the problem as a minimum cut problem provides a powerful and efficient way to integrate diverse information (anaphoricity probabilities, coreference probabilities) and optimize complex objectives.
  • Balancing conservativeness and recall: The tunable parameters ($c$ and $c_2$) in their graph-cut model allow for fine-grained control over the anaphoricity classification, striking a better balance than previous methods that were often too conservative.
  • Limitations of previous evaluation: The authors highlight that previous evaluations on "true mentions" (from answer keys) might not fully reflect the utility of anaphoricity determination, as it inherently aims to identify non-anaphoric mentions. Their evaluation on automatically extracted mentions provides a more realistic assessment.

Key Results

The proposed graph-cut-based approach consistently outperformed all five baseline anaphoricity determination methods across all three ACE datasets and both MUC and CEAF scoring metrics.

  • Significant improvements: The graph-cut approach achieved F-scores that were significantly higher than the "No Anaphoricity" baseline, with MUC F-scores rising by 2.0-4.4% and CEAF F-scores rising by 2.6-4.1%.
  • Best performance: It achieved the best F-score for every dataset/scoring-program combination.
  • Robustness: The approach demonstrated robustness, outperforming the best baseline (Denis & Baldridge, 2007) in most cases.
  • Precision gains: The improvement was attributed to a large gain in precision and a smaller drop in recall, indicating that the method successfully identified many non-anaphoric mentions while misclassifying fewer anaphoric mentions compared to other methods.

Limitations and Future Work

  • Directionality: The paper notes that the minimum cut algorithm itself doesn't inherently maintain the notion of directionality, which could be useful for identifying discourse-new mentions (first mentions of a chain) as non-anaphoric. They mention that their current setup tends to classify all members of a coreference chain, including the first mention, as anaphoric.
  • Future work: The authors suggest that exploring ways to incorporate directionality into the graph cut framework could be a fruitful avenue for future research. They also imply that their flexible mechanism for coordinating anaphoricity and coreference decisions could be extended to other related NLP tasks.

Summary updated

BibTeX
@inproceedings{ng2009graph,
  author = {Vincent Ng},
  title = {{Graph-Cut-Based Anaphoricity Determination for Coreference Resolution}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure