1.6.8 A Final Brief Note on Psychology

Many of the chapters in this book include short summaries of psychological research on human processing. Of course, understanding human language processing is an important scientific goal in its own right and is part of the general field of cognitive science. However, an understanding of human language processing can often be helpful in building better machine models of language. This seems contrary to the popular wisdom, which holds that direct mimicry of nature's algorithms is rarely useful in engineering applications. For example, the argument is often made that if we copied nature exactly, airplanes would flap their wings; yet airplanes with fixed wings are a more successful engineering solution. But language is not aeronautics. Cribbing from nature is sometimes useful for aeronautics (after all, airplanes do have wings), but it is particularly useful when we are trying to solve human-centered tasks. Airplane flight has different goals than bird flight; but the goal of speech recognition systems, for example, is to perform exactly the task that human court reporters perform every day: transcribe spoken dialog. Since people already do this well, we can learn from nature's previous solution. Since an important application of speech and language processing systems is for human-computer interaction, it makes sense to copy a solution that behaves the way people are accustomed to.

1.7 SUMMARY

This chapter introduces the field of speech and language processing. The following are some of the highlights of this chapter.

• A good way to understand the concerns of speech and language processing research is to consider what it would take to create an intelligent agent like HAL from 2001: A Space Odyssey, or build a web-based question answerer, or a machine translation engine.

• Speech and language technology relies on formal models, or representations, of

knowledge of language at the levels of phonology and phonetics, morphology, syntax, semantics, pragmatics and discourse. A small number of formal models including state machines, formal rule systems, logic, and probabilistic models are used to capture this knowledge.

• The foundations of speech and language technology lie in computer science, linguistics, mathematics, electrical engineering and psychology. A small number of algorithms from standard frameworks are used throughout speech and language processing.

The critical connection between language and thought has placed speech and language processing technology at the center of debate over intelligent machines. Furthermore, research on how people interact with complex media indicates that speech and language processing technology will be critical in the development of future technologies.

• Revolutionary applications of speech and language processing are currently in use around the world. The creation of the web, as well as significant recent improvements in speech recognition and synthesis, will lead to many more applications.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Research in the various subareas of speech and language processing is spread across a wide number of conference proceedings and journals. The conferences and journals most centrally concerned with natural language processing and computational linguistics are associated with the Association for Computational Linguistics (ACL), its European counterpart (EACL), and the International Conference on Computational Linguistics (COLING). The annual proceedings of ACL, NAACL, and EACL, and the biennial COLING conference are the primary forums for work in this area. Related conferences include various proceedings of ACL Special Interest Groups (SIGs) such as the Conference on Natural Language Learning (CoNLL), as well as the conference on Empirical Methods in Natural Language Processing (EMNLP).

Research on speech recognition, understanding, and synthesis is presented at the annual INTERSPEECH conference, which is called the International Conference on Spoken Language Processing (ICSLP) and the European Conference on Speech Communication and Technology (EUROSPEECH) in alternating years, or the annual IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE ICASSP). Spoken language dialogue research is presented at these or at workshops like SIGDial.

Journals include Computational Linguistics, Natural Language Engineering, Speech Communication, Computer Speech and Language, the IEEE Transactions on Audio, Speech & Language Processing and the ACM Transactions on Speech and Language Processing.

Work on language processing from an Artificial Intelligence perspective can be found in the annual meetings of the American Association for Artificial Intelligence (AAAI), as well as the biennial International Joint Conference on Artificial Intelligence.

gence (IJCAI) meetings. Artificial intelligence journals that periodically feature work on speech and language processing include Machine Learning, Journal of Machine Learning Research, and the Journal of Artificial Intelligence Research.

There are a fair number of textbooks available covering various aspects of speech and language processing. Manning and Schütze (1999) (Foundations of Statistical Language Processing) focuses on statistical models of tagging, parsing, disambiguation, collocations, and other areas. Charniak (1993) (Statistical Language Learning) is an accessible, though older and less-extensive, introduction to similar material. Manning et al. (2008) focuses on information retrieval, text classification, and clustering. NLTK, the Natural Language Toolkit (Bird and Loper, 2004), is a suite of Python modules and data for natural language processing, together with a Natural Language Processing book based on the NLTK suite. Allen (1995) (Natural Language Understanding) provides extensive coverage of language processing from the AI perspective. Gazdar and Mellish (1989) (Natural Language Processing in Lisp/Prolog) covers especially automata, parsing, features, and unification and is available free online. Pereira and Shieber (1987) gives a Prolog-based introduction to parsing and interpretation. Russell and Norvig (2002) is an introduction to artificial intelligence that includes chapters on natural language processing. Partee et al. (1990) has a very broad coverage of mathematical linguistics. A historically significant collection of foundational papers can be found in Grosz et al. (1986) (Readings in Natural Language Processing).

