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

44 %
56 %
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 ^ i21(C)  (Ii _ Oi _ Ui) ^ (:Ii _ :Oi)^(:Ii _ :Ui) ^ (:Oi _ :Ui)  ^ ^ i21(C) 0 @Ii _ 0 @ _ (:Oj ) fjj(j)!(i)g 1 A 1 A ^ ^ i21(C) 0 @ ^ fjj(j)!(i)g :Ii _ Oj 1 A^ ^ i21(C) 0 B@ ^ fj21(C)j(j)!(i)g :Ij _ Oi 1 CA ^ ^ i21(C) 0 B@ :Oi _ 0 B@ _ fj21(C)j(j)!(i)g Ij 1 CA 1 CA ^ ^  ^  ^ i21(C) fkj(k)!(i)g  Ui _ :Uk _  _  fj21(C)j(j)!(i)g Ij  ^ ^ i21(C) fj21(C)j(j)!(i)g (:Ui _ :Ij ) ^  :Ui _  _ fkj(k)!(i)g Uk  ^ ^  :Ii ^ (Oi _ Ui) ^ (:Oi _ :Ui) i21(AnC)  ^ ^ i21(AnC) 0 B@ ^ fj21(C)j(j)!(i)g :Ij _ Oi 1 CA ^ i21(AnC) 0 B@:Oi _ 0 B@ _ fj21(C)j(j)!(i)g Ij 1 CA 1 C A^ ^ i21(AnC) 0 B @Ui _ 0 B@ _ fj21(C)j(j)!(i)g Ij 1 CA 1 CA ^ ^ i21(AnC) 0 B@ ^ fj21(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 I1(a) 2 V()g [ f(b; out) j O1(b) 2 V()g [ f(c; undec) j U1(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.

Add a comment

Related presentations

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
Read more

Cerutti

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

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

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

AAAI Publications, Fourteenth International Conference on ...

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

Federico Cerutti | Mendeley

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

Federico Cerutti - Google Scholar Citations

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

ArgSemSAT: Solving Argumentation Problems Using SAT

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

Federico Cerutti | LinkedIn

A SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation ... obtained by exploiting the SCC-recursive ...
Read more

Generating Challenging Benchmark AF - University of Dundee

Generating Challenging Benchmark AFs ... Dung’s abstract argumentation framework ... SCC Recursive Meta-Algorithm for Computing Preferred Labellings in ...
Read more