ME290M Expert Systems in Mechanical Engineering Spring 1999, T-Th 12:30-2:00 pm 1165 Etcheverry Hall, Course Control No. 56369 http://best.me.berkeley.edu/~aagogino/me290m/s99

1 INTRODUCTION

MYCIN RULE NO. 37:

Following this rule, a conclusion about the class of organism present can be drawn (with a certain degree of confidence) from satisfaction of all of the antecedents. In the MYCIN expert system this uncertain degree of belief is represented in certainty factors. Positive certainty factors show support for the hypothesis "H" given the evidence "E1"; negative certainty factors show the degree of support against the hypothesis.

Fig. 1.1: Certainty Factor of Hypothesis "H" Given Evidence "E1"

CF(H, E1) =max(0, CF(E1))• CF(H,E1) [equation 1.1]

The rules for combining evidence were introduced in Chapt. 9. The form below is equivalent to the use of separate factors for measures of belief and disbelief but requires less storage, where x=CF(H,E1) and y = CF(H,E2).

Fig. 1.2: Certainty Combination Function for Two Rules with Evidence E1 and E2 as Antecedents

In addition to explicit rules of inference like those in MYCIN, human beings also have unique skills in holistic reasoning, in the use of intuition, in deciding what parameters or variables are important to a problem, and in knowing what questions to ask when more information is needed. We are able to synthesize the interrelationships of complex problems and gain qualitative insights about them. If a computerized system is expected to capture any of this deeper human knowledge, it should at least be able to represent and process expert knowledge in both a symbolic and numeric fashion. As with the example from MYCIN, the inference mechanism and representation must be able to work with the uncertainties and imprecise data of both the material world and the human mind. The representation and management of uncertainty is a critical issue in the development of expert systems. The approach presented in this chapter is based on the intuitive graphical framework of influence diagrams coupled with the powerful Bayesian inference engine and automation algorithms supporting them.

1.1 Certainty Factors and Conditional Independence Assumptions

Certainty factors have been used as a means to incorporate probabilistic knowledge in rule-based expert systems; the rules being weighted by a belief factor. In the medical diagnostic system MYCIN, the knowledge is stored in rules of the form "If E_i then D_j" where E_i represents evidence that supports disease hypothesis D_j. The certainty factor CF(D_j,E_i) associated with each rule ranges between -1 and 1. Positive certainty factors quantify relative (not absolute) support for the hypothesis and negative numbers quantify the relative support against the hypothesis.

Conditional independence is assumed in the combining rules that give the joint factor when multiple pieces of evidence support one disease hypothesis. Heckerman and Horvitz (1987) have shown that the MYCIN function for combining evidence is analogous to Bayes' formula assuming that each knowledge rule is conditionally independent (assuming a probabilistic interpretation of certainty factors). Thus the benefits of approaches using a simple weighting of rules must be compared against the loss in theoretical rigor and robustness (Cheeseman, 1985). All too often, joint and conditional dependencies are critical aspects of diagnostic reasoning. Probabilistic influences more often than not are highly interdependent .