Of course, a wide-variety of speech and language processing resources are now available on the Web. Pointers to these resources are maintained on the home-page for this book at:

http://www.cs.colorado.edu/~martin/slp.html.

Allen, J. (1995). Natural Language Understanding. Benjamin Cummings, Menlo Park, CA.

Backus, J. W. (1959). The syntax and semantics of the proposed international algebraic language of the Zurch ACM-GAMM Conference. In Information Processing: Proceedings of the International Conference on Information Processing, Paris, pp. 125–132. UNESCO.

Berger, A., Della Pietra, S. A., and Della Pietra, V. J. (1996). A maximum entropy approach to natural language processing. Computational Linguistics, 22(1), 39–71.

Bird, S. and Loper, E. (2004). NLTK: The Natural Language Toolkit. In Proceedings of the ACL 2004 demonstration session, Barcelona, Spain, pp. 214–217.

Bledsoe, W. W. and Browning, I. (1959). Pattern recognition and reading by machine. In 1959 Proceedings of the Eastern Joint Computer Conference, pp. 225–232. Academic, New York.

Bresnan, J. and Kaplan, R. M. (1982). Introduction: Grammars as mental representations of language. In Bresnan, J. (Ed.), The Mental Representation of Grammatical Relations. MIT Press, Cambridge, MA.

Brown, P. F., Cocke, J., Della Pietra, S. A., Della Pietra, V. J., Jelinek, F., Lafferty, J. D., Mercer, R. L., and Roossin, P. S. (1990). A statistical approach to machine translation. Computational Linguistics, 16(2), 79–85.

Carlson, L., Marcu, D., and Okurowski, M. E. (2001). Building a discourse-tagged corpus in the framework of rhetorical structure theory. In Proceedings of SIGDIAL.

Charniak, E. (1993). Statistical Language Learning. MIT Press.

Chomsky, N. (1956). Three models for the description of language. IRI Transactions on Information Theory, 2(3), 113–124.

Chomsky, N. (1959). A review of B. F. Skinner's “Verbal Behavior”. Language, 35, 26–58.

Church, K. W. (1980). On memory limitations in natural language processing. Master's thesis, MIT. Distributed by the Indiana University Linguistics Club.

Cohen, P. R. and Perrault, C. R. (1979). Elements of a plan-based theory of speech acts. Cognitive Science, 3(3), 177–212.

