Categorizing Unknown Words: Using Decision Trees to Identify Names and Misspellings

Janine TooleNAACL 2000

TL;DR

This paper introduces a novel multi-component system that uses decision trees to automatically identify and categorize unknown words as either names or misspellings. This approach is particularly effective for noisy text like live closed captions, where traditional methods struggle due to the lack of capitalization.

What Problem Does This Paper Address?

Natural Language Processing (NLP) systems rely on a lexicon of known words to function. When an NLP system encounters a word not in its lexicon – an "unknown word" – its performance can degrade significantly. These unknown words can arise for various reasons: they might be proper names, misspellings, abbreviations, or morphological variants. The crucial first step in handling these unknown words is to identify their category. This paper focuses on distinguishing between two common categories: proper names and misspellings, especially in challenging domains like live closed captions where standard cues like capitalization are absent.

Methods

The core of the system is a multi-component architecture, where each component specializes in identifying a specific type of unknown word. For this paper, the focus is on two components: a "Name Identifier" and a "Misspelling Identifier." Both components utilize decision trees, a machine learning technique that builds a model by asking a series of questions about the data. Decision trees are chosen for their explainability and ability to combine diverse types of evidence.

The Name Identifier aims to distinguish proper names (people, places, concepts typically capitalized) from other words. Since existing name recognizers often rely heavily on capitalization, which is absent in their target domain (live closed captions), the authors developed their own. They use ten features to train the decision tree, including part-of-speech tags (both general and detailed), corpus frequency, word length, edit distance to a dictionary, and character sequence frequencies.

The Misspelling Identifier aims to identify words that are orthographically incorrect representations of known words. It also employs a decision tree, trained on features derived from previous research. These features include corpus frequency, word length, edit distance to the output of the ispell checker, character sequence frequencies, and a binary feature indicating the presence of non-English characters.

A Decision Making Component then combines the predictions from the Name and Misspelling Identifiers. If their predictions are compatible (e.g., one says "name" and the other says "not misspelling"), the decision is straightforward. In cases of conflicting positive predictions, a simple heuristic is used: the prediction with the highest confidence measure (derived from the decision tree's leaf nodes) is accepted.

Datasets

The system was trained and evaluated using data extracted from a 2.6 million word corpus of live business news closed captions.

  • Training Data: 70% of 7000 unknown word cases.
  • Test Data: The remaining 30% (2100 records), used to create ten test sets by random sampling with replacement.
  • Data Distribution: 70.4% of the cases were identified as names, 21.3% as misspellings, and the rest as other types of unknown words.

Key Insights and Ideas

  • Domain-Specific Challenges: Live closed captions present a unique challenge for NLP due to the absence of capitalization, rendering many standard name-recognition techniques ineffective.
  • Decision Trees for Explainability: The use of decision trees allows for interpretable models, where the features influencing a classification are readily understandable. This is valuable for debugging and improving the system.
  • Feature Engineering is Key: The success of the decision trees hinges on carefully selected features that capture the characteristics of names and misspellings, even in the absence of capitalization. Features like corpus frequency and character sequence patterns prove crucial.
  • Modular Architecture Benefits: The multi-component approach allows for specialization and the potential to integrate improved individual components or add new categories of unknown words in the future.
  • Name Features Don't Always Help Misspelling Identification: Surprisingly, features designed for name identification did not improve the misspelling identifier's performance, suggesting that word-external context is less relevant for identifying spelling errors.
  • Portability Potential: The system's reliance on relatively few linguistic resources (a corpus, a spell checker, and a POS tagger) suggests it could be portable to new domains and languages.

Key Results

  • Name Identifier: Achieved 86.5% precision and 92.9% recall, a significant improvement over a baseline that assumes all unknown words are names (70.4% precision, 0% recall).
  • Misspelling Identifier: Achieved 77.1% precision and 73.8% recall, outperforming the baseline (70.4% precision, 0% recall).
  • Combined System: The overall unknown word categorizer achieved 86% precision and 89.9% recall on the task of identifying names and misspellings.
  • Decision Maker Behavior: In cases where both components made positive predictions, the decision-maker favored the name prediction, likely due to the name identifier's higher confidence scores. This also led to a higher error rate where misspellings were misclassified as names.

Limitations and Future Work

  • Error Analysis: The authors identified specific types of misspellings that the current system struggles with, such as those involving syllable additions/deletions or phonetic similarities to intended words. They suggest incorporating features to address these.
  • Foreign Words: Foreign words with unusual character sequences were sometimes misclassified as misspellings.
  • Decision-Making Refinement: While the confidence-based tie-breaker worked reasonably well, the authors plan to experiment with alternative decision-making processes.
  • Expanding Categories: The current system only handles names and misspellings. Future work will focus on developing components to identify other types of unknown words, such as abbreviations and morphological variants.
  • Portability to Other Languages: While the approach is designed to be portable, specific features might need adaptation for languages with different writing systems (e.g., ideographic languages).

Summary updated

BibTeX
@inproceedings{toole2000categorizing,
  author = {Janine Toole},
  title = {{Categorizing Unknown Words: Using Decision Trees to Identify Names and Misspellings}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2000},
}
Figure