A Metric Space Defined on English and Its Relation to Error Correction

James BradfordCOLING 1982

TL;DR

This paper introduces a novel metric space defined on strings of grammatical symbols, enabling a quantitative measure of structural similarity between sentences. This metric is then applied to develop an error correction system for ungrammatical English sentences, demonstrating that grammatical similarity can be effectively captured by syntactic structure alone.

What Problem Does This Paper Address?

Parsing natural language sentences often fails not only due to genuine grammatical errors but also because of "holes" in the grammar – cases where a syntactically correct sentence is not anticipated by the parser's rules. This leads to the rejection of valid input. The paper addresses the challenge of correcting these ungrammatical sentences by proposing a method that relies solely on the syntactic structure of the sentence, assuming that grammatical errors often leave the core structure relatively intact.

Methods

The core of the paper is the definition of a distance function that maps pairs of strings of grammatical symbols to real numbers, forming a metric space. This distance is based on a "transformation cost" which comprises two components:

  • Rearrangement Cost: Measures the disorder between two strings by counting "gaps" between common substrings.
  • Edition Cost: Accounts for the cost of inserting or deleting symbols to transform one string into another. This cost is assumed to be constant for any grammatical symbol.

A key concept is the "match set," which pairs elements (words) from two strings. The rearrangement cost is derived from the gaps identified using a successor function, which includes a wrap-around characteristic to ensure a string's distance to itself is zero. The edit distance is then calculated based on the number of non-matching symbols and a constant unit edit cost. The paper formally defines these concepts and proves that under certain conventions (constant unit edit costs), the resulting distance function forms a metric space.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Syntactic Structure as a Proxy for Grammaticality: The paper posits that grammatical errors, even those arising from "holes" in the grammar, often preserve significant portions of a sentence's syntactic structure. This insight is crucial as it allows for error correction based on structural similarity rather than a complete understanding of all possible grammatical rules.
  • Metric Space for Sentence Similarity: Defining a metric space on strings of grammatical symbols provides a rigorous mathematical framework for quantifying the "distance" between sentences. This allows for systematic searching and comparison of sentence structures.
  • "Nearest Neighbor" Correction: The approach leverages the metric space to find the "nearest grammatical neighbor" to an ungrammatical input sentence. This nearest neighbor is a grammatically correct sentence that is structurally most similar to the input, making it a plausible correction.
  • Local Nature of Errors: The paper assumes that single error operations (insertion, deletion, alteration) tend to have a local impact, not drastically altering the global structure. This assumption underpins the effectiveness of structural comparison.

Key Results

The paper describes a program called Eta (Error Tolerant Analysis) that implements this metric-based error correction. While specific quantitative results are not detailed, the authors report that:

  • The program successfully corrects many common grammatical errors and those arising from "holes" in the grammar.
  • The proposed metric effectively captures the intuitive notion of grammatical similarity.
  • Users often find acceptable corrections proposed by Eta within three or four interactions.
  • The system can present alternatives that are structurally similar to the input, even for sentences that might otherwise defy analysis.

Limitations and Future Work

  • Subjectivity of "Likely" Alternatives: The authors acknowledge that the "likeliness" of the proposed alternatives is subjective. While the metric provides structural similarity, it doesn't guarantee semantic correctness or naturalness.
  • Focus on Syntactic Structure: The current approach relies solely on syntactic structure. Future work could explore incorporating semantic information to improve correction accuracy and relevance.
  • Pathological Cases: While the system can handle pathological cases with patience by presenting a sequence of alternatives, the efficiency and user experience for such cases might be a concern.
  • Constant Unit Edit Costs: The assumption of constant unit edit costs simplifies the metric but might not accurately reflect the varying difficulty of correcting different types of errors. Future work could explore variable edit costs.

Summary updated

BibTeX
@inproceedings{bradford1982metric,
  author = {James Bradford},
  title = {{A Metric Space Defined on English and Its Relation to Error Correction}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1982},
}

Loading related content...

Figure