Schedule of Topics

This is the schedule of topics for an advanced seminar in natural language processing, focused on the foundations of cutting-edge methods in NLP. Foundations, as used here, are the things that the cutting-edge research papers assume you already understand.

To the extent possible, the readings here are available on the Web. "Additional readings" are optional links pointing either to material you should already know (but might want to review) or to related material you might be interested in.

Some topic areas may take longer than expected, so keep an eye on the class mailing list or e-mail me for "official" dates..

[September 2]
Topic Area 1

• Topics:
  • Administrivia and course overview
  • Maximum likelihood estimation
  • Optimization and search: big picture
• Reading(s):
  • S. Purcell, Maximum Likelihood Estimation, Sections 1-3.
  • Numerical Recipes in C, Chapter 15 (Modeling of Data), Sections 15.0 15.1 15.2
  • Numerical Recipes in C, Section 10.9, Simulated Annealing Methods
• Assignment 1 (due next class)
  • Version for less experienced programmers: Write a program that reads in a text file and produces a file containing unigram, bigram, and trigram MLE probability estimates. Write a second program that reads the data file, inputs text strings one per line, and produces as output the unigram, bigram, or trigram model probability for the string. Feel free to exploit Pedersen's N-gram Statistics Package.
  • Exercise for more experienced programmers: same exercise but using character N-grams up to arbitary N. (You can hard-code N.)
• Additional reading
  • Manning and Schuetze, Chapter 2, "Mathematical Foundations"
  • Mathworld: Bernoulli Distribution
  • Mathworld: Maximum Likelihood
  • Cover and Thomas, Chapter 2, "Entropy, Relative Entropy, and Mutual Information"

  • Dan Melamed's simulated annealing software
  • Simulated annealing info and software

[September 9]
Topic Area 2

• Topics:
  • Smoothing
• Reading(s):
  • Stanley Chen and Joshua Goodman (1998), An Empirical Study of Smoothing Techniques for Language Modeling (1998 techreport)
• Assignment 2 (due next class)
  • Extend the previous assignment so your language model estimates use smoothed probabilities. Use any smoothing method you like except add-K. Feel free to exploit Dan Melamed's Simple Good-Turing smoothing software.
