A Theory of Diagnosis for Incomplete Causal Models

1. INTRODUCTION

In recent years many approaches have been proposed to provide problem solvers with some form of "deep knowledge". Most of the efforts towards the logical for­ malization of diagnostic problem solving have been based on "ontological approaches" [9, 24] while in the machine learning community the use of a "domain theory" has gained popularity [16]. One of the critical problems in both cases concerns the completeness of the domain model. However, while some attempts to deal with incomplete (and imperfect) theories are being made in the learning community [23], the completeness of the model is a common assumption in first principles diagnostic sys­ tems (which have been successfully applied to the solu­ tion of problems such as electronic troubleshooting [8, 13]). This assumption is not adequate for the applica­ tion of ontological approaches to complex problems (such as medical diagnosis or mechanical troubleshooting) [15] since in these cases a complete model is either not avail­ able or intractable. Working at multiple levels of abstrac­ tion can reduce the computational complexity of the rea­ soning process; one cannot assume, however, that the lowest level of description is complete 1 · A further limita­ tion of ontological approaches directly concerns the definition of diagnosis as a set of faulty components to be replaced This definition can be too restrictive since we may want to distinguish between different faults for the same component, and, on the other hand, in many cases a faulty behavior is not due to a small set of responsible faulty components (consider, for example, human "sys­ temic diseases").

The research described in this paper has been partially supported by grants from MPI 40% (Automated Reasoning Techniques for Intelli­ gent Systems) and CNR of Italy.

Since the early 80's, another major family of approaches to diagnosis has been widely adopted, espe­ cially in medical domains: the so called "causal modeling approaches" 2 (after PatH's seminal work [18] and succes­ sive proposals as [11, 26]). Although widely applied to many real world problems, such approaches seem to be less constrained and well-defined than ontological ones; therefore their formal definition has not yet received much attention. Moreover, some form of incompleteness must be accommodated in causal models (as well as in ontolog­ ical ones). Although this need has been recognized [17] and has led some researchers to provide probabilistic foundations to causal diagnostic reasoning [7, 19], a lot of work still has to be done on the logical treatment of incompleteness in causal models.

The aim of this paper is to describe a causal model­ ing formalism which on the one hand accommodates some forms of incompleteness and on the other hand has a precise logical formalization. In particular, the main goals and issues we want to address can be synthesized by the following items:

• introducing a formalism to represent incomplete causal knowledge;
• giving a logical foundation of causal reasoning on incomplete knowledge and introducing precise definitions of the concepts of "diagnostic problem" and of "solution to a diagnostic problem";
• providing a formal treatment of multiplejault diagnosis
• within causal models;
• providing some criteria to select the "best" solution to a

1 "Even the lowest level of explanation in a domain theory may incorporate abstractions [ ... ] Abstractions at the lowest level of a domain theory imply missing knowledge .. " ( [10] page 543).

2 The term "causal" has not been used here to mean that these ap­ proaches are the only ones based on causal knowledge. Many of the on­ tological approaches are in fact based on the representation of causal

formalism: STATE nodes. (elliptic boxes in figure 1), representing partial states of the modeled system; FIND­ ING nodes (rhomboidal boxes), representing observable manifestations of internal states (which cannot be observed); HYPOTIIESIS nodes (hexagonal boxes), representing diagnostic hypotheses; INITIAL CAUSE nodes (double-lined elliptic boxes), representing initial perturbations (i.e. the mechanisms starting the processes which may lead the system to a faulty behavior). In the following we shall assume that INITIAL CAUSEs are not observable (which is the most general and interesting case). This corresponds to a first form of incompleteness in the model: such nodes are abstractions of the actual perturbation processes, and the model gives no direct way to establish their presence. ·

The nodes in a network can be connected by means of different types of arcs (relationships): each CAUSAL arc (continuous lines in figure 1) connects one or a set (conjunction) of STATE and INmAL CAUSE nodes to a STATE node and represents a cause:effect relationship; each HAM arc (dashed lines) connects a STATE node to a FINDING node (HAM - that is Has As a Manifestation - arcs connect states to their external manifestations); each DEFINED_AS arc (double lines) connects a STATE (or a conjunction of STATE nodes) to a HYPOTIIESIS node (to represent that the hypothesis is defined as the presence of the state, therefore hypotheses are defined concepts).

