A Knowledge-Level Account of Abduction

1 Introduction

Using the terminology of C. S. Peirce, given sentences a, {3, and (a ::J {3), there are three operations one can consider: from a and (a ::J {3), one might deduce {3; from a and {3, one might induce (a ::J {3); 1 and from !3. ~nd (a ::J {3), one might abduce a. Of course, charactenzmg precisely what should be deduced, induced, or abduced in various circumstances is quite another matter, and the last of these is the subject of this paper.

Abduction can be thought of as a form of hypothet­ ical reasoning. To ask what can be abduced from {3 is to ask for an a which, in conjunction with background knowledge, 2 is sufficient to account for {3. When a and {3 are about the physical world, this normally involves finding a cause a for an observed effect {3. For instance, {3 might say that a symptom of some sort is observed and a might say that a disease is present. We often say in this case, that a explains {3. But not all abduction is concerned with cause and effect. If we happen to known that Marc is 3 or 4 years old, the fact that he is not yet 4 does not explain his being 3, although it does imply it, given what is known. 3 It would be more acc~.uate to say that the a is sufficient to tell us that the {3 IS true. But this is a bit cumbersome, so with this caveat in mind, we will often use the explanation terminology here.

·Fellow of The Canadian Institute for Advanced Research. This research was made possible in part by a grant from the Nat ural Sciences and Engineering Research Council of Canada.

1 More likely, one would want to induce Vx(a :::> {3) from instances of a and {3.

2 The distinction between knowledge and belief is not im­ portant here, and we will use the terms interchangeably.

When it comes to formally characterizing abduction, existing approaches fall into two broad camps: those, like [Reggia, 1983, Allemand et al., 1987], that are set-cove.r based, and those, like [Poole, 1988, Eshghi and Kowalski, 1988], that are logic based. In the former case, abduc­ tion is defined over sets of observations and hypotheses, in terms of coverings, parsimony, plausibility, and the like. A disadvantage of this approach is that it is dif­ ficult to express how a small change in the background knowledge can contribute to changing what counts as an explanation. In the latter case, however, this knowledge is represented directly as a logical theory, and a is con­ sidered an explanation for {3 if ( 1) it is logically consistent with what is known, and (2) together with this knowl­ edge, logically implies {3. The disadvantage of .defin~ng abduction in this way is that it locks the specificatiOn of reasoning into global properties of the logic such as consistency and implication. Different reasoning abili­ ties, deductive or abductive, will then require different notions of implication or consistency.

Here we take a different approach and characterize abduction in terms of a model of belief. When belief is closed under ordinary logical consequence, this account will coincide with the idealized logic-based version. How­ ever we can look at different forms of abduction by vary­ ing the underlying notion of belief, without changing the meaning of implication. This knowledge-level approach [Newell, 1982, Levesque and "Brachman, 1986] will also force us to characterize the abduction task independently of how the knowledge is represented, and thus afford the greatest freedom in how to represent and manipulate this knowledge at the symbol level.

3 Another reason for distinguishing this from explanation is that we normally say that a explains f3 only when we be­ lieve f3 to be true, for example, when we have obser~ed the symptoms in question. So a true account of explanatiOn per se is complicated by the fact that it must consider what was known prior to believing f3 [Gardenfors, 1988], or else there will be nothing left to explain, given what is known.

In the next section, we introduce notation, discuss the need for a simplicity measure, and define a new knowledge-level operator EXPLAIN. In Section 3, we discuss the concept of regular belief and its relation to EXPLAIN . In Section 4, we examine a form of belief that is closed under logical consequence, and the ATMS as an abductive reasoner. In Section 5, we consider the spec­ ification of a more limited abductive reasoner. Finally, we draw conclusions in Section 7.

2 Abduction at the knowledge level

To define abduction, we start with£, a standard proposi­ tional language (except that for convenience, we include a special constant 0, for falsity). All beliefs will be expressed in £. We use p, q, and r to range over the propositional letters of£; a, {J, and 1 to range over the sentences of£; m to range over the literals of£; m to mean the complement of m; and, ;\ { ai} to conjoin a set of sentences, and V { ai} to disjoin them.

To talk about what is or is not believed, we use a logical language £* that is structured like £ , except that all of its atomic sentences are of the form Ba, where a is a sentence of £. 4 For different kinds of belief, we use a subscript on the belief operator. So, B>.a says that a is a belief of type .A.

The languages £ and £* are both interpreted in the standard way in that the truth values of non-atomic sen­ tences are the usual functions of the truth values of their components. For the atomic sentences of£, an assign­ ment is a total function from the propositional letters to {0,1}, and wl=a means that a is true with respect to assignment w according to the ordinary truth table (where 0 always comes out false) . For the atomic sen­ tences of£*, we assume that an epistemic state of some sort determines which sentences of£ are believed. The notation e I= B>. a says that B>. a is true at epistemic state e, which we will take as a primitive notion for now, until we look at specific types of belief.

For any sentence a of£, it will be useful to talk about II a II, the proposition expressed by a. Nothing hinges on how exactly propositions are defined, but for con­ creteness, they can be taken to be the set of all assign­ ments where the sentence in question is true. Similarly, II {at. ... , an} II is defined as {II a1ll, . . . , II an II}.

2.1 Simplicity and uniqueness

Deductive and abductive reasoning appear to be duals, but one difference between the two is that in the case of deduction, we are usually interested in testing if some sentence is deducible, while in the case of abduction, we want to produce a sentence that is abducible. 5

4 For the purpose of this paper, therefore, we will not con­ sider beliefs about other beliefs.

5 However, see Section 7 where the symmetry between de­ duction and abduction is reconsidered.

For example, consider a medical domain where sen­ tences of £ stand for properties that may or may not hold of a certain patient. Suppose we know that male and (hepatitis::::> jaundice) are both true. If we observe jaundice in the patient, we might be interested in deter­ mining what might explain it, based on .what we know about the patient. In other words, we want to reason ab­ ductively from jaundice, to find something that accounts for it, given what is known. In this case, the answer is clearly hepatitis, but it is not obvious how to characterize in general the answers we are looking for.

First of all, we cannot expect a single explanation since, for example,

( (-.-.hepatitis A migraines) V (hepatitis A -.migraines))

also accounts for jaundice. But even if we factor out logi­ cally equivalent sentences and think in terms of proposi­ tions, there will be propositions that are logically too strong, and others that are logically too weak. For instance, (hepatitis A migraines) accounts for the jaun­ dice in that it is consistent with what is known, and if it were true, then jaundice would be too. Similarly, (hepatitisV -.male) accounts for jaundice since it too is consistent with what is known, and if it were true, then jaundice would be also, since male is known to be true. Yet ( hepatitisA migraines) implies hepatitis which implies (hepatitis V -.male).

So what is it that distinguishes II hepatitis II from these other propositions? Is there a way to sort this out purely logically (in terms of sets of possible worlds and dis­ tance measures or whatever) and define an appropriate explanation? As it turns out, the answer is no. To see this, suppose to the contrary that there were a func­ tion F that given the proposition expressed by (a ::::> [J) and the one expressed by {J would always return the one expressed by a. That is, suppose that for every a and fJ, F(ll (a ::::> [J) 11.11 fJ 11)=11 a II· Then, we would have F(ll (q ::::> q) II. II q II)= II q II and F(ll ( 0 ::::> q) 11,11 q II)= II 0 II· However, II (q ::::> q) 11=11 ( 0 ::::> q) II since the two sen­ tences are logically equivalent. 6 But this implies that II 0 11=11 q II, which is incorrect. So such a function F cannot exist, and we are forced to go beyond the logic of the sentences (that is, beyond the propositions ex­ pressed) to differentiate hepatitis from other potential explanations.

One obvious approach is to maintain a list of sen­ tences that are marked as possible hypotheses as is done in [Poole, 1988, Reiter, 1987] and to only consider sen­ tences appearing in this list. But this fails to account for why we find hepatitis so compelling as the unique explanation for jaundice i~ the above. Perhaps it is be­ cause hepatitis does not deal with any other conditions, either to insist on (conjoin) irrelevant restrictions like migraines, or to allow for (disjoin) possibilities known to be false like -.male. This suggests that we should be look­ ing for sentences that are as simple as possible in their subject matter. With this notion of simplicity in mind, we are ready to provide a formal definition of abduction in terms of belief.

6 A stronger argument would be needed for a notion of proposition that was finer-grained than logical equivalence.

2.2 A general definition

First, we define explanation wrt an epistemic state e for a type of belief A:

This definition does not distinguish between trivial and non-trivial occurrences of B(a :> /3). For example, as­ suming that (jaundice :> jaundice) is believed but that -.jaundice is not, jaundice explA jaundice wrt e holds, that is, having jaundice is clearly (and trivially) suffi­ cient to account for having jaundice. More generally, if nothing is believed about f3 other than logical truths, then there will only be trivial explanations. In addition, for many types of belief, we have that if -.f3 is believed, then there will be no explanations at all, whereas if f3 it­ self is believed, then -. 0 will be-the unique explanation.

As discussed above, the definition of explanation must depend on some syntactic criterion of simplicity. Per­ haps the easiest one is the following:

Definition 2 The literals of a, LITS(a), is defined by:

LITS(0)=0; LITS(p)={p};

LITs(-.a)={m I mE LITS(a)};

LITS(a I\ {J)=LITS(a V fJ)=LITS(a) U LITS(/3).

Definition 3 a is simpler than f3 (written a -< (3) iff LITS(a) C LITS({J); also a ::S f3 iff LITS(a) ~ LITS(f3). 8

So "simpler" means "containing fewer propositional let­ ters," but keeping track of their polarity. For example, (pA-.q)-< (q :> (pVr)), but (p/1.-.q)-/< (-.q :> (pVr)) . We define a simplest explanation in the obvious way:

Definition 4

a min-explA f3 wrt e iff a explA f3 wrt e and for no a* -< a is it the case that a* explA f3 wrt e.

Finally, since there may be more than one simplest ex­ planation, and since we do not really care at this level how each simplest explanation is expressed, the task of abduction will be to return the set of propositions of all simplest explanations:

Definition 5

EXPLAINA[e,(J] = ll{a I a min-explA/3 wrt e}ll·

These simplest explanations should be understood dis­ junctively. For example, if we know that (p1 :> qi) and (P2 :> q2), then Pl is a simplest explanation of (q1 V q2) and so is P2· However, it is the disjunction (p1 V p2) that fully and non-trivially accounts for (q1 V q2 ).

7 1n the final paper, various other options for these two conjuncts will be examined. Instead of the first one, we might want to say that if we were told 0!, then we would believe (3, which need not be the same as believing ( 0! :::> (3) in the presence of defaults; instead of the second one, we might prefer saying for a given 1 that we do not believe ( 0! :::> 1) (to handle negative evidence), which for regular belief (see below) coincides with the above when 1 is D.

8 For some applications, we might wish to use a superset of this relation. For example, we might want to say that p -< q even though both are atomic, if we consider p to be much more likely than q. But we should never have to consider a subset of the relation.

This completes the knowledge-level characterization of abduction. The theorems to follow below (especially the relationship to the ATMS) are the best evidence that the definition is apt. But it is worth noting here how simple and general the account is. It is the first (to my knowl­ edge) that not only works for sentences f3 of arbitrary syntactic form, but is also sensitive to what is known without requiring an explicit list of the known sentences. In other words, it does not depend in any way on how the epistemic state e is represented (and so is truly at the knowledge level). Computations at the symbol level, of course, will need to operate on finite symbolic rep­ resentations of that state. Typically, for each type of belief A, there will be a function ~A that maps (finite) sets of sentences into epistemic states. At the symbol level, there will be a procedure of some sort that takes a representation of knowledge KB and a sentence f3 as ar­ guments, and produces a set of sentences by abductive reasoning. For an abductive procedure to be correct, the sentences it returns must express all and only the simplest explanations of f3 wrt the epistemic state rep­ resented by KB. Thus, what we will want to establish for various types of belief and associated computational procedures explain[KB, (3] is the following: 9

Note that for this general account, correctness does not require the sentences returned by the symbol-level pro­ cedure to be in a certain syntactic form, provided that they express the right propositions.

3 A generic abduction operation

Before looking at two specific types of belief, we define what it means for belief to be regular. In what follows, we use the following notation: x, y, and z stand for clauses, that is, finite sets of literals always understood disjunctively; the empty clause is 0; (x-y) is the clause whose literals are those in the set difference of x and y; x is the set of complements of the literals in x, now under­ stood conjunctively; :E and r stand for sets of clauses; for any :E, J.L:E is the set of smallest (in the sense of subset) elements of :E; and finally, CNF( a) is the set of small­ est clauses that result from converting a to conjunctive normal form, and analogously for DNF(a) .

Definition 6 A type of belief A is regular iff for every epistemic state, the following sentences of C* are true:

1. BA-.0;
2. (BAa V B>./3) ::J B>.(a V /3);
3. BA(a I\ /3) :> (B>.a A BA/3);
4. (B>.a A B>./3) :> BA(a A /3);

5. BAa = BAa*, if a* is a in CNF or DNF, or is the result of replacing any subformula f3 in a by /3*, where (recursively) BA/3 = BA/3* is always true. 10

We now define a very general operation on two sets of clauses (which we will eventually use for both types of belief below) as follows:

9 We use this font to indicate a symbol level procedure. 10 Note that this does not sanction replacing (3 by every­ thing logically equivalent to it.

This generalizes the MIN-SUPPORTS operation of [Re­ iter and de Kleer, 1987]: MIN-SUPPORTS(x,:E) = 'V(IMPS(:E),{x}), where IMPS(:E) is defined below. In­ formally, the elements of :E should be thought of as the clauses that are believed, the elements of r as the clauses to be explained, and 'V(:E, r) as the minimal explana­ tions. For instance, if

then 'V(:E, r)={(p4t\p6t\p7), (pst\p6t\P7), (pst\p7t\pg)}. That is, if we take one of these explanations, (p4t\p6t\p7 ), and assume that it and the elements of :E are true, we get that (Pl t\ P2) must be true, which implies that the clauses of r must all be true. The other two explanations work analogously. Note that (P4 t\ps) is not returned as an explanation since it is believed to be false, that is, its negation is an element of :E.

The important property of \1 is that although it only deals with clauses, it can be used to provide correct ab­ ductive reasoning for regular belief:

Proof: The proof depends on two key lemmas:

The final paper proves these and the theorem.

·

What this theorem establishes at a very abstract level is that for regular belief, it is sufficient to work with the set of clauses believed and the CNF of the sentence to be explained. This will immediately lead to two abductive procedures below.

4 Case 1: Implicit belief

The first notion of belief we consider is the "classical" one where beliefs are closed under logical consequence. Following [Levesque, 1984], we call this implicit belief and use B1 as the belief operator. An epistemic state for implicit belief can be modeled by any set of assignments, where we have the following:

If KB is a set of sentences, then ~1(KB ), the epistemic state represented by KB, is modeled by the set of all assignments that satisfy every element of KB. What is believed in this state is precisely what follows from KB, that is, if e = ~1 (KB ), we have that e f= B1a iff KB f= a. From this it follows that

which is precisely the account of explanation given by (among others) Poole in [Poole, 1988].

4.1 The ATMS

One abductive procedure that is receiving considerable attention is the ATMS [de Kleer, 1986]. Unfortunately, descriptions of the overall function computed by the ATMS have been largely in terms of how it goes about computing it. The first account that attempted to pro­ vide a lo~ical reconstruction was that of Reiter and de Kleer in [Reiter and de Kleer, 1987]. Although idiosyn­ cratic terms like labels, nodes, and nogoods are no longer part of the formulation, their definition is in terms of clause intersections and differences, notions that are ( ar­ guably) still best understood as symbol level manipula­ tions of sentences in a certain form. However, given their characterization, they are able to show the following:

Definition 8

Theorem 2 (Reiter and de Kleer) Given a set of Horn clauses :E and a letter p, the ATMS procedure is defined by atms[:E, p] = {(q1 t\ ... t\ q~:) I k 2: 0 and {ql, ... , ql:> p} E J-LIMPS(:E)}.

In fact, Reiter and de Kleer generalize the account of the ATMS to where the first argument is not necessarily Horn and the second argument is any clause. However, we can go even further by noting that

Using this as a pattern, we can define a generalized ATMS as follows: 11

Clearly this coincides with the ATMS specification when :Eisa set of Horn clauses and ,8 is a propositional letter. But what do these operations mean, and why should anyone care about them? The answer, we claim, is that the ATMS procedure correctly performs abduction for implicit belief:

Theorem 3 EXPLAIN1 [~I(:E), ,8] = II gatms[:E, ,BJII ·

Proof: It is not hard to show that implicit belief is regular, and we have that

The theorem then follows from Theorem 1. ·

However else it has been characterized in the past, this theorem establishes that an ATMS can be understood as computing all simplest explanations with respect to this type of implicit belief. Among other things, this guarantees that Poole's account of abduction (with the addition of the notion of simplicity defined here) also specifies the task performed by an ATMS.

5 Case 2: Explicit belief

The second notion of belief we consider is a variant of the one introduced in [Levesque, 1984] called explicit belief We use BE as the belief operator for beliefs of this type.

11 In the final paper, we will consider a very different way of generalizing the ATMS to handle arbitrary sentences.

The motivation behind explicit belief was to study a form of belief that was more computationally tractable than implicit belief, but remained defined in terms of truth conditions on the sentences believed. Since ~ sentence is implicitly believed if it comes out true at each element of a set of assignments (or alternatively, accessible possible worlds), it follows that implicit belief is closed under logical consequence. For explicit belief, instead of using assignments, we use situations, which can be taken to be total functions from the literals to {0, 1}, such that for every p, at least one of p or p is assigned to 1.12 We can think of assignments as those situations where s(p) = 1- s(p) for every letter p. But because not every situation is an assignment, we must define truth support recursively over sentences and their negations:

s I= p iff s(p) = 1; s I= --.p iff s(p) = 1;

s I= (a 1\ .B) iff s I= a and s I= .B;

s I=--.( a 1\ .B) iff s I= --.a or s I= --.,B;

s!=--.--.a iff sl=a.

An epistemic state for explicit belief is modeled by a set of situations where we have the following:

e I= BE a iff for every s E e, s I= a.

As in [Levesque, 1984], it is also useful to talk about the implicit beliefs of e:

As before, ~E(KB) is modeled by the set of all situa­ tions that satisfy every element of KB. What is explictly believed in such a state is not what logically follows from KB, but rather what is tautologically entailed by the KB (once tautologies are taken into account) in the sense of Relevance Logic [Anderson and Belnap, 1975, Dunn, 1976]. More precisely, if e = ~E(KB ), we have that e I= BEa iff KB u r tautologically entails a, where r is the set of all clauses of the form {p, p}.

5.1 Limited abductive reasoning

To establish what form of abductive reasoning is appro­ priate for explicit belief, we need something that will play the role that IMPs(.E) played for implicit belief:

Definition 10

The abductive reasoning we will use for explicit belief is the same as that performed by the ATMS, but using EXPS(.E) instead of IMPS(.E):

Definition 11 abd[.E, .8] = 'V(ExPs(.E), CNF(,B)).

To see the difference between this procedure and the ATMS, suppose that KB1 = {{q},{sVp},{pVqVr}}. In this case, atms[KB1, r]={r, s, {p 1\ q}}, so there are three simplest explanations for r wrt implicit belief; but abd[KB1, r]={r, {p/\ q}}, so sis not a simplest explana­ tion for r wrt to explicit belief. The difference is that whereas (s V r) is implicitly believed (since it follows from KB1), it is not explicitly believed. In other words, unlike the ATMS, abd[.E, .8] will not chain backwards to see what might explain ,8, and this is exactly what is required for explicit belief:

12 This restriction on situations was not present in [Levesque, 1984]. It has the effect of making explicit be­ lief similar to the knowledge retrieval of [Frisch, 1988] in that tautologies are always believed. This does not adversely af­ fect the desirable computational properties of explicit belief, since for (non-quantificational) CNF, tautologies can be de­ tected in linear time.

Theorem 4 EXPLAINE[~E(.E), .8] = II abd[.E, .8] II·

Proof: Like implicit belief, explicit belief is regular. Also we have that

The theorem then follows from Theorem 1. ·

This theorem establishes that abd[.E, .B] correctly calcu­ lates all simplest explanations with respect to this type of explicit belief.

But why should we care about a procedure that can­ not find some perfectly reasonable explanations that can be found by an ATMS? The problem is that we may have to wait too long for an ATMS to find them. This has caused researchers to look for parallel realizations of the procedure [Dixon and de Kleer, 1988]. But this is not just an ATMS implementation problem; the task it performs is inherently difficult: in general, there will be an exponential number of clauses to find, 13 and just deciding if {p, P} has any explanations at all is equiv­ alent to determining whether or not the set of clauses .E is satisfiable. So although (a parallel version of) the ATMS may work fine in many application areas, as a general-purpose mechanism for abductive reasoning, it has serious computational drawbacks.

On the other hand, just as explicit belief is easier than implicit belief when it comes to deductive reasoning, a similar result carries over to abductive reasoning:

Theorem 5 If KB is in CNF, there is an O(IKBI ·Ixl) algorithm for calculating abd[KB, x].

Proof: We use the fact that abd[KB, x] = {(y- x) 1 y E pEXPs(KB), x n y f:. 0} . We construct the answer as follows: cycle through the elements of pKB, and for each y that is not tau­ tologous and that has an intersection with x, put (y- x) into a set f. Then, for each mE x, put m into f, unless { m} E KB. Finally, return z for each z E pf. ·

So for single clauses anyway, abductive reasoning for ex­ plicit belief is considerably easier than abductive reason­ ing for implicit belief.

For arbitrary sentences ,8, the case is not so clear even if .B is in CNF. Although we can quickly calcu­ late abd[.E, x] for each clause x in ,8, putting the answers together involves converting a sentence into DNF:

Proof: The proof will appear in the final paper. ·

To see how this works, let KB2 be KB1 U {{aV b}, {cV b}} , where KB1 is defined above. Then abd[KB2, (r/\b)] can be computed by calculating Vabd[KB2 , r] (as above), which gives (rV(pAq)), then Vabd[KB2, b], which gives (aVbVc), and then conjoining and putting the result into DNF, which gives

13 ln an unpublished note, David McAllester shows that this remains true even when I:: is a set of Horn clauses.

The only potential difficulty here is calculating the DNF. When (3 has very few clauses, or when almost all of the abd[E, x] return fewer than 2 simplest explanations, the entire operation will be fast. But to guarantee that it will work well in all cases appears to require an even more restricted form of belief. 14

6 From explicit to implicit belief

One of the reasons for introducing explicit belief in [Levesque, 1984] was to specify a tractable deductive service for Knowledge Representation in terms of a set of beliefs which, unlike the implicit ones, could always be reliably computed. However, one difficulty with this whole approach is how exactly to go beyond what is ex­ plicitly believed. When deliberately trying to solve a problem (in what is called puzzle mode in [Levesque, 1988]), it is necessary to combine beliefs and follow through on their consequences in a controlled and sys­ tematic way. If all that is available at the knowledge level is a way of finding out if something is explicitly believed and a way of finding out if something is im­ plicitly believed (in one very large unsupervised step), there is nothing the agent can do to begin exploring in a controlled way the implications of what is explicitly believed. For instance, the agent cannot simply perform theorem proving over what is known without access to the sentences at the symbol level used to represent that knowledge.

With a limited abduction operation, on the other hand, there is a way of moving under the control of the agent from the explicit beliefs towards the implicit be­ liefs. To find out if a sentence (3 is implicitly believed, the procedure (roughly) is this: first find out if (3 is explicitly believed; if it is, then exit with success; otherwise, calcu­ late the full (explicit) explanation for (3; if there is none or it is trivial, then exit with failure; otherwise replace (3 by the explanation, and repeat. In other words, the pro­ cedure deals with the following questions, starting with some (3°: according to what is believed,

is (3° true? what would it take for (3°

is (3 2 true? etc.

This "backward-chaining" procedure terminates when it either finds something that is believed or fails to find a non-trivial explanation. Each step in this procedure is tractable, 15 and the agent can exit the loop if it seems to be taking too long relative to the importance of the original question. More formally, we have the following:

14 It appears that a type of belief that is regular except for condition 4, closure under conjunction, does the trick here, but this needs further investigation.

15 Strictly speaking this is not true because of the DNF problem noted in the previous section. I suspect, however, that the procedure will also work for the more restricted no­ tion of belief, but this has yet to be established.

Definition 12 For any epistemic state e and any (3 from C, a sequence of sentences P:, k = 0, 1, 2, ... is defined by (3~ = (3 and (3:+ 1 = VEXPLAINE[e, pk].16

Proof: The proof is based on the following:

Lemma 7.1 lfE is satisfiable, Enr = 0, and there exists a linear set-of-support resolution refutation of E u r I with r as the set of support, then e F BEak where e = ~E(E), a= Vfx I x E r}, and k is the depth of the refutation tree.

In the final paper, we prove this lemma and the theorem. ·

So a sentence is implicitly believed iff it is accounted for ultimately by something that is explicitly believed.

To see this in action, let KB3=KB2 U {{s}, {a V c}}, where KB2 is defined above, and let e=~E(KB3), the epis­ temic state represented by KB3. Although ( r 1\ b) is not explicitly believed in state e, it is implicitly believed and so should be derivable. First we set (3° to (r 1\ b), and compute (3 1 = EXPLAINE[e ; (3°] = abd[KB3 , (3°], which is

as presented above for KB2 . Putting this into CNF, we get { { aVbVc}, { qVr}, {pVr}} . 17 Notice that the first two clauses of (3 1 are already explicitly believed by KB3. Now calculate {3 2 = EXPLAINE[e, {3 1 ] = abd[KB3 , (p V r)j = {r,p,s}. But then (3 2 is explicitly believed (since sis), and so we are done. Notice how the iterative procedure works its way back to s the way an ATMS would, but now in bite-sized pieces under the control of the agent. 18

This theorem thus has the following perhaps surprising conclusion: we can determine if something is a logical consequence of what is (explicitly) believed without ever getting access to the set of sentences that are believed. We need only be able to ask for any specific sentence two questions: is it believed? and if not, what would be sufficient to account for it, according to what is believed?

The theorem also provides for the first time a knowledge-level account, that is, an account that is inde­ pendent of how knowledge is symbolically represented, of how a limited notion of belief can be extended systemati­ cally to include all of its logical consequences. It also sug­ gests a knowledge-level account of how an agent's beliefs could be made to evolve deductively over time: starting with some beliefs in some state e0 , the agent would be­ lieve a in state ek+l iff he believed an explanation of a in state ek . 19 With a deductive architecture of this form, we would have that a sentence was implicitly believed iff at some point in the future it would be explicitly be­ lieved. Interestingly enough, to represent at the symbol level the epistemic state ek, it is not necessary (though certainly sufficient and perhaps desirable) to use a set of sentences KBk (calculated from some initial represen­ tation KBo). We might just as well represent the state ek by a pair of symbols <KBo, k>, since this pair also determines whether or not ek I= BEa, for any a. One nice property of our knowledge-level characterization is that it does not commit us to representing what is known using a set of sentences.

16 We are abusing notation here in treating the result of EXPLAIN as a set of sentences.

17 In practice, one would not want to iterate an abductive procedure that takes the trouble of putting its answer into DNF, since the next step of the iteration requires an argu­ ment that is in CNF.

18 Similar iterative techniques, we suspect, will lead to a procedure for full (implicit) abductive reasoning, as a con­ trolled alternative to the ATMS itself.

7 Conclusion

There are a number of questfons left open by this re­ search: how should nested beliefs be handled? What about quantified beliefs? Is there indeed (as hinted above) an account of limited belief that leads to tractable abduction for any sentence and yet can be iterated to produce all implicit beliefs? Can explicit abduction be used to produce implicit abduction?

On another front, one possibility suggested by this work is a new deductive operation. If abductive rea­ soning asks "what would tell you that [J is true," we might also consider asking "what would a tell you," and expect to find a simplest sentence (or a set of them) that captures what a adds to what is believed. This would be very useful information when doing "what-if'' exper­ iments, for example. In the medical domain, we could ask what we should expect to see if hepatitis were present and get jaundice as the only (non-trivial) answer. This is just the dual of abduction, and the two operations should be interdefinable. Indeed, the appropriate defini­ tion appears to be something like --, VEXPLAIN >. [ e, ·a].

8 Acknowledgements

I have been mulling over the ideas presented here for some time. I wish to thank Jim des Rivieres, Greg McArthur, and Calvin Ostrum for general discussion on this topic, Bart Selman for exploring the complex­ ity issues, Syd Hurtubise for the specious reasoning, and Ron Brachman, Russ Greiner, Gerhard Lakemeyer, Joe Nunes, Ray Reiter and Rick Sobiesiak for commenting on an earlier draft. But I especially want to thank Ray Reiter and Johan de Kleer for writing the first ATMS paper I could get a real handle on.