Computing Grounded Semantics of Uncontroversial Acyclic Constellation Probabilistic Argumentation in Linear Time

Abstract

We propose a new and faster (linear instead of exponential) way to compute the acceptability probability of an argument (in uncontroversial acyclic graph) with the grounded semantics in the constellations approach of probabilistic argumentation frameworks. Instead of computing all the worlds of the constellation (which is exponential) we show that it is possible to compute the probability of an argument only according to the acceptability probability of its direct attackers and the probability of its attacks by using a function.

Keywords

• eol>Probabilistic Argumentation Framework
• Constellation
• Grounded Semantics

1. Introduction

In recent years, argumentation has been increasingly recognised as a promising new research direction in artificial intelligence. As a consequence of this growing interest, many authors have studied different argumentation frameworks with different features and for various applications, like decision making (e.g. [ 1 ]), negotiation (e.g. [ 2 ]), explainability (e.g. [ 3 ]). The pioneering article in the field of abstract argumentation comes from Dung [ 4 ], where the notion of an abstract argumentation framework is defined. These frameworks can be seen as directed graphs where the nodes are arguments and the edges represent conflict relations (called attacks) between two arguments. A fundamental issue in these argumentation frameworks is to determine the acceptability of arguments and for this purpose so-called semantic methods are used. As mentioned earlier, since Dung many extensions to this framework have been proposed, e.g. the addition of a support relation (e.g. [ 5 ]), the addition of a similarity relation (e.g. [ 6, 7, 8, 9 ]), or the addition of weights on arguments (e.g. [ 10 ]), on attack (e.g. [ 11 ]) and support relations (e.g. [ 12 ]). Note that the meaning of the weights on arguments and relations can have different interpretations involving different semantics for computing the collective acceptability of arguments.

In this paper we place ourselves in the framework of probabilistic argumentation [ 13 ] where our graphs only have arguments connected by probabilistic attacks, i.e. the weights on these attacks indicate the probability that this attack exists. Recall that the two main approaches to (abstract) probabilistic argumentation are constellations and epistemic approaches [ 14 ]. The former considers probability functions on subgraphs of abstract argumentation frameworks, the latter uses probability theory to represent degrees of belief in arguments, given a fixed framework. Hence, our work is about the constellation approach. In this case, when we want to study the acceptability of an argument, we need to look at all the possible worlds (i.e. the whole set of possible subgraphs depending on the presence or absence of attacks). However, the creation of a constellation (the set of subgraphs) is in general exponential [ 13 ] and for this reason the attractiveness of research in this field is reduced for practical reasons. This paper is a first step to show that it is possible to optimize the computation of the acceptability probability of an argument without having to build the constellation.

2. Background

2.1. Dung Argumentation Frameworks

Following [ 4 ], an argumentation frameworks (AF) is a pair ⟨, ℛ⟩, where is a set of elements called arguments and ℛ is a binary relation on , called the attack relation. For , ∈ , if (, ) ∈ ℛ, then we say that attacks and that is an attacker of . If for ∈ there is no ∈ with (, ) ∈ ℛ, then is unattacked. For a set of arguments ⊆ and an argument ∈ , defends if ∀(, ) ∈ ℛ, ∃ ∈ such that (, ) ∈ ℛ. We say that is defended if for each last argument (unattacked) for each path to (i.e. {(, − 1), . . . , (1, )}), all the arguments defend , i.e. is even. Let the set of attackers of denoted by Att() = { ∈ | (, ) ∈ ℛ}. We say that an AF is uncontroversial ([ 4 ]) if ∀ ∈ , is uncontroversial, i.e. ∄ ∈ s.t. attacks and defends (e.g. let AF be an odd cycle, then AF and each argument are controversial).

An AF provides means to represent conflicting information. Reasoning with that information is done by means of argumentation semantics. A semantics provides a characterisation of acceptable arguments in an AF. A set of acceptable arguments according to a semantics is called an extension and is taken as a reasoning outcome. Many semantics have been proposed, see e.g. [ 15 ] for overviews. In this work, we will consider the very well established grounded semantics: the grounded extension of ⟨, ℛ⟩ can be constructed as gr = ⋃︀≥ 0 , where 0 is the set of all unattacked arguments, and ∀ ≥ 0, +1 is the set of all arguments that defends. For any ⟨, ℛ⟩, the grounded extension gr always exists and is unique.

2.2. Constellation Probabilistic Argumentation Frameworks

There exist different ways to extend the classic AF with probability into probabilistic argumentation framework (PrAF). For example, we can label arguments and/or attacks with a probability. In [ 16 ] the authors proposed a way to transform any PrAF having probability on arguments and attacks to PrAF with probability only on attacks (or only on arguments) thanks to the probabilistic attack normal forms (or probabilistic argument normal form). They showed that all these forms are equivalent, i.e. same probabilistic distribution on their extensions.