In case of different arcs entering a node N, such arcs are implicitly ORed (see, for example, the CAUSAL arcs entering the STATE "oil_lack" in figure 1). Nodes can have attributes (i.e. variables giving a better characteriza­ tion of the entity represented by the node itself): a func­ tion, describing how the values of the attributes of the caused state (manifestation) depend on those of the caus­ ing ones, is associated with each CAUSAL and HAM arc. Besides the incompleteness associated with INITIAL_ CAUSE nodes, some other form of

problem.

In our logical approach diagnosis is seen as an abductive process starting from the logical correspondent of a causal model. In order to draw conclusions from incomplete models some forms of nonmonotonic reason­ ing are adopted and, as a consequence, the solutions we obtain are defeasible. In particular, instead of using one of the nonmonotonic logics proposed in the literature, we adopt first-order logic supplemented with specific forms of hypothetical and circumscriptive reasoning [2]. This is in the same line of Poole's first-order approach to default reasoning and diagnosis [21, 22].

This paper is organized as follows: in section 2 we outline an abstract formalism to represent causal knowledge; in section 3 we define a formal theory of causal diagnostic problem solving; in section 4 we present an example of diagnosis.

2. A FORMALISM TO REPRESENT DEEP CAUSAL KNOWLEDGE

In this section we shall briefly introduce a formalism to represent causal knowledge and its logical formalization (the causal modeling formalism we shall introduce is a rather general one, although strongly influenced by our past experiences in the design of the CHECK system [3, 27]). Causal networks are a general formalism to represent causal knowledge, i.e. to describe the set of behaviors of a physical {physiological) system. In the fol­ lowing we shall assume, in particular, that causal net­ works are used to model the faulty behavior of a system (which seems to be the most interesting case in diagnostic applications).

Consider the simple example in figure 1. At least four types of nodes have to be used in a causal modeling incompleteness must be accommodated by causal model­ ing formalisms. Causal models of complex physical (phy­ siological) systems may be incomplete at least for the fol­ lowing reasons (see [2, 4] for a discussion):

knowledge (together with other fonns of knowledge).

• Choosing the level of detail of a model is quite arbitrary (or, at least, domain and task dependent). However, in order to constrain the complexity of a model, some bounds have to be imposed to the level of detail at which knowledge is represented [18, 23]. Therefore, processes and conditions at a lower level than the chosen one have to be abstracted.

- There exist (especially in physiological systems) processes and conditions which are not perfectly known.

In order to deal with such forms of incompleteness we have introduced the possibility of labeling each CAUSAL or HAM relationship in the causal model as a MAY one. A MAY label · denotes that the model of the relationship is incomplete, i.e. that some condition or process has been abstracted. A relationship not explicitly labeled as MAY is assumed to be fully specified.

Let us discuss now how a logical semantic can be associated with the formalism introduced in the previous paragraphs. All the entities and relationships in a causal network can be modeled in a logical framework; the main ideas of such a formalization can be summarized as fol­ lows:

• Each STATE, FINDING and INmAL CAUSE can be characterized as an atomic formula. More specifically, different sets of predicate symbols are used for each type of node: "state symbols" for STATE nodes, "man­ ifestation symbols" for FINDING nodes and "initial cause symbols" for INITIAL CAUSE nodes 3 · The arity of a predicate symbol equals-the number of attributes of the node it represents. For example, a STATE S with two attributes is represented by the formula S(x,y) with S e "state symbols".
• CAUSAL and HAM relationships are modeled by implication formulae. Functions are used to express how the values of the attributes of the caused state depend on those of the causing ones. For example:

lubric oil burning(x) --+ stack smoke(f1(x)) is part of the logical model of the network in figure 1. The state "lubric_oil_burning" has the attribute "quan­ tity" and the finding "stack smoke" has the attribute "color"; the function is defined as follows:

f1(low)=grey and f1(high)=black