Colmerauer, A. (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.

Colmerauer, A. (1975). Les grammaires de métamorphose GIA. Internal publication, Groupe Intelligence artificielle, Faculté des Sciences de Luminy, Université Aix-Marseille II, France, Nov 1975. English version, Metamorphosis grammars. In L. Bolc, (Ed.), Natural Language Communication with Computers, Lecture Notes in Computer Science 63, Springer Verlag, Berlin, 1978, pp. 133–189.

Cullingford, R. E. (1981). SAM. In Schank, R. C. and Riesbeck, C. K. (Eds.), Inside Computer Understanding: Five Programs

plus Miniatures, pp. 75–119. Lawrence Erlbaum, Hillsdale, NJ.

Davis, K. H., Biddulph, R., and Balashek, S. (1952). Automatic recognition of spoken digits. Journal of the Acoustical Society of America, 24(6), 637–642.

Dejean, H. and Tjong Kim Sang, E. F. (2001). Introduction to the CoNLL-2001 shared task: Clause identification. In Proceedings of CoNLL-2001.

Fillmore, C. J. (1968). The case for case. In Bach, E. W. and Harms, R. T. (Eds.), Universals in Linguistic Theory, pp. 1–88. Holt, Rinehart & Winston, New York.

Francis, W. N. (1979). A tagged corpus – problems and prospects. In Greenbaum, S., Leech, G., and Svartvik, J. (Eds.), Studies in English linguistics for Randolph Quirk, pp. 192–209. Longman, London and New York.

Francis, W. N. and Kučera, H. (1982). Frequency Analysis of English Usage. Houghton Mifflin, Boston.

Gazdar, G. and Mellish, C. (1989). Natural Language Processing in LISP. Addison Wesley.

Grosz, B. J. (1977). The representation and use of focus in a system for understanding dialogs. In IJCAI-77, Cambridge, MA, pp. 67–76. Morgan Kaufmann. Reprinted in Grosz et al. (1986).

Grosz, B. J., Jones, K. S., and Webber, B. L. (Eds.). (1986). Readings in Natural Language Processing. Morgan Kaufmann, Los Altos, Calif.

Hajič, J. (1998). Building a Syntactically Annotated Corpus: The Prague Dependency Treebank, pp. 106–132. Karolinum, Prague/Praha.

Harris, Z. S. (1962). String Analysis of Sentence Structure. Mouton, The Hague.

Hobbs, J. R. (1978). Resolving pronoun references. Lingua, 44, 311–338. Reprinted in Grosz et al. (1986).

Joshi, A. K. and Hopely, P. (1999). A parser from antiquity. In Kornai, A. (Ed.), Extended Finite State Models of Language, pp. 6–15. Cambridge University Press, Cambridge.

Kaplan, R. M. and Kay, M. (1981). Phonological rules and finite-state transducers. Paper presented at the Annual meeting of the Linguistics Society of America. New York.

Karttunen, L. (1999). Comments on Joshi. In Kornai, A. (Ed.), Extended Finite State Models of Language, pp. 16–18. Cambridge University Press, Cambridge.

Kay, M. (1979). Functional grammar. In BLS-79, Berkeley, CA, pp. 142–158.

Kilgarriff, A. and Palmer, M. (Eds.). (2000). Computing and the Humanities: Special Issue on SENSEVAL, Vol. 34. Kluwer.

Kintsch, W. (1974). The Representation of Meaning in Memory. Wiley, New York.

Kleene, S. C. (1951). Representation of events in nerve nets and finite automata. Tech. rep. RM-704, RAND Corporation. RAND Research Memorandum.

Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In Shannon, C. and McCarthy, J. (Eds.), Automata Studies, pp. 3–41. Princeton University Press, Princeton, NJ.

Koenig, W., Dunn, H. K., Y., L., and Lacy (1946). The sound spectrograph. Journal of the Acoustical Society of America, 18, 19–49.

Küçera, H. and Francis, W. N. (1967). Computational analysis of present-day American English. Brown University Press, Providence, RI.

Lehnert, W. G. (1977). A conceptual theory of question answering. In IJCAI-77, Cambridge, MA, pp. 158–164. Morgan Kaufmann.

Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press, Cambridge, UK.

Manning, C. D. and Schütze, H. (1999). Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, MA.

Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A. (1993). Building a large annotated corpus of English: The Penn treebank. Computational Linguistics, 19(2), 313–330.

McCulloch, W. S. and Pitts, W. (1943). A logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5, 115–133. Reprinted in Neurocomputing: Foundations of Research, ed. by J. A. Anderson and E Rosenfeld. MIT Press 1988.

Merton, R. K. (1961). Singletons and multiples in scientific discovery. American Philosophical Society Proceedings, 105(5), 470–486.

Miltsakaki, E., Prasad, R., Joshi, A. K., and Webber, B. L. (2004). The Penn Discourse Treebank. In LREC-04.

Mosteller, F. and Wallace, D. L. (1964). Inference and Disputed Authorship: The Federalist. Springer-Verlag, New York. 2nd Edition appeared in 1984 and was called Applied Bayesian and Classical Inference.

Naur, P., Backus, J. W., Bauer, F. L., Green, J., Katz, C., McCarthy, J., Perlis, A. J., Rutishauser, H., Samelson, K., Vauquois, B., Wegstein, J. H., van Wijnagaarden, A., and Woodger, M. (1960). Report on the algorithmic language ALGOL 60. Communications of the ACM, 3(5), 299–314. Revised in CACM 6:1, 1-17, 1963.

Norman, D. A. and Rumelhart, D. E. (1975). Explorations in Cognition. Freeman, San Francisco, CA.

Och, F. J. and Ney, H. (2003). A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1), 19–51.

