Calendar

Mon	Tue	Wed	Thu	Fri
4/2	4/3	4/4 PA1 out Lecture 1: Intro	4/5	4/6
4/9 Lecture 2: N-gram Models	4/10	4/11 Lecture 3: StatMT	4/12	4/13 Section 1: Smoothing
4/16 Lecture 4: StatMT & EM	4/17	4/18 PA1 due; PA2 out Lecture 5: StatMT Systems	4/19	4/20 Section 2: EM
4/23 Lecture 6: IE/NER & NB Models	4/24	4/25 Lecture 7: MaxEnt Classifiers	4/26	4/27 Section 3: MaxEnt
4/30 Lecture 8: MaxEnt Sequence Classifiers	5/1	5/2 PA2 due; PA3 out Lecture 9: IE and text mining	5/3	5/4 Section 4: Corpora
5/7 Lecture 10: Syntax & Parsing	5/8	5/9 Final project proposal due Lecture 11: DPs for Parsing	5/10	5/11 Section 5: Parsing & PCFGs
5/14 Lecture 12: PCFGs	5/15	5/16 PA3 due Lecture 13: StatParsers	5/17	5/18
5/21 Lecture 14: Semantic Role Labeling	5/22	5/23 Lecture 15: ComSem	5/24	5/25
5/28 Memorial Day	5/29	5/30 Lecture 16: ComSem II	5/31	6/1
6/4 Lecture 17: Lexical Semantics	6/5	6/6 Final project due Lecture 18: QA & Inference	6/7	6/8 8:30am - 11:30am Final project presentations

Syllabus

Lecture 1
Wed
4/4/07

