Elamur Research⌕
☰
home / papers / 1996 / MBT: A Memory-Based Part of Speech Tagger-Generator

MBT: A Memory-Based Part of Speech Tagger-Generator

Summary

The paper presents MBT, a system that learns a part-of-speech tagger from an annotated corpus by storing tagged examples rather than estimating a probabilistic model. Each example pairs a word, or its ambiguous tag representation, and its neighbouring context with the correct tag. A new word is tagged by finding the most similar stored examples. Similarity is a feature-overlap measure in which each feature is weighted by its information gain (IB-IG), so the focus word counts more than distant context. Plain nearest-neighbour search is too slow for large memories, so the authors use IGTree. IGTree compresses the case base into a decision tree with a fixed feature order and stores only the feature values needed to separate the classes. Trained on millions of cases, the tagger matches the accuracy of established statistical taggers. Training and tagging are fast, and unknown words are handled reasonably well without morphological analysis. The work shows that lazy, example-based learning can scale to realistic NLP tasks while remaining incremental and explainable.

Key points

  • The authors describe three algorithms:
    • IB1 uses unweighted overlap distance and keeps class distributions for ambiguous patterns.
    • IB-IG adds information-gain feature weights.
    • IGTree is a heuristic, compressed approximation of IB-IG, structured as an oblivious decision tree with default classes at inner nodes and pruning of redundant leaves.
  • Unoptimised memory-based retrieval costs O(NF), where N is the number of stored cases and F the number of features. IGTree lookup time does not depend on the number of stored cases, and tagging runs at about 1000 words per second.
  • Good performance is already reached with 300–400K tagged words. The main experiments use a case base of about 3 million cases.
  • On the WSJ corpus, more than 90% of unknown words are tagged correctly using context and word-form features.
  • The paper compares MBT with Cardie's case-based tagger, which reached 95% overall and 89.1% on unknown words on 120 TIPSTER JV sentences. MBT differs in three ways: it weights features instead of selecting them, it is evaluated on a much larger corpus, and it uses IGTree indexing.

Interesting ideas

  • I1. Information gain as feature weights. Scoring each feature by how much it reduces class entropy gives a cheap, automatic way to combine heterogeneous cues such as word form, left context and right context. This could suit low-resource taggers or classifiers for Ukrainian, where hand-tuning feature importance is costly.
  • I2. Storing only disambiguating feature values. IGTree keeps a path only until the example's class is unique, so the context size adapts per case. This is a useful pattern wherever some decisions need little context and others need more.
  • I3. Default classes at inner nodes as built-in backoff. When a feature value is unseen, the tree falls back to the most frequent class at the last matching node. This replaces explicit smoothing for rare contexts and could work for any sparse symbolic classification task.
  • I4. Incremental learning from corrections. New cases, such as tagger output fixed by an annotator, can be added without retraining a probabilistic model. This fits an active, human-in-the-loop annotation workflow for building a corpus.
  • I5. Explanations through the decision path. The matched tree path and the nearest stored examples serve as a human-readable justification for each tag. This helps with error analysis and with checking annotation consistency.

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

TopicsPart-of-speech tagging

Institutions

🎓Tilburg UniversityTilburg · Netherlands30 works · 5,198 citations🎓University of AntwerpAntwerp · Belgium5 works · 1,220 citations

Cite

Cite as Walter Daelemans, Jakub Zavrel, Peter Berck and Steven Gillis. 1996. MBT: A Memory-Based Part of Speech Tagger-Generator. Fourth Workshop on Very Large Corpora.

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

