Introduction
In the field of Natural Language Processing, resolving lexical ambiguity—determining the correct form or meaning of a word based on its context—remains a fundamental challenge. David Yarowsky's seminal work introduces a statistical procedure using Decision Lists to tackle this problem. By prioritizing the single most reliable piece of evidence in a given context, the algorithm achieves remarkable accuracy, specifically in the task of restoring missing accents in Spanish and French text.
The Challenge of Accent Restoration
Accent restoration is a specific form of lexical ambiguity resolution. In languages like Spanish and French, diacritics are frequently omitted in informal communication, capitalized headlines, or legacy email systems. This omission creates significant ambiguity. For instance, in Spanish, the word completo (complete) can be confused with completó (he/she completed), representing a conflict in both tense and part-of-speech. Traditional spell-checkers often struggle with these context-dependent distinctions. Yarowsky’s goal was to build a system capable of automatically re-inserting these accents by analyzing surrounding linguistic clues.
Methodology: The Decision List Approach
The core innovation of this research is the use of Decision Lists, a supervised learning approach that follows a "winner-takes-all" strategy. This differs from standard Bayesian classifiers, which typically combine multiple correlated features—a process that can lead to "double-counting" evidence when features are not independent.
The algorithm operates through four main steps:
- Feature Extraction: The system identifies potential clues, such as the immediate neighboring words, word pairs at specific offsets, or words appearing within a wider window (e.g., $\pm 20$ to $50$ words).
- Log-Likelihood Ranking: For every identified clue (collocation), the algorithm calculates a reliability score using the absolute log-likelihood ratio: $Abs(\log(\frac{Pr(Sense_1 | Collocation_i)}{Pr(Sense_2 | Collocation_i)}))$.
- List Construction: All clues are sorted into a single list, ordered from the most reliable to the least reliable.
- Inference: To disambiguate a word, the system scans the list and applies the first matching rule. All subsequent, less-reliable clues are ignored.
This approach also leverages class-based models. When specific word data is sparse, the system utilizes general lists trained on broader patterns, such as common Spanish verb endings like -ara/-ará.
Datasets and Evaluation
To provide a rigorous "ground truth," the author used large-scale corpora where accents were programmatically stripped from correctly accented text:
- Spanish AP Newswire (1991-1993): 49 million words.
- French Canadian Hansards (1986-1988): 19 million words.
- Le Monde (French): 1 million words.
Key Insights
The success of the Decision List model rests on several empirical observations:
- The "Single Best Evidence" Rule: Using only the top-ranked clue often outperforms complex combinations of clues because linguistic features are rarely independent.
- One Sense Per Collocation: Words almost always exhibit a single sense when paired with a specific neighbor.
- Transparency and Efficiency: Unlike modern "black box" models, Decision Lists are human-readable and computationally inexpensive, making them ideal for real-time applications like grammar checkers or text-to-speech systems.
Results and Performance
The algorithm demonstrated exceptional performance, exceeding 99% overall accuracy for both Spanish and French. Even in strictly ambiguous cases—which accounted for 18% of the Spanish tokens—the system achieved 98% agreement with the original text, significantly outperforming the "most frequent sense" baseline of 93%.
Difficult distinctions, such as the Spanish subjunctive vs. future tense (terminara vs. terminará), were resolved with 92% accuracy by utilizing broader context clues like "WEEKDAY" indicators.
Conclusion
Yarowsky’s Decision List algorithm provides a robust, transparent, and highly accurate solution for lexical ambiguity. While corpus noise and data sparsity for rare words remain minor hurdles, the framework's success suggests broad applicability to other linguistic tasks, including capitalization restoration and vowel restoration in languages like Hebrew.
Summary updated