Exploiting Domain Knowledge for Approximate Diagnosis

1 Motivation

The AI literature contains many definitions of diagnostic rea­ soning. However, there are many reasons why we should not search for the appropriate definition of diagnosis, but instead search for alternative definitions, and investigate how they re­ late to each other. There exists a whole space of reasonable notions of diagnosis. These notions can be seen as mutual approximations.

Strategies for approximate diagnosis can be used (1) to choose another, related notion of diagnosis when one defini­ tion of diagnosis fails (e.g. too many diagnoses, no diagnosis), (2) to reduce the cost of diagnosis using an anytime algorithm, (3) to deal with incompleteness of data and knowledge (4) to find an appropriate definition suited for the purpose and cir­ cumstance of performing diagnosis. See [van Harmelcn and ten Teije, 1995] for more motivation for approximations in diagnosis.

In the literature, the definition of diagnosis is usually char­ acterised using the logical entailment relation (Sec. 2 of this paper). In this paper we usc existing notions of approximate entailment [Schacrf and Cadoli, 1995] (Sec. 3) to define no­ tions of approximation in diagnosis (Sec. 4). In Sec. 5 we give four strategies for exploiting approximations in di­ agnosis using approximate entailment, and we illustrate these strategies in a small car domain example. The final section discusses related work and concludes.

2 Definition of Diagnosis

We use a common definition of diagnosis that is widespread in the literature. We follow [Console and Torasso, 1991] and combine in our definition both abductive and consistency

Frank van Harmelen

Dept. of Math. and CS

Vrije Universiteit Amsterdam

frankh@cs.vu.nl

based diagnosis, which accounts for a large variety of diag­ nostic systems from the literature.

Definition 1 (Diagnosis problem and solution)

Given a behaviour model BM (a logical theory in clausal form) , and two sets of observations o+ and o- (both sets of literals read as conjunctions), a solution to a diagnostic problem is a set of literals E ( "E" for explanation, again read as a conjunction), which satisfies the following:

We will write OBS for the set of all possible observables from which the letters of o+ and o- must be taken, and require that E is disjoint from OBS. o+ is the set of observations that must be explained abductively (i.e. they must be implied by the explanation E), while o- only needs to be consistent with the explanation E.

