On the Relation between Argumentation and Non-monotonic Coherence-Based Entailment

1 Introduction

Reasoning from inconsistent beliefs is a significant problem in Artificial Intelligence. In this paper, belief bases are considered "syntactically", as in [Nebel, 1991]: each belief is a distinct piece of information and only beliefs which are explicitely present in the base are taken into account. It departs from the logical point of view where a base is identified with the set of its models. Our purpose is to compare two main types of approaches to reasoning from inconsistency:

- The approaches based on the notion of maximal consistent subbase 1, where non-monotonic inference relations are defined by the combination of a mechanism for generating "preferred" belief subbases, a principle for selecting some of these subbases and the classical inference. (See [Cayrol and Lagasquie-Schiex, 1993; 1994] for a thorough presentation of these inference relations). As preferred subbases, all the maximal consistent subbases may be considered, or the consistent subbases of maximal cardinality [Benferhat et al., 1993a]. Other meanings of "preferred" have been studied, induced by the presence of an ordering on the belief base [Brewka, 1989; Geffner, 1992; Cayrol et al., 1993]. As a selection principle (see [Pinkas and Loui, 1992] for a taxonomy of selection principles), we usually find the existential one, selecting one of the preferred subbases, or the universal one, selecting all the preferred subbases. An intermediary principle, called argumentative in [Benferhat et al., 1993b], leads to the following consequence relations "I conclude cj> from the belief base if at least one preferred subbase classically entails cj> and no preferred subbase classically entails ..... cj>" .

1maximal for set-inclusion consistent subbases were first introduced by Rescher and Manor [1970] .

-Independently, argument-based approaches to defeasible reasoning have been developed [Lin and Shoham, 1989; Vreeswijk, 1991; Pollock, 1992; Simari and Loui, 1992; Dung, 1993; Elvang-Goransson et al., 1993a & 1993b; Hunter, 1994]. Argumentation is a general principle based on the construction and use of arguments. An argumentation system is defined by specifying the way of constructing and using arguments. The basic idea is to view reasoning as a process of first constructing arguments in favor of a conclusion, and then selecting the most acceptable of them. In other words, a statement will be inferred if the arguments supporting this statement can be successfully defended against the arguments supporting the opposite statement.

As recently discussed in [Benferhat et al., 1995], these two types of approaches correspond to two attitudes in front of inconsistent beliefs: one attitude is to restore coherence by selecting consistent subbases, the other one is to accept inconsistency by providing arguments for each conclusion.

In this paper, we establish a close correspondence between these two models of reasoning, referred to as coherence-based reasoning and argument-based reasoning, in the following. First, we present and discuss two completely formalized argumentation systems. Then, we show that the associated inference relations can be exactly restated in the framework of coherence-based entailment with an appropriate selection principle on maximal consistent subbases. Finally, we propose directions for further research concerning the integration of preference relations in argumentation systems. Results are given without proofs due to space limitations. Proofs appear in [Cayrol, 1995].

2 Argumentation Systems

Throughout this paper .L is a propositional language. r-­ denotes classical entailment. 1( and 'E denote sets of formulas of.£. 1(, which may be empty, represents a core of knowledge and is assumed consistent. Contrastedly, formulas of 'E represent defeasible pieces of knowledge, or beliefs. So '1( U 'E may be inconsistent. 'E will be referred to as the beliefbase.

2.1 Arguments Built from a Belief Base

We introduce the notion of argument in the framework ('1(, '£). A similar definition appears for instance in [Simari and Loui, 1992].

Definition! An argument of 'E is a pair (H, h), where h is a formula of L and His a subbase of 'E satisfying: (i) '1( U H is consistent, (ii) '1( U H 1-- h, (iii) H is minimal (no strict subset of H satisfies ii). His called the support and h the conclusion of the argument. The set of all the arguments of 'E will be denoted by AR('E).

Remarks

• All the arguments considered in this paper have a consistent support.
• In the work reported here, an argument is simply a pair of set of supporting sentences and conclusion. We do not considered structured arguments involving chains of reasons, as in [Pollock, 1992].
• The minimality criterion (point iii) in Definition!) might be enforced by other criteria such as specificity, or any other preference criteria. That point will be discussed in Section 5.

