AILP: Abductive Inductive Logic Programming

1 Introduction

It is often argued that the use. of- a subset of- first or­ der logic as a representation language situates Inductive Logic Programming (ILP) at the intersection of Logic Programming and Machine Learning. The research in ILP is concerned with the derivation of logic programs from (positive and negative) evidence in the presence of background knowledge. Characteristic for this approach is the use of induction, i.e., a form of synthetic reasoning that infers general laws from observations. [Muggleton and De Raedt, 1994] reviews theoretical results, imple­ mented systems and practical applications in this area. Two major problems tackled in ILP are predicate learn­ ing and theory revision. The former is concerned with the induction of rules for an undefined or partially de­ fined predicate from examples, whereas the latter con­ cerns the updating of a theory (a logic program) when it is inconsistent with newly incoming information. Proto­ type systems are - amongst others - the predicate learn­ ers MIS [Shapiro, 1983], FOIL [Quinlan, 1990], GOLEM [Muggleton and Feng, 1990], CLINT [De Raedt, 1992], and the theory revision systems RX [Tankitvanitch and Shimura, 1992], KR-FOCL [Pazzani and Brunk, 1991] and RUTH [Ade et al., 1994].

In the area of Logic Programming (LP) abduction has been recognized as an important form of non-monotonic reasoning. It is a form of synthetic reasoning, which - as opposed to induction - infers explanations for ob­ served facts, according to known (general) laws. Abduc­ tion has been shown useful for fault diagnosis [Charniak and McDermott, 1985], planning and temporal reason­ ing [Denecker et al., 1992] and knowledge assimilation [Kakas and Mancarella, 1990], and it has also been suc­ cessfully applied in Intensional Knowledge Base U pdat­ ing approaches such as [Bry, 1990], [Kakas and Mancar­ ella, 1990] and [Guessoum and Lloyd, 1990]. A critical survey on the extension of logic programming to perform abductive reasoning can be found in [Kakas et al., 1993].

In this paper we argue that both abduction and in­ duction are different, yet related forms of reasoning on incomplete knowledge. They are both forms of hypothet­ ical reasoning and attempt to "complete" the knowledge by proposing additional hypotheses. However, they dif­ fer in the sort of hypotheses.

According to the "declarative semantics", a logic pro­ gram can be seen as a set of definitions for a number of concepts. This interpretation is already present in Clark's work on completion semantics [Clark, 1978]. Un­ der Clark's interpretation, a program consists of a set of possibly empty definitions for all predicates; predi­ cates are defined by enumerating exhaustively the cases in which they are true. Under this interpretation, a prob­ lem with the use of logic programs for knowledge repre­ sentation, is that an expert needs to provide complete definitions for all predicates. In many applications, such complete information is not available. A natural solution is to extend the logic program formalism such that only a subset of the predicates is to be defined while other predicates can be left undefined. In addition, partial knowledge about these undefined predicates can be given using FOL axioms. The role of these FOL axioms is in­ timately tied to the representation of uncertainty: when a number of concepts cannot be defined, then other, less precise information may be available which can be rep­ resented as a set of assertions. E.g., if the predicates father/1 and mother/1 are declared as being undefined, the axiom mother(X} V father(X} +- parent(X} expresses the weaker partial knowledge that it cannot be the case that someone is a parent without being a mother or a father.

The actual procedures for "completing" incomplete knowledge developed in the ALP and ILP area, are - as to be expected- quite different. The ALP approaches construct hypotheses in the form of ground facts for the undefined predicates. These facts are seen as the de­ scription of a scenario that explains a given observation. As opposed to this, ILP systems in general - even in case of a specific-to-general search - disallow facts. The hypotheses they generate are sets of rules that express general - scenario independent - information on the un­ defined predicates. As such an ALP approach is appro­ priate when the expert has great confidence in his general knowledge, but wants to find a concrete explanation for an observation. On the other hand, an ILP approach is more appropriate when the expert searches for general rules that compact the positive and negative evidence, and that later can be reused to classify new examples.

A first step towards inte_gration of techniques from both domains was taken by lDe Raedt and Bruynooghe, 1992]. De Raedt and Bruynooghe argue that- when re­ formulated within a logical framework- both intensional knowledge base updating and predicate learning are in­ stances of the belief updating problem. As a proof for this claim they present an adapted version of Shapiro's MIS system in which techniques from both parent do­ mains are integrated. These ideas were later further elaborated and implemented in the theory revision sys­ tem RUTH [Ade et al., 1994].

