# Disproving XAI Myths with Formal Methods –
Initial Results ††thanks:  This work was supported by the AI Interdisciplinary
Institute ANITI, funded by the French program “Investing for the Future –
PIA3” under Grant agreement no. ANR-19-PI3A-0004, and by the H2020-ICT38
project COALA “Cognitive Assisted agile manufacturing for a Labor force
supported by trustworthy Artificial intelligence”.

Joao Marques-Silva  IRIT, CNRS
Toulouse, France
<EMAIL_ADDRESS>
###### Abstract

The advances in Machine Learning (ML) in recent years have been both
impressive and far-reaching. However, the deployment of ML models is still
impaired by a lack of trust in how the best-performing ML models make
predictions. The issue of lack of trust is even more acute in the uses of ML
models in high-risk or safety-critical domains. eXplainable artificial
intelligence (XAI) is at the core of ongoing efforts for delivering
trustworthy AI. Unfortunately, XAI is riddled with critical misconceptions,
that foster distrust instead of building trust. This paper details some of the
most visible misconceptions in XAI, and shows how formal methods have been
used, both to disprove those misconceptions, but also to devise practically
effective alternatives.

###### Index Terms:

Explainable AI, Formal Methods, Automated Reasoners

##  I Introduction

The advances in Machine Learning (ML) in recent years have been absolutely
remarkable [50, 11], and are posed to impact many aspects of society. However,
the most promising ML models exhibit important shortcomings. First, ML models
can be brittle, in that small changes to the inputs can cause unexpected
changes on the output [85]. The assessment of _robustness_ of ML models aims
to confirm that ML models are not brittle, and has been an active area of
research in recent years. Second, ML models can exhibit bias, and well-known
examples exist of biased decision making [69, 86]. Fairness of ML models is
another active area of research [61, 68, 10], with the use of formal methods
also proposed [38]. Third, ML models are inscrutable in their operation, and
as a result are often referred to as black-box ML models. Both shortcomings of
ML models motivate distrust by human decision makers, and so represent
critical limitations to the widespread deployment of ML models in many
practical applications, especially among those that are deemed high-risk or
safety-critical. In recent years, there have been calls for the verification
of AI [79], aiming to target both the lack of robustness of ML models and
their inscrutability.

eXplainable Artificial Intelligence (XAI) [28, 29, 30], addresses the
shortcoming of inscrutability, in that it broadly aims to help human decision
makers in understanding the operation of ML models. The perceived importance
of XAI motivated a large body of research, covering a wide range of topics,
with the overarching goal of helping to build trust in the use of ML models.
However, most work on XAI is not supported by formal guarantees of rigor. We
will refer to such XAI efforts as _non-formal XAI_. The most visible exception
to this state of affairs is formal XAI, which builds on rigorously defined
notions of explainability, and the use of automated reasoning for computing
explanations. Formal XAI is not without limitations, with the best-known being
scalability with respect to complex ML models.

This paper makes a case for the importance of formal XAI, but showing how
formal reasoning about explanations has served to refute three of the most
established myths of non-formal XAI.

#### Myth #01 – intrinsic interpretability.

Some ML models are widely accepted to be interpretable [65], even if there is
no rigorous definition of what _interpretable_ means [51]. Concrete examples
of so-called interpretable models include decision trees, lists and sets. The
_interpretability_ of these ML models has motivated recent works to advocate
for their use in high-risk applications [73, 75].

In recent work [45, 34, 46, 60], we demonstrated that these so-called
interpretable models will not provide interpretable explanations as long as
these relate with explanation succinctness. Section IV overviews the main
results reported in recent work, which disprove existing claims about
interpretability of some ML models.

#### Myth #02 – model-agnostic explanations.

The most popular approaches for explaining ML models using _feature selection_
(i.e. sets of features) are referred to as _model-agnostic_. Essentially, a
model-agnostic explainability approach ignores the ML model, and proposes an
explanation given the training data, and an estimated distribution of the
input. One of the best-known approaches for model-agnostic explainability
reports explanations as sets of features which explain the prediction. Anchors
is arguable one of the best known model-agnostic explainers [72].

In recent work [44, 37, 89], we demonstrated that the sets of features
reported by model-agnostic approaches are in the vast majority of cases _not_
sufficient for the prediction, and so can mislead human decision makers by
overlooking critical features. Section V overviews the main results reported
in recent work, which disprove the ability of model-agnostic methods for
computing sufficient reasons for explanations.

#### Myth #03 – explainability with Shapley values.

The best-known alternative to feature selection is _feature attribution_ ,
where each feature receives a score of its relative importance for a
prediction. Methods of feature attribution rank among the best-known and more
widely used explainability approaches [8, 71, 54, 77]. Among these, SHAP [54]
builds on the use of Shapley values [80]. The success of Shapley values for
explainability is illustrated by a number of works. Furthermore, Shapley
values for explainability provide a theoretical justification for SHAP-like
feature attribution methods.

In recent work [36], we demonstrated that Shapley values for explainability,
as proposed by a number of authors [83, 84, 54, 53], will provide misleading
information about feature importance. To derive this result, we characterized
features in terms of being relevant or irrelevant for rigorous explanations
based on feature selection. We then showed that irrelevant features for
explanations based on feature selection, i.e. features that do not occur in
_any_ (irreducible) explanation based on selection of features, will exhibit
an absolute Shapley value larger than relevant features for explanations based
on feature selection. Section VI overviews the main results reported in recent
work, which disprove the adequacy of Shapley values for explainability.

#### Organization.

The paper is organized as follows. Section II introduces the notation and
definitions used throughout. Section III provides a brief account of XAI,
emphasizing formal explainability, which we will then use in later sections.
Then, Sections IV, V and VI will disprove the myths of XAI listed above.
Section VII briefly discusses the significance of disproving those myths of
XAI. The paper concludes in Section VIII.

##  II Preliminaries

#### Classification in ML.

A classification problem is defined on a set of features
${\mathcal{F}}=\\{1,\ldots,m\\}$, each with domain $\mathbb{D}_{i}$, and a set
of classes ${\mathcal{K}}=\\{c_{1},c_{2},\ldots,c_{K}\\}$. Domains can be
categorical or ordinal, in this case with values that can be integer- or real-
valued. Feature space $\mathbb{F}$ is defined as the Cartesian product of the
domains of the features, in order:
$\mathbb{F}=\mathbb{D}_{1}\times\cdots\times\mathbb{D}_{m}$. We will use
$\mathbf{x}=(x_{1},\ldots,x_{m})$ to denote an arbitrary point in feature
space, i.e. each $x_{i}$ is a variable taking values from $\mathbb{D}_{i}$. In
contrast, we will use $\mathbf{v}=(v_{1},\ldots,v_{m})$ to denote a specific
point in feature space, i.e. each $v_{i}$ is a constant taken from
$\mathbb{D}_{i}$. A classification function is a non-constant map from feature
space into the set of classes, $\kappa:\mathbb{F}\to{\mathcal{K}}$. (Clearly,
a classifier would be useless if the classification function were constant.) A
boolean classifier is one where the feature domains are boolean, i.e.
$\mathbb{D}_{i}=\mathbb{B}=\\{0,1\\}$, for $i\in{\mathcal{F}}$, and the set of
classes is also boolean, i.e. ${\mathcal{K}}=\mathbb{B}$. An instance is a
pair $(\mathbf{v},c)$ representing a point $\mathbf{v}$ in feature space, and
the prediction by the classifier, i.e. $\kappa(\mathbf{v})=c$. Finally, a
classifier ${\mathcal{M}}$ is a tuple
$({\mathcal{F}},\mathbb{F},{\mathcal{K}},\kappa)$. In addition, an explanation
problem ${\mathcal{E}}$ is a tuple $({\mathcal{M}},(\mathbf{v},c))$, where
${\mathcal{M}}=({\mathcal{F}},\mathbb{F},{\mathcal{K}},\kappa)$ is a
classifier. Thus, in this paper, and given an explanation problem, our
objective is to define explanations and investigate approaches for computing
such explanations.

#### Sample of ML models.

In this paper we study so-called interpretable models, concretely decision
trees and decision sets, but also classifiers represented by truth tables. All
these representations of classification functions are well-known, and the
concrete notation used is clarified with the running examples presented in the
rest of this section.

#### Running examples.

Throughout the paper, we will use a few simple running examples. For the first
parts of the paper, we will consider both a decision tree (DT) and a decision
list (DL). These rank among the simplest ML models, and that simplicity often
motivates claims of interpretability.