Introduction [slides: 1: pdf, ps; 2: pdf, ps, 3: pdf, ps; tarred: pdf, ps]
Overview of NLP. Statistical machine translation. Language models and their role in speech processing. Course introduction and administration.
Good background reading: M&S 1.0-1.3, 4.1-4.2, Collaboration Policy
Optional reading: Ken Church's tutorial Unix for Poets [ps, pdf]
The IBM 701 translator (1954)
(If your knowledge of probability theory is limited, also read M&S 2.0-2.1.7. If that's too condensed, read the probability chapter of an intro statistics textbook, e.g. Rice, Mathematical Statistics and Data Analysis, ch. 1.)
Distributed today: Programming Assignment 1

Lecture 2
Mon
4/9/07

N-gram Language Models and Information Theory [slides: pdf; MegaHal: html]
n-gram models. Entropy, relative entropy, cross entropy, mutual information, perplexity. Statistical estimation and smoothing for language models.
Assigned reading: M&S 1.4, 2.2, ch. 6.
Optional reading: Joshua Goodman (2001), A Bit of Progress in Language Modeling, Extended Version [pdf, ps]
Optional reading: Stanley Chen and Joshua Goodman (1998), An empirical study of smoothing techniques for language modeling [pdf, ps]

Lecture 3
Wed
4/11/07

Statistical Machine Translation (MT), Alignment Models [slides: pdf ]

Section 1
Fri
4/13/07

Smoothing [notes: xls ]
Smoothing: absolute discounting, proving you have a proper probability distribution, Good-Turing implementation. Information theory examples and intuitions. Java implementation issues.

Lecture 4
Mon
4/16/07

Statistical Alignment Models and Expectation Maximization (EM) [slides: pdf, spreadsheet: xls]
EM and its use in statistical MT alignment models.
Assigned reading: Kevin Knight, A Statistical MT Tutorial Workbook [rtf]. MS., August 1999. (see also the relevant FAQ)
Reference reading: Geoffrey J. McLachlan and Thriyambakam Krishnan. 1997. The EM Algorithm and Extensions. Wiley
Further reading: M&S 13.
J&M chapter 24. Machine Translation
Moore, Robert C. 2005. Association-Based Bilingual Word Alignment. In Proceedings, Workshop on Building and Using Parallel Texts: Data-Driven Machine Translation and Beyond, Ann Arbor, Michigan , pp. 1-8.
Moore, Robert C. 2004. Improving IBM Word Alignment Model 1. In Proceedings, 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, pp. 519-526.

Lecture 5
Wed
4/18/07

Putting together a complete statistical MT system [slides: pdf]
Decoding and A* Search. Recent work in statistical MT: statistical phrase based systems and syntax in MT.
Further reading: Brown, Della Pietra, Della Pietra, and Mercer, The Mathematics of Statistical Machine Translation: Parameter Estimation [pdf, pdf]. Computational Linguistics.
Ulrich Germann, Michael Jahr, Kevin Knight, Daniel Marcu, and Kenji Yamada. 2001. Fast Decoding and Optimal Decoding for Machine Translation. ACL.
K. Yamada and K. Knight. 2002. A Decoder for Syntax-Based Statistical MT. ACL.
David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. ACL 2005, pages 263-270.
Due today: Programming Assignment 1
Distributed today: Programming Assignment 2

Section 2
Fri
4/20/07

The EM algorithm [notes: xls]

Lecture 6
Mon
4/23/07

Information Extraction (IE) and Named Entity Recognition (NER). Naïve Bayes (NB) Models for entity classification. [slides: ppt]
Information sources, performance bounds, dictionary methods, supervised machine learning methods, Naïve Bayes classifiers.
Evaluation reading: M&S 8.1
Background IE reading: Ion Muslea (1999), Extraction Patterns for Information Extraction Tasks: A Survey [pdf, ps], AAAI-99 Workshop on Machine Learning for Information Extraction.
Background IE reading: Douglas E. Appelt. 1999. Introduction to Information Extraction Technology

Lecture 7
Wed
4/25/07

Maximum Entropy Classifiers [slides: pdf]
Assigned Reading: class slides.
Other references: Adwait Ratnaparkhi. A Simple Introduction to Maximum Entropy Models for Natural Language Processing. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania.
M&S section 16.2

Section 3
Fri
4/27/07

Maximum entropy models [notes: pdf, xls]

Lecture 8
Mon
4/30/07

Maximum Entropy Sequence Classifiers [slides: pdf]
Assigned Reading: class slides.
Other references: Adwait Ratnaparkhi. A Simple Introduction to Maximum Entropy Models for Natural Language Processing. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania.
M&S section 16.2
Adam Berger, A Brief Maxent Tutorial
Distributed today: Final project guide

Lecture 9
Wed
5/2/07

IE and text mining [slides: pdf]
HMMs for IE reading: Dayne Freitag and Andrew McCallum (2000), Information Extraction with HMM Structures Learned by Stochastic Optimization, AAAI-2000
Maxent NER reading: Jenny Finkel et al., 2005. Exploring the Boundaries: Gene and Protein Identification in Biomedical Text
Due today: Programming Assignment 2
Distributed today: Programming Assignment 3

Section 4
Fri
5/4/07

Corpora and other resources [notes: txt]

Lecture 10
Mon
5/7/07

Syntax and Parsing for Context-Free Grammars (CFGs) [slides: pdf]
Top-down parsing, bottom-up parsing, empty constituents, left recursion.
Background reading: M&S 3 (if you haven't done any linguistics courses) or J&M ch. 9
Optional reading: J&M ch. 10

Lecture 11
Wed
5/9/07

Dynamic Programming for Parsing [handout: pdf]
Dynamic programming methods, chart parsing, the CKY algorithm.
Optional reading: J&M ch. 10
Due today: final project proposals

Section 5
Fri
5/11/07

Parsing, PCFGs [notes: pdf]

Lecture 12
Mon
5/14/07

Probabilistic Context-Free Grammars (PCFGs) [slides: pdf (probparse), pdf (unlexicalized)]
PCFGs, finding the most likely parse, refining PCFGs. Other questions for PCFGs: the inside-outside algorithm, and learning PCFGs.
Assigned reading: M&S Ch. 11

Lecture 13
Wed
5/16/07

Modern Statistical Parsers [slides: see last time, pdf (search), and pdf(statparse)]
Parsing for disambiguation, weakening independence assumptions, lexicalization, search methods, probabilistic left corner grammars, parser evaluation.
Assigned reading: M&S 8.3, 12
Optional readings:

Eugene Charniak (1997), Statistical techniques for natural language parsing, AI Magazine.
Dan Klein and Christopher D. Manning. 2002. A Generative Constituent-Context Model for Improved Grammar Induction. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 128-135.
Dan Klein and Christopher D. Manning. 2002. Natural Language Grammar Induction using a Constituent-Context Model. In Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (eds), Advances in Neural Information Processing Systems 14 (NIPS 2001). Cambridge, MA: MIT Press, vol. 1, pp. 35-42.
Dan Klein and Christopher D. Manning. 2003. Accurate Unlexicalized Parsing. ACL 2003, pp. 423-430.
Dan Klein and Christopher D. Manning. 2003. Factored A* Search for Models over Sequences and Trees. IJCAI 2003.
Dan Klein and Christopher D. Manning. 2003. A* Parsing: Fast Exact Viterbi Parse Selection. HLT-NAACL 2003.
Kristina Toutanova, Christopher D. Manning, Stuart M. Shieber, Dan Flickinger, and Stephan Oepen. 2002. Parse Disambiguation for a Rich HPSG Grammar. First Workshop on Treebanks and Linguistic Theories (TLT2002), pp. 253-263. Sozopol, Bulgaria.
Kristina Toutanova, Christopher D. Manning, Dan Flickinger, and Stephan Oepen. 2005. Stochastic HPSG Parse Disambiguation using the Redwoods Corpus. Research in Language and Computation 2005.
B. Taskar, D. Klein, M. Collins, D. Koller and C. Manning. Max-Margin Parsing. Empirical Methods in Natural Language Processing (EMNLP04), Barcelona, Spain, July 2004. Received best paper award.
Eugene Charniak (1997), Statistical parsing with a context-free grammar and word statistics, Proceedings of the Fourteenth National Conference on Artificial Intelligence. AAAI Press/MIT Press, Menlo Park (1997).
Eugene Charniak (2000), A Maximum-Entropy-Inspired Parser, Proceedings of NAACL-2000.
Eugene Charniak and Mark Johnson (2005). Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking, Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL 2005)
Ryan McDonald, Koby Crammer and Fernando Pereira (2005). Online Large-Margin Training of Dependency Parsers. 43rd Annual Meeting of the Association for Computational Linguistics, ACL 2005.