The contribution of our work is that we reformulate the ALP and ILP approaches as instances of a generic version of Bry's framework [Bry, 1990] for intensional knowledge base updating. In doing so we show that there is a clear relationship between inductive and abductive reasoning. Moreover, this setting enables us to intro­ duce inductive reasoning into an abductive schema, thus resulting in a setting which one could call Abductive In­ ductive Logic Programming (AILP) . As an example we transform a typical abductive procedure, namely SLD­ NFA into a new procedure SLDNFAI (SLDNFA-with­ Induction) by enhancing it with a general-to-specific pro­ cedure for inducing clauses. Furthermore, this enhance­ ment could also be beneficial for the ILP approach, since SLDNFA is a procedure for normal clauses, whereas the ILP setting used to be restricted to definite clauses.

This paper is organized as follows. In Section 2 we introduce a generic framework that formalizes different forms of hypothetical reasoning on incomplete knowl­ edge. In Section 3 we map both the ALP and ILP ap­ proaches to this framework, and discuss the similarities and differences. In Section 4 we elaborate an abductive procedure for ILP, by introducing inductive reasoning into the abductive procedure SLDNFA. Finally, in Sec­ tion 5 we formulate our conclusions.

2 Problem formalization

Intuitively one can outline the problem of handling in­ complete knowledge as follows. Given is a logic program P, which is declaratively read as the description of the problem domain. One part of this program is regarded as being correct, the other part is regarded as incom­ plete. Also given is evidence E, containing requirements for a logic program Pnew . The aim is to find such a Pnew that satisfies all the restrictions imposed by E.

A logic programs P consists of a finite set C(P) of program clauses, a set U(P) of predicate names, namely those predicates that are not or only partially defined by clauses in C(P), and a finite set of First Order Logic (FOL) axioms T(P). The declarative semantics of P is given by the classical logic theory comp{P) = GET U T(P) U {p <---- B I p <---- B E C(P) and p E U(P) } U { compdeft..p, C(P)) I p (/. U(P)}. Here GET denotes Clark's equality theory and compdeft..p, C(P)) denotes the completed definition of the predicate p in C(P) [Clark, 1978]. GET expresses that two different terms represent different objects. compdeft..p, C( P)) expresses that if p <--­ B is in C(P) and B is true, then pis true, but also vice versa, if p is true then for at least one (instance of a) rule p <---- B of C(P), B is true. Note that for undefined or partially defined predicates, the rules in C( P) are not completed. £(P) denotes the language of P, i.e., the set of all well-formed formulas using predicates and functors in P.

A logic program P is said to be consistent iff comp(P) is a consistent FOL theory. We say that a logic program pis consistent w.r.t. a set of well-formed formulas :F c £(P) iff comp(P)u:F is a consistent FOL theory. Finally, if F E £( P) is a well-formed formula, P F= F means comp(P) F= F.

To formalize hypothetical reasoning, we use an adapted version of Bry's framework [Bry, 1990]. We rely on a meta-predicate new for expressing the evidence E, i.e., for expressing statements that describe the desired logic program Pnew. E.g., the constraint new(mother(x)) V new(father{x)) <---- parent(x) states that in Pnew all parents should also be mothers or fathers.

According to [Bry, 1990] P and Pnew can be viewed as two distinct logical theories, and a declarative expres­ sion of an update of P resulting in Pnew is a finite set of logical formulas defining Pnew in terms of P. The set of well-formed formulas Lnew ( P) is defined as an exten­ sion of L{P ). The base of this set consists of the well­ formed formulas of £{P) and the formula new(F), where FE £{P ), and this set is closed under negation, logical connectives and the quantifiers V and :3. Definition 1 formalizes the notion of evidence E to transform a logic program p into a logic program p new .

Definition 1 Evidence E to transform a logic program P into a logic program Pnew is a set of closed formulas FE~ Lnew{P) \ £{P). D

Requiring that Pnew satisfies all restrictions imposed by E is formalized to the requirement that Pnew F= E. Finally, in Figure 1, we formalize the problem setting.

