Preliminary Study on Reinstatement Labelling for Weighted Argumentation Frameworks?

Abstract

Argumentation Theory allows for reasoning with uncertain and controversial information, and provides tools for deciding which arguments (for instance, of a debate) can be accepted together. The strength of an argument and its attacks can be expressed through weighted argumentation frameworks; in this case, the selection criteria, called semantics, used to identify the sets of acceptable arguments, need to take into account the information given by the weights. In this paper, we conduct an initial study on a novel labelling semantics for weighted argumentation frameworks, extending and generalising the crisp one.

Keywords

• Argumentation
• Weighted Frameworks
• Labelling

Introduction

Generalised notions of defence for weighted AFs are studied in several works, each with a di↵erent definition for the notion of weights. In two recent papers [ 3,4 ] the attacks from an argument to a set of arguments are grouped together as if they were a unique attack; such a weighted notion of defence also generalises the approaches of [ 7 ] and [ 9 ]. Through the reasoning on the acceptability of the arguments according to a notion of defence, one can divide the set of arguments into two separated subsets, respectively containing accepted and non-accepted arguments. However, for certain applications of argumentation (especially those in which defeating an argument leads to the reinstatement of another one [ 6 ]), it is convenient to consider more degrees of acceptability in order for one to be able to further di↵erentiate among arguments. The labelling, defined in [ 6 ], refines the concept of acceptable argument and builds on the classical semantics for providing an additional acceptance status.

In this work, we extend the notion of labelling to weighted argumentation frameworks and we provide a definition that is parametric to a chosen notion of defence [ 3,7,9 ] and that corresponds to the original labelling [ 6 ] when a boolean semiring is used. For each weighted semantics, we give the conditions under which a labelling corresponds to a set of extensions. ? This work was partially supported by “Argumentation 360” (Ricerca di Base 20172019) and “RACRA18” (Ricerca di Base 2018-2020).

Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons

License Attribution 4.0 International (CC BY 4.0).

Background

An abstract argumentation framework [ 8 ] is a pair hA, Ri where A is a set of arguments and R is a binary relation on A. Consider two arguments a, b belonging to an AF. We denote with (a, b) 2 R (or simply a ! b) an attack from a to b; we can also say that b is defeated by a. We define the sets of arguments that attack (and that are attacked by) another argument as follows. Definition 1 (Attacks). Let F = hA, Ri be an AF, a 2 A and A ✓ A . We define the sets a+ = {b 2 A | a ! b}, a = {b 2 A | b ! a}, A+ = [{ a+ | a 2 A} and A = [{ a | a 2 A}.

In order for b to be acceptable, we require that every argument that defeats b is defeated in turn by some other argument of the AF.

Definition 2 (Acceptable argument [ 8 ]). Given an AF F = hA, Ri, an argument a 2 A is acceptable with respect to D ✓ A i↵ 8 b 2 A such that (b, a) 2 R, 9 c 2 D such that (c, b) 2 R, and we say that b is defended by D.

By using the notion of defence as a criterion for distinguishing acceptable arguments, one can further refine the set of selected arguments through semantics. Definition 3 (Extension-based semantics). Let F = hA, Ri be an AF. A set E ✓ A is conflict-free in F i↵ there are no a, b 2 A such that (a, b) 2 R. A conflict-free subset E is then: i) admissible if each a 2 E is defended by E; ii) complete if it is admissible and 8 a 2 A defended by E, a 2 E. 2.1

Labelling-Based Semantics

The authors in [ 1 ] and [ 6 ] describe how to assign labels to the arguments of an AF in such a way that the set of arguments is partitioned in three subsets, each representing a di↵erent degree of acceptance.

Definition 4 (Labelling). Let F = {A, R} be an AF. A labelling is a total function L : A ! { IN, OUT, UNDEC}. For any A ✓ A , we denote A|IN, A|OUT and A|UNDEC the set of all the arguments labelled IN, OUT and UNDEC by L, respectively.

Given a labelling L, it is also possible to identify a correspondence with the extension-based semantics [ 1 ]. More in detail, the set of IN arguments coincides with an extension. We rephrase the semantics of Definition 3 as follows. Definition 5 (Labelling-based semantics). Let L be a labelling of an AF F = hA, Ri and a 2 A. Then L is: – conflict-free i↵ L(a) = IN =) a |IN = ; ^ – admissible i↵ L(a) = IN =) a = a |OUT ^ – complete i↵ L(a) = IN () a = a |OUT ^ L(a) = OUT =) a |IN 6= ; L(a) = OUT =) a |IN 6= ; L(a) = OUT () a |IN 6= ;

Note that a complete labelling coincides with the definition of reinstatement labelling given in [ 6 ]. 2.2

