Prediction is Deduction but Explanation is Abduction

1. Introduction

Temporal reasoning involves both prediction and explanation. Prediction is projection forwards from causes to effects whilst explanation is projection backwards from effects to causes. That is, prediction is reasoning from events to the properties and events they cause, whilst explanation is reasoning from properties and events to events that may have caused them. Although it is clear that a complete framework for temJ?Or.al reasoning should provide facilities for solving both pred1ct10n and explanation problems, prediction has received far more attention in the temporal reasoning literature than explanation.

Frequently, outside of the temporal reasoning literature, ~xplanat10n.problems are seen as deductive. Domain knowledge 1s captured m a theory T, the effects that require explanation are represented by a set of sentences L1, and the causes of L1 are amongst the logical consequences G such that T v L1 I= G. For e~ample, in Mycin. a set of rules T relates symptoms to diseases. Each rule 1s roughly of the form cause if effect. The symptoms are represented by L1 and the disease which causes

those symptoms is a logical consequence of T v L1.

~yci~ rules look rather peculiar, since they invert the relat10nsh1p between cause and effect. This is because Mycin treats explanation as deduction rather ::han abduction. This kind of "compilation" of causal laws into inverted implications is counter-intuitive and is not always appropriate or possible. Furthermore, a set of Mycin rules is no good for predicting what symptoms are caused by a given disease, even though intuiti.vely it is clear that if the rules ir. T adequately capture the domam, they should be equally good for both prediction and . explanation.

This confusion of explanation with deduction is possible

Prediction is Deduction but Explanation is Abduction

Murray Shanahan Imperial College Department of Computing, 180 Queen's Gate, London SW7 2BZ. England.

not onl.Y with Mycin's shallow sort of causal reasoning, but also w1th temporal reasoning in general, in which time is represented explicitly. Domain knowledge is captured in a theory T, events and properties are represented by a set of sentences L1, and amongst the logical consequences G such that T v L1 I= G are both predictions and explanations. That is, G represents projections both forwards and backwards from L1.

An alternative and more natural approach is one in which prediction is deductive but explanation is strictly abductive. Causal laws are captured in a theory T, and each law has the more intuitive form effect if cause. For prediction, a set of events is represented by a set of sentences L1, and the task is to find the causal consequences of L1 by finding the logical consequenc~s G such that Tv L11= G. For explanation, events and propert1es are represented by G, and the task is to find sets of events L1 which could have caused G, in other words, to find L1's such that T v L1 I= G. The same theory T is used for both prediction and explanation .

. In combination with the assumption that all properties wh1ch .are known to hold must be explained by events, the abductive approach deals correctly with default persistence. Suppose we are told that a property p holds at timet] . In order to apply default persistence to conclude that it still holds at a later time t2, we postulate through abduction the occurrence of an event e before t] which initiates p. In other words, it is necessary t? explain why p holds at t]. Then default persistence can be apphed to show that the property p persists from the time of e through t] and through t2.