In [Bry, 1990] a non-Horn theory N for the meta­ predicate new is defined in terms of operations on the object program facts and clauses. In Definition 4 we give a 'generic' version of this theory, in that we re­ placed the actual operations on the object program by the predicates evaLpos_atom and evaLneg_atom that are to be instantiated. The rules rely on a meta-predicate clause that ranges over the clauses of C(P) defining the predicates that are not in U(P). More specifically, de­ fine Clause(P} as the meta-program consisting of facts clause(A <----B) for each rule A<---- Bin C(P) and offacts undefined( A) for all atoms A containing a predicate of U(P).

Definition 2 An update of a logic program P is a set of expressions of the form evaLpos_atom(A) or evaLneg_atom(A) where A is an atom. 0

Definition 3 Let P be a logic program and U an update of P. The procedure update is a function that maps P and U to a logic program, such that the following correctness criterion is fulfilled 1 :

• ·update(P, U) FA if evaLpos_atom(A} E U

·update(P, U) F ·A if evaLneg_atom{A) E U

We define the logic program Pu as the result of the call update(P, U). D

Definition 4 The theory N for 'new'

where A denotes an atomic formula in .C(P), F and G de­ note formulas in .C(P), and R is a conjunction of atoms with z a free variable. 0

The if-parts of the equivalences can be viewed as a meta-program for new. They recursively distribute new over quantifiers and logical connectives. Once new ap­ plies to atoms, it is evaluated on the object program facts and clauses. The equivalences can be viewed as the completion [Clark, 1978] of this meta-program for new. Since negation in new occurs only at the object level and not in the meta-language, this theory correctly defines new. The following proposition is analogous to the one found in [Bry, 1990] .

Proposition 1 Let P be a logic program, U an update of P and FE .C(P).

1 As usual T f= A with A an open atom is to be interpreted as T f= V(A).

3 Abduction versus Induction

In this section we discuss the ALP and ILP approaches in terms of the generic problem setting of Figure 1 and the rewrite rules for the meta-predicate new.

3.1 ALP

In general, abductive reasoning is concerned with the construction of explanations for observations using gen­ eral laws. These explanations are expressed in terms of a predetermined set of predicates, called abducible pred­ icates. Moreover, most ALP approaches require the ex­ planations to be a set of ground facts. First, this restricts the number of possibilities, and second, in ALP one is in­ terested in constructing a concrete scenario rather than general rules. As a consequence updates of a logic pro­ gram P are restricted to removing and inserting ground facts for the abducible predicates.

In the formalization of the previous section this means that ALP regards the logic program P as having a fixed part, consisting of C(P) and T(P), and the set U(P) containing the names of the abducible predicates. All of C(P) belongs to the complete part; the incomplete part defining the predicates of U(P) is empty. Once evidence E is given, it is translated into operations on the abducible predicates.

The general idea of an abductive approach is captured by the rules (l)ALP and (2)ALP·

The effect of the meta-predicate abduce operating on the program P is that the atom A is added to the pro­ gram as (part of) the definition for the abducible predi­ cate. The meta-predicate avoid_unification has as effect that it continuously constrains the atom A so that it can­ not unify with any ofthe abduced atoms. Note that both predicates abduce and avoid_unification are still generic in the sense that they do not give any exact procedural information. Every abductive system implements these predicates in its own particular way.

3.2 ILP

In general ILP approaches are concerned with the deriva­ tion of logic programs from positive and negative evi­ dence in the presence of background knowledge. In most systems evidence is a set of positive and negative exam­ ples of predicates for which no or only incomplete defini­ tions are given. We will call these predicates inducible. ILP aims at constructing general rules that define the in­ ducible predicates, since one is interested in compacting the knowledge represented by the positive and negative examples. Furthermore, one wants to be able to reuse the induced rules for the classification of unknown ex­ amples.

In the formalization of Section 2 this means that the background knowledge is a part of C(P). It is the fixed part of P that is correct and complete, and that can be used as a logic program. U(P) is the set of in­ ducible predicates. C( P) can contain clauses for these inducible predicates. However, these clauses are only an incomplete (or incorrect) definition. The evidence E can be written as new(p1 1\ ... 1\ Pmp 1\ --ml/\ ·nm,.) with {Pb ... , Pmp}, resp. {n1, ... , nm,.}, the set of positive, resp. negative examples given for the inducible predi­ cates. Finally, Pnew should be such that Vi, 1 :::; i :::; 771.p: Pnew f= Pi, and Vj, 1:::; j:::; m,..: Pnew ~ n;.