We consider the DT shown in Figure 1, adapted from[31], and studied for
explainability in [46, 60]. The nodes are numbered 1 to 15. The internal nodes
test the value of a (single) feature, and the terminal nodes show the
predicted class. Each edge defines a literal on the feature associated with
the edge’s starting node. Paths are sequences of nodes, starting at the root,
and terminating at a terminal node. Path $\langle 1,2,4,6\rangle$ is an
example of a path. The literals associated with this path are: $x_{1}=0$,
$x_{2}=0$ and $x_{3}=0$. Given an instance $(\mathbf{v},c)=((0,0,0,0,0),0)$,
the path consistent with $\mathbf{v}=(v_{1},v_{2},v_{3},v_{4},v_{5})$ is
$\langle 1,2,4,6\rangle$, where each $v_{i}$ is assigned to feature $i$.
Similarly, for the instance $((0,1,1,0,0),1)$ is consistent with path $\langle
1,2,5,8,12\rangle$.

BDT/.style= for tree= l=1.5cm,s sep=1.15cm, if n children=0circle,
draw=black,text=black,edge= my edge , if n=1 edge+=0 my edge, , edge=thick, ,
BDT [$x_{1}$, label=[yshift=-6.875ex]1 [$x_{2}$, label=[yshift=-6.875ex]2,
edge label=node[midway,left,xshift=-0.5pt] $=0$ [$x_{3}$,
label=[yshift=-6.875ex]4, edge label=node[midway,left,xshift=-2.5pt] $=0$ [0,
label=[yshift=-5.0ex]6, edge label=node[midway,left,xshift=-0.5pt] $=0$,
rectangle, fill=tred3!20 ] [$x_{4}$, label=[yshift=-6.875ex]7, edge
label=node[midway,right,xshift=0.5pt] $=1$ [$x_{5}$,
label=[yshift=-6.875ex]10, edge label=node[midway,left,xshift=-1.5pt] $=0$ [0,
label=[yshift=-5.0ex]14, edge label=node[midway,left,xshift=-1.5pt] $=0$,
rectangle, fill=tred3!20 ] [1, label=[yshift=-5.0ex]15, edge
label=node[midway,right,xshift=0.5pt] $=1$, rectangle, fill=tgreen3!25 ] ] [1,
label=[yshift=-5.0ex]11, edge label=node[midway,right,xshift=0.5pt] $=1$,
rectangle, fill=tgreen3!25 ] ] ] [$x_{4}$, label=[yshift=-6.875ex]5, edge
label=node[midway,right,xshift=1.5pt] $=1$ [$x_{5}$, label=[yshift=-6.875ex]8,
edge label=node[midway,left,xshift=-0.5pt] $=0$ [0, label=[yshift=-5.0ex]12,
edge label=node[midway,left,xshift=-0.5pt] $=0$, rectangle, fill=tred3!20 ]
[1, label=[yshift=-5.0ex]13, edge label=node[midway,right,xshift=0.5pt] $=1$,
rectangle, fill=tgreen3!25 ] ] [1, label=[yshift=-5.0ex]9, edge
label=node[midway,right,xshift=0.5pt] $=1$, rectangle, fill=tgreen3!25 ] ] ]
[1, label=[yshift=-5.0ex]3, edge label=node[midway,right,xshift=0.5pt] $=1$,
rectangle, fill=tgreen3!25 ] ]

Figure 1: Example decision tree (adapted from [31])

As described elsewhere [31], the DT was generated with an algorithm for
learning optimal DTs. Hence, the DT does not exhibit any redundancy in terms a
cost function defined on an aggregated set of criteria, namely the loss (or
misclassification error) and tree size.

Moreover, we also consider the DL shown in Figure 2.

$\begin{array}[]{lclclc}\textnormal{R}_{1}:&&\textnormal{IF}&({x_{1}}\land{x_{3}})&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{R}_{2}:&&\textnormal{ELSE
IF}&(x_{2}\land{x_{4}}\land{x_{6}})&\textnormal{THEN}&\kappa(\mathbf{x})=0\\\
\textnormal{R}_{3}:&&\textnormal{ELSE
IF}&(\neg{x_{1}}\land{x_{3}})&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{R}_{4}:&&\textnormal{ELSE
IF}&(x_{4}\land{x_{6}})&\textnormal{THEN}&\kappa(\mathbf{x})=0\\\
\textnormal{R}_{5}:&&\textnormal{ELSE
IF}&(\neg{x_{1}}\land\neg{x_{3}})&\textnormal{THEN}&\kappa(\mathbf{x})=1\\\
\textnormal{R}_{6}:&&\textnormal{ELSE
IF}&(x_{6})&\textnormal{THEN}&\kappa(\mathbf{x})=0\\\
\textnormal{R}_{\textnormal{DEF}}:&&\textnormal{ELSE}&&&\kappa(\mathbf{x})=1\\\
\end{array}$
Figure 2: Example of decision list (adapted from [60])

If the condition of some rule $\textnormal{R}_{i}$ is true, and the conditions
of previous rules are false, then the prediction is the one of rule
$\textnormal{R}_{i}$, and we say that that rule fires. As an example, for the
point in feature space $(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})=(1,1,1,1,1,1)$,
rule $\textnormal{R}_{1}$ fires since $x_{1}=x_{3}=1$.

We will also consider two boolean classifiers represented by their truth
tables, as shown in Figure 3. The instances that will be analyzed in more
detail are highlighted, and correspond to $((0,0,1,1),0)$ for Figure 3(a), and
$((1,1,1,1),0)$ for Figure 3(b).

$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $\kappa_{I4}(\mathbf{x})$
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 1 | 0
0 | 0 | 1 | 0 | 0
0 | 0 | 1 | 1 | 0
0 | 1 | 0 | 0 | 0
0 | 1 | 0 | 1 | 0
0 | 1 | 1 | 0 | 0
0 | 1 | 1 | 1 | 1
1 | 0 | 0 | 0 | 0
1 | 0 | 0 | 1 | 0
1 | 0 | 1 | 0 | 1
1 | 0 | 1 | 1 | 0
1 | 1 | 0 | 0 | 1
1 | 1 | 0 | 1 | 1
1 | 1 | 1 | 0 | 1
1 | 1 | 1 | 1 | 1

(a) Function $\kappa_{I4}$

$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $\kappa_{I5}(\mathbf{x})$
---|---|---|---|---
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 1 | 0
0 | 0 | 1 | 0 | 0
0 | 0 | 1 | 1 | 0
0 | 1 | 0 | 0 | 0
0 | 1 | 0 | 1 | 0
0 | 1 | 1 | 0 | 0
0 | 1 | 1 | 1 | 1
1 | 0 | 0 | 0 | 0
1 | 0 | 0 | 1 | 0
1 | 0 | 1 | 0 | 0
1 | 0 | 1 | 1 | 1
1 | 1 | 0 | 0 | 0
1 | 1 | 0 | 1 | 1
1 | 1 | 1 | 0 | 0
1 | 1 | 1 | 1 | 0

(b) Function $\kappa_{I5}$

Figure 3: Examples of boolean classifiers

##  III A Glimpse of Explainable AI

###  III-A Intrinsic Interpretability

Intrinsic interpretability [65] builds on a long-held belief that some ML
models are naturally interpretable. (This belief has been stated for example
for decision trees [14], but also for decision sets [49], among others.)
Indeed, it is the case that, for some ML models, an explanation can be
produced by some sort of manual inspection of the model. This is the case with
decision trees, decision lists, decision sets, but other graph-based ML models
[34].

Recent years have witnessed proposals for the use of interpretable models in
high-risk applications [73, 74]. Unfortunately, it is unclear that a rigorous
definition of interpretability can be devised [51]. Given the motivation for
work on interpretable models, we equate interpretability with succinctness and
irreducibility of explanations.

###  III-B Feature-Based Explanations

Most practical work on explainability relates explanations with the model’s
features. Two main lines of work exist: _feature attribution_ and _feature
selection_.

Feature attribution (e.g. [8, 71, 54]) assigns some value of importance to
each of the model’s features. Relative feature importance is then obtained by
comparing the value of importance of the different features. Among others,
Shapley values have found widespread acceptance as a mechanism for feature
attribution in explainability.

Feature selection (e.g. [71, 81, 42]) identifies sets of features that are
sufficient (probabilistically or deterministically) for the prediction. The
most visible feature selection methods are heuristic, but there has been
recent work on formal approaches for feature selection in explainability; this
is discussed in Section III-E.

###  III-C Non-Formal Explainability

The vast majority of work on explainability has been based on what we refer to
as _non-formal explainability_ , i.e. approaches that offer no guarantees of
rigor in computed explanations. There are fairly up to date overviews of non-
formal explainability approaches [66, 27, 77, 78, 65, 76].

One well-known line of work are model-agnostic methods [71, 54, 72]. Model-
agnostic methods approach explainability by ignoring the actual implementation
of the ML model, and either sample the behavior from training data, or sample
the black-box behavior of the model using an inferred distribution from
training data. As an example, SHAP [54] approaches feature attribution by
proposing to approximate the computation of Shapley values for explainability.

###  III-D Shapley Values for Explainability

