Categorical Disambiguation

Gavan DuffyAAAI 1986

Introduction

In natural language processing, "categorical ambiguity"—where a single word can represent multiple parts of speech—poses a significant challenge for efficient parsing. For instance, in the sentence "The doctor might cure the patient," the word "cure" can function as either a noun or a verb, while "patient" can be a noun or an adjective. Traditional parsing methods often struggle with this ambiguity, leading to an exponential increase in the number of potential grammatical paths that must be evaluated. This paper, originally presented at AAAI in 1986, proposes a computationally efficient "Categorial Disambiguator" that utilizes rule-based constraint propagation to resolve these ambiguities before intensive syntactic or semantic analysis begins.

The Problem of Exponential Explosion

The primary issue addressed is the "explosive" nature of breadth-first searching in traditional parsers. If every word in a sentence has multiple possible category assignments, the total number of paths to check is the product of these possibilities.

Complexity of path evaluation for a simple sentence.

As shown in Figure 1, a simple six-word sentence can generate 16 distinct paths. In more complex sentences, this number grows rapidly, making real-time parsing difficult without a mechanism to prune incorrect categories early.

Methodology: The Categorial Disambiguator

The proposed solution is inspired by David Waltz’s constraint propagation techniques in computer vision. The system employs a set of approximately 40 prioritized pattern-action rules, referred to as CONDS. These rules operate on local constraints by examining the immediate neighbors of an ambiguous word.

Sample pattern-action rules (CONDS) used for disambiguation.

The disambiguation process follows several key principles:

  1. Prioritization: Rules are ordered by computational cost, ensuring that the simplest checks are performed first.
  2. Constraint Propagation: Once a word's category is determined, this information is propagated to adjacent words, potentially triggering further rules.
  3. Rule-Out Strategy: For words with multiple possibilities, the system often focuses on ruling out the least likely categories rather than selecting the correct one immediately.
  4. Lexical Queries: The rules can query a lexicon for specific syntactic or semantic subcategories to resolve finer distinctions.

Key Insights and Results

The core innovation of this approach is the "power of pruning." By resolving part-of-speech ambiguity early, the system transforms a multi-path parsing problem into a single-path problem. In the example sentence provided in Figure 1, the disambiguator reduces the 16 potential paths to a single valid path before the main parser even begins its work.

This modular design allows the disambiguator to act as a high-speed pre-processor, significantly simplifying the downstream parser. Furthermore, the system demonstrates robustness; a relatively small set of well-crafted rules can handle a wide variety of common English ambiguities.

Limitations and Future Directions

While effective, the system has limitations. It can struggle with "sense ambiguity," where a word's category depends entirely on deep semantic context or discourse cues. The author suggests that future iterations could incorporate discourse-level information or even automatically learn new rules from disambiguation failures. Despite these challenges, the constraint-propagation model remains a foundational concept for reducing complexity in linguistic analysis.

Summary updated

BibTeX
@inproceedings{duffy1986categorical,
  author = {Gavan Duffy},
  title = {{Categorical Disambiguation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure