Abducing Priorities to Derive Intended Conclusions

1 Introduction

In commonsense reasoning, it is important to represent and reason about preference in order to reduce non­ determinism due to incomplete knowledge. To represent such knowledge about preference, it is required that pri­ orities among commonsense knowledge are to be found out. For example, to get the desired result of the Yale shooting problem [Hanks and McDermott, 1987], an ade­ quate priority should be expressed according to our com­ monsense. The essence of this problem can be repre­ sented by the following extended logic program, P, where ab1 and ab2 are abnormality predicates, loadedi and alivej denote that the gun is loaded at the time T; and the turkey is alive at the time Tj, respectively. We also assume that some unknown action wait is done at T0 , and that the shoot action, which causes the turkey dead whenever the gun is loaded, is done at T1 .

Chiaki Sakama

Dept. Computer and Communication Sciences Wakayama University Sakaedani, Wakayama 640-8510, Japan sakama@sys.wakayama-u.ac.jp

Here, not denotes negation as failure, and (1) and (2) represent the inertia of actions. Without any priority information, we do not know which default of (1) or (2) should take precedence. Then, to the contrary of our intention that ·alive2 should be inferred, neither alive2 nor ·alive2 is decided from the above program. In fact , there are two answer sets of P , one including loaded1, ab2, ·alive2 (intended), and the other contain­ ing alive2, ·loaded1, abl.

Historically, the Yale shooting problem revealed the so called multiple extension problem. In this case, we should decide which ab1 or ab2 must have a higher priority for minimization. Using prioritized circumscription [Lifs­ chitz, 1985], for example, the criterion can be manually given for the Yale shooting problem that ab1 should be minimized with a higher priority than ab2 in order to de­ rive ·alive2 . Other than circumscription, recent devel­ opment in the field of logic programming and nonmono­ tonic reasoning has provided a number of mechanisms for freely specifying preference on multiple extensions in default reasoning. Such prioritized reasoning systems include prioritized default logics and prioritized logic programs [Brewka, 1994; Baader and Hollunder, 1995; Dimopoulos and Kakas, 1995; Sakama and Inoue, 1996; Brewka and Eiter, 1998]. For the Yale shooting problem, we would like to prefer the default (1) to (2), and then a higher priority is given to (1) in these frameworks.

Although the Yale shooting problem is so simple that we can find the proper priority manually, it becomes more complicated and difficult to find priorities among many complex default knowledge in the real world's com­ monsense reasoning. Hence, a framework and a method for automatic finding of such priority information are highly required.

In this paper, we provide a framework for finding pri­ orities as a part of a prioritized logic program [Sakama and Inoue, 1996] in order to derive an intended conclu­ sion as a theorem of the logic program. To this end, we introduce the notion of preference abduction, which infers a sufficient priority relation to make the intended conclu­ sion hold. This inference is in fact a form of abduction, i.e. , abduction of meta-knowledge which is preference in this case. We further provide an integrated framework of abduction, in which both literals and priorities can be abduced. Using such an abductive framework, we can infer skeptical explanations of an observation even when only credulous explanations are obtained due to non-determinism of a given abductive program.

There are many applications of nonmonotonic reason­ ing that require to find out priorities among conflicting rules. For example, in the legal domain, priorities among the conflicting laws are oft~n required for disputants to derive their desired conclusion, which give them the ad­ vantage in the argumentation of a court . The proposal in this paper enables us to derive a desired conclusion by abducing appropriate priorities in such cases. An in­ teresting application is preference view, which transfers a given priority relation among observations into a priority relation among base abducible literals.

This paper is organized as follows. Section 2 intro­ duces the theoretical background in this paper. Sec­ tion 3 provides the framework for preference abduction. Section 4 goes on elaborating on preference abduction. Section 5 discusses related work, and Section 6 is the conclusion. Due to the lack of space, we will omit proofs of propositions and theorems in this paper.

2 Background

2.1 Extended Logic Programs

An extended logic program (ELP) [Gelfond and Lifschitz, 1990] is a set of rules of the form

where L/s (0 :::; i :::; n ; n 2: m) are literals. Here, the left-hand side La is called the head of the rule (3), and the right-hand side is called the body of the rule. The head is possibly empty. A rule with an empty body is called a fact, and each fact L +- is identified with the literal L . Two kinds of negation appear in a program: not is the negation as failure (NAF) operator, and ..., is classical negation. Intuitively, the rule (3) can be read as: if L1, ... , Lm are believed and Lm+l, ... , Ln are not believed then La is believed.

The semantics of an ELP P is given by the answer set semantics [Gelfond and Lifschitz, 1990], which is defined by the following two steps. Let Cp be the set of all ground literals in the language of P, and let S ~ Cp. First, let P be a not-free ELP (i.e., for each rule m = n). Then, S is an answer set of P if S is a minimal set satisfying the conditions:

1. For each ground rule La +- L1, ... , Lm from P, {L1, ... , Lm} ~ S implies La E S.
2. If S contains a pair of complementary literals L and ·L, then S = Cp .

Second, let P be any ELP and S ~ Cp. Then, define a not-free ELP p S as follows : a rule

is in P 5 iff there is a ground rule of the form (3) from P such that { Lm+l, . .. , Ln } n S = 0. For p s, its answer sets have already been defined. Then, S is an answer set of P if S is an answer set of p s .

The class of ELPs is a subset of Reiter's default logic [Gelfand and Lifschitz, 1990]. An answer set of an ELP P is consistent if it is not C p. P is consistent if it has a consistent answer set. An ELP P (skeptically) entails a literal L, written as P f= L, if L is included in every answer set of P. On the othe!hand, P credulously infers L if L is included in an answer set of P.

2.2 Abductive Logic Programs

An abductive (extended) logic program (ALP) is a pair ( P, r) , where P is an ELP and r is a set of literals from the language of P. The set r is identified with the set of ground instances from r , and each literal in r is called an abducible. The model-theoretic semantics for ALPs is given in [Inoue and Sakama, 1996]. A set S ~ Cp is called a belief set of ( P, r) if S is a consistent answer set of P U A for some A ~ r . Note that belief sets reduce to consistent answer sets when r = 0.

Let 0 be a ground literal called an observation. A ~ r is an skeptical explanation of 0 ( wrt ( P, r)) if PUA f= 0 and P u A is consistent. On the other hand, A ~ r is a credulous explanation of 0 ( wrt ( P, r ) ) if there is a belief set S of ( P, r) such that 0 E S and S is a consistent answer set of P U A. A skeptical/credulous explanation A of 0 is minimal if no A' C A is a skeptical/credulous explanation of 0 .

In an ALP ( P, r ), each abducible in r is a literal. Often however, we would like to introduce rules of the form (3) with n 2: m 2: 1 in r . Such a rule, called an ab­ ducible rule, intuitively means that if the rule is abduced then it is used for inference together with background knowledge P. This extended abductive framework is in­ troduced in [Inoue, 1994] as a knowledge system. Any knowledge system ( P, r), where both P and r are ELPs, can be translated into an ALP ( P', r') where r' is a set of literals [Inoue, 1994]: For each abducible ruleR in r , a new naming atom 8 R is associated with R, and let

2.3 Prioritized Logic Programs

A reflexive and transitive relation ~ is defined on C p. Each e1 ~ e2 is called a priority, and we say e2 has a priority over e1. We write e1 -< e2 if e1 ~ e2 and e2 ~ e1. When x and y are tuples of variables, e1(x) ~ e2(y) stands for any priority e1 ( s) ~ e2 ( t) for any instances s of x and t of y.

A prioritized (extended) logic program (PLP) by [Sakama and Inoue, 1996] is given as a pair (P, <I>), where P is an ELP and <I> is a set of priori ties on C p. 1 The declarative semantics of PLP is defined using the answer sets. Given a PLP (P,1>), suppose that 51 and 52 are two distinct answer sets of P. Then, S2 is preferable to S1, written as S1 ::; S2, if for some element e2 E S2 \ S1, (i) there is an element e1 E 51\52 such that e1 ::; e2, and (ii) there is no element e3 E S1 \ S2 such that e2 -< e3. Here, the relation ::; on answer sets is also defined as reflexive and transitive. Note that the condition (ii) is automatically satisfied if there is no priority chained on more than two different elements (i.e., e1 ::; e2 ::; e3 im­ plies either e1 = e2 or e2 = e3). An answer set S of P is called a preferred answer set (or p-answer set, for short) of P ( wrt 1>) if S ::; S' implies S' ::; S for any answer set S' of P.