This paper presents the abductive approach to explanation and shows how it deals with default persistence. To illustrate this approach I introduce a shortened form of the Event Calculus of Kowalski and Sergot [1986], which is similar to thatyre~~nted in [K.owalski, 198?1· To demonstrate its practical reahsab1hty, I descnbe an abductive mechanism which is related to the techniques of Finger and Genesereth [1985] and Cox and Pietrzykowski [ 1986], and is a simplif.cation of the mechanism described by Eshghi [19881, tailored for the shortened form of the Event Calculus.

2. The Event Calculus

In Kowalski and Sergot's Event Calculus [1986] and its variants [Kowalski, 1986], the ontological primitives are events, ~hich initiate and terminate periods during which properties hold. The Horn clause subset of the Predicate Calculus is used, augmented with negation-as-failure. The Event Calculus used in this paper is a simplified version of that given by Kowalski and Sergot [198fi]. Only two clauses are necessary, as follows .

The formula holds-at(P,T) represents that property P holds at timeT. The formula happens( E) represents that the event E occurs. The time of event E is named by the term time( E). Times are ordered by the usual comparative operators, but for brevity I will sometimes write E instead of time( E) in expressions involving temporal ordering. The formula initiates( E ,P) represents that the event E initiates a period during which property P holds, and terminates(E,P) represents that the event E terminates any ongoing period during which property P holds. The not operator is interpreted as negation-as-failure. The use of negation-as-failure in Axiom (1.1) gives a form of default persistence.

The formula clipped(E,P,T) represents that there is a possible mapping of events onto time points in which the property P ceases to hold at some time between event E and time T. The use of negation-as-failure in the definition of clipped ensures that holds-at works correctly even when events and times are only partially ordered and this mapping is not fully known.

Part of the domain theory is captured in a set of initiates and terminates clauses. For example, the Blocks World is described by the following clauses. The term on(X,Y) names the property that block X is on top of block Y or at location Y, and the term clear(X) names the property that block or location X has nothing on top of it. The term move(X,Y) names the event or act type of moving block X onto block or location Y.

To simplify examples, these clauses do not account for th_e preconditions of events, such as the need for X to be clear tf move(X,Y) is going to have any effect. If n~cessary, preconditions can easily be incorporated by addmg extra conditions to the bodies of initiates and terminates clauses, or can be expressed as integrity constraints [Eshghi, 1988].

The importance of supplying a clear semantics for formulations of default persistence has been demonstrated by Hanks and McDermott [ 1987]. The example here has a clear semantics because Axioms (1.1) to (2.4) are stratified and therefore have a unique standard model [Apt et al., 1988], [Przymusinski, 1988]. But note that Axiom (2.2) ha~ a. holds-at in its body. If a terminates clause had a holds-at m tts body, then we would no longer have stratification, because holds-at is defined in terms of terminates via a negation, and terminates would be defined in terms of holds-at. Such cases are quite likely to arise. Intuitively, it is clear that this does not cause a problem because of the partial ordering of the ~vents .. To sho_w this formally, we need to perform a constructiOn whtch I wtll sketch briefly. Each terminates clause defined in terms of holds­ at is folded up with Axioms (1.1) and (1.2) giving a replacement clause of the form

This can be replaced by a set of clauses, one for each pair of times t],t2 in the Herbrand universe such that fJ < t2, of the form

Since times are ordered, any set of such clauses is locally stratified [Przymusinski, 1988], and accordingly has a clear semantics. So, for example, the Yale shooting problem can be formulated by a simple set of initiates and terminates clauses, without the attendant semantic problems described by Hanks and McDermott [1987].

In fact, using negation-as-failure, the correct handling of not holds-at in all cases requires some extensions, since holds­ at can fail simply because the ordering of events and times is not known. There is a distinction between necessarily-holds-at, meaning that holds-at is true in all possible orderings of times and events, and possibly-holds-at, meaning holds-at is true in some possible ordering of times and events. Likewise there is a distinction between possibly-clipped and necessarily-clipped. The existing definitions are for necessarily-holds-at in terms of not possibly-clipped. But a symmetrical definition is required for possibly-holds-at in terms of not necessarily-clipped. _Then, we write not possibly-holds-at where we would previously have written not holds-at, meaning that holds-at fails in all possible orderings of events. To make all this clear would require considerable further discussion, and to incorporate the extensions in this paper woulc;l only make the examples more confusing, so I won't mention the 1112.tter again.

3. Prediction and Explanation

The Event Calculus as described can be used to solve prediction problems, that is problems of reasoning from causes to effects, through deduction. The domain is captured by a theory T which includes a set of initiates and terminates clauses and other causal laws as well as the Event Calculus Axioms ( 1.1) and ( 1.2). A particular history of events is represented by a set L1 of happens and temporal ordering clauses. Then, the properties which hold as a consequence of these events are represented by the set G of atomic holds-at clauses which are logical consequences of T v ..1. In other words prediction is

determining members of G where Tv ..11= G.

The domain theory Tis strictly causal in the sense none of its rules is of the form cause if effect. The intuitive and correct way to express the relationship between causes and effects is with the implication the other way around. Rules of the form cause if effect, like those used in Mycin, are almost invariably false, since a given effect usually has many potential causes. Only in particular domains is it possible to assume that there is a unique cause for a given effect, and even then expressing causal laws as inverted implications is counter-intuitive.

However, this begs the question of how explanation, that is reasoning from effects to causes, is to be done. It is tempting to add further clauses to facilitate explanation, possibly of the cause if effect form criticised above. But this temptation should be resisted. If the theory T adequately captures the relationship between causes and effects it should be equally good for both prediction and explanation. It is important to recognise that explanation can be done through abduction with the same theory. Suppose we are given the theory T and we wish to find possible histories of events L1 which would explain a set of properties G expressed as holds-at clauses. Then we wish to find L1's such that Tv ..11= G, and this is abduction.

We can be a bit more precise about what sorts of L1 constitute good explanations. First, L1 should describe a history of events. So it should contain only atomic happens, act and temporal ordering clauses. Second, it should be minimal in the sense that there should not be a .1* such that .1* c L1 and T u L1* I= G. There can, of course, be many minimal L1's. A third criterion for a good explanation is that it should postulate the fewest events possible. This suggests a preference relation on L1's such that L\1 is preferable to L12 if it contains fewer happens clauses. Of course, there may still be many equally preferable minimal L1's. Clauses which appear in all L1's for a given G can be thought of as the defeasibly necessary conditions for G. They are only defeasibly necessary since the addition of new causal laws to T could render G explicable in other ways. Each separate L1 is a set of defeasibly sufficient conditions for G. They are only defeasibly sufficient, because of default persistence - the addition of further events to L1 could mean that G is no longer explicable by L1.

4. Persistence

This section shows how default persistence is handled by the abductive approach to explanation. Suppose we are told that property p holds at time t]. In the absence of any further information, what inferences may we reasonably make about a time t2 after t}? The usual notion of default persistence which licenses the inference that p still holds at t2, and which is built in to the Event Calculus as well as many other formalisms, is based on two epistemological assumptions and one metaphysical assumption. First, it is assumed that no events occur other than those which are known to occur. Second, it is assumed that no types of event can affect a given property other than those which are known to do so. Third, it is assumed that properties do in fact persist until something happens which affects them.

