Elamur Research
☰
home / papers / 1994 / Tagging English Text with a Probabilistic Model

Tagging English Text with a Probabilistic Model

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/J94-2001.pdf

Summary

The paper asks how to estimate the parameters of a probabilistic part-of-speech tagger for English, and in particular whether untagged text can help. Merialdo uses a triclass (tri-POS) hidden Markov model, where each tag depends on the two preceding tags and each word depends only on its own tag. A dictionary restricts which tags each word may take. Two estimation methods are compared and combined. The first, Relative Frequency (RF) training, counts events in hand-tagged text and smooths the counts by deleted interpolation. The second, Maximum Likelihood (ML) training, runs Forward-Backward (Baum-Welch) iterations over untagged text. Two decoding schemes are also compared: Viterbi tagging and per-word ML tagging.

The best accuracy came from RF estimates built on as much hand-annotated data as possible. Forward-Backward re-estimation raises the likelihood of the data but generally lowers tagging accuracy. It helps only when the starting model was trained on very little tagged text. The two decoding methods performed almost identically. These findings matter because they show that likelihood is not a reliable stand-in for tagging quality. The author therefore recommends checking accuracy on held-out tagged data during re-estimation and stopping early.

Key points

  • With RF training and Viterbi decoding on a 45,583-word test set, accuracy grows with the amount of tagged data. It is 77.0% with no tagged sentences, 90.0% with 100 sentences and 97.0% with all the training data (1,365 errors).
  • Starting from the full RF model, ten Forward-Backward iterations steadily lower accuracy, from 97.01% to 95.21%.
  • Viterbi and per-word ML tagging differ by only a handful of errors at every iteration. The choice of decoder matters far less than the kind of training data.
  • Constrained ML training slows the decline in accuracy but does not reverse it:
    • The tw-constraint fixes p(t/w) for the 1,000 most frequent words and ends at 96.09% after 10 iterations, versus 95.21% for standard ML.
    • The t-constraint keeps p(t) fixed and was tested only on a biclass model, ending at 95.30% versus 95.18%.
  • The recommended recipe has three steps:
    1. Build an initial model M0 from relative frequencies on hand-tagged text.
    2. Re-estimate it on untagged text with Forward-Backward.
    3. Stop when accuracy on held-out tagged data drops or when an iteration limit is reached.

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

Cited by

132 papers of our library cite it (of the 140673 whose bibliographies we read); 3 of them have a page here, 129 not yet.

Cite

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