• MAY relationships are modeled through the introduction of an "abstracted condition symbol" 4 · Each "abstracted condition" . atom models the actual condition (process) abstracted (ignored) in the model. As an example from figure 1, we have:

high_engine_temp(x) A a--+ power_decrease(f2(x))

Since INITIAL CAUSEs and MAY relationships represent two forms of incompleteness that will be dealt with in a similar way, we introduce the following definition:

3 In definitions and in symbolic examples "state symbols" will be denoted by upper case roman letters, "manifestation symbols" by lower case roman letters and "initial cause symbols" by the last letters of the greek alphabet

4 "abstracted condition" symbols will be denoted by the first letters of the greek alphabet

Definition 2.1. The set of assumption symbols is the union of the sets of abstracted condition and initial cause symbols, that is:

{assumption symbols} =

{abs~acted condition symbols} u {initial cause symbols}

A form of "hypothetical reasoning" will be defined in the following sections to deal with such assumptions in the diagnostic reasoning process.

Notice that no logical correspondent is defined for DEFINED_ AS relationships. Such relationships are, in fact, at a different knowledge level than the other ones (hypotheses are defined concepts), so it is not necessary to model them as logical formulae. However, since each diagnostic hypothesis is defined as the presence of a con­ junction of states (i.e. each HYPOTHESIS node is con­ nected to a set of STATE nodes through a DEFINED AS arc), we introduce the following definition: -

Definition 2.2. Given a diagnostic hypothesis H (i.e. a HYPOTHESIS node H), we denote with def(H) the for­ mula

in case a DEFINED _AS arc connects Sh····Sk to H.

In the following, for the sake of brevity, we shall limit ourselves to consider "singly connected" causal networks, i.e. those networks in which, given two nodes N1 and N2, there exists at most one path connecting N1 and N2· A discussion about more general causal networks can be found in [5].

3. DIAGNOSTIC PROBLEMS AND THEIR SOLUTIONS

In this section we introduce the concepts of diagnostic problem and of solution to a diagnostic problem, defining in which way the solutions are affected by the form of hypothetical reasoning that is used to find them.

3.1. Basic Definitions

A causal network represents the general knowledge about some domain. We have a diagnostic problem when we add to this knowledge the set of findings that have been observed in the case under examination.

Definition 3.1. A diagnostic problem (d.p. in the follow­ ing) P is a triple <NET,HYP, '1'>, where:

• NET is the set (conjunction) of logical formulae model­ ing a causal network NETWORK;
• HYP={<H,def(H)> I H is a HYPOTHESIS node in the causal network NETWORK};
• 'I' is a nonempty set of ground manifestation atoms.

Since manifestation predicates represent observable condi­ tions, we assume that the manifestations which have not been declared as observed are absent therefore in the fol­ lowing we use the set:

'I' = { -,m I m is a ground manifestation atom, m fi. 'I'}

This is the first non-monotonic rule we introduce in the diagnostic process in order to draw conclusions from incomplete knowledge: this is a case of (possibly) incom­ plete factual knowledge, i.e. we only have a partial description of the case under examination. In a real application such a rule must be made explicit, even if it does not preclude that data are acquired incrementally by the system's control strategy (that is, the systems asks for further data when necessary). However, in the following the whole diagnostic process is described in a declarative way, abstracting from the definition of a control strategy. It is worth noting that, as an alternative, we can give the possibility to leave some findings as "unknown"; we shall briefly return to this point at the end of this subsection.

The reasoning process involves the concept of hypothetical world, in the (syntactical) sense of a set of formulae including assumptions. Such a world may be regarded as a tentative reconstruction of the causal evolu­ tion that has led to the observed situation. The notion of hypothetical world to be used in solving a diagnostic problem is defined recursively. The basis is the case of a world containing initial causes; the recursive case involves abstracted conditions on causal relationships.

Definition 3.2. Given a d.p. P=<NET,HYP,'¥>, and given a world W, W is a world for P iff

W =NET u {<Jt> ··· , <Jk} where <Ji> for i=l, .. ,k, is a ground initial cause atom (in this case we say that W is an initial world for P)

or W = W' u {a} where