There is growing support in the artificial intelligence research community for the use of influence diagrams (probabilistic influence diagrams are sometimes called Bayes' networks or belief networks) for representing uncertain knowledge in building expert systems (Heckerman & Horvitz, 1987; Henrion, 1987; Henrion & Cooley, 1987; Holtzman, 1985; Horvitz et al., 1986,88; Pearl, 1986). Influence diagrams provide an intuitive graphical framework for representing complex interdependencies and rules for combining evidence that are based on rigorous probability theory. The IDES (Influence Diagram Based Expert System) developed at the University of California at Berkeley (Agogino & Rege, 1987) is an implementation of influence diagram technology with efficient algorithms designed for real time applications.

1.2 Representing Conditional Independence with Influence Diagrams

Influence diagrams provide an attractive graphical scheme for explicitly codifying conditional independence between critical probabilistic variables as justified by the expert's knowledge and statistical data. The salient information in the diagram is, in fact, not which variables influence each other, but rather, which ones do not influence each other given the conditioning information. Thus influence is defined by its dual concept "lack of influence".

Definition 1: Consider two variables x and y. y does not influence x given C if Pr(x|y,C) = Pr(x|C) where C represents the state of information and other conditioning variables. The reverse implication is also true for all cases except the degenerate case where Pr(y|C) = 0.

In graph-theoretic terms, an influence diagram can be represented as a directed graph G = (V,A) where V is a set of n nodes and A is the set of directed arcs joining these nodes. Given n state variables x₁, x₂, . . . x_n in the problem being modeled, there are n! expansions of the associated joint probability distribution. An influence diagram represents one expansion of the joint distribution which can be manipulated to realize other expansions through application of Bayesian probability theory. An expert may find one expansion more natural than others in codifying and conditioning subjective probabilities. Yet another expansion may be computationally more efficient in solving the diagram in order to answer a specific inference question. In manipulating the diagram during a solution sequence, any intermediate diagram must be "consistent" to the original in the following sense. (Interested readers are referred to Smith (1989) for a rigorous axiomatic development of this concept, using implication.)

Definition 2 : An influence diagram G' = (V',A') is said to be consistent with another influence diagram G = (V,A) if and only if, the set of explicit independencies I_G' associated with G' can be derived from the set I_G associated with G where V' is a subset of V (Rege & Agogino, 1986b,88).

Thus, for diagram G' to remain consistent with diagram G, there should not be any assertion about conditional independence between variables in G' which cannot be concluded from the information in the original diagram G. Consequently, the terms in the expansion represented by the new diagram should be computable from the terms in G. (Note, however, that it is possible for the information on conditional independence in G' to be a proper subset of that in G.)

Figure 1.3: Topologically Consistent World Views: (b) is consistent with (a)

(Rege & Agogino, 1988)

The concept of consistency provides us with an important tool to compare the information on conditional independence asserted by two experts, say 'A' and 'B', who provide different influence diagram models of the same problem domain. Consider the two influence diagrams shown in Fig. 1. The first, Fig. 1a, shows that expert A believes that the variable T influences the variables T₁ and T₂ which are conditionally independent of each other given T. Thus in the view of expert A the information flow, so to speak, is from T to T₁ and T₂. On the other hand expert B views the problem domain as in Fig. 1b implying that he is more comfortable with inferring the probability distribution for T given T₁ and T₂. Further, he asserts that in his view of the world T₁ and T₂ are not independent. If we treat the variables T₁ and T₂ as "observables" (e.g., readings of thermocouples for the same process) and T as a state variable that is not directly observable (the temperature of that process) we notice the cognitive differences in the thought processes of the two experts. Expert A sees the temperature as influencing the observable thermocouple readings T₁ and T₂; in other words, he knows the accuracy of each thermocouple given the process temperature. Expert B, on the other hand, feels more comfortable inferring the process temperature from the two thermocouple readings. In fact, he can make an inference about the reading on one thermocouple given the reading of the other (hence the arc from T₂ to T₁). According to Definition 2, expert B has a view topologically consistent with that of expert A, but his experiential knowledge may differ. Expert A might be a scientist who sees a causal mapping from process temperature to thermocouple readings (causal reasoning). Expert B may be a plant operator who has considerable experience in inferring the true process temperature from thermocouple readings (diagnostic reasoning).

Shachter and Heckerman (1987) note that a "causal" representation is often less complex in that it captures more information concerning conditional independence (as is the case in Fig. 1a), although this may be in the direction opposite of the intended usage. Kahnemann and Tversky (1985) also observe that the probability of consequence given cause (causal reasoning) is psychologically more readily available than the probability of cause given consequence (diagnostic reasoning). However, they caution that their experimental studies indicate that influences perceived as causal may exhibit a confidence bias unjustified by the data. The advantage of modeling with influence diagrams is that the model can be created in the direction that the expert has experienced the world, but can be transformed directly in order to answer a specific query. We go on to argue, that for real time applications, some of these transformations can be performed off-line so as to minimize the computational cost required in actual operation.

1.3 Mathematical Formalism of Influence Diagrams

Influence diagrams were conceived of and developed by researchers in the Decision Analysis Group at SRI International in order to automate the modeling of complex decision problems involving uncertain and incomplete information from a variety of sources (Miller, Merkhofer et al. [1976]). Knowledge of the interrelationships between variables is represented in a compact graphical and numerical framework which identifies the critical variables and explicitly reveals any conditional independence between them. Although the original objective in the development of influence diagrams was for computer-aided modeling, they have been used effectively in improving communication among people. Use of influence diagrams in participative modeling of complex decision problems is described in Owen [1978] and Howard and Matheson [1981]. A direct solution procedure to automate influence diagrams has been developed by Olmsted [1984] and formalized in algorithmic form by Shacter [1984a&b], Rege and Agogino [1986] and Gopalasamy and Agogino [1987]. The application of influence diagrams as a development tool for building expert systems was originally proposed by Agogino [1985] and Holtzman [1985].

An influence diagram is a knowledge representation that can be viewed at three hierarchical levels: (1) topological, (2) functional, and (3) numerical. At the topological level the nodes in the influence diagram represent the important variables in the system being modeled and the directed arcs identify conditional influences between them. From a graph-theoretic framework, the topology of an influence diagram can be described as an acyclic directed network. The nature of the influences between nodes in an influence diagram is specified at the functional level and further quantified at the numerical level. Formal calculi have been developed for deterministic functions and probabilistic relationships (based on either Bayesian or fuzzy probabilities). Only probabilistic influences will be described in this document. Readers are referred to Rege and Agogino [1986] for a formal description of fuzzy influences.

1.3.1 Topological Level

Three different kinds of nodes will be considered in building an influence diagram: 1) circular state nodes, 2) rectangular decision or control nodes and 3) diamond-shaped value nodes. Addition or deletion of nodes is analogous to similar operations on rules in rule-based expert systems but the effect of the same is much more apparent and intuitive with influence diagrams.