The rules (l)rLP and (2)rLP capture the general idea of the ILP way of implementing the predicates eval_pas_atam and evaLneg_atam.

A call to the meta-predicate induce has the following effect. First it is checked whether there is a clause in C( P) that covers the atom A 2 · If this is the case, noth­ ing needs to be done. Else, a clause is constructed that covers the atom A and that is consistent with the nega­ tive evidence seen so far. We formulate the requirements for such a clause only in a very general way, since each approach has its own particular way of implementing the induction of a clause. For example in a specific­ to-general approach one would start with a most spe­ cific clause, which can then later be generalized, whereas a general-to-specific approach would rather construct a most general clause covering the example and consistent with the negative evidence.

The meta-predicate refine is called when a negative example is covered by one or more clauses in the par­ tial definitions for the inducible predicates. In that case these clauses are refined, i.e., made more specific, such that they no longer cover the negative example. Making a clause more specific is usually done by adding one or more literals to its body, although this is not the only way to implement refine. E.g., MIS [Shapiro, 1983] just removes the whole clause, and if necessary, replaces it later by a more specific clause.

3.3 Discussion

Taking a closer look at the rules (l)ALP, (2)ALP, (l)rLP and (2)rLP' one can see some important similarities in the reasoning mechanisms of the ALP and ILP ap­ proaches. Consider for example the rules (!)ALP and (l)rLP· The first disjunct of the right hand side looks very much the same: reduction of a goal via resolution with a clause of P . The main difference of course lies in the second disjunct of the rules, namely in the meta­ predicates abduce and induce. The meta-predicate ab­ duce reasons on the level of ground facts, whereas the meta-predicate induce is concerned with definite Horn clauses. However, there still is a certain analogy in these predicates. induce first backtracks over the possibly in­ complete definition of the inducible predicate, and only if the atom is not covered a new clause in induced. Most abductive systems realize abduce by just inserting the atom as a new fact, but there exist more sophisticated abductive approaches that also first backtrack over the already abduced atoms, and only abduce a new fact when unification fails.

2 A clause C covers an atom A if P U { C} f= A.

Notice that an analogue duality can be found in the rules (2)ALP and (2)rLP · The first conjunct of the right hand side expresses that once a negative atomic goal unifies with the head of a clause, the instantiated body should not be true in Pnew . The second conjunct ex­ presses what should be done when the negative goal con­ tains a predicate p of U(P) . The difference between the ALP and the ILP approach lies in the fact that in ALP one must avoid unification with the abduced atoms for the predicate p, whereas in ILP one must avoid coverage by the (induced) clauses for p.

4 SLDNFAI : an abductive procedure for ILP

In this section we consider the abductive procedure, SLDNFA [Denecker et al., 1992], and show that replacing the reasoning on the level of ground facts by an induc­ tive reasoning schema, transforms it into an inductive procedure, which we call SLDNFAI.

4.1 SLDNFA

The SLDNFA procedure of [Denecker and De Schreye, 1992] is an abductive procedure for normal abductive programs. The procedure is a natural extension of SLDNF-resolution and incorporates both abduction and negation as failure. The major strengths of the algorithm are that it is able to handle both positive and negative goals, and also its way of treating non-ground abductive goals. The procedure starts with an (incomplete) logic program and a query ?- q. that should succeed. SLD­ NFA produces a set b. C Lnew 3 such that camp( P + b.) f= q, where P +b. = C(P) U b. and U(P +b.) = 0. In SLDNFA both I(P) and I(P +b.) are empty. In terms of the formalization of Section 2 SLDNFA handles the following problem:

Given:

• a logic program P = (C(P),U(P),I(P)), with U(P) the abducible predicates and I (P )=0.

· evidence E = { new( q) +- } 4

Find:

a logic program Pnew = P + b. with b. a set of ground facts such that camp( P + b.) F= q

Basically the SLDNFA procedure proves an initial goal by constructing a set pg of goals that must succeed and a set .Ng of goals that must fail. SLDNFA tries to re­ duce goals in pg to the empty goal D, and tries to build finitely failed trees for the goals in .Ng. We explain how the rules (l)ALP and (2)ALP are implemented. We start with the predicate abduce that handles the case where A is selected in a positive goal. SLDNFA solves this - via backtracking - by resolving A against all abduced atoms and finally, by skolemizing A - replacing all of its variables by skolem constants - and adding the re­ sult to D.. In order to solve problems with unification with skolem constants, classical unification is extended. In a first phase, extended unification treats skolem con­ stants as variables; in a second phase, it skolemizes the terms bound to the original skolem constants. This is illustrated in Example 1.

