LINGUIST 289 (Jurafsky/Kay): The History of Computational Linguistics

LING 289: History of Computational Linguistics
Winter 2011

Intellectual history of computational linguistics and natural language processing, together with related aspects of dialogue and speech processing, using primary sources.

Dan Jurafsky, jurafsky@stanford.edu 460-117
Martin Kay, mjkay@stanford.edu, 460-119

Tues, 2:15-5:05pm, 460-126 Email: linguist289-win1011-staff@lists.stanford.edu
Required Work

Leading Class Discussion: One or to three times during the quarter you will run the discussion (for a half-session).
Readings: Before class, read the papers and write 3 "questions or comments" on each reading. This means on weeks with 3 readings we expect 9 question/comments. The questions or comments can be short but should be substantive and suggestive, not just a summary of the paper. Since they are due before class, we will use them to inform our discussion of the papers. Comments should be posted to the class discussion site:
http://www.piazzza.com/stanford/linguist289
Final Project: The final project should be a historical investigation of some topic in the history of computational linguistics. This can include interviewing primary figures, investigating other primary sources (letters, notebooks, eamil), or a computational project using online data.
Grade determination:
- 25% comments on readings
- 25% leading class discussion
- 10% class participation
- 40% final project

	SCHEDULE
Wk	Date	Discussants	Slides	Topic and Readings
1	Jan 4	Martin and Dan		Introduction to the Course and Brief Overview of the History of the Field
2	Jan 11	Everyone		Computational History in Computational Linguistics: the ACL Anthology Radev, Dragomir R., Joseph, Mark Thomas, Gibson, Bryan, and Muthukrishnan, Pradeep. A Bibliometric and Network Analysis of the field of Computational Linguistics. To appear, Journal of the American Society for Information Science and Technology, David Hall, Daniel Jurafsky, and Christopher D. Manning. 2008. Studying the History of Ideas Using Topic Models. In Proceedings of EMNLP 2008, 363-371. Computational History more Generally A. L. Porter, D. E. Chubin and Xiao-Yin Jin. 1988. Citations and scientific progress: Comparing bibliometric measures with scientist judgments Sean M. Gerrish and David M. Blei. 2010. A Language-based Approach to Measuring Scholarly Impact. Proceedings of the 26th International Conference on Machine Learning, Haifa, Israel, 2010 Ketan K. Mane and Katy Börner. 2004. Mapping topics and topic bursts in PNAS. PNAS vol 101, 5287-5290. *Extra: Related papers for further research* Eugene Garfield. 2001. From Computational Linguistics to Algorithmic Historiography. Text of Lazerow Lecture at University of Pittsburgh. Kevin W. Boyack, Katy Börner, Richard Klavans. 2009. Mapping the structure and evolution of chemistry research Scientometrics, Vol 29, No 1. 45-60. Tom L. Griffiths and Mark Steyvers. 2004. Finding scientific topics. PNAS, 101 Suppl 1:5228-5235, April. Christian G. Specht. 2010. Opinion: Mutations of citations. The Scientist, 16 September 2010. http://www.the-scientist.com/news/display/57689/ Dragomir R. Radev, Pradeep Muthukrishnan, and Vahed Qazvinian. The ACL anthology network corpus. In Proceedings, ACL Workshop on Natural Language Processing and Information Retrieval for Digital Libraries, Singapore, 2009 Luis M. A. Bettencourt, David I. Kaiser, Jasleen Kaur, Carlos Castillo-Chavez, and David E. Wojick. 2008. Population modeling of the emergence and development of scientific fields Scientometrics, Vol. 75, No. 3, 495-518. Howard D. White and Katherine W. McCain. 1997. Visualizing a Discipline: An Author Co-Citation Analysis of Information Science, 1972-1995. JASIS 49:4
3	Jan 18	Everyone		History of Science: Foundations Bruno Latour. 1987. Science in Action. Harvard University Press. Chapters 1-3 Thomas Kuhn. 1961. The Structure of Scientific Revolutions. Chapter 2, Chapter 6, Chapter 12. Robert K. Merton. 1961. Singletons and Multiples in Scientific Discovery. Proceedings of the American Philosophical Society 105:5, 470-486. You need to read only from section II, starting at page 475. History of Science: Relevant Theories and Examples Scott Frickel and Neil Gross (2005). A General Theory of Scientific/Intellectual Movements. American Sociological Review 70(2): 204-232. Charles Camic and Yu Xie. 1994. The Statistical Turn in American Social Science: Columbia Univeristy, 1980 to 1915 Americal Sociological Revew 59:5, 773-805. Best Practices in Conducting Oral History Extra: Related papers for further research Darin J. Arsenault, Laurence D. Smith and Edith A. Beauchamp. 2006. Visual Inscriptions in the Scientific Hierarchy: Mapping the "Treasures of Science". Science Communication 27:376-428. Steven Shapin. 1992. . History of science and its sociological reconstructions. History of Science 20: 157-211. Steven Shapin. 1994. A social history of truth: civility and science in seventeenth-century England. University of Chicago Press. Philip Mirowski. 1989. The Probabilistic Counter-Revolution, or How Stochastic Concepts came to Neoclassical Economic Theory Oxford Economic Papers, New Series, Vol. 41, No. 1, History and Methodology of Econometrics (Jan., 1989), pp. 217-235
4	Jan 25	Finite State Panel (Martin, Ron Kaplan, Lauri Karttunen+)		Finite State Models in Computational Linguistics Lauri Karttunen and Ken Beesley. Twenty-Five Years of Finite-State Morphology. Aravind K. Joshi and Phil Hopely. 1996. A parser from antiquity. Natural Language Engineering 2 (4) 291-294. Fernando C. N. Pereira and Michael D. Riley. 1997. Speech Recognition by Composition of Weighted Finite Automata. In Finite State Language Processing, edited by Emmanuel Roche and Yves Schabes. read pages 431-434 only. Jerry R. Hobbs, Douglas Appelt, Mabry Tyson, John Bear, and David Israel. 1992. SRI INTERNATIONAL: DESCRIPTION OF THE FASTUS SYSTEM USED FOR MUC-4. FOURTH MESSAGE UNDERSTANDING CONFERENCE (MUC-4), Proceedings of a Conference Held in McLean, Virginia, June 16-18, 1992. Fernando Pereira. 1990. Finite-State Approximations of Grammars. Speech and Natural Language: Proceedings of a Workshop Held at Hidden Valley, Pennsylvania, June 24-27,1990 Read the Open FST Tutorial and understand the basic idea of the Open FST Toolkit. In Memoriam Maurice Gross Dan's Interview on Jan 21, 2011 with Fernando Pereira on the origins of the AT&T finite state work (30 minutes) Just skim this: Gross, Maurice. 1989. The use of finite automata in the lexical representation of natural language page 333 of Kaplan, R.M. and Kay, M.. 1994. Regular models of phonological rule systems Computational linguistics 20,3: 331-378 Kenneth Ward Church. 1980. pages 11 and 12 of Church's masters thesis, On Memory Limitations in Natural Language Processing. Just skim this: Mehryar Mohri. Weighted Finite-State Transducer Algorithms: An Overview. In Carlos Martín-Vide, Victor Mitrana, and Gheorghe Paun, editors, Formal Languages and Applications. volume 148, VIII, 620 p., pages 551-564. Springer, Berlin, 2004. Extra: Related papers on Finite-State models for further research Kaplan, Ronald M. and Martin Kay. 1981. Phonological rules and finite-state transducers. In Linguistic Society of America Meeting Handbook, Fifty-Sixth Annual Meeting. New York. Abstract. C. Douglas Johnson. 1972. Formal Aspects of Phonological Description. Mouton. The Hague. Koskenniemi, Kimmo. 1983. Two-level morphology: A general computational model for word-form recognition and production. Publication 11, University of Helsinki, Department of General Linguistics, Helsinki. Koskenniemi, Kimmo. 1986. Compilation of automata from morphological two-level rules. In F. Karlsson, ed., Papers from the Fifth Scandinavian Conference on Computational Linguistics, pages 143-149. Karttunen, Lauri, Kimmo Koskenniemi, and Ronald M. Kaplan. 1987. A compiler for two-level phonological rules. In M. Dalrymple, R. Kaplan, L. Karttunen, K. Koskenniemi, S. Shaio, and M. Wescoat, eds., Tools for Morphological Analysis, vol. 87-108 of CSLI Reports, pages 1-61. Palo Alto, CA: Center for the Study of Language and Information, Stanford University. Kenneth Ward Church. 1980. On Memory Limitations in Natural Language Processing. MIT-LCS-TR-245. Ken's Master's thesis. Kenneth Ward Church. 1983. A Finite-State Parser for Use in Speech Recognition. ACL 1983. Fernando Pereira and Rebecca N. Wright. 1990. Finite-State Approximation of Phrase-Structure Grammars. 29th Annual Meeting of the Association for Computational Linguistics, 1991, pp. 246-255. Kenneth Church and Ramesh Patil. 1982. Coping with Syntactic Ambiguity or How to Put the Block in the Box on the Table. Computational Linguistics 8:3-4, pages 139-149.
5	Feb 1	Unification (Discussants: Dan Flickinger, Ron Kaplan, Lauri Karttunen, Martin Kay, Gerald Penn, Ivan Sag).		Unification Jurafsky and Martin. 2009. Speech and Language Processing, page 560: Historical Notes on Unification Martin Kay. 1979. Functional Grammar. Proceedings of the Berkeley Linguistics Society, 142-158. Ivan A. Sag, Ronald M. Kaplan, Lauri Karttunen, Martin Kay, Carl Pollard, Stuart Shieber, and Annie Zaenen. 1986. Unification and Grammatical Theory. Proceedings of the Fifth West Coast Conference on Formal Linguistics. Alain Colmerauer and Philippe Roussel. 1993. The birth of Prolog. Proceeding of HOPL-II: The second ACM SIGPLAN conference on History of programming languages. ACM New York, NY, USA 1993. Bert F. Green, Jr., Alice K. Wolf, Carol Chomsky, and Kenneth Laughery. 1961. Baseball: An Automatic Question-Answerer Proceedings of the IRE-AIEE-ACM '61 (Western); Papers presented at the May 9-11, 1961, western joint IRE-AIEE-ACM computer conference Kevin Knight. 1989. Unification: A Multidisciplinary Survey.. Read only sections 2, 5, and 7. ACM Computing Surveys, Vol. 21, No. 1, March 1989 Fernando C. N. Pereira and David H. D. Warren. 1980. Definite Clause Grammars for Language Analysis -- A Survey of the Formalism and a Comparison with Augmented Transition Networks. Artificial Intelligence 13, 231-278. Read only pages 231-240, and section 3.6 (pages 251-253) Extra: Related papers for further research Martin Kay. 1975. Syntactic Processing and Functional Sentence Perspective. Proceedings of TINLAP 1975. Stuart M. Shieber: An Introduction to Unification-Based Approaches to Grammmar. reprint from Microrome Publishing, Brookline, MA. Alain Colmerauer. 1970. Les systèmes-q ou un formalisme pour analyser et synthétiser des phrase sur ordinateur. Internal publication 43, Département d'informatique de l'Université de Montréal", Alain Colmerauer. 1975. Les grammaires de métamorphose GIA. Internal publication, Groupe Intelligence artificielle, Facult\'{e} des Sciences de Luminy, Universit\'{e} Aix-Marseille II, France, Nov 1975. English version, Metamorphosis grammars. In L. Bolc, (Ed.). 1978. Natural Language Communication with Computers, Lecture Notes in Computer Science 63, Springer Verlag, pp. 133-189", Fernando C. N. Pereira and Stuart M. Shieber. 1987. Prolog and Natural-Language Analysis. CSLI Publications. Robinson, Alan. 1965. A Machine-Oriented Logic Based on the Resolution Principle. Journal of the Association for Computing Machinery, Vol. 12, No. 1 (January, 1965), pp. 23-41 Interview with Alan Robinson Norvig, Peter. 1991. Correcting a widespread error in unification algorithms. Software Practice and Experience, 21, 2, 231-233, February, 1991. The Wikipedia page on IPL (Information Processing Language) and its attribute-value data structures.
6	Feb 8	First half: Adam Second half: David C		Models for Dialogue Daniel G. Bobrow, Ronald M. Kaplan, Martin Kay, Donald A. Norman, Henry Thompson and Terry Winograd. GUS, A Frame-Driven Dialog System. Artificial Intelligence, Volume 8, Issue 2, April 1977, Pages 155-173 Allen, J. F. and C. R. Perrault (1980). Analyzing Intention in Utterances. Artificial Intelligence 15(3), 143-178. Barbara J. Grosz and Candace L. Sidner. 1986. Attention, intentions, and the structure of discourse. Computational Linguistics 12, 3 (July 1986), 175-204. Montague's PTQ and its relationship to CL of the time Jerry R. Hobbs and Stanley J. Rosenschein. 1978. Making Computational Sense of Montague's Intensional Logic. Artificial Intelligence 9 (1978) 287-306. William A. Woods (1978). Semantics and Quantification in Natural Language Question Answering. Advances in Computers, 17, 1-87. Joyce Friedman and David S. Warren. 1978. A parsing method for montague grammars Linguistics and Philosophy 2 (1978) 347-372.
7	Feb 15	First half: Nikhil Second half: More on Semantics		History of Topic Modeling: Vectors, LSI/LSA, LDA Luhn, H. P. 1957. A Statistical Approach to Mechanized Encoding and Searching of Literary Information. IBM Journal of Research and Development, Vol. 1, No. 4, (October 1957), pp.309-317 Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K. and Harshman, R. (1990), Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41: 391-407. David M. Blei, Andrew Y. Ng, and Michael I. Jordan. 2003. Latent dirichlet allocation. Journal of Machine Learning Research 3 (March 2003), 993-1022. Story Understanding: Schank, Wilks, Charniak Eugene Charniak. 1973. Jack and Janet in Search of a Theory of Knowledge. Proceedings of Third International Joint Conference on Artificial Intelligence (IJCAI 1973). Yorick Wilks. 1976. Parsing English II. In E. Charniak and Y Wilks, (eds.), Computational Semantics. North-Holland Publishing Roger Schank. 1980. Language and Memory. Cognitive Science 4(3), 1980, 243-284.
8	Feb 22	First half: Natalia Second half: Karen		Proposing parsers for alternative grammatical formalisms Remo Pareschi and Mark Steedman. 1987. A Lazy way to Chart-Parse with Categorial Grammars Proceedings of ACL. Daniel Sleator and Davy Temperley. 1993. Parsing English with a Link Grammar. Third International Workshop on Parsing Technologies K. Vijay-Shankar and Aravlnd K. Joshl. 1985. Some Computational Properties of Tree Adjoining Grammars Influential Papers in Machine Translation John R. Pierce, John B. Carroll, Eric P. Hamp, David G. Hays, Charles F. Hockett, Anthony G. Oettinger, and Alan J. Perlis. 1966. Languages and Machines: Computers in Translation and Linguistics (The ALPAC Report).. National Academy of Sciences, National Research Council. Washington, DC. John R. Pierce. 1969. Whither Speech Recognition?. J. Acoust. Soc. Am. Volume 46, Issue 4B, pp. 1049-1051 (October 1969) Warren Weaver. 1955. Translation. In William N. Locke and A. D. Booth (eds). Machine Translation of Languages: Fourteen Essays. Reprinted from a memorandum written by Weaver in 1949. Extra: More Influential Papers in Machine Translation George A. Miller and J. G. Beebe-Center. 1958. Some Psychological Methods for Evaluating the Quality of Translations. Mechanical Translation 3, 73-80.
9	Mar 1	Guests: Gerald Penn and Paul Kiparsky		Panini and the role of the Indian Grammarians in Mathematical Linguistics Paul Kiparsky. 1993. Paninian Linguistics. Encyclopedia of Languages and Linguistics,. R E Asher (ed). Oxford: Pergamon, 1993. Kiparsky, Paul (2009). On the Architecture of Panini's Grammar. Proceedings of the First and Second Sanskrit Computational Linguistics Symposia, Springer LNCS 5402, pp. 33-94. Petersen, Wiebke (2009). On the Construction of Sivasutra-Alphabets. In A. Kulkarni and G. Huet (eds.): Sanskrit Computational Linguistics. LNCS 5406, p. 79-98, Springer.
10	Mar 8	Everyone		Presentations