Weighted Argumentation Frameworks

Dung’s argumentation frameworks can be extended by associating the attacks with a weight that represents the support of the relation.

Definition 6 (WAF). A weighted argumentation framework is a triple W = hA, R, wi where hA, Ri is a Dung-style abstract argumentation framework and w : R ! R+ is a function assigning positive real valued weights to attacks.

Notions of weighted defence have been proposed in [ 4,7,9 ]. In this paper, we use the interpretation of [ 4 ] (which generalises the other two definitions [ 3 ]), where WAFs are equipped with a commutative semiring that provides the operation for composing the weights. The acceptability of an argument is determined by comparing the compositions of attacks with the composition of defences. Definition 7 (c-semirings). A commutative semiring is a tuple S = hS, , ⌦ , ? , >i such that S is a set, >, ? 2 S, and , ⌦ : S ⇥ S ! S are binary operators making the triples hS, , ?i and hS, ⌦ , >i commutative monoids, satisfying i) 8 s, t, u 2 S.s ⌦ (t u) = (s ⌦ t) (s ⌦ u), and ii) 8 s 2 S.s ⌦ ? = ? .

Di↵erent c-semirings can represent di↵erent notions of defence for WAFs, by using the operators and ⌦ for obtaining an ordering among the weights in S. Common instances of c-semirings are Sboolean = h{false, true}, _ , ^ , false, truei and Sweighted = hR+ [ { +1} , min, +, +1 , 0i. We denote with WAFS a WAF endowed with a c-semirings and we call it a semiring-based WAF. Definition 8 (WAFS). A semiring-based WAF is a quadruple hA, R, W, Si, where S is a c-semiring hS, , ⌦ , ? , >i, A is a set of arguments, R the attack binary-relation on A, and W : A ⇥ A ! S is a binary function. Given a, b 2 A and R(a, b), then W (a, b) = s means that a attacks b with a weight s 2 S. Moreover, we require that R(a, b) i↵ W (a, b) <S >.

Given a WAFS, we can evaluate the overall weight of all the attacks from a set of arguments towards another set through the composition operator ⌦ [ 3 ]. In particular, we say that a set of arguments B attacks a set of arguments D, and the weight of such attack is k 2 S, if W (B, D) = Nb2B ,d2D W (b, d) = k. The notion of weighted defence (or w-defence) can then be expressed as follows. Definition 9 (w-defence). Let F = hA, R, W, Si be a WAF S. B ✓ A wdefends b 2 A i↵ 8 a 2 A such that R(a, b), we have W (a, B [ { b}) S W (B, a).

According to [ 4 ], by using the notion of w-defence for checking the acceptability of the arguments in the weighted framework, it is possible to redefine all the extension-based semantics presented in Definition 3.

Definition 10 (Extension-based semantics for WAFS). Given a WAFS F = hA, R, W, Si, a subset B ✓ A is w-conflict-free if W (B, B) = >. Then B is: i) w-admissible i↵ it is w-conflict-free and the arguments in B are w-defended by B from the arguments in A \ B; ii) w-complete i↵ it is a w-admissible extension and each argument b 2 A such that B [ { b} is w-admissible belongs to B;

Labelling for Weighted AFs

Contrary to classical AFs, for which we can use the procedure in [ 6 ] for assigning labels to the arguments in such a way that there is a correspondence between the labelling and the set of extension, no work on this direction has been done for what concerns the weighted case. We extend the notion of labelling introduced in [ 6 ] to a WAFS and we give the conditions for determining whether a labelling corresponds to a certain extension. In order to incorporate the notion of weighted defence in the labelling, we need to take into account the strength of the attack relations: according to the definition of collective defence [ 3 ] we need to know the resulting strength of the composition of all the attacks towards an argument. Definition 11 (Labelling for WAFs). Let F = hA, R, W, Si be a WAFS. A labelling L of F is a total function L : A ! { IN, OUT, UNDEC}. We also define, for each argument, the weight of attacks, incoming into and outgoing from an argument, as wa |IN = W (a |IN, a) and wa+|IN = W (a, a+|IN).

In our system, OUT arguments are associated with the N of the incoming attacks. An argument a with label OUT is attacked by the arguments in a |IN with a total strength that is expressed by wa. In the following, we give a characterisation of the weighted semantics through the notion of labelling of WAFs. The intuition behind this representation is that when an argument a attacked by an OUT b cannot be labelled IN because of another IN argument that is “consuming” the attacks of the defending arguments towards b, then a is labelled UNDEC. The w-conflict-free labelling coincides with the conflict-free labelling. Indeed, since no attacks are allowed within a conflict-free set of arguments, one does not need to consider the weights.

Definition 12 (Labelling-based semantics for WAFs). Let L be a labelling of a WAFS F = hA, R, W, Si and a 2 A. Then – L is a w-admissible labelling for F i↵: • L(a) = IN =) a = a |OUT ^ 8 b 2 a . wb |IN  S wb+|IN • L(a) = OUT =) wa |IN <S > – L is a w-complete labelling for F i↵: • L(a) = IN () a = a |OUT ^ 8 b 2 a . wb |IN  S wb+|IN • L(a) = OUT () wa |IN <S >

