This is the schedule of topics for Computational Linguistics I, Fall 2006.
Readings are from Dan Jurafsky and James Martin, "Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics", Prentice-Hall (2000), unless otherwise specified. The "other" column has other info, e.g. pointers to material you should already know (but might want to review), or to related material you might be interested in, or names of guest lecturers.
THIS SCHEDULE IS A WORK IN PROGRESS!
In addition, some topic areas may take longer than expected, so keep
an eye on the class mailing list or e-mail me for "official"
dates.
| Class | Topic | Readings* | Assignments | Other |
|---|---|---|---|---|
| Aug 30 | Administrivia, semester plan; overview of NLP | Ch 1 | Assignment 1 | |
| Sep 6 | FSAs and regular expressions | Ch 2 | Guest lecturer: Adam Lopez | |
| Sep 13 | Morphology and finite-state transducers | New Ch 3 | Assignment 2 | |
| Sep 20 | N-gram language models | New Ch 4: sections TBA | Assignment 3 | |
| Sep 27 | Hidden Markov models (HMMs) | New Ch 5, except sections 5.6, 5.7; main focus is on 5.5. See also the Wikipedia entry on dynamic programming | ||
| Oct 4 | Expectation-Maximization and HMM training | New Ch 5, same sections as last week. Optional reading: Adam Berger, Convexity, Maximum Likelihood, and All That (sections 1 and 2), notes to accompany Berger, and simple perl example of the linear interpolation EM update. | Assignment: play with EM for learning lambdas for linear interpolation, convincing yourself it works, and do Assignment 4, turning in hardcopy (or e-mail of a hardcopy) | |
| Oct 11 | Context-free grammars (CFG), linguistic phenomena, and complexity | Ch 9 | Guest lecture: Smaranda Muresan | |
| Oct 18 | Context-free parsing: parsing as search | Ch 10.1-10.3; see also Wikipedia: CYK algorithm; Ch 10.4 and Shieber et al. (1995) sections 1-3 and 5 up to p. 28 | Take home midterm handed out. | |
| Oct 25 | Context-free parsing: chart parsers | See New Ch 12 for equivalents of the readings in Ch 10. | Assignment 5 | |
| Nov 1 | Feature structures and unification | Ch 11, lecture notes | Assignment 6 | Guest lecture: Smaranda Muresan |
| Nov 8 | Special event. Attend Marc Hauser's talk: Language, Mathematics and Morality, Maryland Room, Marie Mount Hall, 3-5pm | Recommended: (a) Hauser, M.D., Barner, D., & O'Donnell, T. (in press): Evolutionary linguistics: a new look at an old landscape. In: Language, Learning, and Development. (b) O'Donnell, T. J., Hauser, Marc D., and Fitch, W.T. (2005) Using mathematical models of language experimentally. In: Cognitive Sciences, vol. 9, no. 6, June 2005. | ||
| Nov 15 | Tree-adjoining grammars | Pages 1-13 and 27-33 (Section 8) of Aravind Joshi and Yves Schabes, Tree-Adjoining Grammars, in Handbook of Formal Languages, G. Rozenberg and A. Salomaa (eds.), Vol. 3, Springer, Berlin, New York, 1997, 69-124. | Assignment 7 | Additional pointers to important TAG-related papers are in these notes for a seminar lecture given by Aravind Joshi in January 2006. Also possibly of interest: Searls, D. B. (2002) The language of genes. Nature, 420:211--217. Also briefly discussed (for assignment): Robert Moore, "Improved Left-Corner Chart Parsing for Large Context-Free Grammars" [local link]. |
| Nov 22 | No class: Happy Thanksgiving! | Eat! | ||
| Nov 29 | Semantics |
(a) Mark Steedman, Categorial Grammar (tutorial overview), Lingua, 90:221--258, 1993.
(b) Patrick Blackburn and Johann Bos, Computational Semantics, Theoria 18(1), pp. 27-45, 2003, (c) Jurafsky and Martin, New Ch 16 (up through Section 16.5) |
||
| Dec 6 | Tentative: Lexical semantics | Tentative: Jurafsky and Martin, New Ch 19 | Take home final handed out |