# A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation

43 %
57 %
Information about A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in...
Education

Published on September 22, 2014

Author: fcerutti

Source: slideshare.net

## Description

A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation

Presentation at KR2014, Vienna, 2014

A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation Federico Cerutti, Massimiliano Giacomin, Mauro Vallati, Marina Zanella KR-2014 — Monday 21st July, 2014

Background on Dung’s AF SCC-Recursiveness Exploiting the SCC-Recursiveness Empirical Results Conclusions

Background Definition Given an AF = hA;Ri, with R  A  A: - a set S  A is conflict–free if @ a; b 2 S s.t. a ! b; - an argument a 2 A is acceptable with respect to a set S  A if 8b 2 A s.t. b ! a, 9 c 2 S s.t. c ! b; - a set S  A is admissible if S is conflict–free and every element of S is acceptable with respect to S; - a set S  A is a complete extension, i.e. S 2 ECO(), iff S is admissible and 8a 2 A s.t. a is acceptable w.r.t. S, a 2 S; - a set S  A is the grounded extensions, i.e. S 2 EGR(), iff S is the minimal (w.r.t. set inclusion) complete set; - a set S  A is a preferred extension, i.e. S 2 EPR(), iff S is a maximal (w.r.t. set inclusion) complete set.

Background Definition Let hA;Ri be an AF: Lab : A7! fin; out; undecg is a complete labelling iff 8a 2 A: - Lab(a) = in , 8b 2 aLab(b) = out; - Lab(a) = out , 9b 2 a : Lab(b) = in. Let S  A a conflict–free set: the corresponding labelling is Ext2Lab(S)  Lab, where - Lab(a) = in , a 2 S - Lab(a) = out , 9 b 2 S s.t. b ! a - Lab(a) = undec , a =2 S ^ @ b 2 S s.t. b ! a Proposition ([Caminada, 2006]) Given an an AF = hA;Ri, Lab is a complete (grounded, preferred) labelling of if and only if there is a complete (grounded, preferred) extension S of such that Lab = Ext2Lab(S).

An Example

An Example

Background on Dung’s AF SCC-Recursiveness Exploiting the SCC-Recursiveness Empirical Results Conclusions

SCC-Recursiveness: Path-Equivalence

SCC-Recursiveness: Partial Order of the SCCs

SCC-Recursiveness: Recursiveness of the approach