The condition wb |IN  S wb+|IN for the w-admissible labelling makes sure that the composition of the attacks of the arguments defending a is stronger than the attack of b. For an argument to be OUT, we require wa |IN <S >, that is to say that there must exist at least an attack coming from an IN argument (as for the classical admissible labelling). The definition of the w-complete labelling is similar to the w-admissible one, with the exception that the conditions given for IN arguments are both necessary and sucient. The weighted semantics generalise the classical case: all the labellings for WAFS correspond to the respective Dung semantics when the framework is instantiated with a boolean semiring. Remark 1. Let F = hA, R, W, Si be a WAFS where S is boolean, and L a labelling of F . If L is a w-admissible (respectively w-complete) labelling, then L is an admissible (respectively complete) labelling of F . The definitions of the labelling-based semantics for WAFs, that we give in Section 3, do not include conditions for the UNDEC since they are obtained from IN and OUT arguments. In this sense, we would like to investigate the possible advantages of giving explicit conditions for labelling the UNDEC arguments, similarly to what is done in [ 10 ] for classical AFs. We also plan to extend the presented labelling to all the semantics (including preferred, stable and grounded). An interesting study could then be carried out on the don’t care and don’t know labels, that are used in [ 2 ] as further di↵erentiation of UNDEC arguments. In our context, the di↵erence between the two labels could be made more continuous by considering the weight on the attack relations. Moreover, the weights wa |IN and wa+|IN of the attacks towards and from each argument (other than the respective weights for OUT and UNDEC) could be used for defining a ranking-based semantics for WAFs. Finally, we want to implement the labelling-based semantics for WAFs in ConArg [ 5 ], an online tool for dealing with argumentation problems.

References

1. Baroni , P. , Caminada , M. , Giacomin , M.: An introduction to argumentation semantics . Knowledge Eng. Review 26 ( 4 ), 365 - 410 ( 2011 )

2. Baroni , P. , Giacomin , M. , Liao , B.S.: I don't care, I don't know ... I know too much! On Incompleteness and Undecidedness in Abstract Argumentation . In: Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation. Lecture Notes in Computer Science , vol. 9060 , pp. 265 - 280 . Springer ( 2015 )

3. Bistarelli , S. , Rossi , F. , Santini , F. : A Collective Defence Against Grouped Attacks for Weighted Abstract Argumentation Frameworks . In: Proceedings of FLAIRS 2016 . pp. 638 - 643 . AAAI Press ( 2016 )

4. Bistarelli , S. , Rossi , F. , Santini , F. : A novel weighted defence and its relaxation in abstract argumentation . Int. J. Approx. Reasoning 92 , 66 - 86 ( 2018 )

5. Bistarelli , S. , Santini , F. : Modeling and solving afs with a constraint-based tool: Conarg . In: Theorie and Applications of Formal Argumentation - First International Workshop, TAFA 2011 . Revised Selected Papers. Lecture Notes in Computer Science , vol. 7132 , pp. 99 - 116 . Springer ( 2011 )

6. Caminada , M. : On the Issue of Reinstatement in Argumentation . In: Proceedings of JELIA 2006. Lecture Notes in Computer Science , vol. 4160 , pp. 111 - 123 . Springer ( 2006 )

7. Coste-Marquis , S. , Konieczny , S. , Marquis , P. , Ouali , M.A. : Weighted Attacks in Argumentation Frameworks . In: Principles of Knowledge Representation and Reasoning. Proceedings of KR 2012 . AAAI Press ( 2012 )

8. Dung , P.M. : On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games . Artificial Intelligence 77 ( 2 ), 321 - 357 ( Sep 1995 )

9. Mart´ınez, D.C. , Garc´ıa, A.J. , Simari , G.R.: An Abstract Argumentation Framework with Varied-Strength Attacks . In: Principles of Knowledge Representation and Reasoning: Proceedings of KR 2008 . pp. 135 - 144 . AAAI Press ( 2008 )

10. Modgil , S. , Caminada , M. : Proof Theories and Algorithms for Abstract Argumentation Frameworks . In: Argumentation in Artificial Intelligence , pp. 105 - 129 . Springer ( 2009 )