3 Note that in SLDNFA the alphabet of Cnew is extended with a set of skolem constants skt, sk2, ....

iNote that this is just the query ?- q. formulated using the meta-predicate new.

Example 1 Consider the fact p(f(g( Z), V)) +- and the query +- r(X), p(X) where r is an abducible predicate. Consider the following partial derivation {selected literals are underlined):

When solving the positive goal +- p( sk) with p(f(g(Z) , V)) +- 1 SLDNFA replaces sk by f(g(skt), sk2 ) and returns D. = {r(f(g(sk!), sk2 ))}. D

The predicate avoid_unification, which handles the case where an abductive atom A is selected in a neg­ ative goal Q, is more complex. One must compute the failure tree obtained by resolving the goal with each of the abduced atoms in D.. A problem is that the final D. may not be totally known when A is selected. SLDNFA solves this by interleaving the computation of the failure tree with the construction of D.. This is implemented by storing for each negative abductive goal the triplet ( Q, Aq, Dq) where Q is the negative abductive goal, Aq is the abductive atom selected in Q, and Dq is the set of abduced atoms that have been resolved with Q. When a new fact is abduced, the stored goal is retrieved and is resolved with the new fact .

Finally, SLDNFA has a special negative unification procedure for handling the case where skolem constants occur in negative goals. We will not go into detail on this procedure. We just mention that it produces expressions of the form sk =F term as constraints on the generated solutions.

In [Denecker, 1993] the SLDNFA procedure is formal­ ized and it is proven to be sound w.r.t . completion se­ mantics: comp(P +D.) f= q. As a completeness result it is proven that if the computation terminates, then SLD­ NFA generates at least all minimal solutions.

4.2 A simple inductive procedure

We design a simple inductive procedure which can be seen as prototypical for a general-to-specific incremen­ tal ILP approach to predicate learning. In terms of the formalization of Section 2, our procedure handles the fol­ lowing problem:

Given:

· a logic program P = (C(P),U(P),I(P)) where U(P) are the names of the unknown predicates and I(P) = 0 · evidence E = new(/\7:; 1 Pi 1\ /\j.; 1 n; ), where the Pi are the positive examples and n; the negative examples Find:

a logic program Pnew = P U 7-l such that P U 7-l f= E 5

6 Note that in a classical ILP setting P U 1t under FOL semantics should entail the positive examples and should be consistent with the negative examples. When P U 7-l is a

As representation language we use functor-free, linked Horn clauses. The procedure starts with an empty hypothesis 7-l and handles the examples incrementally. Clauses in 7-l are represented as couples of the form (c,coverage), where Cis a clause and coverage is the set of positive examples encountered so far that are cov­ ered by c. The clauses of C(P) defining predicates of U(P) are considered to belong to 7-l . Their coverage is initialized to the empty set. We use a set JV to store the negative examples handled so far.

We now specify how the predicates induce and refine are implemented in our inductive procedure. The predi­ cate induce is called when a positive example is encoun­ tered. When it is already covered by one or more of the clauses in 7-l, it is added to the coverage of each of these clauses. When the example is not covered by the current 7-l, a most general clause is constructed that covers the example, and does not cover any of the negative exam­ ples in JV. The actual construction of such a clause goes as follows. The procedure starts with a clause with an empty body, and with as head a variabilized version of the positive example. This very general clause is then gradually refined until it does not cover any of the nega­ tive examples in the current JV. Refining a clause is done either by unifying two distinct variables, or by adding a literal to the body. The arguments of this literal should be distinct variables, with at least one variable in com­ mon with the original clause. The predicate can be any predicate of P.

The meta-predicate refine is called for handling a nega­ tive example. If the example is covered by one or more clauses in 7-l, each of these clauses is refined such that it no longer covers the negative example. Next it is checked for each of these refined clauses which examples in their coverage are no longer covered. The examples that are no longer covered by any of the clauses in 7-l are then again added to E.

4.3 Introducing induction m SLDNFA : SLDNFAI