1 In [Sakama and Inoue, 1996], a PLP (P, <I>) is defined with a general extended disjunctive program P, which allows NAF and disjunctions in heads of rules, and <I> may contain NAF formulas. Here, we consider a subset of their PLPs.

By definition, (P, 1>) has a p-answer set if P has a finite number of answer sets. In particular, the p-answer sets of (P, 1>) coincide with the answer sets of P when 1> = 0. It is also clear that if a program P has the unique answer set, it also becomes the unique p-answer set of ( P, 1>) for any 1>. We say ( P, 1>) entails a literal L, written as P 1=~ L, if L is included in every preferred answer set of P.

Using PLPs, we can represent preference knowledge naturally, and it is helpful to reduce non-determinism in logic programming. Moreover, various forms of common­ sense reasoning such as (prioritized) minimal abduction, (prioritized) default reasoning, and prioritized circum­ scription can be realized in terms of PLP. In particu­ lar, the mapping from prioritized circumscription of any clause set to a PLP is given in [Sakama and Inoue, 1996], which much extends the previous translation into a strat­ ified logic program by Gelfond and Lifschitz [1988].

3 Preference Abduction

In this section, we introduce preference abduction, which is the process of abducing priorities to explain given ob­ servations.

3.1 Basic Framework

Given an ELP P and a literal 0, we first consider the case that 0 is credulously inferred by P but is not skep­ tically entailed by P. In this case, there exists a multiple extension problem, that is, both answer sets containing 0 and answer sets not containing 0 coexist . Let AS+ be the set of answer sets containing 0, and As- the set of answer sets not containing 0. A direct way to prefer answer sets containing 0 is to construct priorities between answer sets in As+ and As-, so that some sub­ set of AS+ are made the set of preferred answer sets of P. However, there are many ways to associate priorities between AS+ and As-. Hence, we assume the existence of some set \lf of pre-specified candidate hypotheses for priorities in the following abductive framework.

Definition 3.1 Let P be a consistent ELP, and 0 a literal. Suppose that \lf is a set of candidate priorities on Lp. A set '1/J of priorities is a (skeptical) explanation of 0 ( wrt ( P, \lf ) ) if

Also, '1/J is a minimal explanation of 0 if no '1/J' C '1/J is an explanation of 0.

Given a pair ( P, \lf) for preference abduction, let 51 and 52 be two distinct answer sets of P. Then, in order to find priorities '1/J from \lf such that sl ::; 52 holds, one should select a literal e1 E 51 \ 52 and another literal e2 E S2 \51 such that (i) e1 ::; e2 and (ii) for any literal e3 E S1 \ S2, e2 -/, e3, i.e., e2 ::; e3 implies e3 ::; e2.

Example 3.1 Suppose that the ELP P is given as

and \lf = {p ::; q, q ::; p}. There are two answer sets of P: 51= {p, o} and 52= {q, ·o}. Suppose we want to find an explanation of o. Abducing the priority q ::; p, we get the relation 52::; 51 , hence P F{q~p} o.

Example 3.2 (Yale shooting) Consider the ELP Pin­ troduced in Section 1. The candidate hypotheses for this problem can be supplied as \lf = {ab1::; ab2, ab2::; ab1}. Then, {ab1 ::; ab2} is the explanation of ·alive2 . This abduced priority corresponds to our commonsense that the abnormality wrt the shoot action should be stronger than that wrt the wait action.

3.2 Combining with Credulous Abduction

When an observation 0 cannot be credulously inferred by P, the basic framework in Section 3.1 cannot give a sufficient explanation of 0. In such a case, we can combine preference abduction with ordinary abduction in Section 2.1 so that 0 gets a skeptical explanation. An extended abductive framework is given as follows.