Formulae (1) and (2) constitute the abductive part of our no· tion of diagnosis (ABO), and (3) the consistency based part (CBD). Although (2) directly follows from (3) for classical entailment we include both conditions explicitly, because the central idea of our method of approximations in diagnosis is to parametcrise the notion of diagnosis over different approx­ imations of the entailment relation (in particular of Schaerf & Cadoli 's approximate entailment relations).

We emphasise that our particular definition of a diagnostic problem and its solution is not of crucial importance to our central message that approximate entailment can be usefully exploited for diagnostic reasoning to obtain interesting and efficient results.

3 Summarising approximate entailment

In this section we will summarise the work in [Schaerf and Cadoli, 1995], which defines the approximate entailment rela­ tions that we will exploit for our work on diagnoses. Schaerf and Cadoli define two approximations of classical entailment, named f- 1 and h which arc either unsound but complete (h) or sound but incomplete (f- 3) . By analogy, they sometimes write f- 2 for classical entailment. Both of these approxima­ tions are parameterised over a set of predicate letters S (written f-f and f-f) which determines their accuracy. We repeat some of the basic definitions from [Schaerf and Cadoli, 1995):

Definition 2 (1-S -assignment, 3-S -assignment)

A 1-S- and 3-S -assignment are defined as follows:

• ·If x E S then x and --.x get opposite truth values
• If x '/. S then
• for a I-S-assignment, x and ·X both become 0.
• for a 3-S -assignment, x and ·X do not both become 0.

In other words: for letters in S, these assignments behave as classical truth assignments, while for letters x '/. S they make either all literals false (1-S -assignments) or make one or both of x and --.x true (3-S -assignments).

Satisfaction of a clause by a 1-S- or 3-S -assignment, and the notions of 1-S -entailment and 3-S -entailment are defined in the same way as classical satisfaction and entailment.

Intuitively, for 3-S -entailment the predicates outside S are deemed irrelevant for deduction, while for 1-S -entailment these predicates are taken as false. The following syntactic notions can be used to clarify these definitions. For a the­ ory in clausal form, 1-S -entailment corresponds to classical entailment, but after removing from every clause any liter­ als with a Jetter outside S. When this results in an empty clause, the theory becomes the inconsistent theory L Simi­ larly, 3-S -entailment corresponds to classical entailment, but after removing every clause from the theory that contains a literal with a Jetter outside S . This may result in the empty theory T.

The main result of [Schaerf and Cadoli, 1995] is:

Theorem 1 (Approximate entailment)

where S ~ S'. (Everywhere primed letters are a superset of the unprimed Jetter~.

This states that I- 3 is a sound but incomplete approximation of the classicall-- 2· The counterpositive of the second half of the theorem (reading Iff =>Iff =>ft'z) states that Iff is a sound but incomplete approximation of ft'z.

Example 1 (Illustrating I-~ and Iff)

We illustrate these notions with figure 1. We can see that I-~ is incomplete with respect to 1--z, since in the theory BM of figure 1 we have that classically BMU{H3} 1--z 0 1, but if we restrict S to LET(BM) \ {H3}, where LET(BM) stands for all the predicate letters in BM, we do not have that BM U {H3} I-~ 0 1. This is so because takingS= LET(BM)\ {H3} amounts to removing H3 ---+ 0 1 from BM.

Similarly, Iff is incomplete with respect to ft'z (or equiv­ alently, i-f is unsound w.r.t. 1--z) since, for example, if S = LET(BM) \ {Ho}, then BM U {Ht} ft'z OJ. but BM U {H1} 1--f 0 1· This is so because taking S = LET(BM) \ {Ho} amounts to removing H0 as a conjunct from H1 1\ Ho---+ OJ.

Furthermore, with increasing S, the accuracy ofthese approx­ imations improves, until the approximate versions coincide with classical entailment when all letters are included in S.

Schaerf and Cadoli also give incremental algorithms for computing i-f and I-~ when S increases. They have obtained attractive complexity results which state that even when com­ puting 1--z through iterative computation of I-~, the total cost of the iterated computation is not larger than the direct compu­ tation of 1--z (and similarly for Iff to compute ft'z). However, the iterative computation of the approximate entailment has as important advantage that the iteration may be stopped when a confirming answer has already obtained for a smaller value of S. This yields a potentially drastic reduction of the com­ putational costs. The size of these savings depend on the appropriate choice for S.

Although the summary above is based on a propositional calculus, the theory that we will apply the approximations to in this paper is first-order (Fig. 3). In [Schaerf and Cadoli, 1995] they show how the propositional results can be extended to the first-order case in a straightforward way.

4 Summarising approximate entailment in diagnosis

In this section we summarize the results [ten Teije and van Harmelen, 1996] on applying 1--f and I-~ in diagnosis. We use 1--f and I-~ in both the ABO-part of our definition of diagnosis (written as ABDf , ABD~) and the CBD-part (written as CBDf, CBD~). Since we write 1-- 2 for the classical entailment relation, we will also write ABD2 and CBDz.

The main intuitions behind using 1--f and I-~ in diagnosis are as follows. By using i-f, candidate solutions more easily satisfy part (1) of our definition of diagnosis, because 1--z=>i--f. Similarly, by using I-~, candidate solutions more easily satisfy parts (2) and (3) of our definition of diagnosis, since ft'z=>ft'~ .

We will write ABDf when we intend both ABDf and ABD~, and similarly for CBDf. Furthermore, we write ABDf for the set of all diagnoses E which satisfy ABDf (E), and similarly for ABDz, CBDf and CBDz

There are two im~ortant relations ~ and ~ for relating the ABDf and CBDi diagnoses.

Definition 3 For any set of sets P and P', P ~---+ P' and P ~ P' are defined by:

Notice that these relations are relations between sets of sets. The required superset and subset relation is among the ele­ ments (sets) of these sets of sets.

I

For the set of abductive diagnoses we have the following relation:

Theorem 2 (Relations between ABVf)

This states that ABDf diagnoses consist of parts of ABD2 diagnoses, and that ABO~ diagnoses contain ABDz diagnoses. Another result is on the number of diagnoses:

Theorem 3 (Sizes of ABVf)

We have analogous results for the CBD-part:

Theorem 4 (Relations between csof)

• 0 = CBV~ c CBVf 8 CB'Dz 8 CBVf 8 CBV~ = £
• 0=CBV~cCBVfcCB'DzcCBV~cCB'D~=£
• 0 = ICB'D~I < ICB'Dfl < ICB'Dzl < ICB'Dfl < ICB'D~I

where £ stands for any consistent set of literals whose letters are taken from LET(BM) \ OBS. The first sequence of inclu­ sions states that csof diagnoses consist of parts of classical CBD-diagnoses, and that every classical diagnosis is contained in at least one csof diagnosis. In [ten Teije and van Harme­ len, I <J<J6] we also ·have theorems about the type (superset or subset) of new diagnoses that can be found by changing S. "New" means that using the new value of S, we compute at least one superset/subset diagnosis which was not present for the old value of S. These theorems are summarized in Fig. 2.

5 Strategies for approximate diagnosis

5.1 General strategies

We can usc approximate diagnosis (results of Sec. 3 and 4) for solving problems of too many, too few, too large and too small diagnoses. When such a problem occurs with a particular notion of diagnosis, we could choose another related notion. In our case of using Schaerf & Cadoli's approximate entailment relation, this means changing the parameterS.

In this section we only consider increasing S, because this allows us to use the incremental algorithm of Schaerf & Cadoli. They show that the total cost of the iterated computa­ tion is not larger than directly computing classical entailment. However, the iterative computation of the approximate entail­ ment may be stopped when a satisfactory answer is already obtained for a smaller value of S.

Focusing on increasing S results in the following general strategies:

Solutions for the problem of too few diagnoses:

• Shifting from ABDf to ABDf'
• Shifting from ABDf to ABDf (see strategy III)
• Shifting from csof to csof' (see strategy II).

Solutions for the problem of too many diagnoses

• Shifting from csof to csof (see strategy I)

Solutions for the problem of too small diagnoses

• Shifting from ABDf to ABDf' (see strategy IV)
• Shifting from csof to csof'

Solution for the problem of too large diagnoses

• Shifting from ABDf to ABDf

These strategies are general in the sense that they do not exploit specific properties of the behaviour model. Using such properties would be more attractive because this enables us to be more precise about how we could extend S and determine the characteristics of the diagnoses that will be computed. In Sec. 5.3 we give such specific strategies.

5.2 Example Behaviour Model (BM)

The example that we use for our strategies is taken from [Dupre, 1 <J<J4] and is shown in Fig. 3. This figure shows a partial causal model of a car. The causal network contains 42 nodes and 40 causal links. We transform the causal network of Fig. 3 to an equivalent two layered network, because we use the results of [ten Teije and van Harmel en, 1 <J<J6), and some of them are restricted to a two layered network.

In causal networks f Console and Torasso, 1 <J<JO ], states are represented as predicates, and the fact that stateS; necessarily causes state Sj is represented as S; ~ Sj. The fact that S; possibly causes state Sj can be written as S;l\o:;j ~ Sj , where O:ij (called the incompleteness assumption) is interpreted as the unknown condition required for S; to cause Sj .

The letters of the two layered version of the network from Fig. 3 are the initial causes (written as the set H), the incom­ pleteness assumptions (the set A), and the observables (the set 0).

5.3 Strategies Dependent on properties of BM

In this section we give four strategies of approximations in diagnosis which depend on properties of the behaviour model.

Strategy (I) and (II) use the specificity of observables, strat­ egy (Ill) and (IV) use the necessity of the causal relations. Besides using different properties of the behaviour model, the strategies arc distinct examples of approximating diagnoses. Strategy (I) and (II) arc examples of changing the CBO-part. Strategy (Ill) and (IV) are examples of changing the ABO­ part. Also, they are strategies to deal with different types of problems with the diagnoses: strategy (I) reduces the number of diagnoses, strategy (II) and (IV) increase the number of diagnoses, strategy (Ill) increases the size of the diagnoses.

Using Specificity of Observations

Strategy (I) and (II) arc based on the specificity of obscrv­ ables. We usc a whole spectrum from specific to a-specific obscrvablcs. We call an observable more specific if it has fewer possible causes. For the car example this spectrum is shown in Fig. 4.

Strategy (1). This strategy can solve the problem of" too many diagnoses". The strategy is based on the idea that an expla­ nation cannot be a diagnosis if one of its specific observablcs is not observed. We approximate this by using the spectrum from the specific to the a-specific end. We apply definition 1 using CBof, AB02, and the initial value of S (Sinit) is only all the possible causes and the incompleteness assumptions, and none of the obscrvablcs. Because the consistency part of the ABO-formula (2) implies CBO;'n", any ABO-explanation will be a diagnosis. Extending s· with the most specific ob­ scrvablcs means that a cause of such an observable can only remain part of the diagnosis when its specific observables arc observed. We extendS with increasingly less specific observ­ ablcs until one diagnosis is left or no diagnosis is left. In the latter case we consider the diagnoses of the previous step as

the best diagnoses.

Example 3 (Strategy (I)) (In the examples we give only the subset minimal diagnoses.) We illustrate this strategy using the following values:

For Sinit each ABO-explanation is CBD~ -consistent with o-, because S contains no observables. We do not introduce inconsistency by extending S with Spec~, in contrast with extending S further with Spec2. This extension introduces inconsistency between ·exhaust smoke(black) and each of the explanations {engine mileage(> 1 00000km),a2} and {engine mileage(> 100000km),a3}. We stop at Sinit +Spec1 +Spec2 because we have just one diagnosis left.

Our final explanation is CBD~ -consistent with the nega­ tive observation -, accelerator response( delayed) (for S = Sinit + Spec1 + Specz). Under CBDz it would have been in­ consistent with this observation, but we consider this is of less importance because of the low specificity of this observable.

Strategy (II). This strategy can solve the problem of "too few diagnoses". The strategy is based on the idea that a cause has to be excluded if a specific observable is not observed. We apply definition 1 using csof and ABD2. If an observable is not in S, then no possible cause of this observable can be part of the diagnosis. We allow non-observed observables to be implied by the diagnosis only if these additional observables are non-specific. Therefore the strategy uses the spectrum of specificity of observables from a-specific to specific.

We initialise S with all possible causes, plus o+ and o-. Excluding o+ from S would result in inconsistency of all the explanations, because each possible cause of an o+ observ­ able would be excluded by CBDf. Excluding o- would mean inconsistency with o- and BM. We increasingly extend S with more specific observables. This introduces possibly more diagnoses, because more causes will be enabled by the observables inS.

Example 4 (Strategy (II)) We illustrate this strategy using the following values:

o+ =

o- =

{fuel(irreg)}

{ ·fuses(burned)}

Sinit = HuAu o+ uo-

Sinit gives no diagnoses because every cause still has an ob­ servable which is not in Sinit · Sinit extended with Specs and Spec4 results in the first diagnosis. All observables of the causes spark plugs mileage and as are in S. If we continue extending S more diagnoses could be found. This example illustrates that one would prefer the diagnosis whose observ­ ables are observed (consistent) or (if they are not observed) riot very specific.

Using Necessity of Causal Relations

Strategies (III) and (IV) are based on the necessity of the causal relation.

Our behaviour model contains necessary causal relations (Si -+ Sj) and possible causal relations (Si 1\ aij -+ Sj ). However, for our strategies we will use a whole spectrum of the necessity of the causal relation by dividing the incom­ pleteness assumptions ai in several groups and ordering them. This ordering is meant to indicate the degree of necessity of the causal relation. This ordering in the car domain is as follows·

Note that this spectrum IS domam specific knowledge, whereas the specificity of observables can be determined syn­ tactically.

Strategy (III). This strategy can solve the problem of "too few diagnoses". The strategy is based on the idea of taking as little notice as possible of non-necessary relations. We use the spectrum from the necessary-side to the possible· side. This amounts to first completely ignoring the possible relations and introducing them increasingly starting from the most necessary ones. We apply definition 1 using ABD~, CBD2, and the initial value of Sis all symbols of BM without the o ;. This results in only diagnoses which use necessary causal relations. If we extend S with o;, we also use less necessary causal relations.

Example 5 (Strategy (Ill)) We illustrate this strategy using the following values:

o+ = {battery power( between 20 and 45 ah)}

o- = 0

S init = 1-l U 0

In the first step only necessary relations are used, and no diag­ nosis is found. Extending S with the incompleteness assump· tions with the highest degree of necessity (Foss 1) enables the use of the causal relations with a 5 and Ct<J giving the diagnosis {alternator belt(slack),a9}. Adding more incompleteness as­ sumptions allows us to use more possible relations and results in two extra diagnoses.

Strategy (IV). This strategy can solve the problem of "too small diagnoses". The strategy is based on the idea to start with paying no attention to the necessity of relations, i.e. to use all relations as necessary. All diagnoses will be without the incompleteness assumptions even though they might be using non-necessary links. These diagnoses can later be extended using the necessity of the causal relations. We apply definition 1 using ABDf, CBD2, and the initial value of S is all letters of BM excluding the a;. Extending S with those a; which are in the spectrum at the possibie end, results in detailed diagnoses if such relations are used in the explanation. This means that those diagnoses with the most unreliable causal links will be the first to get extended with the appropriate a; .

We do not illustrate this strategy because of lack of space.

6 Discussion

The main message of this paper is that we apply approx­ imation strategies to diagnosis, and that the approximation strategies are informed by particular properties of the domain knowledge. The strategies (!)-(IV) all deal with problems concerning the size and number of the diagnoses. However, our approximation techniques can also be used to model many of the general focusing strategies described in the literature. For instance, by dividing the behaviour model in sub-models, and by choosing for S only the letters of a particular sub­ model, we effectively obtain a focusing strategy based on the use of these sub-models. Other focusing strategies can be dealt with in the saine way.

A first obvious task for future work would be to apply our proposed algorithms to a more realistic application. A can­ didate for this could be a domain where explanations can be ordered based on their urgency. According to theorem 2, us­ ing ABDf and initialising S with the most urgent explanation candidates, and adding gradually less urgent candidates com­ putes only urgent subsets of classical diagnosis, and computes only non-urgent abductive diagnoses when S is increased if resources allows. This yields an anytime algorithm that per­ forms well for urgent diagnoses under time pressure. A sec­ ond obvious task is to study the efficiency behaviour of our approximation algorithms in larger behaviour models then we have presented here.

Finally, our approach to diagnostic strategies should be compared with other approaches, in particular [Bottcher and Dressler, 1994], based on [Struss, 1992]. In this approach, so called "working hypotheses" indicate various restrictions on, or preferences for potential diagnoses. The set of active working hypotheses is then modified to switch from one set of diagnoses to another. We claim that defining S as the set of all letters from the behaviour model plus the active working hypotheses would yield an alternative formalisation.