Head-Driven Statistical Models for Natural Language Parsing

What it is about

Collins gives three generative models for lexicalized parsing of the Penn Treebank. A tree is generated top-down from its head: at each step the model chooses the head's modifiers on each side, with distance, subcategorization frames, and for Model 3 traces for wh-movement. Model 1 reaches 87.7% labelled precision and 87.5% recall on section 23 (sentences up to 100 words); Models 2 and 3 reach 88.3% and 88.0%. Read as dependencies, Model 2 gets 91.0% of head-modifier pairs right on section 0 without labels. The per-type analysis shows that verb complements are recovered well (above 93%), while coordination (recall 61.47%) and some noun-phrase modifiers are the weak spots.

Ideas

• I1. en/src/parse.rs: add a distance feature for each candidate arc (direction, binned distance, and a count of verbs or punctuation between the two words); measure cv LAS on the train folds, then EWT test once per release.
• I2. en/src/parse.rs: add a subcategorization feature for a verb head, namely which of its obligatory dependents (nsubj, obj, iobj, ccomp, xcomp) are already attached; measure cv LAS and the LAS of verb-headed arcs with en ud-eval.
• I3. en ud-eval: report accuracy by relation (conj, cc, punct, amod, nmod) on EWT test, as the paper's Table 5 does, so that the coordination gap is visible for Mova before any change is made.

For Mova

The subcategorization and distance features are what the verb chapter and the clause chapter describe, so the relevant chapters are 23-complementation, 24-coordination-subordination and 22-phrases. The code is en/src/parse.rs for the features, en/src/convert.rs for the head rules used in conversion, and en ud-eval for the breakdown. Measure first: the per-relation breakdown of idea I3, which costs one run and shows where the errors are.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/089120103322753356