• W' is a world for P;
• X 11 a --+ Y is an instance of a formula in NET, where a is an abstracted condition symbol;
• W' 1-X.

In the latter case of the definition, the world W' u {a} has to be considered in order to examine the conse­ quences of assuming that the condition a is actually true in the case under examination; that is, assuming that the corresponding "MAY" relationship holds in the case under examination.

To test a world against the observed manifestations we introduce the following definitions.

Definition 3.3. Given a d.p. P=<NET,HYP,'¥>, a world W for P is inconsistent iff W 1- m for some ground manifestation atom m such that m fi. '¥.

In other words, W is inconsistent for P iff W u '¥ is inconsistent in the logical sense. This has similarities with consistency-based approaches to nonmonotonic reasoning [25], with the difference that in our diagnostic system, which is not a general-purpose approach to nonmonotonic reasoning, the consistency check can be limited to a small class of formulae.

Definition 3.4. Given a world W and a set '¥ of ground manifestation atoms, W covers '¥ iff \/me'¥, W 1- m .

In order to give a solution to a diagnostic problem P=<NET,HYP,'¥>, a world W for P has to explain the observed findings in '¥ and must not predict the presence of findings that have not been observed; this is summar­ ized by the following definition.

Definition 3.5. Given a d.p. P=<NET,HYP, '¥>, a world W for P is a final world iff W covers '¥ and is not incon­ sistent, that is

'¥ = {m I m ground manifestation atom, W 1-m} .

The definition of solution to a diagnostic problem is given as follows, in terms of diagnostic hypotheses whose definition is satisfied in a final world, i.e. in a world representing a causal evolution that is consistent with the observed situation.

Definition 3.6. Given a dp. P=<NET ,HYP,'¥> and a final world W for P, the set

diagnosis(W) = {HI <H,def(H)>eHYP, W 1- def(H)} is a solution to P. We say that W is a causal explana­ tion of the solution.

It is worth noting that this kind of explanation of a solu­ tion may be very important for the user, for example to remove the fault in the system under examination.

The definitions in this section are sufficient to characterize diagnosis as a nonmonotonic process. Con­ sider, for example, the network in figure 2. In such a case we have that 9 1={H1} is the solution to the problem characterized by '¥1={md and 9 2={H2} is the solution to the problem characterized by '¥2={ml>m2}.

The previous definition·s can be extended to the case of "unknown" findings. In such a case the set of ground manifestation atoms is partitioned into the three classes of "observed", "unknown" and "absent" ones. A world W is inconsistent if and only if an "absent" finding is deduced in W, while final worlds must cover only observed findings and may predict the presence of some unknown finding (more details are given in [5]).

3.2. Confirmation or assumptions and solutions

The form of hypothetical reasoning described in the previ­ ous definitions is the first step to solve the problem of dealing with incomplete knowledge. It is not enough because, in many cases of interest in real-world applica­ tions, there may be more than one final world and then more than one solution to a diagnostic problem, according to the definitions given above. A solution is one of the possible explanations of the given data. The problem is that we have no direct way to establish the bUth of the conditions that have been assumed in order to explain the observed findings: we need some stronger form of abduc­ tive reasoning to give an indirect confirmation to the assumptions, or, at least, to give some preference criteria between the different solutions to a diagnostic problem.

In particular, we introduce a non monotonic criterion for the confirmation of assumptions. The conclusions obtained in this way are strongly dependent on the hypothesis that the causal network contains all the relevant knowledge, that is all the possible causes for a given state and all the states that (may) have a given finding as a manifestation. Therefore, such conclusions are defeasible, as it is typical in nonmonotonic reasoning. The idea is to confirm those assumptions that are neces­ sary to explain the presence of the observed findings.

Definition 3.7. Given a d.p. P, an assumption a is confirmed iff for every final world W for P, a EW.

The extension of the definition to give confirmation to a world and to a solution is straightforward.

Definition 3.8. A final world W for a d.p. P is confirmed iff every assumption a E W is confirmed.

In other words, a final world W is confirmed if its assumption set Assumptions(W) is a subset of the assumption sets of any (other) final world.

Definition 3.9 ·. A solution 9 to a diagnostic problem P is strongly confirmed iff e = diagnosis(W) for some confirmed final world W.

