From 11-711
Jump to: navigation, search


Date Topic Instructor Reading Homework
T 9/1 Introduction to 11-711 Frederking
R 9/3 Introduction to NLP Ballesteros

Part I: Finite-State NLP

Date Topic Instructor Reading Homework
T 9/8 DFAs and NFAs Dyer Hopcroft & Ullman: 1 (all), 2.1, 2.2
R 9/10 Regular Expressions Dyer Hopcroft & Ullman: 3 (all)
F 9/11 Recitation: Example DFA Proof Dyer
T 9/15 Finite state properties & finite state transducers Dyer M. Mohri. Finite-State Transducers in Language and Speech Processing. (skim).
R 9/17 Finite state morphology Mortensen
T 9/22 Statistical Language Modelling Rosenfeld
R 9/24 Weighted Finite State Transducers Dyer Notes on Weighted FSTs
F 9/25 Recitation: Installing OpenFST and probability review Dyer
T 9/29 Intro to HMMs Dyer
  • Homework #1 due
R 10/1 HMM estimation Dyer
F 10/2 Recitation: Viterbi Algorithm Vivian
T 10/6 Dyer
R 10/8 Semirings and Generalized Path Sums Dyer
F 10/9 Recitation on semirings Austin
T 10/13 Ballesteros
R 10/15 PDAs and their equivalence to CFGs Ballesteros
F 10/16 Recitation: Exam Review TAs
T 10/20 Midterm Exam

Part II: Parsing and Context-Free Languages

Date Topic Instructor Reading Homework
R 10/22 Introduction to parsing: top down vs. bottom up, exponential space of parses, ambiguity, charts, CKY and CNF Ballesteros
F 10/23 No Recitation: Mid-semester Break
T 10/27 Earley's algorithm and Shift-Reduce Phrase-Structure algorithm. Ballesteros
  • Jay Earley, “An Efficient Context-Free Parsing Algorithm” Comm. of the ACM vol. 13 (2), pp. 94–102
  • Yue Zhang, Steve Clark. Syntactic processing using the generalized perceptron and beam search. Computational Linguistics. 2011
R 10/29 PCFGs, weighted CFGs, and weighted CKY, inside-outside Ballesteros
  • Eugene Charniak. Tree-Bank Grammars. In Proceedings of AAAI. 1996.
  • Michael Collins. PCFGs. Lecture notes. 2012
F 10/30 Recitation: CFG conversions Vivian
T 11/3 Parameter estimation from treebanks, Markovization, etc Ballesteros
  • Dan Klein and Christopher D. Manning. Accurate Unlexicalized Parsing. In Proceedings of ACL. 2003
  • S. Riezler, et al. Parsing the Wall Street Journal Using a Lexical-Functional Grammar and Discriminative Estimation Techniques. ACL. 2002
  • Michael Collins. Lexicalized PCFGs. Lecture notes. 2012
  • Slav Petrov, Leon Barrett, Romain Thibaux and Dan Klein. Learning Accurate, Compact and Interpretable Tree Annotation. ACL-Coling. 2006.
R 11/5 Dependency syntax introduction: linguistics, relationship to phrase structure syntax. Ballesteros
  • Sandra Kübler, Ryan McDonald and Joakim Nivre. Dependency Parsing. Morgan and Claypool. 2009.
F 11/6 Recitation: inside-outside algorithm for PCFGs. Austin
T 11/10 Transition-based dependency parsing Ballesteros
  • Joakim Nivre. Algorithms for Deterministic Incremental Dependency Parsing. Computational Linguistics 34(4). 2008.
  • Joakim Nivre. Non-Projective Dependency Parsing in Expected Linear Time. In Proceedings of ACL. 2009
  • Bernd Bohnet and Joakim Nivre. A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing. EMNLP. 2012.
  • Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews and Noah Smith. Transition-Based Dependency Parsing with Stack Long Short-Term Memory. ACL 2015
  • Miguel Ballesteros, Chris Dyer and Noah Smith. Improved Transition-Based Parsing by Modeling Characters instead of Words with LSTMs. EMNLP 2015.
R 11/12 Arc-factored models, Eisner's algorithm, Spanning tree parsing, Graph-based dependency parsing Ballesteros
  • Jason Eisner. Three New Probabilistic Models for Dependency Parsing: An Exploration. In Proceedings of Coling. 1996.
  • Ryan McDonald, Koby Crammer and Fernando Pereira. Online Large-Margin Training of Dependency Parsers. In Proceedings of ACL. 2005.
  • Ryan McDonald and Fernando Pereira. Online Learning of Approximate Dependency Parsing Algorithms. In Proceedings of EACL. 2006.
  • Xavier Carreras. Experiments with a Higher-Order Projective Dependency Parser. EMNLP-CoNLL 2007.
  • Terry Koo and Michael Collins. Efficient third-order dependency parsers. ACL 2010
F 11/13 Recitation: Transition-based dependency parsing Vivian
T 11/17 Weighted logic programs, semirings, agenda algorithm Dyer
R 11/19 Feature Structures and Unification Frederking Jurafsky and Martin: Ch. 15 (Note: errors in textbook)
F 11/20 Recitation: Unification Austin

Part III: Semantics and Discourse

Date Topic Instructor Reading Homework
T 11/24 First order predicate calculus Frederking Jurafsky and Martin: 17 and 18 (Note: errors in textbook)
R 11/26 No Class: Thanksgiving
F 11/27 No Recitation: Thanksgiving
T 12/1 CCGs and Lambda Calculus Frederking

Jurafsky and Martin: Section 12.7.2. And see this tutorial online (especially section on "Template-based GENLEX"). See also the paper Steedman for a brief introduction, and Steedman and Baldridge for more details. Lambda calculus was in Ch. 17 and 18.

R 12/3 Lexical Semantics: PropBank, PredArg, and Distributions Frederking

Jurafsky and Martin: 19 and 20.6-20.9 (Note: errors in textbook)

F 12/4 Recitation: CCGs Vivian
T 12/8 Discourse Structure, Coreference Resolution Frederking Jurafsky and Martin: 21
R 12/10 Current NLP at CMU and LTI/Overview Instructors
  • Homework #5 due
F 12/11 Recitation: Final exam review TAs
M 12/14 Final exam 1-4 p.m.
Location Doherty A302