Incorporated into the framework presented here is a fourth assumption; that every property which is known to hold has an explanation in terms of events. The conclusion that p holds at t2 is derived partly through deduction and partly through abduction. An event is postulated to explain why p holds at t], which initiates p and which occurs before tJ, and then default persistence is applied to conclude that p still holds at t2. Suppose that the domain theory T comprises Axioms ( 1.1) to (2.4), that we have a set of axioms L1 which represents a history of events, and that we are told that block a is at location x at timet]. So we have

This fact is not added directly to the set of axioms L1 and used to predict new consequences G such that T u L1 I= G. Rather, since it is a holds-at fact, it requires explanation. So it is added to the set of theorems G, and suitable L1's must be sought through abduction which rebalance the sequent T u ,11= G. We do not wish to extend the domain theory, so L1 must contain only happens, act and temporal ordering axioms. For this example all such L1's include three axioms of the following form.

In the absence of further axioms, these plus Axioms (1.1) to (2.2) allow us to conclude the default persistence of the property on(a,x) through timet] and through any time t2 after t]. The new constant e is invented by abduction to name the event it has postulated. The only thing known about the time of this event is that it is before tJ. If such an event were already a part of L1 then it would not of course be necessary to add anything to L1.

Suppose that in addition to (4.1), we are also told that the block a is at location y at time t3 which is after t]. So we have

Let us be clear how default persistence should behave with this information. In general, if we are told that a property holds at a time t], we assume that it still holds at any later time t2 unless we have reason to believe that it changes some time between t} and t2. But in this case, we know that at some time between t] and t3 the block ceases to be at location x and starts to be at location y. In fact, since we do not know when between t} and t3 this change occurs, it is not reasonable to conclude anything about whether the book is on the table or the shelf at any given point between these times. This problem is analogous to Kautz's "stolen car" problem [Kautz, 1986], and many approaches to default persistence do not deal with it correctly. For _example, with Shoham's logic [Shoham, 1988], default pers1stenc~ postpones change until as late as possible, and it is then a logical consequence of the information in ( 4.1 ), (6.1) ~nd (6.2) that the block is still at location x immediately before time tJ.

The approach to default persistence proposed here does not suffer from this problem because of its insistence that every property that holds has an explanation in terms of events. Others have proposed similar solutions using deduction [Morgenstern and Stein, 1988], [Lifschitz and Rabinov, 1988]. But using abduction, rather than adding (4.1) and (6.1) to the set of axioms L1, they are added to the set of theorems G. This leads to the rebalancing of the sequent T u L1 I= G via the abduction of axioms (5.1) to (5.3) to explain (4.1) as described above, and also the abduction of the following four axioms to explain (6.1).

With the addition of (7.1) to (7.4) to L1, because the relative ordering of e' and t2 is not known, default persistence no longer licenses the conclusion that holds-at( on( a,x),t2). Axioms (7.1) to (7.4) will be present in any L1 which explains G, and can be thought of as the necessary conditions for G given T. A more complicated example might yield many L1's, and each such L1 is a set of (defeasibly) sufficient conditions for G given T.

