Recently there has been an increasing interest in probabilistic abstract argumentation, an extension of Dung’s abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP#P-hard and propose polynomial approximation algorithms with bounded additive error for probabilistic argumentation frameworks where odd-length cycles are forbidden. This is quite surprising since, as we show, such kind of approximation algorithm does not exist for the related FP#Phard problem of computing the probability of the credulous acceptance of an argument, even for the special class of argumentation frameworks considered in the paper.
Explainable Acceptance in Probabilistic Abstract Argumentation: Complexity and Approximation / G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna - In: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning / [a cura di] D. Calvanese, E. Erdem, M. Thielscher. - [s.l] : IJCAI Organization, 2020. - ISBN 978-0-9992411-7-2. - pp. 33-43 (( Intervento presentato al 17. convegno Principles of Knowledge Representation and Reasoning tenutosi a Rhodes nel 2020 [10.24963/kr.2020/4].
Explainable Acceptance in Probabilistic Abstract Argumentation: Complexity and Approximation
M. Calautti;
2020
Abstract
Recently there has been an increasing interest in probabilistic abstract argumentation, an extension of Dung’s abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP#P-hard and propose polynomial approximation algorithms with bounded additive error for probabilistic argumentation frameworks where odd-length cycles are forbidden. This is quite surprising since, as we show, such kind of approximation algorithm does not exist for the related FP#Phard problem of computing the probability of the credulous acceptance of an argument, even for the special class of argumentation frameworks considered in the paper.File | Dimensione | Formato | |
---|---|---|---|
kr2020-0004-alfano-et-al.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
251.59 kB
Formato
Adobe PDF
|
251.59 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.