A last topic we didn't get to: Key early papers on probabilistic models

A. A. Markov. 1911/2006. Classical Text in Translation: A. A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains. Translated by David Link. Science in Context 19:4, 591-600.
The first probabilistic parser:
K. C. Knowlton. 1960. SENTENCE PARSING WITH A SELF-ORGANIZING HEURISTIC PROGRAM (this is a two page summary of his MIT dissertation).
A proposal for probabilstic dependencies as part of a language model for machine translation:
Bjarne Ulvestad. 1962. On the use of transitional probability estimates in programming for mechanical translation. Statistical Methods in Linguistics 2,1:24-40.
plus of course Shannon 1948 and 1951
and Zipf 1929, 1935

Primary Source Info: Interviews and Oral Histories

Yorick Wilks interviews Martin Kay
Yorick Wilks interviews Victor Ynvge
Terry Winograd
Allen Newell
Gerald Gazdar
The Saras Institute Interviews These are mainly speech researchers, but a number are relevant for computational linguistics more generally, including:

Project Ideas

Finite-state models throughout the history of CL (Joshi, Kaplan and Kay, etc)
The influence of IR on CL
The history of unification
Multiple Inventions in Computational Linguistics: the Viterbi Algorithm (edit distance, the chart, etc etc)
The history of frequency and probability in linguistic description (dating back to the arabic grammarians)
The impact of the web on computational linguistics
The history of parsing
Dependency parsing and Constituency parsing in CL: Tesniere, etc etc.
The origin of sequence models (HMMs) at IDA and their transfer into speech and then text.