SCC-Recursiveness Definition A given argumentation semantics  is SCC-recursive if for any argumentation framework = hA;Ri, E() = GF(;A)  2A. For any = hA;Ri and for any set C  A, E 2 GF(;C) if and only if - E 2 BF(;C) if jSCCj = 1 - 8S 2 SCC (E S) 2 GF(#Sn(EnS)+;U(S;E) C) otherwise where - BF(;C) is a function, called base function, that, given an argumentation framework = hA;Ri such that jSCCj = 1 and a set C  A, gives a subset of 2A - U(S;E) = fa 2 S n (E n S)+ j 8b 2 (a n S); b 2 E+g

SCC-Recursiveness and semantics restricted to a set of arguments Definition Given an AF = hA;Ri and a set C  A, a set E  A is: - an admissible set of in C if and only if E is an admissible set of and E  C - a complete extension of in C if and only if E is an admissible set of in C, and every argument a 2 C which is acceptable with respect to E belongs to E - the grounded extension of in C if and only if it is the least (with respect to set inclusion) complete extension of in C - a preferred extension of in C if and only if it is a maximal (with respect to set inclusion) complete extension of in C.

Research Questions How can we exploit the SCC-Recursiveness in an algorithm? Is it worth doing it?

Background on Dung’s AF SCC-Recursiveness Exploiting the SCC-Recursiveness Empirical Results Conclusions

The Starting Point

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm Proposition Let hA;Ri be an argumentation framework and let C  A a set of arguments. Considering the grounded labelling Lab of in C and the set U including the undec-labelled arguments according to Lab, it holds that LPR(;C) = fLab [ E j E 2 LPR(#U;C U)g.

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm

The Meta-Algorithm I = ff ; gg O = ;

The Meta-Algorithm

The Base Case: Complete Labelling in C Definition Let = hA;Ri be an argumentation framework and C  A be a set of arguments. A total function Lab : A7! fin; out; undecg is a complete labelling of in C iff it satisfies the following conditions for any a 2 C: C: Lab(a) = in , 8b 2 aLab(b) = out; L2 L1 C: Lab(a) = out , 9b 2 (a C) : Lab(b) = in; L3 C: Lab(a) = undec , 8b 2 (a C);Lab(b)6= in ^ 9c 2 a : Lab(c) = undec; and the following conditions for any a 2 (A n C): L1 : Lab(a) = out , 9b 2 (a C) : Lab(b) = in; AnCL2 AnC: Lab(a) = undec , 8b 2 (a C);Lab(b)6= in. Proposition Given an an AF = hA;Ri and a set C  A, Lab satisfies the above conditions if and only if there is a complete extension S of in C such that Lab = Ext2Lab(S).

Complete Labelling in C and CNF ^ i21(C)  (Ii _ Oi _ Ui) ^ (:Ii _ :Oi)^(:Ii _ :Ui) ^ (:Oi _ :Ui)  ^ ^ i21(C) 0 @Ii _ 0 @ _ (:Oj ) fjj(j)!(i)g 1 A 1 A ^ ^ i21(C) 0 @ ^ fjj(j)!(i)g :Ii _ Oj 1 A^ ^ i21(C) 0 B@ ^ fj21(C)j(j)!(i)g :Ij _ Oi 1 CA ^ ^ i21(C) 0 B@ :Oi _ 0 B@ _ fj21(C)j(j)!(i)g Ij 1 CA 1 CA ^ ^  ^  ^ i21(C) fkj(k)!(i)g  Ui _ :Uk _  _  fj21(C)j(j)!(i)g Ij  ^ ^ i21(C) fj21(C)j(j)!(i)g (:Ui _ :Ij ) ^  :Ui _  _ fkj(k)!(i)g Uk  ^ ^  :Ii ^ (Oi _ Ui) ^ (:Oi _ :Ui) i21(AnC)  ^ ^ i21(AnC) 0 B@ ^ fj21(C)j(j)!(i)g :Ij _ Oi 1 CA ^ i21(AnC) 0 B@:Oi _ 0 B@ _ fj21(C)j(j)!(i)g Ij 1 CA 1 C A^ ^ i21(AnC) 0 B @Ui _ 0 B@ _ fj21(C)j(j)!(i)g Ij 1 CA 1 CA ^ ^ i21(AnC) 0 B@ ^ fj21(C)j(j)!(i)g :Ui _ :Ij 1 CA

Complete Labelling in C and CNF Proposition Let hA;Ri be an argumentation framework and C  A be a set of arguments. If Lab is a complete labelling of in C, then the assignment V()  f(Ii;>) j Lab((i)) = ing [ f(Oi;>) j Lab((i)) = outg [ f(Ui;>) j Lab((i)) = undecg satisfies the ENCall encoding shown before. Conversely, if V() is a satisfying assignment of the ENCall encoding, then the labelling Lab  f(a; in) j I1(a) 2 V()g [ f(b; out) j O1(b) 2 V()g [ f(c; undec) j U1(c) 2 V()g is a complete labelling of in C.

The Base-Case

The Base-Case

The Meta-Algorithm

Background on Dung’s AF SCC-Recursiveness Exploiting the SCC-Recursiveness Empirical Results Conclusions

Analysis Using the International Planning Competition (IPC) Score - For each test case (in our case, each test AF) let T be the best execution time among the compared systems (if no system produces the solution within the time limit, the test case is not considered valid and ignored). - For each valid case, each system gets a score of 1=(1 + log10(T=T )), where T is its execution time, or a score of 0 if it fails in that case. - The (non normalized) IPC score for a system is the sum of its scores over all the valid test cases. The normalised IPC score ranges from 0 to 100 and is defined as (IPC=# of valid cases)  100.

The Experiment - SAT approach optimized ([Cerutti et al., 2014] SAT-P) vs SCC-Recursiveness using SAT for the base case (SCC-P); - I1: on s.t. jSCCj = 1, SCC-P performs worse than SAT-P; - I2: there exists a value  such that on where jSCCj > , SCC-P performs better that SAT-P; - I3: on s.t. jSCCj > , the greater jEPR()j, the more SAT-P performs worse than SCC-P.

First Hypothesis 790 AFs (), s.t. jSCCj = 1 and A = 25 : 25 : 250 IPC value (normalised) for SCC-P and SAT-P when |SCC| = 1, varying || 100 90 80 70 60 50 40 0 50 100 150 200 250 || SCC-P SAT-P

Second Hypothesis 720 AFs varying jSCCj in 5:5:45. Size of SCCs N( = 20 : 5 : 40,  = 5); attacks among SCCs N( = 20 : 5 : 40,  = 5) 100 90 80 70 60 50 40 IPC value (normalised) for SCC-P and SAT-P when 5  |SCC|  45 0 10 20 30 40 50 |SCC| SCC-P SAT-P

Second Hypothesis 720 AFs varying jSCCj in 5:5:45. Size of SCCs N( = 20 : 5 : 40,  = 5); attacks among SCCs N( = 20 : 5 : 40,  = 5) 100 90 80 70 60 50 40 IPC value (normalised) for SCC-P and SAT-P when 5  |SCC|  45 Remark For jSCCj = 35, Md(SCC-P) = 8:81, Md(SAT-P) = 8:53, z = 0:35, p = 0:73; 0 10 20 30 40 50 |SCC| SCC-P SAT-P

Third Hypothesis 2800 AFs (as before) s.t. jSCCj = 50 : 5 : 80 Median of times for SCC-P and SAT-P when 50  |SCC|  80 varying |EPR()| 900 800 700 600 500 400 300 200 100 0 0 50 100 150 200 250 300 s |EPR()| SCC-P SAT-P

Third Hypothesis 2800 AFs (as before) s.t. jSCCj = 50 : 5 : 80 Remark Regression to the function f(x) = a x+b: SCC-P, a = 0:43, b = 31:33; SAT-P, a = 2:40, b = 87:53 Median of times for SCC-P and SAT-P when 50  |SCC|  80 varying |EPR()| 900 800 700 600 500 400 300 200 100 0 0 50 100 150 200 250 300 s |EPR()| SCC-P SAT-P

Background on Dung’s AF SCC-Recursiveness Exploiting the SCC-Recursiveness Empirical Results Conclusions

Conclusions 1. Efficient algorithmic implementation of the SCC-recursiveness schema - [Liao et al., 2013] decomposition but not the recursiveness - Other [Baumann et al., 2012, Dvorák et al., 2012b, Baroni et al., 2012] 2. Generalisation of [Cerutti et al., 2014] for the computation of labellings in sub-frameworks - [Besnard and Doutre, 2004, Dvorák et al., 2012a, Arieli and Caminada, 2013]. . . 3. Empirical evaluation: - with jSCCj >  = 35 statistical evidence that the SCC-recursive schema reduces the computational effort of enumerating the preferred labellings; - Execution time of the SCC-recursive implementation is less sensible to the number of labellings

Future Works - Exploiting and comparing different equivalent encodings of complete labellings in C including the redundant ones - Different B-PR algorithm for computing labellings in sub-frameworks [Egly et al., 2010, Nofal et al., 2014, Dvorák et al., 2014] - Meta-algorithm to stable and CF2 semantics (directly fit the SCC-recursive schema [Baroni et al., 2005]) and to semi-stable and ideal semantics (relationship with preferred semantics)

References I [Arieli and Caminada, 2013] Arieli, O. and Caminada, M. W. (2013). A QBF-based formalization of abstract argumentation semantics. Journal of Applied Logic, 11(2):229–252. [Baroni et al., 2012] Baroni, P., Boella, G., Cerutti, F., Giacomin, M., van der Torre, L., and Villata, S. (2012). On Input/Output Argumentation Frameworks. In Proceedings of the 4th International Conference on Computational Models of Arguments (COMMA 2012), pages 358–365. [Baroni et al., 2005] Baroni, P., Giacomin, M., and Guida, G. (2005). SCC-recursiveness: a general schema for argumentation semantics. Artificial Intelligence, 168(1-2):165–210. [Baumann et al., 2012] Baumann, R., Brewka, G., Dvorák, W., and Woltran, S. (2012). Parameterized Splitting: A Simple Modification-Based Approach. In Erdem, E., Lee, J., Lierler, Y., and Pearce, D., editors, Correct Reasoning, volume 7265 of Lecture Notes in Computer Science, pages 57–71. Springer Berlin Heidelberg.

References II [Besnard and Doutre, 2004] Besnard, P. and Doutre, S. (2004). Checking the acceptability of a set of arguments. In Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), pages 59–64. [Caminada, 2006] Caminada, M. (2006). On the Issue of Reinstatement in Argumentation. In Proceedings of the 10th European Conference on Logics in Artificial Intelligence (JELIA 2006), pages 111–123. [Cerutti et al., 2014] Cerutti, F., Dunne, P. E., Giacomin, M., and Vallati, M. (2014). Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach. In Black, E., Modgil, S., and Oren, N., editors, TAFA 2013, volume 8306 of Lecture Notes in Computer Science, pages 176–193. Springer-Verlag Berlin Heidelberg. [Dvorák et al., 2012a] Dvorák, W., Järvisalo, M., Wallner, J. P., and Woltran, S. (2012a). Complexity-Sensitive Decision Procedures for Abstract Argumentation. In Proceedings of 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), pages 54–64.

References III [Dvorák et al., 2014] Dvorák, W., Järvisalo, M., Wallner, J. P., and Woltran, S. (2014). Complexity-sensitive decision procedures for abstract argumentation. Artificial Intelligence, 206:53–78. [Dvorák et al., 2012b] Dvorák, W., Pichler, R., and Woltran, S. (2012b). Towards fixed-parameter tractable algorithms for abstract argumentation. Artificial Intelligence, 186:1–37. [Egly et al., 2010] Egly, U., Alice Gaggl, S., and Woltran, S. (2010). Answer-set programming encodings for argumentation frameworks. Argument & Computation, 1(2):147–177. [Liao et al., 2013] Liao, B., Lei, L., and Dai, J. (2013). Computing Preferred Labellings by Exploiting SCCs and Most Sceptically Rejected Arguments. In Second International Workshop on Theory and Applications of Formal Argumentation (TAFA-13). [Nofal et al., 2014] Nofal, S., Atkinson, K., and Dunne, P. E. (2014). Algorithms for decision problems in argument systems under preferred semantics. Artificial Intelligence, 207:23–51.

 User name: Comment:

January 23, 2019

January 23, 2019

January 23, 2019

January 23, 2019

January 23, 2019

January 23, 2019

## Related pages

### A SCC Recursive Meta-Algorithm for Computing Preferred ...

A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation Federico Cerutti School of Natural and Computing Science

### Cerutti

AAAI Publications, Fourteenth International Conference ... Computing Preferred Labellings in Abstract ... SCC Recursive Meta-Algorithm for Computing ...

### A SCC Recursive Meta-Algorithm for Computing Preferred ...

A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation

### AAAI Publications, Fourteenth International Conference on ...

An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation

### Federico Cerutti | Mendeley

A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation Cerutti F, Giacomin M, Vallati M, Zanella ...

### Federico Cerutti - Google Scholar Citations

Computing preferred extensions in abstract argumentation: ... An SCC recursive meta-algorithm for computing preferred labellings in abstract argumentation.

### ArgSemSAT: Solving Argumentation Problems Using SAT

enumerating preferred extensions. Keywords. argumentation, ... Dung’s theory of abstract argumentation ... SCC Recursive Meta-Algorithm for Computing ...