We present approximation algorithms for reasoning in structured argumentation approaches such as ASPIC+. While classical approaches consist in constructing all arguments from a knowledge base and determine acceptable arguments from the resulting argument graph, we sample only a small number of arguments and thus only consider a subgraph of the complete argument graph. We develop two approaches for sampling arguments, one which samples arguments independently and one which samples arguments dependently on a query. We present results of an extensive experimental evaluation that showed that runtime can be drastically reduced while the accuracy is only marginally a ected.
Structured argumentation approaches consider arguments to be collections of
formulas and/or rules which entail some conclusion. The most prominent structured
approaches are ASPIC+ [
In this paper, we are interested in approximate methods to reasoning with
structured argumentation approaches. This means we are investigating methods
that are not necessarily sound and complete in general, but trade correctness for
performance. Our approach is motivated by use cases where the number of rules
is so high|such as rule mining scenarios as mentioned in [
For our investigation, we will focus on the propositional logic instantiation
under the grounded semantics of the general framework ASPIC+ [
To summarise, the contributions of this paper are as follows: 1. We present two novel approximation algorithms for ASPIC+ that rely on sampling arguments (Section 4). 2. We conduct an extensive experimental evaluation of our approaches that show their viability (Section 5).
Moreover, Section 2 recalls necessary preliminaries while Section 3 describes baseline approaches for reasoning with ASPIC+. Section 6 concludes with a summary.
We recall necessary preliminaries regarding abstract argumentation [
elements are called arguments and A A is a binary relation called attack.
We say that a set E A is con ict-free i there are no a; b 2 E s. t. a b.
Moreover, a set E defends an argument a 2 A i for all c 2 A with c a there is
b 2 E with b c. Building on these notions, the basic extension-based semantics
[
De nition 2 Let (A; ) be an argumentation framework. A set E A is said to be admissible i E is con ict-free and for all a 2 E, E defends a; complete i it is admissible and for all a 2 A s. t. E defends a, a 2 E; preferred i E is complete and maximal wrt. set inclusion; grounded i E is complete and minimal wrt. set inclusion; stable i E is con ict-free and for all b 2 A n E there is a 2 E with a b.
Given an argument a 2 A, a is said to be (credulously) accepted under semantics (either complete, grounded, stable, or preferred ) i a is a member of at least one -extension of (A; ).
Structured argumentation approaches can be used to give structure to
arguments. In the following, we present a minimal variant of the propositional
instantiation of ASPIC+ [
Let L be a nite set of propositions and let L^ be the set of literals of L, i. e., L^ = fa; :a j a 2 Lg. For a 2 L de ne a = :a and :a = a. ASPIC+ di erentiates rules into strict rules (rules that are always supposed to hold) and defeasible rules (rules that \usually" hold).
De nition 3 A knowledge base K is a pair K = (Ks; Kd) where • Ks is a set of strict rules 1; : : : ; n ! • Kd is a set of defeasible rules 1; : : : ; n ) with 1; : : : ; n; 2 L^.
with 1; : : : ; n; 2 L^.
A strict rule 1; : : : ; n ! with n = 0 is written as ! and is also called an axiom. A defeasible rule 1; : : : ; n ) with n = 0 is written as ) and is also called an assumption. For practical reasons we often identify K = (Ks; Kd) with Ks [ Kd, e. g., expressions such as \r 2 K" are to be read as \r 2 Ks or r 2 Kd".
Arguments can now be constructed by chaining rules. Following [
De nition 4 The set of arguments AK generated by a knowledge base K = (Ks; Kd) is inductively de ned as follows: • If ) 2 K then () ) is an argument with Prem() ) = f) g, Conc() ) = , Sub() ) = f) g, DefRules () ) = f) g, TopRule() ) = () ). • If ! 2 K then (! ) is an argument with Prem(! ) = f! g, Conc(! ) = , Sub(! ) = f! g, DefRules (! ) = ;, TopRule(! ) = (! ). • If 1; : : : ; n ) 2 K and A1; : : : ; An are arguments such that 1 = Conc(A1); : : : ; n = Conc(An), then A = (A1; : : : ; An ) ) is an argument such that: Prem(A) = Prem(A1) [ : : : [ Prem(An), Conc(A) = , Sub(A) = Sub(A1) [ : : : [ Sub(An) [ fAg, DefRules (A) = DefRules (A1) [ : : : [ DefRules (An) [ f 1; : : : ; 1 ) g, TopRule(A) = 1; : : : ; n ) . 2Note also that we depart from ASPIC+ terminology at times.
Thimm and Rienstra / Approximate Reasoning with ASPIC+ by Argument Sampling 25 A4
A6
A3
A5
A2
A1 • If 1; : : : ; n ! 2 K and A1; : : : ; An are arguments such that 1 = Conc(A1); : : : ; n = Conc(An), then A = (A1; : : : ; An ! ) is an argument such that: Prem(A) = Prem(A1) [ : : : [ Prem(An), Conc(A) = , Sub(A) = Sub(A1) [ : : : [ Sub(An) [ fAg, DefRules (A) = DefRules(A1) [ : : : [ DefRules(An), TopRule(A) = 1; : : : ; n ! .
An argument A is called strict if DefRules(A) = ;, otherwise it is called defeasible.
In our simpli ed framework, we only consider rebuts [
as A B, if Conc(A) = a for some B0 2 Sub(A) of the form B100; : : : ; Bn00 ) a. Using the previous two de nitions an abstract argumentation framework can be derived from a knowledge base K as follows.
knowledge base K is an argumentation framework AFK = (AK; ) where AK is the set of arguments generated by K as de ned by De nition 4 and is the attack relation on AK as de ned by De nition 5.
We conclude this section with a small example illustrating our simpli ed ASPIC+ framework.
Example 1 Let K = (Ks; Kd) be a knowledge base with
Ks = f! a; ! c; ! :d; d ! :bg Kd = fa ) b; c ) dg The corresponding abstract argumentation framework is AFK = (AK; ) with AK = fA1; : : : A6g,
A1 = (! a) A4 = (A1 ) b)
A2 = (! c) A5 = (A2 ) d)
A3 = (! :d) A6 = (A5 ! :b) and A3 A5, A3 A6 and A6 A4. AFK is depicted in Figure 1. Note that fA1; A2; A3; A4g is the single grounded, complete, stable, and preferred extension of AFK. It follows that A1; A2; A3; A4 are accepted under these semantics.
As already hinted by De nition 6, reasoning in ASPIC+ is reduced to reasoning in abstract argumentation frameworks. More precisely, given an abstract argumentation semantics (either complete, grounded, stable, or preferred ) as a meta parameter, we say that a literal l 2 L is acceptable wrt. a knowledge base K if there is an argument A of K with Conc(A) = l and A is acceptable under in AFK.3 In Example 1, literals a; c; :d; b are therefore acceptable for all considered semantics .
As the most obvious baseline for the evaluation of our approximate inference
algorithms, we consider a direct implementation of De nition 6 that constructs
all possible arguments of a knowledge base. More concretely, the Naive algorithm
rst constructs all arguments from axioms and assumptions. Then it iteratively
continues by considering each (strict and defeasible) rule and each combination
of already constructed arguments for each literal in the body of that rule. It
terminates once no further argument can be constructed. However, it is clear that
not all arguments from a knowledge base have to be constructed in order to
determine the acceptability of a certain literal. Works such as [
In the following, we present two algorithms that sample arguments in order to obtain a sub-graph of the full corresponding abstract argumentation framework of the knowledge base. We will therefore only modify the part of constructing the argumentation framework, but leave the actual reasoning on the abstract framework untouched. For both algorithms we assume the existence of a function attRel(args) that, given a set of arguments args constructs the attack relation according to De nition 5.
Our rst approach consists in simply sampling some number of arguments independently from all constructible arguments. As the total number of constructible arguments is unknown beforehand (and also hard to determine), we cannot tell the algorithm to sample a certain percentage of the constructible arguments. Thus, the algorithm is parametrised by two values maxArgs and maxDuplicates. The rst value maxArgs restricts the number of distinct arguments to be sampled. As the same argument may be sampled twice (and certainly will if there are actually less constructible arguments than maxArgs) the parameter maxDuplicates sets the 3Note that other variants of acceptability can be de ned.
Thimm and Rienstra / Approximate Reasoning with ASPIC+ by Argument Sampling 27 Algorithm 1 The randI algorithm ^ Premises(r) \ acc = ;g upper bound of how many duplicates can be encountered before the algorithm is terminated, even if maxArgs many arguments have not been sampled.
The algorithm randI is shown in Listing 1 (we only show the part responsible for constructing the abstract argumentation framework). The function genRandI takes as input a knowledge base K and the two parameters maxArgs and maxDuplicates. The sampling of a single argument is implemented by the sampleArgument function. It rst picks a random literal and then attempts to construct an argument for that literal. The construction, implemented by the constructArgument function, rst picks a random rule with the required conclusion, but only if that rule does not contain a premise that already occurs in the argument that is being constructed (this is kept track of by the set acc). It then recursively construct sub-arguments for that rule until the argument is complete. If the construction of an argument fails (this happens if there is no rule for some literal) then constructArgument returns \fail" and the sampling is restarted.
In general, if genRandI terminates, it generates an argumentation framework restricted to a random subset of arguments of size at least 1 (in the rare event that sampleArgument returns the same argument every time) and at most maxArgs (in the event that the number of duplicate arguments never exceeds Algorithm 2 The randD algorithm args [ newArgs maxDuplicates ). However, note that this algorithm may never terminate (theoretically) if at line 14 a literal is repeatedly chosen, for which no argument exists. However, this behaviour was not observed in our experiments (see Section 5).
The directional sampling (randD) algorithm is shown in Listing 2. The following functions are assumed to be de ned: argsWithConc(K; ) returns all arguments A constructible from K with conclusion ; attackingConcs(A) returns all formulas such that, if B is an argument with Conc(B) = then B attacks A; and FLIP(p) returns true (resp. false) with probability p (resp. 1 p).
The algorithm takes as input a knowledge base K, formula , and probability p and is based on initially constructing all arguments for , then the attackers of this set, the attackers of those attackers, and so on. However, for each argument A that is constructed, we rst call FLIP(p), and we generate the attackers of A only if the result is true (line 10). To avoid generating an argument more than once, we use the set argsDone to keep track of arguments whose attackers are generated, and concsDone for conclusions for which arguments are generated.
The result of running randD for a query formula is an argumentation
framework which contains all arguments for as well as a random selection of
the (indirect) attackers of those arguments. However, an argument A is included
only if all arguments on the directed path from A to some argument for are also
included. This restricts the set of generated arguments to those that are relevant
to the query formula, under the assumption that the semantics in use satis es
the directionality property [
In general, genRandD generates an argumentation framework consisting only of the arguments for the given conclusion, plus a subset of its attackers and their attackers etc.
Thimm and Rienstra / Approximate Reasoning with ASPIC+ by Argument Sampling 29
In order to test the feasibility of our algorithms we performed an experimental evaluation. The goal of this evaluation is to show that our approaches signi cantly reduce the runtime of evaluating queries while still being accurate in their answers.
All algorithms presented in this paper have been implemented using Java in the TweetyProject4, including the complete algorithms described in Section 3. The source code for all implementations can be found here5.
Due to the lack of existing real-world ASPIC+ knowledge bases, we rely on randomly generated knowledge bases and knowledge bases extracted from sources with originally di erent purposes. More precisely, in our evaluation we used the following three sets of benchmarks: Random knowledge bases (Random) We implemented a simple algorithm6 that randomly generates (propositional logic) ASPIC+ knowledge bases as follows. The algorithm takes as input the number of propositions (n), the number of formulas (m), the maximum number of literals in bodies of rules (l) and the percentage of strict rules (s), and generates m rules, each with at most l body literals (uniformly distributed, zero body literals are also possible, giving rise to axioms and assumptions) and uniformly distributed head literal. For each knowledge base generated in that fashion, we selected a single literal at random to be the xed query. Using this generator, we created a set of 5400 random instances with n 2 f5; 10; 15g, m 2 f10; 20; 30g, l 2 f2; 3g, s 2 f0:2; 0:4; 0:6g.
Knowledge bases learnt from data (Animals) The dataset \Animals with
attributes"7 describes 50 animals, e. g. ox, mouse, dolphin, using 85 binary
attributes such as \swims", \black", and \arctic". Following the approach
outlined in [
we used the set of incomplete weighted SAT instances for the MaxSAT Evaluation 20178, which are propositional clauses divided into a set of soft clauses and a set of hard clauses. First, we removed the 7 largest instances from this set, as they brought about severe memory issues for all our solvers. 4http://tweetyproject.org 5http://tweetyproject.org/r/?r=aspic_reasoner 6http://tweetyproject.org/r/?r=aspic_random 7http://attributes.kyb.tuebingen.mpg.de 8http://mse17.cs.helsinki.fi/benchmarks.html For each remaining instance, hard clauses with only one literal are interpreted as axioms. For larger hard clauses, one literal is uniformly selected to be the head of a strict rule while the complements of the remaining literals are put into the body of the rule. Soft clauses are similarly transformed to assumptions and defeasible rules. Note that this transformation does not preserve the semantics of the original instances, but still yields knowledge bases with a structure similar in spirit to the original instances. For each original instance, we generated 10 di erent variants using this scheme and for each of these variants, we selected one literal at random to be the xed query. The nal dataset contained 1490 instances.
All datasets used in our experiments, i. e., knowledge bases with associated queries, are available online9.
Each instance of the three datasets was used to query the following ve solvers: Naive The naive complete algorithm described in Section 3.
MB The module-based complete algorithm described in Section 3. DIR The complete version of the algorithm randD where the sampling probability is set to 1, see Section 4.
ISAMP The implementation of algorithm randI ; as this algorithm depends on two parameters (maximum number of sampled arguments and maximum number of duplicates), we performed a small pre-test in order to nd a suitable parameter combination; the results presented in the next section refer to setting the rst parameter to 500 and the second one to 50. DSAMP The implementation of algorithm randD; as this algorithm depends on a parameter (sampling probability), we performed a small pre-test in order to nd a suitable parameter; the results presented in the next section refer to setting this parameter to 0:9.
For determining acceptable arguments of the individual corresponding argumentation frameworks we used grounded semantics for all solvers (for reasons of simplicity of computation).
For each instance/solver combination we set a timeout of 5 minutes and recorded the runtime. In order to measure the accuracy of the approximate approaches ISAMP and DSAMP, we considered the subset of instances that could be solved by at least one of the complete approaches Naive, MB, and DIR. For each of those instances we checked whether the approximate approaches returned the same answer and we took the ratio of the number of correct answers to the size of this subset as a measure of accuracy.
We did not include TOAST [
Thimm and Rienstra / Approximate Reasoning with ASPIC+ by Argument Sampling 31 Naive MB DIR ISAMP
S 99.9% 99.8% 99.9%
All experiments were performed on a single virtual machine running Ubuntu with eight Intel Xeon 2GHz CPUs and 16GB RAM.
Table 1 summarises the results of our experiments. For each of the three datasets Random, Animals, and MaxSAT and each solver mentioned above, we report on the percentage of solved instances within the time limit of 5 minutes (column \S"), the average runtime of solved instances in milliseconds (column \RT"), and the accuracy as a percentage of the number of correctly solved instances wrt. all solved instances (column \Acc"). In each column we emphasised the best solver with bold face. As a rst remark, note that the complete solvers Naive, MB, and DIR have, of course, perfect accuracy. Second, all solvers are quite similar in terms of the percentage of solved instances within the time limit (98%{100%). So let us look a bit closer at the important measures of runtime and accuracy of our sampling-based approaches. In terms of runtime, our new solvers signi cantly outperfom the baseline approaches in all cases. For the Random dataset, the solver ISAMP has an average runtime of 336.8 milliseconds, compared to 476.4 milliseconds of the best performing complete solver (RT). The di erence is most signi cant for the Animals dataset where ISAMP has an average 455.9 milliseconds compared to 1881.1 milliseconds (MB), therefore outperforming the complete approaches by a factor over 3. In the MaxSAT dataset, the solver DSAMP outperforms the best direct one (DIR), though only slightly. However, recall that we used grounded semantics to determine acceptable arguments in the corresponding abstract argumentation frameworks, which is a problem of polynomial complexity in the size of the argumentation framework. If we had used a more complex semantics, di erences in runtime would have been even more signi cant. Evaluating this aspect is envisioned for future work.
Interestingly, the gain in performance comes with almost no cost wrt. accuracy. In all datasets, all approximate approaches show an accuracy of at least 99%. This shows that our approaches are indeed competitive for the task at hand.
In order to explain the di erence between the performances of solver ISAMP and DSAMP wrt. to the datasets Random and Animals on the one hand (where ISAMP performs better than DSAMP) and MaxSAT on the other (where DSAMP outperforms ISAMP and the di erences between the complete approaches and the approximate approaches di er only slightly), we took a closer look at the structure of the knowledge bases in the di erent datasets. For each instance we computed the distribution of strict rules, defeasible rules, axioms, and assumptions and determined the average of those values for each dataset. Table 2 reports those numbers. Comparing these statistics, we can see that instances in the MaxSAT dataset have a signi cantly larger proportion of strict rules (and therefore fewer defeasible rules). Consequently, many arguments built from this dataset will have few or no attackers as arguments can only be attacked on defeasible rules in our simpli ed framework, cf. De nition 5. By sampling dependently on the existence of counterarguments, DSAMP likely includes most arguments relevant for making correct decisions (as also indicated by the accuracy of 100% on this dataset). This also explains the similarity of the performances of DSAMP and DIR, the latter being a version of DSAMP with sampling probability 1. On the other hand, ISAMP does not care about the connectedness of arguments and samples arguments independently. This means that many arguments irrelevant to the query are constructed, this resulting in a larger (relative) runtime.
To summarise the results, by sampling arguments we get signi cant improvements of the average runtime with only minimal loss of accuracy. Moreover, the performance gain is larger when an instance contains many defeasible rules and fewer strict rules.
In this paper we presented the rst approximation algorithms for structured argumentation approaches such as ASPIC+. Instead of constructing all possible arguments from a knowledge base, our algorithms only sample a limited number of arguments. We developed two variants of this general idea. The rst variant (algorithm randI with implementation ISAMP) samples arguments independently from the knowledge base while the second variant (algorithm randD with implementation DSAMP) samples arguments dependently on arguments constructed so far. Our experimental evaluation showed that approximation by sampling signi cantly improves runtime while accuracy is only marginally a ected.
While the present paper used ASPIC+ as the underlying argumentation formalism, it should be noted that our algorithms are general enough to be applied to other structured argumentation approaches such as ABA, DeLP, or deductive argumentation. Investigating these application formalisms is part of ongoing work.
Acknowledgements The research reported here was partially supported by the Deutsche Forschungsgemeinschaft (grant KE 1686/3-1).