Consider the following two-state variable influence diagram shown in Figure 1.4. The circular nodes represent two state variables, x and y, and the arc can be considered informally to signify that a conditional influence may exist. On the topological level, one interpretation of the influence diagram in Figure 1 is : "x may influence y". A variable x is said to influence a state variable y if given information about x tells you something about y. However, this should not be interpreted to mean that x causes y. No sense of causality is implied.

Figure 1.4: x Influences y

Conversely, if knowing x gives you no new information about state variable y, then variables x and y are said to be independent and no influence exists between them. This strong information about the interrelationship (or rather lack of) between variables x and y is signified by the absence of an arc between the corresponding nodes as illustrated in the influence diagram in Figure 1.5.

Figure 1.5: x is Independent of y

It should be noted that the lack of an arc is in some ways a stronger statement of our knowledge than the existence of an arc. The presence of an arc indicates that a possible dependency exists, while the lack of an arc states that no dependency exists. In other words, an arc can be thought of as representing our state of ignorance rather than our state of knowledge.

Decision Variables and Interpretation of Arcs

In addition to state variables, influence diagrams represent decision or control variables by rectangular nodes, following the same symbolism used in decision trees. The nature of an influence arc going into a state node and that going into a control node is conceptually and mathematically distinct. Arcs leading into state nodes represent conditional influences as discussed in the previous two paragraphs. Three examples of influence arcs into state nodes are shown in Figures 1.6ab&d. The influence can be deterministic, probabilistic or fuzzy. Arcs between state nodes can be reversed though legal topological transformations on the diagram according to Bayes' rule and providing a cycle is not introduced. Arcs going into decision or control nodes (Figure 1.6c&e) serve a different function and represent informational influences and show exactly which variables will be known by the decision maker or controller at the time that the decision is made. An arc from a decision node to a chance node indicates causality in the sense that the selection of one decision option over the other choices restricts, in general, the space or the universe of values the state variable can take on. Thus the meaning of an arc must be viewed relative to the types of nodes it connects.