Definition 1 (PrAF). A probabilistic argumentation frameworks (PrAF) is a tuple = ⟨, ℛ, ⟩ ∈ 1 such that: ⊆ Arg 2, ℛ ⊆ × , : ℛ →]0, 1]. 1We denote by the universe of all probabilistic argumentation frameworks. 2The notation ⊆ Arg stands for: is a finite subset of the universe of all arguments.

The constellation of a graph is composed by all its possible subgraphs (worlds), and we compute the probability of one subgraph as follows.

Definition 2 (Probability of a world).

Let = ⟨, ℛ, ⟩ ∈ and = ⟨′, ℛ′, ⟩ be () = probabilistic argumentation graph such that ⊑ 3. The probability of subgraph , denoted such that ((, )) = 0.4, ((, )) = 0.7, ((, )) = 0.2 and is controversial . Example 1. Let see the controversial acyclic graph = ⟨{, , }, {(, ), (, ), (, )}, ⟩ Let see the constellation of with the probability of each world:

(1) = 0.056

(2) = Let = ⟨, ℛ, ⟩ ∈ , then ∑︀

⊑ () = 1. belonging to the extensions of an extension-based semantics.

Let us recall now how to compute the probability of an argument or a set of arguments

Definition 3 (Acceptability Probability).

an extension-based semantics, we denote by () = ∑︀

Let = ⟨, ℛ, ⟩ ∈ , ⊆

and In (, ), where In (, ) = 1 if is a subset of each extension of in , otherwise it is equal to 0. ⊑ () ×

Note that in [ 17 ], instead of giving a probability of acceptability for each argument (or set of arguments) for the grounded semantics, they return a single set of acceptable arguments for the initial graph. We consider that returning the probabilities is more generic and can be used in a second step to provide an acceptable set of arguments.

Example 1 (Continued). The acceptability probabilities of the arguments with the grounded semantics are: gr() = 1, gr() = 0.084 + 0.336 + 0.144 = 0.564, gr() = 0.024 + 0.096 + 0.036 + 0.144 = 0.3.

3. Linear Computation in Uncontroversial Acyclic PrAF

Let us introduce the new function Fastgr, which is able to compute the probability of an argument to be accepted in the grounded extension.

Definition 4 ( Fastgr). Let Fastgr the function from any PrAF ⟨, ℛ, ⟩ ∈ which compute the acceptability probability of any argument to be in the grounded extension ( → [ 0, 1 ]), s.t. ⎧⎨ 1 ⎩ ∈Att() Fastgr() = ∏︀ 1 − (︀ Fastgr() × (, ))︀ if Att() = ∅ otherwise 3The notation ⊑ stands for: ′ ⊆ and ℛ′ = {(, ) ∈ ℛ | ∈ ′ and ∈ ′}: is a subgraph of an AF.

Let start by discuss the intuition of this function to understand why it characterises the acceptability probability of the grounded semantics in some graph.

Recall that an argument is in the grounded extension if it is defended, i.e. if all its incoming attacks fail. Trivially, an unattacked argument will be acceptable in all worlds so its probability of acceptability is 1. Let us now look at the case where an argument is attacked. The Fastgr() × (, ) makes the conjunction (computes the probability) of the events argument is acceptable AND the attack (, ) exists. Thus 1 − Fastgr() × (, ) gives the probability that argument is not acceptable OR attack (, ) does not exist, i.e. this attack fails. Finally, the product of this computation for each attack ensures that all the attacks on fail, i.e. is defended.

Remark: the coherence constraint results from the fact that Fastgr considers the acceptability of arguments independently, i.e. it is possible for an controversial argument to be acceptable in its defence path and rejected in its attack path. Therefore, for an acyclic PrAF AF, Fastgr returns the probabilities of the arguments for the equivalent version of AF such that it is uncontroversial , i.e. each controversial argument is duplicated for its attacks and defences.

Note that if controversial arguments are always rejected or accepted in worlds, as in Example 1 ( gr() = 1), then Fastgr can return the same values as the constellation method (Fastgr() = gr() = 1, Fastgr() = gr() = 0.564 and Fastgr() = gr() = 0.3). We show next that Fastgr characterises gr for any uncontroversial acyclic PrAF.

Theorem 1. If ∈ is uncontroversial and acyclic then ∀ ∈ , gr() = Fastgr().

We also study complexity of Fastgr: in the worst case (when an argument have as attackers and defenders all other arguments) the complexity is linear O(n) (n is the number of all attacks) and in the best case (unattacked argument) the complexity is constant O(1).

Theorem 2. Let ∈ is uncontroversial and acyclic. For any argument ∈ , the complexity of Fastgr() depends on the number of attacks (direct and indirect) to , i.e. ().

4. Related Work and Conclusion