The basic idea is to maintain the overall structure of the SLDNFA procedure and to replace the abduction of the set of ground facts D. by the induction of a set of clauses 7-l using the inductive procedure of Section 4.2. For doing so, we will consider positive abductive goals as positive examples, and negative abductive goals as nega­ tive examples 6 . The set 7-l is initialized with the clauses of C(P) defining predicates of U(P), with an empty cov­ erage for each of these clauses. As in SLDNFA we use sets pg and Ng to store positive and negative goals. For a positive abductive goal, SLDNFAI extends 7-l - if necessary- with a new clause that is consistent with the negative examples encountered so far. These negative examples are stored in the set JV. Interleaving the com­ putation of the failure tree for a negative abductive goal and the construction of the set D. is replaced by refin­ ing 7{ each time a new negative example is encountered. We clarify this idea by illustrating SLDNFAI on a small example.

definite program, this is equivalent with P U 1i under least Herbrand Model semantics entails both the positive and the negated negative examples.

6 A positive, resp. negative, abductive goal is an atom for an abducible predicate, selected in a positive, resp. negative, goal.

Example 2 Consider the following fault diagnosis prob­ lem for lamps.

1. lamp(h) <­
2. lamp(b) <-

(3) conn_to_battery(h ,bl) <­ (4) conn_to_battery(b,b2) <- ( 5) faulty _lamp( X )<-lamp(X ),conn_ to_empty _battery(X, Y) (6) conn_to_empty_battery(X,Y) <- conn_to_battery(X,Y) (7) empty(b1) <- (8) false<- conn_to_empty_battery(X,b2) Initial query : ? - faulty _lamp(h ), ·false.

The predicate conn_to_empty _battery is inducible. Nate that this implies that clause (6) is not necessarily com­ plete and correct. The following enumeration describes how SLDNFAI operates in order to make the initial query succeed. In each step we indicate the operation and the updated datastructures.

1. initialization PC}= {faulty_lamp(h ), ·false }, NCJ=0, N=0, H={ ( conn_to_empty _battery(X,Y) <-conn_to_bat­ tery(X,Y),0)}
2. re&olve faultyJamp{ll} with clau&e (5) PCJ={lamp(h ), conn_to_empty_battery(h ,Y), -,false }, NCJ=0, N =0, H={( conn_to_empty _battery(X,Y) <-conn_to_battery(X,Y),0)}
3. re&olve lamp(h) with clau&e (1) PCJ={conn_to_empty_battery(h,Y), -,false}, NCJ=0, N =0, H={( conn_to_empty _battery(X,Y) <-eonn_to_ battery(X,Y),0)}
4. conn_to_empty_battery(ll, Y) i& a po&itive example. Rewlution with clau&e (6) and clau&e (3) in&tantiate& the variable Y to b1. conn_to_empty_battery(h,bl) i& put in the coverage of clau&e (6) . PCJ={ -,false }, NCJ=0, N =0, H={( conn_to_empty _bat­ tery(X,Y) <- conn_to_battery(X,Y), { conn_to_empty _battery(h, b1)})}
5. &witch ·fal&e to negative goal PCJ={D}, NCJ={false}, N=0, 1-l={( conn_to_empty _battery(X,Y) <-conn_to_bat­ tery(X,Y),{ conn_to_empty _battery(h ,b1)})}
6. rewlve fal&e with clau&e (8) PCJ={D}, NCJ={ conn_to_empty _battery(X,b2 )}, N =0, H={ ( conn_to_empty _battery(X,Y) <-conn_to_bat­ tery(X, Y), { conn_to_empty _battery(h , b1)})}
7. conn_to_empty_battery(X,b2) i& a negative example. Re&olution with clau&e (6) and clau&e (3) in&tantiate& X to l2. H need& to be refined mch that conn_to_empty_battery(l2,b2) i& no longer covered. Thi& can be done by adding the literal empty(Y) to the body of the clau&e in H.

PCJ={D}, NCJ={D}, N ={ conn_to_empty _battery(b, b2 )}, H={( conn_to_empty _battery(X,Y) <- conn_to_bat­ tery(X, Y),empty(Y),{ conn_to_empty _battery(h, b1)})}

The result is that SLDNFAI has induced the clause conn_to_empty _battery(X,Y) <- conn_to_battery(X,Y), empty(Y) for the predicate conn_to_empty _battery. 0

