From 11-711
Jump to: navigation, search


Date Topic Instructor Reading Homework
T 8/26 Introduction to NLP Lavie & Dyer

Part I: Finite-State 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 (NDFSA-e) 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.1-4.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 II-III of the course may be reordered.

Part II: Context-Free NLP

Date Topic Instructor Reading Homework
T 10/7 Formal Language Theory (Context-Free Grammars) (Notes. See pages 20-27) Lavie Hopcroft & Ullman: 5.1, 5.2, 5.4
R 10/9 Formal Language Theory (Pushdown Automata) Lavie Hopcroft & Ullman: 6.1-6.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(+) (Bottom-Up) (Notes) Dyer Jurafsky and Martin: chapter 13, up to and including 13.4.1
F 10/17 Mid-semester break
T 10/21 Parsing CFLs: Earley Parsing Algorithm (Top-Down) (Slides) Lavie

Sample Midterm Exam Sample Solution

F 10/24

Recitation (Equivalence of PDAs accepting by final state / empty stack) (Slides)

T 10/28 Solving weighted logic programs & Dynamic Programming (Agenda slides, Dynamic Programming slides) Dyer 2.3.4-2.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.4-2.3.5

Smith section 2.3 through 2.3.3; recommended: "Semiring Parsing" (Goodman, 1999)

F 10/31 Midterm Solutions Austin

Part III: Context-Sensitive NLP and Semantics

Date Topic Instructor Reading Homework
T 11/4 Shift-Reduce (LR/GLR) Parsing (LR parsing slides, GLR parsing slides) Lavie
R 11/6 Tree Substitution Grammar and Tree Adjoining Grammar Lavie
  • Aravind Joshi & Yves Schabes, “Tree-Adjoining Grammars” link
  • Anthony Kroch & Aravind Joshi, “The Linguistic Relevance of TAG” link
  • XTAG Online Tutorial: at link
F 11/7 Recitation (Dynamic Programming and Complexity Analysis) Austin
T 11/11 Dependency Parsing (Slides) Dyer
  • Kuebler, McDonald, and Nivre (chapters 1 and 2; the rest is optional)
  • Eisner "Three New Probabilistic Models for Dependency Parsing: An Exploration" 1996 link
  • Homework 4a due
R 11/13 Graph-based Dependency Parsing and Spanning Tree Algorithms (Slides) Sam and Swabha

McDonald et al. (2005). Non-projective 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 First-order 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.
  • Homework 4b due
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, Predicate-Argument Structure, and Frame Semantic Parsing (Slides) Frederking Jurafsky and Martin: Ch. 19 and 20.6-20.9 (see errors in textbook)
R 12/4 Deeper analysis: coreference resolution, discourse structure (Slides) Frederking Jurafsky and Martin: 21
  • Homework 5 due
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