@inproceedings{daelemans1996mbt,
  title = {{MBT: A Memory-Based Part of Speech Tagger-Generator}},
  author = {Walter Daelemans, Jakub Zavrel, Peter Berck and Steven Gillis},
  booktitle = {Fourth Workshop on Very Large Corpora},
  year = {1996},
  url = {https://aclanthology.org/W96-0102/}
}

References

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

  1. Aha, D. W., Kibler, D., & Albert, M. (1991). 'Instance-based learning algorithms'. Machine Learning, 7, 37-66. our card
  2. Brill, E. (1992) 'A simple rule-based part-of-speech tagger'. Proceedings Third ACL Applied, Trento, Italy, 152-155. our card
  3. Cardie, C. (1993a). 'A case-based approach to knowledge acquisition for domain-specific sentence analysis'. In AAAL93, 798-803. find
  4. Cardie, C. (1993b). 'Using Decision Trees to Improve Case-Based Learning'. In Proceedings of the Tenth International Conference on Machine Learning, 25-32. find
  5. Cardie, C. (1994). 'Domain-Specific Knowledge Acquisition for Conceptual Sentence Analysis'. Ph.D. Thesis, University of Massachusetts, Amherst, MA. find
  6. Chandler, S. (1992). 'Are rules and modules really necessary for explaining language?' Journal of Psycholinguistic research, 22(6): 593-606. find
  7. Church, K. (1988). 'A stochastic parts program and noun phrase parser for unrestricted text'. Proceedings Second A CL Applied NLP, Austin, Texas, 136-143. our card
  8. Cost, S. and Salzberg, S. (1993). 'A weighted nearest neighbour algorithm for learning with symbolic features.' Machine Learning, 10, 57-78. find
  9. Cutting, D., Kupiec, J., Pederson, J., Sibun, P. (1992). A practical part of speech tagger. Proceedings Third A CL Applied NLP, Trento, Italy, 133-140. our card
  10. Daelemans, W. (1995). 'Memory-based lexical acquisition and processing.' In Steffens, P., editor, Machine Translation and the Lexicon, Lecture Notes in Artificial Intelligence 898. Berlin: Springer, 85-98. find
  11. Daelemans, W., Van den Bosch, A. (1992). 'Generalisation performance of backpropagation learning on a syllabification task.' In M. Drossaers & A. Nijholt (Eds.), TWLT3: Connectionism and Natural Language Processing. Enschede: Twente University, 27-38. find
  12. Daelemans, W., Van den Bosch, A., Weijters, T. (1996). 'IGTree: Using Trees for Compression and Classification in Lazy Learning Algorithms.' In Aha, D. (ed.). AI Review Special Issue on Lazy Learning, forthcoming. our card
  13. DeRose, S. (1988). 'Grammatical category disambiguation by statistical optimization. ' Computational Linguistics 14, 31-39. find
  14. Derwing, B. L. and Skousen, R. (1989). 'Real Time Morphology: Symbolic Rules or Analogical Networks'. Berkeley Linguistic Society 15: 48-62. find
  15. Federici S. and V. Pirelli. (1996). 'Analogy, Computation and Linguistic Theory.' In Jones, D. (ed.) New Methods in Language Processing. London: UCL Press, forthcoming. find
  16. Garside, R., Leech, G. and Sampson, G. (1987). The computational analysis of English: A corpus-based approach, London: Longman, 1987. find
  17. Greene, B.B. and l~ubin, G.M. (1971). Automatic Grammatical Tagging of English. Providence RI: Department of Linguistics, Brown University. find
  18. Hindle, Donald. (1989). 'Acquiring disambiguation rules from text.' In Proceedings, 27th Annual Meeting of the Association for Computational Linguistics, Vancouver, BC. find
  19. Hunt, E., J. Matin, P. Stone. (1966). Experiments in Induction. New York: Academic Press. find
  20. Jones, D. Analogical Natural Language Processing. London: UCL Press, 1996. find
  21. Klein S. and Simmons, R. (1963). 'A grammatical approach to grammatical coding of English words.' JACM 10, 334-347. find
  22. Kolodner, J. (1993). Case-Based Reasoning. San Mateo: Morgan Kaufmann. find
  23. Langley, P. and Sage, S. (1994). 'Oblivious decision trees and abstract cases.' In D. W. Aha (Ed.), Case-Based Reasoning: Papers from the 1994 Workshop (Technical Report WS-94-01). Menlo Park, CA: AAAI Press. find
  24. Merialdo, B. (1994). 'Tagging English Text with a Probabilistic Model.' Computational Linguistics 20 (2), 155-172. our card
  25. Pereira, F., Y. Singer, N. Tishby. (1995). 'Beyond Word N-grams.' Proceedings Third Workshop on Very Large Corpora, MIT, Cambridge Mass., 95-106. find
  26. Quinlan, J. (1993). C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann. our card
  27. Salzberg, S. (1990) 'A nearest hyperrectangle learning method'. Machine Learning 6, 251-276. find
  28. Samuelsson, C. (1994) 'Morphological Tagging Based Entirely on Bayesian Inference.' In Proceedings of the 9th Nordic Conference on Computational Linguistics, Stockholm University, Sweden, 1994. find
  29. Scha, R. (1992) 'Virtuele Grammatica's en Creatieve Algoritmen.' Gramma/TTT 1 (1), 57-77. find
  30. Schmid, H. (1994) 'Part-of-speech tagging with neural networks.' In Proceedings of COLING, Kyoto, Japan. find
  31. Schfitze, H., and Y. Singer. (1994) 'Part-of-speech Tagging Using a Variable Context Markov Model' Proceedings of ACL 1994, Las Cruces, New Mexico. find
  32. Skousen, R. (1989). Analogical Modeling of Language. Dordrecht: Kluwer. find
  33. Sejnowski, T. J., Rosenberg, C. S. (1987). Parallel networks that learn to pronounce English text. Complex Systems, 1, 145-168. find
  34. Stanfill, C. and Waltz, D. (1986). 'Toward memory-based reasoning.' Communications of the ACM, 29, 1212-1228. find
  35. Weiss, S. and Kulikowski, C. (1991). Computer systems that learn. San-Mateo: Morgan Kaufmann. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/daelemans-1996-mbt-memory-based-part-speech/