@article{merialdo1994tagging,
  title = {{Tagging English Text with a Probabilistic Model}},
  author = {Merialdo, Bernard},
  journal = {Computational Linguistics},
  year = {1994},
  url = {https://aclanthology.org/J94-2001/}
}

References

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

  1. Bahl, Lalit R., and Mercer, Robert L. (1976). "Part of speech assignment by a statistical decision algorithm." In IEEE International Symposium on Information Theory, 88-89. Ronneby. find
  2. Bahl, Lalit R.; Jelinek, Frederick and Mercer, Robert L. (1983). "A maximum likelihood approach to continuous speech recognition," In IEEE Transactions on PAML 5(2), 179-190. find
  3. Baum, L. E., and Eagon, J. A. (1967). "An inequality with application to statistical estimation for probabilistic functions of Markov processes and to a model for ecology." Bulletin of the American Mathematicians Society, 73, 360-363. find
  4. Beale, A. D. (1985). "A probabilistic approach to grammatical analysis of written English by computer." In Proceedings, Second Conference of the European Chapter of the ACL, Geneva, Switzerland, 159-165. find
  5. Beale, A. D. (1988). "Lexicon and grammar in probabilistic tagging of written English." In Proceedings, 26th Annual Meeting of the Association for Computational Linguistics, Buffalo NY: 211-216. find our card
  6. Bellman, R. E. (1957). Dynamic Programming. Princeton University Press. find
  7. Benello, J.; Mackie, A. W.; and Anderson, J. A. (1989). "Syntactic category disambiguation with neural networks." Computer Speech and Language, 3, 203-217. find
  8. Brill, E.; Magerman, D.; Marcus, M.; and Santorini, B. (1990). "Deducing linguistic structure from the statistics of large corpora." In Proceedings, DARPA Speech and Natural Language Workshop, Hidden Valley PA. 275-282. find
  9. Brodda, Benny (1982). "Problems with tagging and a solution." Nordic Journal of Linguistics, 93-116. find
  10. Church, Kenneth W. (1989). "A stochastic parts program noun phrase parser for unrestricted text." In IEEE Proceedings of the ICASSP, Glasgow, 695-698. find
  11. Codogno, M.; Fissore, L.; Martelli, A.; Pirani, G.; and Volpi, G. (1987). "Experimental evaluation of Italian language models for large-dictionary speech recognition." In Proceedings, European Conference on Speech Technology, Edinburgh, 159-162. find
  12. Cutting, D.; Kupiec, J.; Pedersen, J.; and Sibun, P. (1992). "A practical part-of-speech tagger." In Proceedings, Third Conference on Applied Language Processing, Trento, Italy, 133-140. find
  13. Debili, Fathi (1977). "Traitements syntaxiques utilisant des matrices de precedence frequentielles construites automatiquement par apprentissage." Doctoral dissertation, Engineering Department, Universite Paris 7, France. find
  14. DeRose, S. (1988). "Grammatical category disambiguation by statistical optimization." Computational Linguistics, 14(1), 31-39. find
  15. Derouault, Anne-Marie, and Merialdo, Bernard (1986). "Natural language modeling for phoneme-to-text transcription." In IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6), 742-749. find
  16. Garside, R., and Leech, F. (1985). "A probabilistic parser." In Proceedings, Second Conference of the European Chapter of the ACL, Geneva, Switzerland, 166-170. find
  17. Jelinek, Frederick (1976). "Continuous speech recognition by statistical methods." In Proceedings of the IEEE, 64, 532-556. Jelinek, Frederick, and Mercer, Robert L. find
  18. (1980). "Interpolated estimation of Markov source parameters from sparse data." In Proceedings, Workshop on Pattern Recognition in Practice, Amsterdam, 381-397. find
  19. Katz, S. (1987). "Estimation of probabilities from sparse data for the language model component of a speech recognizer." IEEE Transactions on ASSP, 34(3), 400-401. find
  20. Klein, S., and Simmons, R. E (1963). "A grammatical approach to grammatical coding of English words." JACM, 10, 334-347. find
  21. Leech, G.; Garside, R.; and Atwell, E. (1983). "The automatic grammatical tagging of the LOB corpus." Newsletter of the International Computer Archive of Modern English, 7, 13-33. find
  22. de Marcken, C. G. (1990). "Parsing the LOB corpus." In Proceedings, ACL Annual Meeting, Pittsburg PA, 243-251. find
  23. Marshall, Ian (1983). "Choice of grammatical word-class without global syntactic analysis: Tagging words in the LOB corpus." Computers and the Humanities, 139-150. find
  24. Merialdo, Bernard (1991). "Tagging text with a probabilistic model." In IEEE Proceedings of the ICASSP, Toronto, 809-812. find
  25. Nakamura, M., and Shikano, K. (1989). "A study of English word category prediction based on neural networks." In IEEE Proceedings of the ICASSP, Glasgow, 731-734. find
  26. Paulussen, H., and Martin, W. (1992). "Dilemma-2: A lemmatizer-tagger for medical abstracts." In Proceedings, Third Conference on Applied Language Processing, Trento, Italy, 141-146. find
  27. Poritz, Alan B. (1988). "Hidden Markov models: A guided tour." In IEEE Proceedings of the ICASSP, New York, 7-13. find
  28. Stolz, W. S.; Tannenbaum, P. H.; and Carstensen F. V. (1965). "A stochastic approach to the grammatical coding of English." Communications of the ACM, 8, 399-405. find