argumentation (AA-CBR), previous work has used arbitrated dispute trees as a methodology for explanation. Those are dispute trees where nodes are seen as losing or winning depending on the outcome for the new case under consideration. In this work we show how arbitrated dispute trees can be readapted for diferent inputs, which allows a broader interpretation of them, capturing more of the input-output behaviour of the model. We show this readaptation is correct by construction, and thus the resulting reasoning based on this reuse is monotonic and thus necessarily a faithful explanation.
Recent work on explainability raises the question of what diferent types of explanations actually
mean. In particular, one general idea is that explanations can reveal information about model
behaviour on at least some other inputs. That is, an explanation can, at least in principle,
suggest some input-output behaviour of the model. Previous work has modelled this as a form
of reasoning, that can be possibly seen as non-monotonic when this usage of the explanation
for extrapolating model behaviour can be revised by further interactions [
Dispute trees have been proposed as explanations for argumentation methods, in particular
for classification with -, a model based on abstract argumentation (AA) for case-based
reasoning (CBR) [
Here we show how an ADT for classifying a new case can possibly be reused for other new cases. This shows that an ADT can be seen as “committing” to outcomes for other possible cases, instead of simply the case to be explained (and previous cases occurring in the ADT itself). Indeed, this reuse yields another admissible dispute tree, and is therefore a faithful explanation, by construction.
In this work we instantiate our previous model of interactive explanations to dispute trees in -, via a method of readapting a dispute tree providing explanation for a prediction. Such method is not always applicable but when it is it results in a provably faithful explanation. When modelling this as reasoning, we show this will result in a form of monotonic inference.
An abstract argumentation framework (AF) [
We will present - following the presentation of Paulino-Passos and Toni [
relation ̸∼ . Let = { , ¯} be the set of (all possible) outcomes, with the default outcome.
( , ) for ∈ , ∈ ) and a new case is of the form ( , ?) for ∈ . We also discriminate a particular element ∈ and define the default argument ( , ) ∈ × .
A casebase is coherent if there are no two cases ( , ), ( , ) ∈ such that = but ̸= , and it is incoherent otherwise.
For simplicity of notation, we sometimes extend the definition of ⪰ and ≁ to × , by setting ( , ) ⪰ ( , ) if ⪰ .
Definition 2. The AF mined from a dataset and a new case ( , ?) is (Args, ⇝ ), in which: • Args = ∪ {( , )} ∪ {( , ?)}; • for ( , ), ( , ) ∈ ∪ {( , )}, it holds that ( , ) ⇝ ( , ) if 1. ̸= , 2. ⪰ , and 3. ∄( , ) ∈ ∪ {( , )} with ≻ ≻ and = ; • for ( , )∈ ∪{( , )}, it holds that ( , ?)⇝ ( , ) if ( , ?)̸∼ ( , ). The AF mined from a dataset alone is (Args′, ⇝ ′), with Args′ = Args ∖ {( , ?)} and ⇝ ′=⇝ ∩(Args′ × Args′).
Definition 3. Let G be the grounded extension of the AF mined from and ( , ?), with default argument ( , ). The outcome for is if ( , ) is in G, and ¯ otherwise. Definition 4. The AF mined from alone and the AF mined from and ( , ?), with default argument ( , ), are regular when the following holds:
In this paper we will restrict our attention to regular mined AFs. We will refer to the (regular) AF mined from and ( , ?), with default argument ( , ), as ⪰ (, ), and to the (regular) AF mined from alone as ⪰ ().
Example 1. For concreteness, let us consider a simple example of credit application. Applicants will be described by two features: age and income. System developers decided from background knowledge and previous data that the default case of an applicant is of {age:30; income:25} (age in years, income in £1000 per year) and by the default it is denied ( = 0). The casebase is formed of the following cases:
= {({age:20; income:100}, 1), ({age:40; income:23}, 1), ({age:32; income:40}, 1), ({age:60; income:42}, 0), ({age:86; income:150}, 1)}
More formally, we could say inputs are elements of = R2, and outputs of = {0, 1}. We will interpret the partial order in the following way: {age:; income:} ⪯ { age:2; income:2} if i) 30 ≤ ≤ 2 or 2 ≤ ≤ 30; and ii) 25000 ≤ ≤ 2 or 2 ≤ ≤ 25000. Essentially, a case is smaller than when, for both dimensions (features), the value of the dimension for is between and the default value. Notice this means that the notion of atypicality, represented by the partial order ⪯ , is neither being too big or being too small. The corresponding framework is presented in Figure 1.
1Indeed this is not a strong condition, since it can be proved that if ̸⪰ then all cases ( , ) in the casebase could be removed, as they would never change an outcome. On the other hand, assuming also the first condition in Definition 4, if ( , ?) is the new case and ̸⪰ , then the outcome is ¯ necessarily.
A more in-depth discussion of interactive explanations as reasoning is in previous literature [
The motivation for interactive explanations is scenarios where a user evaluates the behaviour of a model via multiple, sequential, queries. They may ask for the output for a specific input, and ask as well for an explanation. The explanation may motivate then a new query, resulting in a new output and explanation. One may thus ask what should we a priori expect of such process, or such sequence of explanations. We thus consider an interactive process (as overviewed in Fig. 2), where the user queries for an output and explanation thereof, given an input, the system returns them, and then the user may query again. We see the AI system as including a classifier and an explainer, with both considered black-boxes by our conceptual model.
We assume that the explanation method (although not the classifier) can keep track of the history of inputs it received and their outputs. This allows supporting two scenarios: i) of an explainer that tries to improve its explanations by knowing what it explained before; and ii) of a malicious explainer that, trying to manipulate or mislead the user and to avoid being detected, keeps track of what was explained before.
Histories give a snapshot of the process by finite sequences of inputs and their outputs. Note that we assume the explainer to be a function, thus ignoring randomness of the explanation method itself. This assumption implies that no information about the computed explanations needs to be stored in the history, as awareness of earlier inputs and outputs already gives all information needed to infer what explanations were also previously returned. Example 2. Let us illustrate the framework with a model of counterfactual explanations. We will continue Example 1 and assume the classifier is a regular -⪰ model mined from . For illustrative reasons, we will assume this classifier is treated as a black-box model. As for the counterfactual explanations, we will not assume a particular algorithm, but we will assume it
User System 1.
Classifier 3. (, ), 2. (, )
Explainer
((0, 0), . . . , (, ))
ifnds a counterfactual by heuristical search [
This way, for a single input-output pair (, ), the method returns a new input-output pair ( , ). For describing the intended interpretation is: let (Δ, Δ) = − , and (Δ′, Δ′) such that 0 ≤ Δ′ ≤ Δ, and 0 ≤ Δ′ ≤ Δ. For any such (Δ′, Δ′), ′ = + (Δ′, Δ′) is intuitively a smaller change to than , and thus is expected to be classified as , and not as .
For example, for a case 0 = {age:50; income:50} the output is 0 = 1, if the counterfactual is 0 = ({age:75; income:43}, 0), then for input 1 = {age:65; income:45} the expected output would still be 1.
Now suppose a user interacts with the system querying for 0, receives 0 as output and 0 as an explanation. What would be expected if the user queries for 1, but instead receives 1 = 0 and 1 = ({age:59; income:43}, 1)? Is this an inconsistency of the method? Could it be solved?
We assume an input set and an output set as well as a set of possible explanations ℰ , that we keep abstract. Regarding notation, for a set , we denote the set of finite sequences of elements of as (), i.e., () = ⋃︀∈N for a sequence of elements of . Given ∈ N, we use the notation [] = { ∈ N | ≤ }. Thus a sequence (0, 1, . . . , ) ∈ () can be written as ()∈[].
We consider that the system is composed of a classifier C : → and an explanation method E : ( × ) → (ℰ ), mapping from a sequence of input-output pairs (, )∈[] to a sequence of explanations ()∈[], of the same length as the sequence of pairs. Notice that the explainer uses information on the entire past of inputs-outputs, as we discussed in Section 3.1. We can think of this sequence of pairs as a history. We consider that at each time step ∈ N, the user queries for an input ∈ , which receives a classification C() = and an explanation . In this way, the explainer provides an explanation motivated by a specific input-output, while considering the history ((, ))∈[− 1].
( × )
E (ℰ) |= ⊢ ⊢ × |= ℰ
An important particular case is when there is a function E∙ : × → ℰ , mapping from a single example (, ) to an explanation . In this case, the explainer function E can be defined as applying E∙ to each element of the sequence: formally, E(((, ))∈[]) = (E∙ (, ))∈[]. In this particular case the history is disregarded when explanations are computed.
This view of the interactive explanation process does not enforce that previously exhibited explanations are kept, that is, that is unchanged for all ∈ [] when +1 is queried. Past explanations being unretractable, in the sense that the system cannot replace the explanation of any previous query, is captured by the following property: Definition 5 (Interaction-stability). An explainer E is said to be interaction-stable whenever, for every sequence of input-output pairs (, )∈[] and for every < , if ()∈[] = E((, )∈[]) and (′)∈[] = E((, )∈[]) then = ′ for any ∈ [].
That is, an interaction-stable explainer will always keep the explanation associated to the pair (, ), even as the interaction moves on. It is straightforward to see that an explainer E derived from a function E∙ is always interaction-stable.
With this setup, inference can be defined. We assume that a sequence of explanations ()∈[] “commits” to some model behaviour. We model this by an entailment relation |= between (ℰ ) and × , in such a way that ()∈[] |= (, ) means that ()∈[] “commits” to the outcome , given the input . We will abuse notation and define |= (, ) to mean () |= (, ) (for () the sequence with just one explanation, ). This entailment relation we keep abstract and application-dependent. What is important is that it captures how a user would interpret the explanation or plausible inferences therefrom, including as regards the input-output being explained. One example is explanations as suficient reasons: any suficient reason is exactly a rule that guarantees the output for a part of the input space, including the given input. An important particular case of entailment is when it does not depend on the order of the elements of the sequence. In this case, a set-based representation would be enough, and it is in this sense that sequences generalise sets.
From this core notion of |=, relating explanations to input-output, we can derive two “homogeneous” notions of “entailment”, that is, from sequences of elements of a set to elements of the same set. This makes that notion more analogous to the notion of entailment in logic, which is defined from sets of formulas to a single formula. One such notion is at input-output level, and the other at explanation level. For the former, we say (, )∈[] ⊢ (, ) if E((, )∈[]) |= (, ). For the latter, ()∈[] ⊢ if ∀(, ) ∈ × , if |= (, ) then ()∈[] |= (, ) (summarised in Fig. 3).
We shall now define properties of explainers, in particular of consistency and non-monotonicity for the relations associated with explainers.
does not exist ∈ , , ′ ∈ , with ̸= ′, such that ()∈[] |= (, ) and ()∈[] |= (, ′). An entailment relation |= is said to be consistent if every sequence of explanations is consistent. A relation ⊢ is said to be consistent if there does not exist ∈ , , ′ ∈ , with ̸= ′, and ((, ))∈[] such that ((, ))∈[] |= (, ) and ((, ))∈[] |= (, ′).
Since the relations ⊢ and ⊢, derived from the base notion of |= , are “homogeneous”, we
can define properties borrowed from the literature on non-monotonic reasoning [
Also, given a set , a relation ⊢′ from () to , and , ∈ , for ∈ N, the relation ⊢′ is said to satisfy non-monotonicity if there is ()∈[], +1, s.t. ()∈[] ⊢′ and ()∈[+1] ̸⊢′ .
Which concrete methods satisfy which of those properties and what is the impact on user experience are open questions.
Example 2 (continued). An instantiation for counterfactuals as presented in this example is that an explanation is a tuple of original input, output, and counterfactual and counterfactual output (, , ). Thus the explainer E is interaction-stable, based on a E∙ that, given a single inputoutput pair, returns this tuple. The entailment relation is then defined as: for a single explanation = (, , , ), |= (′, ′) if: 1. ′ = and ′ = ; 2. ′ = and ′ = ; or 3. with (Δ, Δ) = − and (Δ′, Δ′) = − ′, 0 ≤ ′ = ′. Δ′ ≤ Δ, and 0 ≤ Δ′ ≤ Δ and
For a sequence of explanations, a naïve aggregation can be used: ()∈[] |= (′, ′) if there is such that |= (′, ′). Using this definition, the behaviour in Example 2 is inconsistent.
An alternative method could aggregate restricting by a specificity criterion: say covers ′ if there is ′ such that |= (′, ′). We say that 1 is more specific than 2 if the set of inputs covered by 1 is a subset of the set of inputs covered by 2. Then redefine for sequences in the following way: ()∈[] |= (′, ′) if there is such that |= (′, ′) and there is no such that |= (′, ′′), where ′ ̸= ′′. By this definition, even if 0 |= (1, 1), (0, 1) |= (1, 0) and (0, 1) ̸|= (1, 1). This would make such relation consistent and non-monotonic.
Dispute trees [
a child of such that is a L-node labelled by ;
labelled by some attacker of ; and
An example of a dispute tree is in Figure 4a. Dispute trees have been originally defined as
being possibly infinite, while Čyras et al. [
An arbitrated dispute tree explanation is a finite arbitrated dispute tree.
5. Arbitrated dispute trees as interactive explanations
While arbitrated dispute trees have been used as explanations in previous literature [
ADTs are way of presenting and explaining the behaviour of - as a more succinct structure than the entire argumentation framework. Our idea here is simply that such presentation can be generalised to other cases: intuitively, an ADT for a new case may show a set of suficient reasons for justifying a decision for another new case 2. In a sense, 2 does not need more information than was already presented in that ADT in order to be decided, therefore the rest of the AF is unnecessary. This can be verified simply by the structure of the decision tree and by checking for relevance. Let us first define this formally.
2This not being the case, some results from the original presentation are inapplicable, such as [3, Prop. 3.4].
Let be a dataset, and (Args, ⇝ ) = ⪰ () be its corresponding argumentation framework. Let be a new case, and be an ADT explanation for its prediction. Now let 2 be a second new case. Depending on the partial order relation, on the ADT and on the new cases, it might be possible to reuse the ADT , without looking at (Args, ⇝ ) directly, to decide the outcome for 2. Indeed, in that case another ADT would be generated as well.
The two core ideas are: 1) if a past case is relevant to the new case, then every case smaller than it is also relevant; 2) every attacker of a W-node is in an ADT (as a L-node).
be the node in the path from the root to which is maximally relevant to 2 (that is, there is no node in the path greater than it such that it is also relevant to ).
If all are W-nodes, then the predicted outcome for 2 is the same as the predicted outcome for . Besides, let 2 be the tree constructed by the following process: start with the subtree of ′ containing only and their ancestors, add all L-nodes which are children of in ′, and, finally, for each L-node added in this way, add as a child a new W-node labelled by 2.
When this is the case for new cases and 2, we will say can be readapted to 2. Before proving the theorem, let us illustrate the process: Example 3. Given our casebase , suppose we would like to have the prediction for 2 = {age:90; income:200} and an ADT explanation. One would notice that the outcome is 2 = 1 with the ADT in Figure 4a. The idea is, if one would like to predict for 0 = {age:50; income:50}, this ADT could be readapted in a straightforward way. The processed is illustrated in the remaining of Figure 4.
Proof of Theorem 10. For every , exists: by regularity, the default case (thus the root) is relevant to 2. Let us see that 2 is an ADT. Clearly the condition 1 is satisfied. Let us check conditions 3 and 4 for each node. For every branch, every node until satisfies the conditions in Definition 8, since is an ADT. Now consider . By assumption, every is a W-node. Again, since is an ADT for , for every , each child of it is included in as a L-node child. Since those are also in 2, the condition is satisfied for each . Next, each of those attackers require exactly one W-node as a child, attacking it. This is satisfied by every added W-node labelled by 2, which is an attacker since the arguments which label such L-nodes are irrelevant (otherwise would not be maximally relevant). Finally, since 2 has no attackers in ⪰ (, 2,), it satisfies the conditions of a leaf. Condition 5 is clearly satisfied.
The last requirement to check is whether condition 2 is satisfied. Indeed it is, since, given
that the other conditions are satisfied, then the set of arguments labelling W-nodes is in the
grounded extension of ⪰ (, 2), which can be verified by induction [ 3, Prop. 3.3]. Therefore
if the root is a W-node, it is in the grounded extension and thus the prediction if . Otherwise, it
is a L-node and then it has as a child which is a W-node, that is, the default argument is attacked
by the grounded extension (and thus not in it, since it is conflict-free) and so the prediction of
2 is the ¯.
5.2. The |= relation for dispute trees
Now we can instantiate our framework with dispute trees. We will define E∙ as a function
that receives a new case and its predicted outcome -⪰ (, ) = , and returns an
ADT explanation for it. While the choice of the decision tree could matter for practical
applications, for our purposes our concern is only that some decision tree is returned. Regarding
existence, it requires the argumentation frameworks to be acyclic. This can be achieved by
restricting ourselves to coherent casebases, or instead applying -⪰ , a variation of the
original method which guarantees acyclic AFs [
We can then easily instantiate the remaining of the framework, extending for sequences as previously suggested E(((, ))∈[]) = (E∙ (, ))∈[], and defining |= as: ( )∈[] |= (, ) if there is such that can be readapted to . Indeed, this readapted tree is precisely an explanation such that ⊢ .
The intuition for this relation is a possible answer to the question: what does and ADT explanation say about other inputs, beyond the originally one being explained? Surely it also reveals how the cases which label the appearing nodes are decided, but would that be all? What we show from Theorem 10 is precisely that, for a new input case, if, when filtering the tree for only nodes labelled by relevant arguments, all leaves are W-nodes, then not only we can guarantee what the output is, but also acquire an explanation for it via a transformation. Also notice that this all is done without running the prediction algorithm entirely from scratch. How could this be used to accelerate inference time in practice is outside the scope of this paper.
Another interesting aspect to notice is that, if there is a single L-node as a maximally relevant node, then nothing can be said. This can be seen from Figure 4. For a new case {age:19; income:110}, the only relevant case is the root (the default case), which is a L-case. However the prediction for it is still 1 since the case ({age:20; income:100}, 1) is relevant, and would attack the default case in the grounded extension. The slightly diferent new case {age:21; income:110} would have no such attacker.
We can then state the following consequences: Theorem 11. Let E(((, ))∈[]) = ()∈[], and (, ) ∈ × Then: 1. E is interaction-stable; 2. ()∈[] |= (, ) if there is an explanation such that ()∈[] ⊢ and |= (, ); 3. (faithfulness) if ()∈[] |= (, ), then -⪰ (, ) = . 4. |= is consistent; 5. |= is monotonic.
Those are straightforward from |= being defined from existence of an explanation in the sequence and from the fact that all arguments labelling W-nodes are contained in the grounded extension [3, Prop. 3.3].
ADT explanations are simple, but provably faithful explanations for -. This should not be surprising, since this inference relation is conservative: a single L-node as a maximally relevant node in the tree makes the entire ADT unusable.
A possible discussion is whether the entire set of ADTs for a input could not be returned instead.
While this is a possibility, likely for a practical application all this information would be used, but
still adapted and filtered in a way not to avoid overwhelming the final user. This is especially the
case since many diferent dispute trees could have overlaps, being partly redundant. Depending
on context, this could be less informative than having the entire argumentation framework,
since although not a tree, there is no repetition of cases in there. Thus having a single ADT
seems a more efective strategy. The condition is, as previously mentioned, that either the
casebase is coherent, or that -⪰ is used [
We leave for future work an exploration of how would ADTs be for real applications of -, including how often ADTs can be reused, and whether this can create gains in inference time. Another aspect left for future work is user studies for evaluating the efectiveness of ADT as explanations. An interesting question is whether ADTs with maximally relevant L-nodes could be readapted in some way, even if fallible. An idea would be considering those prima facie explanations, resulting in a non-monotonic entailment relation from sequences of explanations.
GPP was supported by Capes (Brazil, Ph.D. Scholarship 88881.174481/2018-01). FT was partially funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 101020934) and by J.P. Morgan