Class Meeting for 10-710 10-11-2011

This is one of the class meetings on the schedule for the course Structured Prediction 10-710 in Fall 2011.

Natural Language Parsing with Context-Free Grammars

• Slides

Required Readings

• Sections 1.4, 2.2.3 (review), and 3.3.4, of Linguistic Structure Prediction, Smith 2011; figures 2.18 and 2.19 show, in semiring weighted logic program notation, the CKY and Earley parsing algorithms

Optional Readings

• Statistical Parsing with a Context-free Grammar and Word Statistics, E. Charniak, AAAI 1997
• PCFG Models of Linguistic Tree Representations, M. Johnson, Computational Linguistics 1998
• A Maximum-Entropy-Inspired Parser, E. Charniak, NAACL 2000
• Fast Exact Inference with a Factored Model for Natural Language Parsing, D. Klein and C. D. Manning, NIPS 2002
• Head-Driven Statistical Models for Natural Language Parsing, M. Collins, Computational Linguistics 2003 (a journal version of the parsers in his 1999 Ph.D. thesis, found in papers in 1996 and 1997)
• Accurate Unlexicalized Parsing, D. Klein and C. D. Manning, ACL 2003
• Max Margin Parsing, B. Taskar, D. Klein, M. Collins, D. Koller, and C. D. Manning, EMNLP 2004
• Better k-Best Parsing, L. Huang and D. Chiang, IWPT 2005
• Learning Accurate, Compact, and Interpretable Tree Annotation, S. Petrov, L. Barrett, R. Thibaux, D. Klein, ACL 2006
• Efficient, Feature-based, Conditional Random Field Parsing, J. R. Finkel, A. Kleeman, and C. D. Manning, ACL 2008
• Coarse-to-Fine Natural Language Processing, S. Petrov, 2009 dissertation

Background Readings

• Slav Petrov's slides on syntax and parsing, from the 2011 Lisbon Machine Learning Summer School
• Building a Large Annotated Corpus of English: The Penn Treebank, M. Marcus, B. Santorini, and M. A. Marcinkiewicz, Computational Linguistics 1993

Natural language and formal language

• Three Models for the Description of Language, N. Chomsky, IEEE Transactions on Information Theory 1956
• Natural Languages and Context-Free Languages, G. K. Pullum and G. Gazdar, Linguistics and Philosophy 1985
• Evidence Against the Context-Freeness of Natural Language, S. Shieber, Linguistics and Philosophy 1985