We present VisPrAF, a system supporting the usage of probabilistic abstract argumentation for modeling disputes in the presence of uncertainty. VisPrAF provides a user-friendly graphical interface for specifying the possible scenarios (in terms of sets of arguments and attacks occurring in the dispute) and their probabilities. Moreover, it provides a reasoning engine that allows the analyst to evaluate the probabilities of extensions and acceptable arguments. Both the graphical interface and the reasoning engine consider the most popular paradigms for modeling prAAFs, and they allow the use of simple constructs for specifying typical correlations between arguments/defeats (such as co-existence and mutual exclusivity) that can make the specification of intricate scenarios intuitive and compact.
In the literature, there are several proposals for modeling the uncertainty of
arguments/defeats in Dung’s Abstract Argumentation Frameworks (AAFs), using
di↵erent paradigms (e.g., weights, preferences, probabilities). In this regard, [
Example 1. Mary and Marc’s defense attorney is reasoning on the trial of a robbery case involving her clients and the witness Ann. The arguments are: a: “Mary says that she was at the park at the time of the robbery, and thus denies being involved in the robbery”; Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0). b: “Marc says he was at home when the robbery took place, and therefore denies being involved in the robbery”; c: “Ann says that she certainly saw Mary near the bank just before the robbery, and possibly saw Marc there too”.
The dispute can be modeled by the AAF A, whose arguments are {a, b, c}, and whose defeats are ac = (a, c), ca = (c, a), bc = (b, c) and cb = (c, b), meaning that arguments a and b are attacked by c and they counter-attack c.
The lawyer believes that the arguments/defeats are not certain, and that the only scenarios (i.e., combinations of arguments/defeats) that may happen are: S1: “Ann does not testify”; S2: “Ann testifies, and the jury will deem that her argument c undermines Mary and Marc’s arguments a, b, and vice versa”; S3: “Ann testifies, and the jury will deem that her argument c undermines Mary and Marc’s arguments a, b, while, owing to the bad reputations of Mary and Marc, a and b will be not perceived as strong enough to undermine c”; S4: “Ann testifies, and the jury will deem that argument c undermines argument a but not b, as Ann is uncertain about Marc’s presence. Vice versa, a and b will be not perceived as strong enough to undermine c”.
The hypothesis of the lawyer can be modeled by using the paradigm ex, according to which the possible scenarios (each consisting of a “traditional” AAF) must be enumerated, and each of them must be assigned the probability that it represents the case that occurs in practice. In our example, each Si is encoded by the AAF ↵ i in the following list: ↵ 1 = h{a, b}, ;i , ↵ 2 = h{a, b, c}, { ac, ca, bc, cb}i, ↵ 3 = h{a, b, c}, { ca, cb}i, ↵ 4 = h{a, b, c}, { ca}i. Then, on the basis of the lawyer’s perception of how likely each scenario is, the probability distribution function over the possible scenarios could be: P (↵ 1) = 0.1 and P (↵ 2) = P (↵ 3) = P (↵ 4) = (1 P (↵ 1))/3 = 0.3, meaning that the lawyer thinks that there is 10% probability that Mary will not testify (owing to her ill-health), and that, if she testifies, the other scenarios are equi-probable.
Otherwise, assume that the lawyer still believes that the arguments/defeats are uncertain, but also that there is no correlation between the terms of the dispute. Then, instead of using ex, which would require to explicitly enumerate too many scenarios (corresponding to all the possible combinations of arguments/defeats), the adoption of the paradigm ind is more suitable: what is required to define the prAAF according to ind is the marginal probability of the terms of the dispute. For instance, the lawyer may set P (c) = 0.9 (meaning that there is 10% probability that Mary will not testify) and P (a) = P (b) = 1 (meaning that Mary and Marc will certainly testify). Moreover, she/he could set P ( ca) = 1 (meaning that she/he is certain that the jury will consider Ann’s argument as a solid rebuttal of Mary’s argument). Analogously, she/he could set P ( cb) = 0.8 and P ( ac) = P ( bc) = 0.4. Given this, since the arguments are considered independent, the possible scenarios modeled by ind are all the AAFs hAi, Dii where Ai is a subset of the arguments and Di a subset of the defeats between the arguments in Ai. Specifically, there are 9 possible AAFs, where 4 out of 9 are equal to ↵ 1, . . . ↵ 4 of the previous example, and the others are ↵ 5 = h{a, b, c}, { ac, ca}i, ↵ 6 = h{a, b, c}, { ca, bc}i, ↵ 7 = h{a, b, c}, { ca, cb, ac}i, ↵ 8 = h{a, b, c}, { ca, cb, bc}i, ↵ 9 = h{a, b, c}, { ca, ac, bc}i. The probability of each AAF hA, Di is a product, whose factors are the probabilities (resp., the complements of the probabilities) of the arguments in A (resp., not in A) and of the defeats in D (resp., not in D). For instance, P (↵ 1) = P (a) ⇥ P (b) ⇥ (1 P (c)) = 0.1 and P (↵ 3) = P (a) ⇥ P (b)⇥ P (c) ⇥ P ( ca) ⇥ P ( cb) ⇥ (1 P ( ac)) ⇥ (1 P ( bc)) = 0.26. 2
More recently, in [
Contribution. We here introduce VisPrAF, a system that supports the
specification and the reasoning over prAAFs. In fact, VisPrAF provides both a
visual interface for specifying the possible scenarios and their probabilities, and
a reasoning engine, that is able to solve the probabilistic counterparts of the
verification problem (i.e., “what is the probability that a set of arguments is an
extension?”) and the acceptability problem (i.e., “what is the probability that
an argument a is acceptable?”). VisPrAF allows the user to select the paradigm
to be adopted for representing the prAAF. Besides ex, ind and gen, it also gives
the possibility to choose a fragment of gen, called mon⇤ , where typical
correlations (in particular, co-existence and XOR relationships) can be still specified. In
this regard, an ad-hoc interface for mon⇤ is provided, where simplified graphical
constructs can be used, so that even intricate prAAFs can be defined intuitively
and compactly. As for the reasoning engine, its algorithms work under the most
popular semantics of extensions, and their implementation derive from the
results in [
A set S ✓ A of arguments is said to be conflict-free if there are no a, b 2 S such that a defeats b. An argument a is said to be acceptable w.r.t. S ✓ A i↵ 8 b 2 A such that b defeats a, there is c 2 S such that c defeats b.
An extension is a set of arguments that is considered “reasonable” according to some semantics. In particular, we consider the following popular semantics from the literature: – admissible (ad): S is an admissible extension i↵ S is conflict-free and its arguments are acceptable w.r.t. S; – stable (st): S is a stable extension i↵ S is conflict-free and S defeats each argument in A \ S; – complete (co): S is a complete extension i↵ S is admissible and every argument acceptable w.r.t. S is in S; – grounded (gr): S is a grounded extension i↵ S is a minimal (w.r.t. ✓ ) complete set of arguments; – semi-stable (sst): S is a semi-stable extension i↵ S is a complete extension where S [ S+ is maximal (w.r.t. ✓ ); – preferred (pr): S is a preferred extension i↵ S is a maximal (w.r.t. ✓ ) complete set of arguments; – ideal-set (ids): S is an ideal-set extension i↵ S is admissible and S is contained in every preferred extension; – ideal (ide): S is an ideal extension i↵ S is a maximal (w.r.t. ✓ ) ideal-set extension.
An argument a is acceptable w.r.t. a semantics sem i↵ a belongs to some sem extension. Given an AAF, a semantics sem, a set of arguments S and an argument a, the fundamental problems of verifying whether S is a sem extension and whether a is acceptable (w.r.t sem) will be denoted as Extsem(S) and Accsem(a), respectively. 3
A well-established way of modeling uncertainty in abstract argumentation is that of considering the alternative possible scenarios, and assigning probabilities to them. Basically, given a set A of possible arguments and a set D of possible defeats, each scenario (called “possible AAF ”) is an AAF whose arguments and defeats are subsets of A and D that can be viewed as a hypothesis on which arguments/defeats will actually occur in the dispute. Thus, a probabilistic AAF is a tuple F = hA, D, ↵ , P i where ↵ = ↵ 1, . . . , ↵ m is a set of possible AAFs taking arguments and defeats from A and D, while P is a probability distribution function (pdf) over ↵ such that P (↵ ) represents a measure of how likely the arguments and defeats occurring in the dispute are exactly those in ↵ .
Several forms of prAAFs exist in the literature, di↵ering in the paradigm used to encode the pdf P : di↵erent paradigms have di↵erent expressiveness, and this influences the correlations that can be imposed between arguments/defeats. 3.1
ex is a form of prAAF (at the basis of the frameworks in [
In the prAAF of form ex of Example 1, A = {a, b, c}, D = { ca, cb, ac, bc}, ↵ = [↵ 1, . . . , ↵ 4] and P is such that P (↵ 1) = 0.1, P (↵ 2) = P (↵ 3) = P (↵ 4) = 0.3. 3.2
In prAAFs of form ind [
In [
In our context, the set ↵ of possible AAFs and the pdf P over them can be easily represented by associating each argument/defeat x with a wss: this wss describes the set of possible worlds where x occurs, and the probability of each possible AAF ↵ is the overall probability of the possible worlds containing the arguments/defeats in ↵ .
The major benefit of using the paradigm gen is that it is as expressive as ex, as it allows any pdf to be encoded, but it is more compact (there is no P that requires a longer encoding in gen than in ex, while in several cases the encoding in gen is strictly shorter than in ex). Compared with ind, gen is more expressive, and when used to represent the independence between arguments/defeats, it is as compact as ind. From a “modeling” perspective, resorting to gen can make it easier to specify the correlations between the arguments/defeats: for instance, the co-existence between two arguments can be expressed by associated the same wss to them, while an XOR relationship can be expressed by associating them with wsss with empty intersection. Example 2. Consider the set of arguments A = {a1, a2, a3, a4} and the set of defeats D = { 13, 23, 34} (where ij denotes a defeat from ai to aj ). Assume that the possible scenarios are only those satisfying these conditions: 1) a4 is in every possible scenario (i.e., it certainly occurs in the dispute); 2) the occurrence of a1, a2, a3 is uncertain: however, they must co-exist, and the probability of their occurrence is 0.8; 3) analogously, 13 and 23 are uncertain and must co-exist: the probability that they occur (conditioned to the occurrence of the involved arguments a1, a2, a3) is 0.6; 4) the occurrence of 34 is conditioned only on the occurrence of a3 and a4, and the probability of its occurrence (given the presence of a3 and a4) is 0.5. This means that the possible scenarios are: ↵ 1 = h{a4}, ;i , with P (↵ 1) = 1·(1 0.8) = 0.2; ↵ 2 = h{a1, a2, a3, a4}, ;i , with P (↵ 2) = 1·0.8·(1 0.6) · (1 0.5) = 0.16; ↵ 3 = h{a1, a2, a3, a4}, { 12, 23}i, with P (↵ 3) = 1 · 0.8 · 0.6 · (1 0.5) = 0.24; ↵ 4 = h{a1, a2, a3, a4}, { 34}i, with P (↵ 4) = 1·0.8·(1 0.6)·0.5 = 0.16; ↵ 5 = h{a1, a2, a3, a4}, { 12, 23, 34}i, with P (↵ 5) = 1 · 0.8 · 0.6 · 0.5 = 0.24.
This case can be represented by a prAAF of the form gen defined as follows. The set V contains the binary random variables X123, X4, Y13,23, Y34, and the possible scenarios where the arguments/defeats occur are defined via the following function , associating each argument/defeat with a wss: (a1) = (a2) = (a3) = {X123 = 1} ; (a4) = {X4 = 1} ; ( 12) = ( 23) = {Y13,23 = 1} ; ( 34) = {Y34 = 1} . Then, the pdf over the possible scenarios defined above can be modeled by defining the following probability distributions for the random variables in V : P (X123 = 1) = 0.8 (thus P (X123 = 0) = 0.2); P (X4 = 1) = 1 (thus P (X123 = 0) = 0); P (Y13,23 = 1) = 0.6 (thus P (Y13,23 = 0) = 0.4); P (Y34 = 1) = P (Y34 = 0) = 0.5. 2 3.4
In the probabilistic setting, Extsem(S) and Accsem(a) naturally turn into the functional problems P-Extsem(S) and P-Accsem(a) of evaluating the probabilities P sem(S) that S is an extension and P sem(a) that a is acceptable, respectively. In particular, these probabilities are the sums of the probabilities of the possible AAFs where these properties hold.
In the complexity analysis performed in [
sem ad, st, co, pr gr sst
Accsem(a)
(from literature)
NP-c
P ⌃ p2-c
P-Accsem(a) ind ex gen, ind-a, ind-d FP||NP -c
FP FP#P -c in FP||⌃ p2 , FP#P -c
FP||NP -h
FP||NP -c ids, ide in ⇥ 2p, coNP-h
Table 2: Complexity of Accsem(a) and P-Accsem(a) and gen the possible AAFs are implicitly defined by the marginal probabilities and the wsss, respectively. Hence, solving a problem over ex may benefit from saving a “level of exponentiality”, compared with gen or ind.
Another interesting point is that the presence of di↵erent forms of correlations has an impact on the complexity of P-Extsem(S) under the admissible and stable semantics. In fact, in these cases, P-Extsem(S) can be polynomially solved when defeats are independent, and correlations (in terms of co-existence and XOR constraints) are expressed between arguments (see column ind-d in Table 1). Interestingly, switching things, by making arguments independent and defeats correlated, makes the complexity explode. Observe that this is not implied by the fact that Extsem(S) is in P under sem 2 { ad, st}. In fact, P-Extsem(S) over ind-d is F P #P -complete under the complete and the grounded semantics, under which Extsem(S) is polynomially decidable. As for P-Accsem(a), it is already F P #P -complete under every semantics over ind. However, the result that P-Accsem(a) over gen is still in F P #P implies that imposing correlations does not further increase the complexity. 4
In this section we describe the main features of the VisPrAF GUI that enables the visual specification of prAAFs. The construction of a prAAF in the VisPrAF GUI is tightly coupled with the type of the prAAF to be represented. A preliminary step for the user willing to define a prAAF consists in specifying the AAF containing all the arguments and the defeats that occur in at least one scenario. The interface for specifying the AAF is reported in Figure 1(a). The designer can add arguments and attacks 1, and can specify for each argument its name and a description. It is possible to remove both arguments and attacks, and to save/load the AAF. The AAF in Figure 1(a) consists of the arguments and defeats described in Example 2.
After drawing the AAF, the user can specify the list of possible scenarios and the pdf over them. To do this, the user is asked to choose the form of prAAF he/she intends to use. Four alternative forms are available: ex, ind, gen and mon*, where mon* is a visually expressible restriction of gen that is described in the following (Section 4.1). For each form, an ad-hoc interface is provided to the user, and in what follows we briefly describe the main characteristics of each interface.
The interface for ind. The interface for ind displays the AAF defined in the preliminary step and allows the user to specify the marginal probabilities (thus obtaining a prAAF of the form ind) by simply clicking on any attack/defeat and then inserting its probability (see Figure 1(b)).
The interface for ex. The GUI for specifying a prAAF of type ex is shown in Figure 2. In this figure, the prAAF admits five alternative scenarios, that are 1 The GUI allows us to specify supports between arguments too. This extension is not described in the paper. those described in Example 2. The user can define each scenario by selecting its arguments and attacks from the AAF defined in the preliminary step, and can assign a probability to each scenario. The designer is given the possibility to revise existing scenarios by adding arguments/attacks that were not included in it (possibly changing the AAF defined in the preliminary step) or by removing arguments/attacks.
The interface for gen. The specification of a prAAF of type gen requires the explicit definition of the set V of the independent random variables that will occur in the ws-sets and the lambda functions. The variables in V and their pdfs must be encoded as entries in the so called “world table”: for each variable x 2 V , and for each value v in the domain of x, the world table contains a triple (x, v, p) where p is the probability that the value of x is v. The GUI allows the user to import the AAF defined in the preliminary step (see Figure 3(a)) and then to define the world table and the lambda functions as shown in Figure 3(b), that is a screenshot of the final phase of the definition of the prAAF of type gen of Example 2.
When inserting a new random variable into the world table, the user is asked to specify its name and the size of its domain (see Figure 4(a)) along with the probabilities associated to the values in the domain (see Figure 4(b)). Then, for each argument/attack in the prAAF, the user is asked to associate it with a ws-set (see Figure 5(b)), and this is done by specifying the ws-descriptors in it (see Figure 5(a)).
As highlighted in Section 3.3, the form gen exhibits a nice trade-o↵ between
expressiveness and compactness, as its paradigm for encoding the pdf over the
possible AAFs allows any pdf to be represented, while being exponentially more
succinct than ex. Indeed, the price to be paid for this combination of
expressiveness and compactness is the fact that gen may not be user-friendly: the
user must be able to encode the pdf according to the ws-set paradigm, and this
requires to choose and enumerate suitable random variables and to properly
define their probabilities distributions. However, in many situations the entire
expressive power of gen may not be useful: several typical correlations (such as
coexistence and mutual exclusivity) can be expressed without exploiting all the
possibilities provided by the ws-set paradigm. For instance, consider Example 2.
Here, the possible scenarios are those resulting from imposing the co-occurrence
of arguments a1, a2 and a3, and the co-occurrence of defeats 13 and 23. By
looking into the definition of function in Example 2, this can be specified by
associating every argument/defeat with a ws-set satisfying these properties: the
random variables occurring in the ws-descriptors are binary, and every ws-set
consists of exactly one ws-descriptor, that in turn contains exactly one valuation.
It can be shown that these restrictions suce to express also mutual exclusivity
between arguments/defeats [
In this regard, our contribution is the design and implementation of a GUI allowing the user to easily define a prAAF satisfying these restrictions of gen. By means of this GUI, the user can define a prAAF without being asked to enumerate the scenarios (which is required by the visual interface for ex) and without being asked to list the random variables, their pdfs and ws-sets (which is required by the GUI for the unrestricted gen). The user is only asked to edit the argumentation graph containing all the possible arguments and defeats and to augment it as follows: arguments and defeats must be enriched with their marginal probabilities and co-existence and XOR relationships between must be specified by means of intuitive graphical constructs. The graphical representation produced by the user is automatically and transparently translated by VisPrAF into a prAAF of form gen conforming to the “monadicity” described above. We call mon⇤ the restricted form of gen definable via the GUI provided by VisPrAF.
In particular, the augmented graph definable by the user graph has the following characteristics (see Figure 6): – the nodes represent the arguments and the arcs the defeats; they are both labeled with their marginal probabilities; – nodes and arcs can be pairwise connected by means of red lines labeled with “AND ” or dashed green lines labeled with “XOR”. AND and XOR lines denote a co-existence and a XOR relationships between the connected arguments/defeats, respectively; thus, for arguments/defeats linked by dotted lines marked with AND or XOR, their probabilities are due to be equal or complementary, respectively.
Remarkably, this way of specifying correlations and probabilities resembles the way of assigning probabilities that is used in ind (which is very user-friendly, since the user may reason on the probability of each term of the dispute separately from the others), while allowing common types of correlations to be specified, thus overcoming a limit in expressiveness of ind.
Fig. 6 shows how the prAAF of form mon⇤ of Example 2 can be drawn by means of VisPrAF : the AND lines connecting a1 and a2 with a3 encode the co-existence of these three arguments, while the XOR line encodes the mutual exclusivity between the attacks (a1, a3) and (a2, a3). The semantics of the graph drawn with the GUI is obtained by assuming independence wherever not explicitly specified through co-existence and XOR constraints. For instance, the fact that the node a4 in the graph of Figure 6 is connected to no argument via AND/XOR lines means that argument a4 is independent from all the other arguments (this independence would hold even if a4’s probability were not 1). The translation into a prAAF of form mon⇤ is computed by VisPrAF applying these simple rules: the co-existence constraints are translated into associating the involved arguments/defeats with the same ws-set, while XOR constraints into associating the two involved argument/defeats with alternative values of the same variable. Independent arguments/defeats are instead associated with ws-sets with distinct variables. The reader can see from the screenshot in Fig. 6 that the translation into a prAAF of the graph drawn by the user is shown by VisPrAF besides the graph itself: the right-hand side of the window contains both the world table and the function (mapping arguments/defeats to ws-sets) automatically computed by VisPrAF.
The reasoning engine of VisPrAF comprises a set of algorithms for supporting the analysis of the dispute modeled by a prAAF. In particular, algorithms solving the two fundamental problems P-Accsem(a) and P-Extsem(S) are provided. The algorithms can be invoked from the same GUI used to define the prAAF: after specifying the details of the prAAF, the user can select a set S of arguments (resp., a single argument a) and then choose an algorithm in the library evaluating the probability that S is an extension (resp., a is acceptable).
The prAAF given as input to the solvers can be of any of the forms ex, ind, gen, mon⇤ . The input is encoded as an XML document conforming to a specific DTD, that is the format of the output of the module of VisPrAF providing the graphical interface for defining a prAAF. Figure 7 reports the DTD describing the structure of the document encoding a prAAF of the form gen: the root element ARGUMENTATION contains the element2 BAF, encoding the set of possible arguments/defeats, and the element GEN, containing the definitions of the world table and the lambda function associating arguments/defeats with ws-sets.
The algorithms for solving P-Accsem(a) and P-Extsem(S) derive from the
study of complexity presented in [
The library of algorithms is under implementation, and all the semantics
listed in Section 2 are supported. Moreover, the library is currently being
augmented with approximate Monte Carlo-based algorithms for estimating the
probabilities asked by P-Extsem(S) and P-Accsem(a) [
We have presented the main features of VisPrAF, a tool aiming at making the use of probabilistic abstract argumentation a realistic choice for modeling and analyzing disputes where the presence of arguments and defeats is characterized by some uncertainty. VisPrAF is under implementation: at the moment, the prototype provides a user-friendly visual interface for “drawing” a prAAF and allows the user to choose the form of prAAF most suitable for her/his needs. VisPrAF also embeds algorithms for solving the fundamental problems P-Extsem(S) and P-Accsem(a) behind the reasoning over prAAFs (i.e., evaluating the probability of extensions and of acceptable arguments): the most popular semantics of extensions in the literature are considered and di↵erent strategies are implemented depending on the form of prAAF. Future work will be devoted to introducing approximate algorithms for enhancing the eciency of the computation of hard cases of P-Extsem(S) and P-Accsem(a).