The Generation of Explanations within Evidential Reasoning Systems

1. Compute for each BOE;:

Here, spt;(A) is interpreted as the sensitivity of the support for A to BOE;, and likewise for plausibility.

2. Identify those BOE; with the extreme values.

The quantities in the preceding equations indicate the change in the support or plausibility relative to a change in the credibility of an evidence source. The partial derivative is evaluated at a ; :0: 1 to assess the sensitivity of the conclusion, which was computed at a; = 1.

In theory these quantities can be computed algebraically or nu­ merically; in practice numeric techniques are required. Returning to the previous example, we find

From this information, it is apparent that BOE1 is strong evi­ dence in support of A and BOE2 weakly detracts from its sup­ port .

In general, the quantities Spt;(A) and Pls;(A) can be com­ pared on the following scale:

It can also be informative to analyze Spt;(A) and .P/S;(A) si­ multaneously by making use of a sensitivity space plot as seen in Figure 4. Plotting Spt;(A) and Pls;(A) on this graph for each i yields a scattergram that can be used to further analyze the results of the sensitivity computation. The farther a point from the origin of sensitivity space, the greater the impact of that BOE upon the conclusion. Entries in the northeast quadrant identify BOEs that support the conclusion, while the southwest quadrant indicates an argument against the conclusion. Points in the northwest signify BOEs that add to the confusion about the hypothesis , while the southeast quadrant identifies BOEs that serve to decrease the ignorance without necessarily arguing for or against.

To this point, we have only given examples of a sensitivity analysis for a single fusion node. The techniques can be extended straightforwardly to apply across the full extent of an analysis graph. For example, the analysis in Figure 3 can be augmented with discounting nodes after each primitive evidence node. When the resulting analysis graph is viewed as a data flow model, the discounting nodes can be seen to act as "valves," where lowering the a-value serves to diminish the flow of information through the valve.

By systematically setting each of the ai's to ( 1 - c), for some small c, and reevaluating the data flow, a discrete approximation to the quantities Spt;(A) and PlS;(A) can be obtained for any proposition in a conclusion node. This information then indicates the relevant import of each primitive evidence. Plotting each point in sensitivity space yields a graphic illustration of the effect each evidence has upon the conclusion.

Returning to the Rufus example, sensitivity analysis shows

From this information, we can conclude that my knowing that Rufus was at home at 8:00 had no bearing on the conclusion that he is probably in Los Altos now, while the remaining three reports were all necessary to the supporting argument. Therefore, only those reports should be included in the explanation:

Why do you believe Spt(Los Altos) · .47?

Because the police reported that Rufus vas seen in San Mateo at 9:00, and my coworker reported seeing a dog that looks like Rufus along Highway 280, and Rufus vas found in Palo Alto once in the ten times he ran away.

Another example uses the negativity of PfsHistory(LosAltos) to answer a question:

Is there any reason to believe that Rufus is not in Los Altos?

Yes.

Rufus vas found in Palo Alto once in the ten tiaes he ran avay.

If the user desires a more complete response than this, we could conceivably conjure an explanation from those compatibility re­ lations that were used along any particular path in the graph. A natural language text that describes what the compatibility re­ lation encodes might suffice (e.g., DELTA-Cities is "the limits on how far a dog can travel in one hour"); otherwise, the iden­ tification of particular links in the relation (perhaps graphically) can help pinpoint a reason.

This analysis only indicates the effect of each primitive ev­ idence individually; the joint effect of multiple evidences is not determined. To compute joint effects numerically, while straight­ forward theoretically, requires exploration of a combinatorically large parameter space. Whether or not such a multivariate sen­ sitivity analysis would be useful for real problems remains to be determined.

B. Entire Body of Evidence

Explanations of a single hypothesis (such as those derived in the preceding section) are quite similar to those produced in systems based on certainty factors or inference nets. The notion of a body of evidence that is used in evidential reasoning permits a higher-level description of an inference chain. Rather than asking a question about a belief in a particular proposition, the user can pose questions that search for the primitive pieces of evidence that were the most influential in general.

There have been numerous proposals for characterizing BOEs [4] that can be used as the basis for selecting informative expla­ nations. While nearly any sound characterization will suffice for our present purposes, we will make use of several due to Yager [16].

We have already noted that the theory of belief functions al­ lows representation of varying degrees of precision as well as un­ certainty. The relative precision of a BOE can be characterized by the following expression for specificity:

where IIAi II is the cardinality of the subset Aj. It is easy to show that

Roughly speaking, S pee( m) measures the degree of commitment of a belief function to precise propositions. The vacuous belief function, m : m(0) = 1, has the smallest possible specificity for any frame 0. A mas~ function whose specificity is 1 ,is a probability distribution as well.

The relative uncertainty of a BOE can be characterized by an entropy-like measure. Yager defines

and shows that Ent(m) is just Shannon's measure of entropy in the special case when m is a probability distribution. To use this measure to generate explanations, it will be more convenient to work instead with a measure o( consonance:

so that

Minimal consonance is thus maximal entropy, and exists when­ ever the focal elements of a mass function are mutually exclusive. Consonance equal to 1 occurs when all the focal elements are nested and thus represents a possibility distribution as defined by fuzzy set theory [17].