This is the most natural case for the confirmation of a solution: it allows us to confirm the explanation of a solu­ tion, i.e. to confirm an instance of a subnetwork represent­ ing the causal evolution that has led to the observed situa­ tion. There are cases where this cannot be done, but it is still possible to give some kind of "weak" confirmation to a solution, directly confirming diagnostic hypotheses without dealing with the (niore primitive) level of the assumptions.

Definition 3.10. Given a d.p. P=<NET,HYP, '1'>, a diag­ nostic hypothesis H occurring in HYP is confirmed iff HE 9 for every solution 9 to P.

Definition 3.11. A solution 9 to a diagnostic problem P is weakly confirmed iff every HE e is confirmed (and e is not strongly confirmed).

The following property shows that the concept of confirmed solution is well-defined.

Property 1. A diagnostic problem has at most one (either strongly or weakly) confirmed solution.s

3.3. Object level characterization of confirmation

We have seen in the previous section that the confirmation of assumptions is based on the nonmonotonic hypothesis that all relevant knowledge is modeled. If this is the case, when a state (or manifesta­ tion) is present, one of its possible causes must be present This can be formalized using Me Carthy's cir­ cumscription principle [14], giving in such a way an object level characterization of the confirmation criterion. In particular, we use parallel circumscription in ordered formulae which has been proven equivalent to a first-order formula ([12], theorem 6.11, p.148). Notice that in our case the same results can be obtained using predicate completion [1].

~ The proof of this property and of the following ones can be found in [5].

Considering the topological order defined in a singly connected causal network, it is easy to prove that the log­ ical model of such a causal network is an ordered formula with respect to the set of state and manifestation predi­ cates.

We give, therefore, an alternative definition for the confirmation of assumptions using the parallel cir­ cumscription of the set of state and manifestation predi­ cates in the formula NET - that is, the (first-order) for­ mula NETcirc defined as follows, (where STATE and FINDING are the classes of state and manifestation sym­ bols of the alphabet):

This formula gives a formalization to the intuition described above and can be used to give the following definition.

Definition 3.12. Given a d.p. P=<NET,HYP,'I'>, an assumption a is circumscription-confirmed iff

The two different criteria can be proven to be equivalent.

Theorem 2. Given a d.p. P=<NET,HYP, '1'>, an assump­ tion a is confirmed iff it is circumscription-confirmed.

The importance of this result sterns from the different nature of definitions 3.7 and 3.12. The latter is an object level characterization, while the former is a meta level one and can be easily implemented, since we are generally interested in finding all the final worlds for a problem (or at least the non redundant ones - see next section). The object-level approach can be generalized to characterize the entire set of solutions to a diagnostic problem [6].

3.4. Parsimonious solutions

The confirmation criteria defined in the previous section may sort out one of the solutions to a diagnostic problem; when there is no confirmed solution, we may still be interested in ranking the solutions, trying to find the "best" one or at least a selected subset of equally good or incomparable ones.

This problem has been analyzed by some researchers over the last few years. In the "Parsimonious Covering Theory" [20] the notions of minimality and minimum car­ dinality have been used to define some parsimony criteria. Similarly de Kleer [9] and Reiter [24] proposed parsimony criteria based on minimality considerations 6 ·

The basic justification supporting the "minimal cardi­ nality" parsimony criterion is the assumption that faults are independent Such an assumption can be questioned in many real world domains. In many cases, in fact, two faults (diseases or diagnostic hypotheses) can be causally correlated (e.g. "burnout" and "melting" in figure l). On the other hand, the "minimality" (irredundancy) parsi­ mony criterion seems to be much more widely applicable since it does not require any a-priori assumption on the nature of the diagnostic hypotheses being considered. Of course this criterion is weaker, since it is based on a par­ tial order, where we may have different (and incompar­ able) minimal elements (while in the other case two different solutions of minimum cardinality can be con­ sidered equally good).

In our case the two criteria can be applied to the solutions as sets of diagnostic hypotheses, and, more interestingly, to the set of assumptions that characterize the final worlds or, equivalently, to the final worlds them­ selves. We have already remarked that assumptions are a more primitive notion; moreover, if a solution has more than one explanation, we can select the best one by con­ sidering their assumption set.

Definition 4.1. A solution 9 to a diagnostic problem P is

• SA-parsimonious iff it has an explanation which has a ~-minimal assumption set within the final worlds for P;
• SH-parsimonious iff it is a ~-minimal element of the set of solutions to P;
• CA-parsimonious iff it has an explanation with minimum number of assumptions within the final worlds for P;
• CH-parsimonious iff it has minimum cardinality within the set of solutions to P.

The various definitions are not independent from each other and from the concept of confirmed solution; these relationships are summarized by the following pro­ perties.

Property 3. Given a solution 9 to a diagnostic problem, (a) e is SA-parsimonious iff it is SH-parsimonious;

• (c) if e is CH-parsimonious, then it is SH-parsimonious.
• (b) if e is CA-parsimonious, then it is SA-parsimonious;

Property 4.

• (a) A strongly confirmed solution to a diagnostic problem is CA-parsimonious and CH-parsimonious (and then SH-parsimonious and SA-parsimonious).
• (b) A weakly confirmed solution to a diagnostic problem is CH-parsimonious (and then SH-parsimonious and SA-parsimonious).

It is worth noting that there is no general relation between CA-parsimony and CH-parsimony or weak confirmation. Consider the example in figure 3. For the problem characterized by '¥1={m1} the solution 9 1 ={H 1 } obtained under the assumption set {cr1,cr2} is CH-parsimonious and weakly confirmed; the solution 9 2={HhH2} obtained under the assumption set {t1} is CA-parsimonious.

6 The idea in Reiter's and de Kleer's approaches as well as in our one is that parsimony can be also used to gain in efficiency, avoiding the construction of redundant solutions.

4. AN EXAMPLE

As a simple example in a real-world domain, consider the following diagnostic problem on the causal model in figure 1, where we assume, for the sake of simplicity, that nodes have no attributes:

P1=<NET1,HYP1,'¥1>, where:

• NET 1 is the logical model of the networlc
• HYP1={<burnout,high engine temp>,
• <melting, melted _pistons>,
• <ignition _problems,irreg_ignition>}
• '¥1 = {dirty_sparlc_plugs, lack_of_accel, temp_indic_red, vapour}

The only final world is that containing the assumptions {oil_cup_holed, old_spark_plugs, ex}, where ex is the assumption associated with the CAUSAL arc between the states "high engine temp" and "power decrease". There­ fore the oniY solution to P is {burnout}. Notice that the presence of "old _spark _plugs" is necessary to explain "dirty _spade _plugs", but the related diagnostic hypothesis "ignition _problems" is not part of any solution, due to the absence of "mumbling engine". In this case the "MAY" relationship between "spark _plugs_ used_ up" and "irreg ignition" does not hold. On the other hand, the initiaC assumption "oil_ cup_ holed" is necessary to explain "temp indic red" and "vapour"; in fact "stack smoke" is absent and -thus the assumption "piston rings used" is rejected while the absence of "oil below cat' is not relevant because it is not a necessary consequence of "oil_ cup_ holed".

5. CONCLUSIONS

In this paper we have presented a formal theory of causal diagnostic reasoning, paying particular attention to the problem of dealing with incomplete knowledge. Different forms of incompleteness have been discussed, and a non­ monotonic reasoning process for drawing (defeasible) con­ clusions in the presence of incompleteness has been presented. In summary, such forms of incompleteness can be divided into two main classes:

• Abstracted knowledge: initial causes and abstracted

• conditions fall within such a class. A hypothetical rea­ soning scheme has been designed in order to deal with abstracted knowledge.
• Missing knowledge: in order to draw conclusions from incomplete models, different forms of circu~ptive reasoning have been used on the causal model Itself and on the findings observed in a specific case under exami­ nation.

The diagnostic process described in this paper has been implemented in Prolog, experimenting different control strategies in order to avoid inefficiencies. In particu~ar, compiled heuristic rules are used' to focus the reasorung process (i.e. to limit the number of initial worlds to be considered) [5].