On Relating "Why?" and "Why Not?" Explanations
Authors: Alexey Ignatiev
Nina Narodytska
Nicholas Asher
Joao Marques-Silva
Venue:  (2021)
Keywords: Explanability
contrastive explanations
duality

Abstract: Explanations of Machine Learning (ML) models often address a ‘Why?’ question. Such explanations can be related with selecting feature-value pairs which are sufficient for the prediction. Recent work has investigated explanations that address
a ‘Why Not?’ question, i.e. finding a change of feature values that guarantee a change of prediction. Given their goals, these two forms of explaining predictions of ML models appear to be mostly unrelated. However, this paper demonstrates otherwise, and establishes a rigorous formal relationship between ‘Why?’ and ‘Why Not?’ explanations. Concretely, the paper proves that, for any given instance, ‘Why?’ explanations are minimal hitting sets of ‘Why Not?’ explanations and vice-versa. Furthermore, the paper devises novel algorithms for extracting and enumerating both forms of explanations.


Under review as a conference paper at ICLR 2021
ON RELATING 'WHY?' AND 'WHY NOT?' EXPLANATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Explanations of Machine Learning (ML) models often address 'Why?' question. Such explanations can be related with selecting feature-value pairs which are sufficient for the prediction. Recent work has investigated explanations that address a "Why Not?" question, i.e. finding a change of feature values that guarantee a change of prediction. Given their goals, these two forms of explaining predictions of ML models appear to be mostly unrelated. However, this paper demonstrates otherwise, and establishes rigorous formal relationship between 'Why?' and "Why Not?' explanations. Concretely, the paper proves that, for any given instance, 'Why?" explanations are minimal hitting sets of 'Why Not?' explanations and vice-versa. Furthermore, the paper devises novel algorithms for extracting and enumerating both forms of explanations.
INTRODUCTION
The importance of devising mechanisms for computing explanations of Machine Learning (ML) models cannot be overstated, illustrated by the fast-growing body of work in this area. A glimpse of the importance of explainable AI (XAI) is offered by a growing number of recent surveys and
overviews Hoffman & Klein (2017); Hoffman
al. (2017); Biran & Cotton (2017); Montavon
ct al. (2018); Klein (2018) 1 Hoffman et al. 2018 Adadi & Berrada (2018); (2018);AAoosss Alonso et al. (2018);
Dosilovic al. (018 ; Hoffman et al. (2018b); Guidotti et al. (2019); Samek et al. (2019) Samek
Müller (2019) Miller (2019b a): Anjomshoae et al. (2019); Mittelstadt et al. (2019): Xu et al. (2019).
Past work on computing explanations has mostly addressed local (or instance-dependent) explana- tions et al. (2016); Lundberg & Lee (2017); Ribeiro et al. (2018): (Shih et al. (2018) (209));
Ignatiev et al. [l]][(219)) 9a); Darwiche & Hirth (2020); Darwiche [ (2020). Exceptions include for example approaches that distill ML models, e.g. the case of NNs Frosst & Hinton (2017) among many oth- ers Ribeiro et al. 2016), or recent work on relating explanations with adversarial examples] Ignatiev et al. (2019b), both of which can be seen seeking global (or instance- -iniuneeeiddeeedeen) explanations. Prior research has also mostly considered model-agnostic explanations Ribeiro et al. (2016); Lund berg & Lee (017); Ribeiro et al. 2018). Recent work on model-based explanations, e.g. Shihh et al. Ignattie et al. (2019a), reters to local (or global) model-agnostic explanations as heuristic. given that these approaches offer no formal guarantees with respect to the underlying ML mode]" (017): Examples of heuristic approaches include Ribeiro et al. (2016); (2016);[nndie Lundberg & Lee (2017); Ribbiro et al. (2018), among many others In contrast, local (or global) model-based explanations are referred to as rigorous, since these offer the strongest formal guarantees with respect to the underlying ML model.
(2018): Ignatiev
Concrete examples of such rigorous approaches include Shih et (2018); Tran d' d'Avila Garcez (2018); Shhh al. (2019) Ignatiev et al. (2019a by: Darwiche & Hirth (2020) et al. (2019).
Most work on computing explanations aims to answer a 'Why prediction ? question. Some work proposes approximating the ML model's 's behavior with a linear model Ribeiro et al. (2016) Lundberg Leee 2017). Most other work seeks to find a (often minimal) set of feature value pairs which is sufficient for the prediction, i.e. as long as those features take the specified values, the prediction does not change. For rigorous approaches, the answer to a 'Why prediction x?? question has been referred as Pl-explanations Shih al. (2018 2019). abductive explanations Ignatiev al. (2019a), but also as (minimal) sufficient reasons Darwiche & Hirth (2020); (Dawwiche (2020). (Hereinafter, we use the term abductive explanation because of the other forms of explanations studied in the paper.)
A taxonomy of ML. model explanations used this paper is included in Appendix A
There is also recent XAI service offered by Google: hctps: // a1 oud googl com/
exp1 a nable-ai7 inspired similar ideas ideas 2019)

---

Under review as a conference paper at ICLR 2021
Another dimension of explanations, studied in recent work Miller (2119)), is the difference between explanations for "Why prediction x?" questions, c.g., "Why did I get the loan?', and for "Why prediction and not 8?" questions, e.g., "Why didn't 't I get the loan?'. Explanations for "Why Not?' questions, labelled by Miller] (2019b) contrastive explanations, isolate pragmatic component of explanations that abductive explanations lack. Concretely, an abductive explanation identifies a set of feature values which are sufficient for the model to make prediction π and thus provides an answer to the question 'Why x²' A constrastive explanation sets up counterfactual link between what was a (possibly) desired outcome of a certain set of features and what was the observed outcome Bromberger (1962); Achinstein (1980). Thus, a contrastive explanation answers a 'Why л and not 5?" question Miller (2018); Dhurandhar et al. 2018); Mittelstadt et al. (2019).
In this paper we focus on the relationship between local abductive and contrastive explanation One of our contributions is to show how recent approaches for computing rigorous abductive explanations Shih et al. (2018) 2019); Ignatiev et al. (2019a); Darwiche Hirth 2020): Darwiche (2020) can also be exploited for computing contrastive explanations. To our know knowledge, this is new. In addition, we demonstrate that rigorous mmodel-based local abductive and contrastive explanations are related by minimal hitting set relationship 3 which builds on the seminal work of Reiter in the 80s Reiter (9877). Crucially, this novel hitting set relationship reveals a wealth of algorithms for computing and for enumerating contrastive and abductive explanations. We emphasize that it allows designing the first algorithm to enumerate abductive explanations. Finally, we demonstrate feasibility of our approach experimentally. Furthermore, our experiments show that there is strong correlation between contrastive explanations and explanations produced by the commonly used SHAP explainer.
2 PRELIMINARIES
Explainability in Machine Learning. The paper assumes an ML model M, which is represented by a finite set of first-order logic (FOL) sentences M. (When applicable, simpler alternative representations for M can be considered, e.g. (decidable) fragments of FOL., (mixed-)intege) linear programming, constraint language(s), etc. A set of features F = =[1,...,ff } is assumed. Fach feature f; is categorical (or ordinal), with values taken from some set D,. An instance is an assignment of values to features. The space of instances, also referred to as feature (or instance) space, is defined by F = D2 D2 X X DL. (For real-valued features, suitable interval discretization can be considered.) A (feature) literal X; is of the form (fa = v;), with 8, E D,. In what follows, a literal will be viewed an atom, i.e. it can take value true false. As result, instance can be viewed as a set of L literals, denoting the L distinct features, i.e. an instance contains a single occurrence of a literal defined on any given feature. A set of literals is consistent if it contains at most one literal defined on each feature. A consistent set of literals can be interpreted as conjunction or as disjunction of literals; this will be clear from the context. When interpreted as a conjunction, the set of literals denotes a cube in instance space, where the unspecified features can take any possible value of their domain. When interpreted as a disjunction, the set of literals denotes a clause in instance space. As before, the unspecified features can take any possible value of their domain.
The remainder of the paper assumes a classification problem with a set of classes IK = [AI,.... K.M) )- A prediction E IK is associated with each instance X E F. Throughout this paper, an MI. model Mi will be associated with some logical representation (or encoding), whose consistency depends on the (input) instance and (output) prediction. Thus, we define predicate M C F x K, such that M(X, σ) is true iff the input X is consistent with prediction π given the ML model M We further simplify the notation by using (X) to denote a predicate M(X, x) for concrete prediction π. Moreover, we will compute prime implicants of Mn. These predicates defined on and represented as consistent conjunctions (or alternatively sets) of feature literals. Concretely, consistent
"In contrast with recent work Ignatiev al. 2019b). which studies the relationship between global model- based (abductive) explanations and adversarial examples.
AA local abductive (resp. contrastive) explanation is minimal hitting of the set of all local contrastive
(resp. abductive) explanations.
M is referred to as the (formal) model of the ML model M. The use of FOL is not restrictive, with fragments of FOL being used in recent years for modeling ML models in different settings. These include NNs Ignatiev
(2019a) and Bayesian Network Classifiers Shhh al. (2019), among others.
This altermative notation is used for simplicity and clarity with respect to earlier work Shih et al. 2018): g
Ignatiev et al. (2019a]h) b). Furthermore, defining M as predicate allows for multiple predictions for the same point in feature space. Nevertheless, such cases are not considered in this paper.
2

