Inside Computer Understanding

Five Programs Plus Miniatures

R. C. Schank,C. K. Riesbeck

• Publisher: Psychology Press
• Year: 2013
• ISBN:
  9781135830397
• Edition: 1
• Topic: Psychology
• Subtopic: History & Theory in Psychology
• Index: Psychology

First published in 1981. This book has been written for those who want to comprehend how a large natural language-understanding program works. Thirty-five professionals in Cognitive Science, mostly psychologists by training, in a summer school were taught to grapple with the details of programming in Artificial Intelligence. As a part of the curriculum designed for this project the authors created what they called micro-programs. These micro-programs were an attempt to give students the flavor of using a large AI program without all the difficulty normally associated with learning a complex system written by another person. Using the authors' parser, ELI, or story understanding program, SAM, they also gave students the micro versions of these programs, which were very simple versions that operated in roughly the same way as their larger versions, but without all the frills. Students were asked to add pieces to the programs and otherwise modify them in order to learn how they worked.

1	Our Approach to Artificial Intelligence

The goal of Artificial Intelligence (AI) is commonly considered to be making machines intelligent. In the beginning, two domains dominated AI: chess and problem solving (e.g., Greene, 1959; Minsky, 1961; Newell et al., 1958; Newell and Simon, 1961). It was felt that a reasonable approach towards creating intelligent computers would be to make computers do things that clearly exhibited intelligence. Automated chess playing and theorem proving attracted maximum interest, largely because they were instances of things that were especially hard to do, and thus that exhibited intelligence.

Early work in AI did not have a particularly psychological flavor. Questions about how people played chess were not of primary interest. Much of the work done by Newell and Simon (1961) on problem solving was oriented towards finding out how people do various tasks, but the motivation of getting machines to do hard things predominated in AI nonetheless. Current chess playing programs are very good but not because they have simulated expert human chess players. Although some research has been done in that area within AI proper (Berliner, 1974), most expert chess programs perform well because they compute quickly and cleverly.

A great deal of current AI research is in the area of Robotics, that is, the adding of eyes, hands, and feet (or wheels) to the computer. Automated vision work (Duda and Hart, 1973; Winston, 1975) has in general not put any great emphasis on getting computers to see the way people do. Indeed, the problems really are quite different. AI researchers must primarily concern themselves with interpreting noisy input from a television camera. This makes the psychologist’s and AI researcher’s problems fundamentally different. Here again the AI emphasis is not always on the simulation of cognition but on computational achievement.

Our orientation in AI is much more in the area of cognitive simulation. The fundamental barrier to the achievement of intelligent machines is, in our opinion, our lack of knowledge about what people know and how they use what they know. We believe that it will be impossible to achieve machine intelligence without first coming to understand how people think.

Increasingly, AI in general has become concerned with the issue of what kind of knowledge people have, how it is stored, accessed, applied and acquired. This new focus is a result of the realization that world knowledge is behind people’s ability to do almost anything intelligent. An AI simulation of an expert chemist requires finding out what that chemist knows. Similarly, a simulation of a three year old’s linguistic ability also requires finding out what he knows (among other things). AI has gotten into the knowledge business in a big way in the last few years, partially because of the success of MYCIN, DENDRAL and other programs (Buchanan et al., 1969; Feigenbaum, 1977; Shortliffe, 1976).

As work in natural language processing began, researchers realized that initial toy systems could not be extended in the absence of a theory. Thus they began to experiment with whatever theories were available. Implementations of various linguistic theories emphasizing syntax had their heyday in AI for a while, but meaning was the real issue for AI, whereas for a long time linguists were assiduous in avoiding meaning altogether. When linguists did begin to approach issues of meaning, they did not do so from a process point of view. The notion of process, that is the construction of step by step models with precise beginning and end points, is fundamental to the building of any computer program. Natural language researchers within AI thus had to come to grips with the fact that they would have to build their own theories of the linguistic process. Since people can easily perform those tasks that AI wanted machines to perform, the quest for a theory of language processing gradually has become identical with the quest for a theory of human cognition.

Computer programs that attempt to replicate understanding without simulating the human understanding process are doomed to failure when it comes to very complex processes. Nowhere has this been clearer than in natural language processing. The tendency in the early years of mechanical translation (e.g., see Oettinger, 1960; Locke and Booth, 1955) and computational linguistics (e.g., Hays, 1967), two fields that preceded the AI approach to natural language processing, was to write programs based on grammars that would do initial syntactic parses of a sentence. These syntactic parsers failed for three important reasons. First, they were incredibly complicated to write, often employing tens of thousands of grammar rules for only very small parts of English. Second, they totally ignored meaning considerations, attempting to resolve syntactic issues as if they were completely independent of meaning. Third, and most important, they attempted to create a process that had nothing in common with its human counterpart. People are good at predicting the content of what they will hear. However, they are not very good at remembering long sequences of words. Because of these two factors, people do not wait until a sentence is finished before they begin to process it. Rather, they attempt to understand as much as they can of what they hear or read as the hearing or reading goes along.