Shapley values were first introduced by L. Shapley [80] in the context of game
theory. Shapley values have been extensively used for explaining the
predictions of ML models, e.g. [83, 84, 21, 54, 15, 62, 82, 88], among a vast
number of recent examples. The complexity of computing Shapley values (as
proposed in SHAP [54]) has been studied in recent years [4, 22, 3, 23, 18].
This section provides a brief overview of Shapley values. Throughout the
section, we adapt the notation used in recent work [4, 3], which builds on the
work of [54].

Let $\Upsilon:2^{{\mathcal{F}}}\to 2^{\mathbb{F}}$ be defined by,

$\Upsilon({\mathcal{S}};\mathbf{v})=\\{\mathbf{x}\in\mathbb{F}\,|\,\land_{i\in{\mathcal{S}}}x_{i}=v_{i}\\}$
(1)

i.e. for a given set ${\mathcal{S}}$ of features, and parameterized by the
point $\mathbf{v}$ in feature space, $\Upsilon({\mathcal{S}};\mathbf{v})$
denotes all the points in feature space that have in common with $\mathbf{v}$
the values of the features specified by ${\mathcal{S}}$.

Also, let $\phi:2^{{\mathcal{F}}}\to\mathbb{R}$ be defined by,

$\phi({\mathcal{S}};{\mathcal{M}},\mathbf{v})=\frac{1}{2^{|{\mathcal{F}}\setminus{\mathcal{S}}|}}\sum_{\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})}\kappa(\mathbf{x})$
(2)

For the purposes of this paper, and in contrast with [4, 3], one can solely
consider a uniform input distribution, and so the dependency with the input
distribution is not accounted for. As a result, given a set ${\mathcal{S}}$ of
features, $\phi({\mathcal{S}};{\mathcal{M}},\mathbf{v})$ represents the
average value of the classifier over the points of feature space represented
by $\Upsilon({\mathcal{S}};\mathbf{v})$.

Finally, let $\mathsf{Sv}:{\mathcal{F}}\to\mathbb{R}$ be defined by,

$\displaystyle\mathsf{Sv}(i;{\mathcal{M}},\mathbf{v})=$
$\displaystyle\sum_{{\mathcal{S}}\subseteq({\mathcal{F}}\setminus\\{i\\})}\frac{|{\mathcal{S}}|!(|{\mathcal{F}}|-|{\mathcal{S}}|-1)!}{|{\mathcal{F}}|!}\times$
$\displaystyle\left(\phi({\mathcal{S}}\cup\\{i\\};{\mathcal{M}},\mathbf{v})-\phi({\mathcal{S}};{\mathcal{M}},\mathbf{v})\right)$
(3)

Given an instance $(\mathbf{v},c)$, the Shapley values assigned to each
feature measure the _contribution_ of the features with respect to the
prediction. A positive/negative value indicates that the feature can
contribute to changing the prediction, whereas a value of 0 indicates no
contribution. Moreover, and as our results demonstrate, SHAP never really
replicates exact Shapley values. As a result, we focus on the relative order
of features imposed by the computed Shapley values. The motivation is that,
even if the computed values are not correct (as in the case of SHAP), then
what matters for a human decision maker is the order of features.

######  Example 1.

We consider the example boolean functions of Figure 3. If the functions are
represented by a truth table, then the Shapley values can be computed in
polynomial time on the size of the truth table, since the number of subsets
considered in (III-D) is also polynomial on the size of the truth table [36].
(Observe that for each subset used in (III-D), we can use the truth table for
computing the average values in (2).) For example, for $\kappa_{I4}$ (see
Figure 3(a)) and for the point in feature space $(0,0,1,1)$, one can compute
the following Shapley values: $\mathsf{Sv}(1)=-0.125$,
$\mathsf{Sv}(2)=-0.333$, $\mathsf{Sv}(3)=0.083$, and $\mathsf{Sv}(4)=0.0$.

###  III-E Formal Explainability

This section offers a brief perspective of the emerging field of formal
explainable AI. Recent detailed accounts are available [59, 56].

#### Abductive explanations (AXp’s).

An AXp [42]111AXp’s are also referred to as prime implicant (PI) explanations
[81] and as sufficient reasons for a prediction. represents a subset-minimal
set of literals (relating a feature value $x_{i}$ and a constant
$v_{i}\in\mathbb{D}_{i}$) that are logically sufficient for the prediction.
AXp’s can be viewed as answering a Why? question, i.e. why the prediction.
(AXp’s can be described in terms of logic-based abduction, which explains the
name used [59].) AXp’s offer guarantees of rigor that are not offered by other
alternative explanation approaches. More recently, AXp’s have been studied in
terms of their computational complexity [9, 6, 7, 19]. There is a growing body
of recent work on formal explanations [20, 2, 87, 55, 13, 12, 26, 59, 1, 24,
5, 52]. Formally, given $\mathbf{v}=(v_{1},\ldots,v_{m})\in\mathbb{F}$, with
$\kappa(\mathbf{v})=c$, an AXp is any subset-minimal set
${\mathcal{X}}\subseteq{\mathcal{F}}$ such that222In the remainder of this
section, the parameterization of the presented predicates on the classifier
${\mathcal{M}}$ and on $(\mathbf{v},c)$ is omitted for the sake of brevity.,

$\displaystyle\mathsf{WAXp}($ $\displaystyle{\mathcal{X}}){~{}:=~{}}$
$\displaystyle\forall(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{i\in{{\mathcal{X}}}}(x_{i}=v_{i})\right]\operatorname*{\rightarrow}(\kappa(\mathbf{x})=c)$
(4)

If a set ${\mathcal{X}}\subseteq{\mathcal{F}}$ is not minimal but (III-E)
holds, then ${\mathcal{X}}$ is referred to as a _weak_ AXp. Clearly, the
predicate $\mathsf{WAXp}$ maps $2^{{\mathcal{F}}}$ into $\\{\bot,\top\\}$ (or
$\\{\textbf{false},\textbf{true}\\}$). Given $\mathbf{v}\in\mathbb{F}$, an AXp
${\mathcal{X}}$ represents an irreducible (or minimal) subset of the features
which, if assigned the values dictated by $\mathbf{v}$, are sufficient for the
prediction $c$, i.e. value changes to the features not in ${\mathcal{X}}$ will
not change the prediction. We can use the definition of the predicate
$\mathsf{WAXp}$ to formalize the definition of the predicate $\mathsf{AXp}$,
also defined on subsets ${\mathcal{X}}$ of ${\mathcal{F}}$:

$\displaystyle\mathsf{AXp}($ $\displaystyle{\mathcal{X}}){~{}:=~{}}$
$\displaystyle\mathsf{WAXp}({\mathcal{X}})\land\forall({\mathcal{X}}^{\prime}\subsetneq{\mathcal{X}}).\neg\mathsf{WAXp}({\mathcal{X}}^{\prime})$
(5)

The definition of $\mathsf{WAXp}({\mathcal{X}})$ ensures that the predicate is
_monotone_. Indeed, if
${\mathcal{X}}\subseteq{\mathcal{X}}^{\prime}\subseteq{\mathcal{F}}$, and if
${\mathcal{X}}$ is a weak AXp, then ${\mathcal{X}}^{\prime}$ is also a weak
AXp, as the fixing of more features will not change the prediction. Since the
$\mathsf{WAXp}$ predicate is monotonic, the definition of the predicate
$\mathsf{AXp}$ can be simplified as follows, with
${\mathcal{X}}\subseteq{\mathcal{F}}$:

$\displaystyle\mathsf{AXp}($ $\displaystyle{\mathcal{X}}){~{}:=~{}}$
$\displaystyle\mathsf{WAXp}({\mathcal{X}})\land\forall(j\in{\mathcal{X}}).\neg\mathsf{WAXp}({\mathcal{X}}\setminus\\{j\\})$
(6)

This simpler but equivalent definition of AXp has important practical
significance, in that only a linear number of subsets needs to be checked for,
as opposed to exponentially many subsets in (III-E). As a result, the
algorithms that compute one AXp are based on (III-E) [59].

######  Example 2.

For the boolean function $\kappa_{I4}$ in Figure 3(a), and the instance
$((0,0,1,1),0)$, we can observe that the value of the function is 0 for the
first four rows of the truth table. Thus, if both $x_{1}$ and $x_{2}$ equal 1,
then the prediction is guaranteed to be 0. Hence, $\\{1,2\\}$ is a weak AXp.
By inspection of the remaining rows, where either $x_{1}$ or $x_{2}$ changes,
we can conclude that $\\{1,2\\}$ is indeed an AXp.

#### Contrastive explanations (CXp’s).

A CXp is a subset-minimal set of features which suffices to change the
prediction.

Similarly to the case of AXp’s, one can define (weak) contrastive explanations
(CXp’s) [64, 41]. ${\mathcal{Y}}\subseteq{\mathcal{F}}$ is a weak CXp for the
instance $(\mathbf{v},c)$ if,

