Schedule
From 11711
Contents
Introduction
Date  Topic  Instructor  Reading  Homework 
T 8/26  Introduction to NLP  Lavie & Dyer 
Part I: FiniteState NLP
Date  Topic  Instructor  Reading  Homework 
R 8/28  Introduction to Formal Language Theory (Notation, DFSA)  Lavie  Hopcroft & Ullman: 1 (all), 2.1, 2.2  
F 8/29  Recitation: An Example of FSA Proof  Austin  
T 9/2  Formal Language Theory (NDFSA, FSA with Output)  Lavie  Hopcroft & Ullman: 2.3, 2.4  
R 9/4  Formal Language Theory (NDFSAe)  Lavie  Hopcroft & Ullman: 2.5 

F 9/5 

Sam  
T 9/9  Formal Language Theory (REs)  Lavie  Hopcroft & Ullman: 3.1, 3.2  
R 9/11  Formal Language Theory (Pumping Lemma)  Lavie  Hopcroft & Ullman: 4.14.3  
T 9/16  Formal Language Theory (Properties of Regular Languages)  Lavie  
R 9/18  Finite State Morphology (Slides)  Dyer  Jurafsky and Martin, chapter 3; optional: Beesley and Kartunnen (2003), Roark and Sproat (2007), Kartunnen and Beesley (2005)  
F 9/19  Recitation (Open FST and PyFST) (Setting up PyFST (Ubuntu), Setting up PyFST (OSX))  Austin  
T 9/23  Weighted finite state machines (FSA, FST) (Slides, Notes on WFSA)  Dyer  Jurafsky and Martin, Ch. 6.1, 6.2, 6.4; for lots more about WFSTs, see Mohri (1997) 

R 9/25  WFST best path, and the special case of HMMs (Notes , Slides)  Dyer  
F 9/26  Using PyFST (Recitation IPython Notebook. Use gzip d recitation.ipynb.gz to unzip)  Austin  
T 9/30  Applications of HMMs: POS, NER, chunking, shallow parsing, supersense tagging, alignment (Slides)  Dyer  
R 10/2  Generalized Path Algorithms and Semirings (Notes)  Dyer  Huang (2006) through section 3 and Tarjan (1981) A Unified Approach to Path Problems (you may need to be on campus to access). 
Note: Some lectures in parts IIIII of the course may be reordered.
Part II: ContextFree NLP
Date  Topic  Instructor  Reading  Homework 
T 10/7  Formal Language Theory (ContextFree Grammars) (Notes. See pages 2027)  Lavie  Hopcroft & Ullman: 5.1, 5.2, 5.4  
R 10/9  Formal Language Theory (Pushdown Automata)  Lavie  Hopcroft & Ullman: 6.16.3 

F 10/10  Recitation (Converting CFGs to Chomsky Normal Form) (Slides)  Sam  
T 10/14  Formal Language Theory (Equivalence of CFGs and PDAs)  Lavie  
R 10/16  Parsing CFLs: Chart Parsing and CKY(+) (BottomUp) (Notes)  Dyer  Jurafsky and Martin: chapter 13, up to and including 13.4.1  
F 10/17  Midsemester break  
T 10/21  Parsing CFLs: Earley Parsing Algorithm (TopDown) (Slides)  Lavie 


R 10/23  MIDTERM EXAM  
F 10/24 
Recitation (Equivalence of PDAs accepting by final state / empty stack) (Slides) 
Sam  
T 10/28  Solving weighted logic programs & Dynamic Programming (Agenda slides, Dynamic Programming slides)  Dyer  2.3.42.3.5
Smith section 2.3 through 2.3.3; recommended: "Semiring Parsing" (Goodman, 1999) 

R 10/30  Solving weighted logic programs & Dynamic Programming  Dyer  2.3.42.3.5
Smith section 2.3 through 2.3.3; recommended: "Semiring Parsing" (Goodman, 1999) 

F 10/31  Midterm Solutions  Austin 
Part III: ContextSensitive NLP and Semantics
Date  Topic  Instructor  Reading  Homework 
T 11/4  ShiftReduce (LR/GLR) Parsing (LR parsing slides, GLR parsing slides)  Lavie 


R 11/6  Tree Substitution Grammar and Tree Adjoining Grammar  Lavie  
F 11/7  Recitation (Dynamic Programming and Complexity Analysis)  Austin 


T 11/11  Dependency Parsing (Slides)  Dyer 


R 11/13  Graphbased Dependency Parsing and Spanning Tree Algorithms (Slides)  Sam and Swabha 
McDonald et al. (2005). Nonprojective Dependency Parsing using Spanning Tree Algorithms 

T 11/18  Parsing: Unification Grammars (Slides)  Frederking  Jurafsky and Martin: 15 (see errors in textbook) 

R 11/20  Firstorder predicate calculus and semantic attachments on CFGs (Slides)  Frederking  Jurafsky and Martin: 17 and 18 (see errors in textbook)  
F 11/21  Recitation: Unification (Slides, latex)  Sam  
T 11/25  CCG and Lambda Calculus (Slides)  Frederking  Jurafsky and Martin: Section 12.7.2; see Steedman for a brief introduction, and Steedman and Baldridge for more details. Lambda calculus was in Ch. 17 and 18. 

R 11/27  NO CLASS: Thanksgiving Break 
Part IV: Current NLP Challenges and Research
Date  Topic  Instructor  Reading  Homework 
T 12/2  Lexical semantics, PropBank, PredicateArgument Structure, and Frame Semantic Parsing (Slides)  Frederking  Jurafsky and Martin: Ch. 19 and 20.620.9 (see errors in textbook)  
R 12/4  Deeper analysis: coreference resolution, discourse structure (Slides)  Frederking  Jurafsky and Martin: 21 

F 12/5  Q&A session before the final exam  
T 12/9 1:00 PM ‐ 4:00 PM  FINAL EXAM DH A302, Open books/notes 