Reconstructive Explanation: Explanation as Complex Problem Solving

1 Introduction

A computer is generally poor at explaining its problem solving to a human user. Early work on expert systems suggested an explicit knowledge base of expert-defined, problem-solving rules might be used to help such a pro­ gram explain its reasoning. During the past decade, re­ search has been conducted on ways of using this knowl­ edge base to explain the expert system's actions and conclusions. Although significant advances have been made, explanations still suffer from several important flaws. The underlying premise of previous work is that the basis of the explanation is the trace of the expert sys­ tem's line of reasoning. We believe another approach is possible that, for certain audiences, will overcome many of the problems evident in earlier explanations. A human expert, when asked to account for complex reasoning, rarely does so exclusively in terms of the actual process used to solve the problem [Ericsson and Simon, 1984]. Instead, an expert tends to reconstruct a "story" that accounts for the problem solving. This story reflects the expert's line of explanation [Paris et al., 1988] that is not

*Present Address: Computer Science Department, Wash­ ington State University, Pullman, Washington 99164-1210.

This research is sponsored in part by the National Science Foundation, grant number IRI-8715623.

William B. Thompson

Computer Science Department University of Minnesota Minneapolis, MN 55455

necessarily the same as the original line of reasoning. For example, consider the following line of reasoning taken by an inspector attempting to find the cause of the ex­ cessive load on a concrete dam (based on [Franck, 1987]).

... the debris on top of the dam suggests a recent flood. The water markings on the abutments do too. I suspect the flood is the cause of the exces­ sive load. No, the duration of the flood wasn't long enough. Sometimes settlement has these same features. Perhaps settlement is involved. That would account for the high uplift pressures suggested by the slow drainage over time. But the damage to the drainage pipes isn't right . It must be erosion causing the dam to drop more at the toe. Yes, erosion is causing the excessive load ...

Note that the inspector is using a heuristic, data-driven problem-solving process. Later, the field inspector is asked to explain the reasoning that led to the conclu­ sion .

. .. the symptoms led me to believe the problem is internal erosion of soil from under the dam. See, erosion would cause the selectively broken pipes under the dam, therefore slowing drainage and causing high uplift pressures that cause the dam to slide downstream ...

Notice how the line of explanation is different from the line of reasoning. During problem solving, the line of reasoning is directed to settlement through a heuristic association with flood, and then on to erosion. However, the line of explanation moves to erosion directly. The line of explanation is not simply a version of the line of reasoning pruned for dead-ends. The heuristic associa­ tion between flood and settlement that eventually led to the conclusion erosion has been replaced by relationships that bond the symptoms directly to erosion.

Data introduction is another interesting feature of this explanation. During explanation, evidence not used dur­ ing problem solving is introduced as additional support. This includes not only the underlying causality of many of the items, but also the introduction of new symptoms that further support the final conclusion (i.e. the move­ ment of the dam). This type of data introduction is common in domains marked by nonexhaustive problem solving. In such domains, an expert will use a small set of cues from the data to reach a conclusion. Once this conclusion has been made, the expert will support it with additional data items. In some explanations, the initial data cues are replaced with new more directly support­ ing data. In our example, the triggering data (i.e. the duration of the flood) is dropped as it is not needed to directly support the conclusion.

As illustrated by this example, the line of explanation and the line of reasoning are often considerably differ­ ent in both form and content. In contrast to previous work, our research aims at creating the explanation as a product of a problem-solving activity largely distinct from the expert system's problem-solving process. This breaks the tight bond between explanation and problem solving. With this bond broken, the explanation system has freedom to reconstruct the explanation to create a more direct account of the expert system's conclusion.

2 Previous Work

Mycin [Shortliffe, 1976] was one of the first systems to explain its actions. Mycin provided two basic explana­ tion queries: why and how. These two queries form the foundation of nearly all explanation facilities to date.

Swartout [Swartout, 1983] introduced a system, called XPLAIN, explicitly designed to attack the problem of ex­ planation. Swartout used domain principles and domain rationales to record the designer's rule justifications by using an automatic programmer to build the expert sys­ tem. The XPLAIN system produced excellent explana­ tions. However, the information presented appears to be best suited for a knowledge engineer.