---

Under review as a conference paper at ICLR 2021
conjunction of feature literals 7 is implicant of M, if the following FOL statement is true:
v(X (X) - ()
(1)
The notation r Ma is used to denote that an implicant of Ma. Similarly, a consistent set of feature literals is the negation of an implicate of M, if the following FOL statement is true:
v(X E F)) - (VpxxM(X,,))
M2 M-F, or alternatively (μ=~M²) = (v V MptmMM) An implicant (resp. implicate v) is called prime if none of its proper subsets 7' & T (resp. v & 1)) is an implicant (resp. implicate). Abductive explanations represent prime implicants of the decision function associated with some predicted class =[
Analysis of Inconsistent Formulas. Throughout the paper, we will be interested in formulas F that are inconsistens (or unsatisfiable), i.c. FF= L, represented as conjunctions of clauses. Some clauses in F can be relaxed (i.e. allowed not to be satisfied) to restore consistency, whereas others cannot. Thus, we assume that F is partitioned into two first-order subformulas F = R. where R contains the relaxable clauses, and B contains the non-relaxable clauses. B can be viewed as (consistent) background knowledge, which must always be satisfied.
Given inconsistent formula F, represented
set of first-order clauses, identify the clauses that are responsible for unsatisfiabilitt among those that can be relaxed, as defined nex
Definition (Minimal Unsatisfiable Subset (MUS)) Let F B U R. denote an inconsistent of clauses (F== L). U C R is Minimal Unsatisfiable Subset (MUS) iff B BUUF 1 and Vurcu, B U u'K
Informally, an MUS provides the minimal information that needs to be added to the background knowledge to obtain an inconsistency; it explains the causes for this inconsistency. Alternatively, one might be interested in correcting the formula, removing some clauses in R to achieve consistency.
Definition (Minimal Correction Subset (MCS)) Let F BU denote an inconsistent set of clauses (FF LJ. T S R. is Minimal Correction Subset (MCS) iff B U R TV 1. and VT'ST, BURY AT.
A fundamental result in reasoning about inconsistent clause sets is the minimal hitting set (MHS) duality relationship between MUSes and MCSes Reiter (987): Birnbaum & Lozinskii (2003): MCSes are MHSes of MUSes and vere-versa. This result has been extensively used in the development of algorithms for MUSes and MCSes Bailey & Stuckey/ (2005):
: Liffiton & Sakallah (2008; Liffiton et al.
(2016), and also applied in number of different settings. Recent years have witnessed the proposal of a large number of novel algorithms for the extraction and enumeration of MUSes and MCSes Bacchus
& Katsirelos (2015); Liffiton al. (2016): Grééooire et al.) (2:18); Bendik et al. (2018). Although most work addresses propositional theories, these algorithms can easily be generalized to any other setting where entailment is monotonic, e.g. SMT de Moura & Bjørner (2008).
Running Example. The following example will be used to illustrate the main ideas.
Example We consider a textbook example Poole & Mackworth (2010) 7.1, page 289] addressing the classification of a user's 's preferences regarding whether to read or to skip given book. For this dataset, the set of features is:
{ A(utorr), T(hredd), L(ength), W(hereRead) }
All features take one of two values, respectively (known, unknown)) [new, followUp), (long, short) }. and (home, work]. An example instance is: {AA = known), (T new), (L long), (W = home)) This instance is identified e1 Poole & Mackworth ( (010)) with prediction skips. Figure Ia shows a possible decision tree for this example Poole & Mackworth (2010 The decision tree can be represented set of rules shown in Figure 1810
By definition of prime implicant, abductive explanations are sufficient reasons for the prediction. Hence the
names used in recent work: abductive explanations Ignatiev et al. (2019a). Pl-explanations Shih et al. (2018) 2019) and sufficient reasons Darwiche & Hirth (2020) : Darwiche 22000)
"The definitions in this section are often presented for the propositional case, but the extension to the
first-order case is straightforward.
'The choice of a decision tree aims only keeping the example(s) presented in the paper as simple as possible. The ideas proposed the paper apply to any MI. model that can he represented with FOI.. This encompasses any existing MI. model, with minor adaptations in case the ML. model keeps state.
The abbreviations used relate with the names in the decision tree, and serve for saving space.
3

---

