Elamur Research⌕
☰
home / papers / 1992 / A Practical Part-of-Speech Tagger

A Practical Part-of-Speech Tagger

Summary

The paper addresses a practical engineering question: how to build a part-of-speech tagger that holds up on messy real-world corpora, runs fast, and can be moved to a new tagset, domain or language cheaply. The Xerox PARC authors implement a first-order hidden Markov model trained with Baum-Welch on unlabeled text. The only inputs are a lexicon and raw text, so no hand-tagged corpus is needed. Words are grouped into ambiguity classes, meaning the set of tags each word allows. Only frequent words keep their own parameters. Unknown words are handled by suffix-based guessing, with a default open-class fallback. Implementation work covers numerical scaling, log-space Viterbi decoding and trie-based lookup, which keep tagging linear in text length. Accuracy is above 96%. The tagger then feeds three shallow-analysis systems: phrase recognition, noun sense disambiguation and grammatical function labeling. Its importance lies in showing that a competitive tagger can come from cheap resources, which matters most for languages and domains without treebanks.

Key points

  • The model is a first-order HMM, estimated with the forward-backward (Baum-Welch) algorithm and decoded with Viterbi. Training needs only a lexicon plus untagged text, and accuracy exceeds 96%.
  • Ambiguity classes shrink the roughly 50,000-word Brown corpus vocabulary to about 400 classes. Reasonable results came from training on as few as 3,000 sentences.
  • The lexicon works in three stages: a hand-built lexicon for frequent words, then suffix-based class prediction for unknown words, then a default class containing all open-class tags. Both dictionaries and suffix tables are stored as tries.
  • Rescaling the forward and backward probabilities and running Viterbi on log probabilities prevent numerical underflow. Unseen tag sequences get small non-zero probabilities, so any input can still be tagged.
  • Downstream results:
    • Hearst's CatchWord noun homograph disambiguator reached about 90% on nouns with clearly distinct senses.
    • The Sopa grammatical function assigner (Subject/Object/Predicative) reached about 80%.

Interesting ideas

  • I1. Pooling rare words by ambiguity class. Rare words share statistics with other words that have the same tag set, so far less data is needed. New lexicon entries usually fit an existing class and need no retraining. This could help any low-resource sequence labeling task, for example Ukrainian morphology with rich tag sets.
  • I2. Separating the tagset from the training data. Since training uses raw text, switching to a different or specialized tagset only requires changing the lexicon. This makes experimenting with tagset designs cheap.
  • I3. A layered fallback for unknown words. Lookup goes from an exact dictionary, to suffix heuristics, to a broad default class. The result degrades gracefully instead of failing, which suits noisy or out-of-domain corpora.
  • I4. Favoring precision in downstream chunking. The phrase recognizer accepts only simple, contiguous tag patterns and takes the longest match. It may miss parts of some phrases but rarely produces false positives, so later stages such as argument labeling can trust what it outputs.
  • I5. Explicit practical requirements as design criteria. Robustness, efficiency, accuracy, tunability and reusability are stated up front and guide every design choice. This is a useful checklist when building NLP components meant for production pipelines rather than benchmarks.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Part-of-speech tagging

Cited by

131 papers of our library cite it (of the 140884 whose bibliographies we read); 13 of them have a page here, 118 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/974499.974523