It is our contention that computer models must model this process. That is, they must do a great deal more upon hearing the first few words of a sentence than simply attempting to find the syntactic relationships that hold between those words. They must also be processing the meanings, inferences, and general world knowledge related to those words, just as people do. That processing significantly alters the remainder of the processing that will be done in any given sentence.

Language has evolved through people’s efforts to ease communication, given limitations of memory and time. Natural languages are not like programming languages. They have been built for speech and for quick reading, not for logical completeness and exactness. Because people are good at supplying missing information in what they read or hear, natural language leaves out a great deal of information. This explains why elliptical utterances, anaphoric references, and highly ambiguous words are so common. If you know what’s being talked about, you only need to be given a few verbal clues to aid your understanding.

Thus, the Yale view of AI is that people are the best models of intelligent behavior that we have. We must attempt to simulate them before even considering improving upon the human algorithm. However, while all the work presented here was done with the above viewpoint in mind, it does not necessarily follow that we regard each program we have written as a psychologically correct model subject to empirical test. Frequently we will write a program in order to learn from it, never fully believing that our program was psychologically plausible in the first place.

The Evolution of Our Ideas or (Whatever Became of Margie?)

When we write an AI program we are attempting to walk the narrow line between human cognitive models and intelligent machines. We want our programs to serve two purposes. They should work, and thus extend the capabilities of computers, and they should tell us something about how people might work. Frequently we make trade offs between one or another of our goals. While we want our programs to work, they will have little value if they only do some limited task using a method which lacks generality. An AI program should tell us something of fundamental importance about cognition, either mechanical or human.

The programs that are described in this book are all intended to model one or another aspect of human cognition. None of them model every aspect, of course, and in that sense they are all rather artificial. One of the trade-offs that we must make is the decision to process language in what is a fairly artificial situation, usually lacking full background knowledge and full context. We make such trade-offs so that we can continue to test our ideas. Thus, for us, theory creation is a process of thought, followed by programming, then by additional thought, with each serving the other. Thus AI really operates under a novel view of science. Normal scientific method holds that first a theory is postulated, and then tested and found to be right or wrong. But in AI our theories are never that complete, because the processes we are theorizing about are so complex. Thus our tests are never completely decisive. We build programs that show us what to concentrate on in building the next program. Our theories evolve in this manner. This evolutionary way of thinking is a virtual requirement in AI and probably in any science whose domain is so complex as to make isolated testing of little use.

Margie

The fundamental problem that is addressed by the programs that are presented in this book, and by the work we did prior to these programs, is the problem of the representation of knowledge. Initially our work focused on the problem of the representation of the meaning of sentences. We developed Conceptual Dependency (CD) theory (the basics of which are described in Chapter 2) as the basis for our meaning representations. The purpose of our first computer program was to test the usefulness of CD as a meaning representation language. Our theory was that a meaning representation language for use in a computer program must provide the same representation to different inputs which mean the same thing, regardless of what input language or phraseology is used. For example, “John kissed Mary” and “Mary was given a kiss by John” should have the same meaning representation. Thus CD had to be capable of allowing us to do simple paraphrase and translation of sentences with inputs and outputs that varied considerably in syntactic form as well as in the selection of lexical items. To do this, we had to develop a program that would decode inputs into CD (i.e., a parser) and encode CD’s back into a natural language (i.e., a generator).

As we were doing this, we began to realize the importance of inference in the understanding process. Accounting for inference processes in a general way was thus added to our requirements for CD.

MARGIE (Schank et al., 1975) was designed to test out the usefulness of CD and to serve as a prototype for an understanding system. MARGIE was an attempt to demonstrate that language can be mapped into a deep-level, language-independent conceptual base, and then mapped back out into either the same or another language without losing any essential information.

The MARGIE system had three separate modules: a conceptual analyzer or parser, which mapped the input sentences into Conceptual Dependency; a generator, which mapped the meaning structures back into natural language; and a memory and inference program, which determined the referents for new inputs and made inferences about this input.

MARGIE worked in two modes: Paraphrase and Inference. The paraphrase mode produced over 100 paraphrases of an input sentence. These were not simple transformations of the original sentence, but rather they were newly generated expressions based upon the meaning of the original sentence as determined by the analyzer. For example, the following is a sample of MARGIE in paraphrase mode:

INPUT:	John killed Mary by choking Mary.
OUTPUT 1:	John strangled Mary.
OUTPUT 2:	John choked Mary and she died because she could not breathe.
OUTPUT 3:	Mary died because she was unable to inhale some air and she was unable to inhale some air because John grabbed her neck.

In inference mode, many of the possible inferences that could be made from the input sentence were produced and then generated. The inferencer speculated about the possible uses of an object, the possible goals of an actor, and the possible results of an action. The following is an example of MARGIE in inference mode:

INPUT:	John gave Mary an aspirin.
OUTPUT 1:	John believes that Mary wants an aspirin.
OUTPUT 2:	Mary is sick.
OUTPUT 3:	Mary wants to feel better.
OUTPUT 4:	Mary will ingest the aspirin.

MARGIE was our first attempt to model the understanding of natural language on a computer. The program was, however, rather unrealistic in that it worked with isolated sentences which had no overall context. This caused difficulties for the analyzer because it could not disambiguate input sentences with multiple meanings without a context to guide it. More importantly, the lack of context created a very serious problem for the inferencer. Because the inference mode created as many inferences as possible, both from the input sentence and from each successive level of inferences, there quickly arose a problem of the combinatorial explosion of inferences.

Clearly people do not make all possible inferences from what they hear; they make only the relevant ones. How people determine what path will be fruitful in inference-making thus became a serious issue for research.

MARGIE convinced us that Conceptual Dependency could function as a meaning representation language. Since we were able to generate sentences in languages other than English in MARGIE, we also had reason to believe that we had an interlingual representation language. MARGIE was the first computer program that made inferences from input sentences in the context of an overall theory of the inference process.

The major theoretical problem that resulted from the MARGIE system was that of unlimited inferencing. We decided to look at language in a more natural context. We believed that context held the answer to the inference explosion problem.

Sam

As part of our attack on the problem of irrelevant inferences, we began to design SAM. The purpose of SAM was to extend the work done in MARGIE to stories and to attack the problem of context.

To approach this problem, we worked on developing a theory of causal connectedness of text. The rudiments of this theory are presented in Chapter 3. We were able to control inferences partially by connecting sentences in a text by their causal relatedness. It was not always easy to do this, since causal relationships between sentences do not always exist or are often obscure and difficult to determine.

To solve this problem we examined certain simple stories on the most mundane of situations to determine how causal relations were likely to be computed by people engaged in story understanding. We came up with the notion of a script, which is basically a prepackaged chain of causal relations between events and states. In actual use, scripts represent a knowledge structure composed of stereotyped sequences of events that define some common everyday occurrence, such as eating in a restaurant, taking a bus ride, or going to a museum. (Scripts are described more fully in Chapter 3.)

At this point we began the construction of SAM, a computer program that read simple script-based stories. To do this, SAM constructed a representation of the meaning of each sentence that it read, and connected it to its place in the script that it had found to be active at that point in the story. Thus, the SAM system augmented MARGIE’s inference capability by supplying detailed knowledge about all the usual events in a standardized situation. In this way the inference process was constrained by the context of the story, and only those inferences relevant to the events in the story were generated.

SAM was a major advance over the MARGIE program, because its use of scripts allowed it to understand real stories, such as newspaper accounts of traffic accidents, without getting mired in a series of irrelevant inferences. SAM demonstrated that an understanding system has to be context-based in order to function effectively.

However, SAM did have its own set of problems. It was built as a model of a person reading a story in great detail; its paraphrases of newspaper stories were quite laborious in explaining every minor detail. Obviously, people do not concern themselves with every script-based inference applicable when reading a story. Furthermore, the processing time involved in SAM’s understanding a story was extremely large. To remedy these and other problems, we built FRUMP (DeJong, 1979). FRUMP is, at this writing, still under development at Yale. FRUMP is an extremely robust program, which can process stories it has never seen before that are taken directly off a news wire, in a time frame which is actually faster than that of a human reader.

PAM and TALE-SPIN

SAM demonstrated that knowledge is at the root of understanding. In order to understand texts, we had to build in knowledge of the world, in the form of a script, to help “fill in the blanks”, i.e., the gaps in the causal inference chain between events in a story. Representing a text,...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright
• Contents
• Preface
• 1. Our Approach to Artificial Intelligence
• 2. The Theory Behind the Programs: Conceptual Dependency
• 3. The Theory Behind the Programs: A Theory of Context
• 4. LISP
• 5. SAM
• 6. Micro SAM
• 7. PAM
• 8. Micro PAM
• 9. TALE-SPIN
• 10. Micro TALE-SPIN
• 11. POLITICS
• 12. Micro POLITICS
• 13. Conceptual Analysis of Natural Language
• 14. Micro ELI
• Bibliography
• Author Index
• Subject Index