Under review as a conference paper at ICLR 2021
Length?
IF
{L Ing)
THEN skips (R1)
long
short
IF
(L shrt) (T flUp) A (A ukwn)
THEN
skips
(R2)
IF
(L shrt) (T new)
THEN
reads
(R3)
skips
Thread?
IF
(L shrt) (T flUp) A (A = kwn)
THEN
reads
(R4)
followUp
new
(b) Rule set
reads
Author?
ML, W)
unknown
known
[[L ALLV-AATE - LATA A) + = skips)] ^
[(LA-TV-LATT ( = reads)
skips
reads
(c) Encoding of Mr
(a) Decision tree
Figure I: Running example Poole & Mackworth 2010
Our goal is to reason about the ML model, i.c. implement model-based reasoning, so we need to propose a logical representation for the MI. model.
Example For implementing model-based reasoning, we need to develop an encoding in some suitable fragment of FOL 11 O-place predicates 12 are used for L, T, A and W, as follows. We will associate (L long) with and (L short) with -L. Similarly, we associate (T new) with -T, and (T followUp) with T. We associate (A known) with A and (A unknown) with -A Furthermore, we associate (W = home) with -W and (W = work) with W. An example encoding is optional (i.e. propositional values could be used) and serve to illustrate how non non-prroosiitional valued could be modeled.
shown in Figure Ic The explicit values
3 CONTRASTIVE vs. ABDUCTIVE EXPLANATIONS
Recent work Shih et al. (2018 2019); Ignatiev al. 2019ab; Darwiche 2020) proposed to relate model-based explanations with prime implicants. All these approaches compute a set of feature values which, unchanged, are sufficient for the prediction. Thus, one can view such explanations as answering a 'Why?' question: the prediction is the one given, as long as some selected set of feature values the one given. In this paper, such explanations will be referred motivated by one of the approaches used for their computation Ignatiev et al. (2019a).
abductive explanations,
3.1 DEFINING ABDUCTIVE EXPLANATIONS (AXPS)
As indicated earlier in the paper, we focus on local model-based explanations. Definition (Abductive Explanation) Given an instance т, with a prediction x. and an ML model represented with predicate M,. i.e. TF Mx, an abductive explanation is minimal subset of literals of r, a C T, such that o F M
Example 3 With respect to Example 1 let us consider the instance (A known, T new, short, W = work), which we will represent instead as
-L, W), corresponding to prediction reads. By inspection of the decision tree (sedFigure laß. possible answer to the 'Why pred. reads?' question is: -TL. In this concrete case we can conclude that this is the only abductive explanation, again by inspection of the decision tree.
3.2 DEFINING CONTRASTIVE EXPLANATIONS (CXPS)
As Miller (019b) notes, contrastive explanations are,
"sought in response particular counterfactual cases... That is, people do not ask why event P happened, but rather why event P happened instead of some event Q."
Depending the MI. problem, more expressive fragments of FOL. logic could be considered Kraening Strichman| (2016). Well-known examples include real, integer and integer-real arithmetic, but also nonlinear arithmetic Kroening & Strichman (2016). 12 Which this used as propositional variables.
4

---

Under review as a conference paper at ICLR 2021
As result, are interested in providing answer to the question "Why π and not 8?', where is the prediction given some instance т, and is some other (desired) prediction.
We consider again [xample 1 but with the instance specified in Example 3 A possible answer to the question "Why pred. reads and not pred. skips??' is {L}. Indeed, given the inpur instance (A,-T, -L, W), if the value of feature L changes from short to long, and the value of the other features remains unchanged, then the prediction will change from reads to skips.
Example 4
The following definition of a (local model-based) contrastive explanation captures the intuitive notion of the contrastive explanation discussed in the example above.
Definition 4 (Contrastive Explanation) Given an instance т, with a prediction n, and an ML model represented by predicate Ma. i.e. T FMg, a contrastive explanation is a minimal subset of literals Tf T, p S T, such that T pاl M.
This definition means that, there is an assignment to the features with literals in p. such that the prediction differs from и. Observe that a CXp is defined to answer the following (more specific) question 'Why (pred. π and) not -m? The more general case of answering the question 'Why (pred. π and) not 8?" will be analyzed later.
3.3 RELATING ABDUCTIVE & CONTRASTIVE EXPLANATIONS
The previous section proposed a rigorous, model-based, definition of contrastive explanation. Given this definition, one can think of developing dedicated algorithms that compute CXps using decision procedure for the logic used for representing the ML model. Instead, we adopt a simpler approach. We build on a fundamental result from model-based diagnosis Reiter (1987) (and more generally for reasoning about inconsistency Birnbaum & Lozinskil (2003); Bailey & Stuckey (2005) and demonstrate a similar relationship between AXps and CXps. In turn, this result reveals variety of novel algorithms for computing CXps, but also offers ways for enumerating both CXps and AXps. Local Abductive Explanations (AXps), Consider a set of feature values т. s.t. the predicion is n. for which the notation 7 F M2 is used. We will use the equivalent statement, 7 A -M L. Thus,
T ~
(3)
inconsistent, with the background knowledge being B A -M and the relaxable clauses being R L 7. As proposed in Shih et al. (2018); Ignatiev et al. (201aa), a (local abductive) explanation is a subset-minimal set a of the literals in such that, a ^ -M, F Thus, a denotes subset of the example's ' input features which, no matter the other feature values, ensure that the ML model predicts Thus, any MUS of equation iis (local abductive) explanation for M to predict π given T. Proposition 1 Local model-based abductive explanations are MUSes of the pair (5, R), T -M.. where R 2 T and 2 -Ma-
[
Example 5 Consider the ML model from Example 1 the encoding from Example 2 and the instance with prediction π = skips (wri) Figure 1 we replace skips = skips with truc and skips reads with false). We thus confirm that 7 Mr. We observe that the following holds:
{A,
A AA-TALA - [L [LLV ALV-LLTAN
truc] A (L-LL-TV-LLTAAA
+ false]
(4)
which can be rewritten as,
A AA-TALA W A [[L -LTAA A -rree] V (-LA-TV-LATANE -false
(5)
is easy to conclude that equation Flis inconsistent. Moreover, a = (L) denotes an MUS oUS ef and denotes one abductive explanation for why the prediction is skips for the instance T.
Local Contrastive Explanations (CXps). Suppose we compute instead an MCS p of equation 3
with p C T. As result, , (!) A -M, F holds. Hence, assigning feature values to the inputs of the ML model is consistent with a prediction that is not n, i.c. prediction of some value other than æ. Observe that p is a subset-minimal set of literals which causes 7 Ap -M to be satisfiable, with any satisfying assignment yielding a prediction that is not π.
Proposition 2 Local model-based contrastive explanations are MCSes of the pair (B, R), T A A-M.
where R 2 T and B A -M
5

---

Under review as a conference paper at ICLR 2021
Example 6 From equation 3 and equation 5
we can also compute p - such that \p K,
For example p = (L) is an MCS of equation 5 11
Thus. from -T, -W} we can get a prediction
other than skips, by considering feature value-
Duality Among Explanations. Given the results above, and the hitting set duality between MUSes and MCSes Reiter y: Birnbaum & Lozinskii (2003), we have the following.
Theorem AXps are MilSes of CXps and vice-versa.
Proof. Immediate from Definition Definition Proposition
Proposition
2 and Theorem 4.4 and
Corollary 4.5 of Reiter (1987).
D
Proposition Proposition 2, and Theorem can now serve to exploit the vast body of work on the analysis inconsistent formulas for computing both contrastive and abductive explanations and, arguably more importantly, to enumerate explanations. Existing algorithms for the extraction and enumeration of MUSes and MCSes require minor modications to be applied in the setting of AXps and CXps (The resulting algorithms are briefly summarized in Appendix BJ Interestingly, a consequence of the duality is that computing an abductive explanation is harder than computing a contrastive explanation in terms of the number of calls to decision procedure Appendix B).
Discussion. As observed above, the contrastive explanations we computing answer the question: 'Why (T and) not - A more general contrastive explanation would be 'Why (I and) not 6, with π + 8?" Miller (2019b). Note that, since the prediction π is given, we are only interested in changing the prediction to either - or 8. We refer to answering the first question as a basic contrastive explanation, whereas answering the second question will be referred to as a targeted contrastive explanation, and written as CXp;- The duality result between AXps and CXps in Theorem I applies only to basic contrastive explanations. Nevertheless, the algorithms for MCS extraction for computing a basic CXp can also be adapted to computing targeted CXps, as follows. We want a pick of feature values such that the prediction is 8. We start by letting all features to take any value, and such that the resulting prediction is 6. We then iteratively attempt to fix feature values to those in the given instance, while the prediction remains 6. This way, the set of literals that change value are a mubset-minimat set of feature- value pairs that is sufficient for predicting 8. Finally, there are crucial differences between the duality result established in this section, which targets local explanations, and recent result Ignatiev al. (2019b), which targets global explanations. Earlier work established a relation between prime implicants and implicates as a way to relate global abductive explanations and so-called counterexamples. In contrast, we delved into the fundamentals of reasoning about inconsistency, concretely the duality between MCSes and MUSes, and established a relation between model-based local AXps and CXps.
4 EXPERIMENTAL EVALUATION
This section details the experimental evaluation to assess the practical feasibility and efficiency of the enumeration of abductive and contrastive explanations for few real-world datasets, studied in the context of explainability and algorithmic fairness. To perform the evaluation, we adapt powerful algorithms for enumeration MCSes or MCSes and MUSes find all abductive and contrastive explanations Bailey & Stuckey (2005); Liffiton & Sakallah (2008): Grégoire et al. (011)) Bendik al. (2018) Algorithm I and Algorithm 2 in Apppeddix show our adaptations of MCS (resp. MCS and MUS) enumeration algorithms to the enumeration of CXps (resp. AXps and CXps).
Enumeration of CXps. These experiments demonstrate novel, unexpected practical use case of CXps enumeration algorithms. In particular, we show that our method gives a new fine-grained view on both global and local standard explanations extracted from ML models. The goal of these experiments is to gain better understanding of existing explainers rather than generate all CXps for a given input. We conduct two sets of experiments. The first experiment, called "real vs fake", distinguishes real from fake images. A dataset contains two classes of images: (a) original MNIST digits and (b) fake MNIST digits produced by a standard DCGAN model Radford et al. (2016) (see Figure 2a and Figure 2g for typical examples). The second experiment, called "3 vs 5 digits". uses dataset that contains digits "3" and "5" from the standard MNIST dataset (discussed in Appendix C.T). Next, we discuss the results of the "real vs fake" experiment in details (Figure 2). For "real vs fake".
13 Althoughh in general not the case, in Example 5 and Example an MUS of size 1 is also an MCS of size 1. The prototype and the experimental setup are available at wwt.tttpsss/. / /i thub. com/ /nduax waduaaxxuuuaaaa /xxuaal

---

Under review as a conference paper at ICLR 2021
6
(a) Real 6
(b) XGBoost
(c) SHAP
(d) CXp'
(c) CXp²
(1) CXp
6
(g) Fake 6
(h) XGBoost
(i) SHAP
() CXp
(k) CXp'
CXp*
Figure 2: The 'real vs fake' images. The first row shows results for the real image 6; the second results for the fake image The first column shows examples of inputs; the second - heatmaps of XGBoost's important features; the third - heatmaps of SHAP's explanation. Last three columns show heatmaps of CXp of different cardinality. The brighter pixels are more influential features.
we train an XGBoost model Chen & Guestrin (2016) with 100 trees of depth 6 (accuracy 0.85/0.80 on train/test sets). We quantized images so that each pixel takes a value between 0 and 15, image pixels are categorical features in the model.
Brief overview of the SHAP explainer. Given classifier f and an explainer model g. SHAP aims to train g be similar to f in the neighborhood of some given point æ. The objective function for SHAP is designed so that: (1) g approximates the behavior of the black box f accurately within the vicinity of and (2) achieves lower complexity and is interpretable: {xx) = arg mingeg L(T2; 9, J) + Mgg), where the loss function is defined to minimize the distance between I and g the neighborhood of x using weight function ग. and (2(g) quantifies the complexity of g: (2(g) and Te are defined based on game-theoretic notions (Lundberg & Lee 2017).
Global and local explainers. We start by discussing our results on a few samples (Figure 2a and Figure 2g. First, we extract important features provided by XGBoost. As these features are global for the model, they are the same for all inputs (Figure 2b and Figure 2h are identical for real and fake images). Figure shows that these important features are very informative for this dataset as these pixels form a blob of pixels that cover an image. Then we compute an image-specific explanation using the standard explainer SHAP (see Figure 2c|for the real image and Figure 2i for the fake image).
SHAP explanations are more focused on specific parts of images compared to XGBoost. However, still not easy to gain insights about which areas of an image are more important as pixels all over the image participate in the explanations of SHAP and XGBoost. For example, both XGBoost and SHAP distinguish some edge and middle pixels as key pixels (the bright pixels are more important) but it is not clear why these are important pixels.
CXps enumeration approach. We recall that our goal is to investigate whether there is a connection between the important pixels that SHAP/XGBoost finds and CXps for given image. The most surprising result is that, indeed, a connection exists and, for example, it reveals that the edge pixels of an image, highlighted by both SHAP and XGBoost as important pixels, are, in fact, CXps of small cardinalities. Given all CXps of size k, we plot heatmap of occurrences of each pixel in these CXps of size k. Let us focus on the first row with the real Consider the heatmap CXp' Figure 2d that shows all CXps of size one for the real 6. It shows that most of important pixels of XGBoost and SHAP are actually CXps of size one. This means that is sufficient to change single pixel value to some other value to obtain different prediction. Note that these results reveal an interesting observation. DCGAN generates images with a few gray edges pixels (see Figure 4 in Appendix. Indeed, some of them have several edge pixels in gray.) This 'defect' does not happen often for real MNIST images. Therefore, the classifier 'hooks' on this issue to classify an image as fake. Now, consider the heatmap CXp² at Figure 2e of CXps of size two. It overlaps a lot with SHAP important pixels in the middle of the image explaining why these are important. Only a pair of these pixels can be changed to get different prediction.
A correlation between CXps and SHAP's important features. To qualitatively measure our observa- tions on correlation between key features of CXps and SHAP, we conducted the same experiment as
7

---

Under review as a conference paper at ICLR 2021
Dataset
Adult
Lending
Recidivism
Compas
German
Spambase
instances
5579.0
4414.0
3696.0
778.0
1030.0
2344.0
total time (sec.)
7666.9
443.8
3688.0
78.4
16943.2
6859.2
minimal time (sec.)
0.1
0.0
0.1
0.0
0.2
0.1
average time (sec.)
1.4
0.1
1.0
0.1
16.9
2.9
maximal time (sec.)
13.1
0.8
8.9
0.5
193.0
23.1
total oraele calls minimal oracle calls average oracle calls
990.0
65.053
581 716.0
227.0
176 354.0
14.0
11.0
17.0
13.0
23.0
12.0
88.4
15.8
157.4
27.3
748.2
75.2
maximal oraele calls
581.0
73.0
1426.0
134.0
7829.0
353.0
of Axps
52 137.0
8105.0
60688.0
1931.0
592.22.0
876.0
average # of AXps average AXp size
9.4
1.8
16.4
2.5
59.2
8.1
5.3
1.9
6.4
3.8
7.5
total of CXps average of CXps average CXp size
66 219.0
8663.0
77 784.0
3558.0
66 781.0
774.0
11.9
2.0
21.1
4.6
66.8
10.6
2.4
1.4
2.6
1.5
3.6
2,3
Table 1: Results of the computational experiment on enumeration of AXps and CXps.
above on 100 random images and measured the correlation between CXps and SHAP features. First, compute set T of pixels that is the union of the first (top) 100 smallest size CXps. On average, we have 60 pixels in T. Note that the average 60 pixels represent a small fraction (7%) of the total find set S of [T] SHAP pixels with highest absolute weights. Finally, compute corr = IS n |/|S| as the correlation measure. Note that corr = 0.4 on average, i.c. our method hits 40% of best SHAP features. As the chances of two tools independently hitting the same pixel (out of 784) are quite low, the fact that 40% of |S| are picked indicates a significant correlation.
number of pixels. Then
Enumeration of CXps and AXps Here, we aim at testing the scalability of explanation enumera- tion and consider the six well-known and publicly available datasets. Three of them were previously studied in Ribeiro et al. (018) in the context of heuristic explanation approaches, namely, An- chor Ribeiro al. (2018) and LIME Ribeiro et al. (2016), including Adult, Lending, and Recidivism. Appendix C.2 provides a detailed explanation of datasets and our implementation. A prototype imple- menting is an adaptation of Liffiton & Sakallah (2008) abductive (2) all contrastive explanations was created. In the experiment, the prototype implementation is instructed to enumerate all abductive explanations. The prototype is able to deal with tree ensemble models trained with XGBoost [Chen & Guestrin (2016). Given a dataset, we trained an XGBoost model containing 50 trees per class, each tree having depth 3. (Further increasing the number of trees per class and also increasing the maximum depth of a tree did not result in significant increase of the models' accuracy on the training and test sets for the considered datasets.) All abductive explanations for every instance of each of the six datasets were exhaustively enumerated using the duality-based approach (Algorithm 2 in Appendix B). This resulted in the computation of all contrastive explanations as well).
Evaluation results. Table shows the results. There are several points to make. First, although it seems computationally expensive to enumerate all explanations for a data instance, it can still be achieved effectively for the medium-sized models trained for all the considered datasets. This may on average require from a few dozen to several hundred of oracle calls per data instance (in some cases, the number of calls gets up to few thousand). Also observe that enumerating all explanations for an instance takes from a fraction of a second to a couple of seconds on average. These results demonstrate that our approach is practical.
Second, the total number of AXps is typically lower than the total number of their contrastive counterparts. The same holds for the average numbers of abductive and contrastive explanations per data instance. Third and finally, AXps for the studied datasets tend to be larger than contrastive explanations. The latter observations imply that contrastive explanations may preferred from a user's perspective, as the smaller the explanation is the easier it is to interpret for human decision maker. (Furthermore, although it is not shown in Table I we noticed that in many cases contrastive explanations tend to be of size 1, which makes them ideal to reason about the behaviour of an ML model.) On the other hand, exhaustive enumeration of contrastive explanations can be more time consuming because of their large number.
Summary of results. We show that CXps enumeration gives insightful understanding of classifier's ' behaviour. First, even in cases when we cannot enumerate all of CXps to compute AXps by duality, still draw some conclusions, e.g. CXps of size one are exactly features that occur
8

---

Under review as a conference paper at ICLR 2021
in all AXps. Next, clearly demonstrate the feasibility of the duality- based exhaustive enumeration of both AXps and CXps for a given data instance using a more powerful algorithm that performs enumeration of AXps and CXps.
CONCLUSIONS
This paper studies local model-based abductive and contrastive explanations. Abductive explanations answer 'Why?' questions, whereas contrastive explanations answer "Why Not?" questions. Moreover, the paper relates explanations with the analysis of inconsistent theories, and shows that abductive explanations correspond to minimal unsatisfiable subsets, whereas contrastive explanations can be related with minimal correction subsets. As consequence of this result, the paper exploits a well-known minimal hitting set relationship between MUSes and MCSes Reiter (1987); Birnbaum & Lozinskil (2003) to reveal the same relationship between abductive and contrastive explanations. In addition, the paper exploits known results on the analysis of inconsistent theories, to devise algorithms for extracting and enumerating abductive and contrastive explanations.
REFERENCES
P. Achinstein. The Nature of Explanation. Oxford University Press, 1980.
Amina Adadi and Mohammed Berrada. Peeking inside the black-box: A survey explainable artificial intelligence (XAI). IEEE Access, 6:52138-52160, 2018. doi: 10.1109/ACCESS.2000 2870052.
José M. Alonso, Ciro Castiello, and Corrado Mencar, A bibliometric analysis of the explainable artificial intelligence research field. In IPMU, pp. 2018 doi: 10.10779783333119-944--21111
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. http: dd7m 2016.
Sule Anjomshoae, Amro Najjar, Davide Calvaresi, and Kary Främling. Explainable agents and robots: Results from a systematic literature review. In AAMAS, pp. 1078-1088, 2019.
Fahiem Bacchus and George Katsirelos. Using minimal correction sets to more efficiently compute minimal unsatisfiable sets. In CAV, pp. 86, 2015.
James Bailey and Peter J. Stuckey. Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization. In PADI., pp. 174-186, 2005.
Jaroslav Bendík, Ivana Cerná, and Nikola Benes. Recursive online enumeration of all minimal unsatisfiable subsets. In ATVA, pp. 143- 2018
Or Biran and Courtenay Cotton. Explanation and justification machine learning: A survey. In IJCAI-17 workshop explainable Al (XAI), volume 8, pp. 2017.
Elazar Birnbaum and Eliezer Lozinskii. Consistent subsets of inconsistent systems: structure and behaviour. J. Exp. Theor. Artif. Intell., 15(1):25-46, 2003.
Alessio Bonfietti, Michele Lombardi, and Michela Milano. Embedding decision trees and random forests in constraint programming. In CPAIOR, pp. 74-90, 2015.
S. Bromberger. An approach explanation. In R. Butler (ed.), Analytical Philsophy, pp. 105 Oxford University Press, 1962.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In KDD, pp. 785-794.
ACM, 2016.
Adnan Darwiche. Three modern roles for logic in Al. CoRR, abs/2004.08599, 2020. URL https
w/arxii. aarxiv.erg/abs/204.. 08599
Adnan Darwiche and Auguste Hirth. On the reasons behind decisions. CoRR, abs/2002.0922 2020.
URL wtt.hhttt///aaatit abs /2002. 09284

---

Under review as a conference paper at ICLR 2021
Leonardo Mendonça de Moura and Nikolaj Björner. Z3: efficient SMT solver. In TACAS, pp- 337-340, 2008.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Pai-Shun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In NIPS, pp. 590-601, 2018.
Filip Karlo Dosilovic, Mario Breic, and Nikica Hlupic. Explainable artificial intelligence: A survey. In MIPRO, pp. 210-215, 2018. doi: 1.33199MIRR.22088... 88400000
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt::ttpacchh/ee Ics. edu.m
FairMI.. Auditing black-box predictive models. http://tiny.cc// 6m 2016.
Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In KDD, pp. 259-268. ACM, 2015.
Alexander Felfernig, Monika Schubert, and Christoph Zehentner. An efficient diagnosis algorithm for inconsistent constraint sets. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 26:53 -
62, 01 2012. doi: 10:1017/5089000441 1000011.
Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasuubaamanian. On algorithmic faimess, discrimination and disparate impact. 2015.
Sorelle A. Friedler, Carlos Scheidegger, Suresh Venkatasubramaniinn, Sonam Choudhary, Evan P. Hamilton, and Derek Roth. A comparative study of fairness -ainnss-enhanccng interventions in machine learning. In FAT, pp. 329-338. ACM, 2019.
Nicholas Frosst and Geoffrey E. Hinton. Distilling neural network into a soft decision tree. In CE*@AI*IA, 2017.
Marco Gario and Andrea Micheli. PySMT: a solver-agnostic library for fast prototyping of SMT- based algorithms. In SMT Workshop, 2015.
Google. Explainability Whitepaper. http:://iin..cc/tjj/// 2019.
Éric Grégoire, Yacine Izza, and Jean-Maric Lagniez. Boosting MCSes enumeration. In IJCAI, pp. 1309-1315, 2018.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri. Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM Comput. Surv., 51(5): 93:1-93:42, 2019.
doi: 10.1 145/3236009.
Robert R. Hoffman and Gary Klein. Explaining explanation, part 1: Thcoretical foundations. IEEE Intelligent Systems, 32(3):68-73 2017. doi: 10.1 109/MIS.2017.54
Robert R. Hoffman, Shane T. Mueller, and Gary Klein. Explaining explanation, part 2: Empirical foundations. IEEE Intelligent Systems, 32(():78-88) 86, 2017. doi: 10.1109/MIS.000 2017.312211..
Robert R. Hoffman, Tim Miller, Shane Mueller, Gary Klein, and William J. Clancey. Explaining explanation, part 4: deep dive on deep nets. IEEE Intelligent Systems, 33(3):87-95, 2018a. doi: 10.1 10.1009/MI.AAR 201.20018000000 0330033332
Robert R. Hoffman, Shane T. Mueller, Gary Klein, and Jordan Litman. Metrics for explainable AI: challenges and prospects. CoRR, abs/ 812.04608, 2018b.
IBM ILOG. IBM ILOG: CPLEX optimizer 12.10.0.
2020. Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Abduction-based explanations for machine learning models. In AAAI, pp. 1511-1519, 2019a.
Alexey Ignatiev, Nina Narodytska, and Joao Marques-Sine Silva. On relating explanations and adversarial examples. In NewrIPS, pp. 15857-15867, 2019b.
10

---

Under review as a conference paper at ICLR 2021
Susmit Jha, Tuhin Sahai, Vasumathi Raman, Alessandro Pinto, and Michael Francis. Explaining Al decisions using efficient methods for learning sparse boolean formulae. J. Autom. Reasoning, 63
(4):1055-1075, 2019.
Ulrich Junker. QUICKXPLAIN: preferred explanations and relaxations for over-constrained probles In AAAI, pp. 167-172, 2004.
Gary Klein. Explaining explanation, part 3: The causal landscape. IEEE Intelligent Systems, 33(2):
83-88, 2018. doi: 10.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In KDD, pp- 202-207, 1996.
Daniel Kroening and Ofer Strichman. Decision Procedures An Algorithmic Point of View, Second Edition. Texts in Theoretical Computer Science. An EATCS Series. Springer. 2016. ISBN
doi: 10. 6-2----77--
URL htttpt:/ org/00.rg/00... 1007/
1-8-3-662-20
Mark Liffiton and Karem Sakallah. Algorithms for computing minimal unsatisfiable subsets of constraints. J. Autom. Reasoning, 40(1): 2008.
Mark H. Liffiton, Alessandro Previti, Ammar Malik, and Joao M. Silva. Fast, flexible MUS enumera- tion. Constraints, 21(2):223-250, 2016.
Michele Lombardi, Michela Milano, and Andrea Bartolini. Empirical decision model learning. Artif. Intell., 244:343-367, 2017.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In NIPS, pp.
4774,, 2017.
Tim Miller. Contrastive explanaaion A structural-mode: approach. CoRR, abs/ 0bb//1811.03163, 2018.
URL http:://aaai...rrr//////111..... 03163
Tim Miller. "but why?" understanding exadersttadinggexlllaaabbaa artificial intelligence. ACM Crossroads, 25(3):
20-25, 2019a. doi: 10.1 10/333//33
Tim Miller. Explanation in artificial intelligence: Insights from the social sciences. Artif. Intell., 267:
1-38, 2019b. doi:
Brent D. Mittelstadt, Chris Russell, and Sandra Wachter. Explaining explanations in AI. In FAT, pp. 279-288, 2019. doi: 1 /..114//227550.228777777
Grégoire Montavon, Wojciech Samek, and Klaus-Robert Müller. Methods for interpreting and understanding deep neural networks. Digital Signal Processing, 73:1-15, 2018. doi: 10.1016/j. 1.p.2017.10.001.
Nina Narodytska, Nikolaj Bjørner, Maria-Cristina V. Marinescu, and Mooly Sagiv. Core-guided minimal correction set and core enumeration. IJCAI, pp. 1353-1361, 2018.
Laurent Perron and Vincent Furnon. Or-tools. URL htt.:tss////eeooorrrs.ooog/// cow.://e.ppprrs.ooooo.o.ooo
optimi z /
David Poole and Alan K. Mackworth. Artificial Intelligence Foundations of Computational Agents. Cambridge University Press, 2010. ISBN 978-0-521-51900-7.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:/ http://axxivv.rrro
1511
06434
Raymond Reiter. theory of diagnosis from first principles. Artif. Intell., 32(1):57-95, 1987.
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?": Explaining the predictions of any classifier. In KDD, pp. 1135-1144, 2016.

---

Under review as a conference paper at ICLR 2021
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High High-precision model-agnostic explanations. In AAAI, pp. 1527-1535, 2018.
Wojciech Samek and Klaus-Robert Müller. Towards explainable artificial intelligence. In Samek al. 2019), pp. 5-22. ISBN 978-3-030-28953-9, doi:
Wojciech Samek, Grégoire Montavon, Andrea Vedaldi, Lars Kai Hansen, and Klaus-Robert Müller (eds.). Explainable AI: Interpreting, Explaining and Visualizing Deep Learning, volume 1 11700 of Lecture Notes in Computer Science. Springer, 2019. ISBN 978-3-030-28953-9 doi: 10.1007/ 978-3-030-28954-6
Peter Schmidt and Ann D. Witte. Predicting recidivism in north carolina, 1978 and 1980. Inter- University Consortium for Political and Social Research, 1988.
Andy Shih, Arthur Choi, and Adnan Darwiche. symbolic approach to explaining bayesian network classifiers. IJCAI, pp. 5103-5111, 2018.
Andy Shih, Arthur Choi, and Adnan Darwiche. Compiling bayesian network classifiers into decision graphs. In AAAI, pp. 7966-7974, 2019.
Son N. Tran and Artur S. d'' Avila Garcez. Deep logic networks: Inserting and extracting knowledge from deep belief networks. IEEE Trans. Neural Networks Learn. Syst., 29(2):246-255 2018. doi:
URL
1109//101111110111 1109 TTL.OT//TNNN... 2016
2603784
Sicco Verwer, Yingqian Zhang, and Qing Chuan Ye. Auction optimization using regression trees and linear models as integer programs. Artif. Intell., 244:368-333 395, 2017.
Feiyu Xu, Hans Uszkoreit, Yangzhou Du, Wei Fan, Dongyan Zhao, and Jun Zhu. Explainable AI: brief survey on history, research areas, approaches and challenges. In NLPCC, pp. 563-574, 2019. doi: 10. 1007/9787 01117799888-000-333 3-77783--0000322-66333
12

---

Under review as a conference paper at ICLR 2021
Appendices
A
TAXONOMY
The taxonomy of explanations used in the paper is summarized in Table 2
Table 2: Taxonomy of ML. model explanations used the paper.
Instance-
dependent
independent
agnostic
Heuristic local explanation for æ. Examples: SHAP, LIME, Anchor, etc.
Heuristic global explanation for л.
ML model-
Examples: SHAP, LIME (e.g. submodular pick)
Rigorous local explanation for Examples:
based
Rigorous global explanation for m.
'Why m?'
"Why not - contrastive (CXps)
Examples: absolute/global AXps
PI- (lbduuuct)vv))
explanations (AXps)
(our work)
B EXTRACTING & ENUMERATING EXPLANATIONS
The results of Section 3.3 enable exploiting past work on extracting and enumerating MCSes and MUSes to the setting of contrastive and abductive explanations, respectively. Perhaps surprisingly, there is a stark difference between algorithms for extraction and enumeration of contrastive explana- tions and abductive explanations. Due the association with MCSes, contrastive explanation can be computed with a logarithmic number of calls to a decision procedure Liffiton & Sakallah (2008). Moreover, there exist algorithms for the direct enumeration of contrastive explanations Liffiton & Sakallah (200).. In contrast, abductive explanations are associated with MUSes. As a result, any known algorithm for extraction of one abductive explanation requires best a linear number of calls to decision procedure Junker (2004). in the worst-case. Moreover, there is no known algorithm for the direct enumeration of abductive explanations, and so enumeration can be achieved only through the enumeration of contrastive explanations Liffiton & Sakallah (208)) Liffiton et al. (2016); Felfernig et al. (2012).
We adapt state-of of-the-art algorithms for the enumeration MUSes and MCSes to find all the abductive and contrastive explanations. Note that as in the case of cnumeration of MCSes and MUSes, the enumeration of CXps is comparatively easier than the enumeration of AXps. Algorithm I shows adaptation of MCS enumeration algorithm to the enumeration of CXpssLifiiie & Sakallah (2008). Other alternatives Grégoire et al. (2018) could be considered instead. Algorithm finds CXp. blocks it and finds the next one until no more exists. To extract a single CXp. we can use standard algorithm, e.g. [Bailey Stuckey (2005). In principle, enumeration of AXps be achieved by computing all CXps and then computing all the minimal hitting sets of all CXps, as proposed in the propositional setting Liffiton& Sakallah (2008). However, there are more efficient alternatives that we can adapt here Bailey & Stuckey| (2005); Liffiton et al.) (2016); Narodytska et al. (2018); Bendik al. (2018), AAlgorithm 2 adapts Liftton et al. (2016) the case computing both AXps and CXps. The a goriithm simultaneously searches for AXps and CXps and is based on the hitting set duality.
Algorithm 1 Enumeration of CXps
Function CXPENUM MM.C.m)
Input: M,; ML model, C: Input cube, и: Prediction
Variables: N and P. defined on the variables
I t- 0:
// Block CXps
while true do μ f- ExtractccppMM,.......
u = 0 then break;
ReportCXp(w)
I - I #Uggaatettttttrrsst
13

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Enumeration of AXps (and CXps)
Function XPENUM (MM,CC, T)
Input: Mr: ML model, C: Input cube, и: Prediction
Variables: N and P defined on the variables
== (N,
(0,0);
// Block AXps CXps
while true do
(stx, A) f FindMES(P,N))
// st
if Stx then break;
(stp, P) + SAT(A A M+)
if st then
// /entai 1ment hclds
ReportAXp(1)
N + - wueegggteetteraallogg.
else
/ Rxtractcxx(MM,,
11
Repor:CXp(p)
12
P - PUCseLtteralssOtpp
C ADDITIONAL EXPERIMENTAL RESULTS
C.I ENUMERATION OF CXPS
Setup. To perform enumeration of contrastive explanations in our first experiment, we use constraint programming solver, ORtools Perron & Furnon 15 To encode the enumeration problem with ORtools we converted scores of XGBoost models into integers keeping 5 digits precision. We enumerate contrastive explanations in the increasing order by their cardinality. This can be done by simple modification of Algorithhm I forcing it to return CXps in this order. So, we first obtain all minimum size contrastive explanations, and so on.
Second experiment. Consider our second the "3 vs digits" experiment. We use dataset that contains digits "3" (class 0) and "5" (class 1) from the standard MNIST (see (igure 3a and Figure 3g for representative samples). XGboost model has 50 trees of depth 3 with accuracy 0.98 (0.97) on train/test sets. We quantized images so that each pixel takes value between 0 and 15. As before, each pixel corresponds to feature. So, we have 784 features in our XGBoost model.
3
(a) Digit
(b) XGBoost
(c) SHAP
(d) CXp'
(e) CXp"
(I) CXp
(g) Digit 5
(h) XGBoost
(i) SHAP
( CXp'
CXp²
()) CXp
Figure 3: Results of the 3 vs 5 digits experiments. The first row shows results for the image 3. The second row shows results for the image 5. The first column shows examples of inputs; the second column shows heatmaps of XGBoost's is global important features; the third column shows heatmaps of SHAP's important features. Last three columns show heatmaps CXp of different cardinality.
Global and local explainers. We start by discussing our results on few random samples (Figure 3a and Figure 3g). First, obtain the important features from XGBoost. As these features global for the model so they are the same for all inputs FFgure 3b and Figure 3h are identical for and
The prototype and the experimental setup available at htththtt/ttthhhiie com xdua1 /xdual
14

---

Under review as a conference paper at ICLR 2021
5
6
I
3
Figure 4: Additional fake images. We reduced values of zero-valued pixels to highlight gray pixels on the edges for some fake images.
images). Figure 2bj shows that these important features. The important pixels highlight that the top parts of images are important, which is plausible high-level explanation of the classifier behavior. Digits 3 and 5 are mostly differ in the top part of the image. However, some pixels are way more important than other and it is hard to understand why.
Next, we compute an image-specific explanation using the standard explainer SHAP ( see Figure 3c for the digit 3 and Figure for the digit 5). While SHAP explanations mimic XGBoost important features, they do provide additional insights for the user. Note that both XGBoots and SHAP mark a "belt" of pixels in the upper middle part that important (bright pixels is the most important pixels).
CXps enumeration approach. We run our enumeration algorithm to produce CXps of increasing cardinality. For each image, we enumerate first 2000 CXps. Given all CXps of size k. we plot heatmap of occurrences of each pixel in these CXps of size k. Let us focus on the second row with the digit For example, CXp² (Figure 3k) shows the heatmap of CXps of size two for the digit 5. As we mentioned above, both XGBoost and SHAP hint that the 'belt' of important pixels in the middle. Again, our method can explain why this is the case. Consider the heatmap CXp' at Figure 3i This picture shows all CXps of size one for the digit 5. It reveals that most of important pixels of XGBoost and SHAP are actually CXps of size one. We reiterate that it sufficient to change single pixel value to some other value to obtain a different prediction. Now, consider the heatmap CXp at Figure 3T. This figure shows 2000 CXps (from size I to size 6). It overlaps lot with SHAP important pixels in the middle of the image. So, these pixels occur in many small size CXps and changing their values leads to misclassification.
Correlation between CXps and SHAP features. To qualitatively measure observations on correlation between key features of CXps and SHAP, we conducted the same experiment as above on 100 random images and measured the correlation between CXps and SHAP features. First, compute set T of pixels that is the union of the first (top) 100 smallest size CXps. On average, we have 38 pixels in T. Note that the average 38 pixels represent small fraction (5%) of the total number of pixels. Then we find set S of [S] SHAP pixels with highest absolute weights. Finally, we compute corr = |S n T|/(S] as the correlation measure. Note that corr 0.6 on average, i.e. our method hits 60% of best SHAP features. As the chances of two tools independently hitting the same pixel (out of 784) are quite low, the fact that 60% of [T] are picked indicates a significant correlation.
C.2 ENUMERATION OF CXPS AND AXPS
Datasets. The results obtained on the six well- and publicly available datasets. Three of them were previously studied in Ribeiro et al. (018) in the context of heuristic explanation approaches, namely, |ichor et al. (2018) and LIME Ribeiro et al. (016)) including Adult, Lending, and Recidivism. These datasets were processed the same way as in Ribeiro et al. (2018). The Adult dataset [otaae][Kohav (1996) is originally taken from the Census bureau and targets predicting whether or not given adult person earns more than $50K year depending on various attributes, e.g. education, hours of work, etc. The Lending dataset aims at predicting whether or not loan on the I Lending Club website will turn out bad. The Recidivism dataset was used to predict recidivism for individuals released from North Carolina prisons in 1978 and (980/Schmidt & Witte (1988). Two more datasets were additionally considered including Compas and German that were previously studied the context the FairML and Algorithmic Fairness projects projects|aiirML, FairML, Friedler et al. (2015); Feldman et al. 20155;; Friedler et al. (2019), area in which the need for explanations is doubtless. Compas is a popular dataset, known Angwin et al. (2016) for exhibiting racial bias of the COMPAS algorithm used for scoring criminal defendant's ' likelihood of reoffending. The latter dataset is
German credit data (e.g. see Feldman et al. (2015); Friedler et al. (2019)) which given a list of
people's attributes classifies them as good or bad credit risks. Finally, we consider the Spambase
15

---

Under review as a conference paper at ICLR 2021
dataset from the UCI repository Dua & Graff (017). The main goal is to classify an email spam non-spam based on the words that occur in this email. Due to scalability constraints, we preprocessed the dataset to keep words per email that were identified as the most influential words by random forest classifier.
Implementation and Setup. prototype implementing Algorithm targeting the enumeration of either (1) all abductive or (2) all contrastive explanations was created. In the experiment, the prototype implementation is instructed to enumerate all abductive explanations. (Note that, as was also mentioned before, matter what kind of explanations) [|llanations/Agortthhn /Algrritmm 2Jaims for, all the dual explanations are to be computed as side effect of the hitting set duality.) The prototype is able to deal with tree ensemble models trained with XGBoost Chen & Guestrin (011)). For that purpose, simple encoding of tree ensembles into satisfiability modulo theories (SMT) was developed. Concretely, the in the theory of linear arithmetic over reals (RIA formulas). (Note that encodings
target formulas of a decision tree into logic are known [Bonfettt et al. )): Lombardi et al.] (017); Verwer et al. (2017). The final score summations used in ensembles can be encoded into RIA formulas.)
Due to the twofold nature of Algorithm 2 it has to deal with (1) implicit hitting set enumeration and (2) entailment queries with SMT. The former part is implemented using the well-known MILP solver CPLEX [BM ILOG SMT solvers are accessed through the PySMT framework Gario & state-of-the-arr SMT solvers. In the experiments, we use Z3 de Moura & Bjørner (2008) as one of the best performing SMT solvers. The conducted experiment was performed in Debian Linux on an Intel Xeon E5-2630 2.60GHz processor with 64GByte of memory.
Micheli (2015), which provides a unified interface a variety
16


Reviews:
[{"review_id": "vUrQcSFhoL5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I thank the authors for their submission. I believe the investigated content is relevant and timely and would perhaps benefit from the discussion in a community such as the one of ICLR. Please find my comments below, as potential points of discussion.\n\nHigh-level comments:\n* generally, the paper does a good review of existing literature and aims to relate two important subfields (abductive vs contrastive explanations) using rules of logic, particularly using the minimal hitting set relationship \n* beyond showing that such a duality holds between abductors and contrastive explanations, I believe the experimental section should further explore comparisons with related work such as Dhurandhar et al. (as cited in earlier sections) and Rebeiro et al.\n* furthermore, the idea of using FOL for generative contrastive explanations (also sometimes called counterfactual explanations) has been explored before (e.g., [Karimi et al.]);\n* on the presentation of material, there seemed to be an underwritten requirement to be familiar and have a background in logic and verification, which makes me wonder whether ICLR is the right venue here (I also apologize for not being to provide much feedback on the technical front)\n\nMinor comments and nits:\n- the footnotes seemed to contain important details, but the number of footnotes seemed overwhelming and hurt the flow of reading\n- [footnote 9] seems incorrect; e.g., non-linearities in MLPs or RBF kernels in SVMs cannot be encoded as first-order logic\n- perhaps figure 2 can be redone to more visually demonstrate the benefit of using the proposed method; if the provided explanations aren’t visually appealing (relatively), then perhaps consider a non-image-based dataset?\n\n[Ribeiro et al.] https://homes.cs.washington.edu/~marcotcr/aaai18.pdf\n[Karimi et al.] https://arxiv.org/abs/1905.11190 ", "extra_scores": {}, "extra_text": {}}, {"review_id": "hRr9lqH0LBI", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overview\nThis paper develops, what it calls, contrastive explanations using first order logic. Contrastive explanations answer the why not question, while standard explanations (abductive in this paper's language), answer why. This paper formulates the problem as a first order logic problem and then leverages what seems like classic algorithms from that domain to learn these explanations. First, I want to point out that I have no expertise in first order logic, so this review is perhaps an educated guess as to the quality of this work. \n\nClarity/Writing\nThe writing is relatively clear and straightforward. One issue is with the citations: there is a missing bracket with the citations, which then makes them part of the sentence and ultimately distracting. \n\nQuality/Significance. \nContrastive explanations could be useful for a variety of tasks and importantly provide actionable insights about how to change a sample to satisfy positive rating. In that regard, the goal of this work is a worthy one. I cannot judge the quality of this work since I donot have any expertise in formal logic. \n\nQuestions\nWhat is the difference between the contrastive explanations as defined here and what watcher et. al. and the literature calls counterfactual explanations? \n\nI am somewhat surprised at the computational performance from the results presented here; these seem much faster than I would have expected. It seems like the task of identifying a contrastive explanation, for the discretized data set, should be NP-Hard. Is this the case? \n\nIn looking at figure 2, I can't really see the differences in attribution for CXp for the real data vs the fake one. How does the CXp help distinguish real from fake data? In the summary of results, the authors conclude that the CXps enumeration provide insight into the behavior of the classifier. However, the behavior is not discussed nor is any insight provided. What are the authors referring to? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Kg9Gdwg7F-S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to extract two types of explanations: abductive and contrastive explanations to address a gap in the literature of explainable AI. Indeed, that's a great point and often explainable models address the \"why\" and rarely the \"why not\" that can help identify the features guiding the change in the class. \nThe ideas presented are compelling and it is good to see that we can re-use state of the art AI first order logic (FOL) statements in the field of explainable models. The references are excellent. \nHowever, the paper suffers from several drawbacks: \n1- The setting is limited to ML models that are expressed as a set of FOL sentences\n2- Discretization of numerical features is required. We know static discretization can be problematic (large versus small interval); no discussion is in the paper to how to address this point\n3- More details should be presented about SHAP since this is the main method the authors compare to;\n4- Figure 1 part c) is not explained. There seems to be missing parentheses in the FOL statement;\n5- The experimental section is rather weak.  The example on the real-vs-fake digit is not clear. Pointing out the brighter pixels as those responsible of the classification is not convincing to me. Comparison to Shap (using correlation) is not discussed.\nThe second experiment. provides some statistics on the time, number of abductive and contrastive explanations. Perhaps it would have been good to provide other examples of the importance of extracting both explanations and how pertinent they are. Overall, there is a need for some baseline to validate the explanations (both types); \n6- The methodology should be made clearer, notations introduced or re-introduced, many readers might not be familar with some notations like entailments; \n\nOverall, I feel there are good ideas in there, the authors should consider enlarging the spectrum of the applicability of their approach, may be rework the definitions and methodology section and design more solid experiments. \n\nMinor comments:\nseeFigure\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1ZW-z_u0fpm", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n-------------\nThis work presents first of a kind logic-based framework that relates contrastive (minimally absent) and abductive (minimally present) explanations and shows that abductive explanations are essentially minimal hitting sets of contrastive explanations. \n\n+ve:\n-----\nA much needed formal framework and proofs that relate the different types of explanations. With many different types of explanations proposed in the XAI literature, this line of work improves are understanding of the overall space & taxonomy of explanations. Also the relationship between types of explanations may helps us enumerate/compute other types of explanations based on the computation of one type. \n\nSuggestions:\n-------------------\nIt would be good to comment a bit on the overall steps needed to convert any ML problem into the proposed framework - costs of binarizing feature values, etc. before applying the proposed ideas for local or global explanations. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider local 'why' or 'abductive' explanations for a model and a given class, which identify a minimal subset of features such that they're sufficient to imply that the model predicts the class; and 'why not' or 'contrastive' explanations, which identify a minimal subset s.t. they're sufficient to imply that the model predicts a different class. The two types of explanation are related using earlier work on minimal hitting sets going back to Reiter (1987). 

Reviewers were divided in their opinions. R4 was very positive but with little detail and only medium confidence, then did not participate in discussion. R2 was the only reviewer with high confidence, leaning against acceptance. The paper relies on FOL which was hard for reviewers to grapple with, and may make it challenging for readers. The presentation could be improved by clearly linking to existing work and demonstrating why the new approach is important.
Decision: Reject