Let us for the sake of comparison discuss how SLDNFA would have operated on the same exam­ ple. First, SLDNFA would not take into account clause (6), since it assumes that initially there is no definition for the abducible predicates. The first three steps in example 2 stay the same for SLDNFA. In step 4 however, SLDNFA would abduce the atom conn_to_empty_battery(h,skl), with sk1 a skolem con­ stant, and add it to D. . Step 5 and 6 stay the same as for SLDNFAI, but step 7 is again different. Since conn_to_empty_battery(X,b2) is a negative abduc­ tive goal, unification with conn_to_empty_battery(l11 sk1) should be avoided. Therefore SLDNFA adds the con­ straint sk1 # b2 . The result is that SLDNFA has ab­ duced that lamp h has an empty battery sk1 which is different from b2 ·

Which of both solutions - i.e., the one produced by SLDNFA or the one produced by SLDNFAI - is prefer­ able of course depends on the actual problem situation, i.e., whether one is interested in general rules, or in a concrete scenario.

Finally, we want to make two important remarks con­ cerning SLDNFAI. First, we claim that in a "degener­ ate" case, SLDNFAI reduces to the inductive procedure of Section 4.2. Indeed, when SLDNFAI is given as ini­ tial query the conjunction · of all positive and negative examples, it will behave as the inductive procedure we described, and produce a set of clauses that covers all the positive examples, and none of the negative examples.

And second, we claim that by using the SLDNFA ap­ proach, SLDNFAI provides an elegant way of extending ILP approaches to handle normal clauses. The use of completion- as in SLDNFA- allows to extend the covers relation in a straightforward way to cope with negated atoms in the body of clauses. This approach was also taken by [Taylor, 1993] in their extension of a particular generalization operator, nl. absorption, towards normal clauses in an inductive learning context. Moreover, since SLDNFA can cope both with positive and negative goals, it functions in a very natural way as an example gen­ erator for both positive and negative examples for the inducible predicates, as can be seen in Example 2.

5 Conclusions

In this paper we have made the link more clear between ALP and ILP. We have argued that both induction and abduction are different, yet related forms of hypothetical reasoning on incomplete knowledge. On the one hand, abductive procedures complete this incomplete knowl­ edge by hypotheses containing ground facts. Such a solution is appropriate when one has confidence in the available general laws, and one is interested in finding a concrete scenario that explains certain observations. On the other hand, inductive procedures produce gen­ eral rules to complete the incomplete knowledge. This is interesting in case one is interested in compacting the positive and negative evidence, and in later reusing the rules for classifying new examples.

Borrowing ideas of Bry's setting [Bry, 1990] for inten­ sional knowledge base updating, we have developed a generic framework that formalizes the problem of completing incomplete knowledge. In this framework a declarative expression of an update of a logic program P resulting in a logic program Pmw is a set of logical for­ mulas using a meta-predicate new that applies on atoms and negated atoms. A set of rewrite rules translates these formulas into operations on the object level pro­ gram.

Next, we mapped our framework both to the ALP and ILP approaches. In doing so, more light is shed on the relationship between abduction and induction. As an illustration we considered the abductive procedure SLDNFA of [Denecker and De Schreye, 1992]. We refor­ mulated this procedure as an instantiation of our generic approach and showed that this enabled us to replace in a straightforward way the abduction of ground facts by a general-to-specific procedure for inducing clauses. We call the resulting procedure SLDNFAI, i.e., SLDNFA ex­ tended with induction. Finally, we claim that this en­ hancement of SLDNFA can also be beneficial for the ILP approach, since SLDNFA works with normal program clauses, whereas ILP is restricted to definite clauses.

As a general conclusion we can say that our paper has established a clear relationship between ALP and ILP. We pointed out that it is worthwhile transferring results and techniques from one domain to the other. E.g., ILP could benefit from formal and theoretical re­ sults obtained in ALP, whereas ALP could benefit from inductive techniques to alleviate the restriction to abduc­ ing only ground facts. We are convinced that the first promising results achieved in this paper suggest that fur­ ther research on this issue can lead to interesting results.

Acknowledgements

We wish to thank Maurice Bruynooghe, Gunther Sablon and Luc De Raedt for their comments on earlier versions of this paper, and for the inspiring discussions. Research for this paper was partially supported by the Esprit Bra nr.6020 (ILP). We are also grateful to the anonymous reviewers for their encouraging comments.