Ogburn, W. F. and Thomas, D. S. (1922). Are inventions inevitable? A note on social evolution. Political Science Quarterly, 37, 83–98.

Palmer, M., Fellbaum, C., Cotton, S., Delfs, L., and Dang, H. T. (2001). English tasks: All-words and verb lexical sample. In Proceedings of SENSEVAL-2: Second International

Workshop on Evaluating Word Sense Disambiguation Systems, Toulouse, France.

Palmer, M., Kingsbury, P., and Gildea, D. (2005). The proposition bank: An annotated corpus of semantic roles.. Computational Linguistics, 31(1), 71–106.

Partee, B. H., ter Meulen, A., and Wall, R. E. (1990). Mathematical Methods in Linguistics. Kluwer, Dordrecht.

Pereira, F. C. N. and Shieber, S. M. (1987). Prolog and Natural-Language Analysis, Vol. 10 of CSLI Lecture Notes. Chicago University Press, Chicago.

Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufman, San Mateo, Ca.

Pereira, F. C. N. and Warren, D. H. D. (1980). Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks. Artificial Intelligence, 13(3), 231–278.

Perrault, C. R. and Allen, J. (1980). A plan-based analysis of indirect speech acts. American Journal of Computational Linguistics, 6(3-4), 167–182.

Quillian, M. R. (1968). Semantic memory. In Minsky, M. (Ed.), Semantic Information Processing, pp. 227–270. MIT Press, Cambridge, MA.

Rabiner, L. R. and Juang, B. (1993). Fundamentals of Speech Recognition. Prentice Hall, Englewood Cliffs, NJ.

Reeves, B. and Nass, C. (1996). The Media Equation: How People Treat Computers, Television, and New Media Like Real People and Places. Cambridge University Press, Cambridge.

Russell, S. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs, NJ. Second edition.

Schank, R. C. (1972). Conceptual dependency: A theory of natural language processing. Cognitive Psychology, 3, 552–631.

Schank, R. C. and Albelson, R. P. (1977). Scripts, Plans, Goals and Understanding. Lawrence Erlbaum, Hillsdale, NJ.

Schank, R. C. and Riesbeck, C. K. (Eds.). (1981). Inside Computer Understanding: Five Programs plus Miniatures. Lawrence Erlbaum, Hillsdale, NJ.

Searle, J. R. (1980). Minds, brains, and programs. Behavioral and Brain Sciences, 3, 417–457.

Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423. Continued in following volume.

Shieber, S. M. (1994). Lessons from a restricted Turing test. Communications of the ACM, 37(6), 70–78.

Sidner, C. L. (1983). Focusing in the comprehension of definite anaphora. In Brady, M. and Berwick, R. C. (Eds.), Computational Models of Discourse, pp. 267–330. MIT Press, Cambridge, MA.

Simmons, R. F. (1973). Semantic networks: Their computation and use for understanding English sentences. In Schank, R. C. and Colby, K. M. (Eds.), Computer Models of Thought and Language, pp. 61–113. W.H. Freeman and Co., San Francisco.

Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 230–265. Read to the Society in 1936, but published in 1937. Correction in volume 43, 544–546.

Turing, A. M. (1950). Computing machinery and intelligence. Mind, 59, 433–460.

Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer-Verlag, New York.

Voorhees, E. M. and Tice, D. M. (1999). The TREC-8 question answering track evaluation. Proceedings of the TREC-8 Workshop.

Weizenbaum, J. (1966). ELIZA – A computer program for the study of natural language communication between man and machine. Communications of the ACM, 9(1), 36–45.

Weizenbaum, J. (1976). Computer Power and Human Reason: From Judgement to Calculation. W.H. Freeman and Company, San Francisco.

Wilensky, R. (1983). Planning and Understanding. Addison-Wesley, Reading, MA.

Wilks, Y. (1975a). Preference semantics. In Keenan, E. L. (Ed.), The Formal Semantics of Natural Language, pp. 329–350. Cambridge Univ. Press, Cambridge.

Wilks, Y. (1975b). A preferential, pattern-seeking, semantics for natural language inference. Artificial Intelligence, 6(1), 53–74.