Definition 3.2 A preference abduction framework is a triple ( P, r, \lf ), where P is an ELP, r ~ Lp is a set of abducibles, and \lf is a set of candidate priorities on L p. A pair (A, '1/J) is a (skeptical} explanation of a literal 0 ( wrt ( P, r, \lf ) ) if

1. A~ r,

1. '1/J ~ \lf'
2. P U A is consistent, and
3. PUAj=.pO.

Also, (A, '1/J) is a minimal explanation of 0 if for any explanation (A', '1/J') of 0, A' ~ A and '1/J' ~ '1/J imply A' = A and '1/J' = '1/J.

Note that the basic framework of preference abduction in Section 3.1 is a special case of Definition 3.2, where r = 0. Moreover, the traditional ALP framework in Sec­ tion 2.2 is also a special case, where \lf = 0. We can also consider an abductive framework ( P, r, \lf) in which r is a set of abducible rules and \lf includes priorities on such abducible rules. In that case, a naming technique simi­ lar to the one in Section 2.2 can be applied to abducible rules, and then priorities among rules are translated into priorities among rule names, thereby reducing such an abductive framework to that in Definition 3.2.

Example 3.3 Let us consider the abductive framework ( P, r , Ill), where

There are four belief sets of ( P, r): S1 = { q}, S2 = {a,p}, S3 = {a,q}, S4 = {a,b,p,·q}. Then, both E1 = ({a} , {q ::; p}) and E2 = ({a, b}, 0) are the min­ imal explanations of p. In fact, P U {a} F{qjp} p and P U {a, b} I= p. For E1 the p-answer set of P U {a} is S2, while S4 is the unique answer set of P U {a, b} for E2.

Note in the above example that explanations are ob­ tained either from credulous explanations with abduced priorities or from skeptical explanations wrt the given ELP. Hence, a naive procedure to compute preference abduction is as follows.

Procedure 3.1 PrefAbd(P,r, IJ!,O,E)

Input: a preference abduction framework ( P, r, Ill),

a literal 0 (observation) .

Output: a skeptical explanation E of 0 wrt ( P, r, Ill ) .

1. Compute a credulous explanation A of 0 wrt (P,r);
2. If A is a skeptical explanation of 0 wrt ( P, r), then return E = (A, 0);
3. Otherwise, compute the answer sets of P U A; As+ := the set of answer sets containing 0; As- := the set of answer sets not containing 0;
4. Find priorities 'lj; ~ Ill and P-AS ~ AS+ such that T::; S for any S E P-AS and any TEAs-; Then, 'lj; is an explanation of 0 wrt ( P U A, Ill); Return E = (A,'Ij;).

In Procedure 3.1, computing credulous explanations of 0 at Step 1 can be realized by existing abduc­ tive procedures such as [Kakas and Mancarella, 1990; Inoue and Sakama, 1996]. At Step 2, each credulous ex­ planation A is checked to see whether it is skeptical or not . This test can easily be realized by checking the con­ sistency of Pu Au { +-- 0 }. At Step 3, the answer sets of P u A or belief sets of ( P, r) can be computed by some bottom-up procedures, e.g., [Inoue and Sakama, 1996]. At Step 4, it can be shown that: if 'lj; is an explanation of 0 wrt ( P u A, Ill), then (A, 'lj;) is an explanation of 0 wrt ( P, r, Ill). Hence, the next theorem holds.

Theorem 3.1 Procedure Pref Abd(P,r, Ill, 0, E) is sound. That is, if it terminates, its output E is a skeptical explanation of 0 wrt ( P, r, Ill).

The completeness of Procedure 3.1 holds for a ground ELP P and finite r and Ill if we assume (i) the existence of an abductive procedure that is complete for comput­ ing credulous explanations at Step 1, and (ii) the exhaus­ tive search for finding 'lj; at Step 4. However, since many existing abductive procedures are designed to compute credulous explanations, it is more difficult to compute skeptical explanations directly. In fact, the skeptical ex­ planation {a, b} of p wrt ( P, r) in Example 3.3 cannot be obtained by top-down abductive procedures in general. In this sense, to compute skeptical explanations of an observation, it is easier to compute credulous explana­ tions first, then priorities are added to make explanations skeptical as in Procedure 3.1.

4 Finding Further Preference

In Section 3.2, we considered an abductive framework ( P, r, Ill) in which r and Ill are pre-specified. However, such candidate hypotheses are often insufficiently given so that we cannot explain an observation skeptically.

Example 4.1 (legal reasoning [Kowalski and Toni, 1996]) Suppose that the ELP P is given as:

inherits(x, y) +-- beneficiary(x, y), not ·inherits(x, y),(4)

Rule ( 4) indicates that a person inherits an estate if he/she is the beneficiary of a valid will and it cannot be shown that the person does not inherit it. Rule (5) says that a person usually does not inherit an estate if he/she murders the owner of the estate. The program P has two answer sets, one containing inherits(j, h) and the other ·inherits(j, h). Given the observation ·inherits(j, h), we cannot get any explanation wrt ( P, 0, 0 ) .

In this section, we consider a method to generate new abducibles for obtaining further preference.

4.1 Generating New Abducibles

A method to discover new abducibles is considered in [In­ oue and Haneda, 1999], where abducibles are newly in­ vented in learning ALPs. Here, we modify their method by associating priorities with new abducibles.

Firstly, notice that rules (4) and (5) in Example 4.1 are the source of non-determinism in the program. Then, these non-deterministic rules are converted into ab­ ducible rules. Without loss of generality, we assume that such rules in an ELP P are of the form: 2

where a and f3 are literals and both B1 and B2 are con­ junctions of literals and NAF formulas. Here, we assume that neither a nor f3 appears in the head or the body of any rule other than (6) in P. Now, let N1 be a pair of rules of the form (6), and P1 = P \ N1 . Also, let E1 be the set of ground instances of a and f3 that are en­ tailed by P. Then, f 1 is obtained by converting N1 into abducible rules:

2 Using the unfolding operation, we can get pairs of rules of the form (6) which cause non-determinism in P.

Next, using the translation in Section 2.2, each abducible rule R of the form (7) in f 1 can be named with a new atom 8n, and put P2 = P1 U { (H +-- B,8n) I R = (H +­ B) E rl} and r2 = {8n IRE r!}. Then, compute the set E2 of instances of new abducibles in f 2 such that P2 U E2 f= e for every e E E1 . This identification of E2 from E1 is easy, and it is used to assure that the literals in E1 can also be entailed by the new program. We now obtain the ALP ( P', f') = ( P2 u E2 , f2 ).

Proposition 4.1 Let P be an ELP, and ( P', f' ) the ALP constructed as above. Then, for every consistent answer set S of P , there is a belief set S' of ( P', f') such that S = S' \ f' . 3

Example 4.2 (cont. from Example 4.1)

Let N1 be the last two rules ( 4,5) in P, P1 = P \ N1, and E1 = {inherits( a, b) , ·inherits(c, d)}. Then, non­ deterministic rules N1 are converted into abducible rules:

By naming these abducible rules with 8inherit(x,y) and 8~inherit(x,y), the ALP (P',f') is obtained as:

In the ALP, inherits(j, h) is concluded by abduc­ ing 8inherit(j, h), while ·inherits(j, h) is skeptically ex­ plained by 8~inherit(j, h) .

4.2 From Abducibles to Priorities

So far , we have not yet introduced new priorities into the process of finding new abducibles. That is, appropriate literals are just abduced to explain the observation. Such a right selection of hypotheses in abduction can be con­ sidered as our preference of some particular causes over others. With this regard, we can acquire new preference information from abductive programs as follows .

Suppose that 8a and 813 are the naming atoms for a pair of abducible rules of the form (7). Then, the ALP ( P', f' ) in Section 4.1 can be further translated into the semantically equivalent ELP P* by replacing each pair of abducibles 8a and 813 in f' with the pair of rules:

This time, we have the following relationship between the answer sets of the original ELP P and those of P*.

Proposition 4.2 Let P be a consistent ELP, and P* the ELP constructed as above. Then, for every answer set S ef P, there is an answer set S* of P* such that S = S* \ f', where f' is the same as in Proposition 4 .1. Conversely, for every answer set S* of P*, there is an answer set s of p such that s = s· \ r'.

3 The converse of Proposition 4.1 does not hold. In Exam­ ple 4.2, the ALP ( P', r') has a belief set containing neither inherits(], h) nor ·inherits(j, h), which is not an answer set of P.