$\displaystyle\mathsf{WCXp}($ $\displaystyle{\mathcal{Y}})~{}{:=}~{}$
$\displaystyle\exists(\mathbf{x}\in\mathbb{F}).\left[\bigwedge_{i\not\in{\mathcal{Y}}}(x_{i}=v_{i})\right]\land(\kappa(\mathbf{x})\not=c)$
(7)

Thus, given an instance $(\mathbf{v},c)$, a (weak) CXp is a subset of features
which, if allowed to take any value from their domain, then there is an
assignment to the features that changes the prediction to a class other than
$c$, this while the features not in the explanation are kept to their values.

Furthermore, a set ${\mathcal{Y}}\subseteq{\mathcal{F}}$ is a CXp if, besides
being a weak CXp, it is also subset-minimal, i.e.

$\displaystyle\mathsf{CXp}($ $\displaystyle{\mathcal{Y}})~{}{:=}~{}$
$\displaystyle\mathsf{WCXp}({\mathcal{Y}})\land\forall({\mathcal{Y}}^{\prime}\subsetneq{\mathcal{Y}}).\neg\mathsf{WCXp}({\mathcal{Y}}^{\prime})$
(8)

A CXp can be viewed as a possible irreducible answer to a Why Not? question,
i.e. why isn’t the classifier’s prediction a class other than $c$?

As before, monotonicity of predicate $\mathsf{WCXp}$ allows simplifying
Section III-E to get,

$\displaystyle\mathsf{CXp}($ $\displaystyle{\mathcal{Y}}){~{}:=~{}}$
$\displaystyle\mathsf{WCXp}({\mathcal{Y}})\land\forall(j\in{\mathcal{Y}}).\neg\mathsf{WCXp}({\mathcal{Y}}\setminus\\{j\\})$
(9)

######  Example 3.

For the example function $\kappa_{I4}$, and instance $((0,0,1,1),0)$, if we
fix features 1, 3 and 4, respectively to 0, 1 1, then by allowing feature 2 to
change value, we see that the prediction changes, e.g. by considering the
point $(0,1,1,1)$ with prediction 1. Thus, $\\{2\\}$ is a CXp. In a similar
way, by fixing the features 2 and 3, respectively to 0 and 1, then by allowing
features 1 and 4 to change value, we conclude that the prediction changes.
Hence, $\\{1,4\\}$ is also a CXp.

#### Duality between explanations.

Given an explanation problem ${\mathcal{E}}$, the sets of AXp’s and CXp’s are
defined as follows:

$\begin{array}[]{l}\mathbb{A}({\mathcal{E}})=\\{{\mathcal{X}}\subseteq{\mathcal{F}}\,|\,\mathsf{AXp}({\mathcal{X}})\\}\\\\[3.0pt]
\mathbb{C}({\mathcal{E}})=\\{{\mathcal{Y}}\subseteq{\mathcal{F}}\,|\,\mathsf{CXp}({\mathcal{Y}})\\}\end{array}$
(10)

By taking into account the definition of AXp, CXp, and their sets (see (10)),
and also by building on Reiter’s seminal work [70], recent work [41] proved
the following duality between minimal hitting sets (MHSes)333Given a set
${\mathcal{S}}$ of sets, an MHS is a subset-minimal set of elements such that
the intersection with each of the sets of ${\mathcal{S}}$ is non-empty.:

######  Proposition 1 (Minimal hitting-set (MHS) duality between AXp’s and
CXp’s).

Given an explanation problem ${\mathcal{E}}$, we have that,

  1. 1.

${\mathcal{X}}\subseteq{\mathcal{F}}$ is an AXp (and so
${\mathcal{X}}\in\mathbb{A}({\mathcal{E}})$) iff ${\mathcal{X}}$ is an MHS of
the CXp’s in $\mathbb{C}({\mathcal{E}})$.

  2. 2.

${\mathcal{Y}}\subseteq{\mathcal{F}}$ is a CXp (and so
${\mathcal{Y}}\in\mathbb{C}({\mathcal{E}})$) iff ${\mathcal{Y}}$ is an MHS of
the AXp’s in $\mathbb{A}({\mathcal{E}})$.

We refer to Proposition 1 as MHS duality between AXp’s and CXp’s. The previous
result has been used in more recent papers for enabling the enumeration of
explanations [58, 40, 34].

######  Example 4.

For the function in Figure 3(b), and instance $((1,1,1,1),0)$, there is only
one AXp: $\mathbb{A}({\mathcal{E}})=\\{\\{1,2,3\\}\\}$, i.e. $\\{1,2,3\\}$ is
the only subset-minimal set of features which, if fixed to the values dictated
by $\mathbf{v}$, is sufficient for predicting 0. Moreover, the set of CXp’s
is: $\mathbb{C}({\mathcal{E}})=\\{\\{1\\},\\{2\\},\\{3\\}\\}$. Clearly, each
CXp is an MHS of the set AXp’s and the AXp is an MHS of the set of CXp’s.

Let us defined the sets
$F_{\mathbb{A}}({\mathcal{E}})=\cup_{{\mathcal{X}}\in\mathbb{A}({\mathcal{E}})}{\mathcal{X}}$
and
$F_{\mathbb{C}}({\mathcal{E}})=\cup_{{\mathcal{Y}}\in\mathbb{C}({\mathcal{E}})}{\mathcal{Y}}$.
$F_{\mathbb{A}}({\mathcal{E}})$ aggregates the features occurring in any
abductive explanation, whereas $F_{\mathbb{C}}({\mathcal{E}})$ aggregates the
features occurring in any contrastive explanation. Given the above, the
following results are a consequence of Proposition 1:

######  Proposition 2.

${F}_{\mathbb{A}}({\mathcal{E}})={F}_{\mathbb{C}}({\mathcal{E}})$.

######  Corollary 1.

Given a classifier function $\kappa:\mathbb{F}\to{\mathcal{K}}$, defined on a
set of features ${\mathcal{F}}$, a feature $i\in{\mathcal{F}}$ is included in
some AXp iff $i$ is included in some CXp.

Additional duality results in (formal) explainability have been established
elsewhere [43].

#### Explanability queries – feature relevancy [34, 35, 32].

Let us consider a classifier ${\mathcal{M}}$, with features ${\mathcal{F}}$,
domains $\mathbb{D}_{i}$, $i\in{\mathcal{F}}$, classes ${\mathcal{K}}$, a
classification function $\kappa:\mathbb{F}\to{\mathcal{K}}$, and a concrete
instance $(\mathbf{v},c)$, $\mathbf{v}\in\mathbb{F},c\in{\mathcal{K}}$.

######  Definition 1 (Feature Necessity, Relevancy & Irrelevancy).

Let $\mathbb{A}$ denote the set of all AXp’s for a classifier given a concrete
instance, i.e.
$\mathbb{A}=\\{{\mathcal{X}}\subseteq{\mathcal{F}}\,|\,\mathsf{AXp}({\mathcal{X}})\\}$,
and let $t\in{\mathcal{F}}$ be a target feature. Then,

  1. i.

$t$ is necessary if $t\in\cap_{{\mathcal{X}}\in\mathbb{A}}{\mathcal{X}}$;

  2. ii.

$t$ is relevant if $t\in\cup_{{\mathcal{X}}\in\mathbb{A}}{\mathcal{X}}$; and

  3. iii.

$t$ is irrelevant if
$t\in{\mathcal{F}}\setminus\cup_{{\mathcal{X}}\in\mathbb{A}}{\mathcal{X}}$.

Because of feature occurs in some AXp iff it occurs in some CXp, then the
previous definitions could consider instead the set of contrastive
explanations.

######  Example 5.

For the example function Figure 3(b), let us consider the instance
$((1,1,1,1),0)$. By inspection, we conclude that the only AXp is
$\\{1,2,3\\}$. Hence, features $1,2,3$ are relevant, and feature $4$ is
irrelevant.,

In the rest of the paper, we will use the predicate
$\textnormal{\small{{Relevant}}}(i)$ to hold true when feature $i$ is
relevant, and the predicate $\textnormal{\small{{Irrelevant}}}(i)$ to hold
true when feature $i$ is irrelevant.

#### Progress in formal XAI.

Figure 4 summarizes the progress observed in recent years for computing one
explanation [59, 56].

NBCs [57]DTs [45, 47]XpGs [34]GDFs [34]Monotonic [58, 17]d-DNNF [33]DLs
[40]RFs [48]BTs [37, 39]NNs [42]BNs [81]Practical scalability
(effectiveness)EffectiveIneffectiveComputational complexityComputationally
hardPoly-timeComputing one XP Figure 4: Progress in formal XAI [59, 56]

For several families of classifiers there exist practical efficient solutions,
either in theory or in practice. These include Naive Bayes Classifiers [57],
Decision Trees [45, 46], restricted boolean circuits (e.g. d-DNNFs, GDFs,
BDDs) [34, 33] and monotonic classifiers [58, 17], but also decision lists
[40], random forests and boosted trees [37, 48, 39]. For some families of
classifiers, e.g. Neural Networks and Bayesian Network Classifiers,
scalability is still an issue [81, 42].

