Prerequisites

• Finite state grammars, automata, and transducers
• Context-free grammars and chart parsers (CKY, Earley)
• Computational complexity (big-O notation)

Main Sources for Readings:

• (JM) Dan Jurafsky and Jim Martin, Speech and Language Processing: An Introduction to Speech Recognition, Natural Language Processing, and Computational Linguistics, draft in progress (version of 10 June 1998).
• (KS) Brigitte Krenn and Christer Samuelsson, The Linguist's Guide to Statistics
• Also see other in syllabus (many with Web links)

Day 1

• Practical issues
  • Character codes (tutorial by Jukko Korpela)
  • Tokenization (KS 3.2)
  • Sentence boundary detection (KS 3.2, Reynar and Rathnaparkhi ANLP-1997)
  • Stemming and lemmatization (JM 3.4)

• Probability and probability estimation
  • Probability, independence, conditional probability (KS 1.1-1.2.4)
  • Bayes Theorem (KS 1.2.5)
  • Maximum likelihood probability estimates
  • Smoothing methods: add-k, Good-Turing, interpolated (JM 6.2, 6.3)

• Measures of lexical association
  • Mutual information (Church and Hanks, ACL-1989)
  • Hypothesis testing
  • Chi-squared (Georgetown chi-square tutorial)
  • Likelihood ratio (Dunning, CL 19(1):61-74, 1993)

Lab for Day 1:Bigram Counts and Association Statistics.

Day 2

• Language models
  • The noisy channel model
  • N-gram (Markov) models (JM 6.0-6.1, KS 2.1-2.1.3)
    • Application: language identification (Dunning (1994), Statistical Identification of Language. Technical report. CRL MCCS-94-273. Computing Research Lab, New Mexico State University)
  • Hidden Markov models (JM 7.1-7.2)
    • Application: POS tagging (JM 7.1-7.2)
  • Probabilistic CFGs (Charniak (1997), "Statistical Techniques for Natural Language Parsing", AI Magazine 18(4), Winter 1997, pp. 33-44; for more reading: KS chapter 4)
  • Lexicalized probabilistic parsing (Charniak sec. 5)

• Brief intro to information-theoretic concepts
  • Entropy (JM 6.8)
  • Relative entropy [KL divergence]
  • Average mutual information
  • Maximum entropy (Rathnaparkhi (1997) sections 1-3 [overview]; also of interest: Eric Ristad's maximum entropy modeling toolkit.)

Lab for Day 2:Exercise Using an HMM. (You can either download the code now or follow the instructions given in the Lab.)

Day 3

• Performance Evaluation (KS Ch. 3)
  • Lower and upper bounds
  • Agreement and chance-corrected agreement (Carletta (1996), Assessing agreement on classification tasks: the kappa statistic, CL 22(2):249-254.)
  • Evaluation of part-of-speech tagging
  • Evaluation of sense disambiguation (Resnik and Yarowsky (1997), A perspective on word sense disambiguation methods and their evaluation, Proc. ACL SIGLEX Workshop at ANLP 1997.)
  • Evaluation of parsers
  • Evaluation of IR systems
  • Evaluation of MT systems
  • Decision-based evaluation (Resnik (1997), Evaluating Multilingual Gisting of Web Pages, Technical Report UMIACS-TR-97-39, presented at AAAI Symposium on Natural Language Processing for the World Wide Web, Stanford, CA, March 1997.)

• Class-based probabilistic methods (Resnik, in revision [to appear in JAIR])
  • WordNet and class-based probabilities
  • Measures of semantic similarity
  • Methods for word sense disambiguation