• Additional reading
  • Stanley Chen and Joshua Goodman (1996), An Empirical Study of Smoothing Techniques for Language Modeling (1996 ACL paper) (N.B. The 1998 techreport is much more illuminating: it's much longer but the authors made good use of the space to create a more tutorial, accessible presentation.)
  • Joshua Goodman (2000) "Putting it All Together: Language Model Combination"
  • Joshua Goodman (2001), A Bit of Progress in Language Modeling: Extended Version. (Contains lots of useful discussion, real-world implementation details, and editorial commentary).
  • Smoothing discussion in Manning and Schuetze

[September 16 and 23]
Topic Area 3

• Topics:
  • EM algorithms Note: this topic area is scheduled for two meetings.
• Reading(s):
  • Jason Eisner, Lagrange multipliers
  • Manning and Schuetze, Chapter 9 (will be available in course reserve folder)
  • Adam Berger, Convexity, Maximum Likelihood and All That (sections 1 and 2).
  • Jeff Bilmes (1998), A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. (Focus on discrete models only.)
• Assignment 3 (Due Monday, Oct 11)
  • Option 1. Define language model uses linear interpolation to combine evidence from models at the word level and the character level. (The previous assignments provide you with implementations of these component models. Clever, huh?) Train the coefficients of the interpolated model using EM. Evaluate the perplexity of this model versus the individual component models on unseen test data.
  • Option 2. Consider an "aggregate bigram model" where p(w2|w1) = sum_{c in C} p(w2|c) x p(c|w1). (C is a hidden variable ranging over a set of classes {c1,...,cN} with, say, N=16.) Come up with (do not look up!) an EM algorithm for estimating the parameters of this model. Implement your algorithm, train on a large sample of English, and compare the probabilities of "colorless green ideas sleep furiously" versus "furiously sleep ideas green colorless".
• Additional reading
  • Dan Klein's Lagrange Multipliers without Permanent Scarring
  • LR Rabiner, "A tutorial on HMM and selected applications in speech recognition", In Proc. IEEE, Vol. 77, No. 2, pp. 257-286, Feb. 1989.
  • Jason Eisner's Interactive Spreadsheet for Teaching the Forward-Backward Algorithm (TNLP 2002)
  • A cute movie showing the Viterbi algorithm in action (link stolen from Dan Jurafsky's speech course)
  • And if the Viterbi movie wasn't enough petty larceny for you, how about Dan Jurafsky's nice lecture notes on the forward-backward algorithm?
  • Mark Liberman, Colorless Green Probability Estimates
  • Gliozzo, Magnini, and Strappavara, Unsupervised Domain Relevance Estimation for Word Sense Disambiguation

[September 30]
Topic Area 4

• Topics:
  • Weighted finite state transducers
• Reading(s):
  • Mehryar Mohri and Michael Riley (2002). Tutorial on Weighted Finite-State Transducers in Speech Recognition, (Part 1), International Conference on Spoken Language Processing 2002 (ICSLP '02), Denver, Colorado, September 2002.
  • Hobbs et al. (1996), FASTUS: A Cascaded Finite-State Transducer for Extracting Information from Natural-Language Text.
  • Fernando C. N. Pereira and Michael Riley. Speech Recognition by Composition of Weighted Finite Automata. In E. Roche and Y. Schabes, editors, Finite-State Language Processing. MIT Press, Cambridge, Massachusetts. 1997.
• Assignment (for extra credit, due Nov 16)
  • Using WFSTs for OCR Error Correction
• Additional reading
  • Richard Sproat's lecture notes on a brief introduction to weighted finite state machines
  • Steven Abney (1996) Partial Parsing via Finite-State Cascades
  • Knight and Graehl (1997), "Machine Transliteration"
  • S. Kumar and W. Byrne (2003), A Weighted Finite State Transducer Implementation of the Alignment Template Model for Statistical Machine Translation
  • AT&T FSM library

[October 7]
Topic Area 5

• Guest leader: David Chiang
• Topics:
  • Parsing as inference
  • Semirings and parsing
• Reading(s):
  • Jason Eisner, Parameter estimation for probabilistic finite-state transducers, ACL 2002. (Focus is on Section 4.)
  • Shieber, Schabes, and Pereira (1995), "Principles and Implementation of Deductive Parsing", J. Logic Programming 24(1-2), pp. 3-36. (You can skip section 4 if you're not interested.)
  • Joshua Goodman (1999), Semiring Parsing, CL 25(4), 573-605.
    (Note: there is an erratum on p. 592, Fig. 7. You can skip section 4, as we'll just discuss Eisner's method for calculating expectations.)
  • What is it with "Section 4"???! :-)
• Assignment
  • Optional exercise: Applying semirings to ATTM decoding
• Additional reading (and David's comments)
  • Lari and Young, 1990. Applications of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language 4, 35-56. (For some reason this, and not the original Baker paper, is the standard reference. The derivation of the update equations is not as simple as it could be, I think.)
  • Nederhof, 2003. Weighted deductive parsing and Knuth's algorithm. CL 29(1), 135-143. (On best-first parsing. There is a similar paper by Klein and Manning (IWPT, 2001), but this is much simpler. However, the proofs in section 4 are spotty.)
  • Goodman (1997). Global thresholding and multiple-pass parsing", EMNLP.
  • Chiang, 2003, Mildly context sensitive grammars for estimating maximum entropy models . Conference on Formal Grammar. (Only tangentially related. Implicitly uses the idea of semirings to generalize Inside-Outside and conditional random fields to a large class of grammar formalisms beyond CFG.)

[October 14]
Interlude: alignment templates for translation: models, decoding, and evaluation

• Topics and leaders:
  • Background on IBM statistical MT models
  • ATTM modeling and decoding
  • Evaluation
• Reading(s):
  • Kevin Knight (1999), A Statistical MT Tutorial Workbook
  • Philipp Koehn (2004), Pharaoh: a Beam Search Decoder for Phrase-Based Statistical Machine Translation Models (also: his slides)
  • Kishore Papineni, Salim Roukos, Todd Ward, Wei-Jing Zhu (2001), Bleu: a Method for Automatic Evaluation of Machine Translation
  • Philipp Koehn (2004), Statistical Significance Tests for Machine Translation Evaluation
• Assignment (due next class)
  • Another opportunity to do last week's optional exercise: Applying semirings to ATTM decoding.
• Additional reading
  • Peter F. Brown, John Cocke, Stephen A. Della Pietra, Vincent J. Della Pietra, Fredrick Jelinek, John D. Lafferty, Robert L. Mercer, Paul S. Roossin (1990), A Statistical Approach to Machine Translation
  • Brown et al. (1993), The Mathematics of Statistical Machine Translation: Parameter Estimation
  • Franz Och, F. Och (2002), Section 5.1 (phrase extraction) and Chapter 6 (search, especially Section 6.3) of Statistical Machine Translation: From Single Word Models to Alignment Templates. Ph.D. thesis, RWTH Aachen, Germany.
  • Franz Och (2003), Minimum Classification Error Training for Statistical Machine Translation.
  • Chin-Yew Lin and Eduard Hovy (2003), Automatic Evaluation of Summaries Using N-gram Co-Occurrence Statistics
  • Lavie, A., K. Sagae and S. Jayaraman (2004), The Significance of Recall in Automatic Metrics for MT Evaluation
  • JHU summer workshop 2003 statistical MT bibliography
  • Lin and Och (2004), Automatic Evaluation of Machine Translation Quality Using Longest Common Subsequence and Skip-Bigram Statistics
  • Babych and Hartley (2004), Extending the BLEU MT Evaluation Method with Frequency Weightings
  • More summarization evaluation references

[October 21]
Topic Area 6

• Topics:
  • MT evaluation discussion (carried over from last week)
  • Supervised classification: Naive Bayes
• Reading(s):
  • David Lewis (1998), "Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval"
• Assignment (due next class)
  • Start putting together your class project idea.
• Additional reading
  • More recent literature on naive Bayes text classification.
  • WEKA Web page
  • WEKA tutorial

Related Talk on November October 25

[October 28]
Topic Area 7

• Topics:
  • Decision lists
  • Support vector machines
• Reading(s):
  • David Yarowsky (1994), "Decision Lists For Lexical Ambiguity Resolution: Application to Accent Restoration in Spanish and French"
  • Schoelkopf and Smola (2002), "Learning with Kernels", Chapter 1 (collated from the on-line book).
• Assignment
  • Class project sketch/proposal due Monday Nov 1
• Additional reading
  • Yarowsky (1999), "Hierarchical Decision Lists for Word Sense Disambiguation"
  • Goodman, "An incremental decision list learner"
  • Marti Hearst (1998) "Support Vector Machines"
  • T. Joachims (1997), "Text Categorization with Support Vector Machines: Learning with Many Relevant Features"
  • Schoelkopf and Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond, Chapter 7; see also the appendix on mathematical background.
  • Andrew Ng, Lecture notes on support vector machines
  • Burges (1998), A Tutorial on Support Vector Machines for Pattern Recognition
  • Martin Law, An introduction to support vector machines (slides)

[November 4]
Topic Area 8

• Topics:
  • Supervised classification with special attention to unlabeled or noisy examples
    • Co-training
    • Boosting
• Reading(s):
  • David Yarowsky (1995), Unsupervised Word Sense Disambiguation Rivaling Supervised Methods
  • Steven Abney, Robert Schapire, and Yoram Singer, Boosting Applied to Tagging and PP Attachment
• Assignment (for extra credit, due Nov 16)
  • Using WFSTs for OCR Error Correction
• Additional reading
  • Hwa et al., Corrected Co-training for Statistical Parsers
  • Robert Schapire (1999), A Brief Introduction to Boosting
  • Steedman et al. (2003), Bootstrapping Statistical Parsers from Small Datasets
  • Avrim Blum and Tom Mitchell (1998), Combining Labeled and Unlabeled Data with Co-Training
  • Schapire (2002), The Boosting Approach to Machine Learning: An Overview
  • Leo Breiman (1996), Bagging Predictors
  • Abney, Understanding the Yarowsky Algorithm
  • Rudin et al., Dynamics of Boosting (shows that AdaBoost can converge to a non-maximum margin)
  • Rudin et al., Analysis of Boosting Algorithms using the Smooth Margin function (introduces two new boosting algorithms that maximize the margin, plus more analysis of AdaBoost)

Related Talk on November 8

[November 11]
Topic Area 9

• Topics:
  • Discriminative reranking
• Reading(s):
  • Michael Collins (2000), Discriminative Reranking for Natural Language Parsing
  • Franz Och, Minimum error rate training for statistical machine translation.
    (Note: there is a gaping hole in this paper around equations 8 and 9, which the presenters will attempt to fill during the in-class presentation using information from outside the paper.)
• Assignment
  • none
• Additional reading
  • Och et many al., A Smorgasbord of Features for Machine Translation, NAACL '04.
  • Och & Ney, Discriminative Training and Maximum Entropy Models for Statistical Machine Translation, ACL 2002.
  • Shen, Sarkar and Och Discriminative Reranking for Machine Translation NAACL '04.

[November 18]
Topic Area 10

• Guest lecturer: Lise Getoor
• Topics:
  • Graphical models
• Reading(s):
  • Chapter from draft book on graphical models (available only in hardcopy)
• Assignment
  • none
• Additional reading
  • Kevin Murphy (1998), A Brief Introduction to Graphical Models and Bayesian Networks

[November 25]
No class. Happy Thanksgiving!

[December 2]
Topic Area 11

• Guest leader: Noah Smith
• Topics
  • Log-linear and maximum entropy models and conditional random fields
• Reading(s):
  • Adam Berger's max ent tutorial
  • Adwait Ratnaparkhi. A Maximum Entropy Model for Part-Of-Speech Tagging. In Proceedings of the Empirical Methods in Natural Language Processing Conference, May 17-18, 1996. University of Pennsylvania.
  • See Noah's slides plus a very nice handout containing mathematical details. (Note: you might need texpoint, the tool that lets you put latex equations into Powerpoint slides, to view the formulas properly.)
• Assignment (due next class)
  • none
• Additional reading
  • Highly recommended: 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.
  • Abney (1997), Stochastic Attribute-Value Grammars (?)
  • Mark Johnson, Joint and conditional estimation of tagging and parsing models
  • Klein and Manning, "Conditional Structure versus Conditional Estimation in NLP Models"
  • Stephen Della Pietra, Vincent Della Pietra, and John Lafferty (1997), Inducing features of random fields
  • Hannah Wallach (2004) Conditional Random Fields: An Introduction
  • John Lafferty, Andrew McCallum, Fernando Pereira (2001), Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

[December 9]

• Last meeting: Project presentations.
  Final projects are due by December 19 at 11:59pm.

Some topics of potential interest that we're not covering

• Eisner's Dyna programming language
• Evaluation and significance testing
• Clustering
• Suffix trees
• Using evidence from the Web
• Minimum Bayes risk
• Minimum description length (MDL)
• Osborne notes