Representing Diagnostic Knowledge for Probabilistic Horn Abduction

1 Introduction

Determining what is in a system from observations ( di­ agnosis and recognition) are an important part of AI. There have been many logic-based proposals of what a diagnosis is [Reiter, 1987; de Kleer and Williams, 1987; Poole, 1989; de Kleer et al., 1990]. One problem with these proposals is that for any problem of a reasonable size there are far too many "logical possibilities" to han­ dle (for a human or a computer) . For example, when considering fault models [de Kleer and Williams, 1989; Poole, 1989], there is almost always an exponential num­ ber oflogical possibilities (e.g., each component could be in its normal state or in the abnormal unknown state). For practical problems, we find that many of the log­ ically possible diagnoses are so unlikely that it is not worth considering them. There is a problem, however, in removing the unlikely possibilities a priori: it may happen that the unlikely occurrence is the actual truth in the world.

Such analysis of the combinatorial explosions would tend to suggest that we need to take into account prob­ abilities of the diagnoses [de Kleer and Williams, 1987; Peng and Reggia, 1990; Neufeld and Poole, 1987], and not generate the unlikely diagnoses. Similar experi­ ence has been found in natural language understanding [Hobbs et al., 1988; Goldman and Charniak, 1988].

Probabilistic models of diagnostic reasoning [Pearl, 1988; Heckerman and Horvitz, 1990; Andreassen et al., 1987], being purely propositional by nature, do not have the modelling power of the logic-based models.

In all of the implementations, we do not generate the unlikely explanations unless we need to. Hopefully we can cut down on the combinatorial explosions that are inherent in considering the set of all logi­ cally possible explanations, but this is beyond the scope of this paper.

2 The System

2.1 Abductive Framework

The formulation of abduction used is in terms of Theorist [Poole et al., 1987; Poole, 1987].

Given a language L, and a consequence relation (writ­ ten I=) on L, and an abductive scheme is a pair (F, H) where F and Hare sets of sentences in L .

Definition 2.1 [Poole et al., 1987; Poole, 1987] If g is a ground formula, an explanation of g from (F, H) is a set D ~ H such that

• F U D I= obs and
• FUD~l.

where .1. is an atom representing false . The first condi­ tion says that, D is a sufficient cause for obs , and the second says that Dis possible (i.e., FUD is consistent).

Definition 2.2 A minimal explanation of g is an ex­ planation of g such that no strict subset is also an ex­ planation.

Associated with each minimal explanation D, is a measure JJ(D) [Neufeld and Poole, 1987]. This measure could be an assumption cost that is added [Hobbs et al. , 1988], but in this paper we investigate the use of proba­ bility as a measure over explanations.

2.2 Probabilistic Horn abduction

In probabilistic Horn abduction we restrict the language L to be Horn clauses.

We use the normal Pro log definition of an atomic sym­ bol [Lloyd, 1987]. A Horn clause is of the form:

where a and each a; are atomic symbols. false is a special atomic symbol that is not true in any interpretation 2 . All variables in F are assumed universally quantified.

We restrict the elements of H to be ground instances of atoms. If we are given a set of open atoms as possible hypotheses we mean the the set of ground instances of these atoms.

2 Notice that we are using Horn clauses differently from how Prolog uses Horn clauses. In Prolog, the database con­ sists of definite clauses, and the queries provide the negative clauses [Lloyd, 1987]. Here the database consists of definite and negative clauses, and we build a constructive proof of an observation.

2.3 Probabilities

The measure we use is the probability of the explanation. Associated with each possible hypothesis (i.e., with each ground instance of an open possible hypothesis) is a prior probability. The aim is to compute the posterior probability of the explanations given the observations. Abduction gives us what we want to compute the prob­ ability of and probability theory gives a measure over the explanations [Neufeld and Poole, 1987].

We use the declaration

where h can contain free variables, to mean each ground instance of h is in H with prior probability p .

To compute the posterior probability of an explana­ tion H = { h11 ... , hn} given observation obs, we use Bayes rule and the fact that P(obsiH) = 1 as the explanation logically implies the observation:

The value, P( obs) is the prior probability of the obser­ vation, and is a constant factor for all explanations. We compute the prior probability of the conjunction of the hypotheses using:

The value of P(h1 1\ ... 1\ hn-d forms a recursive call, with P( true) = 1. The only other thing that we need to compute is

The first thing to notice is that if hn is inconsistent with the other hypotheses, then its probability is zero. These are exactly the cases that are removed by the incon­ sistency check. Similarly if hn is implied be the other hypotheses, its probability is one. This will never be the case if the explanations are minimal. While any method can be used to compute this conditional probability, the assumption of conditional independence is often an ap­ propriate assumption in many domains [de Kleer and Williams, 1987; Peng and Reggia, 1990]. We make this assumption here and in later sections we show how to al­ low arbitrary probabilistic interactions, without chang­ ing the underlying system. The system uses the following assumption:

Assumption 2.3 Logically independent instances of hypotheses are probabilistically independent.

Definition 2.4 A set H of hypotheses are logically in­ dependent (given F) if there is no S C H and h E H\S such that

The assumptions in a minimal explanation are always logically independent. Minimality ensures that no hy­ pothesis in an explanation can be implied by other hy­ potheses in the explanation. Consistency ensures the negation of a hypothesis cannot be implied by other hy­ potheses.

Under assumption 2.3, if{h1, ... , hn} are part of a min­ imal explanation, then

thus

To compute the prior of the explanation we multiply the priors of the hypotheses. The posterior probability of the explanation is proportional to this.

One problem that arises is in determining the value of P(obs).

When using abduction we often assume that the di­ agnoses are covering. This can be a valid assumption if we have anticipated all eventualities, and the observa­ tions are within the domain of the expected observations (usually if this assumption is violated there are no ex­ planations) . This is also supported by recent attempts at a completion semantics for abduction [Poole, 1988; Console et al., 1989; Konolige, 1990]. The results show how abduction can be considered as deduction on the "closure" of the knowledge base that includes statements that the given causes are the only causes. The closure implies the observation are logically equivalent to the disjunct of its explanations. We make this assumption explicit here:

Assumption 2.5 The diagnoses are covering.

For the probabilistic calculation we make an additional assumption:

Assumption 2.6 The diagnoses are disjoint (mutually exclusive).

It turns out to be straightforward to ensure that these properties hold, for observations that we can anticipate 3 . We make sure that the rules for each possible sub goal are disjoint and covering (see section 3.1) .

Under these assumptions, if { e1, ... ,en} is the set of all explanations of obs:

2.4 Implementation

The very simple definition of the framework makes im­ plementation straight forward (although some difficult problems do arise in trying to make it very efficient) . We are currently experimenting with implementations based on Logic programming technology and based on ATMS technology (similar to [de Kleer and Williams, 1989]) . Both implementations keep a priority queue of sets of hypotheses that could be extended into explana­ tions ("partial explanations") . At any time the set of all the explanations is the set of already generated expla­ nations, plus those explanations that can be generated from the partial explanations in the priority queue. It is possible to put a bound on the probability mass in the queue, and this allows us to estimate errors on the results before the computation is completed (forming an "anytime" algorithm) . See [Poole, 1991b] for details.

3 Like other systems (e.g., [Pearl, 1988]), we have to as­ sume that unanticipated observations are irrelevant.

The difference between these two represents a differ­ ence between "interpreted" and "compiled" approaches [Reiter and de Kleer, 1987]. As far as the rest of the paper is concerned, it is irrelevant as to how the system is implemented. Given a specification of what it is we want to compute we can now experiment with trade-offs between various implementation strategies.

Note that the problem is NP-complete [Provan, 1988], thus we are never going to expect efficient polynomial worst-case algorithms. The best we can expect is good average-case behaviour; but this is, of course, what we are interested in.

3 Representational Methodology

Once we have a tool, it is important to know how to use it. The problem of a representational methodology [Poole, 1990] is an important and much overlooked part of automated reasoning research.

It may seem that the assumptions used in designing the system were so restrictive that the system would be useless for real problems. In this section, I argue that this is not the case.

3.1 Disjoint and Covering Explanations

For our probabilistic analysis (section 2.3), we assumed that the explanations were disjoint and covering. If we want our probabilities to be correct 4 , we must ensure that the explanations are disjoint and covering.

If the rules for an atom a are not covering, we can invent another cause for the goal representing "all the other possible causes" of the atom [de Kleer and Williams, 1989; Poole, 1989], and add

assumable ( some_other ..reason _for ..a, p).

Where p is the prior probability that something else would have caused a.

We can locally ensure that any explanations gener­ ated are disjoint. The following proposition can be easily proved:

Proposition 3.1 If for any two rules with the same con­ sequent (a +- b1, and a +- b2), the antecedents are in­ consistent (F I= b1 /1. b2 => false), then the minimal explanation are disjoint.

Although disjointedness of explanations places a re­ striction on the knowledge base, it does not place a re­ striction on the sorts of knowledge that we can represent . In general, if we have rules

'It may be the case that they are "good enough" for any decisions that we may want to make, even though they are not accurate.

these can be made disjoint by adding hypotheses h1, ... , hn to the rules

and making sure these rules are disjoint by having, for each different i and j, the fact

We need to associate a probability with each hypoth­ esis such that E, P(h;) = 1. This probability represents the probability that the particular body was "the cause" for a.

Sometimes we can make the rules naturally disjoint, by ordering the rules and making sure that the bodies of rules are false if the bodies of previous rules are true.

Example 3.2 Suppose we want to represent an "and­ gate" that should have value 0 if either of the inputs are zero. Suppose we represent the proposition that port G has output V at time T as val(G, V, T). We can en­ sure that the explanations are disjoint locally by ensur­ ing that only one body can ever be true:

This has repercussions in biasing the most likely ex­ planation to the first rule which is more general than the others. To make it more fair the first rule could be split into two cases depending on the value of in­ put 2. This problem of the most likely diagnosis de­ pending on the representation seems endemic to ap­ proaches that try to find the diagnosis (either explana­ tion or interpretation) that is "most likely" [Pearl, 1988; Poole and Provan, 1990].

3.2 Parametrizing Hypotheses

The next important part of the methodology for ab­ duction concerns parametrizing possible hypotheses and the interaction with the independence assumption. I have argued elsewhere [Poole, 1989; Poole, 1990] that there is much power obtainable and subtlety involved in parametrizing hypotheses appropriately.ln this section we expand on previous analysis [Poole, 1990], and show how probabilities affect parametrization considerations by considering some case studies on different proposals.

3.2.1 Hypotheses with indeterminate output

As an example, suppose we have a gate G that takes two values as input, and outputs a value that can be in the range 1 to n. Suppose we want to represent the gate being in an unknown state (this is applicable whether or not we have fault models [de Kleer and Williams, 1989; Poole, 1989]). Suppose we represent the proposition that gate G has output Vat timeT as val(G, V, T).

We cannot representing the hypothesis that the gate is in the unknown state by using the hypothesis u( G) and the fact

The problem is that the above fact states that a gate in the unknown state produces all values of output, rather than saying that it produces some output. Knowing a gate is in an unknown state does not imply any value for the output.

When there are no probabilities involved [Poole, 1990; Poole, 1989] we parametrize the hypothesis by the values on which it depends. This could be done by having the hypothesis produces(G, V, T) and the rule

We would say that a port has only one value at a time by having the constraint

Suppose we know that gate g1 has probability € of being in the unknown state. If we assume that each possible output value has equal chance, and that there are n possible output values, then the prior probability that it produces output value V is €/n.

When we have more than one observation, there is another problem. For the probabilities we assumed that the hypotheses were independent. We would not expect that

Once we know that the gate is in an unknown state at time t1 it should not be so unlikely that it is in an un­ known state at time t2 · Put another way, once we have paid the price once for assuming that the gate is in an unknown state at time t1 we should not pay the price again for assuming that it is in an unknown state at time t2 .

To work in general, we need a mixture of the above two ideas. Suppose a gate G has probability of € of being in the unknown state, and that there are n possible output values, each of which has an equal prior chance of being produced by a gate in the unknown state. This can be represented as the hypotheses

and the rule

u( G) means G is in the unknown state, and produces(G, V, T) means that given gate G is broken, it produces value V at time T . We assume once that the gate is broken, and then make other assumptions of what values it is producing at different times.

It is interesting to note that this analysis of dividing by n can be done when building the knowledge base and does not need to be carried out dynamically (as [de Kleer and Williams, 1989] seem to need to do). This means that distributions other than the uniform distribution can be given if appropriate.

3.2.2 Intermittent versus non-intermittent faults

Because of the way we parametrized the hypotheses, the above representation of faults says that the out­ put is only a function of the time. The hypothesis prod( G, V, T) and the above rules places no constraints on the values of the outputs at different times. This is a way to represent the fact that the gate can have an intermittent fault (it depends only on the time of ob­ servation). There is no constraint that says the gate produces the same output when given the same inputs at different times.

We can give the non-intermittency assumption by say­ ing that the fault only depends on the input and not on the time. This can be done instead by having the hypothesis prod( G, V, II, 12) (meaning gate G produces output V when given II and 12 as input) and a rule

With the same integrity constraint as before, it is in­ consistent to assume that the gate has different outputs for the same input.

3.3 Causation events

When using abduction we run into the problem of a cause not actually implying a symptom. For example, having a cold does not imply sneezing, but could cause sneezing. To implement this idea we introduce another hypothesis that the cold caused the sneezing. This idea is analogous to the notion of a "causation event" of Peng and Reggia [1990] .

To implement the causation events, we can use the relations has_disease(D) to mean that the pa­ tient has disease D; actually..causes(D, M) to mean that diseaseD "actually caused" manifestation M; and has..manifestation(M) to mean that the patient has manifestation M.

We can say that a manifestation is caused by the dis­ ease that actually causes it by:

We can use the rule to say that there is only one actual cause of a manifestation by:

This rule ensures that the explanations for having a manifestation are disjoint.

The conjunction

corresponds to Peng and Reggia [1990]'s causation event M : D. The completion semantics of abduction [Poole, 1988; Console et al., 1989; Konolige, 1990] show that, un­ der the covering explanation assumption, we implicitly have the relationship

We have the possible hypothesis

where p;; is the "conditional causal probability" ("causal strength") of [Peng and Reggia, 1990]. It can be seen as the fraction of the cases of d; being true that m; is actually caused by d;.

We also have the possible hypotheses

where p; is the prior probability of the diseased;.

4 Representing Bayesian networks

In this section we give the relationship between Bayesian networks and our probabilistic abduction. The analysis here is, in some sense, the dual of the analysis given by Charniak and Shimony [1990] . We show how any proba­ bilistic knowledge that can be represented in a Bayesian network, can be represented in our formalism.

Suppose we have a Bayes net with random variables a1, ... , an, such that random variable a; can have values v;,t. ... , Vi,n;. We will represent random variable a; having value v;,; as the proposition a;( v;,; ).

The first thing we need to do is to state that the values of variables are mutually exclusive. For each i and for each j, k such that j :f. k, we have the rule

A Bayes net [Pearl, 1988] is a directed acyclic network where the nodes represent random variables, and the arcs represent a directly influencing relation. Terminal nodes of a Bayes net are those variables that do not influence any other variables. A composite belief [Pearl, 1987] is an assignment of a value to every random variable.

Suppose variable a is directly influenced by variables bt, ... , bm in a Bayes network. This can represented in our system by the rule:

Here the intended interpretation of

is that a has value v because bl has value vl, ... , and bm has value Vm .

Associated with the Bayes net is a contingency table [Pearl, 1988] which gives the marginal probabilities of the values of a depending on the values of bt, ... , bm . This will consist of probabilities of the form

This is translated into the assertion

assumable( caused_a( v, v1 , v2 , ... , vm), p) .

The following propositions can be proved [Poole, 1991b]:

Lemma 4.1 The minimal explanations of the terminal variables having particular values correspond to the com­ posite beliefs in the Bayes net with the terminals having those values. The priors for the explanations and the composite beliefs are identical.

As the same procedure can be used to get from the priors of composite hypotheses and explanations to the posteriors given some observations, the following theo­ rem is a direct corollary of lemma 4.1.

Theorem 4.2 If the observed variables include all ter­ minal variables, the composite beliefs with the observed variables having particular values correspond exactly to the explanations of the observations, and with the same posterior probability.

If the observed variables do not include all terminal values, we need to decide what it is that we want the probability of [Poole and Provan, 1990]. If we want to commit to the value of all variables, as in the composite belief of Pearl [1988], then we consider the set of possible observations that include assigning values to terminal nodes. That is, if o was our observation that did not not include observing a value for variables a;, then we need to consider the observations o 1\ a;( v;,1), ... , o 1\ a;( v;,n;). To find the accurate probabilities we need to normalise over the sum of all of the explanations. Whether or not we want to do this is debatable.

It is not only the probability of a composite hypothesis that has a characterisation in terms of explanations.

Let e:epl(a) be the set of minimal explanations of proposition a. Define

Lemma 4.3 If H is a set of assignments to variables in a Bayesian Network, and H' is the analogous propositions to H in the corresponding probabilistic Horn abduction system, then

A simple corollary of the above lemma can be used to determine the posterior probability of a hypothesis based on some observations:

Theorem 4.4

The denominator can be obtained by finding the ex­ planations of the observations (or can be approximated by finding some of the explanations that cover some proposition of the probability mass) . The numerators can be obtained by explaining z;( v;) from these expla­ nations (see [Poole, 1991a]).

What is important about the comparison with the Bayes net is that any probability distribution that can be represented as a Bayes net can be represented using the probabilistic Horn abduction. The opposite is not the case, however, because our Horn abduction is not restricted to a propositional language.

5 Comparison with other diagnostic systems

The closest work to that presented here, namely the work of de Kleer and Williams [1987; 1989] and Peng and Reg­ gia [1990], both incorporate probabilistic knowledge to find the most likely diagnoses.

5.1 de Kleer and Williams

de Kleer and Williams [1987; 1989] have explored the idea of using probabilistic information in consistency­ based diagnosis (see [Poole, 1988; Poole, 1989; Console et al., 1989; Konolige, 1990] for comparisons between abductive and consistency-based diagnoses) . .

They differ from us in what they compute the prob­ ability of. de Kleer and Williams are finding the most likely interpretations (this is the same as the diagnoses of Peng and Reggia [1990] and the composite beliefs of Pearl [1987], but is different to the kernel or minimal di­ agnoses of de Kleer, Mackworth and Reiter [1990]). We are computing the most likely explanations; we want to remain agnostic about the value of the irrelevant hy­ potheses. de Kleer and Williams cannot distinguish be­ tween the remaining diagnoses that differ in substantial ways from the most likely in.terpretation, and those that differ only in varying values that are irrelevant to the diagnosis. In our system, hypotheses that are not part of an explanation are ignored, and play no part in the probability of a diagnosis.

We differ in the use of the assumption-based frame­ work. We are using the assumption-based reasoning, with variables, as the object language. They use the ATMS as a book keeping mechanism for their diagnostic engine.

5.2 Peng and Reggia

Peng and Reggia [1990] also consider an abductive def­ inition of diagnosis and incorporate probabilities, and best-first search. Like [de Kleer and Williams, 1989; Pearl, 1987] they are trying to find probabilities of in­ terpretations. We also do not assume that the set of manifestations is complete. The main difference, how­ ever, is in the underlying language. They use the notion of "hyper-bipartite" graphs made up of causation rela­ tions on sets of manifestations (can be observed), dis­ orders (can be hypothesised), and pathological states. We, however, allow the full power of Horn clauses. We can represent the probabilistic knowledge of Peng and Reggia (see section 3.3) .

6 Conclusion

This paper presented a simple but powerful mechanism for diagnostic reasoning and showed how it can be used to solve diagnostic representation problems. One main advantage of the simple specification of what we want to compute is that we can investigate different imple­ mentation techniques to determine which works best in practice.

One question that needs to be asked is whether a set of most likely explanations is really what we want to compute [Poole and Provan, 1990]. We conjecture that for real problems , the probability mass of the most likely explanations will be so close to one to make the question moot. By ignoring the large number of very unlikely explanations, we will not make many mistakes. Whether this is true in practice remains to be seen.

We are also investigating the use of the abductive framework for differential diagnoses, and for making de­ cisions, but that is beyond the scope of this paper.

Acknowledgements

Thanks to Alan Mackworth and Mike Horsch for valu­ able comments on a previous version of this paper, and Mike for work on the implementation. This research was supported under NSERC grant OGP0044121, and under Project B5 of the Institute for Robotics and In­ telligent Systems.