«Abstract Combinatorial explosion of inferences has always been a central problem in arti cial intelligence. Although the inferences that can be drawn ...»
Once the diagnostic step that failed has been identi ed, the explanation process can identify the faulty knowledge. Each step in the diagnostic process uses both general knowledge and rules speci c to the current hypotheses to accomplish its tasks. General knowledge can be inappropriate, and speci c knowledge can be incorrect, incomplete, or not operational. IVY has a set of explanation rules for each process that use the diagnosis trace to identify the kind of knowledge that caused the problem. For example, if there was no speci c knowledge about (what would have been) the correct hypothesis, the problem was that inappropriate general knowledge was used. Alternatively, if there was speci c knowledge, but it did not apply given the evidence, then the speci c knowledge was incomplete. The failure explanations that IVY produces generally have three parts: the failed process, the kind of knowledge failure, and bindings of speci c pieces of knowledge to variables in the description of the kind of failure. An example explanation can be paraphrased \Distinction failed, entities were confused due to missing speci c knowledge, the entities were carcinoid tumor cells and intermediate carcinoma tumor cells." Implementational details can be found in Hunter 1989].
The second step in IVY's knowledge goal generation process is to turn these explanations into speci c desires. The transformation is generally straightforward. Each general explanation type (i.e., each combination of failed process and type of failed knowledge) has associated with it a knowledge goal skeleton. Continuing the previous example, distinction failures due to missing speci c knowledge have an associated knowledge goal skeleton for nding the missing knowledge. Variables in the skeletons are bound to the bindings from the explanation. In the example case, the goal generated is to nd a method for distinguishing between carcinoid cells and intermediate carcinoma cells.
2.2.2 IVY's use of its knowledge goals IVY's knowledge planner takes as input newly generated knowledge goals. Each goal leads to the generation of one or more plans. A plan speci es information that would be useful in addressing a goal, and what to do when that information becomes available. The required information forms the plan's preconditions and the speci cation of what to do are the plan's actions. When a plan's preconditions are met, the plan is executed, that is, the plan's actions can be taken.
People use a wide variety of plans to achieve their knowledge goals, ranging from looking up an answer in a reference book to designing and running scienti c experiments. IVY's plans identify methods for nding desired information in single cases. After each successful diagnosis, IVY compares the unsatis ed preconditions of all of its pending plans to the contents of the just diagnosed case. If the case can be used to satisfy the preconditions, the plan speci es how to store the case in memory so that the diagnostic failure that motivated the plan is addressed.
IVY's planning abilities were limited to selection among and instantiation of eight di erent plan schemas.
Knowledge goal skeletons had from one to three plan schemas associated with them. INVESTIGATOR Hunter, 1990b; Hunter, 1990a] uses a more exible knowledge planner. Depending on the speci cs of the knowledge goal (i.e., characteristics of the variable bindings in the goal skeletons) one or more of the plan schemata are instantiated. Consider the following example.
One of the plans IVY used to nd speci c distinction knowledge is to \ nd the visibility conditions under which the distinction can be made." Failures in pathologic diagnosis often occur because the tissue sample was not viewed under the correct conditions. For example, the magni cation may be too low (or too high) or the wrong stain may have been used. It is possible to nd out what the appropriate conditions are by looking for a case in which the distinction is made correctly. The preconditions for this plan are therefore a case where (1) both entities appear on the di erential, and (2) a correct diagnosis (of one of the entities) is reached. When such a case is found, a new piece of distinction knowledge can be inferred. The left hand side (condition) of the new distinction rule has two conjuncts: (a) the visibility conditions (magni cation, stain, etc.) in the success case, and (b) the attribute(s) that were used to make the distinction in the correctly diagnosed case. The right hand side (action) is the diagnosis from the success case.
Consider the example of the carcinoid mistaken for an intermediate cell carcinoma, discussed above.
IVY's explanation for its failure was that the diagnoses were confused because of a lack of speci c distinction knowledge. This explanation led to the generation of a goal to nd knowledge that can be used to distinguish between the two diagnoses. The plan described above applies to this goal. In order for the plan to execute, its preconditions must be met: A case must be found where (1) both carcinoid and intermediate cell carcinoma are on the di erential, and (2) the diagnosis reached was either carcinoid or intermediate cell carcinoma and was correct. IVY later encountered a high magni cation image of a carcinoid; in that case, both carcinoid and intermediate cell carcinoma were on the di erential. The correct diagnosis was reached on the basis of general knowledge (dense core granules, a characteristic of carcinoids but not intermediate cell tumors, were present). After the diagnosis was veri ed, the plan's preconditions were tested and satis ed. The plan's action component created a distinction method for carcinoids with the following conditions: (a) the visibility conditions under which the distinction was made (high magni cation, H&E stain), and (b) the di erence between the hypotheses that allowed the distinction to be made (dense core granules).
IVY's knowledge planner was quite simple. A learner situated in a complex world must therefore make decisions about what is worth learning. The results of these decisions are explicit (although not necessarily
conscious) goals about the knowledge a learner desires. Learning does not have to be a passive process:
people generally act in order to learn. Their goals can be used to direct the selection of the actions taken.
IVY ultimately diagnosed 118 descriptions of lung tumors, selected to be broadly representative. A jackknife test was used to evaluate the power of the learning algorithm. The jackknife test works by removing one case from the training set to use as a test. The learning algorithm is run on the remaining cases, and evaluated on the test case. This procedure is repeated so that each case in the corpus is used as a test, and the percentage of test cases diagnosed correctly is compared to the performance of the algorithm without learning. IVY was capable of diagnosing 95 of the 118 cases correctly without learning (about 80%). The goals generated by three of those failures could eventually be satis ed by the program, leading to four additional correct diagnoses (about 84% success).
More important than any measure of percentage improvement in performance due to learning is the quality of the material learned. Two of the three \lessons" that IVY learned in response to its knowledge goals were identi ed by the domain expert, Dr. Yesner, as good teaching cases. One of the images IVY selected had been previously used as an example in one of Dr. Yesner's publications Yesner and Carter, 1982]. Dr. Yesner considered the third case discovered by IVY \quite useful" for showing how to avoid a subtle diagnostic error. The ability of a program to independently identify cases that a domain expert considers interesting, on the basis of the program's experience and its consequent desire for information, bodes well for the potential of knowledge planning in general. The knowledge it gained through learning involves more than tting parameters or chunking knowledge it already had. After learning, the program was able to accurately diagnose di cult cases, and demonstrate the basis for its diagnoses by using several previous cases as precedents. The program found a use for case in the expert's library that the expert hadn't thought of before, which, at the very least, impressed him. We suggest that this kind of learning o ers a qualitatively signi cant improvement over traditional machine learning approaches.
3 A theory of knowledge goals When either AQUA or IVY tries to reason about something, e.g., it is trying to explain something that seems anomalous, and it needs to know something that isn't there in memory, it formulates a knowledge goal that is indexed in memory at the point at which it expected to nd the information. These goals consist of
1. Concept speci cation: the goal object, i.e., the desired information.
2. Task speci cation: what to do with the information once it comes in, which depends on why the goal was generated.
The transformation of a knowledge goal into a plan for achieving the goal is the attempt to operationalize these components.
3.1 Concept speci cation The concept speci cation represents the information that the question is looking for. This is represented using a memory structure that speci es what would be minimally acceptable as an answer to the question.
A new piece of knowledge is an answer to a question if it matches the speci cation completely. The answer could specify more than the question required, of course.
The concept speci cation looks like any other memory structure, except that it is marked with the label hypothesized, hypothesized-in or hypothesized-out, as appropriate.1 When the question is answered, the concept becomes in or out.
The labels in and out are used to represent belief as in most truth maintenance systems Doyle, 1979].
3.2 Task speci cation The task speci cation represents what to do with the answer once it comes in, which depends on why the question was asked. Typically this involves indexing the new knowledge in the appropriate place in a structured memory (i.e., in the organization of the program's knowledge) or forming a generalization based on the answer. The task speci cation may be represented either as a procedure or closure to be run, or as a declarative speci cation of the suspended task. When the question is answered, either because the program actively pursued it, or opportunistically while it was processing something else, the suspended process that depends on that information is restarted.
Both representations are equivalent for the purposes of restarting suspended understanding tasks. However, if the program needs to reason about the purpose of the question, a declarative representation is necessary because it allows the program to access the internals of the task that produced the question. For example, if the program is trying to decide which of two questions is more interesting or important, it might use a heuristic that preferred explanation questions to, say, text-level questions. In this case, a closure would not su ce as a task speci cation.
3.3 The origins of knowledge goals A mechanism for generating knowledge goals must ultimately be judged by the overall utility of the learning that results from those goals. The utility of knowledge learned depends on the goals that the learner is pursuing, the mechanisms that put knowledge to use in pursuing those goals, and the knowledge that the learner already has.
Why would an understander need to nd something out in the rst place? Ultimately, the point of reading is to learn more about the world. Questions arise when reading a story reveals gaps or inconsistencies in the world model. It is useful to focus attention on such questions because they arise from a \need to learn." For example, questions arising from anomalous facts are more useful than those arising from routine stereotypical facts, since in the former case the understander may learn something new about the world.
We suggest three di erent approaches to generating knowledge goals. The rst approach is to estimate the utility of desired knowledge directly. For certain classes of knowledge, those that are broadly useful to a wide variety of typical goals, this calculation may be possible. The second approach is to generate knowledge goals from other goals of the learner. These goals may be subgoals directly related to a performance goal (e.g., desiring to know the combination to a safe), or may be related through more complex inference, like IVY's goals generated via the explanation of a performance failure. The third method for identifying knowledge goals is to analyze the structural characteristics of the background knowledge of a learner. Let us consider each method in turn.
3.3.1 Knowledge goals of high average utility Some kinds of knowledge are so generally useful to a goal pursuer that they are always worth pursuing. These goals may be innate, because the analysis of the expected utility of the knowledge does not change as the goals or knowledge of the learner change. These knowledge goals are also likely to be the evolutionarily most primitive. Other methods for generating knowledge goals presuppose some existing knowledge; generating goals based on the expected utility of desired knowledge need not.
What kinds of knowledge have an expected utility so high that they are generally worth pursuing? A speci c answer to that question depends on at least a general characterization of the needs and environment of the learner that will acquire that knowledge, but there appear to be several classes of knowledge that many organisms appear to treat as worth learning about generally. One example is the learning of spatial maps of the organism's environment.
Exploration is the general term for behavior based on the goals to learn spatial maps. An animal explores in order to build knowledge of its spatial environment. Knowledge gained by exploration has many uses.
One use in particular illustrates the selective advantage of exploration over stimulus-response learning. A creature that avoids predators by running and hiding can acquire a knowledge of good hiding spaces by exploring. A creature that has a stock of hiding places has a clear advantage over one that must nd a novel hiding place every time it is pursued. It may be possible for a stimulus-response learner to associate rewards with good hiding places, thereby achieving the same bene t, but the high cost of the repeated trials necessary to make such an association gives the animal that explores a signi cant advantage.