Control nodes are the only nodes where the directions of the arcs are immutable aspects of the structure of an influence diagram and should not be reversed unless the intent is to reformulate the problem. Although not always shown explicitly, it is assumed that once a decision has been made, that decision is not forgotten. Hence the term no-forgetting arcs is used to signify the invisible but implicit arcs between decision nodes which must always appear sequentially in time (Figure 1.6e).

Figure 1.6: Six Interpretations of Arcs

The diamond-shaped goal-value value node is used to signify the objective-goal of the decision maker or computer system user. There can be at most only one value-goal node in an influence diagram. For decision problems, the value node may be the cost (or profit) function of which the user hopes to minimize (or maximize). For an inference problem, the goal node is the object of a probabilistic query. However, as will be applied in the diagnostic and probabilistic inference examples, the location of the value node will vary depending on the question being asked of the expert system. Arcs into the single goal-value node signify which nodes (state or decision) directly influence the goal (Figure 1.6f).

In a more rigorous sense, but still at the relational or topological level, the influence diagram can be defined as an acyclic directed graph consisting of N variables represented by N nodes and a set of directed arcs between them. This topological information may be captured in a structural matrix that relates direct predecessors to each node in the diagram. A node "j" is called a direct predecessor of node "i" if and only if (iff) there is an influence arc directed from node "j" into node "i".

The NxN structural matrix A for an influence diagram of N nodes (each representing a distinct state or control variable) is a Boolean matrix of elements a_ij defined as follows:

A node "j" is called a direct successor of node "i" iff there is an influence arc directed from node "i" into node "j". The transpose of the structural matrix, A^T, represents the Boolean matrix of direct successors in an influence diagram.

A directed path from node "i" to node "j" is the set of arcs connected head to tail that form a pathway between the nodes with the tail emanating from node "i" and head pointed to "j". A node "i" is a predecessor of node "j" if there is a directed path leading from node "i" to "j" . A node "i" is an indirect predecessor of node "j" if: (1) node "i" is a predecessor of "j" and (2) node "i" is not a direct predecessor of "j". Analogous definitions are given for successors and indirect successors. A node x_i is a multi-path predecessor of node x_j iff there exist more than one directed path from x_i and x_j.

The following terminology will be used to apply these concepts in this document. An influence diagram is defined as G=(V,A) where V is the set of N nodes and A the set of arcs joining these nodes:

	Pr(y|x,H)=Pr(y|H)	[equation 1.6]
or equivalently,
	Pr(x|y,H)=Pr(x|H)	[equation 1.7]

4 SOLVING INFLUENCE DIAGRAMS

The "solution" of an influence diagram involves either 1) probabilistic inference or 2) decision making under uncertainty. In either case there must be some question to be answered as represented by the diamond-shaped value node.

4.1 Probabilistic Inference

4.2 Decision Analysis

The transformations or operations involved in decision analysis are the same as that for probabilistic inference; that is arc reversals and barren node removal. However the difference is that here instead of determining a probability distribution, we are computing the expected value (or utility) of a sequence of decisions, comparing them and assessing the optimal sequence by maximizing the expected value of the utility function represented by the value node. The topological or symbolic solution procedure is equivalent to ordering the nodes in the correct sequence(s) of integration of state nodes or optimization over decision nodes. As pointed out by Shacter [1984a:14] the steps involved at the numerical level are those used in evaluating a stochastic dynamic program (Bellman [1957]).

Note that the order so determined would correspond to one of the orderings that might be used in a decision tree based technique in which the variables in an expanded decision tree are either integrated or optimized over. The principle of dynamic programming allows pruning of suboptimal branches in this implicit decision tree. However, the influence diagram algorithm allows solution without the need of an intermediate tree representation. All intermediate calculations are performed directly from the influence diagram knowledge base and thus retain their original meaning.

4.3 Node Removal Concept

An equivalent way of looking at the above procedure is to consider node removal as a topological transformation that corresponds to manipulations of probabilistic functions. Nodes are removed in the order of integration/optimization described above. Rules can be formulated that allow one to develop a topological solution to the problem, without explicitly performing functional or numerical evaluations. If the topological transformations are to be useful, these rules need to have a basis in the probabilistic analysis of the problem. The rules described below were first proposed by Olmsted [1984] and then formalized in algorithmic form by Shacter [1984a:15-20].

