Elamur Research
☰
home / papers / 1999 / Supertagging: An Approach to Almost Parsing

Supertagging: An Approach to Almost Parsing

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/J99-2004.pdf

Summary

Bangalore and Joshi tackle robust parsing. Their aim is to keep the precision of linguistically rich lexical descriptions while gaining the coverage of statistical methods. In Lexicalized Tree-Adjoining Grammar (LTAG), each word maps to elementary trees called supertags. A supertag holds exactly the elements the word constrains, so dependencies, including long-distance ones, stay local. Because a word gets a separate supertag for every syntactic environment it can occur in, the number of candidates per word grows sharply. The authors resolve this ambiguity before full parsing, as a tagging step. Their disambiguators use n-gram models of supertag co-occurrence, plus distances between supertags and their dependents, all estimated from a corpus of LTAG parses. The selected supertag sequence is close to a full analysis, an "almost parse," and a light combination step finishes the job. Disambiguation accuracy rises from an earlier 68% to 92%. This makes the method a fast, robust front end that can also handle fragmentary input such as speech.

Key points

  • Supertags combine phrase-structure and dependency information in one representation, and an LTAG derivation tree can be read as an unlabeled dependency tree.
  • Supertag accuracy improves from 68% (Joshi and Srinivas 1994) to 92%, thanks to a larger training corpus and better smoothing.
  • Statistics come from parsed corpora, including the XTAG corpus, which stores derivations with predicate–argument relations.
  • Filtering supertags before parsing makes parsing more efficient. A lightweight dependency analyzer builds on the supertagger's output.
  • The approach is presented as applicable to other lexicalized grammars beyond LTAG.

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

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

Cite

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