@inproceedings{cutting1992practical,
  title = {{A Practical Part-of-Speech Tagger}},
  author = {Cutting, Doug and Kupiec, Julian and Pedersen, Jan and Sibun, Penelope},
  booktitle = {Third Conference on Applied Natural Language Processing},
  year = {1992},
  doi = {10.3115/974499.974523},
  url = {https://doi.org/10.3115/974499.974523}
}

References

26 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, 1986. find
  2. L. E. Baum. An inequality and associated maximization technique in statistical estimation for probabilistic functions of a Markov process. Inequalities, 3:1-8, 1972. find
  3. K. W. Church. A stochastic parts program and noun phrase parser for unrestricted text. In Proceedings of the Second Conference on Applied Natural Language Processing (ACL), pages 136-143, 1988. find our card
  4. D.R. Cutting, J. Pedersen, and P.-K. Halvorsen. An object-oriented architecture for text retrieval. In Conference Proceedings of R[AO'91, Intelligent Text and Image Handling, Barcelona, Spain, pages 285-298, April 1991. find
  5. S. DeRose. Grammatical category disambiguation by statistical optimization. Computational Linguistics, 14:31-39, 1988. find
  6. A. M. Derouault and B. Merialdo. Natural language modeling for phoneme-to-text transcription. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8:742-749, 1986. find
  7. W. N. Francis and F. Ku~era. Frequency Analysis of English Usage. Houghton Mifflin, 1982. find
  8. R. Garside, G. Leech, and G. Sampson. The Computational Analysis of English. Long.man, 1987. find
  9. B. B. Greene and G. M. Rubin. Automatic grammatical tagging of English. Technical report, Department of Linguistics, Brown University, Providence, Rhode Island, 1971. find
  10. M. A. Hearst. Noun homograph disambiguation using local context in large text corpora. In The Proceedings of the 7th New OED Conference on Using Corpora, pages 1-22, Oxford, 1991. find
  11. F. Jelinek and R. L. Mercer. Interpolated estimation of markov source parameters from sparse data. In Proceedings of the Workshop Pattern Recognition in Practice, pages 381-397, Amsterdam, 1980. North-Holland. find
  12. F. Jelinek. Markov source modeling of text generation. In J. K. Skwirzinski, editor, Impact of Processing Techniques on Communication. Nijhoff, Dordrecht, 1985. find
  13. D. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973. find
  14. K. Koskenniemi. Finte-state parsing and disambiguation. In H. Karlgren, editor, COLING-90, pages 229-232, Helsinki University, 1990. find
  15. J. M. Kupiec. Augmenting a hidden Markov model for phrase-dependent word tagging. In Proceedings of the DARPA Speech and Natural Language Workshop, pages 92-98, Cape Cod, MA, 1989. Morgan Kaufmann. find
  16. J. M. Kupiec. Probabilistic models of short and long distance word dependencies in running text. In Proceedings of the 1989 DARPA Speech and Natural Language Workshop, pages 290-295, Philadelphia, 1989. Morgan Kaufmann. find
  17. J. M. Kupiec. Robust part-of-speech tagging using a hidden markov model, submitted to Computer Speech and Language, 1992. find
  18. M. E. Lesk. LEX - - a lexical analyzer generator. Computing Science Technical Report 39, AT&T Bell Laboratories, Murray Hill, New Jersey, 1975. find
  19. S. E. Levinson, L. R. Rabiner, and M. M. Sondhi. An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition. Bell System Technical • Journal, 62:1035-1074, 1983. find
  20. B. Merialdo. Tagging text with a probablistic model. In Proceedings of ICASSP-91, pages 809-812, Toronto, Canada, 1991. find
  21. M. W. Meteer, R. Schwartz, and R. Weischedel. POST: Using probabilities in language processing. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, pages 960-965, 1991. find
  22. IEEE Task P754. A proposed standard for binary floating-point arithmetic. Computer, 14(3):51-62, March 1981. find
  23. L. R. Rabiner and B. H. Juang. An introduction to hidden markov models. IEEE ASSP Magazine, January 1986. find
  24. P. Sibun. Grammatical function assignment in unrestricted text. internal report, Xerox Palo Alto Research Center, 1991. find
  25. G. L. Steele, Jr. Common Lisp, The Language. Digital Press, second edition, 1990. find
  26. A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimal decoding algorithm. In IEEE Transactions on Information Theory, pages 260-269, April 1967. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/cutting-1992-practical-part-speech-tagger/