Strategies for Natural Language Processing

W. G. Lehnert, M. H. Ringle, W. G. Lehnert, M. H. Ringle

• Publisher: Psychology Press
• Year: 2014
• eBook ISBN: 9781317769248
• Topic: Psychology
• Subtopic: Cognitive Psychology & Cognition
• Index: Psychology

First published in 1982. Simply defined, the field of natural language processing is concerned with theories and techniques that address the problem of natural language communication with computers. One of the goals of this research is to design computer programs that will allow people to interact with computers in natural conversational dialogues.

I

INTRODUCTION

1	The State of the Art in Natural-Language Understanding

David L. Waltz

University of Illinois at Urbana–Champaign

INTRODUCTION

The original purpose of this chapter was to give some answers to the following questions about the state of the art in natural-language understanding systems:

What are the limits now?

What are the obstacles to progress?

Where are the answers likely to lie?

In order to answer these questions, I first set out what I feel are the major lines of natural-language research today, including the study of such topics as knowledge representation, metaphor, “speech arts” (the use of language to achieve goals), modeling of “common sense” and plausibility judgment, relationships between language and perception, and so on. One way to make sense of this potpourri of research topics is to consider the basic questions being explored by two or more of the research areas. Looked at this way, I think that the following five questions are motivating much of the current research in natural-language understanding:

1. What is the function/purpose of language? Language is, in general, used by a speaker to achieve goals. Unless we understand these goals, we cannot understand the language. Goals may be extremely complex: A speaker may mean to inform, correct, or mislead a listener; or a speaker may wish to have the listener perform a physical or cognitive action, or undergo a certain kind of experience, or answer questions, and so on. Often it is necessary to have a model of the speaker’s ordinary behavior in order to understand the speaker’s goals—the language alone may not be sufficient. And, in order to tell whether or not a speaker is telling the truth, a listener must be able to compare the speaker’s language with models embodying knowledge of human behavior as well as the behavior of the physical world. To make matters even more problematic, any given utterance may be used to serve quite different goals in different situations, and a single utterance may serve multiple goals simultaneously.

2. What does it mean to “understand language” and how could we show that a system can understand? Research attention has focused on the sentence for a long time. However, many important units of language are much larger than the sentence: dialogues, instructions, scene and event descriptions, stories, explanations, and so on. We currently lack the ability to assign meaning and purpose to all but the very simplest of these larger units of language.

3. How can a program deal with novel language? The preponderance of work to date has allowed us to deal with novel syntactic structures, but we have relatively very little understanding of methods for dealing with novel semantic structures, and virtually no methods for dealing with novel concepts expressed in language. We have a need for semantic methods that can give us meanings for phrases such as “engine housing acid corrosion damage report summary”; we also need a dramatically expanded understanding of metaphor and other nonliteral language (e.g., “The soldiers were shattered by the experience.” or “We found a refrigerator graveyard.”).

4. How can a program judge whether language is meaningful? How do we know that “The man jumped over the fence.” can be literally meaningful whereas “The cow jumped over the moon.” cannot? How can we decide that a message is garbled or that its sender is deranged? How can we decide that a metaphorical interpretation is intended, and how can we know that a given metaphorical interpretation is sensible? To answer such questions a system needs “common sense,” and common sense must surely be based on an extensive and detailed model of the physical world, as well as of the worlds of human action and inner experience (e.g., perception, emotion, memory, and so on).

5. What is the most effective way to make the restricted natural-language systems of the foreseeable future seem natural to humans? We have only the beginnings of an understanding of how users will behave with natural-language systems. Thus, there has been to date a fair degree of mismatch between systems and users. We would like to be able to evaluate both existing systems and future design alternatives for usefulness and convenience. We would like to be able to give casual users systems that allow natural expression, that do not often surprise users by not understanding or misunderstanding their language.

The rest of this chapter is organized historically. I could not find a good way to fit together the five preceding questions to form a coherent picture of the current state of the art of research, and I found it was even more difficult to show how the current questions related to the ultimate natural-language processing questions. I discovered, however, that current research directions seemed much more sensible if they were viewed as responses to specific shortcomings of earlier ways of looking at the process of natural-language understanding.

ANCIENT HISTORY

Before 1940, computers, if they were thought about at all, were considered to be number processors. During the 1940’s, two major developments led to the view of computers as somewhat more than simple number processors. The first set of ideas was due to McCullough and Pitts, who theorized that each neuron is a logical device (roughly an AND or OR gate). We now know that each neuron is far more complex than they believed it to be, but their ideas were important in that they suggested that all intelligent processing, whether arithmetic or symbolic, numerical or verbal, could be performed by a single type of mechanism. Thus, their views were important in a much more precise formulation of the brain-computer analogy than had been possible before.

The second major piece of work was Shannon’s work on information theory. Shannon showed that both numbers and text could be treated as special cases of a more general concept he called “information,” that information content could be quantified, and that ideas about information had interesting mathematical and practical applications.

Machine Translation