Clancey [Hasling et al., 1984] has built an expla­ nation system that augments the facility provided by Mycin. Clancey's system, NEOMYCIN, shifts the focus from the domain knowledge to the strategic problem­ solving knowledge. NEOMYCIN is capable of generating why and how explanations about the strategy used to solve the problem.

Many previous systems, for example X PLAIN, do not present a strict one-to-one mapping of the problem­ solving steps but allow some of the steps to be omitted based on the type of user (i.e. knowledge engineer or domain expert) . Other systems, such as that by Wal­ lis and Shortliffe [Wallis and Shortliffe, 1982], include measures of "complexity" and "importance" for pruning steps from the trace. However, none of these systems includes the ability to completely reconstruct the expla­ nation or to introduce new data not originally used by the expert system.

Tanner [Tanner and Josephson, 1988] has developed on a system to construct justifications that are designed, not necessarily to follow the problem-solving process, but instead to explicitly connect with the user's understand­ ing of the problem. Paris [Paris, 1987] has found that explanations not only vary in abstraction level according to the user, but they also vary in content and emphasis. This work strongly suggests that an expert system must be able to change the content of the explanation, if it is to be practical for varying users. Moore [Moore and Swartout, 1988] is also working on changing the content of an explanation based on the user. Her work centers on the use of rhetorical techniques to plan an explanation of the execution trace to produce a context for follow-up questions.

Our research differs from related work in several ways. Most significantly, our research aims at using knowl­ edge other than the execution trace as the basis for the explanation. Previous work concentrated on methods for translating, presenting, or augmenting the execution trace. Our work focuses on replacing the trace with an equally valid line of explanation.

3 Different Kinds of Explanation

The nature of an effective explanation depends heavily on the user. Knowledge engineers and others involved in the design and maintenance of an expert system re­ quire an explanation facility that elaborates on precisely what the system did to accomplish a specific result. This reflects the common thought that "justification must re­ main true to the expert system". However, an expla­ nation for an end-user is intended to increase the user's confidence in the system and to aid the user in under­ standing the consequences of the system's conclusion. A system designer clearly needs a traced-based explanation that accurately reflects the line of reasoning used in the expert system. This line of reasoning may be inappro­ priate, however, for an end-user. A line of reasoning of­ ten proceeds to a conclusion via an obscure and indirect path. For instance, as illustrated in section 1, many com­ plex domains involve heuristic reasoning [Clancey, 1985]. An effective explanation of the conclusion erosion, al­ though arrived at from a heuristic association with flood, may not only require a substantial reorganization of the line of reasoning, but may require the use of additional supporting information not part of the original reasoning process. Generating such an explanation is possible only within a reconstructive explanation 1 paradigm in which the explanation is reconstructed by an active, problem­ solving process.

There are obvious costs associated with the adoption of a reconstructive explanation strategy. However, these costs may not be as great as might at first be supposed. A clearer separation between problem solving and expla­ nation reduces the need to trade problem-solving com­ petence for comprehensibility that often arises with con­ ventional explanation systems. Another possible prob­ lem with reconstructive explanation is the potential in­ consistency between problem solving and explanation. However, better separation of problem solving and ex­ planation might improve consistency. A recent study has shown that non-experts are not likely to catch reason­ ing errors when presented with trace-based explanations [Erdman, 1983]. This may be because a non-expert, such as an end-user, often will not catch reasoning errors in a difficult to understand line of reasoning. Reconstructive explanation can aid the end-user in a better understand­ ing of the problem and thus provide a basis for the user independently evaluating a system's actions. Overall, quality end-user explanation is not free and the design­ ers of an expert system must determine if they require extensive end-user explanations.

1 It should be noted that this use of "reconstructive expla­ nation" differs from an earlier use [Paris et al., 1988]. The current use is more restrictive than the former, corresponding to what was previously called "plausible explanation."

4 Intuitive Support for Reconstructive Explanation