@article{bangalore1999supertagging,
  title = {{Supertagging: An Approach to Almost Parsing}},
  author = {Bangalore, Srinivas and Joshi, Aravind K.},
  journal = {Computational Linguistics},
  year = {1999},
  url = {https://aclanthology.org/J99-2004/}
}

References

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

  1. Abne~ Steven. 1990. Rapid incremental parsing with repair. In Proceedings of the 6th New OED Conference: Electronic Text Research, pages 1-9, University of Waterloo, Waterloo, Ontario, Canada. find
  2. Alshawi, Hiyan and David Carter. 1994. Training and scaling preference functions for disambiguation. Computational Linguistics, 20(4):635-648. find
  3. Appelt, D., J. Hobbs, J. Bear, D. J. Israel, and M. Tyson. 1993. FASTUS: A finite-state processor for information extraction from real-world text. In Proceedings oflJCAI-93, Charnbery, France, September. find
  4. Black, Ezra, Fred Jelinek, John Lafferty, David M. Magerman, Robert Mercer, and Salim Roukos. 1993. Towards History-based Grammars: Using Richer Models for Probabilistic Parsing. In Proceedings of the 31st Ann ual Meeting, pages 31-37, Columbus, OH. Association for Computational Linguistics. find
  5. Bod, Rens and Ronald Kaplan. 1998. A probabilistic corpus-driven model for lexical-functional analysis. In Proceedings of COLING-ACL "98: 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Montreal, Quebec, Canada, Aug… find
  6. Brill, Eric. 1993. Automatic grammar induction and parsing free text: A transformation-based approach. In Proceedings of the 31st Annual Meeting, Columbus, OH. Association for Computational Linguistics. find
  7. Chandrasekar, R., Christine Doran, and B. Srinivas. 1996. Motivations and methods for text simplification. In Proceedings of the 16th International Conference on Computational Linguistics (COLING'96), Copenhagen, Denmark, August. find
  8. Chandrasekar, R. and B. Srinivas. 1997a. Automatic induction of rules for text simplification. Knowledge-based Systems, 10:183-190. find
  9. Chandrasekar, R. and B. Srinivas. 1997b. Gleaning information from the web: Using syntax to filter out irrelevant information. In Proceedings of AAA11997 Spring Symposium on NLP on the World Wide Web. find
  10. Chandrasekar, R. and B. Srinivas. 1997c. Using supertags in document filtering: The effect of increased context on information retrieval effectiveness. In Proceedings of Recent Advances in NLP (RANLP) '97, Tzigov Chark, Bulgaria, September. find
  11. Chandrasekar, R. and B. Srinivas. 1997d. Using syntactic information in document filtering: A comparative study of part-of-speech tagging and supertagging. In Proceedings of RIAO'97, Montreal, Quebec, Canada, June. find
  12. Charniak, Eugene. 1997. Statistical parsing with a context-free grammar and word statistics. In Proceedings of the Fourteenth National Conference on Artificial Intelligence AAA/, pages 47-66, Menlo Park, CA. find
  13. Chomsk~ Noam. 1992. A Minimalist Approach to Linguistic Theory. MIT Working Papers in Linguistics, Occasional Papers in Linguistics, No. 1. find
  14. Church, Kenneth Ward. 1988. A stochastic parts program and noun phrase parser for unrestricted text. In 2nd Applied Natural Language Processing Conference, pages 136-143, Austin, TX. find
  15. Collins, Michael. 1996. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Annual Meeting, Santa Cruz, CA. Association for Computational Linguistics. find
  16. Doran, Christine, Dania Egedi, Beth Ann Hockey, B. Srinivas, and Martin Zaidel. 1994. XTAG System--A wide coverage grammar for English. In Proceedings of the 17th International Conference on Computational Linguistics (COLING'94), Kyoto, Japan, August. find
  17. Doran, Christine, Michael Niv, Breckenridge Baldwin, Jeffrey Reynar, and B. Srinivas. 1997. Mother of Perl: A Multi-tier pattern description language. In Proceedings of the International Workshop on Lexically Driven Information Extraction, Frascati, Italy, July. find
  18. Doran, Christine and B. Srinivas. 1994. A wide-coverage CCG parser. In Proceedings oJ: the 3rd TAG+ Conference, Paris, France. find
  19. Fujisaki, T., F. Jelinek, J. Cocke, E. Black and T. Nishino. 1989. A probabilistic parsing method for sentence disambiguation. In Proceedings of the 1st Annual International Workshop of Parsing Technologies, Pittsburgh, PA. find
  20. Gazdar, G., E. Klein, G. Pullum, and I. Sag. 1985. Generalized Phrase Structure Grammar. Harvard University Press, Cambridge, MA. find
  21. Good, I. J. 1953. The population frequenceis of species and the estimation of population parameters. Biometrika 40 (3 and 4), pages 237-264. find
  22. Grishman, Ralph. 1995. Where's the syntax? The New York University MUC-6 System. In Proceedings of the Sixth Message Understanding Conference, Columbia, MD. find
  23. Gross, Maurice. 1984. Lexicon-grammar and the syntactic analysis of French. In Proceedings of the lOth International Conference on Computational Linguistics (COLING'84), Stanford, CA. find
  24. Hobbs, Jerry R., Douglas Appelt, John Bear, David Israel Megumi Kameyama, Mark Stickel, and Mabry Tyson. 1997. FASTUS: A cascaded finite-state transducer for extracting information from natural-language text. In E. Roche and Y. Schabes, editors, Finite State Devices for Natural Language Processing. find
  25. MIT Press, Cambridge, MA. Hobbs, Jerry R., Douglas E. Appelt, John Bear, David Israel Andy Kehler, Megumi Kamayama, David Martin, Karen Myers, and Mabry Tyson. 1995. SRI International FASTUS system MUC-6 test results and analysis. In Proceedings of the Sixth Message Understanding Conference, Columbi… find
  26. Jelinek, Fred, John Lafferty, David M. Magerman, Robert Mercer, Adwait Ratnaparkhi, and Salim Roukos. 1994. Decision tree parsing using a hidden derivation model. In Proceedings from the ARPA Workshop on Human Language Technology Workshop, March. find
  27. Joshi, Aravind K. 1960. Computation of syntactic structure. In Advances in Documentation and Library Science, volume III, Part 2. Interscience Publishers, Inc., NY. find
  28. Joshi, Aravind K. 1985. Tree adjoining grammars: How much context sensitivity is required to provide a reasonable structural description? In D. Dowty, I. Karttunen, and A. Zwicky, editors, Natural Language Parsing. Cambridge University Press, Cambridge, U.K., pages 206-250. find
  29. Joshi, Aravind K. 1987. An introduction to tree adjoining grammars. In A. Manaster Ramer, editor, Mathematics of Language. John Benjamins, Amsterdam. find
  30. Joshi, Aravind K. 1998. Role of constrained computational systems in natural language processing. Artificial Intelligence, 103:117-132. find
  31. Joshi, Aravind K. and Philip Hopely. 1997. A parser from antiquity. Natural Language Engineering, 2(4). find
  32. Joshi, Aravind K., L. Levy, and M. Takahashi. 1975. Tree adjunct grammars. find
  33. Journal of Computer and System Sciences. find
  34. Joshi, Aravind K. and Yves Schabes, 1996. Tree-adjoining grammars. In Handbook of Formal Languages and Automata. Springer-Verlag, Berlin. find
  35. Joshi, Aravind K. and B. Srinivas. 1994. Disambiguation of super parts of speech (or supertags): Almost parsing. In Proceedings of the 15th International Conference on Computational Linguistics (COLING'94), Kyoto, Japan, August. find
  36. Kaplan, Ronald and Joan Bresnan. 1983. Lexical-functional grammar: A formal system for grammatical representation. In J. Bresnan, editor, The Mental Representation of Grammatical Relations. MIT Press, Cambridge, MA. find
  37. Karlsson, F., A. Voutilainen, J. Heikkil~i, and A. Anttila. 1994. Constraint Grammar: A Language-Independent System for Parsing Unrestricted Text. Mouton de Gruyter, Berlin and NY. find
  38. Karttunen, L. J-P. Chanod, G. Grefenstette, and A. Schiller. 1997. Regular expressions for language engineering. Natural Language Engineering, 2(4). find
  39. Kasper, Robert, Bernd Kiefer, Klaus Netter, and K. Vijay-Shanker. 1995. Compilation of HPSG to TAG. In Proceedings of the 33rd Annual Meeting, Cambridge, MA. Association for Computational Linguistics. find
  40. Katz, Slava M. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech and SignalProcessing, 35(3):400-401. find
  41. Kempe, Andre. 1994. Probabilistic Tagging with Feature Structures. In Proceedings of the 15th International Conference on Computational Linguistics (COLING'94), Kyoto, Japan, August. find
  42. Kroch, Anthony S. and Aravind K. Joshi. 1985. The linguistic relevance of tree adjoining grammars. Technical Report MS-CIS-85-16, Department of Computer and Information Science, University of Pennsylvania. find
  43. Kuno, S. 1966. Harvard predictive analyzer. In David G. Hays, editor, Readings in Automatic Language Processing. American Elsevier Pub. Co., NY. find
  44. Magerman, David M. 1995. Statistical decision-tree models for parsing. In Proceedings of the 33rd Annual Meeting. Association for Computational Linguistics. find
  45. Marcus, Mitchell M., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313-330. find our card
  46. Nagao, Makoto. 1994. Varieties of heuristics in sentence processing. In Current Issues in Natural Language Processing: In Honour of Don Walker. Giardini with Kluwer. find
  47. Ney, Herman, Ute Essen, and Reinhard Kneser. 1995. On the estimation of 'small' probabilities by leaving-one-out. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(2). find
  48. Niesler, T. R. and P. C. Woodland. 1996. A variable-length category-based n-gram language model. In Proceedings, IEEE ICASSP. find
  49. Pollard, Carl and Ivan A. Sag. 1987. Information-Based Syntax and Semantics. Vol. 1: Fundamentals. CSLI. find
  50. Roche, Emmanuel. 1993. Analyse syntaxique transformationelle du francais par transducteurs et lexique-grammaire. Ph.D. thesis, Universite Paris 7. find
  51. Schabes, Yves. 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, Computer Science Department, University of Pennsylvania. find
  52. Schabes, Yves, Anne AbeillG and Aravind K. Joshi. 1988. Parsing strategies with 'lexicalized' grammars: Application to Tree Adjoining Grammars. In Proceedings of the 12th International Conference on Computational Linguistics (COLING'88), Budapest, Hungary, August. find
  53. Schabes, Yves and Aravind K. Joshi. 1991. Parsing with lexicalized tree adjoining grammar. In M. Tomita, editor, Current Issues in Parsing Technologies. Kluwer Academic Publishers. find
  54. Schabes, Y., M. Roth, and R. Osborne. 1993. Parsing the Wall Street Journal with the inside-outside algorithm. In Proceedings of the European ACL. find
  55. Sleator, Daniel and Davy Temperley. 1991. Parsing English with a Link Grammar. Technical Report CMU-CS-91-196, Department of Computer Sdence, Carnegie Mellon University. find our card
  56. Srinivas, B. 1996. "Almost parsing" technique for language modeling. In Proceedings of lCSLP96 Conference, Philadelphia, PA. find
  57. Srinivas, B. 1997a. Complexity of Lexical Descriptions and its Relevance to Partial Parsing. Ph.D. thesis, University of Pennsylvania. find
  58. Srinivas, B. 1997b. Performance evaluation of supertagging for partial parsing. In Proceedings of the International Workshop on Parsing Technologies, September. find
  59. Srinivas, B., Christine Doran, and Seth Kulick. 1995. Heuristics and parse ranking. In Proceedings of the 4th Annual International Workshop on Parsing Technologies, Prague, September. find
  60. Steedman, Mark. 1987. Combinatory grammars and parasitic gaps. Natural Language and Linguistic Theory, 5:403--439. find
  61. Steedman, Mark editor. 1997. The Syntactic Interface. MIT Press, Cambridge, MA and London, England. find
  62. Tapanainen, Pasi and Timo J~irvinen. 1994. Syntactic analysis of natural language using linguistic rules and corpus-based patterns. In Proceedings of the 15th International Conference on Computational Linguistics (COLING'94), Kyoto, Japan, August. find
  63. Vijay-Shanker, K. 1987. A Study of Tree Adjoining Grammars. Ph.D. thesis, Department of Computer and Information Science, University of Pennsylvania. find
  64. Vijay-Shanker, K. and Aravind K. Joshi. 1991. Unification based tree adjoining grammars. In J. Wedekind, editor, Un~'cation-based Grammars. MIT Press, Cambridge, MA. find
  65. Voutilainen, Atro. 1994. Designing a Parsing Grammar. Publications of the Department of General Linguistics, University of Helsinki. find
  66. Waltz, D. 1975. Understanding line drawings of scenes with shadows. In P. Winston, editor, Psychology of Computer Vision, MIT Press. find
  67. Weischedel, Ralph, Richard Schwartz, Jeff Palmucci, Marie Meteer, and Lance Ramshaw. 1993. Coping with ambiguity and unknown words through probabilistic models. Computational Linguistics, 19(2):359-382, June. find
  68. XTAG-Group, The. 1995. A lexicalized tree adjoining grammar for English. Technical Report IRCS 95-03, University of Pennsylvania. find