A Mention-Synchronous Coreference Resolution Algorithm Based On the Bell Tree

Xiaoqiang Luo, Abraham Ittycheriah, Hongyan Jing, Nanda Kambhatla, Salim RoukosACL 2004 · OpenReview

Abstract

This paper proposes a new approach for coreference resolution which uses the Bell tree to represent the search space and casts the coreference resolution problem as finding the best path from the root of the Bell tree to the leaf nodes. A Maximum Entropy model is used to rank these paths. The coreference performance on the 2002 and 2003 Automatic Content Extraction (ACE) data will be reported. We also train a coreference system using the MUC6 data and competitive results are obtained.

Introduction

Coreference resolution—the task of identifying all mentions in a text that refer to the same real-world entity—is a fundamental challenge in natural language processing. Traditional approaches often rely on local, greedy decision-making. In these systems, a pair of mentions is evaluated, a binary coreference decision is made, and the process moves forward. However, such local decisions are irreversible and can lead to global inconsistencies where later information contradicts an earlier, suboptimal link.

This research introduces a global search framework that represents the coreference problem as a path-finding task within a Bell tree. By exploring multiple possible partitions of mentions into entities simultaneously, the algorithm avoids the pitfalls of greedy strategies and allows the most probable global outcome to emerge.

The Bell Tree Search Space

The core innovation of this approach is the use of a Bell tree to represent the entire space of possible mention partitions. The tree is constructed "mention-synchronously": starting with the first mention as the root, each subsequent mention is added to the tree.

At each step, a new mention can either be linked to an existing entity (represented by a node in the previous level) or start a new entity. This branching structure captures every possible way to group $n$ mentions. The total number of possible partitions for $n$ mentions is the Bell Number, which grows exponentially. To maintain computational efficiency, the authors employ a beam search with pruning, keeping only the most promising paths at each level of the tree.

The Bell tree representation of the coreference search space.

Probabilistic Modeling

To navigate this search space, a Maximum Entropy (MaxEnt) model is used to score the transitions between nodes. The authors explored two distinct modeling paradigms:

  1. Mention-Pair Model: This model scores the likelihood of a link based on the relationship between the current mention and the "best" previous mention already assigned to an entity.
  2. Entity-Mention Model: This model attempts to capture entity-level information by scoring the link between the current mention and the entity as a whole, often represented by a "canonical" mention (e.g., the longest name string).

Interestingly, the Mention-Pair model outperformed the Entity-Mention model in practice. This was largely attributed to the significantly larger feature set available to the Mention-Pair model (171k vs 8.4k features) and the inherent difficulty in selecting a single representative mention for a complex entity. Additionally, a tunable start penalty ($\alpha$) was introduced to balance the probability of starting a new entity versus joining an existing one, helping to manage "entity miss" and "false alarm" rates.

Experimental Results and Analysis

The system was evaluated on standard benchmarks, including the ACE 2002 and 2003 datasets and MUC6. On the ACE 2002 test sets, the system achieved high performance with ACE-values ranging from 88% to 90%. It also demonstrated strong multilingual capabilities, performing well on Chinese and Arabic datasets despite limited training data.

A key insight from the ablation studies is the overwhelming importance of lexical features. As shown in the table below, even a significantly pruned model relying primarily on basic string matching and edit distance maintains a high level of performance.

Ablation study showing the impact of different feature sets on performance.

The "stripped-down" model (removing syntax, count, distance, and type features) still achieved an ACE-value of 86.0%. This suggests that while sophisticated linguistic features provide incremental gains, simple lexical similarity remains the primary driver of coreference resolution accuracy.

Conclusion

By casting coreference resolution as a global search problem on a Bell tree, this algorithm provides a robust framework for managing multiple hypotheses and avoiding the errors of greedy systems. While the Mention-Pair model currently leads in performance due to its rich feature set, future work may focus on better ways to aggregate entity-level information to unlock the full potential of the Entity-Mention approach.

Summary updated

Abstract

This paper proposes a new approach for coreference resolution which uses the Bell tree to represent the search space and casts the coreference resolution problem as finding the best path from the root of the Bell tree to the leaf nodes. A Maximum Entropy model is used to rank these paths. The coreference performance on the 2002 and 2003 Automatic Content Extraction (ACE) data will be reported. We also train a coreference system using the MUC6 data and competitive results are obtained.
BibTeX
@inproceedings{luo2004mention,
  author = {Xiaoqiang Luo and Abraham Ittycheriah and Hongyan Jing and Nanda Kambhatla and Salim Roukos},
  title = {{A Mention-Synchronous Coreference Resolution Algorithm Based On the Bell Tree}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2004},
  url = {https://openreview.net/forum?id=BJWRpnlubr},
}
Figure