Winograd, T. (1972). Understanding natural language. Cognitive Psychology, 3(1), 1–191. Reprinted as a book by Academic Press, 1972.

Woods, W. A. (1967). Semantics for a Question-Answering System. Ph.D. thesis, Harvard University.

Woods, W. A. (1973). Progress in natural language understanding. In Proceedings of AFIPS National Conference, pp. 441–450.

2

REGULAR EXPRESSIONS AND AUTOMATA

User1: Men are all alike.

ELIZA $ _{1} $: IN WHAT WAY

User2: They're always bugging us about something or other.

ELIZA $ _{2} $: CAN YOU THINK OF A SPECIFIC EXAMPLE

User3: Well, my boyfriend made me come here.

ELIZA $ _{3} $: YOUR BOYFRIEND MADE YOU COME HERE

User4: He says I'm depressed much of the time.

ELIZA $ _{4} $: I AM SORRY TO HEAR YOU ARE DEPRESSED.

Weizenbaum (1966)

Imagine that you have become a passionate fan of woodchucks. Desiring more information on this celebrated woodland creature, you turn to your favorite Web browser and type in woodchuck. Your browser returns a few sites. You have a flash of inspiration and type in woodchucks. This time you discover “interesting links to woodchucks and lemurs” and “all about Vermont’s unique, endangered species”. Instead of having to do this search twice, you would have rather typed one search command specifying something like woodchuck with an optional final s. Or perhaps you might want to search for all the prices in some document; you might want to see all strings that look like $199 or $25 or $24.99. In this chapter we introduce the regular expression, the standard notation for characterizing text sequences. The regular expression is used for specifying text strings in situations like this Web-search example, and in other information retrieval applications, but also plays an important role in word-processing, computation of frequencies from corpora, and other such tasks.

After we have defined regular expressions, we show how they can be implemented via the finite-state automaton. The finite-state automaton is not only the mathematical device used to implement regular expressions, but also one of the most significant tools of computational linguistics. Variations of automata such as finite-state transducers, Hidden Markov Models, and N-gram grammars are important components of applications that we will introduce in later chapters, including speech recognition and synthesis, machine translation, spell-checking, and information-extraction.

2.1 REGULAR EXPRESSIONS

SIR ANDREW: Her C's, her U's and her T's: why that? Shakespeare, Twelfth Night

One of the unsung successes in standardization in computer science has been the regular expression (RE), a language for specifying text search strings. The regular expression languages used for searching texts in UNIX (vi, Perl, Emacs, grep), Microsoft Word (version 6 and beyond), and WordPerfect are almost identical, and many RE features exist in the various Web search engines. Besides this practical use, the regular expression is an important theoretical tool throughout computer science and linguistics.

A regular expression (first developed by Kleene (1956) but see the History section for more details) is a formula in a special language that is used for specifying simple classes of strings. A string is a sequence of symbols; for the purpose of most text-based search techniques, a string is any sequence of alphanumeric characters (letters, numbers, spaces, tabs, and punctuation). For these purposes a space is just a character like any other, and we represent it with the symbol ___.

Formally, a regular expression is an algebraic notation for characterizing a set of strings. Thus they can be used to specify search strings as well as to define a language in a formal way. We will begin by talking about regular expressions as a way of specifying searches in texts, and proceed to other uses. Section 2.3 shows that the use of just three regular expression operators is sufficient to characterize strings, but we use the more convenient and commonly-used regular expression syntax of the Perl language throughout this section. Since common text-processing programs agree on most of the syntax of regular expressions, most of what we say extends to all UNIX, Microsoft Word, and WordPerfect regular expressions. Appendix A shows the few areas where these programs differ from the Perl syntax.

Regular expression search requires a pattern that we want to search for, and a corpus of texts to search through. A regular expression search function will search through the corpus returning all texts that contain the pattern. In an information retrieval (IR) system such as a Web search engine, the texts might be entire documents or Web pages. In a word-processor, the texts might be individual words, or lines of a document. In the rest of this chapter, we will use this last paradigm. Thus when we give a search pattern, we will assume that the search engine returns the line of the document returned. This is what the UNIX grep command does. We will underline the exact part of the pattern that matches the regular expression. A search can be designed to return all matches to a regular expression or only the first match. We will show only the first match.