--- title: "Learning Schemata for Natural Language Processing" authors: - "Raymond J. Mooney" - "Gerald DeJong" doi: "" url: "https://ijcai.org/proceedings/1985/132" pdf: "https://ijcai.org/proceedings/1985/0132.pdf" venue: "Proceedings of the Ninth International Joint Conference on Artificial Intelligence" year: 1985 pages: "681-686" track: "Learning and Acquisition" keywords: --- # Learning Schemata for Natural Language Processing Raymond J. Mooney, Gerald DeJong *Proceedings of the Ninth International Joint Conference on Artificial Intelligence*, pages 681-686. ## Abstract This paper describes a natural language system which improves its own performance through learning. The system processes short English narratives and is able to acquire, from a single narrative, a new schema for a stereotypical set of actions. During the understanding process, the system attempts to construct explanations for characters' actions in terms of the goals their actions were meant to achieve. When the system observes that a character has achieved an interesting goal in a novel way, it generalizes the set of actions they used to achieve this goal into a new schema. The generalization process is a knowledge-based analysis of the causal structure of the narrative which removes unnecessary details while maintaining the validity of the causal explanation. The resulting generaliud set of actions is then stored as a new schema and used by the system to correctly process narratives which were previously beyond its capabilities. ## Full text ## LEARNING SCHEMATA FOR NATURAL LANGUAGE PROCESSING Raymond Mooney Gerald DeJong Coordinated Science Laboratory University of Illinois at Urbana..(;hampaign Urbana, IL 61801 in the normal course of processing narratives. 1 After acquiring new schemata, the system is able to correctly process narrative.~ that were previously beyond its capabilities. We call the learning process used by GENESIS explanatory schei'TUl acquisit.ion [DeJong83! It is a form of explanation-based learning [DeJong8.5l which can be briefly defined as learning a new problem solving method by analyzing the causal structure of a problem solution. The system is fully implemented and an example sequence demonstrating the system's learning is given later in the paper. A longer version of this paper appears as [Mooney8.5! ## D GENERAL SYSTEM ORGANIZATION The general organization of the GENESIS narrative processing system is shown in figure 1. First, English input is processed by a parser into a conceptual representation (CRep), a case-frame representation which uses some conceptual dependency prim.ilives [Schank7.5) as well as predicates for complex schemata. Currently, we are using an adaptation of Dyer's McDYPAR [Dyer83) for this purpose; however, since the focus of our research is learning, we make no claims about parsing and alternative approaches could be used for this task (e.g. [Marcus80, Waltz84)). The basic task of the understander is to construct a causally complete representation called the model. A model for a narrative has explicit representations for all the inputs as well as the many inferences that must be made to causally connect them together. There are four types of causal links for connecting assertions in the model of a narrative. These are: p1·econdition: A link between a state and an action it enables. effect: A link. between an action and a resulting state. Figure 1: General System Organization ![Image](https://ijcai.org/proceedings/1985/fulltext/132/image_000000_460772d6e8cf148bce3c2771e9e863fd09a4b3a9093168ce8a689045847322c5.png) 1 The ust of tht term "story" in naturallan&ua&< proccssin& hLI betn controvtr sial 1Brewer82l Therrfore, in this paper .,. .· havc adopted tho trrrn "narrative" to rrfcr to connected text which may Jack a plot or other de!inin~ aspect or · ""ory." ## ABSTR.ACf This paper describes a natural language system which improves its own performance through learning. The system processes short English narratives and is able to acquire, from a sin­ gle narrative, a new schema for a stereotypical set of actions. Dur­ ing the understanding process, the system attempts to construct explanations for characters' actions in terms of the goals their actions were meant to achieve. When the system observes that a character has achieved an interesting goal in a novel way, it gen­ eralizes the set of actions they used to achieve this goal into a new schema. The generalization process is a knowledge-based analysis of the causal structure of the narrative which removes unnecessary details while maintaining the validity of the causal explanation. The resulting generaliud set of actions is then stored as a new schema and used by the system to correctly process narratives which were previously beyond its capabilities. ## I INTRODUCTION A natural language system requires extensive knowledge about the world. Clearly, if a computer system is to summarize, translate, or answer questions about a text, it must have knowledge about the concepts expressed in the text. Imagine trying to process a narrative describing a bank robbery without knowledge of money and why people want it. This is a conceptual rather than linguistic requirement, and it means that at the heart of a natural language processor there must be a problem solver to infer missing but important concepts, to insure that the narrative phrases are causally related in an appropriate way, and perhaps to guide the linguistic processing [DeJong82! Schema-based problem solvers [Charniak77, Minsky7.5, Schank 77) have proven themselves more workable for natural language processing applications than their heuristic search counter­ parts. In order to process a wide range of text, a schema-based natural language processor must possess many schemata, perhaps hundreds of thousands. This presents both practical and theoretical problems. Somehow these schemata must find their way into the system. They cannot all be built in by hand; there are simply too many. Furthermore, hand coding does not allow for dynamic aug­ mentation of world knowledge. This is an important facet of language processing. For example, the word wSkyjacking," is now an accepted newspaper term but was unheard of twenty years aso. Readers have learned it as a by-product of their normal newspaper reading and natural language processing systems must be able to do the same. We have taken the first steps in this direction at the t:niver­ sity of Illinois. A natural language processing system called GENESIS (for GENeralizing Explanations of Stories Into Schemata) has been designed and implemented which acquires new schemata Thi· work ,. ... supponed in pan by th< Air Foret' Oilier of Scicnti!ic Reotarch under grant F49b20-82·K-0009 and in part by tht National Science Foundation undrr grant NSF· IST- ~3-178~9. motivation: in fer·en.ce: A link between a volitional action and the belit'fs and goals of the actor which motivated him to per­ form the action. A link between a state and another state which it implies. To avoid confusion, such "causal" links between assertions in the model will be called support links. since a precondition of an action supports the performance of that action but does not cause it. The closely related term data dependency link [Doyle78l is not used since it is normally reserved for the support of inferences, not for the support of both inferences and actions. Inferring causal connec­ tions necessarily employs a large amount of background knowledge which is stored in the sclumw library. The techniques and representations used in this process are similar to those used in past work in narrative understanding [Charniak 77, Cullingford78, DeJong82, Dyer83, Wilensky83] and are discussed in sections IV and V. In order to demonstrate the abilities of the understander, a simple question answering system is used to inspect the model. Since our interests lie in guiding the generalization process through the use of causal relationships. this subsystem is primarily used for accessing the reasons why an actor performed a certain action or why a particular state exists. This information is easily retrieved by inspecting the support links between the various states and actions in the model. Of course, there are many issues involved in retrieving the most appropriate answers to questions (see [Lehnert78]) which we do not fully confront in this subsystem. A simple natural language generator for translating replies into English is also included as part of the system. If an actor in a narrative achieves an important goal through a novel combination of actions. the explanalion for how the goal was achieved is generalized into a new schema. The combination of actions which supports the achieved goal state is generalized as far as possible without breaking any of the connecting support links or violating the well-formedness of individual actions and states. This genera !ired structure is then stored as a new schema in the library where it is used to facilitate the processing of future narra­ tives. This generalization process is discussed in section VI and is the key to the learning technique of explanatory schema acquisition. ## III AN EXAMPLE Currently, GE'\ESJS has acquired two new schemata. In one example, the system learns a schema for someone kidnapping an indi vidual and holding them for ransom. ln the other, it learns a schema for someone burning his own building to collect the insurance. Here we \\"ill show the performance of the system on the kidnapping example. Before processing the following narratives. GEl\ESIS contains information in its schema library about bargain­ ing, capturing and confming indi viduals. threatening. and many other concepts; however, it does not have a schema for kidnapping for ransom. First it receives the following "test" narrative: ll\PUT: Ted is the husband of Alice. He won S 100000 in the lot­ tery. Bob imprisoned Alice in his basement. Bob got S75000 and released Alice. Processing Story\_ Finished processing. No thematic goals achieved by a novel combination of actions: no generalization. Ready for questions: ? (Who gave Bob the money) Answer unknown. ? (Why did Bob lock Alice in his basement) Cannot find sufficient reason for his action. ? (Why did Bob release Alice) Cannot find sufficient reason for his action. Notice that in this narrative it is not mentioned how Bob got the money or why Bob imprisoned Alice and then released her. Since the system does not have a schema for kidnapping, it cannot infer the missing information and construct a causally complete explana­ tion of the narrative. Next, it is given the following narrative. INPUT: Fred is the father of Mary and is a millionaire. John approached Mary. She was wearing blue jeans. John pointed a gun at her and told her he wanted her to get into his car. He drove her to his hotel and locked her in his room. John called Fred and told him John was holding Mary captive. John told Fred if Fred gave him S 250000 at Trenos then John would release Mary. Fred gave him the money and John released Mary. Processing Story\_ Finished processing. John achieved the thematic goal: John has S 250000. Generalizing- Assembling new schema: CAPTURE-BARGAIN. Ready for questions: ? (Why did John imprison Mary in his room) So John and Fred could make a bargain in which John released Mary and Fred gave John 250000 dollars at Trenos restaurant. ? (Why did John make the bargain with Fred) Because John wanted to have 25000 dollars more than he wanted to hold Mary captive. ? (Why did Fred make the bargain with John ) Because Fred wanted !'\'lary to be free more than he wanted to have 250000 dollars. ? (Why did Fred want Mary free) Because Fred was Mary's father. Unlike the first narrative, this one is detailed enough to allow GENESIS to causally connect the individual actions. The resulting causal structure is then generalized into a new schema of kidnap­ ping for ransom (which GENESIS calls CAPTURE BARGAIN). Next, the system is given the first narrative again, and using the schema it has just acquired. it is able to infer the missing information and causally connect the actions. Consequently, it is able to answer the questions which previously it could not answer. INPUT: Ted is the husband of Alice. He won S 100000 in the lot­ tery. Bob imprisoned Alice in his basement. Bob got S75000 and released Alice. Processing Story\_ Finished processing. No thematic goals achieved by a novel combination of actions: no generalization. Ready for questions: ? (Who gave Bob the money) Ted gave Bob 75000 dollars. ? (Wh.y did Bob lock Alice in his basement) So Bob and Ted could make a bargain in which Bob released Alice and Ted gave Bob 75000 dollars. ? (Why did Bob release Alice) Because Bob and Ted made a bargain in which Bob released Alice and Ted gave Bob 75000 dollars. ## IV KNOWLEOOE REPRESENTATION GENESIS' knowledge is represented in a library of schemata: packets of general information about stereotypical objects, situa- I I I I I I I I tions, and actions. All schemata in the library are arranged in a hierarchical inheritance net under the three major classes of ACTION, STATE, and OBJECT (the highest level class is simply called SCHEMA). Each schema has a set of roles associated with it which can be filled by other schemata to create an instance of the schema. The type of information associated with a schema depends on whether it is an ACTION. STATE, or OBJECT so each of these will be discussed in turn. ACTION schemata represent dynamic events which change the state of the world. The following pieces of information are attached to ACTION schemata. In addition to the information attached directly to a particular schema, each ACTION inherits the informa­ tion attached to ACTIONs above it in the abstraction hierarchy. Role Constraints: Defaults: Preconditions: Motivations: Effects: Terminations: Expansion Schemata: Suggested Schemata: Each role is marked with the type of schema which can legally fill iL Default fillers can be specif1ed for each role. States which must be true in order for the action to take place. States (BELIEFs and GOALs) which explain why an actor would perform this action. States which are true after the action is performed. States which are no longer true after the action is performed. (These are similar to the delete-lists in STRIPs but states are temporally marked as no longer holding instead of being deleted from the model.) A set of lower-level states and actions which actually make up this action along with the support relationships between them (similar to the body of a script). Larger composite actions which this ac­ tion may be a part of. Determining Conditions: A set of lower-level actions and states which if all present indicate the oc­ currence of this action. STATES, on the other hand, represent relatively static situa­ tions in the world, such as an individual being someone's father or being in possession of some objecL The following pieces of informa­ tion are attached to STATE schemata. In addition to the information attached directly to a particular schema, each STATE inherits the information attached to STATEs above it in the abstraction hierar­ chy. Role Constraints: Each role is marked with the type of schema which can legally fill iL Defaults: Default fillers can be specified for each role. Inferences: Other states which are reasonable inferences to make from this state. Achieving Actions: Actions which can be used to achieve this state. OBJECTs represent types of things in the world. The informa­ tion attached to OBJECT schemata varies from class to class. Com­ mon examples for physical objects would be defaults for size, shape, and other physical attributes. ## V THE UNDERSTANDING PROCESS Since applying explanatory schema acquisition depends on having a causal chain of actions to generalize, the "understanding" ability of GE:'-/ESIS is concentrated on constructing this chain by inferring missing information and causally connecting inputs together. \Ve do not attempt to deal with other important issues which have recently occupied researchers in narrative understand­ ing such as plor units [Lehnertli2l thematic abstractions units [Dyer83l story points [Wilensky!i3l affect [Dyer83l and iruegr·ated parsing [DeJong82, Dyerli3! In accomplishing the task of constructing caus;~l wnnections, GENESIS, like FAUSTUS [l\:orvig83, Wilenskyli3l uses a combina­ tion of top-down and bottom-up processing techniques. If a set of inputs in a narrative matches a schema which the system already has, then it uses top-dov.·n processing to fill in the exparuum of this Schema with the particular inputs of this narrati\'e, much like a script driven program such as SAM [Cullingfnrd78) or FRUMP [DeJong82! However, if an action in the narrative is not explained by a known schema, it attempts to rnnnrl'l it to other actions and states in the narrative by searching for existing states which fulfill the preconditions for this action, or by hypothesizing intermediate actions which causally connect it to existing states or actions. In this way, it also operates in a more bottom-up fashion like plan· based programs such as PAM [Wilensky83! ## A. Schema Activation and Determination If a schema-based system is to be able to process a range of possible inputs, it must have access to a large number of schemata. Therefore, in order to avoid repeated searching through the entire database of schemata, it must also have an efficient method for selecting the particular schemata which are applicable to the current inpuL Several researchers have addressed this difficult problem [Charniak78, DeJong82, Norvig83) and below is a brief description of the approach GENESIS uses. When GENESIS processes an input, it adds it to the model and activales all the schemata in the list of suggested sclu!ma.ta attached to the schema class of the inpuL Active schemata then monitor subsequent inputs and check if they match parts of its expansion and can therefore be considered part of this active schema. When all the determining conditions of an active schema are met, it is determined or considered to have occurred in the nar­ rative and is added to model along with the schemata and support relationships given in its expansion. 2 If a determining condition is an action, then it is also considered to have occurred if all of its effects are in the model. ## B. Bottom-up Construction of Support Relationships When a new schema instance is added to the model (either as the result of an input or an inference on the part of the system), the system first tries to explain it as part of a known schema. How­ ever, if the new instance does not suggest any higher-level sche­ mata nor match part of any already active schemata, then GENESIS tries to causally connect it to other actions and states in the model using planning information. The first step in integrating a new schema instance into the model is to add any primary inferences or effects. The effects and inferences attached to a schema are divided into primary and .l'econda,·y categories. Primary ones are used in a forward inferenc· ing fashion while secondary ones are used in a back wards inferenc· ing fashion and only added to the model if they are required by the explanation. If the new instance is an action, then its preconditions must be reconciled with the model. This means that it first searches the model for each precondition and if it finds it, it adds an appropri­ ately labeled support link from it to the new action. If it does not ftnd a precondition, it next attempts to infer it by searching for secondary effects or inferences which match this precondition. If this also fails, it hypothesizes the existence of an action which can i'X' used to achieve this p~econdition (using the achieving actions attached to this state) and attempts to reconcile its preconditions with the model. GENESIS also attempts to find motivations for volitional actions. It does this by checking if the action achieves a state which is a goal for the actor, or if it the actor has the specific goals and beliefs marked as possibly motivating this action. Goals which arise from known themes [Schank 77) can be automatically inferred if they will motivate a character's action. Such goals will be called therrw.tic goals and represent the highest level goals which motivate a person. Goals of possessing money, satisfying hunger, and preserving one's health are examples of thematic goals. 2 The term determined is borrowed from FAUSTUS [Norvig83] which also uses a multi-step schema selection process. Other plan-based understanding systems such as PAM [Wilen­ sky83) used planning information to predict future courses of actions a character might take. However, searching through a space of possible future actions is combinatorially explosive. Conse­ quently, such an approach is intractable if a system's knowledge of actions is large, which it obviously must be if it is to be able to understand a wide range of narratives. For example, if a PAM-like system were used to process the detailed kidnapping narrative, it would conduct an exhaustive search for an explanation of why John captured Mary before continuing to process the rest of the text. If the system had a large knowledge base of actions, it would be a long time before it stumbled upon the idea of using the action of releasing Mary as part of a bargain with another person. Since GENESIS does not conduct a complete search for an explanation, it is incapable of "understanding" narratives which have large gaps and do not suggest known schemata. When the first kidnapping narrative is processed without a schema for "kid­ napping for ransom," very little of the missing structure can be inferred and the only support links the system can construct are shown in figure 2. As a result, it is unable to answer the questions shown earlier. However, with the same initial knowledge, it is able to understand the second narrative because the gaps and missing int"ormation are not too severe. Consequently, the understander is Fi\6ure 2: Support Net work for Narrative #I Before Learning ![Image](https://ijcai.org/proceedings/1985/fulltext/132/image_000001_37c47c7f79068ab5ec57edffa91d16ea0f3213153f8f93c16f537a7e1235eca8.png) able to construct the support network shown in figure 3. It should be noted that the support networks shown in this paper (called highesr-level support networks) contain only the highest level sche­ mata which were determined to be in the narrative. Most of the representation at the level of the inputs and their connecting infer­ ences is contained in the expansions of the CAPTURE and BARGAIN schemata which were activated bottom-up from the inputs. As indicated earlier, this structure is then generalized into a new schema. When the first narrati ve is processed again, Bob's action of imprisoning Alice in his basement determines a CAPTURE schema, and this in turn suggests the new "kidnap" schema. The new schema is then used in a top-down fashion to fill in missing information. It is finally determined when both of the effects of the BARGAIN: Alice becoming free again and Ted receiving money, are added to the model. The final support network (the expansion of the ne~· schema for this narrative) is shown in figure 4. This causal structure allows the system to answer the questions it could not answer before learning the schema. ## VI THE GENERALIZATION PROCESS Once a causally complete explanation has been constructed for a narrative, GE?\ESIS determines whether or not it can be used to learn a useful new schema. If so, it generalizes the causal struc­ ture in the model into a new schema and ·stores it in the schema library where it can be used in the processing of future narratives. Figure 4: Support Network for Narrative #1 After Learning ![Image](https://ijcai.org/proceedings/1985/fulltext/132/image_000002_dacf0edfe631cd363ba3c7ddd0c2d0fa36ce483e5f09fa96de5c223b65a04081.png) ## A. When to Generalize If every combination of actions the system encountered was generali?.ed into a new schema, the system would soon become over­ loaded with rarely used schemata. Most actions would activate a large number of schemata and selecting among these would require an excessive amount of processing time. In order to avoid this prob­ lem, ,-enain conditions must be met before a combination is general­ ized. First, the combination of actions shnuld achieve a goal for one of the characters in the narrative. In the process of motiYating anions, the understander checks if an action achie\·es a goal for a character. so finding achie\·ed goals is a simple matter of inspecting the moctel. Second, this goal should be a common one which is likely to be encountered again. A goal is considered to be common enough if it is a thematir goa l, for example satisfying hunger or acquiring money. Since in the sample narrative John achieves the thematic goal of possessing money, it satisfies both of these condi­ tions. The final condition for generalization is the obvious one of not already possessing a schema for the combination of actions which ad1ieves the thematic goal. This simply involves checking the highest-level support for the achievement of the goal and making sure it contains a combination of actions. If the system already had a schema for th1s case, it would have used it in processing the nar­ rati ve and the goal would be supported by an instance of this schema instead of a combination of actions. Additional conditions for generalization were discussed in [DeJong83~ however, these are currentl y not implemented. ## B. Generalizing the Support Network After deciding to generalize, the system extracts the explana­ tion for the goa l state, isolating the actions and states which actu­ ally contribute to its achievement. This simply involves extracting the highest-level support for the achieved state. In the example, the achieved state is John possessing $250,000 and the support for this state is shown in figure 3. This step eliminates extraneous informa­ tion in the narrative which does not contribute to the achievement of the goal, such as the fact in the example that Mary was wearing blue jeans. Once the support network is extracted, there are several steps involved in constructing a generalized version of this causal struc­ ture. The overall approach is to initially generalize as far as possi­ ble and then re-introduce only the constraints necessary to main­ tain the causal connections bet ween schemata and the well­ formedness of individual schemata. Initially, the class of each schema instance is generalized to SCHEMA (the highest level in the hierarchy) and each role filler is replaced by a unique new parame­ ter. Constraints are then imposed on this over-generalized structure to make it a well-formed causal network. These constraints progres­ sively refine the class of each instance and constrain certain role fillers to be equal. First, the goal which the support network achieves is con­ strained to be a thematic goal. This is accomplished by constraining it to match the pattern for the thematic goal which was achieved in the original narrative. In the kidnapping example, this con­ strains the goal state to be the kidnapper acquiring money. Next the interschenUl constraints are imposed. These involve maintaining the validity of each connecting support link in the network. We will use the kidnapping narrative to illustrate this process by showing how the FATHER relationship in its support net­ work is only constrained by the explanation to be a POSJm·E-JPT (for posi tive-interpersonal-theme, a superclass of rARENT, SPOUSE. etd. tvery time a support link is adde.d during understanding, it is annotattd with the pattern from the schema library used to con­ struct it <md thf class in the schema hierarchv where it was inher­ ited from. In the example, when GENESIS infers that Fred wants Mary frt t more than he want.~ to have $250000 as a secondary inference f'rom the fact that he is her father, it annotates wilh the corresponding inference pattern from the schema library and the fact that this inference was inherited from the schema POSJTI\'E·IPT. When the interschema constraints for this link are imposed, the ransom payer's GOAL·PRIORITY is constrained to match the system's inferen(.'t patttrn, and the instance which was a FATHER state in the original narrative is constrained to be a POSJTJVE-JPT. Thus, the sys­ tfm only Imposts tht required relationship between the individuals filling the roles of kidnap victim and ransom payer. The fact that there was a specific father-<iaughter relationship in this particular narrative is recognized as incidental and not crucial in maintaining the validity of the explanation. Next, the intraschenw constraints are imposed. These concern maintaining the well-formedness of each individual schema instance. This is accomplished by imposing on the filler of each role the appropriate role constraint from the schema library. For exam­ ple, since the role constraints specify that the SUBJECT of a POSSESS schema be a PERSON, the SUBJECT role filler of each POSSESS schema in the support network is constrained to be a PERSON. The final step in constructing a generalized support network is to merge parameterized instances which have been constrained to be equal. The resulting instances form a set of conceptual roles for the overall schema. In the example, this collects together all the indivi­ dual occurrences of the kidnapper, the victim, the ransom payer, and the ransom money and creates a unique OBJECT for each one. The result of this generalization process is a general causal structure which achieves a common goal. The generalized support network generated for the kidnapping example is shown in figure 5. Figure 5: Generalized Support Network for Narrative #2 ![Image](https://ijcai.org/proceedings/1985/fulltext/132/image_000003_c1dfd056a11163c4c5c71fc79a09f629e18bc8989130296fb49695d2999daa57.png) ## C. Packaging Into a New Schema The final step in acquiring a new schema is separating the generalized support network into preconditions, effects, expansion schemata, etc~ which can be added to the schema library. Following is an outline of how this information is extracted. Roles (with constraints): The subject of the achieved thematic goal becomes the actor of the new schema. New roles are created for each remaining person and object in the generalized sup­ port network. In the example, roles are created for the kidnapper, victim, ransom payer, and ransom money. Preconditions: Motivations: STATES which are leaves of the general­ ized support network but not motivalions of actions by the main actor. In the exam­ ple, the ransom payer possessing the ran­ som money is a precondition. STATES which are leaves of the general­ ized support network and motivalions of actions by the main actor. In the example, the kidnapper wanting to have money is a motivation. | Effects: | Effects of all actions within the general­ ized support network which are not ter­ minated by other internal actions. In the example, the kidnapper possessing the ran­ som money is an effect. | |-------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | Terminations: | STATES which are terminated by an action within the generalized support network but not produced by another internal ac­ tion. In the example, the ransom payer no longer possessing the ransom money is a termination. | | Determining Conditions: | The set of all ACTIONS within the general­ ized support network. In the example, the bargain between the ransom payer and the kidnapper is a determining condition. | | Ex pansion Schemata: | All remaining schemata in the generalized support network along with their con­ necting support relationships. | | Suggested Schemata: | The schema for each action within the generalized support network is marked as suggesting the new composite action. In the example, the schema CAPTURE now suggests the new schema. | ## VII RELATION TO OTHER WORK The process just described uses a database of background knowledge to generalize the causal structure or explanation of a single example. This approach differs dramatically from most approaches to learning (e.g. [Michalski83, Mitchel178, Winston70)) in which generalization is accomplished by extracting features \\" hich are shared by a number of examples. GENESIS' genera lization process is most similar to the method used by STRIPS to generalize planning sequences into new MACROPs [Fikes72~ However, unlike STRIPS. GENESIS generalizes actions and states as weJI as objects and locations, and generalizes the order of independent actions (since it uses a dependency net­ work instead of a linear ordering of steps). The general technique used by GENESIS. explanatory schema acquisition, is also being applied to learning theorem proving stra­ tegies [O'Rorkeb4l robot assembly tasks [Segre85l and concepts in physics problem solving [Shavlik85~ Explanatory schema acquisi­ tion is closely related to a growing body of recent work in ex planation-based or analytic learning [Minton84, Mitchel183, Silver83, Winston82l which is characterized by learning from a single example through the analysis of its causal structure. However, there are also important differences between expla­ natory schema acquisition and some of the other work referenced above. While GENESIS learns from the problem solving behavior of other agents, STRIPS and Mitchell's LEX learn from their own problem solving. Although learning from external behavior makes a system less autonomous, it allows a system to learn plans which are beyond its own ability to generate. In addition, LEX only learns heuristics for apply ing operators it already possesses and not new combinations of operators which achieve important goals (MACROPs or schemata). Although Winston's system, like GENESIS, learns from short narratives, it learns if-then rules and not schemata. In addition, Winston's system does not need to infer causal connections during "understanding" since all causal connec­ tions are given explicitly in the input text. ## Vlll CONCLUSION Unlike most learning systems, explanatory schema acquisition does not depend on correlational evidence. Thus, it is capable of one trial learning. Also, it avoids the problem of searching through a large space of features for ones which are relevant to a new concept. Only features which contribute to the explanation of an achieved goal are considered for inclusion in the description of a concept. The approach is heavily knowledge-based; a great deal of background knowledge must be present for learning to take place. hnally, the system does not increase its representation power with this kind of learning. The learning results in greatl y improved effiCiency of processing by avoiding combinatoria lly explosive searches. In the future v.·e plan to address the issue of schema refinement. Clearl :;. the system ought to have the capabi lity of r~fming existing schemata if the system is presented w ith an exam­ ple whit"h violates its expectations. We also hope · to explore language learning. It should be possible to acquire the English names for these new problem solving schemata from context. This direction of parallel and interacting language and concept develop­ m~nt should complement existing work on inducing grammars [Berw ickl\2) and learning to attach new names to known concepts [Se lfridgel\1~ ## ACKNO~EMENTS We would like to thank Paul O'Rorke and Alberto Segre for helpful comments on various versi.ons of this paper. ## References 1. R. Berwick, "Locality Principles and the Acquisition of Syntactic Knowledge," Ph.D. Thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, 1982. 2. W. F. Brewer, "Plan Understanding, Narrati v e Comprehension, and Story Schemas," Proceedings of the National Conference on Artificial Intelligence, Pittsburgh, PA, August 1982, 262- 264. 3. E. Charniak, "MS. MALAPROP, A Language Comprehension System," Proceedings of the Fifth International Joint Conference on Artificial intelligence, Cambridge, MA, 1977. 4. E. Charniak, "With Spoon in Hand this Must be the Eating Frame," Theoretical Issues in Natural Language Processing 2, Urbana, IL, 1978. 5. R. E. Cullingford, "Script Application: Computer Understanding of Newspaper Stories," Technical Report 116, Department of Computer Science, Yale University, New Haven, CT, January 1978. 6. G. F. DeJong, • An Overview of the FRUMP System," in StraJegies for Natural .UZnguage Processing, W. Lehnert and M. Ringle (ed.), Lawrence Erlbaum and Associates, Hillsdale, NJ , 1982. 7. G. DeJong, • Acquiring Schemata through [DeJong85) [Doyle78) Understanding and Generalizing Plans," Proceedings of the Eighth lnte••national Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, 1983. 8. G. DeJong, R. :\1ooney, P. O'Rorke, S. Rajamoney, A. 1\1. Segre and J. Shavlik, "A Review of Explanation-Based Learning," Technical Report in preparation, Coordinated Science Laboratory , Urbana, IL, 1 %5. 9. J. Doy le, "Truth Maintenance Systems for Problem Solving." Technical Report Technical Report-41 9, MIT Artificial Intellige nce Lab, Cambridge. \1 A. 197b. [Dyer83) rikes72) 10. Lehnert 78) Lehnert82) Marcus80) Michalski83) Minsky75) Minton84) Mitche1178) Mitche1183) !\1ooney85) [:\orvig83) 11. O'Rorke84) [Schank75) 12. Srhank77) 13. M. Dyer, In Depth Understanding, MIT Press, Cambridge, MA, 1983. 14. R. E. Fikes, P. E. Hart and !\. J. Nilsson, "Learning and Executing Generalized Robot Plans," Ar•tijtcial 1 ntelligence 3, ( 1972), 251-288. 15. W. Lehnert. The Process of Question Answering, Lawrence Erlbaum and Associates, Hillsdale, !\J, 1978. 16. W. G. Lehnert. "Plot Units: A Narrative Summarization Strategy," in Strategies for Natural Language Processing, M. H. Ringle (ed.), Lawrence Erlbaum and Associates, Hillsdale, NJ, 1982, 375-414. 17. M. P. Marcus, A Theor•y of Syntactic Recognition for Natyral Language, MIT Press, Cambridge, MA, 1980. 18. R. S. Michalski, "A Theory and Methodology of Inductive Learning," in Machine Learning: An Artificial Intelligence Approach, R. S. Michalski, J. G. Carbonell, T. M. Mitchell (ed.), Tioga Publishing Company, Palo Alto, CA, 1983,83-134. 19. M. L Minsky, "A Framework for Representing Knowledge," in The Psychology of Computer Vision, P. Winston (ed.), McGraw-Hill, New York, NY, 1975, 211-277. 20. S. Minton, "Constraint-Based Generalization: Learning Game-Playing Plans from Single Examples," Proceedings of the National Conference on Artificial Intelligence, Austin, TX, August 1984, 251-254. 21. T. 1\1. Mitchell, "Version Spaces: An Approach to Concept Learning," ST AN-CS-78-711, Stanford University, Palo Alto, CA, 1978. 22. T. Mitchell, "Learning and Problem Solving," Pr•oceedings of the Eighth In1ernational Joint Conference on Artificial Intelligence, Karlsruhe, West Germany, 1983,1139-1151. 23. R. \1ooney, "Generalizing Explanations of !\arratives into • Schemata," Technical Report T- 147, Coordinated Science Laboratory, University of 111inois, Urbana, IL, May 1985. 24. P. :\orvig, "Frame Activated Inferences in a Stor ~• Lnderstanding Program," Pr•oceedings of t/,e Eighlh International Joint Conference on Artificial Intelligence, karlsruhe, \\'est Germany, August 19113, 624-626. 25. P. O'Rorke, "Generalization for Explanation-based Schema Acquisition," Froceeeding . 1 • of th~ National Con f er•ence On Artificial I ntelligencc, Austin, TX, August 191\4. 26. R. C. Schank, Conceptual Information Processing, North-Holland/ American Elsevier, Amsterdam, 1975. 27. R. Schank and R. Abelson, Scripts, Plan s. Goals and Understanding: An Inquiry into H uman Knowledge Structures, Lawrence Erlbaum and Associates, Hillsdale, :\J, 1977. 28. A. 1\1. Segre and G. F. DeJong, "Explanation Based • Manipulator Learning: Acquisition of Planning Ability Through Observation," Proceedings of the IEEE In1ernatioTUll Con/erence on Robotics and Automation, St. Louis, MO. March 1985. 29. If ridge81) [Shavlik85) Silver83) Waltz84) 30. Wilensky83] 31. Winston70) 32. R. Mooney and G. DeJong 687 !\1. Selfridge, "A Computer \1odel of Child Language Acquisition," Proceedings of the Seven1h InternatioTUll Joint Conference on Artificial Intelligence, Vancouver, B.C. , Canada, August 1981, 446-451. 33. J. Shavlik, "Learning about Momentum Conservation," Proceedings of the Nin1h International Joint Confer•ence on Artificial Intelligence, Los Angeles, CA, 1985. 34. B. Silver, "Learning Equation Solving Methods from Worked Examples," Proceedings of the 1983 In1et•national Machine Learning Workshop, Urbana, IL, June 1983, 99-104. 35. D. L Waltz and J. B. Pollad., "Phenomenologically Plausible Parsing," Proceedings of the National Conference on Artificial ln1clligence, Austin, TX, August. 1984. 36. R. W. Wilensky, Planning and Understanding: A Computational Approach to Human Reasoning, Advanced Book Program, Addison-Wesley, Reading, MA, 1983. 37. P. H. Winston, "Learning Structural Descriptions from Examples," AI Technical Report-231, MIT Artificial Intelligence Lab, Cambridge, MA, 1970. 38. P. H. Winston, "Learning ]\ew Principles From Precedents and Exercises, • Artificial I ntelligencc 19, (1982), 321-350.