«Abstract Combinatorial explosion of inferences has always been a central problem in arti cial intelligence. Although the inferences that can be drawn ...»
3.3.2 Knowledge goals derived from other goals An entity that uses a knowledge base in the pursuit of its goals has a much more speci c basis for generating new knowledge goals. By analyzing the relationship between its knowledge and its speci c current goals, a learner can devise knowledge goals that directly facilitate the accomplishment of those goals. That is, knowledge goals can be subgoals to other performance goals.
People often generate goals for information that will help them accomplish other tasks. Schank and Abelson 1977] proposes the goal D-KNOW (change knowledge state) as a subgoal for accomplishing some other goal. Their example was the story \Willa was hungry. She took out the Michelin Guide." The actor in this story wanted to know the names and locations of restaurants in order to pick one to eat in.
Other kinds processing can also be used to generate knowledge goals as subgoals to other goals. For example, an animal that associates a particular location both with a good water source and with periodic attacks from predators may be motivated to nd a good hiding place or escape route near that location.
From a story understander's point of view, a fact that answers a question is worth focussing on since it helps to achieve a knowledge goal of the understander, which in turn allows the understander to continue the reasoning task that was awaiting the answer. Also, an inexplicable or anomalous fact is worth focussing if the questions arise from a gap or inconsistency in the understander's knowledge base, since the understander may be able to improve its knowledge base by learning something new about the world. AQUA uses heuristics of this kind, called interestingness heuristics, to decide which knowledge goals to generate and pursue Ram, 1990c].
A somewhat less direct relationship between the goals that an entity is pursuing and the generation of new knowledge goals can be found in goals generated in response to failures. If a goal pursuer is using knowledge to accomplish a goal and unexpectedly fails to achieve the goal, an analysis of the knowledge used may be useful for generating new knowledge goals. This, of course, is the strategy for generating knowledge goals used in IVY. In addition, it may also be possible for a learner to detect knowledge that it needs to acquire by simulating the execution of a proposed plan, rather than waiting for a failure to occur.
In order to generate knowledge goals on the basis of analysis of a goal failure, however, a learner must be able to analyze the processes and knowledge that it was using when the failure occurred. In other words, it must have knowledge about what it was doing, a particularly useful sort of self-knowledge. It is, of course, possible to execute a sequence of actions without knowing the relationship between the actions and the results. On the other hand, an entity that knows the relationship between the actions involved in a sequence and the ultimate result has an advantage over an entity that doesn't. With that knowledge comes the ability to manipulate the process, adapt parts of it to other uses and explain failures. Goals to identify the separable steps in a sequence of actions and to acquire knowledge about their function therefore have an adaptive value. The same is true for nding out about objects that play a role in goal pursuit.
3.3.3 Knowledge goals that arise from analysis of the structure of knowledge Maintaining a large memory of useful knowledge requires organizing it so that it is computationally feasible to retrieve the right piece of knowledge at the right time. This organization also makes possible the generation of an additional class of knowledge goals: those based on an analysis of the structure of existing knowledge.
Consider the structure of a pathologist's knowledge of disease. For pathologists, a disease consists of an etiology (cause), pathogenesis (loosely speaking, the e ects of the disease on the body), and the prognosis (information about the course of the disease useful for making predictions). When a pathologist encounters a novel instance of any of these aspects of a disease, he generates knowledge goals for the other two aspects of that disease. For example, if a pathologist notes an unusual disease course, he wants to know what about the origins or appearance of the disease was also unusual. Of if a pathologist sees a disease with a novel appearance, he then desires information about the origins and expected course of the new disease.
What kinds of characterizations can lead to the formations of new knowledge goals? In the pathology example above, it is an assessment of the completeness of knowledge of an object or process. In order to generate knowledge goals on this basis, there must be some abstract description of what counts as complete knowledge. In the pathology example, this description is expressed in the assertion that every disease has an etiology, pathogenesis and prognosis. Perhaps the most general characterization of the completeness of knowledge is the idea that everything has a cause. A learner that believes this may generate knowledge goals to nd the cause of everything it knows. Other general completeness considerations may lead to the formation of knowledge goals about the composition of objects or the goal priorities of agents, and so on.
Completeness is not the only structural characteristic of knowledge that can be used to generated goals.
A second important structural characterization of memory can be made on the basis of connectivity. More densely interconnected knowledge is, in general, more useful in generating plans or explanations than knowledge which is less closely related to other knowledge. This observation indicates that there may be knowledge goals to determine the relationships between seemingly independent sets of knowledge. The potential number of relationships to explore is very large, so there must be some additional direction to the search for relationships between classes of knowledge. One source of direction may be similar causal factors. For example, the discovery that a single causal agent plays a role in two disparate domains is a good reason to generate goals for determining other relationships between the domains.
There is a risk with both of these methods of generating knowledge, because the number of knowledge goals that might be generated with each is potentially very large. The process of managing the activation of knowledge goals, described below, may help ameliorate this problem, but the generation and prioritization of knowledge goals is still very much an open research issue.
4 Using knowledge goals to guide processing A program that uses knowledge goals to guide understanding is an improvement over one that processes everything in equal detail, that is, one that is completely data-driven. For example, an understander that is completely text-driven would process everything in detail in the hope that it might turn out to be relevant.
To avoid this, the understander should draw only those inferences which would help it nd out what it needs to know. In other words, the understander should use its knowledge goals to focus its attention on the interesting aspects of the story, where \interesting" can be de ned as \relating to something the understander wants to nd out about."
It is useful to focus on knowledge goals because they arise from a \need to learn." There are two basic
ways in which a fact can turn out to be worth processing in this sense:
Figure 5: Control structure: The understanding cycle in AQUA. A fact is interesting if it satis es a knowledge goal pending in memory, or if it gives rise to new knowledge goals. Uninteresting facts pass vertically down with minimal processing; interesting facts cause suspended understanding tasks to be restarted, or new tasks to be created. New tasks can give rise to new knowledge goals, which are suspended along with the tasks if answers are not yet known and cannot be inferred.
Top-down: A fact that helps achieve a knowledge goal, or answers a pending question, is worth focussing on since it allows the reasoning system to continue the reasoning task that required the knowledge in the rst place.
Bottom-up: A fact that gives rise to new knowledge goals, or raises new questions, is worth focussing on if the knowledge goals arise from a gap or inconsistency in the reasoning system's knowledge base, since the system may be able to improve its knowledge base by learning something new about the world.
These correspond to the two diamonds in gure 5.
4.1 Theory of inference control Ideally, only those inferences should be drawn that lead to conclusions that the program needs to know. But this is not always possible in practice. Given that the basic task of a knowledge goal-based understanding program is to try to answer questions in its memory by reading stories, there is an obvious choice to be made
in the design of the program as characterized by the following extremes:
Text-driven: A text-driven program would read the text, build representations for it, and then process it to see if it addressed any knowledge goals in memory.
Goal-driven: A program that was totally goal-driven would pick the most interesting or urgent knowledge goal in memory and try to answer it via inference, reading text, or indeed any other method it had available.
A similar dichotomy arises in the design of problem-solving programs as well. Each of these approaches has its disadvantages. The text- or data-driven method is completely bottom-up. It tries to process in detail everything in the hope that it might turn out to be relevant. Instead, we would like the program to concentrate on those aspects that were of interest to it. In other words, we would like the process to be driven by the interests or goals of the reasoner.
The goal- or question-driven method, when taken to the extreme, is too top-down. A program built using this method would only see what it was looking for already. Furthermore, rather than expending resources in trying to pursue a knowledge goal immediately, it might be advantageous to index the knowledge goal in memory, to be satis ed later when the opportunity arises. Finally, so as not to overlook obvious information and be su ciently sensitive to the exigencies of the input, the process should be data-driven as well. The interaction between these requirements is non-trivial.
AQUA is designed as a compromise between these two approaches. The basic understanding cycle that it uses is as follows. The parser reads the story word by word, trying to build a basic conceptual structure to represent the input. As quickly as possible, this structure is related to pending knowledge goals in memory.
If the new structure satis es a knowledge goal, the suspended understanding task that was awaiting that piece of knowledge is restarted. Thus the program only draws those inferences that are required to match the new structure to its knowledge goals, and, after the suspended task is restarted, those that are demanded by the task that generated the knowledge goal in the rst place.
This method is called \graded parsing" or \variable-depth parsing". The process is data-driven to the extent that pieces of the input for which there are no explicit expectations but which are likely to be relevant are processed to the extent necessary to determine their relevance. In practice, this means that there is a set of bottom-up processes that the program always runs on incoming text. Further processing of the input is done only if these processes generate knowledge goals, or if the input turns out to satisfy a knowledge goal already in memory.
The real issue here, of course, is how much inference should be done at the time the knowledge goals are
generated, and how much should be done when the input comes in. The answer depends on six factors:
1. Certainty of inference: The probability of the inference rules used to nd or infer answers to knowledge goals, or the likelihood that the conclusions will be true. In a logic system where an inference rule represents a deduction, this probability is 1.
2. Cost of inference: The cost of making inferences or of matching and applying inference rules. The cheaper the inference, the more it is worth the system's while to make it.
3. Usefulness of knowledge goal: The usefulness of the conclusion that the knowledge goal is seeking.
Since knowledge goals are generated in service of reasoning tasks, this is the same as the importance of performing that task. If the task is very important, it is worth making the inference even if it is very expensive to do so.
4. Likelihood of knowledge goal being useful: The likelihood that the knowledge goal will be useful, i.e., the likelihood that the knowledge will actually turn out to be useful in performing the reasoning task. If knowledge goals are only generated from tasks that absolutely require that knowledge (as opposed to those that may be facilitated by that knowledge if it were present), this likelihood is 1.
5. Indexing cost: The cost of keeping indexed questions in memory and matching to them. If there are too many questions in memory, it might be too expensive to nd them or to match input to potentially relevant questions. This cost depends on the scheme used to maintain questions in memory, and is discussed below.
6. Likelihood of knowledge goal being satis ed: The above factors are \content-free" heuristics in the sense that the reasoning system does not rely on knowledge of the content or types of knowledge goals that it is likely to generate, or on the content or types of inferences that the system is likely to make when given new input. In addition, one would like the system to generate the types of knowledge goals that are likely to match the inferences normally made by the bottom-up processing that is always performed on incoming facts. The last criterion for inference control, therefore, is the likelihood of a knowledge goal being satis ed, which depends on knowledge about the inferences that are likely to be made by the system's own inference processes.