In [ 18 ], the complexity of computing the acceptability probability of an argument has been done for different semantics and the result for the grounded is FP # -complete. Having such a high complexity, the work in [ 19 ] proposed some restriction on the value of the probability to improve the complexity. If the probability is binary 0 or 1, then the probability of acceptance is polynomial in time in the case of grounded semantics. If the probability is ternary 0, 0.5 or 1, then the acceptability probability with the grounded is P-hard. Finally, in [ 20 ] a new fast algorithm to compute the ground extension has been proposed for classic AF. It could be interesting to study how this algorithm can be extended to PrAF.

The constellations approach [ 13 ] suffers of a high complexity due to the exponential number of generated worlds. In order to tackle this, we propose to compute the acceptance probability of an argument with a new function, which is able to give the same score in linear time when we curb to uncontroversial acyclic PrAFs. As future work, we will investigate how to extend this function to controversial and cyclic PrAFs, then how to compute the probability of acceptance of a set of arguments, and finally how to extend it to other semantics.

References

[1] Q. Zhong , X. Fan , X. Luo , F. Toni , An explainable multi-attribute decision model based on argumentation , Expert Systems Applications 117 ( 2019 ) 42 - 61 .

[2] N. Hadidi , Y. Dimopoulos , P. Moraitis , Argumentative alternating offers , in: Proceedings of the international conference on Autonomous Agents and Multi-Agent Systems (AAMAS'10) , 2010 , pp. 441 - 448 .

[3] K. Cˇ yras, A . Rago , E. Albini, P. Baroni , F. Toni , Argumentative xai: a survey , arXiv preprint arXiv:2105.11266 ( 2021 ).

[4] P. M. Dung , On the Acceptability of Arguments and its Fundamental Role in Non-Monotonic Reasoning, Logic Programming and n-Person Games , Artificial Intelligence 77 ( 1995 ).

[5] A. Cohen , S. Gottifredi , A. J. García , G. R. Simari , A survey of different approaches to support in argumentation systems , The Knowledge Engineering Review 29 ( 2014 ) 513 - 550 .

[6] V. David , Dealing with Similarity in Argumentation , Ph.D. thesis , Université Paul SabatierToulouse III, 2021 .

[7] L. Amgoud , V. David , Measuring similarity between logical arguments , in: 16th International Conference on Principles of Knowledge Representation and Reasoning , 2018 .

[8] L. Amgoud , V. David , D. Doder , Similarity measures between arguments revisited , in: G. Kern-Isberner , Z. Ognjanovic (Eds.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 15th European Conference , ECSQARU, 2019 , pp. 3 - 13 .

[9] L. Amgoud , V. David , A General Setting for Gradual Semantics Dealing with Similarity , in: 35th AAAI Conference en Artificial Intelligence (AAAI 2021 ), 2021 .

[10] J. Leite , J. Martins , Social abstract argumentation , in: T. Walsh (Ed.), Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI'11) , 2011 , pp. 2287 - 2292 .

[11] P. E. Dunne , A. Hunter , P. McBurney , S. Parsons , M. J. Wooldridge , Weighted argument systems: Basic definitions, algorithms , and complexity results, Artif. Intell . ( 2011 ) 457 - 486 .

[12] L. Amgoud , J. Ben-Naim , Evaluation of arguments in weighted bipolar graphs , International Journal of Approximate Reasoning 99 ( 2018 ) 39 - 55 .

[13] H. Li , N. Oren , T. J. Norman , Probabilistic argumentation frameworks , in: International Workshop on Theorie and Applications of Formal Argumentation, Springer, 2011 , pp. 1 - 16 .

[14] A. Hunter , A probabilistic approach to modelling uncertain logical arguments , International Journal of Approximate Reasoning 54 ( 2013 ) 47 - 81 .

[15] G. Charwat , W. Dvorˇák, S. A. Gaggl , J. P. Wallner , S. Woltran , Methods for solving reasoning problems in abstract argumentation-a survey , Artificial intelligence 220 ( 2015 ) 2 .

[16] T. Mantadelis , S. Bistarelli , Probabilistic abstract argumentation frameworks, a possible world view , International Journal of Approximate Reasoning 119 ( 2020 ) 204 - 219 .

[17] S. Bistarelli , F. Santini , A definition of sceptical semantics in the constellations approach , in: International Conference on Logic Programming and Nonmonotonic Reasoning , 2022 .

[18] B. Fazzinga , S. Flesca , F. Parisi , On the complexity of probabilistic abstract argumentation frameworks , ACM Transactions on Computational Logic (TOCL) 16 ( 2015 ) 1 - 39 .

[19] X. Sun , B. Liao , Probabilistic argumentation, a small step for uncertainty, a giant step for complexity , in: Multi-Agent Systems and Agreement Technologies , Springer, 2015 .

[20] S. Nofal , K. Atkinson , P. E. Dunne , Computing grounded extensions of abstract argumentation frameworks , The Computer Journal 64 ( 2021 ) 54 - 63 .