Elamur Research
☰
home / papers / 1995 / Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part-of-Speech Tagging

Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part-of-Speech Tagging

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/J95-4004.pdf

Summary

Corpus-based NLP methods, such as stochastic n-gram taggers, reach high accuracy, but they store what they learn in huge tables of probabilities. That makes the learned knowledge hard to inspect or improve. Brill proposes transformation-based error-driven learning, a rule-based alternative whose learned knowledge stays compact and readable. First, an initial-state annotator labels raw text. This can be as simple as tagging every word as a noun or with its most frequent training tag, or as complex as a stochastic tagger's output. The result is compared against a manually annotated reference corpus, such as the Penn Treebank. A greedy loop then repeatedly selects the transformation that most improves an objective function (e.g., error count) and applies it to the training data. It stops when no transformation helps. New text receives the initial annotation, followed by the learned rules in order. The paper also proves that transformation lists are strictly more expressive than decision trees built from the same primitive queries. Part-of-speech tagging is the main case study. Its quantitative evaluation is in the part of the text missing from the supplied extract, so no accuracy figures are given here.

Key points

  • A transformation combines a rewrite rule with a triggering environment. For example, retagging a modal as a noun when the preceding word is a determiner fixes "can" in "The can rusted."
  • An application of the method must specify three things: the initial-state annotator, the space of allowed transformations, and the objective function. When rules can interact, it must also fix the processing order and whether changes take effect immediately or after a full pass. On the string AAAAAA, these choices yield either ABBBBB or ABABAB.
  • In the paper's toy example, the initial annotation contains 5,100 errors. Transformation T2 is learned first, then T3, and learning stops at 1,231 errors.
  • An inductive proof over binary trees shows that any decision tree can be rewritten as a transformation list, but not the reverse.
  • Besides tagging, the method has been applied to prepositional phrase attachment and syntactic parsing. Work on letter-to-sound generation and pronunciation networks for speech recognition is under way.

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

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

Cite

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

