CS 224N -- Ling 237 Natural Language Processing Spring 2004 - Handout #2

---

Course Syllabus

(updated 2004/05/11)

Date	Topic	Out	Due
Week 1
Wednesday, 31 Mar 04 Lecture Slides ps pdf	What is NLP? History; current applications and topics. Need for precise language understanding. Course introduction and administration. Reading: M&S Sec 1.0-1.3 for general intro; M&S Sec 1.4 and 4.1, 4.2 for assignment. More: Course Information, Questionnaire, Ken Church's tutorial: Unix for Poets ps pdf, Homework Collaboration Policy	HW #1: Text ps pdf sed tutorial
	Rule based approaches to linguistic structure. How to find sentence structure: parsing as search.
Week 2
Monday, 5 Apr 04 Lecture Slides ps pdf	NLP Parsing: top-down parsing, bottom-up parsing; empty constituents, and left-recursive rules. Intro to dynamic programming of parsing Readings: handout, Gazdar and Mellish (1989) pp. 143-155; More: Syntax.doc handout
	Word classes (word clustering), lexical semantics, syntactic ambiguities. Reading: M&S Ch. 3 [if you haven't done any linguistics courses] or J&M Ch. 9 References: J&M Ch. 10
Wednesday, 7 Apr 04	Dynamic programming methods of parsing: Tabular/memoized/chart parsing methods. Well-formed substring tables. The CKY algorithm. The Earley algorithm. Active chart parsing. Readings: handout, Gazdar and Mellish (1989) pp. 179-199 References: J&M Ch. 10 More: Tabular Parsing handout	HW #2: Parsing - Programming: ps pdf Written Part: ps pdf	HW #1 Solutions: doc
	Information theory: entropy, cross entropy, mutual information. Readings: M&S Sec 2.2. If you are rusty or have little knowledge of probability theory, also read Ch. 2, sec 2.0-2.1.7. If that's too condensed, read the probability chapter of an intro statistics textbook, for instance, Rice, Mathematical Statistics and Data Analysis, ch. 1 (your dormmate probably has a copy).
Section	Parsing algorithms
Week 3
Monday, 12 Apr 04 Lecture Slides: speech recog ps pdf n-grams ppt	n-gram models of language: Relative Frequency estimation from corpora, n-gram models of English - Markov models, relative entropy, cross entropy, and perplexity. Smoothing techniques to deal with unseen or insufficiently seen contexts. Readings: M&S Chapter 6 [really it'd be good to glance through all of it, but pay particular attention to things we covered in class] References: Joshua Goodman. 2001. A Bit of Progress in Language Modeling. Computer Speech and Language, October 2001, pages 403-434. Stanley Chen and Joshua Goodman. 1998. An empirical study of smoothing techniques for language modeling. Technical report TR-10-98, Harvard University, August 1998. Jason Hutchens. MegaHAL site.
	Multinomial distributions, and smoothing them (for NLP)
Wednesday, 14 Apr 04 Lecture Slides pdf	Word Sense Disambiguation: The general problem of word sense disambiguation, information sources, performance bounds, dictionary and supervised machine learning approaches. Naive Bayes classifiers. Readings: M&S Sec 7.0-7.3, Sec 7.5 References: Computational Linguistics Vol 24 No 1, 1998 Special Issue on Word Sense Disambiguation (particularly the Introduction)	HW #3: n‑grams ps pdf HW #4: WSD rtf	HW #2
	Naïve Bayes models. Readings: Tom Mitchell Machine Learning, pp. 177-184.
Section	Accessing corpora at Stanford; linguistic annotation Corpora Handout.doc
Week 4
Monday, 19 Apr 04 Lecture slides ps pdf Paying attention (XLS)	POS tagging: Part of speech tagging. Available information sources. Readings: M&S Sec 10.0-10.2; section 4.3.2 More: Mitchell Machine Learning, pp. 177-184 handout,Final Programming Project Guidelines.pdf
	Markov Models and Hidden Markov Models: Fundamental algorithms for hidden Markov models: determining the probability of an observed sequence, and the maximum probability state sequence (the Viterbi algorithm). Readings: M&S Sec 9.0-9.3.2
Wednesday, 21 Apr 04 Lecture Slides ps pdf Comes across (XLS)	Named Entity Recognition and Information Extraction: extracting semantic tokens (names of people, companies, prices, times, etc.) from text, use of cascades, identifying collocations and terminological phrases. Machine learning methods for IE over annotated data. Autoslog and HMM-based techniques. System evaluation: accuracy, precision and recall, F measure. Readings: Dayne Freitag and Andrew McCallum. 2000. Information Extraction with HMM Structures Learned by Stochastic Optimization. AAAI-2000; M&S section 8.1 Reference: Ion Muslea: "Extraction Patterns for Information Extraction Tasks: A Survey", AAAI-99 Workshop on Machine Learning for Information Extraction.		HW #3
	Hidden Markov Models Topics: Baum-Welch reestimation of parameters of HMM. The limited usefulness of this in part of speech tagging. Successful use in IE. EM as data clustering. Readings: M&S from section 9.3.3-9.5.
Section	Hidden Markov Models workshop: Working through HMMs: Jason Eisner's spreadsheet on EM for HMM's. More of Jason Eisner's HMMs
Week 5
Monday, 26 Apr 04 Lecture Slides ps pdf	POS Tagging and other sequence problems continued: Other approaches to and issues that arise in part of speech tagging. Unknown words. Different tagsets.		HW #2 Solutions ps pdf
	Discriminative methods: Logistic regression/Maxent classifiers.
Wednesday, 28 Apr 04 Lecture Slides ps pdf	Conditional/discriminative sequence models applied to NLP tasks. Chunking and segmentation. (Midquarter eval)	HW #5: POS ps pdf	HW #4
	Linguistic discrimination: designing features for discriminative classifiers
Section	Information extraction for the web: wrapper induction and related techniques, ppt
Week 6
Monday, 3 May 04 Lecture slides ppt	Probabilistic parsing Readings: M&S chapter 12 through section 12.1.7, and sec 8.3		HW #3 Solutions ps pdf
	Probabilistic Context-Free Grammars: probabilistic grammars. Calculating the probability of a string from a structured model. Choosing the highest probability parse. Readings: M&S chapter 11
Wednesday, 5 May 04 Lecture slides ppt	Modern probabilistic parsing Reading: (M&S chapter 12) and M&S section 8.3 Reference: Eugene Charniak. A Maximum-Entropy-Inspired Parser Proceedings of NAACL-2000. Eugene Charniak. Statistical techniques for natural language parsing AI Magazine. (1997). Eugene Charniak. 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).	HW #6: PCFG ps pdf	HW #5 ps pdf
	Attachment ambiguities: prepositional phrases, conjunctions, noun compounds; psycholinguistic models, linguistic features
Section	PCFGs and probablistic parsing, ppt
Week 7
Monday, 10 May 04 Lecture slides ps pdf	Term and attribute-value unification; feature grammars and unification-based parsing		FinalP Abstract
	Semantic representations for NLP: (Typed) lambda calculus, compositionality Readings: handout: An Informal but Respectable Approach to Computational Semantics ps pdf
Wednesday, 12 May 04	Building semantic representations (2): rule-to-rule semantic translation. Manipulating semantic forms. Syntax-semantics interfaces. Readings: handout I. Androutsopoulos et al. Language Interfaces to Databases http://citeseer.ist.psu.edu/androutsopoulos95natural.html	HW #7: Semantics ps pdf	HW #6
Section	Semantic representations and logical reasoning, ppt
Week 8
Monday, 17 May 04 Lecture Slides ps pdf	Question answering: TREC-style robust QA, natural language database interfaces. Interface to knowledge representations. Reference: Marius Pasca, Sanda M. Harabagiu: High Performance Question/Answering. SIGIR 2001: 366-374.
Wednesday, 19 May 04 Lecture Slides ps pdf	Dialogue and discourse systems; rhetorical structure; planning and requests Readings: handout Reference: Gazdar & Mellish, ch. 10		HW #7
Section
Week 9
Monday, 24 May 04 Lecture Slides ps pdf	Machine translation: rule-based and statistical approaches; sentence alignment. Readings: M&S chapter 13. Kevin Knight. A Statistical MT Tutorial Workbook. ms., August 1999.
Wednesday, 26 May 04 Lecture Slides ps pdf	Grammar Induction: can one do unsupervised learning of linguistic structure? (And why is it hard.)
Section
Week 10
Monday, 31 May 04	Memorial Day holiday - no class
Wednesday, 2 Jun 04	Project Mini Presentations.		FinalP
Finals Period - time to visit the beach!