As reconstructive explanation is significantly different from previous explanation paradigms, we present some intuitive support for its use. Research in psychology has discovered that, in certain situations, recall is re­ constructive [Dawes, 1964]. That is, during recall of an event, details are filled in that are not available from the memory of that particular event. This same notion of reconstruction has be shown to carry over to complex problem solving [Ericsson and Simon, 1984]. In expert problem solving, many of the details of how and why things happened are not available from a memory of the problem solving [Anderson, 1982]. When asked to report this information, the expert will reconstruct an explana­ tion that integrates the elements of a partial memory trace with the memory of other related entities (for ex­ ample, textbook information). We believe this freedom to reconstruct an explanation based on information in addition to the information and processes used during problem solving is in part responsible for the high qual­ ity of human explanations. Reconstructive expert sys­ tem explanation is the study of how to give an expert system this reconstructive ability.

5 The Rex System

REX (Reconstructive EXplainer) is a test-bed system ca­ pable of producing reconstructive explanations for ex­ pert systems. REX is designed to answer retrospective queries in an attempt to obtain the end-user's ratifi­ cation of the expert system's conclusion. Such retro­ spective queries have been shown to be a useful con­ text for reconstructive explanation techniques [Ericsson and Simon, 1984]. REX provides an explanation of the movement within the competitor set of conclusions, thus showing how the final conclusion was reached.

5.1 A Model of Reconstructive Explanation

The REX system is built on a model of reconstructive explanation that maps the execution of the expert sys­ tem onto a textbook representation of the domain. Here, a textbook representation is simply a representation of the information presented in human explanations, much of which comes from domain textbooks. The process of explanation then becomes the process of mapping over key elements from the execution trace and expand­ ing on them using the more structured textbook knowl­ edge. This should not be confused with "decompiling" the rules used by the expert system. Decompiling re­ sults in an explanation of the relationship between the antecedent and consequent of a rule. Reconstruction re­ sults in textbook knowledge that accounts for the data uncovered by the expert system.

The execution trace is passed from the expert system to REX where it is mapped into a high-level specification of expertise that represents the knowledge required for this problem-solving task. The specification points to structures in the textbook knowledge base that rep­ resent methods and relationships involved in performing each particular problem-solving task. A search is con­ ducted within the textbook knowledge base to find the information necessary to answer the end-user's query.

In the traditional approach to explanation the execu­ tion trace is mapped directly to the explanation text. Sometimes pruning is done to remove unnecessary infor­ mation and auxiliary knowledge (called support knowl­ edge) is added. However, the line of the explanation is based exclusively on the trace or line of reasoning. In our reconstructive explanation approach the execu­ tion trace is mapped through a high-level specification to the textbook knowledge of the domain. As the trace is mapped through the specification, information on the processes and reasons used by the expert system (the "how" knowledge) is filtered out. This leaves only in­ formation on the data used during problem solving (the "what" knowledge). Using this "what" knowledge as an index, textbook methods and relations are found that represent well-organized "how" knowledge. This text­ book information, as opposed to the more obscure infor­ mation found in the trace, forms the content and orga­ nizational structure of the explanation text .

An obvious question arises. Why go through all the extra work of mapping the trace into the textbook knowl­ edge? Why not simply use the "textbook justifications" attached to the rules in the trace? The answer rests in the realization that explanation is a complex problem­ solving task in its own right, requiring at a minimum a significant reorganization of the knowledge used for prob­ lem solving. For example, in medical school, knowledge is presented and explained as symptoms given disease. In the real world, problems are solved as disease given symptoms. However, conclusions are still explained as symptoms given disease as the explanation is then eas­ ier to understand and follow. Likewise, when an expert is asked to explain complex problem-solving methods, what can be given is the textbook method of solving the problem, instantiated for the specific case at hand. This method explains the process for the same reason that it was used to teach the process, it is easier to understand than the more obscure and ad hoc method used during real problem solving.

This raises yet another question. If the textbook methods are so easy to explain, why not use them di­ rectly to solve the problem? The answer rests in the real­ ization that real-world problem solving is also a complex task. Experts often proceed from symptoms to conclu­ sions through long diverted paths. It is rarely possible to identify what method of solving the problem is appropri­ ate from the beginning. It is much easier to reconstruct an appropriate method once the answer is known. Thus, explanation and problem solving are two largely distinct tasks, each requiring its own methods and knowledge.