@article{brill1995transformation,
  title = {{Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part-of-Speech Tagging}},
  author = {Brill, Eric},
  journal = {Computational Linguistics},
  year = {1995},
  url = {https://aclanthology.org/J95-4004/}
}

References

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

  1. Black, Ezra; Jelinek, Fred; Lafferty, John; Magerman, David; Mercer, Robert; and Roukos, Salim (1993). "Towards history-based grammars: Using richer models for probabilistic parsing." In Proceedings, 31st Annual Meeting of the Association for Computational Linguistics. Columbus, OH. find
  2. Black, Ezra; Jelinek, Fred; Lafferty, John; Mercer, Robert, and Roukos, Salim (1992). "Decision tree models applied to the labeling of text with parts-of-speech." In Darpa Workshop on Speech and Natural Language. Harriman, NY. find
  3. Breiman, Leo; Friedman, Jerome; Olshen, Richard; and Stone, Charles (1984). Classification and regression trees. Wadsworth and Brooks. find
  4. Brill, Eric (1992). "A simple rule-based part of speech tagger." In Proceedings, Third Conference on Applied Natural Language Processing, ACL, Trento, Italy. find
  5. Brill, Eric (1993a). "Automatic grammar induction and parsing free text: A transformation-based approach." In Proceedings, 31st Meeting of the Association of Computational Linguistics, Columbus, OH. find
  6. Brill, Eric (1993b). A Corpus-Based Approach to Language Learning. Doctoral dissertation, Department of Computer and Information Science, University of Pennsylvania. find
  7. Brill, Eric (1993c). "Transformation-based error-driven parsing." In Proceedings, Third International Workshop on Parsing Technologies, Tilburg, The Netherlands. find
  8. Brill, Eric (1994). "Some advances in rule-based part of speech tagging." In Proceedings, Twelfth National Conference on Artificial Intelligence (AAAI-94), Seattle, WA. find
  9. Brill, Eric and Resnik, Philip (1994). "A transformation-based approach to prepositional phrase attachment disambiguation." In Proceedings, Fifteenth International Conference on Computational Linguistics (COLING-1994), Kyoto, Japan. find
  10. Brown, Peter; Cocke, John; Della Pietra, Stephen; Della Pietra, Vincent; Jelinek, Fred; Lafferty, John; Mercer, Robert; and Roossin, Paul (1990). "A statistical approach to machine translation." Computational Linguistics, 16(2). find
  11. Brown, Peter; Lai, Jennifer; and Mercer, Robert (1991). "Word-sense disambiguation using statistical methods." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, CA Bruce, Rebecca and Wiebe, Janyce (1994). "Word-sense disambiguation using decomposable mod… find
  12. Church, Kenneth (1988). "A stochastic parts program and noun phrase parser for unrestricted text." In Proceedings, Second Conference on Applied Natural Language Processing, ACL, Austin, TX. find
  13. Cutting, Doug; Kupiec, Julian; Pedersen, Jan; and Sibun, Penelope (1992). "A practical part-of-speech tagger." In Proceedings, Third Conference on Applied Natural Language Processing, ACL, Trento, Italy. find
  14. DeMarcken, Carl (1990). "Parsing the lob corpus." In Proceedings, 1990 Conference of the Association for Computational Linguistics, Pittsburgh, PA. find
  15. Derose, Stephen (1988). "Grammatical category disambiguation by statistical optimization." Computational Linguistics, 14. find
  16. Francis, Winthrop Nelson and Kucera, Henry (1982). Frequency analysis of English usage: Lexicon and grammar. Houghton Mifflin, Boston. find
  17. Fujisaki, Tetsu; Jelinek, Fred; Cocke, John; and Black, Ezra (1989). "Probabilistic parsing method for sentence disambiguation." In Proceedings, International Workshop on Parsing Technologies, Carnegie Mellon University, Pittsburgh, PA. find
  18. Gale, William and Church, Kenneth (1991). "A program for aligning sentences in bilingual corpora." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, Berkeley, CA. find our card
  19. Gale, William; Church, Kenneth; and Yarowsky, David (1992). "A method for disambiguating word senses in a large corpus." Computers and the Humanities. find
  20. Leech, Geoffrey; Garside, Roger; and Bryant, Michael (1994). "Claws4: The tagging of the British National Corpus." In Proceedings, 15th International Conference on Computational Linguistics, Kyoto, Japan. find
  21. Harris, Zellig (1962). String Analysis of Language Structure. Mouton and Co., The Hague. find
  22. Hindle, Donald (1989). "Acquiring disambiguation rules from text." In Proceedings, 27th Annual Meeting of the Association for Computational Linguistics, Vancouver, BC. find
  23. Hindle, D. and Rooth, M. (1993). "Structural ambiguity and lexical relations." Computational Linguistics, 19(1):103-120. find
  24. Huang, Caroline; Son-Bell, Mark; and Baggett, David (1994). "Generation of pronunciations from orthographies using transformation-based error-driven learning." In International Conference on Speech and Language Processing (ICSLP), Yokohama, Japan. find
  25. Jelinek, Fred (1985). Self-Organized Language Modelling for Speech Recognition. Dordrecht. In Impact of Processing Techniques on Communication, J. Skwirzinski, ed. find
  26. Joshi, Aravind and Srinivas, B. (1994). "Disambiguation of super parts of speech (or supertags): Almost parsing." In Proceedings, 15th International Conference on Computational Linguistics, Kyoto, Japan. find
  27. Klein, Sheldon and Simmons, Robert (1963). "A computational approach to grammatical coding of English words." ]ACM, 10. find
  28. Kupiec, Julian (1992). "Robust part-of-speech tagging using a hidden Markov model." Computer Speech and Language, 6. find
  29. Marcus, Mitchell; Santorini, Beatrice; and Marcinkiewicz, Maryann (1993). "Building a large annotated corpus of English: the Penn Treebank." Computational Linguistics, 19(2). find our card
  30. Merialdo, Bernard (1994). "Tagging English text with a probabilistic model." Computational Linguistics. find our card
  31. Miller, George (1990). "Wordnet: an on-line lexical database." International Journal of Lexicography, 3(4). find
  32. Quinlan, J. Ross (1986). "Induction of decision trees." Machine Learning, 1:81-106. find
  33. Quinlan, J. Ross and Rivest, Ronald (1989). "Inferring decision trees using the minimum description length principle." Information and Computation, 80. find
  34. Ramshaw, Lance and Marcus, Mitchell (1994). "Exploring the statistical derivation of transformational rule sequences for part-of-speech tagging." In The Balancing Act: Proceedings of the ACL Workshop on Combining Symbolic and Statistical Approaches to Language, New Mexico State University, July. find
  35. Roche, Emmanuel and Schabes, Yves (1995). "Deterministic part of speech tagging with finite state transducers." Computational Linguistics, 21(2), 227-253. find
  36. Schutze, Hinrich and Singer, Yoram (1994). Part of speech tagging using a variable memory Markov model. In Proceedings, Association for Computational Linguistics, Las Cruces, NM. find
  37. Sharman, Robert; Jelinek, Fred; and Mercer, Robert (1990). "Generating a grammar for statistical training." In Proceedings, 1990 find
  38. Darpa Speech and Natural Language Workshop. find
  39. Weischedel, Ralph; Meteer, Marie; Schwartz, Richard; Ramshaw, Lance; and Palmucci, Jeff (1993). "Coping with ambiguity and unknown words through probabilistic models." Computational Linguistics. find
  40. Yarowsky, David (1992). "Word-sense disambiguation using statistical models of Roget's categories trained on large corpora." In Proceedings of COLING-92, pages 454-460, Nantes, France, July. find