@article{collins2003head,
  title = {{Head-Driven Statistical Models for Natural Language Parsing}},
  author = {Collins, Michael},
  journal = {Computational Linguistics},
  year = {2003},
  doi = {10.1162/089120103322753356},
  url = {https://doi.org/10.1162/089120103322753356}
}

References

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

1. Alshawi, Hiyan. 1996. Head automata and bilingual tiling: Translation with minimal representations. Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages 167–176. find
2. Alshawi, Hiyan and David Carter. 1994. Training and scaling preference functions for disambiguation. Computational Linguistics, 20(4):635–648. find
3. Bikel, Dan. 2000. A statistical model for parsing and word-sense disambiguation. In Proceedings of the Student Research Workshop at ACL 2000. find
4. Bikel, Dan, Scott Miller, Richard Schwartz, and Ralph Weischedel. 1997. Nymble: A high-performance learning name-finder. In Proceedings of the Fifth Conference on Applied Natural Language Processing, pages 194–201. find
5. Black, Ezra, Steven Abney, Dan Flickinger, Claudia Gdaniec, Ralph Grishman, Philip Harrison, Donald Hindle, Robert Ingria, Frederick Jelinek, Judith Klavans, Mark Liberman, Mitch Marcus, Salim Roukos, Beatrice Santorini, and Tomek Strzalkowski. 1991. A Procedure for quantitatively comparing the synt… find
6. Black, Ezra, Frederick Jelinek, John Lafferty, David Magerman, Robert Mercer and Salim Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. In Proceedings of the Fifth DARPA Speech and Natural Language Workshop, Harriman, NY. find
7. Blaheta, Don, and Eugene Charniak. 2000. Assigning function tags to parsed text. In Proceedings of the First Annual Meeting of the North American Chapter of the Association for Computational Linguistics, pages 234–240, Seattle. find
8. Bod, Rens. 2001. What is the minimal set of fragments that achieves maximal parse accuracy? In Proceedings of ACL 2001. find
9. Booth, Taylor L., and Richard A. Thompson. 1973. Applying probability measures to abstract languages. IEEE Transactions on Computers, C-22(5):442–450. find
10. Brill, Eric. 1993. Automatic grammar induction and parsing free text: A transformation-based approach. In Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics. find
11. Charniak, Eugene. 1997. Statistical parsing with a context-free grammar and word statistics. In Proceedings of the Fourteenth National Conference on Artificial Intelligence, AAAI Press/MIT Press, Menlo Park, CA. find
12. Charniak, Eugene. 2000. A maximum-entropy-inspired parser. In Proceedings of NAACL 2000. find
13. Charniak, Eugene. 2001. Immediate-head parsing for language models. In Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics. find
14. Chelba, Ciprian, and Frederick Jelinek. 1998. Exploiting syntactic structure for language modeling. In Proceedings of COLING-ACL 1998, Montreal. find
15. Chiang, David. 2000. Statistical parsing with an automatically-extracted tree adjoining grammar. In Proceedings of ACL 2000, Hong Kong, pages 456–463. find
16. Collins, Michael, and James Brooks. 1995. Prepositional phrase attachment through a backed-off model. Proceedings of the Third Workshop on Very Large Corpora, pages 27–38. find our card
17. Collins, Michael. 1996. A new statistical parser based on bigram lexical dependencies. Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages 184–191. find
18. Collins, Michael. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pages 16–23. find
19. Collins, Michael. 1999. Head-driven statistical models for natural language parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia. find
20. Collins, Michael, Jan Hajic, Lance Ramshaw, and Christoph Tillmann. 1999. A statistical parser for Czech. In Proceedings of the 37th Annual Meeting of the ACL, College Park, Maryland. find
21. Collins, Michael. 2000. Discriminative reranking for natural language parsing. Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000). find our card
22. Collins, Michael. 2002. Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. To appear as a book chapter. find
23. De Marcken, Carl. 1995. On the unsupervised induction of phrase-structure grammars. In Proceedings of the Third Workshop on Very Large Corpora. find
24. Eisner, Jason. 1996a. Three new probabilistic models for dependency parsing: An exploration. Proceedings of COLING-96, pages 340–345. find our card
25. Eisner, Jason. 1996b. An empirical comparison of probability models for dependency grammar. Technical Report IRCS-96-11, Institute for Research in Cognitive Science, University of Pennsylvania, Philadelphia. find
26. Eisner, Jason. 2002. Transformational priors over grammars. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), Philadelphia. find
27. Eisner, Jason, and Giorgio Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proceedings of the 37th Annual Meeting of the ACL. find
28. Freund, Yoav, Raj Iyer, Robert E. Schapire, and Yoram Singer. 1998. An efficient boosting algorithm for combining preferences. In Machine Learning: Proceedings of the Fifteenth International Conference. Morgan Kaufmann. find
29. Gazdar, Gerald, E. H. Klein, G. K. Pullum, and Ivan Sag. 1985. Generalized Phrase Structure Grammar. Harvard University Press, Cambridge, MA. find
30. Gildea, Daniel. 2001. Corpus variation and parser performance. In Proceedings of 2001 Conference on Empirical Methods in Natural Language Processing (EMNLP), Pittsburgh, PA. find our card
31. Goodman, Joshua. 1997. Probabilistic feature grammars. In Proceedings of the Fourth International Workshop on Parsing Technologies. find
32. Hermjakob, Ulf, and Ray Mooney. 1997. Learning parse and translation decisions from examples with rich context. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, page… find
33. Hindle, Don, and Mats Rooth. 1991. Structural Ambiguity and Lexical Relations. In Proceedings of the 29th Annual Meeting of the Association for Computational Linguistics. find
34. Hopcroft, John, and J. D. Ullman. 1979. Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, MA. find
35. Jelinek, Frederick, John Lafferty, David Magerman, Robert Mercer, Adwait Ratnaparkhi, and Salim Roukos. 1994. Decision tree parsing using a hidden derivation model. In Proceedings of the 1994 Human Language Technology Workshop, pages 272–277. find
36. Johnson, Mark. 1997. The effect of alternative tree representations on tree bank grammars. In Proceedings of NeMLAP 3. find
37. Jones, Mark and Jason Eisner. 1992a. A probabilistic parser applied to software testing documents. In Proceedings of National Conference on Artificial Intelligence (AAAI-92), pages 322–328, San Jose, CA. find
38. Jones, Mark and Jason Eisner. 1992b. A probabilistic parser and its application. In Proceedings of the AAAI-92 Workshop on Statistically-Based Natural Language Processing Techniques, San Jose, CA. find
39. Joshi, Aravind and Bangalore Srinivas. 1994. Disambiguation of super parts of speech (or supertags): Almost parsing. In International Conference on Computational Linguistics (COLING 1994), Kyoto University, Japan, August. find
40. Klein, Dan and Christopher Manning. 2002. Conditional structure versus conditional estimation in NLP models. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), Philadelphia. find
41. Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML 2001. find
42. Lafferty, John, Daniel Sleator, and David Temperley. 1992. Grammatical trigrams: A probabilistic model of link grammar. Proceedings of the 1992 AAAI Fall Symposium on Probabilistic Approaches to Natural Language. find
43. Magerman, David. 1995. Statistical decision-tree models for parsing. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, pages 276–283. find
44. Manning, Christopher D., and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, MA. find
45. Marcus, Mitchell, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. 1994. The Penn Treebank: Annotating predicate argument structure. Proceedings of the 1994 Human Language Technology Workshop, pages 110–115. find our card
46. Marcus, Mitchell, Beatrice Santorini and M. Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
47. Miller, Scott, Heidi Fox, Lance Ramshaw, and Ralph Weischedel. 2000. A novel use of statistical parsing to extract information from text. In Proceedings of the 1st Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 226–233. find
48. Pereira, Fernando, and David Warren. 1980. Definite clause grammars for language analysis: A survey of the formalism and a comparison with augmented transition networks. Artificial Intelligence, 13:231–278. find
49. Pinker, Stephen. 1994. The Language Instinct. William Morrow, New York. find
50. Ratnaparkhi, Adwait. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, May. find
51. Ratnaparkhi, Adwait. 1997. A linear observed time statistical parser based on maximum entropy models. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, Brown University, Providence, RI. find
52. Resnik, Philip. 1992. Probabilistic tree-adjoining grammar as a framework for statistical natural language processing. In Proceedings of COLING 1992, vol. 2, pages 418–424. find
53. Roark, Brian. 2001. Probabilistic top-down parsing and language modeling. Computational Linguistics, 27(2):249–276. find
54. Schabes, Yves. 1992. Stochastic lexicalized tree-adjoining grammars. In Proceedings of COLING 1992, vol. 2, pages 426–432. find
55. Schabes, Yves and Richard Waters. 1993. Stochastic lexicalized context-free grammar. In Proceedings of the Third International Workshop on Parsing Technologies. find
56. Sekine, Satoshi, John Carroll, S. Ananiadou, and J. Tsujii. 1992. Automatic Learning for Semantic Collocation. In Proceedings of the Third Conference on Applied Natural Language Processing. find
57. Seneff, Stephanie. 1992. TINA: A natural language system for spoken language applications. Computational Linguistics, 18(1):61-86. find
58. Witten, Ian and Timothy C. Bell. 1991. The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, 37(4):1085–1094. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/cl-2003-collins-head-driven-statistical-models-natural/