«Abstract Combinatorial explosion of inferences has always been a central problem in arti cial intelligence. Although the inferences that can be drawn ...»
The above heuristics are not represented formally in the AQUA program. In other words, there are no explicit functions to compute each of these metrics and to make a decision based on them. However, the heuristics to determine the utility or interestingness of knowledge goals, and to index knowledge goals in memory, have been designed keeping these metrics in mind so that the process is e cient. More research is required to develop a theory of inference control based on the above heuristics that can be used by the reasoning system itself (as opposed to by the programmer) in making inference control decisions. The main concern in AQUA has been the formulation and indexing of knowledge goals, and their use in focussing AQUA's understanding and learning processes.
IVY's knowledge goals control its inference less directly. If all of IVY's knowledge plans were converted to forward chaining inference rules, they would produce a great deal of irrelevant, but true knowledge.
For example, consider one of the knowledge plans described in the carcinoid/intermediate cell carcinoma example above: nding the visibility conditions under which the distinction can be made. The e ect of this plan is to store the visibility conditions (magni cation, stain, etc.) under which a desired distinction can be made. Storing this information for every distinction that the system can make would lead to the kind of combinatorial explosion described in the introduction. Instead, IVY only investigates the visibility conditions of methods that could have made a distinction that is needed to avoid an error.
4.2 Mechanisms for knowledge goal management Maintaining a collection of explicit knowledge goals introduces new issues into the design of AI programs.
The goals themselves must be organized, applied, and disposed of when no longer useful. These management
tasks were addressed by the following general mechanisms which were required in IVY and AQUA:
Knowledge goal retrieval: nding suspended knowledge goals that a new piece of knowledge might satisfy.
Knowledge goal indexing: storing knowledge goals in memory so that they are found almost only when they are relevant.
Process scheduling: restarting suspended tasks that depend on knowledge goals when the knowledge goals are satis ed.
Hypothesis management: deleting alternative knowledge goals and hypotheses when a knowledge goal is satis ed, because their likelihood of being useful decreases since an alternative has been found.
4.2.1 Indexing knowledge goals Where should a knowledge goal be placed in memory? Since a potential answer to a knowledge goal may arrive at any time, particularly when the knowledge goal may not even be \active," the knowledge goal must be indexed in memory exactly where the answer would be placed when it does come in. This ensures that the knowledge goal will be found without extensive searching through lists of questions. The issue of the amount of inference that should be done at this point was addressed in an earlier section.
Thus knowledge goals are indexed in memory on the basis of their concept speci cations. In AQUA, these knowledge goals are used to generate expectations that guide the parser when the concepts to which they are attached are active.
4.3 Retrieving knowledge goals When a new fact becomes known, either because it is part of the input (e.g., it is read in the story), or because it is inferred for some other reason, the reasoner needs to retrieve knowledge goals in memory that the fact could be relevant to. The knowledge goals retrieved in turn determine how useful that fact is.
AQUA's knowledge goal retrieval strategies take advantage of the fact that knowledge goals are indexed on the basis of their concept speci cations in an inheritance hierarchy. AQUA uses three question retrieval
Type retrieval: When a new memory structure is activated, knowledge goals indexed o the types of the concept are retrieved. The new structure is matched against the concept speci cation of the knowledge goal to see whether it provides the desired information. For example, if AQUA reads about a car, it retrieves questions o the \car" concept to see if the car it read about could answer any of these questions.
Relation retrieval: AQUA uses a frame-based representational scheme in which slots and slot llers specify relations between concepts. For example, the results slot speci es a causal relation of a particular kind between an action and a state. Similarly, the actor slot in an action frame speci es a participatory relation between the action and a volitional-agent. Relations are themselves represented as frames in memory (e.g., see Wilensky, 1986]), allowing AQUA to reason about the relations themselves. Knowledge goals seeking relations between concepts are indexed in the appropriate slots in the frames representing these concepts. This allows AQUA to retrieve knowledge goals that seek relations between memory structures (e.g., the connection between a given terrorist attack and the destruction of some building).
Specialization retrieval: Finally, knowledge goals may be retrieved, given an input cue, by checking whether some specialization or re nement of that input might address a knowledge goal. This allows the understanding process to be sensitive to the questions that the system is currently seeking answers to.
Implementational details may be found in Ram 1989].
5 Knowledge goals as a theory of interestingness One interesting outcome of this work is the formulation of a functional theory of interestingness Ram, 1990c]. The decision to focus attention corresponds closely with the notion of \interestingness." When an understander focuses on a particular fact and processes it in greater detail, it can be said to be \interested" in that fact.2 For this reason, focus of attention heuristics can also be thought of as interestingness heuristics.
These heuristics provide a functional de nition of \interestingness" as a criterion for focussing attention:
2 Since interestingness depends on one's goals, the heuristics presented here do not cover interests that arise from goals that lie outside the scope of the basic understanding and learning tasks that AQUA performs. For example, a parent would be interested in the report card of his child. Since AQUA's goals do not include caring for children, it would not have any reason to be interested in a report card, unless the report card was anomalous with respect to AQUA's beliefs.
Interestingness is a guess at what one thinks one might learn from paying attention to a fact or a question.
The guess must be made without processing the fact or question in detail, because otherwise the purpose of focussing attention to control inferences would be defeated. Thus the interestingness heuristics described below are indeed heuristics rather than precise measures of the value of thinking about a fact or a question.
This is a functional approach to the problem of interestingness Hidi and Baird, 1986; Schank, 1979] from the perspective of our theory of knowledge goals. A similar approach can be used for reasoning systems performing other cognitive tasks, such as planning, since these systems would also need to focus their attention on inferences that were relevant to goals arising from their tasks.
In AQUA, interest in a concept is triggered by its likely relevance to questions or knowledge goals, and continuing interest is determined by its continuing signi cance to these goals. This is related to the \goal satisfaction principle" of Hayes-Roth and Lesser, 1976], which states that more processing should be given to knowledge sources whose responses are most likely to satisfy processing goals, and to the \relevance principle" of Sperber and Wilson, 1986], which states that humans pay attention only to information that seems relevant to them. These principles make sense because cognitive processes are geared to achieving a large cognitive e ect for a small e ort. To achieve this, the understander must focus its attention on what seems to it to be the most relevant information available Sperber and Wilson, 1986]. The Hayes-Roth and Lesser paper pre gures the approach presented here. The additional step suggested here is to mediate the in uence of processing goals on attentional decisions by using explicit characterizations of desirable knowledge. The reason for this is the multiplicity of sources of knowledge goals, and their diverse e ects throughout a learning or inference system. As was made clear in the case of IVY, it is not generally possible to calculate all of the potential impacts on processing goals every time an inference is made. Knowledge goals embody the results of that calculation so that it does not have to be repeated for every new input.
AQUA's knowledge goals are used to evaluate the interestingness of various aspects of the stories being read. They also allow the system to evaluate the interestingness of its questions. Once the interestingness of the input has been determined, AQUA uses it to guide processing by focussing its resources on the more interesting aspects of the story. Since interestingness-determining heuristics are geared towards learning, this ensures that AQUA spends its time on those aspects of the story that are most likely to result in something useful being learned. Without its interestingness heuristics, AQUA would still learn the same things, but it would spend a lot more time drawing inferences that ultimately turn out to be irrelevant. Readers interested in this aspect of question-driven understanding are referred to Ram 1990c] for more details.
6 Knowledge planning: Learning through the satisfaction of knowledge goals Knowledge goals can be used both to control inference, and to direct explicit knowledge actions, based on the metaphor of robot planning for physical goals. The generation and representation of goals to learn is only the beginning of the learning process. The theoretical justi cation for generating them depends on their e ectiveness at constraining combinatorics of learning from complex experience. Our idea is to use AI planning techniques for making decisions about which learning actions should be taken in what order to achieve the knowledge goals of an actor situated in the world. Generally speaking, these decisions are based on knowledge about available resources, knowledge about actions and knowledge about the current state of the world (including the actor's current knowledge state). The actions that people take to acquire knowledge span a tremendous range, from looking up an answer in a reference book to designing and running scienti c experiments. In order for a planner to select actions appropriate to goals, the actions must be annotated with the resources that they require, preconditions to executing the actions and expected outcomes of the actions, and perhaps information about possible alternative outcomes and relative probabilities of the alternatives.
In a system capable of taking a large number of possible actions, hierarchies of action classes can improve the combinatorics of the planning process. Classes of knowledge actions are, in e ect, hypotheses about the component cognitive processes involved in learning. A proposal for a taxonomy of learning actions can be found in Hunter 1990b].
With unlimited resources, planning is trivial. Unfortunately, there are always limits. Physical planners have to manage resources like energy, money and time. Learners are similarly constrained, although the resources are di erent. In particular, learners have limitations on the amount of memory they have and on the amount of time they can spend on inference. Other resources may also come into play (e.g., database access may cost money), or there may be limits on the amount of network tra c a learner can generate in pursuit of information. Planners may have strict limits on resource consumption, or may merely try to avoid waste.
The question of managing resources in learning raises the issue of learning over time. Existing machine learning research has focused on learning from a particular dataset. Conversely, human-like learning occurs over an entire lifetime. Learners need to decide not only whether and what to learn, but when to learn.
IVY and AQUA are able to keep \questions in the back of their mind," in the form of unsatis ed knowledge goals, which are satis ed as opportunities arise.
Learning, then, can be viewed as the incremental revision of previously existing knowledge in response to the successes and failures when using that knowledge to understand novel situations or reason about novel problems. In order to learn e ectively in this manner, the reasoner needs to be able to model the gaps in its own knowledge explicitly. It must know what it needs to know, and why. When there is a di culty or error in processing a novel situation, the reasoner must be able to identify the type of gap that resulted in the problem, and invoke the appropriate learning strategy to learn from the experience. For example, AQUA can (a) use domain knowledge that may not be completely understood to understand novel stories, (b) maintain an explicit model of what it needs to know to complete its understanding of the problem, i.e., of the \gaps" in its knowledge base, (c) learn by lling in these gaps when the information it needs becomes available, and hence (d) gradually evolve a better understanding of the domain Ram, 1990b; Ram, 1992].
Thus the learning process is focussed by the knowledge goals of the system. Reading can be thought of as one type of knowledge action. More sophisticated planners might manage a complex and interacting set of learning goals and available knowledge actions, making decisions about when to pursue a particular goal, based on its relationship to the program's other learning and performance goals and on on the current state of the world. These issues are being explored further in the INVESTIGATOR Hunter, 1990b; Hunter, 1990a] and META-AQUA Cox and Ram, 1991; Ram and Cox, 1992] projects.
7 Comparison to other approaches Other cognitive theories have also included reference to desires for knowledge, although there are signi cant di erences between those prior theories and our theory of knowledge goals.