5.2 Specification of Expertise

Before describing how REX reconstructs an explanation, it is first necessary to briefly describe the representation used for the high-level specification. The specifica­ tion represents what knowledge is required to solve the problem. In particular, this representation of expertise takes the form of a graph of hypotheses, each connect to other hypotheses by one or more "transitions" [Johnson et a/., 1987]. Associated with each transition are two sets. A set (called the condition set) of cues defines the data that must be found for the transition to be valid. In other words, this set represents information from the problem solving that can lead to a movement between the two hypotheses. Secondly, another set (called the goal set) defines the goals that must be posted in mov­ ing between the two hypotheses. These two sets combine to define what knowledge (cues and goals) is required to move between two hypotheses in the knowledge specifi­ cation.

At first, this representation may sound like a repre­ sentation of how to solve the problem. However, the representation is neither procedural or deterministic. In other words, each transition tells what information is re­ quired to move between two hypotheses, but does not enforce how that information will be used. For example, the condition and goal elements of a transition are super­ sets of the cues and goals needed to make the transition. Different subset(s) of cues and goals can be used to move between the two hypotheses. The following section will illustrate the use of such a specification for reconstruct­ ing explanations.

5.3 Reconstruction of How from What

To illustrate the process of explanation, consider the line of reasoning given in section 1. In that example, the do­ main expert was trying to identify the cause of the ex­ cessive load on a concrete dam. In the explanation, the expert was attempting to answer how that cause was determined. The expert's problem-solving leaves a trace of data corresponding to symptoms and inferences. The trace for this example contains: debris on dam, water marks, drainage, uplift pressure, and broken pipes. In REX, the data in this trace are used to "activate" the same data in the high-level specification of the knowl­ edge required to solve the problem. This enables REX to determine what data cues were used by the expert system in moving to the conclusion. The line of reason­ ing illustrated in section 1 follows a path from the ini­ tial empty hypothesis through the hypothesis flood, onto the hypothesis settlement and stopping at the final solu­ tion erosion. However, the line of explanation (as shown in section 1) moves from the initial empty hypothesis directly to erosion, using the data cues uplift pressure, drainage , broken pipes and sliding. REX, when given ac­ cess to the expert system to find additional supporting knowledge that was not activated from the expert sys­ tem's problem-solving trace, reconstructs an explanation that closely resembles this line of explanation. This re­ construction involves three core elements of the REX de­ sign: the textbook knowledge base, the explainer, and the story teller. The following paragraphs will describe how each of these elements helps reconstruct a line of explanation for the concrete dam example.

CUE uplift

Value

Type

Name

Nickname

Valuename true direct the high uplift pressures acting on the dam uplift pressures

*cue*

HYPOTHESIS erosion

Value true

N arne the erosion of soil from under the dam

Nickname erosion

Valuename

*hypothesis*

GOAL det-cause

Name

Nickname determine causal relationships determine causes

CUE SCRIPT erosion-to-sliding

Uses

(<drainage> <uplift> <sliding>)

Supports

<erosion>

Achieves det-cause

Vconstraint

Text

(and <drainage> <uplift> <sliding>)

(<erosion> causes <broken-pipes> causing <drainage> resulting in <uplift> and in turn <sliding>)

GOAL SCRIPT causal

Holds

( <det-cause>)

Text

: (simply <det-cause>)

Figure 1: Sample textbook knowledge representations.

The Textbook Knowledge Base is represented in REX as a collection of relationships between cues, hy­ potheses, and goals as illustrated in Figure 1. The cues, hypotheses, and goals themselves represent the domain objects that other relationships and methods manipu­ late. In REX, each relationship is represented as a c:ue script and each method is represented as a goal script as shown in Figure 1. Each frame and script has text slots for English presentation.

Using the representations illustrated in Figure 1, a transition from one hypothesis to another is possible when a method and relationships are found such that each goal and cue used is a member of the goal and con­ dition sets defined between the two hypotheses in the knowledge specification graph. In REX, the structure built by combining the method and the relationships is called an explanation structure as it serves as an expla­ nation of the movement between the hypotheses.

