1 Introduction
Dung’s theory of abstract argumentation (Dung, Reference Dung1995) is a unifying framework able to encompass a large variety of specific formalisms in the areas of non-monotonic reasoning, logic programming, and computational argumentation. It is based on the notion of argumentation framework (AF), that consists of a set of arguments and an attack relation between them. Different argumentation semantics introduce in a declarative way the criteria to determine which arguments emerge as ‘justified’ from the conflict, by identifying a number of extensions, that is sets of arguments that can ‘survive the conflict together’. In Dung (Reference Dung1995) three ‘traditional’ semantics are introduced, namely grounded, stable, and preferred semantics, as well as the auxiliary notion of complete extension, to highlight the linkage between admissibility-based semantics. The investigation on alternative argumentation semantics is an active research area since two decades (Baroni et al., Reference Baroni and Giacomin2011).
Several problems are associated to each semantics, notably credulous and skeptical acceptance of an argument with respect to a given AF—that is, determining whether an argument belongs to at least one (respectively, every) extension—and enumeration of all or some extensions given an AF.
In this work we focus on preferred semantics. It represents one of the main contributions in Dung’s theory and is widely adopted—among other areas—in decision support systems (Tamani et al., Reference Tamani, Mosse, Croitoru, Buche, Guillard, Guillaume and Gontard2015) and in critical thinking support systems (Toniolo et al., Reference Valiant2015), as it allows multiple extensions (differently from grounded semantics), the existence of extensions is always guaranteed (differently from stable semantics), and no extension is a proper subset of another extension. On the other hand, grounded semantics prescribes a unique extension which can be computed in polynomial time, thus all the problems related to grounded semantics are easy to solve. As to stable semantics, enumerating stable extensions is known to be equivalent to solve a Satisfiability (SAT) problem, and thus techniques known in the literature for SAT problems (e.g. Gomes et al., Reference Gomes, Sabharwal and Selman2009) can be re-applied to this case.
Several problems associated to preferred semantics are computationally difficult. In particular, (1) determining if there is at least one non-empty preferred extension is NP-complete; (2) counting the number of preferred extensions is #P-complete; and (3) determining whether an argument belongs to each preferred extension, that is, skeptical acceptance, is
${\rm \Pi }_{2}^{p} $
-complete (Dunne & Wooldridge, Reference Dunne and Wooldridge2009; Baroni et al., Reference Baroni, Dunne and Giacomin2010; Kröll et al., Reference Kröll, Pichler and Woltran2017).
Despite the importance of preferred semantics, and the computational complexity of several problems associated to it, few work has been done in argumentation for investigating the exploitability of machine learning techniques—and particularly empirical predictive models (EPMs)—for supporting computationally complex reasoning problems.
In order to fill this lack of studies in the context of computational models of argumentation, in this work we provide an extensive investigation of the exploitability of automatically generated predictions in dealing with high-complexity problems. Specifically, we analyze the ability of predictive models in (i) given a set of solvers for the preferred extensions enumeration problem, predicting the fastest one, as well as the amount of central processing unit (CPU)-time each solver will need to solve an instance of the problem; and (ii) predicting characteristics of the solution to the problem—without the need to solve it. These characteristics include (1) whether the framework has a single empty preferred extension; and (2) whether the framework has a number of extensions exceeding a given threshold representing the limit for an acceptable burden on the user; or (3) the (estimated) number of preferred extensions.
Our contribution encompasses previous works exploiting features in abstract argumentation (notably, Cerutti et al., Reference Cerutti, Giacomin and Vallati2014a; Vallati et al., Reference Watts and Strogatz2014). Specifically, in this paper:
1. we empirically demonstrate the usefulness of models for predicting solvers performance in solving the enumeration problem associated to the preferred semantics;
2. we introduce a hierarchical predictive model for determining characteristics of the solution of the enumeration problem associated to the preferred semantics;
3. we demonstrate that the proposed hierarchical model is able to provide very accurate predictions, without solving the enumeration problem;
4. we expand the existing set of features used from 50 to 147. Specifically, we added 97 features derived from a matrix representation of AFs;
5. we provide a new, sound, methodology for deriving structured AFs.
The importance of this contribution is twofold. From a theoretical point of view, it explains the runtime variations between different approaches, and links AFs characteristics to the solutions of abstract argumentation problems. From a practical perspective, the proposed analysis provides tools for choosing among a set of available algorithms, in order to achieve the best performance from them, and techniques to predict information that can have a significant impact on argumentation applications. For instance, (1) and (2) can be exploited in cases where the knowledge base changes frequently, the set of arguments needs to be frequently updated and the extensions need to be frequently computed to evaluate the acceptability of each proposition in the knowledge base. In such cases, the acceptability of propositions might have been already changed by the time the answer is computed, thus the predictions can guide the decision on when the computation procedure should be triggered. Moreover, estimating the number of extensions (3) may be useful to get a rough assessment of the uncertainty inherent to an AF, to assess the proportion of acceptance of an argument with respect to the total number of extensions, or to identify a bound for an enumeration algorithm (Baroni et al., Reference Baroni, Dunne and Giacomin2010).
In order to provide predictions, models exploit features extracted from target AFs. Features are real numbers that summarize potentially important properties of the AF, therefore a predictive model can be seen as a mapping from instance features to predictions (solvers performance or solutions structure). This work is based on prior well-received work, such as Cerutti et al. (Reference Cerutti, Giacomin and Vallati2014a); here we establish the most extensive set of features for performing predictions in abstract argumentation.
The paper is organized as follows. Section 2 discusses related work. In Section 3 we provide the required background on abstract argumentation. Then, in Section 4, we provide the list of the features of AFs that are exploited by predictive models. In Section 5 we present the machine learning models to evaluate and select algorithms for enumerating preferred extension, and we analyze them by providing some experimental results. Then, in Section 6, we turn to the models that predict properties of extensions given the chosen set of features, and again we empirically evaluate them. Finally, we provide conclusions and describe future developments in Section 7.
2 Related work
In the field of automated reasoning, the idea of generating models that, according to the values of some features, allow to identify the best algorithm(s) for an instance of a certain problem has been investigated by several researchers. For example, EPMs have been extensively and successfully applied in numerous areas of Artificial Intelligence, such as SAT problem, Mixed Integer Programming (MIP), Answer Set Programming (ASP), Quantified Boolean Formulae (QBF), travelling salesman problem (TSP), and Automated Planning (Brewer, Reference Brewer1994; Nudelman et al., Reference Nudelman, Leyton-Brown, Devkar, Shoham and Hoos2004; Xu et al., Reference Toniolo, Norman, Etuk, Cerutti, Ouyang, Srivastava, Oren, Dropps, Allen and Sullivan2008; Leyton-Brown et al., Reference Leyton-Brown, Nudelman and Shoham2009; Smith-Miles et al., Reference Smith-Miles, van Hemert and Lim2010; Gebser et al., Reference Gebser, Kaufmann, Neumann and Schaub2011; Fawcett et al., Reference Fawcett, Vallati, Hutter, Hoffmann, Hoos and Leyton-Brown2014).
The work described by Fawcett et al. (Reference Fawcett, Vallati, Hutter, Hoffmann, Hoos and Leyton-Brown2014) is focussed on generating models for accurately predicting planners runtime. Such models exploit a large set of instance features, derived from different representations of a given planning problem, and (short) runs of planners. Their experimental results show that the generated performance models are able to produce very accurate runtime predictions.
SATZilla is a prominent example of an algorithm portfolio designed for SAT (Xu et al., Reference Toniolo, Norman, Etuk, Cerutti, Ouyang, Srivastava, Oren, Dropps, Allen and Sullivan2008). It exploits regression techniques to build a predictor of the runtime of a number of provided SAT solvers. For solving a new SAT problem, SATZilla computes the values of a large set of features, predicts the performance of the considered SAT solvers. The solvers are then ordered according to the predicted runtime, and executed for the predicted time, following the established ordering. It should be noted that, for the sake of overall performance, SATZilla exploits also pre- and backup solvers: the former is used before extracting features, in order to quickly solve trivial instances. The latter is run when all the selected solvers failed.
Similarly, Claspfolio (Gebser et al., Reference Gebser, Kaufmann, Neumann and Schaub2011) exploits regression-based EPMs for selecting, among a range of predefined configurations of the well-known ASP solver Clasp (Gebser et al., Reference Gebser, Kaminski, Kaufmann, Schaub, Schneider and Ziller2007), the best configuration to minimize the runtime on a given ASP instances. Predictions are made according to a set of features that are extracted from the considered ASP problem. Claspfolio 2 (Hoos et al., Reference Hoos, Lindauer and Schaub2014) is an improved version of Claspfolio, that provides a modular architecture that allows for integrating several different approaches and techniques for extracting features, predicting solvers’ performance, and combine solvers into a portfolio.
Matos et al. (Reference Matos, Planes, Letombe and Marques-Silva2008) propose an algorithm portfolio solving the MaxSAT problem. According to the values of several features, it estimates the runtime of each incorporated solver, and then solves the instance with the estimated fastest solver. The estimation is done using a (linear) model configured by performing ridge regression (Marquardt & Snee, Reference Marquardt and Snee1975).
Similarly, Pulina and Tacchella (Reference Pulina and Tacchella2007) study an algorithm portfolio solving the QBF problem. They identify some features of the QBF problem, and investigate the usage of four inductive models to select the best solver to use according to the values of the identified features. Maratea et al. (Reference Maratea, Pulina and Ricca2014) applied a similar approach for solving ASP problems: given a set of easy-to-compute features, extracted from the given instance, the authors propose a classification-based approach for selecting the most promising solver to run in order to minimize the required runtime.
3 Background on Dung’s Argumentation framework
An AF (Dung, Reference Dung1995) consists of a set of arguments and a binary attack relation between themFootnote 1 .
Definition 1
An AF is a pair
${\rm \Gamma }\,{\equals}\,\langle {\cal A}_{{}} ,{\cal R}_{{}} \rangle $
where
${\cal A}$
is a set of arguments and
${\cal R}\,\subseteq\,{\cal A}{\times}{\cal A}$
. We say that b attacks a iff
$\langle b,a\rangle \in{\cal R}$
, also denoted as b
→
a
.
The basic properties of conflict-freeness, acceptability, and admissibility of a set of arguments are fundamental for the definition of argumentation semantics.
Definition 2
Given an
$ AF\,{\rm }\Gamma \,{\equals}\,\langle {\cal A}_{{}} ,{\cal R}_{{}} \rangle $
:
∙ a set
$S\,\subseteq\,{\cal A}$
is a conflict-free set of Γ if ∄
a
,
b
∈S s.t.
a
→
b
;
∙ an argument
$a\in{\cal A}$
is acceptable with respect to a set
$S\,\subseteq\,{\cal A}$
of Γ if
$\forall b\in{\cal A}$
s.t.
b
→
a
, ∃c∈S s.t.
c
→
b
;
∙ a set
$S\,\subseteq\,{\cal A}$
is an admissible set of Γ if S is a conflict-free set of Γ and every element of S is acceptable with respect to S of Γ.
An argumentation semantics σ prescribes for any AF Γ a set of extensions, denoted as
${\cal E}_{\sigma } ({\rm \Gamma })$
, namely a set of sets of arguments satisfying the conditions dictated by σ. Here we need to recall the definition of preferred (denoted as PR) semantics only.
Definition 3
Given an
${\rm }AF\,\,{\rm }\Gamma \,{\equals}\,\langle {\cal A}_{{}} ,{\cal R}_{{}} \rangle $
: a set
$S\,\subseteq\,{\cal A}$
is a preferred extension of
$\,{\rm \Gamma }$
, that is
$S\in{\cal E}_{{\rm PR}} (\Gamma )$
, iff S is a maximal (w.r.t. set inclusion) admissible set of
${\rm \Gamma }.$
Problems considered: For our purpose, given a semantics σ and an AF Γ, let us consider the following problems:
1. Exσ: determining if
$${\cal E}_{\sigma } ({\rm \Gamma })\,\ne\,\emptyset ;$$
2. NE σ : determining if
${\cal E}_{\sigma } ({\rm \Gamma })\,\notin\,\{\emptyset ,\{\emptyset \} \} $
Footnote
2
;3. COUNT σ: determining
$\,\mid\!{\cal E}_{\sigma } ({\rm \Gamma })\!\mid\,;$
4. ENUM σ: enumerating
${\cal E}_{\sigma } ({\rm \Gamma }).$
In the case of the preferred semantics, it is known (Dunne & Wooldridge, Reference Dunne and Wooldridge2009; Baroni et al., Reference Baroni, Dunne and Giacomin2010; Kröll et al., Reference Kröll, Pichler and Woltran2017) that ExPR is trivial, that is the existence of at least a preferred extension is always guaranteed; Ne
PR is NP-COMPLETE; Count
PR is #P-COMPLETE
Footnote
3
. We are not aware of any study on the computational complexity of determining if
$\,\mid\!{\cal E}_{\sigma } ({\rm \Gamma })\!\mid\!\leq \,\chi $
.
4 Features
In order to perform predictions, EPMs need to extract information from the considered AFs. Such information are provided under the form of features. A feature is either a real number or a Boolean value, that summarizes a potentially important property of an AF.
Our feature set includes 147 values, which exploit the representation of AFs as a graph or as a matrix.
4.1 Graph-related features
We are able to extract 50 features by representing an AF both as directed graph (DG)and as undirected graph (UG) (lossy) —following the notation introduced in Cerutti et al. (Reference Cerutti, Giacomin and Vallati2014a).
In total, 26 features are extracted from the representation of AFs as DG. Each feature belongs to one of the following four classes: graph size (5 features), degree (4), Strongly Connected Components (SCC) (5), graph structure (5), CPU-times (7).
∙ Graph size features: number of vertices, number of edges, ratios vertices-edges and inverse, and graph density.
∙ Degree features: average, standard deviation, maximum, minimum degree values across the nodes in the graph.
∙ SCC features: number of SCCs, average, standard deviation, maximum, and minimum size of SCCs.
∙ Graph structure: presence of auto-loops, number of isolated vertices, flow hierarchy, and results of test on Eulerian and aperiodic structure of the graph.
∙ CPU-times: the needed CPU-time for extracting each class of features. In our implementation, graph transitivity is computed as the fraction of all the possible triangles which is present in the considered graph. Possible (potential) triangles are identified by the number of ‘triads’, that is two edges with a shared vertex. A graph is Eulerian if there exists a path (starting and ending at the same vertex) that allows to visit every edge exactly once. A given graph is Aperiodic if there is no integer k>1 that divides the length of every cycle. Flow hierarchy is computed as the fraction of edges not participating in cycles in a DG (Luo & Magee, Reference Luo and Magee2011). The features extracted by the UG representation of AFs—that is replacing each directed attack with an undirected edge—and distinct from the DG features are 24, belonging to six classes: graph size (4), degree (4), components (5), graph structure (1), triangles (5), CPU-times (5).
∙ Graph size features: number of edges, ratios vertices-edges and inverse, and graph density.
∙ Degree features: average, standard deviation, maximum, minimum degree values across the nodes in the graph.
∙ Components features: number of connected components, average, standard deviation, maximum, and minimum size.
∙ Graph structure: transitivity of the graph.
∙ Triangles features: total number of triangles in the graph and average, standard deviation, maximum, minimum number of triangles per vertex.
∙ CPU-times: the needed CPU-time for extracting each class of features.
4.2 Matrix-related features
Any AF with N arguments can be encoded as an N×N matrix as follows. The value of a cell (a,b) is 1 if there exists an attack from argument a to argument b, 0 otherwiseFootnote 4 . Given this encoding we are able to extract 97 features, divided in:
∙ basic matrix (9): includes information about rank, number of non-zeros, norm, etc.;
∙ sum (14): includes statistics, like standard deviation, mean, etc., on vectors resulting from sum of either columns or rows;
∙ cumulative sum (21): includes statistics, like standard deviation, mean, etc., on vectors resulting from cumulative sum of columns, rows, and diagonals;
∙ differences (21): includes statistics, like standard deviation, mean, etc., on vectors resulting from differences of cells on either columns, rows, and diagonals;
∙ diagonals (7): includes general information extracted by considering the first and second diagonal of the matrix;
∙ Gradient (21): includes statistics extracted by considering the gradient of the vector resulting by (i) the sum of the rows, (ii) the sum of the columns, and (iii) the sum of the diagonals of the matrix;
∙ Correlation (4): includes the correlation values between the sum of columns, sum of rows, sum of diagonals, and gradients.
4.3 Example of extracted features
To illustrate the process of features extraction, let us consider an intuitive example from Besnard and Hunter (Reference Besnard and Hunter2014). Let a be the argument ‘Patient has hypertension so prescribe diuretics’; b: ‘Patient has hypertension so prescribe betablockers’; and c: ‘Patient has emphysema which is a contraindication for betablockers’. Intuitively, assuming that only one treatment is possible at the very same time, a attacks b and vice versa, while c suggests that b should not be the case (c attacks b). Therefore, let
${\rm \Gamma }_{M} \,{\equals}\,\langle {\cal A}_{M} ,{\cal R}_{M} \rangle $
such that,
$${\cal A}_{M} \,{\equals}\,\{ {\bf a},{\bf b},{\bf c}\} $$
and
${\cal R}_{M} \,{\equals}\,\{ \langle {\bf c},{\bf b}\rangle ,\langle {\bf b},{\bf a}\rangle ,\langle {\bf a},{\bf b}\rangle \} $
. Γ
M
is depicted in Figure 1.
The argumentation framework (AF) Γ M for the hypertension problem on the left, and its matrix encoding on the right
Table 1 presents a subset of the extracted features, and their extracted value on the considered example. For the sake of readability, we focus on less intuitive features. Features such as the number of arguments or the number of attacks are trivial to identify and extract.
A subset of the features extracted by considering the directed graph, undirected graph, and matrix representation of the argumentation framework Γ M for the hypertension problem
5 Exploiting predictive models for performing algorithm selection
This section is devoted to investigate the use of predictive models for performing algorithm selection, in order to combine different systems into a portfolio and improve the overall performance in terms of both coverage (i.e. percentage of problem instances actually solved) and runtime. For this analysis we considered only the problem of enumerating preferred extensions.
5.1 Algorithms for solving the preferred extensions enumeration problem
In this paper we consider four approaches for solving the problem of preferred extensions enumeration: Aspartix, ArgTools, ArgSemSAT, and SCC-P. They have been chosen as representative of the variety of approaches used to enumerate preferred extensions.
First, Aspartix (Dvořák et al., Reference Dvorák, Järvisalo, Wallner and Woltran2011) expresses argumentation semantics in ASP: a single program is used to encode a particular argumentation semantics, and the instance of an AF is given as an input database. Tests for subset-maximality exploit the metasp optimization frontend for the ASP-package gringo/claspDFootnote 5 .
Instead, ArgTools (Nofal et al., Reference Nofal, Atkinson and Dunne2014) is a depth-first backtracking procedure that traverses a binary search tree. The root considers the case where all the arguments in the AF are blank, that is not yet visited. At each step of the search process, a blank node is selected and assumed to belong to the preferred extension, and a local evaluation on its neighbours is performed. Then the procedure recursively calls itself on the assumption that the above arguments are respectively in or out the extension. Any inconsistency leads to a backtrackFootnote 6 .
On the other hand, ArgSemSAT (Cerutti et al., Reference Cerutti, Dunne, Giacomin and Vallati2013, Reference Cerutti, Vallati and Giacomin2017) performs a search in the space of complete extensions to enumerate the maximal ones. In particular, ArgSemSATencodes the constraints corresponding to complete extensions into a propositional formula. A SAT-solver is then used to determine an assignment of propositional variables satisfying the formula, thus returning a complete extension. A depth-first technique is then applied in order to determine a maximal complete extension containing the one already found—that is, a preferred extension. Previously explored search states are excluded from further exploration by adding specific constraints to the encoding of complete extensions. ArgSemSAT is, together with Cegartix (Dvorák et al., Reference Dvořák, Gaggl, Wallner and Woltran2015)—a similar system exploiting a SAT-solver as a NP-oracle—the best system for addressing problems associated to preferred semantics as certified by the First International Competition on Computational Models of Argumentation (ICCMA) 2015 (Thimm et al., Reference Thimm, Villata, Cerutti, Oren, Strass and Vallati2016).
Finally, SCC-P is an instantiation of the meta-algorithm proposed in Cerutti et al. (Reference Cerutti, Giacomin, Vallati and Zanella2014c) which exploits the SCC-recursiveness schema (Baroni et al., Reference Baroni, Cerutti, Dunne and Giacomin2005): it recursively decomposes a framework so as to compute extensions on restricted sub-frameworks, in order to reduce the computational effort. At the beginning, the extensions of the framework restricted to the initial SCCs, that is, those not receiving attacks from others, are computed and combined together. Then each SCC which is attacked only from initial SCCs is considered, and for each extension already obtained, the extensions of such a SCC are locally computed and merged with it. The process is then applied to all SCCs following their partial order, until no remaining SCCs are left to process. Moreover, as the name suggests, the algorithm exploits a recursive procedure for the local computation in every SCC, according to the following steps. First, all arguments attacked by the extension selected in the previous SCCs are suppressed. Then, the procedure is recursively applied to the remaining part of the SCC. When the base of the recursion is reached, a specific ‘base algorithm’ is called. Such base algorithm can be obtained by generalizing existing algorithms that enumerate extensions so as to work on restricted sub-frameworks, for example, a variation of ArgSemSAT as proposed in Cerutti et al. (Reference Cerutti, Giacomin, Vallati and Zanella2014c).
It should be noted that, while a larger number of solvers can be considered in the general EPMs framework, the focus of our work is on identifying the exploitability of predictive models for effectively estimating the runtime needed for solving a given AF and, as a side effect, how such information can be used for selecting the most appropriate solver. For this reason, and for allowing a more in-depth analysis of features, we selected a restricted number of solvers.
5.2 Experimental protocol
We randomly generated a set of 10 000 AFs using the generator described in Cerutti et al. (Reference Cerutti, Giacomin and Vallati2014b), varying the number of SCCs between 0 and 100, the number of arguments between 10 and 5000; and then considering four classes of AFs with uniform probability of attacks—that is, with the probability of having an attack between two arguments respectively of 0.25; 0.5; 0.75; and completely random between 0 and 1—leading to AFs with a number of attacks between 35 and (approximately) 270 000. This was done in order to have, for each selected solver, unsolved AFs as well as AFs solved quickly (few seconds) or in hundreds of seconds. Such a wide distribution is extremely informative for effectively training EPMs. Table 2 lists some of the relevant characteristics of the generated AFs.
Characteristics of the considered argumentation frameworks.
SCC=Strongly Connected Components.
The solvers and the feature extraction algorithms have been run on a cluster with computing nodes equipped with 2.5 Ghz Intel Core 2 Quad ProcessorsTM, 8 GB of RAM, and Linux operating system. A cutoff of 900 seconds was imposed to compute the preferred extensions for each AF. For each solver we recorded the overall result: success (if it finds each preferred extension), crashed, timed-out, or ran out of memory. Unsuccessful runs—crashed, timed-out, or out of memory—were assigned a runtime equal to the cutoff.
We observed that graph-related features are usually quick to compute: on average, the extraction process takes around 3 CPU-time seconds on AFs considered in this experimental analysis. However, extracting information about the aperiodicity of the graph can require up to 20 seconds—even though that happened only once. On the other hand, matrix-related features require a higher CPU-time to be properly extracted: on average, 7 CPU-time seconds on the considered AFs. Given the fact that enumerating the preferred extensions of an AF can require between tens and hundreds of seconds, we decided to focus on the graph-related sets, as they are much quicker to extract.
We considered EPMs for both classification and regression approaches. Classification approaches classify the AF into a single category, corresponding to the algorithm which is predicted to be the fastest. These approaches do not estimate the performance difference between solvers, rather they only look for the best one. Regression techniques model the behaviour of each algorithm in order to predict its runtime on a new AF.
We first assessed the performance of various classification and regression models, using the WEKA tool (Hall et al., Reference Hall, Frank, Holmes, Pfahringer, Reutemann and Witten2009). We considered well-known machine learning techniques: linear regression, neural networks, Gaussian processes, decision trees, and rule-based techniques. The EPMs were evaluated using a 10-fold cross-validation approach on a uniform random permutation of our instances—a standard method where nine slices are used for training and the tenth for testing. According to this analysis, we observed that random forests perform best in classification, and M5-rules in regression. For both classification and regression, the second best approach is based on decision tables (Kohavi, Reference Kohavi1995). In classification, decision tables achieve accuracy performance that is 4% worse than random forest; in regression, the root mean square error (RMSE) is increased, on average, by 0.09.
We then assessed the importance of features by means of a greedy forward search based on the Correlation-Based Feature Subset Selection (CFS) attribute evaluator (Hall, Reference Hall1998), which determines the most relevant subset of features for the task at hand. In short, the search starts from an empty subset of features. At each iteration, the feature that increases the most the evaluation of the current subset is added. The search stops when the addition of any attribute results in a decrease of the subset evaluation. The evaluation of a subset of features considers the predictive ability of each feature along with the degree of redundancy between them (Hall, Reference Hall1998). Given the results shown in Cerutti et al. (Reference Cerutti, Giacomin, Vallati and Zanella2014c), SCC-related information are believed to be extremely informative, thus expected to play a significant role in the EPMs performance. However, it has to be pointed out that the relation between the importance of the features exploited by an EPM and its performance is not deterministic.
Finally, the EPMs have been generated considering seven different sets of features:
∙ the set including the single best feature (B1), the sets including the best two and three features (B2, B3);
∙ the set including the features extracted from the DG;
∙ the set including those extracted from UG;
∙ the set with all the extracted features (All).
It turns out that B1, B2, and B3 include only features from the DG.
5.3 Runtime prediction
As to the M5-rules model to predict solvers runtime, the three best features selected by the greedy approach are summarized in Table 3. This analysis provides several insights on features that are expected to affect solvers performance. First, the density of DG—that is how close it is to a complete graph—seems strongly related to the performance of all the solvers since it is always among the best three features. Second, we observe that also SCC-related information, mainly the number of SCCs and the size of the maximum one, are often selected.
Best features selected for each solver, by the greedy approach, for predicting runtime
SCC=Strongly Connected Components.
Table 4 shows the results, in terms of RMSE, for regression with 10-fold cross-validation on a uniform random permutation of our full set of 10 000 AFs. Since solvers runtimes vary from 0.01 to 900 CPU seconds, we trained our regression models to predict log-runtime rather than absolute runtime: this have been effective in similar circumstances (Hutter et al., Reference Hutter, Xu, Hoos and Leyton-Brown2014).
Cross-validated root mean square error of log10(runtime) for M5-rules models using different features subsets
B1, B2, B3 indicates the best 1, 2, and 3 features according to a greedy forward search; DG (UG) indicates features extracted only from directed (undirected) representation; SCC (Strongly Connected Components) only SCC-related ones; All indicates all the extracted features.
Values in bold indicate the best results, also considering hidden decimals.
Results shown in Table 4 indicate that using all the extracted features leads to the best possible results. Some solvers seem to have easier to predict behaviours, while others are somehow more complex. It is interesting to note that DG and UG features lead to similar predictive performances, which are usually close to those achieved by exploiting the B3 set. Moreover, DG features allow to achieve an RMSE which is very close to the one achievable by exploiting the All set for Aspartix, SCC-P, and ArgSemSAT. Interestingly, this is not true for ArgTools. In this case the UG set of features provides more useful information for EPMS than DG. Moreover, SCC-related features are not informative for predicting the performance of ArgTools, and this is confirmed also by the selected three best features (Table 3). Finally, we noted that the behaviours of ArgSemSAT and SCC-P appear to be hard to predict, when compared to the other considered solvers. A possible explanation is due to the fact that ArgTools ran out of time on most of the AFs, and Aspartix solved a significant number of them in 800–899 CPU-time seconds. ArgSemSAT and SCC-P show different, and more variegated, CPU-time distributions.
5.4 Classification
Differently from the regression EPMS, which generate a predictive model for each considered solver, the classification approach trains a single model that selects the most performant solver.
In this case, the three best features selected for the classification EPM are, in the order, (1) the number of vertices, (2) the density of the DG, and (3) the minimum degree value of the DG. Table 5 shows the results, in terms of overall accuracy and per-algorithm precision, of the classification EPM, evaluated with 10-fold cross-validation. From the set of 10 000 AFs, those which were not solved by any solver were removed. In this approach, an AF is a member of the class corresponding to the solver which has been the fastest in enumerating preferred extensions.
Evaluation of classification empirical predictive models for different features subsets
B1, B2, B3 indicates the best 1, 2, and 3 features according to a greedy forward search, namely: (1) the number of vertices, (2) the density of the directed graph and (3) the minimum degree value of the directed graph; DG (UG) indicates features extracted only from directed (undirected) representation; SCC (Strongly Connected Components) only SCC-related ones; All indicates all the extracted features. A precision value smaller than 50% indicates that most of the argumentation frameworks have been mistakenly classified as members of the class.
Values in bold indicate the best results, also considering hidden decimals.
Accuracy indicates the proportion of correctly predicted results in the whole data set, while precision considers only a single class, and is the proportion of the elements correctly classified as members of the class against all the actual members of the class.
Several considerations can be drawn from Table 5:
∙ the whole set of features usually allows the EPM to achieve the best predicting performance;
∙ using the best two features instead of the single best one guarantees better performance;
∙ SCC-related features are not as informative as we believed;
∙ features derived from UG are usually better than those generated by considering DG. This counter-intuitive result (UG are lossy) is further addressed in Section 5.6. However, no features from the UG set are included in the B3 set: this seems to suggest that UG features are useful when exploited all together, while DG ones seem to be better when considered singularly.
As mentioned above, the greedy approach used for determining the most informative features indicated the number of vertices as the best one. Figure 2 shows how the number of vertices of AFs affect the performance of the considered solvers. Given the precision performance reported in Table 5, and the shape of the graph in Figure 2, we can argue that this feature is quite informative for selecting between SCC-P and ArgSemSAT, which are the fastest systems on most of the considered AFs, but does not provide very reliable information about the other solvers.
The number of time each solver has been the fastest one w.r.t. the cardinality of the set of arguments. SCC=Strongly Connected Components
5.5 Algorithm selection
After evaluating the predicting performance of classification and regression EPMs, we compared them in order to understand which is the most promising approach to be used for online algorithm selection. Algorithm selection done by exploiting the classification EPM is straightforward: the best predicted solver is used for solving the testing AF. Instead, regression EPMs require to predict the runtime of each considered solver, and to select the one predicted to be the fastest. Let us notice that the CPU-time required for generating the predictions, in both classification and regression EPMs, is extremely low. Such predictions are generated by solving easy case-based formulas that test a feature value at a time. The most expensive step is the generation of the predictive models, which requires also to solve the training problems and extract the features from all of them; this is done offline, thus it does not affect the algorithm selection performance.
For this comparison we used the set of All the considered features, and divided the 10 000 AFs in separate training and testing instances. To achieve a more objective comparison between the techniques, the testing instances have been randomly selected across all the different sizes, resulting in 1040 AFs. All the solvers failed to enumerate the preferred extensions before the cutoff time on 33 AFs over the 1040 test instances: these instances were thus excluded from the following evaluation.
For each AF we considered (1) the fastest solver and (2) whether or not either the regression or the classification EPMs successfully select such a solver, counting the times that this happened. The result is shown in the left part of Table 6. There is not a great difference between classification and regression-based algorithm selection; the former is able to select the best algorithm on 788 testing AFs (78%, clearly consistent with Table 5), while the latter on 755 (75%). In most of the cases (834 times) both the EPMs select the same algorithm, and in 687 cases such selection was right. It is worth noting that there is a remarkable difference between the performance of algorithm selection approaches and the single solvers, that is each single solver achieves the best performance in a greatly lower number of AFs w.r.t. the solver predicted by any of the two algorithm selection approaches.
Algorithm selection performance—w.r.t. single solvers (upper part)—using two metrics: the number of times each solver and the selected solver has been the fastest one on the testing set of argumentation frameworks (AFs) (Fastest); and the International Planning Competition (IPC) value achieved by each solver and selected solver
SCC=Strongly Connected Components; EPM=empirical predictive models.
The approaches are ordered from the worse to the best (according to each metric).
It can be argued that the metric used, that is the number of time a system has been the fastest, albeit good for evaluating the algorithm selection performance, might not be very informative from the performance gain perspective. Thus, we analyzed the International Planning Competition (IPU) score, borrowed from the 2008 International Planning CompetitionFootnote 7 . For each AF, each system gets a score of T */T, where T is its execution time and T * the best execution time among the compared systems, or a score of 0 if it fails in that case. Runtimes below 0.01 seconds get by default the maximal score of 1. The IPC score is interesting because it considers, at the same time, the runtimes and the number of solved instances. The maximum IPC score achievable on the testing AFs is 1007, which corresponds to a system that always selects the best solver on the 1007 instances where at least a solver succeeded. Clearly, on AFs where both the EPMs selected the same algorithm, they obtain the same IPC score. According to IPC score, the classification-based algorithm selection approach scores 928.1, followed by the regression EPMs with a score of 887.7. SCC-P and ArgSemSAT score, respectively, 662.4 and 546.7; finally Aspartix scores 288.3 and ArgTools 210.1 (right part of Table 6). Also by comparing the systems using the IPC score, a significant difference can be found between algorithm selection methods and single solvers.
5.6 Discussion
Remarkably, the EPMs which consider features derived from UG—that is without considering the directionality of attacks—are usually better than those generated by considering DG ones (cf. Table 5). Since preferred semantics satisfies the directionality principle (Baroni & Giacomin, Reference Baroni, Caminada and Giacomin2007), one could see this as a counter-intuitive result. However, it is worth mentioning that both Aspartix and ArgTools have some recurrent behaviours—the former often ends the enumeration around 800–900 seconds, the latter often do not end the enumeration in the given time—that turn out to be easily predictable. It is possible that these behaviours are affected just by the features of the UG. Nevertheless, this fails to explain the behaviour of ArgSemSAT and SCC-P. As to ArgSemSAT, it has to be remarked that its performance depends on the performance of the SAT-solver used, in this case GLUCOSE (Audemard & Simon, Reference Audemard and Simon2014). Therefore, further investigations on the translation into SAT problems and its dependency from the AF structure should be considered. Moreover, in Cerutti et al. (Reference Cerutti, Dunne, Giacomin and Vallati2013) we show the dramatic performance difference due to the different encoding of complete semantics in SAT problems: an additional investigation on this topic is already envisaged. As to SCC-P, the (little) advantage exhibited by the features derived from the UG seems to be consistent with the meta-algorithm based on the SCC-recursiveness schema (Baroni et al., Reference Baroni, Cerutti, Dunne and Giacomin2005), which allows to apply the SAT-solver just to SCCs.
6 Exploiting predictive models for estimating the number of preferred extensions
The aim of this investigation is to exploit predictive models for providing in ‘almost real-time’ (i.e. without solving the enumeration problem) an estimation of the number of preferred extensions of a given AF. Specifically, we are interested in determining (1) the solution to the non-emptiness problem (a NP-complete problem), and (2) whether there is more than one preferred extension, with an estimation of the relevant number. Moreover, we introduce an additional theoretical problem, that is ‘does the preferred semantics identify less than
$$\bar{X}$$
extensions?’, where
$$\bar{X}$$
is a configurable, arbitrary, but fixed, parameterFootnote
8
.
6.1 Experimental protocol
The first step of our experimental protocol consists in the generation of an initial data set. To this purpose, we first generated a large number of AFs by using an improved version of AFBenchGen (Cerutti et al., Reference Cerutti, Giacomin and Vallati2014b). In this analysis, differently from experiments in Section 5, our focus is on generating AFs with very different number of preferred extensions, in order to check if EPMs are able to accurately predict the number of extensions of a given framework.
For the purpose of training the models, and maximizing the diversity of AFs in terms of the number of extensions, we randomly generated three sets of 4000 AFs, each one corresponding to a different graph model: Erdös and Rényi (Reference Erdös and Rényi1959), Watts and Strogatz (Reference Wyner, Bench-Capon, Dunne and Cerutti1998), and Barabasi and Albert (Reference Barabasi and Albert1999). Notably, these graph topologies have been already exploited for testing abstract argumentation techniques (Bistarelli et al., Reference Bistarelli, Rossi and Santini2015a, 2015Reference Bistarelli, Rossi and Santinib). In short, in Erdös–Rényi graphs the attacks between arguments are randomly selected according to a uniform distribution. On the other hand, Watts–Strogatz graphs are aimed at modelling many biological, technological, and social networks that are neither completely regular nor completely random. These graphs are obtained by rewiring regular networks so as to introduce increasing amounts of disorder. As a result, they can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. Finally, in Barabasi–Albert graphs the node connectivities follow a scale-free power-law distribution, with the aim of modelling many large networks that expand continuously by the addition of new nodes that attach preferentially to sites that are already well connected.
In particular, as Barabasi and Albert (Reference Barabasi and Albert1999) and Watts and Strogatz (Reference Wyner, Bench-Capon, Dunne and Cerutti1998) produce acyclic graphs—and thus a single extension (Dung, Reference Dung1995)—we introduced a parameter, varying between 0 and 1, for selecting the probability of having mutual attacks instead of directed ones: if the parameter is 0, then the produced graph is acyclic; if it is 1, each attack is mutual. The number of arguments vary between 11 and 1200, and the number of attacks range between 10 and (approximately) 230 000: further details are shown in Table 7. To give an intuition of ‘how difficult’ those AFs are to solve, the current state-of-the-art approaches, w.r.t. the last competition—not restricted to the approaches we considered in previous sections—managed to solve 72% of them before the cutoff time of 900 seconds.
Characteristics of the considered argumentation frameworks
SCC=Strongly Connected Components
In order to generate our initial data set, a pre-processing step has then been applied to the obtained AFs. For each AF we (1) extracted its features; (2) computed the number of preferred extensions; and (3) in the case of a single preferred extension, we checked whether it was empty or not. We used various approaches, from ICCMA 2015 (Thimm et al., Reference Thimm, Villata, Cerutti, Oren, Strass and Vallati2016), to compute the preferred extensions to maximize the chances of obtaining a solution.
Similarly to the process described in Section 5, we computed various classification and regression models included in WEKA (Hall et al., Reference Hall, Frank, Holmes, Pfahringer, Reutemann and Witten2009) and assessed their performance in predicting the solution to the non-emptiness problem, and the above mentioned properties of the solution to the enumeration problem for preferred semantics. We considered linear regression, neural networks, Gaussian processes, decision trees, and rule-based techniques. As in Section 5, models have been evaluated using a 10-fold cross-validation approach on a uniform random permutation of our instances.
On AFs considered in this experimental analysis, the overall features extraction process takes around 1.5 CPU-time seconds. As it is apparent, AFs considered in this empirical analysis tends to be smaller, in terms of number of arguments, than those considered in Section 5. Again, this is due to the different focus of the investigation, and to the different final use of the trained EPMs. It is worth reminding that features will be used for estimating the number of preferred extensions, and no solver will be run afterwards: it is therefore reasonable to invest CPU-time in extracting features, in order to maximize the potential accuracy of predictions.
6.2 Hierarchical model design
We observed that the direct use of regression models for predicting the actual number of preferred extensions achieve a too low accuracy to make them useful. As a consequence, we decided to design a hierarchical predictive model organized in two levels. First, the model predicts if the given AF has an empty (and thus unique) preferred extension, a unique non-empty preferred extension, or more than one preferred extension (and thus all extensions being non-empty). In case the presence of many preferred extensions is predicted, a different classification model is used for determining whether or not the number of preferred extensions is greater than
$\bar{\chi }$
. Moreover, in order to investigate the generality of this approach, at the second level of the hierarchy we consider also a regression model that will output the number of extensions. Figure 3 depicts the two-level system.
The two-level classifier of a argumentation framework (AF)Γ, according to the number/type of preferred extensions. The first level is said to be higher in the hierarchy than the second level
The exploited hierarchical approach is appropriate because the levels evaluate different aspects of frameworks: the first focusses on the non-emptiness problem, while the second one counts the number of extensions. Intuitively, when exploiting a hierarchical approach, models of higher levels should have very good performance; otherwise subsequent levels will be negatively affected by the poorly classified elements. Also, it has been observed that it is possible to achieve better prediction accuracy and simpler models by using hierarchical approaches (Xu et al., Reference Toniolo, Norman, Etuk, Cerutti, Ouyang, Srivastava, Oren, Dropps, Allen and Sullivan2008). Our models use the random forests algorithm for the classification tasks, and the M5-rules (Holmes et al., Reference Holmes, Hall and Prank1999) for regressions. These approaches showed best performance.
We trained both levels by considering the AFs in which at least a solver succeeded. In total, we considered 8640 AFs: about 4000 with empty preferred extensions, 1700 with a single non-empty preferred extension, while the others have more than one preferred extension. The training set for the second level consists of about 2800 AFs with more than one preferred extension. Since the number of preferred extensions is on average 832.1 with a variance of 2310.9, we trained our regression models to predict log-number of extensions (i.e.
${\rm log}_{{10}} \,\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid\,$
) rather than absolute number (i.e.
$\!\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid\,$
): this has been effective in similar circumstances (Hutter et al., Reference Hutter, Xu, Hoos and Leyton-Brown2014).
6.3 Cross-validated results
Table 8 shows the results of the two-level EPMs in terms of accuracy—proportion of instances correctly classified—and precision—the proportion of true positives within a class.
Cross-validation of the classification model: accuracy and precision w.r.t. each considered class (percentages, higher is better)
Graph is the union of direct graph (DG) and undirect graph (UG) features.
Values in bold indicate the best results, also considering hidden decimals.
As to the first level, the All set of features (including all the considered features) provide the best model. According to the results shown, AFs which have a single non-empty preferred extension are the hardest to identify. It should be noted that the UG set of features, which correspond to information extracted from the UG representation of AFs, usually provide the worst predictive performance. Also, we observed that by removing the UG features from the All set, accuracy performance increases to 91.7%. UG features act like noise for the classification model. As expected from the principle-based analysis of argumentation semantics in Baroni and Giacomin (Reference Baroni, Caminada and Giacomin2007), where the directionality principle is shown to characterize preferred semantics, information regarding the direction of the attacks is important for predicting the structure of preferred extensions.
As to the second level classification, Matrix features reveal to be quite informative for accuracy and also precision in the class
$\,\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid\leq \,\bar{\chi }$
(together with All). However, it is worth mentioning that the precision for the class
$\,\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid\gt\,\bar{\chi }$
is slightly lower (85.3%), thus suggesting that the model is less accurate in classifying those AFs. Reasons for that are twofold. On one hand, while graph structures are quite informative at level 1 (i.e. to discriminate between only one empty extension, only one non-empty extension, or more than one extension), they are slightly less accurate in distinguishing between
$\bar{\chi }$
or
$\bar{\chi }\,{\minus}\,1$
or
$\bar{\chi }{\plus}1$
extensions. In addition, the test set is moderately unbalanced (60% of AFs has less than
$\bar{\chi }$
extensions), but given the good results (accuracy and precision between 85% and 90%), we chose not to apply techniques of oversampling to overcome this.
Table 9 shows the performance, in terms of RMSE, of regression models predicting the log-number of preferred extensions (i.e.
${\rm log}_{{10}} \,\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid\,$
). In this case, UG features are significantly worse than others. On the other hand, either using only Matrix-related or DG features allow to achieve better performance than the All set. This is probably due to the noise added by considering the UG set.
Root mean square error (RMSE) of
${\rm log}_{{10}} \,\mid\!{\cal E}_{\sigma } ({\rm \Gamma })\!\mid\,$
of the cross-validated regression model
Graph is the union of direct graph (DG) and undirect graph (UG) features.
Values in bold indicate the best results, also considering hidden decimals.
6.4 Most important features
The importance of features has been assessed using the CFS attribute evaluator, as described in Section 5. The most important features selected are:
∙ Classification, Level 1: number of SCCs (DG); average degree (DG); aperiodicity (DG).
∙ Classification, Level 2: ratio vertice-edges (DG); standard deviation degree (DG); size of maximal SCC (DG); flow hierarchy (DG); average lines sum (Matrix); norm lines sum (Matrix).
∙ Regression: standard deviation degree (DG); aperiodicity (DG); density triangles (UG); average triangles (UG); averages difference columns (Matrix).
As to the first level, by using the three obtained features it is possible to build a model with a 91.0% of accuracy. This indicates that a small set of features is extremely informative, and allows to achieve very good predictive performance. The remaining DG and Matrix performance are probably helpful in complex cases only.
As to the classification task at the second level, with the six identified features it is possible to build a model with 85.7% of accuracy, and with a great precision in the case of
$\,\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid\!\leq \,\bar{\chi }$
, viz. 89.1%, although not exceptional for the other case (78.9%).
By using the five features the CFS techniques selects for the regression task, it is possible to generate regression models with a RMSE of 2.36. This is better than using UG features only (cf. Table 8), but worse than any other set. Interestingly, CFS included features from each of the three considered sets. Intuitively, few of the UG features are informative with regards to the regression task.
6.5 Validation of models against argumentation frameworks with identifiable clusters of information
Frameworks generated using the AFBenchGen tool do not carry any sort of information: they are random sets of arguments organized according to a predefined structure. However, as demonstrated in other areas of AI such as SAT, instances that do carry information lead to results that are very different from those observed on randomly generated instances. For instance, in the case of SAT, information carried by Conjunctive Normal Forms (CNFs) usually relates to some manufacturing processes, and the relevant impact needs to be verified. To prove the generality of our approach w.r.t. the Argument Generation process—thus guaranteeing re-usability of our results in contexts not linked to our investigation—here we validate the proposed framework on AFs with identifiable clusters of information. In the following, their generation process, starting from automated planning problems, is detailed.
6.5.1 Deriving argumentation frameworks with identifiable clusters of information
Given a planning domain model and a problem, we:
1. encode the planning problem in SAT formulae (Sideris & Dimopoulos, Reference Sideris and Dimopoulos2010) in CNF: six different encodings have been considered, for a total of 500 different formulae;
2. transform each disjunction in a material implication: for example, a∨b∨c becomes ¬a∧¬b⊃c;
3. evaluate each material implication as a named strict rule (e.g. r: ¬a, ¬b→ c) and apply the transformation described in Wyner et al. (Reference Xu, Hutter, Hoos and Leyton-Brown2015) (see Figure 4)Footnote 9 .
Argumentation framework (AF) derived from r: ¬a, ¬b→c
The advantage of using planning domain models relies on the small number of operators and objects, which limits the size of resulting SAT formulae. We did not consider SAT instances from SAT competitions due to their size and complexity: in total, the considered solvers were able to analyze less than 10 instances. At the same time, we did not include the AFs proposed by Cabrio and Villata (Reference Cabrio and Villata2014) because there are very few of them.
We chose to use the approach presented by Wyner et al. (Reference Xu, Hutter, Hoos and Leyton-Brown2015) because there is a one-to-one syntactic correspondence between the SAT variables and the generated AF. Dealing with the entire model of argumentation, and thus connecting the two processes of argument generation, using for instance ASPIC+ from a propositional knowledge base, and of semantic evaluation of the proposition in the knowledge base, is already envisaged as the main future work.
6.5.2 Performance of empirical predictive models on argumentation frameworks with identifiable clusters of information
To evaluate the performance of the trained models we derived 500 AFs following the above procedure and using two well-known benchmark planning domains: Blocksworld and Ferry. The former deals with controlling a robot arm for re-assembling stackable blocks, the latter models the use of a ferry boat for moving cars between different islands. Out of the 500 considered AFs with identifiable clusters of information, the solvers successfully analyzed 200 of them, which have been included in our evaluation. The number of arguments range from 86 to ~2000, the number of attacks is between 136 and 4255. Also in this case the number of extensions has a great variance (1989.8) across the considered testing setFootnote 10 . We should remark that successfully analyzed AFs provide the ground truth for the correct evaluation of models.
Table 10 shows the results of classification and regression models against AFs with identifiable clusters of information. It clearly indicates that the classification model is very accurate also on AFs that are significantly different from the training ones. On the other hand, it is worth noting that the considered AFs derived from SAT formulae always have more than one preferred extension. Thus, they are all from the same class, according to the exploited classification model. For this reason, we are not showing precision results. Nevertheless, the predictive model is able to correctly identify all of them. Remarkably, the trend shown in Table 8 is confirmed by results in Table 10: features derived from the UG are not as informative as those from the other sets for the classification task. Also, a model based on the three features selected by using the CFS technique only, is able to correctly classify 100% of AFs.
Classification model evaluated against argumentation frameworks with identifiable clusters of information: accuracy and precision w.r.t. each considered class (percentages, higher is better)
Graph is the union of direct graph (DG) and undirect graph (UG) features.
Values in bold indicate the best results, also considering hidden decimals.
Although the set of AFs with identifiable clusters of information is very unbalanced—only 4.0% of the frameworks has less than
$\bar{\chi }$
extensions—the classification models perform very well, with an accuracy of 94.4% and an average recall of 96% from the features derived from the DG, which appears to be dominating also in the set of Graph as the results are identical. Considering only the six features selected by the greedy forward search on the CFS attribute selector, the accuracy is still quite high, 91.9%. Results presented in Table 10 also highlight the hardness of correctly identifying the (very few) frameworks that has less than
$\bar{\chi }$
extensions: UG, Matrix, and All sets of features show a 0.0 precision value, which indicates they are not able to correctly identify any of such frameworks. This possibly indicates that the structure of frameworks from this specific class is very different from the structure of those, from the same class, included in the training set.
Table 11 shows the performance of the regression model aimed at predicting the log-number of preferred extensions (i.e.
${\rm log}_{{10}} \,\mid\!{\cal E}_{{{\rm PR}}} ({\rm \Gamma })\!\mid$
). Results are significantly different from those observed in Table 8: the All set of features seems to include a lot of noise, and does not allow to make any prediction. Given the results on the Matrix and DG sets, it is reasonable to derive that noise is mainly from these two sets.
Root mean square error (RMSE) of
${\rm log}_{{10}} \!\mid\!{\cal E}_{\sigma } ({\rm \Gamma })\!\mid\,$
of the regression model evaluated against argumentation frameworks with identifiable clusters of information
Graph is the union of direct graph (DG) and undirect graph (UG) features.
Values in bold indicate the best results, also considering hidden decimals.
6.6 Discussion
In summary, according to the results in Tables 8 and 10, the proposed two-level approach shows good overall performance. This demonstrates that the predictive hierarchical model built on the considered training AFs (i.e. those described in Section 6.1) is able to address a testing set including differently structured frameworks, although the relative importance of the considered set of features changes, as will be shown below.
Interestingly, the classification models have generally better performance on this testing set than on the training one. This is probably due to the different structure of the AFs in training and testing sets. Moreover, the informativeness of the sets of features is similar in both the considered sets of instances for the first level of the hierarchical model, but not for the second level classifier, where it is evident that the features from the DG representation are much more informative for the testing (structured) AFs (Table 10).
As to the regression task, features extracted by considering the UG are very informative, and lead to accurate regression model. The regression model relying on the five features selected by the CFS method shows a RMSE of 2.9. This is better than the performance achieved by considering the All set of features, but slightly worse than those obtained by exploiting the UG features only. For confirming the importance of UG features, we applied the CFS technique directly on the testing set. Four features have been selected, two from the UG set, and two from the matrix encoding. Even though this selection might be affected by overfitting, given the number of considered AFs, we believe that the importance of the UG features for the regression task on testing frameworks is confirmed. Intuitively, in the regression task structured AFs have a topology which can effectively be synthesized by considering the UG representation only. Moreover, information added by considering the DG, or the matrix encoding, are misleading with regards to the task of predicting the number of preferred extensions.
7 Conclusions
This work provides an extensive investigation of the exploitability of automatically generated predictions in dealing with high-complexity problems. In order to perform such investigation, we introduced the largest set of features for AFs ever proposed in literature which analyses them both from a graph and matrix perspective. Results presented in Section 5 demonstrate that EPMs can be used to determine the ‘best’ algorithm—relatively to the CPU-time—with an accuracy of about 80%. Moreover, via an empirical investigation, we derive an algorithm selection approach, based on classification, which can identify the fastest algorithm in about the double of the number of cases where the most efficient algorithm outperforms the other ones (SCC-P), and about three times the number of cases of the second most efficient algorithm (ArgSemSAT). It is worth mentioning that the obtained results are consistent with previous empirical investigations (Cerutti et al., Reference Cerutti, Dunne, Giacomin and Vallati2013). For instance, according to Table 5, ArgSemSAT seems to be affected by the number of vertices (feature B1) much more than Aspartix and ArgTools. In Cerutti et al. (Reference Cerutti, Dunne, Giacomin and Vallati2013) we show that both Aspartix and ArgTools show behaviours independent from the cardinality of the set of arguments, while they depend on the percentage of attacks.
Results discussed in Section 6 confirms that we develop a model able to predict, with an overall accuracy of 91.4%, whether or not an AF has a unique empty preferred extension, a problem which is known to be NP-complete (Dunne & Wooldridge, Reference Dunne and Wooldridge2009). Moreover, inspired by the work of Baumann and Strass (Reference Baumann and Strass2014), where an approach for computing the maximum and average number of stable extensions is provided, using a hierarchical predictive model we can distinguish when there is one or more preferred extensions. Finally, if more than one preferred extension is predicted, predictive models are able to predict their log-number. Furthermore, we show how it is possible to discriminate around a pivotal number of extension with an accuracy ≥90.0% both using our randomly generated training set as well as the AFs with identifiable clusters of information.
This work opens the road to a large set of interesting future work and applications of the developed techniques. Future work can be envisaged both from a theoretical point of view—that is, determining potential inter-dependencies between set of features and semantics for the tasks identified in this paper—as well as from an ‘engineering’ perspective. A natural extension to the proposed algorithm selection investigation would be the analysis of portfolios: portfolio approaches are more complex than algorithm selection ones, since they have to (i) select a subset of solvers; (ii) order the solvers and; (iii) allocating CPU-time to each solver. Such increased complexity can potentially lead to further performance improvements: see, for instance, Cerutti et al. (Reference Cerutti, Vallati and Giacomin2018). We also envisage an analysis of the exploitability of predictive models for supporting different, and notably less computationally complex, reasoning problems. We are also interested in extending the set of considered features as well as of benchmarks, to include those of the recent International Competitions on Computational Models of Argumentation (Thimm et al., Reference Thimm, Villata, Cerutti, Oren, Strass and Vallati2016; Thimm & Villata, Reference Thimm and Villata2017). From a solvers’ perspective, it is important to assess the usefulness and impact of probing features: features that are computed by briefly running an existing algorithm on the given AF and extracting characteristics from that algorithm’s trajectory (Hutter et al., Reference Hutter, Xu, Hoos and Leyton-Brown2014). Also, different aspects of the structure of AFs can be considered for extracting more features, such as: information related to symmetric attacks, treewidth (Dunne, Reference Dunne2007; Dvořák et al., Reference Dvořák, Pichler and Woltran2012), acyclicity. Moreover, Dunne et al. (Reference Dunne, Dvořák, Linsbichler and Woltran2015) provides characterization theorems for realizing AFs given a set of extensions under different semantics, including preferred semantics. (Dunne et al., Reference Dunne, Dvořák, Linsbichler and Woltran2015, Proposition 10) indeed shows that if two (maximal) sets of arguments are involved, preferred semantics that satisfies incomparability of extensions is capable to deliver such extensions. Linking the study of features with realizability of AFs is an existing interesting line of future work.
Finally, we will further investigate regressive approaches in order to predict the number of extensions: an investigation in the context of stable semantics in order to provide a comparison with Baumann and Strass (Reference Baumann and Strass2014) is already envisaged, as well as for other semantics.
Among the applications mentioned in Section 1, we point out that the investigated predictive models can be exploited in existing argumentation-based decision support systems (Tamani et al., Reference Tamani, Mosse, Croitoru, Buche, Guillard, Guillaume and Gontard2015; Toniolo et al., Reference Valiant2015). For instance, CISpaces (Toniolo et al., Reference Valiant2015) is an argumentation-based research-grade prototype for supporting intelligence analysts in their sense-making process, now under consideration for transitioning into a commercial product by the US Army Research Laboratory. It supports intelligence analysts in sense-making via compelling hypotheses, where each hypothesis is a preferred extension. Being able to identify the best algorithm to compute preferred extensions is clearly an important feature, especially when the probabilistic engine of CISpaces is enabled, which requires to solve an argumentation problem—for example, the enumeration of preferred extensions—several times evaluating different probabilistic worlds. At the same time, if each preferred extension is an hypothesis that an analyst needs to assess, the more the extensions the more the cognitive burden on the analysts. In this respect, it becomes important to know in advance the number of extensions, and in particular if such number exceeds a given threshold. Moreover, this information can be exploited in environments where the structure of frameworks change frequently, and operators need to quickly obtain an overview of the structure of the solution, for example, in order to know in advance what to change in the knowledge base to reduce the expected number of extensions. We believe that it would be of extreme interest to evaluate how analysts will leverage the proposed tools.
Acknowledgement
The authors would like to acknowledge the use of the University of Huddersfield Queensgate Grid in carrying out this work. The authors also thank the anonymous reviewers for their helpful comments.
Appendix A: Matrix-related Features
Any AF with N arguments can be encoded as an N×N matrix. Given this encoding we are able to extract 98 features, divided in:
∙ Basic matrix (9):
1. Rank.
2. Sparsity of the matrix.
3. Number of non-zero elements.
4. Standard deviation of the matrix elements.
5. Average of the matrix elements.
6. Variance of the matrix elements.
7. Norm.
8. Determinant.
9. Sum of matrix diagonals.
∙ Sum the following statistics are computed on vectors resulting from sum of either columns or rows (14):
1. Standard deviation.
2. Minimum value.
3. Maximum value.
4. Average.
5. Variance.
6. Number of non-zero elements.
7. Norm.
∙ Cumulative sum the following statistics are computed on vectors resulting from cumulative sum of columns, rows, and diagonals (21):
1. Standard deviation.
2. Minimum value.
3. Maximum value.
4. Average.
5. Variance.
6. Number of non-zero elements.
7. Norm.
∙ Difference the following statistics are computed on vectors resulting from differences of cells on columns, rows, and diagonals (21):
1. Standard deviation.
2. Minimum value.
3. Maximum value.
4. Average.
5. Variance.
6. Number of non-zero elements.
7. Norm.
∙ Diagonals the following statistics are extracted by considering the first and second diagonal of the matrix (7):
1. Standard deviation.
2. Minimum value.
3. Maximum value.
4. Average.
5. Variance.
6. Number of non-zero elements.
7. Norm.
∙ Gradient the following statistics are extracted by considering the gradient of the vector resulting by (i) the sum of the rows, (ii) the sum of the columns, and (iii) the sum of the diagonals of the matrix (21):
1. Standard deviation.
2. Minimum value.
3. Maximum value.
4. Average.
5. Variance.
6. Number of non-zero elements.
7. Norm.
∙ Correlation the correlation value of the following couple of vectors (4):
1. Sum of columns, sum of rows.
2. Sum of columns, first diagonal.
3. Sum of rows, first diagonal.
4. gradient of sum of columns, gradient of sum of rows.