Using the above new P*, it is easy to associate pri­ orities on the newly introduced abducibles. Once the ALP ( P', r' ) is constructed, we can just consider the abductive framework ( P*, w· ), where w· is the candi­ date priorities on f'. In this way, abduction to particular causes and preference abduction are made transferable into each other.

Theorem 4.3 Let ( P', f' ) and ( P*, w· ) be the same as in the above discussion, and 0 be an observation. Then, there is a skeptical explanation of 0 wrt ( P', f' ) iff there is a skeptical explanation of 0 wrt ( P*, w· ) .

Example 4.3 (cont. from Example 4.2)

The ALP ( P', f') constructed in Example 4.2 can be now translated into the ELP P* = P' U Pr' where Pr' is given as:

Then, P* has two answer sets, one containing 8inherit(j, h) and inherits(j, h), and the other containing 8~inherit(j, h) and ·inherits(j, h) .

Now, let us consider the preference abduction ( P*, w· ) , where w· contains the candidate priorities:

Given the observation ·inherits(j, h), we have the ex­ planation { 8inherit(j, h)~ 8~inherit(j, h)}.

4.3 Preference View Updates

The advantage of the above translation into preference abduction is that priorities do not have to be given on the target observations but are given on the source hy­ potheses. In this sense, we call such inference to pref­ erence preference view updates, which are analogous to the notion of view updates in deductive databases. In preference view updates, the priority request on given observations 0 1 :::S 0 2 is translated into priorities on their causes 'ljJ ~ w·. A typical application of this kind is abduction to rule preference in the legal domain.