Recent overviews of formal XAI cover additional detail [59, 56], including
recent work on different explainability queries. Furthermore, and with the
purpose of disproving one of the myths in XAI, recent work [36] demonstrated
that for classifiers represented with truth tables, there exist polynomial-
time algorithm for computing one or more explanations (both abductive and
contrastive), but also for answering feature relevancy queries.

##  IV Myth #01: Intrinsic Interpretability

One approach to XAI is _intrinsic interpretability_ [65], based on a long-held
belief that some ML models are _interpretable_. Concrete examples include
decision trees, lists and sets. In the case of decision trees, their
interpretability has been asserted for more than two decades [14]. The assumed
interpretability of some families of ML models has justified recent calls for
their use in high-risk domains [73, 74].

#### Decision trees.

Given a DT and an instance $(\mathbf{v},c)$, an intuitive explanation for the
prediction are the literals tested in the path consistent with $\mathbf{v}$.

######  Example 6.

For the DT of Figure 1, and the instance $(\mathbf{v},c)=((0,0,0,0,0),0)$, the
intuitive explanation for the prediction are the features tested in the path
$\langle 1,2,4,6\\}$, and so we could propose as an explanation for why the
prediction the set of literals $\\{1,2,3\\}$.

However, as proved in earlier work [45, 34, 46], such approach for computing
explanations in DTs can provide arbitrarily redundant results.

######  Example 7.

Let us consider again the DT of Figure 1, but now let the target instance be
$(\mathbf{v},c)=(0,0,1,0,1),1)$. Following the approach outlined above, a
possible explanation would be $\\{1,2,3,4,5\\}$, representing the path
consistent with the instance. However, it is possible to prove that there
exists a significantly simpler abductive explanation. If we pick the features
$\\{3,5\\}$ as a possible AXp, it is simple to conclude that, for any
assignment to the features 1, 2, and 4, the prediction never changes, as shown
in Table I. Hence, $\\{3,5\\}$ is a WAXp, and it is simple to conclude that it
is indeed an AXp (i.e. any subset of $\\{3,5\\}$ is no longer a WAXp).

$x_{3}=x_{5}=1$ | $x_{1}$ | $x_{2}$ | $x_{4}$ | $\kappa_{\textnormal{DT}}(\mathbf{x})$
---|---|---|---|---
1 | 0 | 0 | 0 | 1
1 | 0 | 0 | 1 | 1
1 | 0 | 1 | 0 | 1
1 | 0 | 1 | 1 | 1
1 | 1 | 0 | 0 | 1
1 | 1 | 0 | 1 | 1
1 | 1 | 1 | 0 | 1
1 | 1 | 1 | 1 | 1
TABLE I: DT classification given $x_{3}=x_{5}=1$

Table II summarizes the explanation redundancy of the paths in the DT of
Figure 1. Although some paths exhibit no redundancy, i.e. the AXp corresponds
to the path features, there are other paths with up to 60% redundant features.

Path | Features | AXp | %Red
---|---|---|---
$\langle 1,2,4,6\rangle$ | $\\{1,2,3\\}$ | $\\{1,2,3\\}$ | 0%
$\langle 1,2,4,7,10,14\rangle$ | $\\{1,2,3,4,5\\}$ | $\\{1,4,5\\}$ | 40%
$\langle 1,2,4,7,10,15\rangle$ | $\\{1,2,3,4,5\\}$ | $\\{3,5\\}$ | 60%
$\langle 1,2,4,7,11\rangle$ | $\\{1,2,3,4\\}$ | $\\{3,4\\}$ | 50%
$\langle 1,2,5,8,12\rangle$ | $\\{1,2,4,5\\}$ | $\\{1,4,5\\}$ | 40%
$\langle 1,2,5,8,13\rangle$ | $\\{1,2,4,5\\}$ | $\\{2,5\\}$ | 60%
$\langle 1,2,5,9\rangle$ | $\\{1,2,4\\}$ | $\\{2,4\\}$ | 33%
$\langle 1,3\rangle$ | $\\{1\\}$ | $\\{1\\}$ | 0%
TABLE II: Explanation redundancy figures for DT in Figure 1

Besides comprehensive experimental evidence illustrating the importance of
explaining DTs [46, 60], recent work proved a number of additional results.
First, [45, 46] prove that redundancy of path explanations can be arbitrarily
large on the number of features, i.e. there are DTs for which a path contains
all the features, and the explanation contains a single feature. Second, [46]
proves that the family of classification functions that do not exhibit path
redundancy is very restricted. The results above support the conclusions that
DTs ought not serve as explanations, but should be explained instead.

#### Decision lists.

For DLs it has also be argued that explanations are also required [60], both
to avoid redundancy of features in explanations, but also to ensure the
correctness of computed sets of literals as explanations.

######  Example 8.

For the DL of Figure 2, let the instance be $((0,1,0,1,0,1),0)$. It is plain
that the rule $\textnormal{R}_{2}$ fires, and the prediction is 0. What is a
sufficient reason for this prediction? Clearly, $\\{2,4,6\\}$, as listed in
the condition for the rule to fire, is not sufficient for the prediction.
Indeed, we must ensure that rule $\textnormal{R}_{1}$ does not fire, and so
the abductive explanation must either include feature 1 or feature 3\. Let us
pick feature 3. It is the case that $\\{2,3,4,6\\}$ is a sufficient reason for
the prediction given the values in $\mathbf{v}$ dictating the literals in
features 2, 3, 4 and 6. However, one can prove that feature 2 is irrelevant.
Indeed, if feature 3 is assigned value 0, and features 4 and 6 are assigned
value 1, then because of rule $\textnormal{R}_{4}$, the prediction is
guaranteed to be 0, independently of the value of feature 2.
Clearly, if one of the last rules were to fire, finding an explanation would
be even less intuitive than in the case above.

There is recent comprehensive practical evidence to the existence of
explanation redundancy in DLs [60].

It should be noted that explanation redundancy does not yield incorrect
explanations. However, redundancy of explanations is by itself problematic.
First, because it may cause human decision makers to look at features that are
unneeded for the prediction. Second, because the number of concepts that human
decision makers can relate with is fairly small [63], and redundant
information can push explanations beyond that bound.

##  V Myth #02: Model-Agnostic Explainability

Model-agnostic explainability is arguably one of the most widely used XAI
approaches [72, 54, 71].

One concrete line of work [72] finds a set of features that “explains” the
prediction. Concretely, an _anchor_ is defined to be: “ _An anchor explanation
is a rule that sufficiently ’anchors’ the prediction locally – such that
changes to the rest of the feature values of the instance do not matter._ ”
[72].

If the sets of features reported as anchors are indeed _sufficient_ for the
prediction, such that the other features do not matter, then one should be
able to validate those sets of features as abductive explanations, since AXp’s
also _anchor_ the prediction locally.

Given an instance, $(\mathbf{v},c)$, if the computed anchor is a set of
features ${\mathcal{A}}$, then we should be able to validate that,

$\forall(\mathbf{x}\in\mathbb{F}).\bigwedge_{i\in{\mathcal{A}}}(x_{i}=v_{i})\operatorname*{\rightarrow}\kappa(\mathbf{x})=c)$
(11)

which should be true if ${\mathcal{A}}$ were an AXp. To prove that a set of
features is not an AXp, we decide instead whether the following stament is
true,

$\exists(\mathbf{x}\in\mathbb{F}).\bigwedge_{i\in{\mathcal{A}}}(x_{i}=v_{i})\land\kappa(\mathbf{x})\not=c)$
(12)

which can be formulated as the following decision problem,

$\operatorname*{\textnormal{{{CO}}}\\!}\left(\bigwedge_{i\in{\mathcal{A}}}(x_{i}=v_{i})\land\kappa(\mathbf{x})\not=c)\right)$
(13)

where $\operatorname*{\textnormal{{{CO}}}\\!}\left(\varphi\right)$ decides the
satisfiability of the logic formula $\varphi$. Depending on the logic
representation of the classifier, one can use a suitable decision procedure
for deciding whether (13). So, in practice, and given a set of features
reported by Anchor [72], it suffices to use a decision procedure to check
whether (11) holds. It should be noted that an alternative to deciding whether
(11) is to assess how likely it is for (11) not to hold. This involves (exact
or approximate) model counting, and was investigated in [67].

In the case of boosted trees [16], the model-agnostic tool Anchor [72] was
assessed, and its explanations validated with a logic-based explainer [44,
37]. The correctness results are summarized in Table III (more comprehensive
results are reported in earlier work [44, 37, 89]).