Given an acyclic influence diagram the optimal sequence of decisions can be found by ordering or removing nodes from the diagram according to the following rules:

Therefore, combining these rules with appropriate arc reversals, the topological solution procedure can be determined. The justification of the rules can be found in the literature on decision making under uncertainty (see Raiffa [1970] or Bunn [1984]).

5 COMPUTER ASSEMBLY DIAGNOSTICS TUTORIAL

As an illustration of the use of influence diagrams, we present the Diagnostician's Inference Problem in the context of the automated assembly of microcomputers. In order to simplify the presentation, we will assume that during the final testing of a microcomputer, a system failure can be traced to failures in either of two components:

Let us further assume that a sensor is available that gives rudimentary information about the operating status of the assembled microcomputer and is a function of the operating status of the logic board and the I/O board. The associated influence diagram is shown in Figure 5.1. This represents the Diagnostician's Problem on the topological level.

Figure 5.1: Probabilistic Influence Diagram

In the present structure of the influence diagram, the joint probability can be obtained from the conditional probability of the system status "S" and the marginal distributions on the state of the logic board "L"and the 1/0 Board "1/0" as given in the expansion below.

Pr(S, L, I/O) = Pr(S|L, I/O) • Pr(L) • Pr(I/O) [equation 5.1]

Note that L and I/O are conditionally independent (there is no arc between them) and thus their joint probability distribution is the product of each marginal distribution.

The nature of the influences is specified at the functional level. The influence diagram in Figure 5.1 implies that the conditional distribution on S is known along with the marginal distributions on L and I/O. Let us assume for illustration that the test for system status gives a deterministic result based on the status of the I/O and logic boards: if any of these boards (or both) is in a failure state the system status will show a failed system state. Using a subscript o f "0" for a failed state and "1" for the operational state, this implies on the numerical level that the conditional distribution of the system status, S is:

Using the expansion in equation [5.1] the joint probability distribution associated with influence diagram 5.1 is

Note that the joint distribution in [5.5] can always be derived from the conditional and marginal distributions designated in the influence diagram and expressed numerically in equations [5.2-5.4]. Thus the joint distribution need not be stored but can be derived when necessary.

5.1 Probabilistic Reasoning

The diagram in Figure 5.1 represents the diagnostician's knowledge of the problem and system interrelationships. In diagnostic reasoning, however, we are more apt to want to know the cause of the failure given information about the system status. One question that might be asked is: What is likelihood that the logic board has failed given a system failure has occurred? In this case, the evidence E = S = S₀ the event that there is a system failure. The joint probability distribution on L and I/O given the evidence can be obtained mathematically by use of conditional probability:

where W_I/O is the sample space for the possible states of the I/O board.

This is an example of probabilistic reasoning. On the topological level of the associated influence diagram, equation [5.6] corresponds to a sequence of arc reversals leading to the influence diagrams shown in Figure 5.2a. The logic board node, L, is overlayed with a diamond to signify that this is the goal of our probabilistic reasoning. If the evidence E is known with certainty the probabilistic node "S" is now deterministic and updated with the new information on the system status. Because S is no longer probabilistic, we are only interested in events that are conditioned on this new information, i.e., we want to reverse all arcs leading into S. In Figure 5.2a the arc between L and S is reversed and node L inherits all of the direct predecessors of S, which in this case is the I/O node. Next the arc between I/O and S is reversed in Figure 5.2b without the addition of any new arcs. Finally the I/O node is absorbed in Figure 5.2c by summing over the states of the I/O board according to Rule 1 for state node removal.

Figure 5.2: Solve for Pr(L|E)

In numerical terms, the topological transformation shown in Figure 5.2a can be considered a combination of two steps as shown in Figure 5.3b&c:

Figure 5.3: Temporary Aggregation in Arc Reversal

At the numerical level, the aggregation step corresponds to the following expansion using equations [5.2] and [5.3]:

The deaggregation step involves conditioning this joint distribution on the conditional distribution on S.