According to [Dung, 1993], an argumentation system is defined given any set of arguments .!{ equipped with a binary relation!~{, The intended meaning of "~Al, A2)" is "the argument Al defeats the argument A2". We present below different definitions for that relation of "defeat", within the above context where arguments are built from a belief base.

Definition2 [Elvang-Goransson et al., 1993a] Let (Hl, hl) and (H2, h2) be two arguments of'£. (Hl, hl) rebuts (H2, h2) iff hl "" ~h2. (· means logical equivalence).

An argument is rebutted iff there exists an argument for the negated conclusion.

Definition3 [Elvang-Goransson et al., 1993a] Let (Hl, hl) and (H2, h2) be two arguments of 'E. (Hl, hl) undercuts (H2, h2) iff for some hE H2, h s ~hl.

An argument is undercut iff there exists an argument for the negation of an element of its support. Obviously, an argument which undercuts another argument is rebutted. Another family of definitions was proposed in the work of Simari and Loui [1992]. With the restriction to the above context, we obtain:

Definition4 Let (Hl, hl) and (H2, h2) be two arguments of'£. (H 1, h 1) and (H2, h2) disagree (or are in disagreement) iff '1( U {hl, h2} is inconsistent.

(Hl, hl) is a subargument of (H2, h2) iff Hl ~ H2.

(Hl, hl) counterargues (H2, h2) iff (Hl, hl) 1s m disagreement with a subargument of (H2, h2).

Note that the counterargument relation is a kind of refinement of the disagreement relation, in the sense that it considers subarguments. In an analogous way, we propose a weaker version of definition3.

DefinitionS (Hl, hl) weakly-undercuts (H2, h2) iff (Hl, hl) rebuts a subargument of (H2, h2) (iff '1( U H2 1-- ~hl) .

2.2 About the Various Meanings of "Defeat"

It seems interesting to compare these different relations defined on the set of arguments AR('E). Proofs of the following results can be found in [Cayrol, 1995].

Proposition 1

• Obviously, if (Hl, hl) rebuts (i-12, h2), these arguments disagree. The converse is false as shown by '1( = {a, b, x-c} '£ = {a-x, b-~c}and the arguments ({b-~c}, ~c)and({a-x}, x).
• If two arguments disagree, each one is rebutted by a subargument of the other one. The converse is false as shown by '1( =0, '£ = {a, b, x-c, a-x, b-~c}and the arguments ({b, b-~c, x-c}, ~x) and ({a, a-x, x-c}, c).
• -If (Hl, hl) undercuts (H2, h2) then (Hl, hl) weakly­ undercuts (H2, h2), and then (Hl, hl) counterargues (H2, h2).
• (Hl, hl) counterargues (H2, h2) iff (Hl, hl) is rebutted by a subargument of (H2, h2). Or equivalently, (Hl, hl) counterargues (H2, h2) iff (Hl, hl) weakly-undercuts (H2, h2).

To summarize, Aland A2 denoting two arguments of'£, we have:

A 1 undercuts A2 => A 1 counterargues A2 <=> A 1 weakly-undercuts A2

Al rebuts A2 => Al and A2 disagree.

3 Argumentation-Based Inference

Due to the inconsistency of the available knowledge, arguments may be constructed in favor of a statement and other arguments may be constructed in favor of the opposite statement. The main approaches which have been developed for reasoning within an argumentation system rely on the idea of differentiating arguments with a notion of acceptability. In the proposal by [Elvang-Goransson et al., 1993a; 1993b], acceptability levels are assigned to arguments on the basis of other constructible arguments . Then, from a taxonomy of acceptability classes, consequence relations are defined. Quite independently, Dung [1993] formalized a kind of global acceptability. The set of all the arguments that a rational agent may accept must defend itself against all attacks on it. This leads to defining extensions of an argumentation system.

In this section, we apply both methodologies on the same argumentation system and establish some interesting results about argumentation-based inference, which will contribute to unify different approaches and will particularly enable us to recover coherence-based entailment relations in Section 4.

3.1 Acceptability Classes

Here we show that the consequence relations induced by the construction of acceptability classes are the same whether we consider the family of relations ("rebuts", "undercuts"), or the family ("disagrees", "counterargues"). We still consider the framework ('1(, '£) and the set of arguments AR('E).

Definition6 [Elvang-Goransson et al., 1993a]

AR*(1:) denotes the set of arguments of 1: with an empty support. (0,h) E AR*(1:) iff '1( 1--h.

AR+(1:) denotes the set of arguments of 1: which are not rebutted by some argument of 1:.

AR++(1:) denotes the set of arguments of AR+(1:) (or equivalently of 1:, as proved in [Elvang-Goransson et al., 1993a]) which are not undercut by some argument of 1:.

The following inclusions hold between the so-called acceptability classes: C4 = AR*(1:) ~ C3 = AR++(1:) ~ C2 = AR+(1:) ~ C1 = AR(1:). Inclusion is generally strict as shown by: '1( = 0, 1: ={a, a-+b, -.a} and the argument ({a, ~b}, b) which belongs to AR+(1:) but is undercut by ({~a}, -.a).

The argument (H1, h1) is said more acceptable than (H2, h2) iff there exists a class Ci (1 :s: i :s: 4) containing (H1, hl) but not containing (H2, h2). Consequence relations are defined by:

Definition7 [Elvang-Goransson et al., 1993a] Let <j> be a formula of L .

• ~ is a certain consequence of 1: (1: l~ce <j>) iff AR *(1:) contains an argument concluding <j> .

~ is a confirmed consequence of 1: (1: l~co <j>) iff there exists H ~ 1: with (H, <j> )EAR++(1:).

• ~ is a probable consequence of 1: (1: l~pr <j>) iff there exists H ~ 1: with (H, <j> )EAR+(1:).
• ~ is a plausible consequence of 1: (1: l~pl <j>) iff there exists H ~ 1: with (H, <j> )EAR(1:).

Remarks

• -The "probable consequence" has been considered independently in [Benferhat et al., 1993b] where it was called "argumentative consequence".
• -When the belief base 1: is '](-consistent, confirmed consequence, probable consequence and plausible consequence coincide.
• -The following implications hold 1: l~ce <j> => 1: I~ co <j> = > 'E l~pr <j> => 1: l~pl <j>, but the converse do not generally. Take '1( =0, 1: = {a, a-+b, -.a}: a-+b is a confirmed but not certain consequence; b is a probable but not confirmed consequence; a is a plausible but not probable consequence.

Following the above construction, we consider now the relations of disagreement and counterargument.

DefinitionS

AR'+(1:) . denotes the set of arguments of 1: which disagree with no argument of 1:.

AR'++(1:) denotes the set of arguments of 1: which are not counterargued by some argument of 1: (or equivalently whichareneverweakly-undercut).

Proposition2 AR+(1:) = AR'+(1:) and AR++(1:) = AR'++(1:).

Proof: from Proposition!. See [Cayrol, 1995].

Though the relations "rebuts" and "undercuts" of [Elvang­ Goransson et al., 1993a] are stronger than the relations

"disagrees" and "counterargues" of [Simari and Loui, 1992], we obtain exactly the same consequence relations.

3.2 Extensions of an Argumentation System

First, we recall the definitions of [Dung, 1993] in a general framework. Let (AR, "defeats") denote an argumentation system.

Definition9 [Dung, 1993]

A subset S of AR is conflict-free iff there are no two arguments A1, A2 inS such that A1 "defeats" A2.

A subset S of AR is a stable extension iff

• (i) Sis conflict-free

(ii) for each argument A not belonging to S, there exists an argument BinS such that B "defeats" A. In other words, S "defeats" each argument which does not belong to S.

For instance, AR+(1:) is conflict-free in the system (AR(1:), "rebuts") and AR++(1:) is conflict-free in the system (AR(1:), "undercuts"). Intuitively, a stable extension corresponds to a maximal set of acceptable or admissible arguments for a rational agent. Then, a common proposal to handle multiple stable extensions would be to accept a formula as a consequence when it can be classically inferred from all the stable extensions (conservative point of view), or when it can be classically inferred from at least one stable extension (permissive point of view).

Now, we focus on the particular case of the argumentation system (AR(1:), "undercuts") defined in Section 2. Let S be a subset of AR(1:). S is conflict-free means: there are no two arguments (H1, h1), (H2, h2) in S such that for some h E H2, h a -.hl. S is a stable extension means moreover: If the argument (H, h) does not belong to S, there exists (H', h') inS such that for some h" EH, h" · -.h'.

Let For(S) denote the set of conclusions of arguments of S and Supp(S) denote the union of the supports of arguments of S. T being a subbase of 1:, let Arg(T) denote {(H, h) E AR(1:) I H ~ T}.

Remind that a "maximal for set-inclusion '](_-consistent" subbase of 1: (or "maximal '](-consistent" subbase, for short) is a '](-consistent subbase of 1: which is maximal for set-inclusion among all the '1( -consistent subbases of 1: .

Proposition3 LetS be a stable extension of the system (AR(1:), "undercuts").

• Supp(S) is a maximal '](-consistent subbase of 1:.
• Arg(Supp (S)) = S.
• '1( U Supp(S) 1-- <j> iff <j> E For(S).

Proposition4 LetT be a maximal '](-consistent subbase of 1:. Arg(T) is a stable extension of the system (AR(1:), "undercuts"). Supp(Arg(T)) = T.

As a direct consequence of these two propositions we obtain the following characterization:

PropositionS In the argumentation system (AR(1:), "undercuts"), the stable extensions are exactly the Arg(T), where T is a maximal '](-consistent subbase of 1:.

However, no such characterization exists in the case of the argumentation system (AR(1:}, "counterargues"). In that system, S is conflict-free means : there are no two arguments (H1, h1), (H2, h2) in S such that '1( U H2 1-­ ~hl. S is a stable extension means moreover: If the argument (H, h) does not belong to S, there exists (H', h') in S such that '1( U H 1-- ~h'.

Proposition6 LetT be a maximal '](-consistent subbase of 'E. Arg(T) is a stable extension of the system (AR('E), "counterargues").

However, there are other stable extensions. More particularly, there are stable extensions S such that Supp(S) is '](-inconsistent.

Example! '1(= {(a" b)--+ c} 'E ={a, b, ~c} . LetS be the set of arguments containing: all the arguments of the form (0, g) where '1( 1-- g, all the arguments of the form ({a}, h), all the arguments of the form ({b}, h), all the arguments of the form ( { ~ c}, h) and no other argument. So S contains at least the set {(0, (aAb)--+ c), ({a}, a), ({a}, b --+c), ({b}, b), ({b}, a--+ c),({ ~c}, ~c),({ ~c}, ~a v~b)}. Note that Supp(S) = 'E and then is '](-inconsistent. It can be proved [Cayrol, 1995] that Sis a stable extension of the system (AR('E), "counterargues").

We conclude this section with a few words about related work. A similar notion of stable extension was proposed in [Simari and Loui, 1992] for modelling argumentation-based inference. The construction relies upon a refinement of the counterargumentation, which takes into account the specificity of arguments. More precisely, an argument A "defeats" an argument B iff B contains a subargument less specific than A and which is in disagreement with A. Geffner [1992] proposed a notion of stable argument to account for conditional entailment in the framework of default reasoning. A stable argument is an argument which "defeats" each conflicting argument, where A "defeats" B iff A contains a subargument preferred than Band conflicting with B. The preference relation is extracted from the knowledge base and accounts for conditional aspects of defaults, including specificity. Most inferences authorized by conditional entailment are recovered with the concept of stable argument. Specificity and more generally preference criteria will be briefly discussed in Section 5.

4 Recovering Coherence-Based Nonmonotonic Entailment

Throughout this section, we consider the argumentation system (AR('E), "undercuts"). We recall that the belief base 'E may be '](-inconsistent. The coherence-based approach for handling inconsistency involves a revision step, the selection of several consistent subbases (the so-called preferred belief subbases), before applying classical entailment. The term "syntax-based" has been first used to designate that kind of approach. For instance, syntax-based revision procedures were defined by Nebel [1991], and prioritized syntax-based entailment has been studied by [Benferhatet al., 1993a]. Here, we consider syntax-based inference (from '1( U 'E) as defined through the management of maximal '](-consistent subbases of 'E. A maximal '](­ consistent subbases of 'E is called a thesis of ('1(, 'E), in the following. Three non-monotonic consequence relations may be defined using three main selection principles.

DefinitionlO [Cayrol and Lagasquie-Schiex, 1993; 1994]

According to the skeptical or universal principle, cj> is a strong consequence of 'E ('E 1~ 'V ,t cj>) iff for each thesis T of ('1(, 'E), '1( U T 1-- cj> .

According to the credulous or existential principle, cj> is a weak consequence of 'E ('E 1~3, t cj>) iff there exists at least one thesis T of ('1(, 'E) such that '1( U T 1-- cj>.

According to the argumentative principle, cj> is an argumentative consequence of 'E ( 'E j,-.,A, t cj>) iff there exists at least one thesis T of ('1(, 'E) such that '1( U T 1-- cj> and no thesis T' of ('1(, 'E) such that '1( U T' 1-- ~ cj>.

Now we are able to restate the argumentation-based inference schemas presented in Section 3 in the framework of non-monotonic syntax-based entailment.

Proposition7 cj> is a plausible consequence of 'E ('E 1---pl cj>) iff cj> is a weak consequence of 'E ('E 1~3,t cj>) iff there exists at least one stable extension S of (AR('E), "undercuts") such thatcj> E For(S).

Proof: consequence of Proposition4.

Proposi tion8 cj> is a probable consequence of 'E ('E l~pr cj>) iff cj> is an argumentative consequence of 'E ('E l~,t cj>) iff there exists at least a stable extension S of (AR('E), "undercuts") such that cj> E For(S) and no stable extension S' such that ~cj> E For(S').

Proof: consequence of Proposition?.

Note that the first equivalence ('E l~pr cj> iff 'E l~,t cj>) is also proved in [Benferhat eta/., 1993b].

Proposi tion9 cj> is a confirmed consequence of 'E ('E 1~00 cj>) iff there exists an argument (H, cj>) such that H is included in eoch thesis of ('1(, 'E) iff there exists an argument (H, cj>) which belongs to eoch stable extension of (AR('E), "undercuts").

Proof: consequence of Proposition4.

PropositionlO cj> is a confirmed consequence of 'E ('E 1---co cj>) => cj> is a strong consequence of'E ('E 1~ 'V,t cj> ).

Proof: consequence of Proposition9. The converse is false as shown by the following example.

Example2 '1( =0, 'E = {a, b, a--+~b, a--+c, b--+c}.We obtain three maximal '](-consistent subbases of 'E: T1 = {a, a--+~b, a --+c, b--+c}, T2 ={a, b, a--+c, b--+c}, T3 = {b, a--+~b, a--+c, b--+c}. Soc is a strong consequence of 'E. Besides, we obtain two arguments concluding c: ({a, a--+c}, c) and ({b, b--+c}, c). But neither of them belongs to AR++('E) since there exists an argument concluding ~a and there exists an argument concluding ~b. Hence, c is not a confirmed consequence of 'E.

Another important consequence of Proposition9 is:

Propositionll 4> is a confirmed consequence of 'E ('E ~co <j>) iff 4> is classically entailed by (the union of '1( and) the intersection of all the theses of ('1(, '£) .

Note that in [Benferhat et al., 1993b] the intersection of all the theses of ('1(, 'E) is called the Free part of 'E and is denoted by Free('£). 4> is said a free consequence of 'E iff '1( U Free('£) f- <j> . Then, Proposition II states that the free consequence defined from the theses of ('1(, 'E) is equivalent to the confirmed consequence defined from the argmnentation system (AR('E), "undercuts"). The notion of free consequence is also present, but called cautious consequence, in a work about inference with super-normal defaults [Brass, I993].

Summary

A consequence relation R is said more conservative than a consequence relation R' iff for each formula 4> of .L, 'E R <j> => 'E R' <j> . We obtain the hierarchy pictured in Table I, where the consequence relations are less and less conservative. For each relation, we find the definition in terms of theses and (if it exists) the associated acceptability class of arguments.

5 Conclusions and Perspectives

In the work reported here, our purpose was to provide a better understanding of fundamental mechanisms of defeasible reasoning, and not to propose one more formalism. Our most significant contribution to unifying numerous approaches to defeasible reasoning is the reconstruction of coherence-based non-monotonic inference operations from various argument-based approaches.

We have investigated the relations between argumentation-based reasoning and non-monotonic coherence-based reasoning, through the study of two particular argumentation systems. Our best results have been obtained with the system defined by the binary relation "undercut" on the set of arguments built from a belief base'£.

However, many other relations may be defined to compare arguments of '£: a specificity relation [Simari and Loui, I992], preference relations induced by a priority relation on the belief base [Elvang-Goransson et al., I993b;

Geffner, 1992], [Cayrol et al., 1993], or by certainty degrees [Benferhatet al., 1993b].

More works need to be done to integrate preference orderings between arguments into argumentation systems, particularly as regards the definition of consequence relations. More precisely, the following points deserve consideration:

- comparison of arguments in favor of the same conclusion. Given a priority relation on the belief base, we need appropriate aggregation modes to define a preference relation on the different supports of a statement. This kind of preference should respect the minimality for set­ inclusion. See [Cayrol et al., I993] for preliminary work on the subject.

- comparison of arguments for contradictory conclusions. A preference relation between "conflicting" arguments may lead to a new definition of the relation "defeats" [Simari and Loui, I992; Geffner, 1992]. For instance, the argument (HI, h1) "defeats" (H2, h2) iff there exists a subargument of (H2, h2) in disagreement with, but less preferred than (HI, hi). Thus, a new argumentation system is obtained in which the construction of acceptability classes and associated consequence relations can be performed. A preference between conflicting arguments may be also directly used to define a consequence relation such as: 4> is inferred if there exists an argument concluding 4> which is preferred to each argument concluding ~ <j>. This definition was proposed in the framework of possibilistic logic by [Benferhatet al., 1993b].

- definition of new acceptability classes. Given an argumentation system, for instance (AR('E), "undercuts"), we may consider the arguments which are never "rebutted" (resp. "undercut") by a preferred argument. Once again, new acceptability classes will induce (a priori) new consequence relations.

Besides, much work has been devoted to the integration of preference relations into non-monotonic inference schemas (see [Cayrol and Lagasquie-Schiex, 1993] for a survey). When the belief base is equipped with a pre­ ordering (namely a priority relation), a selection principle (universal, existential or argumentative) is coupled with a mechanism of generation of preferred subbases. These generation mechanisms usually respect maximality for set-

Table 1

inclusion and select preferred subbases among the theses. For instance, inclusion-based preference combines priorities and maximal consistent subbases while lexicographic preference[Benferhatet al., 1993a] combines priorities and consistent subbases of maximal cardinality. As in the case of a flat belief base, it will be interesting to establish connections between the various inference schemas developed in the framework of argumentation systems with preference and the inference relations defined through selection principles of preferred theses. We are currently working on this topic.

Acknowledgements

We thank Thierry Castell for helpful comments and suggestions on an earlier version of this paper.