×

On efficiently estimating the probability of extensions in abstract argumentation frameworks. (English) Zbl 1344.68221

Summary: Probabilistic abstract argumentation is an extension of Dung’s abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability \(\Pr^{\mathrm{sem}}(S)\) that a set \(S\) of arguments is an extension according to a semantics sem. We focus on four popular semantics (i.e., complete, grounded, preferred and ideal-set) for which the state-of-the-art approach is that of estimating \(\Pr^{\mathrm{sem}}(S)\) by using a Monte-Carlo simulation technique, as computing \(\Pr^{\mathrm{sem}}(S)\) has been proved to be intractable. In this paper, we propose a new Monte-Carlo simulation approach which exploits some properties of the above-mentioned semantics for estimating \(\Pr^{\mathrm{sem}}(S)\) using much fewer samples than the state-of-the-art approach, resulting in a significantly more efficient estimation technique.

MSC:

68T27 Logic in artificial intelligence
68T37 Reasoning under uncertainty in the context of artificial intelligence

Software:

Dungine; ASPARTIX
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Fazzinga, B.; Flesca, S.; Parisi, F., Efficiently estimating the probability of extensions in abstract argumentation, (Scalable Uncertainty Management - 7th International Conference, SUM, (2013)), 106-119
[2] Dung, P. M., On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell., 77, 2, 321-358, (1995) · Zbl 1013.68556
[3] Dung, P. M.; Mancarella, P.; Toni, F., Computing ideal sceptical argumentation, Artif. Intell., 171, 10-15, 642-674, (2007) · Zbl 1168.68564
[4] Baroni, P.; Giacomin, M., Semantics of abstract argument systems, (Argumentation in Artificial Intelligence, (2009)), 25-44
[5] Dunne, P. E.; Wooldridge, M., Complexity of abstract argumentation, (Argumentation in Artificial Intelligence, (2009)), 85-104
[6] Dunne, P. E., The computational complexity of ideal semantics, Artif. Intell., 173, 18, (2015)
[7] Dung, P. M.; Thang, P. M., Towards (probabilistic) argumentation for jury-based dispute resolution, (COMMA, (2010)), 171-182
[8] Li, H.; Oren, N.; Norman, T. J., Probabilistic argumentation frameworks, (TAFA, (2011))
[9] Thimm, M., A probabilistic semantics for abstract argumentation, (ECAI, (2012)), 750-755 · Zbl 1327.68290
[10] Rienstra, T., Towards a probabilistic dung-style argumentation system, (AT, (2012)), 138-152
[11] Hunter, A., Some foundations for probabilistic abstract argumentation, (COMMA, (2012)), 117-128
[12] Hunter, A., A probabilistic approach to modelling uncertain logical arguments, Int. J. Approx. Reason., 54, 1, 47-81, (2013) · Zbl 1266.68176
[13] Fazzinga, B.; Flesca, S.; Parisi, F., On the complexity of probabilistic abstract argumentation, (IJCAI, (2013))
[14] Fazzinga, B.; Flesca, S.; Parisi, F., On the complexity of probabilistic abstract argumentation frameworks, ACM Trans. Comput. Log., 16, 3, 22, (2015) · Zbl 1354.68253
[15] Agresti, A.; Coull, B. A., Approximate is better than “exact” for interval estimation of binomial proportions, Am. Stat., 52, 2, 119-126, (1998)
[16] Li, H.; Oren, N.; Norman, T. J., Relaxing independence assumptions in probabilistic argumentation, (Proc. of Tenth International Workshop on Argumentation in Multi-Agent Systems, ArgMAS, (2013))
[17] Dondio, P., Toward a computational analysis of probabilistic argumentation frameworks, Cybern. Syst., 45, 3, 254-278, (2014) · Zbl 1331.68221
[18] Prakken, H., An abstract framework for argumentation with structured arguments, Argument Comput., 1, 2, 93-124, (2010)
[19] Dondio, P., Computing the grounded semantics in all the subgraphs of an argumentation framework: an empirical evaluation, (Proc. of 14th International Workshop Computational Logic in Multi-Agent Systems, CLIMA, (2013)), 119-137 · Zbl 1401.68303
[20] Hunter, A., Probabilistic qualification of attack in abstract argumentation, Int. J. Approx. Reason., 55, 2, 607-638, (2014) · Zbl 1316.68153
[21] Bench-Capon, T. J.M., Persuasion in practical argument using value-based argumentation frameworks, J. Log. Comput., 13, 3, 429-448, (2003) · Zbl 1043.03026
[22] Amgoud, L.; Vesic, S., A new approach for preference-based argumentation frameworks, Ann. Math. Artif. Intell., 63, 2, 149-183, (2011) · Zbl 1234.68371
[23] Amgoud, L.; Cayrol, C., A reasoning model based on the production of acceptable arguments, Ann. Math. Artif. Intell., 34, 1-3, 197-215, (2002) · Zbl 1002.68172
[24] Modgil, S., Reasoning about preferences in argumentation frameworks, Artif. Intell., 173, 9-10, 901-934, (2009) · Zbl 1192.68663
[25] Dunne, P. E.; Hunter, A.; McBurney, P.; Parsons, S.; Wooldridge, M., Weighted argument systems: basic definitions, algorithms, and complexity results, Artif. Intell., 175, 2, (2015)
[26] Coste-Marquis, S.; Konieczny, S.; Marquis, P.; Ouali, M. A., Weighted attacks in argumentation frameworks, (KR, (2012))
[27] Martínez, D. C.; García, A. J.; Simari, G. R., An abstract argumentation framework with varied-strength attacks, (KR, (2008)), 135-144
[28] Amgoud, L.; Prade, H., Reaching agreement through argumentation: a possibilistic approach, (KR, (2004)), 175-182
[29] Alsinet, T.; Chesñevar, C. I.; Godo, L.; Sandri, S.; Simari, G. R., Formalizing argumentative reasoning in a possibilistic logic programming setting with fuzzy unification, Int. J. Approx. Reason., 48, 3, 711-729, (2008) · Zbl 1184.68497
[30] Alsinet, T.; Chesñevar, C. I.; Godo, L.; Simari, G. R., A logic programming framework for possibilistic argumentation: formalization and logical properties, Fuzzy Sets Syst., 159, 10, 1208-1228, (2008) · Zbl 1187.68601
[31] Dunne, P. E.; Caminada, M., Computational complexity of semi-stable semantics in abstract argumentation frameworks, (Proc. of 11th European Conference Logics in Artificial Intelligence, JELIA, (2008)), 153-165 · Zbl 1178.68557
[32] Dvorák, W.; Woltran, S., Complexity of semi-stable and stage semantics in argumentation frameworks, Inf. Process. Lett., 110, 11, 425-430, (2010) · Zbl 1229.68041
[33] Gaggl, S. A.; Woltran, S., The cf2 argumentation semantics revisited, J. Log. Comput., 23, 5, 925-949, (2013) · Zbl 1275.68138
[34] Booth, R.; Caminada, M.; Dunne, P. E.; Podlaszewski, M.; Rahwan, I., Complexity properties of critical sets of arguments, (Proc. of Computational Models of Argument, COMMA, (2014)), 173-184
[35] Baroni, P.; Caminada, M.; Giacomin, M., An introduction to argumentation semantics, Knowl. Eng. Rev., 26, 4, 365-410, (2011)
[36] Kim, E. J.; Ordyniak, S.; Szeider, S., Algorithms and complexity results for persuasive argumentation, Artif. Intell., 175, 9-10, 1722-1736, (2011) · Zbl 1230.68189
[37] Besnard, P.; García, A. J.; Hunter, A.; Modgil, S.; Prakken, H.; Simari, G. R.; Toni, F., Introduction to structured argumentation, Argument Comput., 5, 1, 1-4, (2014)
[38] Haenni, R.; Kohlas, J.; Lehmann, N., Probabilistic argumentation systems, (Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5: Algorithms for Uncertainty and Defeasible Reasoning, (2000), Kluwer), 221-288 · Zbl 0987.68076
[39] Haenni, R.; Anrig, B.; Kohlas, J.; Lehmann, N., A survey on probabilistic argumentation, (ECSQARU’01, Toulouse. Workshop: Adventures in Argumentation, (2001)), 19-25
[40] Shakarian, P.; Simari, G. I.; Falappa, M. A., Belief revision in structured probabilistic argumentation, (Proc. of 8th International Symposium on Foundations of Information and Knowledge Systems, FoIKS, (2014)), 324-343 · Zbl 1405.68366
[41] García, A. J.; Simari, G. R., Defeasible logic programming: an argumentative approach, Theory Pract. Log. Program., 4, 2, 95-138, (2004) · Zbl 1090.68015
[42] Martinez, M. V.; García, A. J.; Simari, G. R., On the use of presumptions in structured defeasible reasoning, (Computational Models of Argument - Proceedings of COMMA 2012, Vienna, Austria, September 10-12, 2012, (2012)), 185-196
[43] Hansson, S. O., Semi-revision (invited paper), J. Appl. Non-Class. Log., 7, 2, (2015)
[44] Verheij, B., Accrual of arguments in defeasible argumentation, (Proceedings of the Second Dutch/German Workshop on Nonmonotonic Reasoning, (1995)), 217-224
[45] Prakken, H., A study of accrual of arguments, with applications to evidential reasoning, (Proceedings of the Tenth International Conference on Artificial Intelligence and Law, (2005), ACM Press), 85-94
[46] Lucero, M. J.G.; Chesñevar, C. I.; Simari, G. R., Modelling argument accrual with possibilistic uncertainty in a logic programming setting, Inf. Sci., 228, 1-25, (2013) · Zbl 1293.68256
[47] South, M.; Vreeswijk, G.; Fox, J., Dungine: a Java dung reasoner, (COMMA, (2008)), 360-368
[48] Egly, U.; Gaggl, S. A.; Woltran, S., ASPARTIX: implementing argumentation frameworks using answer-set programming, (ICLP, (2008)), 734-738
[49] Snaith, M.; Reed, C., TOAST: online ASPIC^{+} implementation, (COMMA, (2012)), 509-510
[50] Alsinet, T.; Béjar, R.; Godo, L.; Guitart, F., Using answer set programming for an scalable implementation of defeasible argumentation, (ICTAI, (2012)), 1016-1021
[51] Charwat, G.; Dvorák, W.; Gaggl, S. A.; Wallner, J. P.; Woltran, S., Methods for solving reasoning problems in abstract argumentation - a survey, Artif. Intell., 220, 28-63, (2015) · Zbl 1328.68212
[52] Ng, R. T.; Subrahmanian, V. S., Probabilistic logic programming, Inf. Comput., 101, 2, 150-201, (1992) · Zbl 0781.68038
[53] Lukasiewicz, T., Probabilistic deduction with conditional constraints over basic events, J. Artif. Intell. Res., 10, 199-241, (1999) · Zbl 0914.68178
[54] Lukasiewicz, T., Probabilistic logic programming with conditional constraints, ACM Trans. Comput. Log., 2, 3, 289-339, (2001) · Zbl 1171.68762
[55] Flesca, S.; Furfaro, F.; Parisi, F., Consistency checking and querying in probabilistic databases under integrity constraints, J. Comput. Syst. Sci., (2014), available online 24 April 2014 · Zbl 1311.68053
[56] Poole, D., The independent choice logic for modelling multiple agents under uncertainty, Artif. Intell., 94, 1-2, 7-56, (1997) · Zbl 0902.03017
[57] Lukasiewicz, T., Probabilistic description logic programs, Int. J. Approx. Reason., 45, 2, 288-307, (2007) · Zbl 1122.68027
[58] Suciu, D.; Olteanu, D.; Ré, C.; Koch, C., Probabilistic databases, synthesis lectures on data management, (2011), Morgan & Claypool Publishers
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.