In the early 1950’s Shannon’s work led to what I call “the era of machine translation.” Being able to treat text and language in general as information allowed the possibility that language might be manipulated on the new digital computers that were then being constructed. The initial idea for machine translation was the following: Translation is a process of dictionary look-up, plus substitution, plus grammatical recordering. As an example, the English sentence, “I must go home.” could be translated into the German “Ich muss nach Hause gehen.” by substituting “Ich” for “I,” “muss” for “must,” “gehen” for “go,” and “nach Hause” for “home.” In the process, two words (“nach Hause” or to the house) had to be substituted for “home”—we do not worry here about that fine point—and a simple kind of grammatical reordering had to take place to move the verb to the end of the sentence.

For simple examples, this model of the possibility of translation seems rather intriguing. However, it soon became clear that translation is really not possible without understanding. To illustrate the need for understanding in translation, a classic story (probably apochryphal) describes the machine translation of the phrase “The spirit is willing but the flesh is weak.” into Russian and then back into English; the translation is said to have come out: “The vodka is strong but the meat is rotten.”

Clearly, a greater amount of world knowledge was needed; a program had to understand what was being said in order to be able to translate it properly. Yet another classic example was given by Bar-Hillel in a 1964 paper in which he explained why he was leaving the field of machine translation. Bar-Hillel cited the sentences, “The pen is in the box.” and “The box is in the pen.” and pessimistically stated that he could not imagine how a machine could translate both sentences correctly, assigning “pen” the meaning “writing implement” in the first sentence, and “playpen” or “stockpen” in the second. Although we still have a long way to go before we could claim to have programs that truly understand or translate a significant range of types of language, we do now know how to write programs that can appropriately assign different meanings to “pen” in Bar-Hillel’s examples by using a system that can manipulate simple spatial models of objects (Waltz, 1981).

The work on machine translation did give a great deal of impetus to work on syntactic theory as evidenced especially by the work of Chomsky and also to a degree in the early work on parsing high-level languages for compiler construction, now a core topic in computer science.

To continue this brief history, other major ideas that have been influential in the history of natural-language processing surfaced in the 1950’s. I refer specifically to the introduction of the idea of heuristic search by Newell and Simon (1956) and also to the introduction of the LISP programming language by McCarthy (1960). Most natural-language processing systems have been written in LISP.

The entire field of machine translation essentially came to an end in the early 1960’s. It is only now undergoing a kind of renaissance, using AI models of meaning, but the early effort was a nearly complete failure.

THE SEMANTIC INFORMATION-PROCESSING ERA

Out of the rubble of machine-translation work grew an effort that is closely associated with artificial intelligence. The “semantic information-processing era” (roughly 1962–1973) produced a number of ideas used in today’s natural-language application systems, some of which have proved to be of practical value. Some notable ideas of this era are the following:

1. The use of limited domains for language-understanding systems. Rather than attempting to understand all language, the limited-domain approach is to design a system that is expert in one specific area of language, but perhaps knows nothing at all about any other domain.

2. The “big-switch” theory. To rationalize the study of limited domains as a contribution to a full cognitive theory, the “big-switch” theory was advanced. This theory holds that it is possible to construct a broadly intelligent system by generating experts in a number of limited domains and then piecing together a huge system containing these experts along with a special expert, the “big switch,” which could select the appropriate expert to handle any given problem.

3. The use of key words to trigger certain actions. Natural-language programs using this idea look in a sentence for one or more key words and, on the basis of what is found, take appropriate action (I give an example later).

4. The “translation” of English into formal languages. Some of the formal languages that have been used include predicate calculus, data-base query languages, and sets of linear equations.

Overall, we could characterize the approaches of the 1960’s to natural-language processing as “engineering approaches,” which attempted to solve specific problem domains, not to embody psychological reality. What do I mean by “engineering approaches”? Let us look at some examples.

Key-Word Systems

The first example is the use of key words. Key words were particularly important in the ELIZA and DOCTOR programs written by Weizenbaum (1966), and the PARRY program (which simulated a paranoid person) by Colby and his collaborators (1975).

In Fig. 1.1 (a highly simplified example based on ELIZA) “*” matches any word or list of words (including no words at all) and the literal words such as “computers” can only match words like “computers.” Thus, if someone were to type “I hate computers” to the ELIZA program, it might respond, “Do computers frighten you?” If the person typed, “My mother is an electrician,” ELIZA could respond, “Tell me more about your family.” ELIZA was also capable of using phrases and words that matched patterns to construct responses; thus, it could respond to “I believe that

x

” with “How long have you believed that

x

?”

Translating English into a Formal System

As an example of the translation of English into a formal language, consider Bobrow’s STUDENT program (Bobrow, 1968), which translated algebra word problems into a set of linear equations. STUDENT treated each input sentence as though it corresponded to a simple equation; thus, “John’s age now is two times Mary’s age” would be translated into ...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• Abstracts
• PART I: INTRODUCTION
• PART II: IMPLEMENTATION ISSUES
• PART III: CONVERSATION AND DISCOURSE
• PART IV: KNOWLEDGE REPRESENTATION
• PART V: THEORETICAL ISSUES
• Notes on Contributors
• Subject Index
• Author Index