This work presents an overview of a research project focused on R&D for approximate query answering in probabilistic structured argumentation based on DeLP [2]. The ultimate goal is to develop a suite of algorithms for tackling the computational cost of this task and selection criteria for choosing the best one based on the analysis of available information. In the rest of this section, we brie y present the basics of DeLP3E knowledge bases.
Analytical Model (AM)
and Presumptions ∪ ∪ ∪
Arguments Dialectical Process
Annotation Function(AF) : Ω ∪ Θ ∪ Δ ∪ Φ →
Environmental Model
(EM) Worlds ... ( ) 1 2 3 …
T T T … T
0.47 T T T … F 0.15 T T T … T 0.05 … … … … …
… 1024 F F F … F 0.003
Probabilistic Model is denoted with WEM . In the same way, the set of all subsets of elements of PAM (subprograms) is called
WAM . Intuitively, given PAM , every element of (rules, facts or presumptions) only holds in certain worlds in the , i.e., these elements are subject to probabilistic events. Each element is thus associated with a formula over the set of all ground elements of PEM (using conjunction, disjunction, and negation, as usual). The notion of annotation function implements this association.
In order to answer a query for a literal of interest, we need to compute the probability interval with which it is warranted in the DeLP3E KB|for this, we must sum the probability mass of the worlds that generate subprograms where the queried literal is warranted (warranting scenarios, for the lower bound) and the mass worlds whose generated subprogram warrants the complement of the query (for the upper bound). The lower and upper bounds obtained in this manner comprise the probability interval for the query. This is one of the main sources of computational intractability, since we must answer the query either present two approaches that we analyze to tackle this intractability. for all the worlds in WEM or all the programs in WAM . In Section 2, we will
Next, we present a simple example to illustrate the DeLP3E KB components and show how the probability interval is calculated for a given query. A Simple Example. Consider a small KB, with components PEM , PAM , and af as shown in Figure 2.
For the environmental model PEM , we use a very simple Bayesian network that describes relationship between the nodes a, b and c (EM elements); we omit a b
c
: ;
: 1 = l1
: 1 = l5 |< l3
2 = l2 |< l4
3 = l2 |< l3
: 1 = l3 |<
2 = l4 |<
af(
The domain knowledge in the analytical model PAM is represented by the DeLP program P = [ [ [ (see Figure 2 bottom left). In that program, there is an empty set of strict rules = ;, only one fact = f 1g, two presumptions = f 1; 2g and three defeasible rules = f 1; 2; 3g. The annotation function af (Figure 2 bottom right) associates elements of P with probabilistic events through formulas. As shown, in this example, almost every element hold in every world (annotated as true), whereas for rule 1 the annotation means that this presumption only holds in worlds which the formula a (probabilistic event a) is satis ed, and the annotation for rule 1 means that this rule only holds in worlds in which the formula b _ c, that relates the probabilistic events b and c, is satis ed.
To answer a query, consider for example the literal l2. To compute the associated probability interval, we need to obtain the warranting scenarios for both l2 (for the lower bound) and its complement l2 (for the upper bound). It is easy to check that the condition for the former is that a does not hold, which yields the set of worlds f 5; 6; 7; 8g; it is also easy to check that there are no warranting scenarios for L2. Therefore, the lower bound is calculated by summing P8
i=5 Pr( i) = 0:7, while the upper bound is simply 1, so the answer to the query is Pr( l2) 2 [0:70; 1]. 7
5 14 … 9 A well-known technique to address intractability in this kind of situation is to sample a subset of the solution space in order to arrive at an approximate answer. In this case, we can consider two types of sampling: world-based and subprogram-based, as illustrated in Figure 3. In world-based sampling, a subset of the possible EM worlds are chosen and, based on the annotation function, di erent subprograms of PAM are obtained (as shown in Figure 1). So, each PAM ( ) is a classical DeLP program [2] in which we can query for the status of some literal. On the other hand, subprogram-based sampling divides the universe of all possible subprograms into regions that represent programs that warrant the query or its complement. Each of these programs can be generated by multiple worlds through their annotations.
In both cases, we also have those worlds or programs in which the status of the query can be \undecided" or \unknown". The objective is to sum the probability value corresponding to the green and red worlds (circles in the gure); that is, those that are warranting scenarios for the query and its complement, respectively. Given the incomplete nature of the process, some probability mass will remain unexplored (the white elements in Figure 3).
A Family of KB Metrics. In order to de ne a suite of sampling algorithms to approximate the answer to a probabilistic query in the most e cient and e ective way possible, we must consider what metrics we have available for the input KB. Figure 4 shows a set of such possible metrics, organized with respect to the component they apply to, and what attribute they are designed to measure. For each one, we also analyze whether or not they can be tractably computed (observable column) or approximated.
For each component (or submodel of the KB), we can focus on two main attributes: size and complexity. For PAM , #Rules and #Facts refers to the total number of di erent rules and facts in the DeLP program, respectively. Regarding the complexity component, the MDDL metric refers to the maximum defeasible derivation length, i.e., the maximum number of defeasible rules present in any argument constructed from the program. In a similar vein, h refers to Component
PAM PEM AF
Attribute Example Metric
Size ##RFaucletss
MDDL
#RandomVars #PGM Arcs PGM TW Entropy %AF ann AF Comp
Yes Yes { { { Yes Yes { { Yes Yes
{ { Yes Yes Yes { { Yes
the maximum length of an argumentation line (a sequence of arguments where each element of the sequence defeats its predecessor), and is the number of dialectical trees (a tree structure formed by all argumentation lines arising from one argument) for each literal in the program [2].
On the other hand, for PEM , #RandomVars refers to the number of random variables in the model (for instance, nodes in a BN), while #PGM Arcs refers to the number of arcs in a probabilistic graphical model (PGM) [4]. The metric PGM TW refers to the treewidth of a PGM (such as a BN), which intuitively measures how \close to a tree" a graph is; approximations for this metric can be computed [3], but the exact value cannot be tractably calculated for very large models. The entropy metric is inherent to the joint probability distribution function represented by PEM , and it is possible to approximate it in some particular scenarios [1].
Finally, for annotation functions (AF) an example metric for the size attribute is %AF ann, which refers to the percentage of formulas of the program that are annotated. For the complexity attribute, metric AF Comp refers to the complexity of each annotation itself (that is, which operators can be used, if nesting is allowed, etc.).
Towards a Suite of Approximation Algorithms. Based on the information obtained using these metrics, we can begin to explore the possible alternatives for deriving sampling-based approximation algorithms. For example, consider a scenario in which we have 10 elements in the PAM (#Rules + #Facts) and 50 in the PEM (#RandomVars), and AF Comp is low (only one variable from PEM is used in the annotations, without operators). Here, we can approximate the probability of a query by sampling subprograms, since the number of subprograms will be smaller in comparison with the number of worlds (210 < 250), and the annotations associated with subprograms are simple to evaluate (conjunctions of variables or their negation). On the other hand, if the annotations are complex (they use several variables, connectors and negations, for example af (!1) = a _ b ! :c) then sampling by worlds is simpler (even if there are more elements in PEM than rules in PAM ). This is because the task of obtaining the subprogram is simple (substitute the random variable values according to the sampled world and evaluating the annotation formula, then query for the literal in the generated program) compared to computing the probability of a complex expression in the EM.
Note that the examples mentioned above expose a kind of asymmetry between the PAM and the PEM |even though given a world it is only possible to generate a single program, a program can be generated by a set of worlds (since the formulas in the annotations can have more than one model). This can be observed also in Figure 3. Consider a case in which the PEM is a BN with high values of treewidth and entropy|for example, 5 (complex structure) and 14, respectively|meaning that the network is far from a tree structure and that the underlying probability distribution has a high degree of uncertainty. This leads to a slower, more complex, and less guided sampling process; therefore, an algorithm to sample worlds randomly is not recommended, and in this case it is better to decide in a previous step which worlds to sample (such as weighted sampling given the BN), in order to optimize resources.
These examples show the variety of possible approaches to approximate query answering in probabilistic DeLP. Our ultimate goal is to develop a set of decision criteria that allow to select the best algorithm for the job, contemplating the inherent tradeo s between running time (including the cost of calculating any necessary approximate metrics) and precision of the result obtained. 3
In this work we presented a preliminary study of the aspects that must be considered when developing a family of approximation algorithms for query answering in the DeLP3E framework. Ongoing and future work consists of developing approximation algorithms that can handle large instances based on the criteria initially explored here, and implement them in the DAQAP platform [5]. In order to do this e ectively, we are developing procedures for automatically generating DeLP3E KBs in order to simulate di erent scenarios, running a suite of approximation algorithms over them, and evaluating their performance. Other approaches currently being evaluated are the application of machine learning techniques to sample in a guided way during the approximation process. Acknowledgments. This work was supported by funds provided by Universidad Nacional del Sur (UNS) under grants PGI 24/N046 and PGI 24/ZN34), Agencia Nacional de Promocion Cient ca y Tecnologica under grant PICT-20180475 (PRH-2014-0007), and CONICET under grant PIP 11220170100871CO.
proach. TPLP 4(
& Business Media (1994)
MIT press (2009) 5. Leiva, M.A., Simari, G.I., Gottifredi, S., Garc a, A.J., Simari, G.R.: DAQAP: defeasible argumentation query answering platform. In: Proc. FQAS 2019. LNCS, vol. 11529, pp. 126{138. Springer (2019)
ence. Elsevier (2014)
107{136 (2006)
and Arti cial Intelligence 78(3-4), 259{301 (2016)