Unlike many formulations of persistence, that presented here works forwards only. Suppose again that we are told that property p holds at time tJ. In the absence of any further information, what inferences may we reasonably make about a time to before t]? The three assumptions which license the default inference that p still holds at a time t2 after tJ do not apply to a time before t] . With the additional assumption that properties require explanations, we conclude that some event must have occurred to initiate p. But we have no idea when that event occurred - it may have been before or after to. So there is no reason to suppose that p holds at to. The correct way to deal with persistence is to ensure that it works forwards only.

5. The Abductive Mechanism

The abductive approach to explanation can be realised using a mechanism which is a straightforward extension of SLD resolution. Let us consider SLD resolution first. Given a set of definite clauses T and a goal clause f-Go, an SLD refutation of f-Go is a sequence of goal clauses f-Go .. . f-Gn where f-Gn is the empty clause and each f-Gi+l is obtained from f-G; by resolving one of its literals with one of the clauses in T. In a Prolog interpreter, the leftmost literal is always selected. Since there may be many clauses in T which can be resolved with the selected literal, a space of possible refutations is defined, which may be searched, for example, depth-first by a simple chronological backtracking procedure. Now suppose that there is some f-G; whose selected literal g will not resolve with any clause in T. Usually this means that sequences beginning with f-Go .. . f-G; are not worth exploring. But if we are searching for a set of unit clauses L1 such that TuL1FGo, then clearly by letting L1 include a unit clause which resolves with g, we can continue the search with f-Gi+l equal to f-G; minus the literal g. This suggests the following extension to SLD resolution.

A subset of the predicate symbols mentioned in T are designated as the abducib/es. A literal whose predicate symbol is abducible is also called abducible. To find a set of unit clauses L1n such that TuL1nFGo and L1n mentions only abducibles, a refutation of the form f-Go ,L1o . .. f-Gn,L1n is constructed, where each f-G; is a goal clause, each L1; is a set of unit clauses mentioning only abducibles, f-Gn is the empty clause, L1o is the empty set, and each f-Gi+l ,L1i+l is obtained from f-G;,L1; as follows. If g, the selected literal of f-G;, can be resolved with one of the clauses in T, then a single resolution step is taken as described above and ..1;+1 is L1;. If g is abducible and cannot be resolved with any clause in T, then Gi+l is G; minus g and L1i+l is L1; plus the unit clause g'f­ where g' is g with all its variables replaced by skolem constants [Cox and Pietrzykowski, 1986]. If g were not skolemised, all the variables in g'f- would be universally quantified, which would make it unnecessarily strong. Its variables only need to be existentially quantified for it be resolvable with g. The accumulated set of unit clauses L1n is called the residue.

The basic mechanism can be extended to cope with negation-as-failure (Eshghi and Kowalski [1988] and Poole [1988] discuss the use of abduction as a general framework for default reasoning). This is essential to cope with default persistence in the Event Calculus. Suppose that the selected literal of the current goal clause is not g. The usual negation-as­ failure method is adopted, and not g is assumed to be true if g cannot be proved with the current residue. But later in the refutation, additions to the residue can make g provable. Accordingly, it is necessary to record all negated assumptions, and whenever new clauses are added to the residue, these assumptions must be rechecked. This is a potential computational bottleneck, but some form of incremental mechanism could be used to minimise this [Sadri and Kowalski, 1988], [Shanahan, 1987]. The negated assumptions that are recorded can be thought of as part of the residue, and rechecking them is like checking for consistency with an implicit integrity constraint. As with abducible literals, all the variables in a recorded negated assumption are replaced by skolem constants.

A further complication arises with nested negation-as­ failure. Suppose that there is a clause of the form g f- not h' and that h' is not provable with the current residue. Then an attempt to prove not g using SLD resolution with negation-as­ failure will fail because it is not possible to prove h'. Yet it might have been possible to render h' provable by adding further clauses to the residue. So rather than using SLD resolution to try to show h', abduction is used instead and is allowed to add to the residue. This procedure can be generalised to any level of nesting - SLD is used at even levels and­ abduction is used at odd levels.

This general abductive mechanism can be specialised for the Event Calculus axioms above. Any goal of the form happens (E), act(E,A) and Tl < T2 is abducible. The initial goal clause is of the form f-holds-at(PJ,TJ), .. . , ho/ds-at(Pn,Tn), and the procedure is then the same as above. Of course, a complete search space for a given G may contain many L1's, as indeed there may be many possible explanations for G. By ordering the branches of the search space appropriately, the simplest explanations -those which postulate the fewest events- will be generated first. One heuristic for extracting the simplest explanations first is to reuse old skolem constants rather than generating new ones. For example, if the residue contains

