The Influence of Minimum Edit Distance on Reference Resolution

Michael Strube, Stefan Rapp, Mark-Christoph MüllerEMNLP 2002 · DOI

Abstract

Coreference resolution—the task of identifying when different expressions in a text refer to the same entity—remains a central challenge in Natural Language Processing. While pronouns are often resolved using grammatical agreement, definite noun phrases and proper names frequently require complex semantic knowledge. This paper proposes a "cheap," language-independent feature: Minimum Edit Distance (MED). By integrating normalized MED into a machine learning framework, the authors achieve a significant performance boost, particularly for difficult-to-resolve noun phrases, bridging the gap between simple string identity and expensive semantic analysis.

Introduction

In reference resolution, systems must determine if two mentions, such as "the old university" and "the university," corefer. While exact string matching (string identity) provides high precision, it suffers from low recall, failing to capture variations caused by case, determiners, or modifiers. Previous attempts to solve this often relied on deep semantic processing or extensive world knowledge, which are computationally expensive and domain-dependent. This study investigates whether a surface-level string comparison algorithm, Minimum Edit Distance, can serve as an effective proxy for these complex features.

Methodology

The authors employed a supervised machine learning approach using C5.0 decision trees to classify pairs of expressions.

Baseline and Innovation

The baseline model incorporated 14 standard features, including grammatical functions, noun phrase (NP) forms, and agreement features (gender, number, person). To improve upon this, the researchers introduced Minimum Edit Distance (MED), also known as Levenshtein distance. MED calculates the minimum number of character-level operations (insertions, deletions, substitutions) needed to transform one string into another.

To account for varying string lengths, the MED was normalized. Two specific features were created: ante_med, normalized by the length of the antecedent, and ana_med, normalized by the length of the anaphor.

Mathematical definitions of the normalized Minimum Edit Distance features.

Experimental Setup

The system was evaluated on a corpus of 242 short German texts concerning the history and sights of Heidelberg, totaling approximately 37,000 tokens. The data was automatically pre-processed for parts of speech and NP chunks, followed by manual correction and coreference annotation. Training pairs were generated by linking anaphors to potential antecedents, with filtering applied to exclude impossible candidates (e.g., indefinite NPs) to minimize noise.

Results and Analysis

The inclusion of MED features resulted in a substantial performance increase across all categories. The baseline model, while effective for pronouns, performed poorly on definite NPs and proper names.

Baseline performance metrics (Precision, Recall, F-measure) for various NP types before the inclusion of MED features.

Key improvements observed after adding MED features include:

  • Overall F-measure: Increased from 59.97% to 67.98%.
  • Definite Noun Phrases: The F-measure more than doubled, rising from 15.84% to 33.94%.
  • Proper Names: Performance improved from 65.14% to 76.22%.

These results highlight that MED acts as a "fuzzy" string identity feature, successfully capturing variations like "die Schülern" versus "die Schüler" that exact matching would miss.

Conclusion

The use of Minimum Edit Distance provides a powerful, "cheap" feature for coreference resolution that is both language-independent and computationally efficient. While it does not solve the problem of purely semantic coreference (e.g., "the car" and "the vehicle"), it significantly improves the handling of definite NPs and proper names. Future work may explore additional surface-level features to further enhance resolution without the need for deep semantic architectures.

Summary updated

BibTeX
@inproceedings{strube2002influence,
  author = {Michael Strube and Stefan Rapp and Mark-Christoph Müller},
  title = {{The Influence of Minimum Edit Distance on Reference Resolution}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2002},
  doi = {10.3115/1118693.1118733},
}
Figure