To gain some intuition, it is useful to note that any BOE is characterized by a point in the unit square shown in Fig­ ure 5, which spans the space of all possible BOEs. The spe­ cial cases of possibility distributions and probability distribu­ tions lie on the boundaries of the square. A Boolean statement has Cons(m) = Spec(m) = 1. The vacuous belief function has Cons(mo) = 1 and Spec(m0 ) = 0 and is represented by the upper-left corner of the square. Starting with no information and gradually fusing pieces of evidence as they became available, we trace a path in the square that starts at the upper-left corner and wanders toward the right. The ideal analysis would reach a Boolean conclusion (upper-right corner), but typically the path stops somewhere short. The intuition, then, is that pieces of ev­ idence that move the path closer to the upper-right corner are the most sufficient ones for focusing the conclusion.

We are now in a position to select pieces of evidence as justi­ fica:tion of an evidential-reasoning·inference chain. As before, we will perform a sensitivity analysis to choose the components of the explanation, but this time we will measure the change in our two characterizations of a BOE. We define

as the sensitivity of specificity and consonance respectively, where a; is the credibility of BOE; as before. Once again, these mea­ sures can be computed for each primitive evidence and plotted in sensitivity space for comparison (see Figure 6). In this graph, the northeast quadrant represents those BOEs whose inclusion in an analysis forces the path to the upper-right (the Boolean case) and are therefore important to the conclusion reached. The southwest quadrant contains BOEs whose inclusion decreases both the con­ sonance and specificity-these are pieces of evidence that run counter to the consensus, and may be suggestive of an errorful source or a need to maintain multiple analysis paths. The other quadrants can be interpreted as labeled. Once again, distance from the origin indicates the relative contribution of evidence to the conclusion.

Sensitivity analysis for the BOE that represents the conclusion from the lost-dog story reveals

The sensitivities of support indicate that the fact that Rufus was at home at 8:00 did not contribute to the conclusion, and that my coworker's report was the most important piece of evidence (albeit by a slim margin). On the consonance side, all the reports were in agreement except for the historical information; this per­ mitted a small amount of belief to be attributed to PaloA/to, a proposition not supported by the consensus.

C. Using Sensitivity Results to Generate Explanations

With these tools in hand, a number of different questions about an analysis can be answered:

Q: Why do you strongly believe A?

A: Choose the BOE; for which Spt;(A) is greatest.

Q: Why don't you believe B?

A: Choose the BOE; for which PzS;(B) is most negative.

Q: Which pieces of evidence serve to focus the conclusion more precisely?

• A: Choose those BOEs for which Spec;(m) and C~s;(m) are both positive.
• Q: Which piece of evidence most strongly disagrees vith the consensus?

A: Choose the BOE; for which C~s;(m) is most negative.

Q: Which opinions can be safely ignored?

A: Choose those BOEs for which Spec;(m) ~ C~s;(m) ~ 0.

• Q: What are the most crucial pieces of evidence that impinge upon this conclusion?

In summary, the three requirements of explanation generation from Section II have been satisfied:

1. The difficulty of recapitulating program actions within sys­ tems that use a numeric measure of uncertainty has been overcome by the use of sensitivity analysis. Focusing on the credibility of bodies of evidence instead of individual proba­ bilities makes this feasible for belief functions.
2. The correct level of detail can be controlled in two ways . First, the depth of exploration of an analysis graph is se­ lected exactly as for proof trees, but with a natural cor­ respondence between arcs and meaningful inference steps. Second, the number of justifications to be provided is ad­ justed by rank ordering the sensitivities and choosing the most important ones.
3. A shared vocabulary is also provided in two forms. As with the other technologies, natural language text is associated

with a primitive evidence node and displayed in place of the machine representation. Second, the vocabulary is in terms of the high-level constructs of a set of related beliefs represented by a BOE, instead of each proposition and its belief individually. This is likely to correspond more closely to human thought processes.

V DISCUSSION

The use of evidential reasoning provides a richer vocabulary for expressing belief about uncertain events than is available in other technologies, but confounds the ability to construct suit­ able explanations of a chain of inferences. The use of sensitivity analysis as described here not only permits the customary forms of explanation characteristic of rule-based systems, but also en­ ables a variety of additional queries to be posed and answered.

The tools presented in this paper have several uses in addition to that of constructing explanations for a user. Sensitivity in­ formation can be an important component of decision analysis. Knowledge·of the sensitivity of conclusions can suggest whether sufficient information is available, or whether additional informa­ tion should be sought. It can also be used to focus information­ collection efforts. By hypothesizing the information that might be collected by a particular source, one can determine whether it could possibly have sufficient impact on the hypothesis to alter a pending decision. These ideas, while promising, have not as yet been investigated.

We have presented an approach to constructing an answer to various kinds of questions that can be asked about a conclu­ sion derived through evidential reasoning. We have argued that the technique satisfies the three requirements for explanations. It also has the generality to be able to provide a variety of in­ formation about an evidential inference chain and can be used to further insulate the user from the cryptic numbers that are manipulated by the machine. Coupling this mechanism with the evidential-reasoning techniques already developed allows the cre­ ation of a powerful knowledge-based system for reasoning under uncertainty that can explain its behavior in terms understand­ able by humans.

VI ACKNOWLEDGEMENTS

The author wishes to thank the members of SRI's Artificial Intelligence Center who read and critiqued earlier drafts of-this paper. In particular, Tom Garvey provided keen insight on the . calculation and interpretation of the sensitivity measures. In addition to examining the theoretical approach, John Lowrance provided valuable assistance in the implementation of the tech­ niques. Discussions with Steve Lesh were valuable for under­ standing the role sensitivity analysis might play in decision anal­ ysis, and Lenny Wesley illuminated the relationship between this paper and his work on evidential control. Finally, Joani Ichiki is to be commended for the rapid and professional layout and production of this paper.