act(s,move(a,b)), and the goal clause is f-act(E,move(a,b)), .. . , where s is a skolem constant, then the simplest way of resolving away the act literal is just to bind E to s, rather than to postulate another event and · add another act clause to the residue. Later on though, this binding may lead to a failing branch of the search, in which case backtracking takes place and a new event has to be postulated after all. A similar case arises if a skolem constant has already been created, but can be eliminated later. For example, suppose the residue contains act(e,move(s,b)) and the goal clause is f-act(e,move(a,b)) . The

simplest way to resolve away the act literal this time is to replace all occurrences of the skolem constant s by a, rather than adding a new act clause to the residue. Again, later failure may mean that backtracking undoes this decision. In general, explanations can be generated in order of simplicity by abandoning a depth-first search strategy in favour of one which explores branches which don't postulate new events first.

Let us consider a trivial example of this mechanism applied to explanation. Given Axioms (2.2) to (2.4) for the Blocks World, suppose that we require an explanation for the fact that holds-at(on(a,x),tO). The search space for this example is shown in Figure 1. Abduction generates the residue L1'={happens( el), act( el ,move( a,x)), el <tO}.

The next example is more complicated and illustates most of the features of the mechanism I have described. Suppose that we are given that tO<tl and tl <t2, and we want an explanation for holds-at( on( a,x),tO) and holds-at( on( a,x),t2) and holds­ at( clear(x),tl ). This is an extension of the previous example, and the search space in Figure 2 would be appended to the one above if the extra goals were added. It is assumed that the residue already contains L\', and the overall residue is L1 = L\' v L1 ".

When abducing an event to explain holds-at(on(a,x),t2), the mechanism has the option of supposing that it is the same event as the one it has already postulated el, or of postulating a new event e2. This gives rise to two branches in the search space. Furthermore, el does initiate the property on( a,x) and does occur before t2, and it cannot yet be shown that clipped(el,on(a,x),t2). But when, in order to explain holds­ at( clear(x),tl ), an event e3 has to be postulated which initiates clear(x), clauses are added to the residue which make it possible to show that clipped(el,on(a,x),t2), and this gives rise to a failure. The mechanism backtracks and explores the second branch of the search space, which succeeds with the overall residue L\={happens(el), act(el,move(a,x)), el<tO, happens(e2), act(e2,move(a,x)), e2<t2, happens(e3), act(e3,move(a,l)), e3<tl, e3<e2, el <e3}. The skolem constant l represents an. unspecified location, and could later be replaced by the name of a reallocation. Note that if the goals had been presented in a different order, then the first branch might not have been explored. Also, if the goal holds-at( clear(x),tl) were not included then the first branch of the search space would succeed with the simplest explanation, postulating only the event el to explain both of the other holds-at goals. The solution of the last not clipped goal shows how extra constraints on temporal ordering can be generated even within a negation. Without the addition of the clause el <e2, it would have been possible to prove clipped(e3,clear(x),tl).

6. Concluding Remarks

Finger and Genesereth [1985] describe an extension to resolution which is similar to the mechanism presented here, but have applied it to design synthesis rather than temporal reasoning. Cox and Pietrzykowski [ 1986] also describe a related technique. Eshghi [1988] has applied abduction to temporal reasoning, specifically to planning, using a form of Kowalski and Sergot's Event Calculus which is very different from their original formulation. His approach employs meta­ level integrity constraints to represent preconditions for actions as well as to handle default persistence, and uses an elaborate mechanism to cope with explicit equalities which are generated in place of the usual implicit bindings generated by a resolution system.

The approach taken in this paper is to use stratification semantics for negation-as-failure, and to use negation-as-failure to give default persistence. Abduction is used only for explanation. Eshghi and Kowalski [1988], however, present an abduction semantics for negation-as-failure itself, and Poole [ 1988] also presents an abductive framework for default reasoning. This suggests that both persistence and explanation could be done in a purely abductive framework, but this possibility needs further investigation.

Morgenstern and Stein [1988] and Lifschitz and Rabinov [1988] tackle a similar problem to the one addressed in this paper, the former using model preference and the latter using circumscription. The relationship between the three approaches is not yet clear and warrants further study.

A prototype of the system described has been implemented in Prolog. This has highlighted the need for a more sophisticated control strategy than that provided by simple chronological backtracking, since the system spends much time exploring possible explanations which are clearly ridiculous, and often loops in subtle and unexpected ways.

Acknowledgements

Thanks for discussion and inspiration to Kave Eshghi, Marek Sergot, Sury Sripada, Vladimir Lifschitz, Bob Kowalski and Chris Evans.