The Explainer is responsible for constructing the line of explanation that will eventually be presented to the end-user. This line of explanation represents a move­ ment from the initial problem-solving state to the final conclusion reached by the expert system. In REX, this corresponds to finding a path through the knowledge specification from the conclusion of the expert system to the empty hypothesis. Each transition in this path must be supported by the existence of a valid explanation structure. REX uses the A* algorithm to search through a space of knowledge specification transitions for which a valid explanation structure has been found. The search is carried out backwards from the final conclusion of the expert system towards the empty hypothesis. Each state in this search corresponds to an emerging line of expla­ nation that uses certain cues and a hypothesis as data, establishes other cues and a hypothesis as conclusions and traverses certain edges in the specification. Tran­ sitions between states in the A* search correspond to expanding the bottom hypothesis by finding each edge with a valid explanation structure that moves to this hypothesis. As the precise explanation structure chosen will determine the cues included in the explanation, a separate transition in the A* search is constructed for each valid explanation structure on each incoming edge of the bottom hypothesis. A complete line of explana­ tion represents a path from the initial problem state (the empty hypothesis) to the final conclusion reached by the expert system.

The Story Teller takes the path found by the ex­ plainer and formats it for English presentation using the grarnmer of Figure 2, thus creating what is called a story tree. Figure 3 shows the story tree for our example. The REX system output of this story tree is as follows: 2

We have a concrete dam under an excessive load. I attempted to find the cause of the ex­ cessive load. Not knowing the solution and based on the broken pipes in the foundation of the dam, and the downstream sliding of the dam, and the high uplift pressures acting on the dam, and the slow drainage of water from the upstream side of the dam to the downstream side I was able to make an initial hypothesis. To achieve this I used the strategy of striving to simply determine causal relationships. In attempting to determine causes, I found that the internal erosion of soil from under the dam causes broken pipes causing slow drainage re­ sulting in uplift and in turn sliding. This led me to hypothesize that internal erosion was the cause of the excessive load. Feeling confident in this solution, I concluded that the internal ero­ sion of soil from under the dam was the cause of the excessive load.

2 The verbose nature of the English output is a result of our focus on the content and structure of the story tree and not on its presentation.

The expert system, using a reconstructive explanation system, is able to present a line of explanation that leads directly to the solution. Whereas the expert system us­ ing a traditional explanation system would be restricted to a line of explanation moving first to flood, through settlement to erosion. Even when the explanation sys­ tem is not given access to the expert system and thus can not ask for additional supporting data (such as slid­ ing) the reconstructive paradigm can still create a more direct explanation than is possible within the traditional paradigm. REX can find the shortest path of "activated" data from the solution hypothesis to the initial empty condition. In other words, REX can find the most direct path to the solution using only information uncovered by the expert system during problem solving. In our exam­ ple, this path is found by moving from the initial empty set directly to settlement and on to erosion. This line of explanation, although less direct than the previous line of explanation, is still more direct than the path followed by the traditional explanation paradigm as it by-passes the need for the heuristic association with flood.

6 Significance

Reconstructive explanation is a significantly new ap­ proach to the automatic generation of expert system ex­ planations. The feasibility of using the reconstructive explanation paradigm has been shown by the REX sys­ tem.

Such a reconstructive explanation paradigm has sev­ eral advantages that show its desirability: (1) The text­ book methods and relations used to integrate the infor­ mation uncovered during problem solving serve to re­ organize the flow of the explanation to be more direct. (2) Different methods and relations can be used to al­ low the explanations to be tailored to the needs of spe­ cific user types. (3) A reconstructive explanation system can provide independent feedback on the performance of the expert system. For example, if the explanation system can not find an explanation for the conclusion, this could suggest an error in the problem solving of the expert system. ( 4) An expert system with a reconstruc­ tive explanation facility will have the ability to use one approach for problem solving and another for explana­ tion. Thus, the system can be implemented with less concern for the tradeoff between problem-solving ability and end-user explanation. (5) Under certain constraints, a reconstructive explanation has the freedom to present multiple lines of explanation leading to the same con­ clusion. (6) Reconstructive explanation provides more flexibility than conventional explanation systems allow­ ing explanations to be built on information other than a subset of the execution trace.