Example 4.4 (cont. from Example 4.3)

Suppose that one rather prefers the conclusion inherits(j, h) to the opposite ·inherits(j, h) . This pref­ erence view:

can be translated into the priority between the hypotheses:

This last relation indicates that she/he should prefer the rule (4) to the other rule (5) in her/his argument.

It should be noted that, as view updates in databases can be characterized through abduction [Kakas and Mancarella, 1990], our formulation of preference view updates are also based on preference abduction.

As far as the authors know, there are very few work on abducing priorities to derive desired conclusion. Zhang and Foo [1998] associate priorities to resolve conflicts be­ tween rules in updating ELPs. Their framework can be regarded as a kind of preference abduction to be applied to theory updates. In general, preference information is helpful to resolve contradiction in a program. Priori­ ties on defaults specify the guideline that some defaults are to be kept but some are discarded in restoring the consistency. Wakaki et al. [1998] present a method of finding priorities as a part of the circumscription pol­ icy to be used in prioritized circumscription. In their method, priorities are selected from the set of all pos­ sible orderings on minimized predicates. On the other hand, our method can discover new priorities on literals for PLPs as shown in Section 4.

There are a lot of recent work on introducing priori­ ties into abductive and nonmonotonic reasoning. Eiter and Gottlob [1995] discuss the computational complex­ ity of a form of prioritized abduction, whose prioritization is similar to that of prioritized circumscription. Sakama and Inoue [1996] propose a different kind of priori tied ab­ duction in the context PLPs, in which priorities are used to select desired abducibles from multiple explanations. Priorities have also been used to represent preference be­ tween conflicting default rules in PLPs and prioritied de­ fault logics [Brewka, 1994; Baader and Hollunder, 1995; Dimopoulos and Kakas, 1995; Sakama and Inoue, 1996; Brewka and Eiter, 1998]. None of these work, however, discusses how to find an appropriate set of priorities to derive desired conclusions.

Brewka [1994] argues the importance of the ability of using defaults that reason about preference between other defaults. Our preference abduction would also be extended by introducing such dynamic preference into not only deduction but abduction on PLPs, but the is­ sue is not addressed in this paper.

6 Conclusion

This paper introduced a novel framework for finding preference to derive intended conclusions in nonmono­ tonic reasoning. Preference abduction is not only an ex­ tension of traditional ALPs, but much extends the rea­ soning ability of PLPs. Applications of preference ab­ duction include the resolution of the multiple extension problem, skeptical abduction, preference view updates, and abduction to rule preference in legal reasoning.

In this paper, we also presented an interesting fact that abduction to a particular cause and abduction to pref­ erence are sometimes transferable to each other. This line of research would extend the applicability of exist­ ing frameworks for ALPs as computational tools for pri­ oritied default reasoning. The design of a more sophis­ ticated algorithm to compute preference abduction also remains to be explored.