Dataset | % Incorrect | % Redundant | % Correct
---|---|---|---
adult | 80.5% | 1.6% | 17.9%
lending | 3.0% | 0.0% | 97.0%
rcdv | 99.4% | 0.4% | 0.2%
compas | 84.4% | 1.7% | 13.9%
german | 99.7% | 0.2% | 0.1%
TABLE III: Correctness results for Anchor’s explanations [44, 37]

Similar results were obtained by interpreting LIME [71] and SHAP [54] as
feature selection explainers [37]. A possible criticism of the results in
Table III is that all inputs are assumed possible, and this may not always be
the case. More recent work reports less negative results on average, when
inferred background knowledge is taken into account [89]. However, even when
inferred background knowledge is taken into account, (non-formal)
explainability with feature selection appears unlikely to contribute to
delivering trust in AI. This remark is confirmed indirectly by results in
[67], where the likelihood of picking the wrong prediction for computed
explanations was shown to be significant.

##  VI Myth #03: Shapley Values in Explainability

Shapley values have been studied as a method of feature attribution for more
than a decade [83, 84], attaining widespread visibility as the result of their
use in SHAP [54, 53].

Nevertheless, SHAP exploits approximate Shapley values [54], given that the
exact computation of Shapley values is generally considered to be intractable.
Thus, and to the best of our knowledge, there is no validation of the adequacy
of Shapley values for explainability. Moreover, recent work proved that
Shapley values could be computed in polynomial-time for restricted classes of
boolean circuits [4]. In addition, when functions are represented by truth
tables, then it is simple to prove that Shapley values can be computed in
polynomial time on the size of the truth table [36].

Furthermore, if Shapley values correctly capture the relative importance of
features, then there should be a tight connection between the values obtained
by methods of feature attribution and the features obtained with feature
selection. Evidently, if a feature _cannot_ be picked by a feature selection
method, then it should have _no_ assigned feature importance. Since most
methods of feature selection are heuristic, offering no guarantees of
correctness, we consider formally defined abductive explanations as described
in Section III-E. Concretely, we focus on the (crucial) distinction between
relevant and irrelevant features and their relative importance as computed by
Shapley values for explainability. Moreover, we investigate whether some
relevant feature(s) could be assigned less importance that some other
irrelevant feature(s). Among a number of possible issues, we investigated the
following issues:

  1. I1.

For a boolean classifier, with an instance $(\mathbf{v},c)$, and feature $i$
such that,

$\mathsf{Irrelevant}(i)\land\left(\mathsf{Sv}(i)\not=0\right)$

Thus, an I1 issue is such that the feature is irrelevant, but its Shapley
value is non-zero.

  2. I2.

For a boolean classifier, with an instance $(\mathbf{v},c)$ and features
$i_{1}$ and $i_{2}$ such that,

$\begin{array}[]{l}\mathsf{Irrelevant}(i_{1})\land\mathsf{Relevant}(i_{2})\land\left(|\mathsf{Sv}(i_{1})|>|\mathsf{Sv}(i_{2})|\right)\end{array}$

Thus, an I2 issue is such that there is at least one irrelevant feature
exhibiting a Shapley value larger (in absolute value) than the Shapley of a
relevant feature.

  3. I3.

For a boolean classifier, with instance $(\mathbf{v},c)$, and feature $i$ such
that,

$\mathsf{Relevant}(i)\land\left(\mathsf{Sv}(i)=0\right)$

Thus, an I3 issue is such that the feature is relevant, but its Shapley value
is zero.

  4. I4.

For a boolean classifier, with instance $(\mathbf{v},c)$, and features $i_{1}$
and $i_{2}$ such that,

$\displaystyle[$
$\displaystyle\mathsf{Irrelevant}(i_{1})\land\left(\mathsf{Sv}(i_{1})\not=0\right)]\land$
$\displaystyle[$
$\displaystyle\mathsf{Relevant}(i_{2})\land\left(\mathsf{Sv}(i_{2})=0\right)]$

Thus, an I4 issue is such that there is at least one irrelevant feature with a
non-zero Shapley value and a relevant feature with a Shapley value of 0.

  5. I5.

For a boolean classifier, with instance $(\mathbf{v},c)$ and feature $i$ such
that,

$[\mathsf{Irrelevant}(i)\land\forall_{1\leq{j}\leq{m},j\not=i}\left(|\mathsf{Sv}(j)|<|\mathsf{Sv}(i)|\right)]$

Thus, an I5 issue is such that there is one irrelevant feature exhibiting the
value Shapley value (in absolute value). (I5 can be viewed as a special case
of the other issues, and is not analyzed separately in earlier work [36].)

Case | Instance | Relevant | Irrelevant |  Shapley values | Justification
---|---|---|---|---|---
I4 | $((0,0,1,1),0)$ | $1,2,4$ | $3$ |  $\begin{array}[]{l}\mathsf{Sv}(1)=-0.13\\\ \mathsf{Sv}(2)=0.33\\\ \mathsf{Sv}(3)=0.08\\\ \mathsf{Sv}(4)=0.00\\\ \end{array}$ | $\begin{array}[]{l}\textnormal{\small{{Irrelevant}}}(3)\land\mathsf{Sv}(3)\not=0\land\\\ \textnormal{\small{{Relevant}}}(4)\land\mathsf{Sv}(4)=0\end{array}$
I5 | $((1,1,1,1),0)$ | $1,2,3$ | $4$ |  $\begin{array}[]{l}\mathsf{Sv}(1)=-0.12\\\ \mathsf{Sv}(2)=-0.12\\\ \mathsf{Sv}(3)=-0.12\\\ \mathsf{Sv}(4)=0.17\\\ \end{array}$ | $\begin{array}[]{l}\textnormal{\small{{Irrelevant}}}(4)\land\\\ \forall(j\in\\{1,2,3\\}).|\mathsf{Sv}(j)|<\mathsf{Sv}(4)|\end{array}$

TABLE IV: Examples of issues with Shapley for explainability for boolean
classifiers of Figure 3

Whereas a more comprehensive assessment is available elsewhere [36], the next
example illustrates the existence of issues I4 and I5 for the boolean
classifiers in Figure 3444Given a boolean classifier represented by a truth
table, [36] describes simple polynomial-time algorithms for computing of
Shapley values, one or more AXp’s, one or more CXp’s, and for deciding
relevancy/irrelevancy of features. The fact that the classifier is represented
by a truth table enables polynomial-time algorithms for analyzing all subsets,
computing average values, but also deciding over existential/universal
quantifiers.

######  Example 9.

We focus on I4 and I5 (a more detailed analysis can be found elsewhere [36]).
Table IV confirms the occurrence of issue I4 for $\kappa_{I4}$ (see Figure
3(a)), and of issue I5 for $\kappa_{I5}$ (see Figure 3(b)). Among these two
cases, the example of Figure 3(b) is significant, in that the irrelevant
feature has the largest absolute Shapley value among all the features.

The example above (and the data reported in earlier work [36]) offer
conclusive evidence that Shapley values for explainability can provide
misleading information, about the relative importance of features, to human
decision makers.

##  VII Discussion

As noted earlier in Section IV, the refutation of myth #01 is based on the
existence of redundant features in explanations produced by manual inspection
of DTs and DLs (a similar situation could be envisioned for DSs). One could
argue that redundancy is not problematic per se, e.g. if DTs are shallow or
small. However, if redundancy of explanations were acceptable, then reporting
all features as an explanation could also be argued to be acceptable. The key
observation is that succinctness and irreducibility are two desirable
properties when reporting explanations. Furthermore, there are recent examples
of large deep DTs in practical use [25].

Regarding the other two myths, the situation is more problematic, in that
human decision makers can obtain erroneous information when using either
model-agnostic explainability (in the case of myth #02) or when using feature
attribution based on Shapley values (in the case of myth #03). If one critical
goal of XAI is to build trust, then neither model-agnostic explainability nor
feature attribution with Shapley values should be employed, in domains where
trust matters, especially in those where situations of catastrophic failure
can occur.

##  VIII Conclusions & Research Directions

This paper overviews a number of recent results which disprove several myths
of (non-formal) XAI. The first myth of XAI is that simple models do not
require explanations since the model (which is called interpretable) is itself
the explanation [73, 65, 74]. Recent results [46, 45] prove in theory and
demonstrate in practice that redundant literals in paths are ubiquitous in
decision trees, one of the hallmarks of model interpretability. A second myth
of XAI is the use of model-agnostic methods. Recent work [44, 37, 89] offers
experimental evidence that model-agnostic explanations are often incorrect. A
third and final myth of XAI is the use of Shapley values as the theoretical
underpinning of (some) feature attribution methods. Recent work [36]
demonstrated that Shapley values can give misleading information regarding the
relative importance of features in explanations.

Future work in applying formal methods to XAI will continue to expand the
range of ML models that can be efficiently explained, but it will continue to
uncover other expected myths of XAI. * This work resulted from collaborations
with several colleagues, including N. Asher, M. Cooper, X. Huang, A. Hurault,
A. Ignatiev, Y. Izza, O. Létoffé, C. Mencía, A. Morgado, N. Narodytska. R.
Passos and J. Planes. The author also acknowledges the incentive provided by
the ERC who, by not funding this research nor a handful of other grant
applications between 2012 and 2022, has had a lasting impact in framing the
research presented in this paper.

## References

  * [1] L. Amgoud and J. Ben-Naim, “Axiomatic foundations of explainability,” in _IJCAI_ , 2022, pp. 636–642.
  * [2] M. Arenas, D. Baez, P. Barceló, J. Pérez, and B. Subercaseaux, “Foundations of symbolic languages for model interpretability,” in _NeurIPS_ , 2021.
  * [3] M. Arenas, P. Barceló, L. E. Bertossi, and M. Monet, “On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results,” _CoRR_ , vol. abs/2104.08015, 2021. [Online]. Available: https://arxiv.org/abs/2104.08015
  * [4] ——, “The tractability of SHAP-score-based explanations for classification over deterministic and decomposable boolean circuits,” in _AAAI_ , 2021, pp. 6670–6678.
  * [5] M. Arenas, P. Barceló, M. Romero, and B. Subercaseaux, “On computing probabilistic explanations for decision trees,” _CoRR_ , vol. abs/2207.12213, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2207.12213
  * [6] G. Audemard, S. Bellart, L. Bounia, F. Koriche, J. Lagniez, and P. Marquis, “On the computational intelligibility of boolean classifiers,” in _KR_ , 2021, pp. 74–86.
  * [7] ——, “On the explanatory power of boolean decision trees,” _Data Knowl. Eng._ , vol. 142, p. 102088, 2022.
  * [8] S. Bach, A. Binder, G. Montavon, F. Klauschen, K.-R. Müller, and W. Samek, “On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation,” _PloS one_ , vol. 10, no. 7, p. e0130140, 2015.
  * [9] P. Barceló, M. Monet, J. Pérez, and B. Subercaseaux, “Model interpretability through the lens of computational complexity,” in _NeurIPS_ , 2020.
  * [10] S. Barocas, M. Hardt, and A. Narayanan, _Fairness in machine learning_. Online book, 2022, https://fairmlbook.org/pdf/fairmlbook.pdf.
  * [11] Y. Bengio, Y. LeCun, and G. E. Hinton, “Deep learning for AI,” _Commun. ACM_ , vol. 64, no. 7, pp. 58–65, 2021. [Online]. Available: https://doi.org/10.1145/3448250
  * [12] G. Blanc, J. Lange, and L. Tan, “Provably efficient, succinct, and precise explanations,” in _NeurIPS_ , 2021.
  * [13] R. Boumazouza, F. C. Alili, B. Mazure, and K. Tabia, “ASTERYX: A model-agnostic SaT-based appRoach for sYmbolic and score-based eXplanations,” in _CIKM_ , 2021, pp. 120–129.
  * [14] L. Breiman, “Statistical modeling: The two cultures,” _Statistical science_ , vol. 16, no. 3, pp. 199–231, 2001.
  * [15] J. Chen, L. Song, M. J. Wainwright, and M. I. Jordan, “L-Shapley and C-Shapley: Efficient model interpretation for structured data,” in _ICLR_ , 2019.
  * [16] T. Chen and C. Guestrin, “XGBoost: A scalable tree boosting system,” in _KDD_ , 2016, pp. 785–794.
  * [17] M. C. Cooper and J. Marques-Silva, “On the tractability of explaining decisions of classifiers,” in _CP_ , L. D. Michel, Ed., 2021, pp. 21:1–21:18.
  * [18] ——, “Tractability of explaining classifier decisions,” _Artif. Intell._ , vol. 316, p. 103841, 2023. [Online]. Available: https://doi.org/10.1016/j.artint.2022.103841
  * [19] A. Darwiche and A. Hirth, “On the (complete) reasons behind decisions,” _J. Log. Lang. Inf._ , vol. 32, no. 1, pp. 63–88, 2023. [Online]. Available: https://doi.org/10.1007/s10849-022-09377-8
  * [20] A. Darwiche and P. Marquis, “On quantifying literals in boolean logic and its applications to explainable AI,” _J. Artif. Intell. Res._ , vol. 72, pp. 285–328, 2021.
  * [21] A. Datta, S. Sen, and Y. Zick, “Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems,” in _IEEE S &P_, 2016, pp. 598–617.
  * [22] G. V. den Broeck, A. Lykov, M. Schleich, and D. Suciu, “On the tractability of SHAP explanations,” in _AAAI_ , 2021, pp. 6505–6513.
  * [23] ——, “On the tractability of SHAP explanations,” _J. Artif. Intell. Res._ , vol. 74, pp. 851–886, 2022. [Online]. Available: https://doi.org/10.1613/jair.1.13283
  * [24] J. Ferreira, M. de Sousa Ribeiro, R. Gonçalves, and J. Leite, “Looking inside the black-box: Logic-based explanations for neural networks,” in _KR_ , 2022, p. 432–442.
  * [25] M. M. Ghiasi, S. Zendehboudi, and A. A. Mohsenipour, “Decision tree-based diagnosis of coronary artery disease: CART model,” _Comput. Methods Programs Biomed._ , vol. 192, p. 105400, 2020. [Online]. Available: https://doi.org/10.1016/j.cmpb.2020.105400
  * [26] N. Gorji and S. Rubin, “Sufficient reasons for classifier decisions in the presence of domain constraints,” in _AAAI_ , February 2022.
  * [27] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi, “A survey of methods for explaining black box models,” _ACM Comput. Surv._ , vol. 51, no. 5, pp. 93:1–93:42, 2019.
  * [28] D. Gunning, “Explainable artificial intelligence XAI(),” DARPA, Tech. Rep. DARPA-BAA-16-53, 8 2016.
  * [29] D. Gunning and D. W. Aha, “DARPA’s explainable artificial intelligence (XAI) program,” _AI Mag._ , vol. 40, no. 2, pp. 44–58, 2019. [Online]. Available: https://doi.org/10.1609/aimag.v40i2.2850
  * [30] D. Gunning, M. Stefik, J. Choi, T. Miller, S. Stumpf, and G. Yang, “XAI - explainable artificial intelligence,” _Sci. Robotics_ , vol. 4, no. 37, 2019\. [Online]. Available: https://doi.org/10.1126/scirobotics.aay7120
  * [31] X. Hu, C. Rudin, and M. I. Seltzer, “Optimal sparse decision trees,” in _NeurIPS_ , 2019, pp. 7265–7273.
  * [32] X. Huang, M. C. Cooper, A. Morgado, J. Planes, and J. Marques-Silva, “Feature necessity & relevancy in ML classifier explanations,” in _TACAS_ , 4 2023.
  * [33] X. Huang, Y. Izza, A. Ignatiev, M. C. Cooper, N. Asher, and J. Marques-Silva, “Tractable explanations for d-DNNF classifiers,” in _AAAI_ , 2022, pp. 5719–5728.
  * [34] X. Huang, Y. Izza, A. Ignatiev, and J. Marques-Silva, “On efficiently explaining graph-based classifiers,” in _KR_ , 2021, pp. 356–367.
  * [35] X. Huang, Y. Izza, and J. Marques-Silva, “Solving explainability queries with quantification: The case of feature relevancy,” in _AAAI_ , 2023.
  * [36] X. Huang and J. Marques-Silva, “The inadequacy of Shapley values for explainability,” _CoRR_ , vol. abs/2302.08160, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2302.08160
  * [37] A. Ignatiev, “Towards trustable explainable AI,” in _IJCAI_ , 2020, pp. 5154–5158.
  * [38] A. Ignatiev, M. C. Cooper, M. Siala, E. Hebrard, and J. Marques-Silva, “Towards formal fairness in machine learning,” in _CP_ , 2020, pp. 846–867.
  * [39] A. Ignatiev, Y. Izza, P. J. Stuckey, and J. Marques-Silva, “Using MaxSAT for efficient explanations of tree ensembles,” in _AAAI_ , 2022, pp. 3776–3785.
  * [40] A. Ignatiev and J. Marques-Silva, “SAT-based rigorous explanations for decision lists,” in _SAT_ , 2021, pp. 251–269.
  * [41] A. Ignatiev, N. Narodytska, N. Asher, and J. Marques-Silva, “From contrastive to abductive explanations and back again,” in _AIxIA_ , 2020, pp. 335–355.
  * [42] A. Ignatiev, N. Narodytska, and J. Marques-Silva, “Abduction-based explanations for machine learning models,” in _AAAI_ , 2019, pp. 1511–1519.
  * [43] ——, “On relating explanations and adversarial examples,” in _NeurIPS_ , 2019, pp. 15 857–15 867.
  * [44] ——, “On validating, repairing and refining heuristic ML explanations,” _CoRR_ , vol. abs/1907.02509, 2019. [Online]. Available: http://arxiv.org/abs/1907.02509
  * [45] Y. Izza, A. Ignatiev, and J. Marques-Silva, “On explaining decision trees,” _CoRR_ , vol. abs/2010.11034, 2020. [Online]. Available: https://arxiv.org/abs/2010.11034
  * [46] ——, “On tackling explanation redundancy in decision trees,” _J. Artif. Intell. Res._ , vol. 75, pp. 261–321, 2022. [Online]. Available: https://jair.org/index.php/jair/article/view/13575/
  * [47] ——, “On tackling explanation redundancy in decision trees,” _CoRR_ , vol. abs/2205.09971, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2205.09971
  * [48] Y. Izza and J. Marques-Silva, “On explaining random forests with SAT,” in _IJCAI_ , 2021, pp. 2584–2591.
  * [49] H. Lakkaraju, S. H. Bach, and J. Leskovec, “Interpretable decision sets: A joint framework for description and prediction,” in _KDD_ , 2016, pp. 1675–1684.
  * [50] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [51] Z. C. Lipton, “The mythos of model interpretability,” _Commun. ACM_ , vol. 61, no. 10, pp. 36–43, 2018.
  * [52] X. Liu and E. Lorini, “A unified logical framework for explanations in classifier systems,” _J. Log. Comput._ , vol. 33, no. 2, pp. 485–515, 2023\. [Online]. Available: https://doi.org/10.1093/logcom/exac102
  * [53] S. M. Lundberg, G. G. Erion, H. Chen, A. J. DeGrave, J. M. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S. Lee, “From local explanations to global understanding with explainable AI for trees,” _Nat. Mach. Intell._ , vol. 2, no. 1, pp. 56–67, 2020. [Online]. Available: https://doi.org/10.1038/s42256-019-0138-9
  * [54] S. M. Lundberg and S. Lee, “A unified approach to interpreting model predictions,” in _NeurIPS_ , 2017, pp. 4765–4774.
  * [55] E. L. Malfa, R. Michelmore, A. M. Zbrzezny, N. Paoletti, and M. Kwiatkowska, “On guaranteed optimal robust explanations for NLP models,” in _IJCAI_ , 2021, pp. 2658–2665.
  * [56] J. Marques-Silva, “Logic-based explainability in machine learning,” _CoRR_ , vol. abs/2211.00541, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2211.00541
  * [57] J. Marques-Silva, T. Gerspacher, M. C. Cooper, A. Ignatiev, and N. Narodytska, “Explaining naive bayes and other linear classifiers with polynomial time and delay,” in _NeurIPS_ , 2020.
  * [58] ——, “Explanations for monotonic classifiers,” in _ICML_ , 2021, pp. 7469–7479.
  * [59] J. Marques-Silva and A. Ignatiev, “Delivering trustworthy AI through formal XAI,” in _AAAI_ , 2022, pp. 12 342–12 350.
  * [60] J. Marques-Silva and A. Ignatiev, “No silver bullet: interpretable ml models must be explained,” _Frontiers in Artificial Intelligence_ , vol. 6, 2023\. [Online]. Available: https://www.frontiersin.org/articles/10.3389/frai.2023.1128212
  * [61] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” _ACM Comput. Surv._ , vol. 54, no. 6, pp. 115:1–115:35, 2021. [Online]. Available: https://doi.org/10.1145/3457607
  * [62] L. Merrick and A. Taly, “The explanation game: Explaining machine learning models using Shapley values,” in _CDMAKE_ , 2020, pp. 17–38.
  * [63] G. A. Miller, “The magical number seven, plus or minus two: Some limits on our capacity for processing information.” _Psychological review_ , vol. 63, no. 2, pp. 81–97, 1956.
  * [64] T. Miller, “Explanation in artificial intelligence: Insights from the social sciences,” _Artif. Intell._ , vol. 267, pp. 1–38, 2019.
  * [65] C. Molnar, _Interpretable Machine Learning_. Leanpub, 2020, http://tiny.cc/6c76tz.
  * [66] G. Montavon, W. Samek, and K. Müller, “Methods for interpreting and understanding deep neural networks,” _Digit. Signal Process._ , vol. 73, pp. 1–15, 2018.
  * [67] N. Narodytska, A. A. Shrotri, K. S. Meel, A. Ignatiev, and J. Marques-Silva, “Assessing heuristic machine learning explanations with model counting,” in _SAT_ , 2019, pp. 267–278.
  * [68] D. Pessach and E. Shmueli, “A review on fairness in machine learning,” _ACM Comput. Surv._ , vol. 55, no. 3, pp. 51:1–51:44, 2023. [Online]. Available: https://doi.org/10.1145/3494672
  * [69] ProPublica, “Machine bias,” https://bit.ly/3zaHb2F, 2016.
  * [70] R. Reiter, “A theory of diagnosis from first principles,” _Artif. Intell._ , vol. 32, no. 1, pp. 57–95, 1987. [Online]. Available: https://doi.org/10.1016/0004-3702(87)90062-2
  * [71] M. T. Ribeiro, S. Singh, and C. Guestrin, “”why should I trust you?”: Explaining the predictions of any classifier,” in _KDD_ , 2016, pp. 1135–1144.
  * [72] ——, “Anchors: High-precision model-agnostic explanations,” in _AAAI_ , 2018, pp. 1527–1535.
  * [73] C. Rudin, “Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead,” _Nature Machine Intelligence_ , vol. 1, no. 5, pp. 206–215, 2019.
  * [74] ——, “Why black box machine learning should be avoided for high-stakes decisions, in brief,” _Nature Reviews Methods Primers_ , vol. 2, no. 1, pp. 1–2, 2022.
  * [75] C. Rudin, C. Chen, Z. Chen, H. Huang, L. Semenova, and C. Zhong, “Interpretable machine learning: Fundamental principles and 10 grand challenges,” _Statistics Surveys_ , vol. 16, pp. 1–85, 2022.
  * [76] W. Samek, G. Montavon, S. Lapuschkin, C. J. Anders, and K. Müller, “Explaining deep neural networks and beyond: A review of methods and applications,” _Proc. IEEE_ , vol. 109, no. 3, pp. 247–278, 2021. [Online]. Available: https://doi.org/10.1109/JPROC.2021.3060483
  * [77] W. Samek, G. Montavon, A. Vedaldi, L. K. Hansen, and K. Müller, Eds., _Explainable AI: Interpreting, Explaining and Visualizing Deep Learning_. Springer, 2019.
  * [78] W. Samek and K. Müller, “Towards explainable artificial intelligence,” in _Explainable AI: Interpreting, Explaining and Visualizing Deep Learning_ , W. Samek, G. Montavon, A. Vedaldi, L. K. Hansen, and K. Müller, Eds. Springer, 2019, pp. 5–22.
  * [79] S. A. Seshia, D. Sadigh, and S. S. Sastry, “Toward verified artificial intelligence,” _Commun. ACM_ , vol. 65, no. 7, pp. 46–55, 2022. [Online]. Available: https://doi.org/10.1145/3503914
  * [80] L. S. Shapley, “A value for $n$-person games,” _Contributions to the Theory of Games_ , vol. 2, no. 28, pp. 307–317, 1953.
  * [81] A. Shih, A. Choi, and A. Darwiche, “A symbolic approach to explaining bayesian network classifiers,” in _IJCAI_ , 2018, pp. 5103–5111.
  * [82] D. Slack, A. Hilgard, S. Singh, and H. Lakkaraju, “Reliable post hoc explanations: Modeling uncertainty in explainability,” in _NeurIPS_ , 2021, pp. 9391–9404.
  * [83] E. Strumbelj and I. Kononenko, “An efficient explanation of individual classifications using game theory,” _J. Mach. Learn. Res._ , vol. 11, pp. 1–18, 2010. [Online]. Available: https://dl.acm.org/doi/10.5555/1756006.1756007
  * [84] ——, “Explaining prediction models and individual predictions with feature contributions,” _Knowl. Inf. Syst._ , vol. 41, no. 3, pp. 647–665, 2014\. [Online]. Available: https://doi.org/10.1007/s10115-013-0679-x
  * [85] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” in _ICLR_ , 2014\.
  * [86] The Verge, “UK ditches exam results generated by biased algorithm after student protests,” https://bit.ly/3kevIsB, 2020.
  * [87] S. Wäldchen, J. MacDonald, S. Hauch, and G. Kutyniok, “The computational complexity of understanding binary classifier decisions,” _J. Artif. Intell. Res._ , vol. 70, pp. 351–387, 2021. [Online]. Available: https://doi.org/10.1613/jair.1.12359
  * [88] D. S. Watson, “Rational Shapley values,” in _FAccT_ , 2022, pp. 1083–1094.
  * [89] J. Yu, A. Ignatiev, P. J. Stuckey, N. Narodytska, and J. Marques-Silva, “Eliminating the impossible, whatever remains must be true: On extracting and applying background knowledge in the context of formal explanations,” in _AAAI_ , 2023.