«Abstract Combinatorial explosion of inferences has always been a central problem in arti cial intelligence. Although the inferences that can be drawn ...»
Memory goals: Knowledge goals of a dynamic memory program, arising from memory-level tasks. A dynamic memory must be able to notice similarities, match incoming concepts to stereotypes in memory, form generalizations, and so on. An example memory goal might be to look for an event predicted by stored knowledge of a stereotyped action, such as wondering about what the ransom will be when one hears about a kidnapping.
Explanation goals: Goals of an explainer that arise from explanation-level tasks, including the detection and resolution of anomalies, and the building of motivational and causal explanations for the events in the story in order to understand why the characters acted as they did, or why certain events occurred or did not occur. An example explanation goal might be to gure out the motivation of a suicide truck bomber mentioned in a story.
Relevance goals: Goals of any intelligent system in the real world, concerning the identi cation of aspects of the current situation that are \interesting" or relevant to its general goals. An example here might involve looking for the name of an airline in a highjacking story if the understander were contemplating travelling by air soon.
Figure 2: Questions underlying the religious fanatic explanation for suicide car bombing, showing the relationships between tasks, knowledge goals, and input.
2.1.2 AQUA's use of its knowledge goals Each of AQUA's knowledge goals type is expressed as a question that focuses on a di erent aspect of the story. For example, explanation questions focus on di erent types of anomalies, and on explanations for these anomalies. Asking an anomaly detection question is essential to detecting the corresponding anomaly.
For example, asking the question \Does the actor want the outcome of this action?" is essential to the detection of a goal violation anomaly, in the sense that the program could not notice the anomaly if it did not focus on the goals of the agent, that is, if it did not think of asking the question.
To put this another way, the questions asked by the understander a ect the nal understanding that the understander comes to. Thus it is important for the understander to ask the \right" questions in order to achieve a detailed understanding of the situation. For the purpose of understanding stories involving motivations of people, we have developed a taxonomy of motivational questions that focus on those motivational aspects of stories that are needed to build volitional explanations based on the planning/decision model that underlies AQUA's theory of explanation Ram, 1990a]. A small part of this taxonomy is shown in gure 3, which depicts basic questions the system asks in explaining an agent's actions.
The taxonomy of questions is based on the understanding tasks that AQUA needs to perform when it reads a story. In addition to their theoretical role in our model of inference control and interestingness, knowledge goals have also played an implementational role in our research by providing a uniform mechanism for the integration of various cognitive processes. For example, knowledge goals arising from, say, memory tasks are indexed in memory and used in the same way as knowledge goals arising from explanation tasks. A knowledge goal generated from one task may be suspended, and satis ed opportunistically during the pursuit of some other task at a later stage or even during the processing of a di erent story. Implementational details of AQUA's opportunistic memory architecture may be found in Ram 1989].
The processing cycle in AQUA has three interacting steps: READ, EXPLAIN and GENERALIZE.
Figure 3: Anomaly detection questions represent knowledge goals arising from the process of detecting anomalies in the input.
These goals seek information needed in order to determine whether the input is anomalous. If this information is, or becomes, available, the reasoner can formulate an explanation for the anomalous input.
Read some text, focussing attention on interesting input as determined below. Build minimal representations in memory.
Retrieve extant knowledge goals or questions indexed in memory that might be relevant, i.e., whose concept speci cations are satis ed by the new input. Use these questions as an interestingness measure to focus the read above.
Answer the questions retrieved in the previous step. Unify the answer with each question, and restart the suspended process represented by the task speci cation. E.g., if the question is
in service of hypothesis veri cation:
Answer question by either con rming or refuting it.
Propagate back to the hypothesis that the question originated from.
Con rm/refute hypotheses. If the veri cation questions of a hypothesis are con rmed, con rm the hypothesis and refute its competitors. If any veri cation question of a hypothesis is refuted, refute the corresponding hypothesis.
Explain the new input if necessary, i.e., if interesting and not already explained.
The EXPLAIN step: The EXPLAIN step implements the basic explanation cycle in AQUA, which is based on Schank's 1986] theory of explanation patterns (XPs). AQUA builds on Schank's theory of explanation patterns in three ways. First, a content theory of volitional explanations for motivational analysis is proposed. Second, a graph-based representation of the structure of explanation patterns is introduced.
Third, the process of case-based explanation, while similar to that used by the SWALE program Kass et al., 1986], is formulated in a knowledge goal-based framework. Our emphasis is on the knowledge goals that underly the creation, veri cation and learning of explanations. Further details of the explanation process may be found in Ram 1990a; 1989].
Detect anomalies in input by asking anomaly detection questions Formulate XP retrieval questions Retrieve XPs that might help explain the anomaly
Apply XP to input:
If in applying the XP an anomaly is detected, characterize the anomaly and explain it recursively.
If the XP is applicable to the input:
Construct hypothesis by instantiating the explanation pattern.
Construct veri cation questions to help verify or refute the new hypothesis.
Index questions in memory to allow them to be found in the next step.
Answer questions by reading further, focussing attention on input concepts that trigger questions in memory.
Con rm/refute hypotheses when their veri cation questions are answered, as appropriate.
The GENERALIZE step: Since questions represent the knowledge goals of the understander, they
provide the focus for learning. As discussed in a later section, AQUA can:
Generalize novel answers to its questions.
Index these answers in memory, so that the task that originally generated the question would now nd the information instead of failing.
As currently implemented, AQUA's memory consists of about 700 concepts represented as frames, including about 15-20
XPs, 10 stereotypical XPs, 50 MOPs (most of which deal with the kinds of actions encountered in suicide bombing stories), 250 relations (including causal and volitional relations), and 20 interestingness heuristics (most of which are represented procedurally). The range of stories that AQUA can handle is limited only by the XPs in memory. We have focussed mostly on the domain of newspaper stories about suicide bombing, such as stories about religious fanatics, depressed teenagers, Kamikazes, and so on, although it would be straightforward to extend the program to other domains. As AQUA reads, it asks better and more detailed questions about the stories, formulates knowledge goals to answer these questions, and learns when its knowledge goals are satis ed (perhaps in a later story). AQUA can identify
and learn from three types of learning situations:
1. Missing knowledge: This occurs when AQUA does not have an XP speci c to a novel situation encountered in the story. For example, when AQUA reads a suicide bombing story for the rst time without a speci c XP that represents religious fanaticism, it can formulate a knowledge goal to learn about religious fanaticism by re ning its general knowledge about goal sacri ce.
2. Misindexed knowledge: This occurs when AQUA does have the required knowledge, but it is represented in a di erent context and hence not retrieved in the present story. For example, when AQUA reads a suicide bombing story in which the bomber is blackmailed into going on the bombing mission, it does not immediately think of blackmail as a possible explanation for suicide bombing.
After reading this story, however, it learns a new index for blackmail in the suicide bombing context.
3. Incomplete knowledge: This occurs when AQUA has the required knowledge and is able to retrieve it in the present situation, but the knowledge structure itself is incomplete. In the blackmail situation, for example, although AQUA ultimately learns to apply blackmail in a suicide bombing context, there are several questions that are still pending: How could someone be blackmailed into suicide? What could the bomber want that was more important than life? These questions constitute knowledge goals that are attached to the \blackmailed into suicide bombing" explanation, and are used to focus attention on, and learn from, relevant facts when AQUA reads future stories about suicide bombers being blackmailed.
Although we have mainly focussed on knowledge goals for the task of learning from explanations and explanation failures, other types of knowledge goals discussed earlier are also formulated by the system and pursued in a uniform manner. AQUA gradually improves its breadth and depth of understanding of the domain through the above types of knowledge goal-driven learning. We are currently extending AQUA to incorporate learning through cross-domain reasoning about knowledge goals as well.
2.2 IVY Knowledge goals are generated and acted upon somewhat di erently in the IVY program. IVY's task is to diagnose structured descriptions of lung tumor pathology images. These descriptions contain information about populations of cells taken from a lung and colored with various stains. There are many levels of description in each image, ranging from characteristics of large groups of cells (such as the shape of a glandular formation) to the presence and character of subcellular organelles. The amount of information available in a typical input is very large (on average, IVY's case descriptions contained 116 slots), and most of it is not relevant to making the ultimate diagnosis. There is also no direct mapping from characteristics to diagnoses in this domain. Many of the diagnoses are imprecise, and do not have de nitions in terms of features that are individually necessary and collectively su cient for their identi cation.
IVY, like human pathologists, uses the method of di erential diagnosis to arrive at a diagnosis. For IVY, the process involves three distinct stages. First, the image description is searched for evidence of the presence of general disease classes; this is the recognition step. Any class not explicitly ruled out is included in the rst pass hypotheses. The second pass involves specifying these hypotheses as far as possible, to create a nal di erential; this is the speci cation step. Associated with each child of a disease class is a set of speci cation rules, which are applied recursively. The last stage in the process is to pick the best hypothesis from the di erential; this is the distinction step. Some pairs of hypotheses have associated rules that specify evidence that will cause one to be preferred over the other. In other cases, general distinction rules are applied, until a single, best hypothesis remains.
Knowledge goals play a role in IVY only after the diagnosis is complete. A lung tumor pathology expert evaluates IVY's conclusions, specifying the correct diagnosis for each case. If the program's diagnosis was incorrect, the program explains its failure, and generates one or more knowledge goals. If the diagnosis was correct, it examines its pending knowledge goals to see if any of them can be satis ed.
2.2.1 IVY's knowledge goals Learning in IVY is failure motivated. Knowledge goals are generated when the program makes an incorrect diagnosis. First, IVY explains the cause of a failure (in terms of missing or incorrect knowledge) and then CORRECT HYPOTHESIS is on the DIFFERENTIAL?
Figure 4: The explanation decision tree for identifying the step in the diagnostic process that led to a failure.
transforms that explanation into a characterization of knowledge that would have prevented the failure, that is, a new knowledge goal.
The basic step in IVY's knowledge goal generation process is explanation of a performance failure.
Di erent kinds of knowledge are used at each stage of the diagnostic process. Therefore, identifying the stage of the diagnostic process at which the failure occurred is helpful in identifying the knowledge that caused the problem. Once the stage of the diagnostic process at which the problem rst appeared has been identi ed, it is possible to further specify the problem by analyzing the speci c knowledge used and the evidence gathered at that processing stage. In order to make these assessments, the explanation process must have access to some of the internal states of the diagnostician. In particular, it must have access to the hypothesis list and the evidence gathered at each stage of the diagnostic process. Such information must be stored at diagnosis time, and, along with the (externally supplied) correct diagnosis, forms the input to the failure explanation process.
IVY's explanations of failures have two components: the process that failed, and the kind of knowledge used (or not used) by that process which caused the failure. By working backwards and considering the inputs and outputs of each step, it is possible to determine where the error was made. The decision tree for identifying the step in the diagnostic process that failed is illustrated in gure 4.