Ending-based Strategies for Part-of-Speech Tagging

Greg Adams, Beth Millar, Eric Neufeld, Tim PhilipUAI 1994

TL;DR

This paper explores a novel approach to part-of-speech (POS) tagging by prioritizing word endings over whole-word statistics, particularly for unknown words. Surprisingly, this "ending-first" strategy, when optimized, not only matches but can even outperform traditional whole-word methods, achieving a remarkable 97.5% accuracy. This suggests that focusing on word structure can be a highly effective, and perhaps more efficient, way to handle linguistic ambiguity.

What Problem Does This Paper Address?

Natural Language Processing (NLP) tasks like POS tagging, which assign grammatical categories to words, often rely on statistical models trained on large corpora. While effective for known words, these models struggle with "unseen" or "unknown" words – those not present in the training data. This is a significant problem, as even large corpora can leave a notable percentage of words untagged. Traditional approaches to this issue involve secondary strategies that exploit word features like capitalization or punctuation. This paper tackles the challenge of improving POS tagging accuracy, especially for unknown words, by investigating a less common primary strategy: using word endings.

Methods

The core of this work lies in a shift from the standard whole-word statistics-first approach to an "ending-based" strategy. The authors trained a Hidden Markov Model (HMM) tagger using word endings as the primary source of information, with whole-word statistics acting as a secondary component.

Key methodological aspects include:

  • Primary Strategy: Word Endings: The tagger was initially trained and tested solely on word endings of varying lengths (2, 3, and 4 letters).
  • Secondary Strategy: Whole-Word Statistics: Subsequently, whole-word statistics for the N most frequent words in the training corpus were incrementally added back into the model.
  • Effective Tag-List (ETL): The paper explores different strategies for defining the set of possible tags for a given word or word ending. "Unit ETL" uses the original word's tag assignments, while "Relexed ETL" derives tag assignments from word endings.
  • Probability Estimation: The authors experimented with different methods for estimating probabilities, including maximum likelihood and the Good-Turing estimator, to handle unseen tag sequences.

Datasets

The primary dataset used in this research is the LOB Corpus. This corpus, containing approximately 500 text samples of about 2000 words each, is annotated with POS tags. The authors utilized subsets of this corpus for training and testing, with specific experiments involving training on up to 900,000 tokens and testing on a 100,000 token subset.

Key Insights and Ideas

  • Word Endings as a Powerful Primary Strategy: The most striking insight is that an ending-based strategy, when used as the primary method, can achieve performance comparable to, and in some cases superior to, traditional whole-word statistical methods. This challenges the conventional wisdom that whole-word statistics are paramount.
  • The "Too Much Information" Paradox: Counterintuitively, adding too much whole-word statistical information (i.e., a very large N) can degrade performance. This suggests that beyond a certain point, the statistics for less frequent words become unreliable due to small sample sizes, leading to errors.
  • "Relexed" vs. "Unit" ETL: The "Unit ETL" strategy, which retains original word-based tag assignments for truncated words, generally outperformed the "Relexed ETL" strategy, which derives tag assignments solely from endings. This highlights the value of preserving some original word-level information.
  • Good-Turing Estimation Offers Marginal Gains: While not a dramatic improvement, the Good-Turing estimator consistently provided a slight edge in performance over the simpler "add-one" strategy.

Key Results

The paper reports several significant findings:

  • Strong Baseline Performance: An ending-based tagger (L=3) alone achieved a success rate of 94.4%, which was competitive with existing whole-word taggers.
  • Optimal N and "Negative Returns": Performance generally improved as more frequent words (N) were added back, but only up to a point (around N=30,000). Beyond this, performance began to decline, demonstrating the "negative returns" phenomenon.
  • Outperforming Whole-Word Taggers: In the best-case scenario, using a 2-letter ending strategy with the "Unit ETL + GT" approach and N=30,000, the tagger achieved a success rate of 97.5%. This is a notable achievement, especially for a strategy that prioritizes endings and handles unseen words without external knowledge.
  • Practicality of High Accuracy: The authors argue that for practical applications like grammar checking, a 99% success rate is desirable. Their findings show consistent reductions in error rates, moving towards this goal.

Limitations and Future Work

  • "Slippery Slope" of Parameters: The authors acknowledge that there are no universally "correct" values for word-ending length (L) and the number of frequent words (N). Performance is highly dependent on the quality of the statistics used, suggesting a complex interplay between these parameters.
  • Morphological vs. Syntactic Knowledge: While the paper focuses on syntactic approaches, the authors note that word endings might implicitly incorporate some morphological information. They suggest that exploring prefixes or other word parts could yield different results.
  • Future Directions: The paper proposes further research into quantifying the relationships between different strategies to find a unifying principle for tagger construction. They are also investigating mixed strategies and applying them to grammar checkers. The ongoing "Sound Probabilistic Reasoning Project" at the University of Saskatchewan continues to explore purely syntactic approaches.

Summary updated

BibTeX
@inproceedings{adams1994ending,
  author = {Greg Adams and Beth Millar and Eric Neufeld and Tim Philip},
  title = {{Ending-based Strategies for Part-of-Speech Tagging}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure