6.881: Natural Language Processing

[main] | [administration] | [homeworks] | [links]

Announcements:

Homework #2 is released, and is due on 11/2/2004
Homework #1 is released, and is due on 10/14/2004
Note that the time has changed, from now on the class will be at 3:00--4:30 (both Tuesdays and Thursdays), at the same room.

Instructor: Regina Barzilay, G468 Stata Center
Office Hours: Tues 9:30--10:30, or by appointment
Time & Location: Tues & Thurs 15:00--16:30, 2-147

The syllabus is still subject to change.

Date	Topic	References
9/9	Introduction and Overview [slides] [pdf]	Lillian Lee I'm sorry Dave, I'm afraid I can't do that: Linguistics, Statistics, and Natural Language Processing circa 2001 To appear in the National Academies' study on the Fundamentals of Computer Science Babel Fish Translation Columbia Newsblaster
9/16	Basic Language Statistics; Zipf's Law [slides] [pdf]	Manning&Schuetze Section 1.4 Rie Kubota Ando and Lillian Lee Mostly-Unsupervised Statistical Segmentation of Japanese: Applications to Kanji. First Conference of the NAACL, pp. 241--248, 2000. Michel Banko and Eric Brill Mitigating the Paucity-of-Data Problem: Exploring the Effect of Training Corpus Size on Classifier Performance for Natural Language Processing First Conference of HLT, 2001. Wentian Li Random texts exhibit Zipf's-law-like word frequency distribution. IEEE Transactions on Information Theory, 38(6), pp. 1842-1845. Frank Keller and Maria Lapata and Olga Ourioupina Using the Web to Overcome Data Sparseness Conference on EMNLP, 2002. George Kinglsey Zipf Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.
9/21	Language Models; Smoothed Estimation [slides] [pdf]	Jurafksy&Martin Section 6 P.F. Brown, V.J. Della Pietra, P.V. deSouza, J.C. Lai, and R.L. Mercer Class-based n-gram models of natural language. Computational Linguistics, 18(4), pp. 467-479 P.F. Brown, V.J. Della Pietra, S.A. Della Pietra, J.C. Lai, and R.L. Mercer An estimate for an upper bound for the entropy of English. Computational Linguistics, 18(1), pp. 31-40 Stanley F. Chen and Joshua Goodman An Empirical Study of Smoothing Techniques for Language Modeling The ACL Conference, 1996, pp. 310-318 Stanley F. Chen and Ronald Rosenfeld A Survey of Smoothing Techniques for ME Models IEEE Transactions on Speech and Audio Processing, 8(1), 2000, pp. 37-50 Kenneth W. Chuch and William A. Gale A Comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech and Language, 5, 1991, pp. 19-55 Frederick Jelinek Statistical Methods for Speech Recognition The MIT Press, 1998 Lillian Lee Similarity-Based Approaches to Natural Language Processing PhD Thesis, Harvard, 1997.
9/23	Tagging; Tranformation Based Learning; HMM Taggers [slides] [pdf]	Manning&Schutze Section 10 Eric Brill Transformation-based error-driven learning and natural language processing: A case study of part-of-speech tagging Computational Linguistics, 21(4), pp. 543-566, 1995 Eric Brill Unsupervised Learning of Disambiguation Rules for Part of Speech Tagging Workshop on Very Large Corpora, pp. 1995 E. Charniak, C. Hendrickson, N. Jacobson, and M. Perkowitz Equations for part-of-speech tagging AAAI Conference, 1993, pp.784-789
9/28	Maximum Entropy Tagger [slides] [pdf]	Manning&Schutze Section 16.2.1 Adwait Ratnaparkhi A Maximum Entropy Part-Of-Speech Tagger EMNLP Conference, 1986 Adawait Ratnaparkhi Maximum Entropy Models for Natural Language Ambiguity Resolution Ph.D. Dissertation. University of Pennsylvania, pp.6-18 J.N. Darroch and D. Ratcliff Generalized Iterative Scaling for Log-linear Models The Annals of Mathematical Statistics, 43(5), pp. 1470-1480
9/30	Introduction to Syntax; Probabilistic Context Free Grammars	Slides of Mike Collins Jurafsky&Martin Section 9 Taylor L. Booth and Richard A. Thompson Applying probability measures to abstract languages IEEE Transactions on Computers C-22, pp. 442-450 Mark Gold Language identification in the limit Information and Control, 1967, pp.447-474
10/5	Syntactic Parsing	Slides of Mike Collins Michael Collins Three Generative, Lexicalised Models for Statistical Parsing ACL Conference, 1997
10/7	Introduction to EM	R. Durbin, S. Eddy, A. Krogh and G. Mitchison The EM Algorithm Biological Sequence Analysis, Cambridge University Press, 1998
10/12	Unsupervised Grammar Induction [slides] [pdf]	Manning&Schutze Section 11.3.4, 11.4 Glenn Carrol and Eugene Charniak Two experiments on Learning Probabilistic Dependency Grammars from Corpora Technical Report CS-92-16, Brown University, 1992. Noam Chomsky Rules and Representations Oxford: Basil Blackwell, 1980, p. 34. Alexander Clark Unsupervised induction of stochastic context-free grammars using distributional clustering Conference on Natural Language Learning, 2001. Mark E. Gold Language identification in the limit. Information and Control, 10, pp. 447-474. James J. Horning A study of grammatical inference PhD thesis, Stanford, 1969. K. Lari and S. J. Young The estimation of stochastic context-free grammars using the Inside-Outside algorithm Computer Speech and Language, 1990, 4, pp.35-56. C. Manning Grammar Induction: can one do unsupervised learning of linguistic structure? (And why is it hard. Geoffrey K. Pullum Learnability, Hyperlearning, and the Poverty of the Stimulus Annual Meeting of the Berkeley Linguistics Society, 1996 Fernando Pereira and Yves Schabes Inside-Outside reestimation from Partially Bracketed Corpora The ACL Conference, 1992, pp. 128-135. Andreas Stolcke and Stephen Omohundro Best-first Model Merging for Hidden Markov Model Induction Technical Report, Berkeley, 1994. Menno van Zaanen ABL: Alignment-Based Learning COLING 2000, pp. 961-967
10/14	Distributional Similarity; Clustering [slides] [pdf]	Manning&Schutze Section 14 JurafskyMartin Section 16.2 P.F. Brown, V.J. Della Pietra, P.V. deSouza, J.C. Lai, and R.L. Mercer Class-based n-gram models of natural language. Computational Linguistics, 18(4), pp. 467-479 C. Fellbaum (ed.) WordNet: An Electronic Lexical Database MIT Press, Cambrisge, MA, 1998 Fernando Pereira, Naftali Tishby and Lillian Lee Distributional clustering of English words The ACL Conference, 1993, pp. 183-190
10/19	Distributional Similarity (cont.) [slides] [pdf]	Manning&Schutze Section 14, 15.4
10/21	Word Sense Disambiguation; Co-training [slides] [pdf]	Manning&Schutze Section 7 David Yarowsky Decision lists for lexical ambiguity resolution: Application to accent restoration in Spanish and French ACL 1994, pp. 88-95 David Yarowsky Unsupervised word sense disambiguation rivaling supervised methods ACL 1995, pp. 189-196 Diana McCarthy, Rob Koeling, Juliee Weeds and John Carroll Finding Predominant Word Senses in Untagged Text ACL 2004, pp. 280-287
10/26	Text Segmentation [slides] [pdf]	Marti Hearst Multi-paragraph segmentation of expository text Proceedings of the ACL, pp. 9-16, 1994. Lev Pevzner and Marti Hearst A Critique and Improvement of an Evaluation Metric for Text Segmentation Computational Linguistics, pp. 9-16, 1994. Rebecca J. Passonneau and Diane J. Litman Intention-based Segmentation: Human Reliability and correlation with linguistic cues Proceedings of the ACL, pp. 148-155, 1993. Barbara Grosz and Julia Hirschberg Some intonational charachteristics of discourse. Proceeding of the ICSLP, 1992. Michel Galley, Kathleen McKeown, Eric Fosler-Lussier and Hongyan Jing Discourse Segmentation of Multi-Party Conversation Proceedings of the ACL, 2003.
10/28	Learning Disourse Structure [slides] [pdf]	Simone Teufel and Marc Moens What's yours and what's mine: Determining Intellectual Attribution in Scientific Text Proceedings of the EMNLP and VLC, 2000 Pablo Duboue and Kathleen R. McKeown Empirically Estimating Order Constraints for Content Planning in Generation Proceeding of the ACL/EACL, 2001. Regina Barzilay and Lillian Lee Catching the Drift: Probabilistic Content Models, with Applications to Generation and Summarization Proceedings of the NAACL/HLT, 2004.
11/2	Rhetorical Parsing [slides] [pdf]	William Mann and Sandra Thompson Rhetorical Structure Theory: Toward a functional thoery of text organization Text 8(3), 1988 Daniel Marcu Building Up Rhetorical Structure Trees Proceeding of the AAAI, 1996 Daniel Marcu and Abdessamad Echihabi An Unsupervised Approach to Recognizing Discourse Relations Proceeding of the ACL/NAACL, 2002
11/4	Text Summarization [slides] [pdf]	Julian Kupiec and Jan O. Pedersen and Francine Chen A Trainable Document Summarizer Proceedings of the SIGIR, 1995. Dan Melamed A Portable Algorithm for Mapping Bitext Correspondence. Proceedings of ACL, 1997. William A. Gale and Kenneth Ward Church A Program for Aligning Sentences in Bilingual Corpora Proceedings of the ACL, 1991 Daniel Marcu The automatic construction of large-scale corpora for summarization research Proceedings of the SIGIR, 1999 Regina Barzilay and Noemie Elhadad Sentence Alignment for Monolingual Comparable Corpora Proceedings of EMNLP, 2003 Document Understanding Conference (2004)
11/9	Summarization (cont.)
11/16	Midterm
11/18	Information Retrieval
11/23	Machine Translation
11/30	Machine Translation
12/2	Machine Translation
12/7	Project Presentations
12/9	Project Presentations