# On Correcting SHAP Scores

Olivier Létoffé  Xuanxiang Huang  Joao Marques-Silva

###### Abstract

Recent work uncovered examples of classifiers for which SHAP scores yield
misleading feature attributions. While such examples might be perceived as
suggesting the inadequacy of Shapley values for explainability, this paper
shows that the source of the identified shortcomings of SHAP scores resides
elsewhere. Concretely, the paper makes the case that the failings of SHAP
scores result from the characteristic functions used in earlier works.
Furthermore, the paper identifies a number of properties that characteristic
functions ought to respect, and proposes several novel characteristic
functions, each exhibiting one or more of the desired properties. More
importantly, some of the characteristic functions proposed in this paper are
guaranteed not to exhibit any of the shortcomings uncovered by earlier work.
The paper also investigates the impact of the new characteristic functions on
the complexity of computing SHAP scores. Finally, the paper proposes
modifications to the tool SHAP to use instead one of our novel characteristic
functions, thereby eliminating some of the limitations reported for SHAP
scores.

Machine Learning, ICML

##  1 Introduction

Shapley values for eXplainable AI (XAI), i.e. SHAP scores (Lundberg & Lee,
2017), are arguably among the most widely used explainability methods that
target the attribution of (relative) feature importance, as exemplified by the
success of the tool SHAP111See https://github.com/shap/shap. Despite the
massive popularity of SHAP scores, some works have identified limitations with
their use (Young et al., 2019; Kumar et al., 2020; Sundararajan & Najmi, 2020;
Merrick & Taly, 2020; Fryer et al., 2021; Yan & Procaccia, 2021; Mothilal et
al., 2021; Afchar et al., 2021; Watson et al., 2021; Kumar et al., 2021;
Campbell et al., 2022). However, most of these limitations can be attributed
to the results obtained with existing tools, and not necessarily with the
theoretical foundations of SHAP scores. More recent work (Huang & Marques-
Silva, 2023, 2024) uncovered examples of classifiers where _exact_ SHAP scores
assign misleading importance to features. Namely, features having no influence
in a prediction can be assigned more importance than features having the most
influence in the prediction. This recent evidence should be perceived as more
problematic, because it reveals limitations with the theoretical foundations
of SHAP scores, and not with concrete implementations. Accordingly, these
results might also be perceived as demonstrating the inadequacy of Shapley
values for explainability. Nevertheless, Shapley values are of fundamental
importance, not only in game theory, but also in many other domains, namely
because of their intrinsic properties (Shapley, 1953).

This paper argues that the key issue with SHAP scores is not the use of
Shapley values in explainability per se, and shows that the identified
shortcomings of SHAP scores can be solely attributed to the characteristic
functions used in earlier works (Strumbelj & Kononenko, 2010, 2014; Lundberg &
Lee, 2017; Janzing et al., 2020; Sundararajan & Najmi, 2020; Arenas et al.,
2021; Van den Broeck et al., 2021, 2022; Arenas et al., 2023). As noted in the
recent past (Janzing et al., 2020; Sundararajan & Najmi, 2020), by changing
the characteristic function, one is able to produce different sets of SHAP
scores222Unfortunately, this paper argues that past alternative proposals of
characteristic functions (Janzing et al., 2020; Sundararajan & Najmi, 2020)
also exhibit key limitations.. Motivated by these observations, the paper
outlines fundamental properties that characteristic functions ought to exhibit
in the context of XAI. Furthermore, the paper proposes several novel
characteristic functions, which either respect some or all of the identified
properties. In addition, the paper analyzes the impact of the novel
characteristic functions on the computational complexity of computing SHAP
scores, by building on recent work on the same topic (Van den Broeck et al.,
2021; Arenas et al., 2021; Van den Broeck et al., 2022; Arenas et al., 2023).
An indirect consequence of our work is that _corrected_ SHAP scores can be
safely used for feature attribution in XAI, while offering strong guarantees
regarding known shortcomings.

The paper is organized as follows. Section 2 introduces the notation and
definitions used throughout the paper. Section 3 dissects some of the recently
reported shortcomings with SHAP scores (Huang & Marques-Silva, 2023, 2024).
The in-depth analysis of these shortcomings motivates the proposal of key
properties that characteristic functions ought to exhibit. These are discussed
in Section 4. Section 5 devises several novel characteristic functions, which
are shown to correct some or all of the shortcomings of the characteristic
functions used in earlier work. Section 6 studies the complexity of computing
SHAP scores given the novel characteristic functions proposed in this paper.
Section 7 outlines a simple modification to the SHAP tool (Lundberg & Lee,
2017), which corrects some of the issues of SHAP scores. Section 8 concludes
the paper.

##  2 Preliminaries

### Classification problems.

Let ${\mathcal{F}}=\\{1,\ldots,m\\}$ denote a set of features and
${\mathcal{K}}=\\{c_{1},c_{2},\ldots,c_{K}\\}$ a set of classes. Each feature
$i\in{\mathcal{F}}$ takes values from a domain $\mathbb{D}_{i}$. Domains can
be categorical or ordinal. If ordinal, domains can be discrete or real-valued.
Classes can also be categorical or ordinal. Throughout the paper domains are
assumed to be discrete-valued and, unless otherwise stated, classes are
assumed to be ordinal. Feature space is defined by
$\mathbb{F}=\mathbb{D}_{1}\times\mathbb{D}_{2}\times\ldots\times\mathbb{D}_{m}$.
The notation $\mathbf{x}=(x_{1},\ldots,x_{m})$ denotes an arbitrary point in
feature space, where each $x_{i}$ is a variable taking values from
$\mathbb{D}_{i}$. Moreover, the notation $\mathbf{v}=(v_{1},\ldots,v_{m})$
represents a specific point in feature space, where each $v_{i}$ is a constant
representing one concrete value from $\mathbb{D}_{i}$. An _instance_ denotes a
pair $(\mathbf{v},c)$, where $\mathbf{v}\in\mathbb{F}$ and
$c\in{\mathcal{K}}$, and such that $c=\kappa(\mathbf{v})$. An ML classifier
${\mathcal{M}}$ is characterized by a non-constant _classification function_
$\kappa$ that maps feature space $\mathbb{F}$ into the set of classes
${\mathcal{K}}$, i.e. $\kappa:\mathbb{F}\to{\mathcal{K}}$. Given the above, we
associate with a classifier ${\mathcal{M}}$, a tuple
$({\mathcal{F}},\mathbb{F},{\mathcal{K}},\kappa)$. If both
$\mathbb{D}_{i}=\\{0,1\\},i=1,\ldots,m$ and ${\mathcal{K}}=\\{0,1\\}$, then
the classifier is referred to as a _boolean_ , in which case we use
$\mathbb{B}=\\{0,1\\}$. If the set of classes is ordinal but non-boolean, then
the classifier is referred to as _multi-valued_. Finally, if both the domains
and the set of classes are ordinal (and discrete), then the classifier is
referred to as _discrete_.

### Deterministic decomposable boolean circuits (DDBCs).

For some complexity results, we will analyze DDBCs (Arenas et al., 2021,
2023)333The definition of DDBC mimics the one in (Arenas et al., 2023).. A
boolean circuit $C$ is defined on a set of (input) variables $X$ and it is
represented as a directed acyclic graph, where each node is referred to as a
gate, and where (i) a node with no input edges is a either a variable gate,
and takes a label from $X$, or it is a constant gate, and takes a label from
$\\{0,1\\}$; (ii) a node with incoming edges is a either a AND, OR or NOT
logic gate, where NOT gates have exactly one input; (iii) exactly one node has
no output edges, and denotes the output gate of $C$. Given some circuit
$C_{g}$, $\textnormal{var}(C_{g})$ denotes the set of elements $x\in{X}$ such
that some variable gate node of $C_{g}$ is labeled with $x$. A DDBC is a
boolean circuit where OR gates are _deterministic_ and AND gates are
_decomposable_. A 2-input OR gate, $g=\textnormal{OR}(g_{1},g_{2})$ is
deterministic if for any assignment to the inputs of the circuit, the inputs
of the gate are _not_ both assigned value 1. A 2-input AND gate,
$g=\textnormal{AND}(g_{1},g_{2})$, is decomposable if
$\textnormal{var}(C_{g_{1}})$ is disjoint from $\textnormal{var}(C_{g_{2}})$.
It is well-known that any DDBC can be _smoothed_ , i.e. all OR and AND gates
can be converted to 2-input AND and OR gates (Arenas et al., 2023), in
polynomial time. DDBCs generalize _deterministic decomposable negation normal
form_ (d-DNNF) circuits (Darwiche & Marquis, 2002). Furthermore, we consider a
recent generalization of DDBCs where inputs are allowed to take multi-valued
discrete values (Arenas et al., 2023).

### Selection of sets of points.

Throughout the paper, it will often be necessary to represent sets of points
in feature space that are consistent with some other point in feature space
with respect to the features dictated by some set of features. Accordingly, we
define $\Upsilon:2^{{\mathcal{F}}}\to 2^{\mathbb{F}}$ as
follows444Parameterizations are shown as arguments after the separator ’;’.
However, for simplicity, we will elide parameterizations whenever these are
clear from the context.,

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

i.e. for some ${\mathcal{S}}\subseteq{\mathcal{F}}$, and parameterized by the
point $\mathbf{v}$ in feature space, $\Upsilon({\mathcal{S}};\mathbf{v})$
denotes all the points $\mathbf{x}=(x_{1},\ldots,x_{m})\in\mathbb{F}$ in
feature space that have in common with
$\mathbf{v}=(v_{1},\ldots,v_{m})\in\mathbb{F}$ the values of the features
specified by ${\mathcal{S}}$. Finally, we write
$\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}$ to signify that
$\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})$.

### Distributions, expected value.

Throughout the paper, it is assumed a _uniform probability distribution_ on
each feature, and such that all features are independent. Thus, the
probability of an arbitrary point in feature space becomes:

$\mathbf{P}(\mathbf{x}):=\nicefrac{{1}}{{\Pi_{i\in{\mathcal{F}}}|\mathbb{D}_{i}|}}$
(2)

That is, every point in the feature space has the same probability. The
_expected value_ of a classification function $\kappa$ is denoted as
$\mathbf{E}[\kappa]$. Furthermore, let
$\mathbf{E}[\kappa\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]$
represent the expected of $\kappa$ over points in feature space consistent
with the coordinates of $\mathbf{v}$ dictated by ${\mathcal{S}}$, which is
defined as follows:

$\mathbf{E}[\kappa(\mathbf{x})\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]:=\nicefrac{{1}}{{|\Upsilon({\mathcal{S}};\mathbf{v})|}}\sum\nolimits_{\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})}\kappa(\mathbf{x})$
(3)

Similarly, we define,

$\displaystyle\mathbf{P}(\kappa($
$\displaystyle\mathbf{x})=c\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}):=$
(4)
$\displaystyle\nicefrac{{1}}{{|\Upsilon({\mathcal{S}};\mathbf{v})|}}\sum\nolimits_{\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})}\textnormal{ITE}(\kappa(\mathbf{x})=c,1,0)$

### Explanation problems.

Given a classification problem ${\mathcal{M}}$ and a concrete instance
$(\mathbf{v},c)$, an _explanation problem_ ${\mathcal{E}}$ is a tuple
$({\mathcal{M}},(\mathbf{v},c))$. When describing concepts in explainability,
it is to be assumed an underlying explanation problem ${\mathcal{E}}$, with
all definitions parameterized on ${\mathcal{E}}$.

### Shapley values.

Shapley values were proposed in the context of game theory in the early 1950s
by L. S. Shapley (Shapley, 1953). Shapley values were defined given some set
${\mathcal{S}}$, and a _characteristic function_ , i.e. a real-valued function
defined on the subsets of ${\mathcal{S}}$,
$\upsilon:2^{{\mathcal{S}}}\to\mathbb{R}$, such that $\upsilon(\emptyset)=0$
555The original formulation also required super-additivity of the
characteristic function, but that condition has been relaxed in more recent
works (Dubey, 1975; Young, 1985).. It is well-known that Shapley values
represent the _unique_ function that, given ${\mathcal{S}}$ and $\upsilon$,
respects a number of important axioms. More detail about Shapley values is
available in standard references (Shapley, 1953; Dubey, 1975; Young, 1985;
Roth, 1988).

### SHAP scores.

In the context of explainability, Shapley values are most often referred to as
SHAP scores (Strumbelj & Kononenko, 2010, 2014; Lundberg & Lee, 2017; Arenas
et al., 2021, 2023), and consider a specific characteristic function
$\upsilon_{e}:2^{{\mathcal{F}}}\to\mathbb{R}$, which is defined by,

$\upsilon_{e}({\mathcal{S}};{\mathcal{E}}):=\mathbf{E}[\kappa(\mathbf{x})\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]$
(5)

and where $\Upsilon$ (used in the definition of the expected value) is defined
by (1). Thus, given a set ${\mathcal{S}}$ of features,
$\upsilon_{e}({\mathcal{S}};{\mathcal{E}})$ represents the _e_ xpected value
of the classifier over the points of feature space represented by
$\Upsilon({\mathcal{S}};\mathbf{v})$. The formulation presented in earlier
work (Arenas et al., 2021, 2023) allows for different input distributions when
computing the average values. For the purposes of this paper, it suffices to
consider solely a uniform input distribution, and so the dependency on the
input distribution is not accounted for. Independently of the distribution
considered, it should be clear that in most cases
$\upsilon_{e}(\emptyset)\not=0$; this is the case for example with boolean
classifiers (Arenas et al., 2021, 2023).

To simplify the notation, the following definitions are used,

$\displaystyle\Delta_{e}(i,{\mathcal{S}})$
$\displaystyle:=\left(\upsilon_{e}({\mathcal{S}}\cup\\{i\\})-\upsilon_{e}({\mathcal{S}})\right)$
(6) $\displaystyle\varsigma(|{\mathcal{S}}|)$
$\displaystyle:=\nicefrac{{|{\mathcal{S}}|!(|{\mathcal{F}}|-|{\mathcal{S}}|-1)!}}{{|{\mathcal{F}}|!}}$
(7)

Finally, let $\operatorname*{\mathsf{Sc}}_{e}:{\mathcal{F}}\to\mathbb{R}$,
i.e. the SHAP score for feature $i$, be defined by,666Throughout the paper,
the definitions of $\Delta$ and $\operatorname*{\mathsf{Sc}}$ are explicitly
associated with the characteristic function used in their definition..

$\mathsf{Sc}_{e}(i):=\sum\nolimits_{{\mathcal{S}}\subseteq({\mathcal{F}}\setminus\\{i\\})}\varsigma(|{\mathcal{S}}|)\times\Delta_{e}(i,{\mathcal{S}})$
(8)

Given an instance $(\mathbf{v},c)$, the SHAP score assigned to each feature
measures the _contribution_ of that feature with respect to the prediction.
From earlier work, it is understood that a positive/negative value indicates
that the feature can contribute to changing the prediction, whereas a value of
0 indicates no contribution (Strumbelj & Kononenko, 2010).

### Abductive and contrastive explanations.

Given an explanation problem ${\mathcal{E}}$, a _weak abductive explanation_
(WAXp) is a set of features ${\mathcal{S}}$ such that the probability of
$\kappa(\mathbf{x})=c$ is equal to 1, when the features in ${\mathcal{S}}$ are
assigned the values dictated by $\mathbf{v}$:

$\mathbf{P}(\kappa(\mathbf{x})=c\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}})=1$
(9)

which implies the condition
$\mathbf{E}[\kappa(\mathbf{x})\,|\,\mathbf{x}_{{\mathcal{S}}}=\mathbf{v}_{{\mathcal{S}}}]=c$
in the case of numerical classes. An _abductive explanation_ (AXp) is a
subset-minimal WAXp. Similarly to the case of AXps, a _weak contrastive
explanation_ (WCXp) is a set of features such that the probability of
$\kappa(\mathbf{x})=c$ is less than 1, when the features not in
${\mathcal{S}}$ are assigned the values dictated by $\mathbf{v}$:

$\mathbf{P}(\kappa(\mathbf{x})=c\,|\,\mathbf{x}_{{\mathcal{F}}\setminus{\mathcal{S}}}=\mathbf{v}_{{\mathcal{F}}\setminus{\mathcal{S}}})<1$
(10)

which is implied by the condition
$\mathbf{E}[\kappa(\mathbf{x})\,|\,\mathbf{x}_{{\mathcal{F}}\setminus{\mathcal{S}}}=\mathbf{v}_{{\mathcal{F}}\setminus{\mathcal{S}}}]\not=c$
in the case of numerical classes. A _contrastive explanation_ (CXp) is a
subset-minimal WCXp. Even though the paper defines AXps/CXps using
probabilities (and expected values), these definitions are equivalent to those
used in earlier works (Wäldchen et al., 2021; Marques-Silva, 2022; Darwiche,
2023). (The rationale for the alternative definitions (9) and (10) will become
apparent in the following sections.)

### Feature (ir)relevancy.

The set of features that are included in at least one (abductive) explanation
are defined as follows:

$\mathfrak{F}({\mathcal{E}}):=\\{i\in{\mathcal{X}}\,|\,{\mathcal{X}}\in
2^{{\mathcal{F}}}\land\mathsf{AXp}({\mathcal{X}})\\}$ (11)

where predicate $\mathsf{AXp}({\mathcal{X}})$ holds true if ${\mathcal{X}}$ is
an AXp. (A well-known result is that $\mathfrak{F}({\mathcal{E}})$ remains
unchanged if CXps are used instead of AXps (Ignatiev et al., 2020), in which
case predicate $\mathsf{CXp}({\mathcal{X}})$ holds true if ${\mathcal{X}}$ is
a CXp.) Finally, a feature $i\in{\mathcal{F}}$ is _irrelevant_ , i.e.
predicate $\mathsf{Irrelevant}(i)$ holds true, if
$i\not\in\mathfrak{F}({\mathcal{E}})$; otherwise feature $i$ is _relevant_ ,
and predicate $\mathsf{Relevant}(i)$ holds true. Clearly, given some
explanation problem ${\mathcal{E}}$,
$\forall(i\in{\mathcal{F}}).\mathsf{Irrelevant}(i)\leftrightarrow\neg\mathsf{Relevant}(i)$
777As noted earlier, the parameterization on ${\mathcal{E}}$ is elided..

##  3 Issues with SHAP Scores

Recent work (Huang & Marques-Silva, 2023, 2024) revealed a number of
limitations of SHAP scores. These limitations can be categorized into two
families, those occurring for boolean classifiers and those occurring for
discrete (but non-boolean) classifiers.

BDT/.style= for tree= l=1.5cm,s sep=1.15cm, if n children=0circle,
draw=midblue,text=midblue,edge= my edge , edge=thick, , BDT [$x_{1}$,
label=[yshift=-6.875ex]1 [$x_{4}$, label=[yshift=-6.875ex]2, edge
label=node[midway,left,xshift=-0.5pt] $\in\\{0\\}$ [$x_{2}$,
label=[yshift=-6.875ex]4, edge label=node[midway,left,xshift=-1.5pt]
$\in\\{1\\}$ [$x_{3}$, label=[yshift=-6.875ex]6, edge
label=node[midway,left,xshift=-1.5pt] $\in\\{0\\}$ [5,
label=[yshift=-5.25ex]8, edge label=node[midway,left,xshift=-0.5pt]
$\in\\{0\\}$, rectangle, fill=torange1!10 ] [2, label=[yshift=-5.25ex]9, edge
label=node[midway,right,xshift=-0.575pt] $\in\\{1\\}$, rectangle,
fill=torange1!10 ] ] [$x_{3}$, label=[yshift=-6.875ex]7, edge
label=node[midway,right,xshift=0.25pt] $\in\\{1\\}$ [4,
label=[yshift=-5.25ex]10, edge label=node[midway,left,xshift=-0.5pt]
$\in\\{0\\}$, rectangle, fill=torange1!10 ] [9, label=[yshift=-5.25ex]11, edge
label=node[midway,right,xshift=-0.575pt] $\in\\{1\\}$, rectangle,
fill=torange1!10 ] ] ] [0, label=[yshift=-5.25ex]5, edge
label=node[midway,right,xshift=-0.5pt] $\in\\{0,2\\}$, rectangle,
fill=torange1!10 ] ] [1, label=[yshift=-5.25ex]3, edge=very thick,draw=tblue2,
edge label=node[midway,right,xshift=0.5pt] $\in\\{1\\}$, rectangle,
fill=torange1!10 ] ]

Figure 1: Example decision tree (DT), for classifier $\kappa_{4,a}$, with
target instance $((1,1,1,1),1)$.

### SHAP scores can mislead – existing example.

The example in Figure 1 is adapted from (Huang & Marques-Silva, 2024) [Fig.
8a], representing classifier $\kappa_{4,a}$. The target instance is
$((1,1,1,1),1)$. It is plain that only feature 1 has influence in predicting
class 1. If feature 1 takes value 1, then the prediction is _guaranteed_ to be
class 1. If we want to change the prediction, then we _must_ change the value
of feature 1. Furthermore, we need not change the value of _any_ other
feature, as the prediction is guaranteed to change to a value other than 1, as
long as the value of feature 1 is changed. However, as can be observed in
Table 1, if we compute the SHAP scores (e.g. using (8)), then the information
about relative feature importance is misleading. For example, feature 4 has
the largest absolute SHAP score, whereas feature 1 has a SHAP score of 0,
meaning _no_ importance. However, as argued above, feature 4 plays no role in
setting the predicted class to 1, or in changing from that predicted class.

Classifier | $\mathsf{Sc}_{e}(1)$ | $\mathsf{Sc}_{e}(2)$ | $\mathsf{Sc}_{e}(3)$ | $\mathsf{Sc}_{e}(4)$ | Rank
---|---|---|---|---|---
$\kappa_{4,a}$ | 0.000 | 0.111 | 0.056 | -0.500 | $\langle 4,2,3,1\rangle$
Table 1: SHAP scores for DT in Figure 1.

row # | $x_{1}$ | $x_{2}$ | $\kappa_{1}(\mathbf{x})$
---|---|---|---
1 | 0 | 0 | $1-6\alpha$
2 | 0 | 1 | $1+2\alpha$
3 | 1 | 0 | $1$
4 | 1 | 1 | $1$

(a) Tabular representation (TR)

BDT/.style= for tree= l=1.5cm,s sep=1.15cm, if n children=0circle,
draw=midblue,text=midblue,edge= 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=-1.5pt] $\in\\{0\\}$ [$1-6\alpha$,
label=[yshift=-5.25ex]4, edge label=node[midway,left,xshift=-0.5pt]
$\in\\{0\\}$, rectangle, fill=torange1!10 ] [$1+2\alpha$,
label=[yshift=-5.25ex]5, edge label=node[midway,right,xshift=-0.575pt]
$\in\\{1\\}$, rectangle, fill=torange1!10 ] ] [1, label=[yshift=-5.25ex]3,
edge=very thick,draw=tblue2, edge label=node[midway,right,xshift=0.5pt]
$\in\\{1\\}$, rectangle, fill=torange1!10 ] ]

(b) Decision tree (DT)

Figure 2: Simple classifier. The target instance is $((1,1),1)$.

${\mathcal{S}}$ | rows picked by ${\mathcal{S}}$ | $\upsilon_{e}({\mathcal{S}})$
---|---|---
$\emptyset$ | 1,2,3,4 | $1-\alpha$
$\\{1\\}$ | 3,4 | 1
$\\{2\\}$ | 2,4 | $1+\alpha$
$\\{1,2\\}$ | 4 | 1

Table 2: $\upsilon_{e}({\mathcal{S}})$ for each set ${\mathcal{S}}$.

### SHAP scores can mislead – another example.

Simpler classifiers can be devised, which even allow selecting by how much
SHAP scores mislead. For the decision tree (DT) classifier in Figure 2, Tables
2 and 3 summarize the computation of the SHAP scores, given their definition
in Section 2 (using (8)). For the function not to be constant, we impose
$\alpha\not=0$. The target instance is $(\mathbf{v},c)=((1,1),1)$. As shown
below, the value of $\alpha$ defines the SHAP score of the irrelevant feature
2, whereas the Shapley value of the relevant feature 1 is always 0. Clearly,
the sets of AXps/CXps are the same, i.e. $\\{\\{1\\}\\}$. Given the computed
Shapley values, for $\alpha=-\nicefrac{{1}}{{2}}$, we get $1-6\alpha=4$ and
$1+2\alpha=0$, with $\operatorname*{\mathsf{Sc}}(1)=0$ and
$\operatorname*{\mathsf{Sc}}(2)=\alpha=-\nicefrac{{1}}{{2}}$. However, by
inspection, it is plain that feature 1 is the _only_ feature that has _any_
influence on the prediction, either in setting the prediction to class 1 or in
changing the prediction to a class other than class 1. In contrast, feature 2
has _no_ influence on the prediction, either in setting the prediction to
class 1 or in changing the prediction to a class other than class 1. Thus, the
computed SHAP scores would mislead a human decision maker into deeming feature
2 more important than feature 1 for the instance $((1,1,),1)$.

$i=1$
---
${\mathcal{S}}$ | $\upsilon_{e}({\mathcal{S}})$ | $\upsilon_{e}({\mathcal{S}}\cup\\{1\\})$ | $\Delta_{e}({\mathcal{S}})$ | $\varsigma_{e}({\mathcal{S}})$ | $\varsigma_{e}({\mathcal{S}})\times\Delta_{e}({\mathcal{S}})$
$\emptyset$ | $1-\alpha$ | 1 | $\alpha$ | $\nicefrac{{1}}{{2}}$ | $\nicefrac{{\alpha}}{{2}}$
$\\{2\\}$ | $1+\alpha$ | 1 | $-\alpha$ | $\nicefrac{{1}}{{2}}$ | $-\nicefrac{{\alpha}}{{2}}$
$\operatorname*{\mathsf{Sc}}_{e}(1)~{}~{}=$ | 0
$i=2$
${\mathcal{S}}$ | $\upsilon_{e}({\mathcal{S}})$ | $\upsilon_{e}({\mathcal{S}}\cup\\{2\\})$ | $\Delta_{e}({\mathcal{S}})$ | $\varsigma_{e}({\mathcal{S}})$ | $\varsigma_{e}({\mathcal{S}})\times\Delta({\mathcal{S}})$
$\emptyset$ | $1-\alpha$ | $1+\alpha$ | $2\alpha$ | $\nicefrac{{1}}{{2}}$ | $\alpha$
$\\{1\\}$ | 1 | 1 | 0 | $\nicefrac{{1}}{{2}}$ | 0
$\operatorname*{\mathsf{Sc}}_{e}(2)~{}~{}=$ | $\alpha$

Table 3: Computation of Shapley values

Earlier work (Huang & Marques-Silva, 2023, 2024) discusses several more
parameterized examples of classifiers that illustrate the limitations of SHAP
scores. Unfortunately, as exemplified in Appendix B, the use of baselines
(Janzing et al., 2020; Sundararajan & Najmi, 2020) also reveals a number of
similar limitations.

### Discussion.

The examples above in this section reveal a number of critical issues with the
existing definition of SHAP scores. Motivated by the issues with SHAP scores,
several recent works (Yu et al., 2023b; Biradar et al., 2023; Yu et al.,
2023a) proposed possible alternatives for feature attribution. However, the
proposed alternatives are _not_ themselves SHAP scores, and so do to not
respect the axioms that Shapley values do.

In this paper we propose a different approach at correcting the existing
issues with SHAP scores. Since the definition of SHAP scores is _unique_ given
some characteristic function (Shapley, 1953), we argue that the issues with
SHAP scores are solely attributed to the characteristic functions used in
earlier works (Strumbelj & Kononenko, 2010, 2014; Lundberg & Lee, 2017;
Janzing et al., 2020; Sundararajan & Najmi, 2020; Van den Broeck et al., 2021;
Arenas et al., 2021; Van den Broeck et al., 2022; Arenas et al., 2023), i.e.
$\upsilon_{e}$ as defined by (5). The issues with $\upsilon_{e}$ can be
categorized as follows:

  1. 1.

$\upsilon_{e}$ is highly dependent of classes’ values. In turn, this can be
used to obfuscate the actual importance of features.

  2. 2.

The definition of the characteristic function ignores feature (ir)relevancy,
or alternatively, it ignores information about whether each set is (or is not)
a (weak) AXp/CXp.

  3. 3.

It is also the case that $\upsilon_{e}$ cannot readily be used in setting
where classes are not ordinal.

(As shown in Appendix B, similar issues exist when baselines are used (Janzing
et al., 2020; Sundararajan & Najmi, 2020).)

In the next section we propose properties that characteristic functions ought
to exhibit, which can eliminate some or all of the issues that have been
identified.

##  4 Properties of Characteristic Functions

Given the issues reported in Section 3, this section identifies properties
that characteristic functions should respect. If characteristic functions fail
to respect some of these properties, then the resulting SHAP scores can
provide misleading information about relative feature importance.

### Weak class independence.

Let
${\mathcal{M}}_{1}=({\mathcal{F}},\mathbb{F},{\mathcal{K}}_{1},\kappa_{1})$ be
a classifier, with domain $\mathbb{D}_{i}$ for each feature
$i\in{\mathcal{F}}$. Moreover, let
${\mathcal{M}}_{2}=({\mathcal{F}},\mathbb{F},{\mathcal{K}}_{2},\kappa_{2})$ be
another classifier, with the same domains, and with
$|{\mathcal{K}}_{1}|=|{\mathcal{K}}_{2}|$. Moreover, let
$\mu:{\mathcal{K}}_{1}\to{\mathcal{K}}_{2}$ be a surjective mapping from
${\mathcal{K}}_{1}$ to ${\mathcal{K}}_{2}$, such that for any
$\mathbf{x}\in\mathbb{F}$,
$\kappa_{2}(\mathbf{x})=\mu(\kappa_{1}(\mathbf{x}))$. Finally, let the target
instances be $(\mathbf{v},c)$, for ${\mathcal{M}}_{1}$, and
$(\mathbf{v},\mu(c))$ for ${\mathcal{M}}_{2}$, thus defining the explanation
problems ${\mathcal{E}}_{1}=({\mathcal{M}}_{1},(\mathbf{v},c))$ and
${\mathcal{E}}_{2}=({\mathcal{M}}_{2},(\mathbf{v},\mu(c)))$. A characteristic
function $\upsilon_{t}$ is _weakly class-independent_ if, given surjective
$\mu$,

$\forall(i\in{\mathcal{F}}).[\mathsf{Sc}_{t}(i;{\mathcal{E}}_{1})=\mathsf{Sc}_{t}(i;{\mathcal{E}}_{2})]$

### Strong class independence.

Let
${\mathcal{M}}_{1}=({\mathcal{F}},\mathbb{F},{\mathcal{K}}_{1},\kappa_{1})$ be
a classifier, with domain $\mathbb{D}_{i}$ for each feature
$i\in{\mathcal{F}}$. Moreover, let
${\mathcal{M}}_{2}=({\mathcal{F}},\mathbb{F},{\mathcal{K}}_{2},\kappa_{2})$ be
another classifier, with the same domains. Moreover, let
$\mu:{\mathcal{K}}_{1}\to{\mathcal{K}}_{2}$ be a mapping from
${\mathcal{K}}_{1}$ to ${\mathcal{K}}_{2}$, such that for
$c\in{\mathcal{K}}_{1}$, and such that,

$\forall(b\in{\mathcal{K}}_{1}).[(b\not=c)\operatorname*{\rightarrow}(\mu(b)\not=\mu(c))]$

Finally, let the target instances be $(\mathbf{v},c)$, for
${\mathcal{M}}_{1}$, and $(\mathbf{v},\mu(c))$ for ${\mathcal{M}}_{2}$, thus
defining the explanation problems
${\mathcal{E}}_{1}=({\mathcal{M}}_{1},(\mathbf{v},c))$ and
${\mathcal{E}}_{2}=({\mathcal{M}}_{2},(\mathbf{v},\mu(c)))$. A characteristic
function $\upsilon_{t}$ is _strongly class-independent_ if, given $\mu$,

$\forall(i\in{\mathcal{F}}).[\mathsf{Sc}_{t}(i;{\mathcal{E}}_{1})=\mathsf{Sc}_{t}(i;{\mathcal{E}}_{2})]$

Given the above, the following result holds888Due to restrictions of space,
most of the proofs are included in Appendix A. ,

######  Proposition 1.

If a characteristic function is strongly class-independent, then it is weakly
class-independent.

### Compliance with feature (ir)relevancy.

Characteristic functions should respect feature (ir)relevancy, i.e. a feature
is irrelevant iff its (corrected) SHAP score is 0. Formally, given a
characteristic function $\upsilon_{t}$ is compliant with feature (ir)relevancy
if,

$\forall(i\in{\mathcal{F}}).\mathsf{Irrelevant}(i)\leftrightarrow(\mathsf{Sc}_{t}(i)=0)$
(12)

In previous work (Huang & Marques-Silva, 2023, 2024), SHAP scores are said to
be _misleading_ when compliance with feature (ir)relevancy is not respected.
In the remainder of the paper, we assign the same meaning to the term
_misleading_.

### Numerical neutrality.

SHAP scores require ordinal classes, but classification often contemplates
categorical classes. A characteristic function respects numerical neutrality
if it can be used with both numerical and non-numerical classifiers.

### Discussion.

The properties proposed in this section target the issues reported in earlier
work, where SHAP scores mislead with respect to relative feature importance.
Additional properties may be devised to address any other existing issues.

##  5 New Characteristic Functions

This section proposes several new characteristic functions999In the rest of
the paper, the symbol $\upsilon_{t}$ will be used to denote some concrete
characteristic function distinguished by the letter $t$. The SHAP scores
obtained with such characteristic function will be denoted by
$\mathsf{Sc}_{t}$. Similarly, we will use $\Delta_{t}$. , which respect some
or all of the target properties outlined in Section 4. Throughout this
section, an explanation problem ${\mathcal{E}}=({\mathcal{M}},(\mathbf{v},c))$
is assumed, and it is used to parameterize the proposed characteristic
functions.

### Similarity function.

The new characteristic functions proposed in this paper build on a _similarity
function_ , $\zeta:\mathbb{F}\to\\{0,1\\}$, that is defined as follows:

$\zeta(\mathbf{x};{\mathcal{E}})=\left\\{\begin{array}[]{lcl}1&&\textnormal{if
$(\kappa(\mathbf{x})=\kappa(\mathbf{v}))$}\\\\[2.0pt]
0&&\textnormal{otherwise}\\\ \end{array}\right.$

i.e. $\zeta$ takes value 1 only for the points in feature space for which the
prediction matches the prediction of the target instance. Observe that
$\forall({\mathcal{A}}\subseteq\mathbb{F}).[\mathbf{E}[\zeta(\mathbf{x})\,|\,\mathbf{x}\in{\mathcal{A}}]\in[0,1]]$.
It is also plain to conclude that for
${\mathcal{A}},{\mathcal{B}}\subseteq\mathbb{F}$, with
${\mathcal{A}}\subseteq{\mathcal{B}}$, and given $u\in\\{0,1\\}$, if
$\mathbf{E}[\zeta(\mathbf{x}\,|\,\mathbf{x}\in{\mathcal{B}})]=u$ then
$\mathbf{E}[\zeta(\mathbf{x}\,|\,\mathbf{x}\in{\mathcal{A}})]=u$, A few more
properties of $\zeta$ are apparent. For ${\mathcal{A}}\subseteq\mathbb{F}$,
$u\in\\{0,1\\}$,
$\left(\mathbf{E}[\zeta(\mathbf{x})\,|\,\mathbf{x}\in{\mathcal{A}}]=u\right)\leftrightarrow\forall(\mathbf{x}\in{\mathcal{A}}).[\zeta(\mathbf{x})=u]$.
As a result, it is also the case that
$\left(\mathbf{E}[\zeta(\mathbf{x})\,|\,\mathbf{x}\in{\mathcal{A}}]<1\right)\leftrightarrow\exists(\mathbf{x}\in{\mathcal{A}}).[\zeta(\mathbf{x})=0]$.

### Defining the new characteristic functions.

Given the definition of the similarity function, we now introduce the
following main new characteristic functions.

$\displaystyle\upsilon_{s}({\mathcal{S}};{\mathcal{E}}$
$\displaystyle)~{}~{}:=~{}~{}\mathbf{E}[\zeta(\mathbf{x})\,|\,\mathbf{x}\in\Upsilon({\mathcal{S}};\mathbf{v})]$
(13) $\displaystyle\upsilon_{a}({\mathcal{S}};{\mathcal{E}}$
$\displaystyle)~{}~{}:=~{}~{}\left\\{\begin{array}[]{lcl}1&&\textnormal{if
$\upsilon_{s}({\mathcal{S}};{\mathcal{E}})=1$}\\\\[2.0pt]
0&&\textnormal{otherwise}\\\ \end{array}\right.$ (16)
$\displaystyle\upsilon_{c}({\mathcal{S}};{\mathcal{E}}$
$\displaystyle)~{}~{}:=~{}~{}\left\\{\begin{array}[]{lcl}1&&\textnormal{if
$\upsilon_{s}({\mathcal{F}}\setminus{\mathcal{S}};{\mathcal{E}})<1$
}\\\\[2.0pt] 0&&\textnormal{otherwise}\\\ \end{array}\right.$ (19)

We will refer to characteristic functions $\upsilon_{e}$ (see (5)),
$\upsilon_{s}$, $\upsilon_{a}$, $\upsilon_{c}$, respectively as the _expected
value_ , the _similarity_ , the AXp-based, and the CXp-based characteristic
functions.

Furthermore, we will introduce another characteristic function, which is shown
to be tightly related with $\upsilon_{a}$.

$\upsilon_{n}({\mathcal{S}};{\mathcal{E}})~{}~{}:=~{}~{}\left\\{\begin{array}[]{lcl}1&&\textnormal{if
$\upsilon_{s}({\mathcal{S}};{\mathcal{E}})<1$}\\\\[2.0pt]
0&&\textnormal{otherwise}\\\ \end{array}\right.$ (20)

(Observe that $\upsilon_{n}$ can be viewed as the complement of
$\upsilon_{a}$.)

### Basic attributes of the new characteristic functions.

We start by deriving some basic results regarding the characteristic functions
$\upsilon_{a}$, $\upsilon_{c}$ and $\upsilon_{n}$. Throughout, it is assumed
an explanation problem ${\mathcal{E}}$.

######  Proposition 2.

Given the definition of $\upsilon_{a}$, $\upsilon_{c}$ and $\upsilon_{n}$,
then $\mathsf{Sc}_{a}(i)\geq 0$, $\mathsf{Sc}_{c}(i)\geq 0$, and
$\mathsf{Sc}_{n}(i)\leq 0$.

######  Proposition 3.

The following holds true:

  1. 1.

$\forall({\mathcal{S}}\subseteq{\mathcal{F}}).[\upsilon_{a}({\mathcal{S}})=1\leftrightarrow\mathsf{WAXp}({\mathcal{S}})]$.

  2. 2.

$\forall({\mathcal{S}}\subseteq{\mathcal{F}}).[\upsilon_{n}({\mathcal{S}})=1\leftrightarrow\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})]$.

  3. 3.

$\forall({\mathcal{S}}\subseteq{\mathcal{F}}).[\upsilon_{c}({\mathcal{S}})=1\leftrightarrow\mathsf{WCXp}({\mathcal{S}})]$.

###### Proof.

We consider each case separately:

  1. 1.

If $\upsilon_{a}({\mathcal{S}})=1$, then, as noted earlier in the paper,
$\zeta(\mathbf{x})=1$ for all points $\mathbf{x}\in\Upsilon({\mathcal{S}})$,
and so the classifier’s prediction is $c$ for all points in
$\Upsilon({\mathcal{S}})$. Hence, by definition, ${\mathcal{S}}$ is a WAXp.
Conversely, if ${\mathcal{S}}$ is an WAXp, then the prediction must be $c$ for
all points $\mathbf{x}$ in $\Upsilon({\mathcal{S}})$,
$\forall(\mathbf{x}\in\Upsilon({\mathcal{S}})).[\zeta(\mathbf{x})=1]$. Thus,
$\upsilon_{a}({\mathcal{S}})=1$.

  2. 2.

If $\upsilon_{n}({\mathcal{S}})=1$, then $\zeta(\mathbf{x})\not=1$ for some
point(s) $\mathbf{x}\in\Upsilon({\mathcal{S}})$, and so the classifier’s
prediction is not $c$ for some point(s) in $\Upsilon({\mathcal{S}})$. Hence,
by definition, ${\mathcal{F}}\setminus{\mathcal{S}}$ is a WCXp. Conversely, if
${\mathcal{F}}\setminus{\mathcal{S}}$ is an WCXp, then the prediction must not
be $c$ for some point(s) $\mathbf{x}$ in $\Upsilon({\mathcal{S}})$, i.e.
$\exists(\mathbf{x}\in\Upsilon({\mathcal{S}})).[\zeta(\mathbf{x}\not=1]$.
Thus, $\upsilon_{n}({\mathcal{S}})=1$.

  3. 3.

If $\upsilon_{c}({\mathcal{S}})=1$, then $\zeta(\mathbf{x})\not=1$ for some
point(s) $\mathbf{x}\in\Upsilon({\mathcal{F}}\setminus{\mathcal{S}})$, and so
the classifier’s prediction is not $c$ for some point(s) in
$\Upsilon({\mathcal{F}}\setminus{\mathcal{S}})$. Hence, by definition,
${\mathcal{S}}$ is a WCXp. Conversely, if ${\mathcal{S}}$ is an WCXp, then the
prediction must not be $c$ for some point(s) $\mathbf{x}$ in
$\Upsilon({\mathcal{F}}\setminus{\mathcal{S}})$, i.e.
$\exists(\mathbf{x}\in\Upsilon({\mathcal{F}}\setminus{\mathcal{S}})).[\zeta(\mathbf{x}\not=1]$.
Thus, $\upsilon_{c}({\mathcal{S}})=1$. ∎

######  Proposition 4.

The following holds true:

  1. 1.

$\forall(i\in{\mathcal{F}}).[\mathsf{Sc}_{a}(i)=-\mathsf{Sc}_{n}(i)]$.

  2. 2.

$\forall(i\in{\mathcal{F}}).[\mathsf{Sc}_{a}(i)=\mathsf{Sc}_{c}(i)]$.

An immediate consequence of the results in Propositions 4 and 3, is that the
complexity of computing SHAP scores $\mathsf{Sc}_{t}$ is the same for
$t\in\\{a,c,n\\}$.

### Properties of the new characteristic functions.

We now prove which of the properties listed in Section 4 are respected by
which characteristic functions among those proposed in this section.

It is plain that characteristic functions based on the similarity function
respect numerical neutrality. Furthermore, another general result is that
characteristic functions based on the similarity function guarantee strong
(and so weak) class independence.

######  Proposition 5.

For $t\in\\{s,a,c,n\\}$ and $i\in{\mathcal{F}}$, it is the case that the
characteristic function $\upsilon_{t}$ respects strong class independence.

######  Proposition 6.

For $t\in\\{a,c,n\\}$, then it is the case that
$\forall(i\in{\mathcal{F}}).\mathsf{Irrelevant}(i)\leftrightarrow(\mathsf{Sc}_{t}(i)=0)$.
Thus, $\mathsf{Sc}_{t}$ does not mislead.

Finally, we observe that $\upsilon_{s}$ represents a boolean classifier, and
so it exhibits the issues with SHAP scores uncovered for boolean classifiers
based on $\upsilon_{e}$ in earlier work (Huang & Marques-Silva, 2023, 2024).

##  6 Complexity of Computing SHAP Scores

The previous section introduced novel characteristic functions that exhibit a
number of desirable properties, which in turn ensure that SHAP scores will not
produce misleading information. Another related question is how the novel
characteristic functions impact the computional complexity of computing SHAP
scores. This section starts the effort of mapping such computional complexity.

### Intractable cases.

A number of intractability results have been obtained in recent years (Van den
Broeck et al., 2021, 2022). As noted earlier in the paper, for boolean
functions, the similarity function does not provide any difference with
respect to the original classifier. The following result is clear.

######  Proposition 7.

For a boolean classifier, with $\kappa(\mathbf{v})=1$, then
$\forall(\mathbf{x}\in\mathbb{F}).\zeta(\mathbf{x};{\mathcal{E}})=\kappa(\mathbf{x})$.

From Proposition 7 and Corollary 8 in (Van den Broeck et al., 2022), it is
immediate that,

######  Proposition 8.

Computing SHAP scores $\mathsf{Sc}_{s}$ is #P-hard for boolean classifiers in
CNF or DNF.

Clearly, given Proposition 8, then the computation of SHAP scores for more
complex boolean classifiers is also #P-hard.

Moreover, a key recent result regarding the computation of SHAP scores is that
for the characteristic function $\upsilon_{e}$ there are polynomial-time
algorithms for computing $\mathsf{Sc}_{e}$ (Arenas et al., 2021, 2023). In
contrast, for characteristic functions that build on WAXps/WCXps, the
computation of SHAP scores becomes NP-hard, even for d-DNNF and DDBC
classifiers.

######  Proposition 9.

For $t\in\\{a,c,n\\}$, the computation of the SHAP scores $\mathsf{Sc}_{t}$ is
NP-hard for d-DNNF & DDBC classifiers.

### Polynomial-time cases.

As shown above, the most significant tractability result that is known for
$\upsilon_{e}$ does not hold for $\upsilon_{t}$, with $t\in\\{a,c,n\\}$.
Nevertheless, some tractability results can be proved.

For classifiers represented by tabular representations (e.g. truth tables), it
is simple to devise algorithms polynomial on the size of the classifier’s
representation (Huang & Marques-Silva, 2023).

######  Proposition 10.

There exist polynomial-time algorithms for computing the SHAP scores
$\mathsf{Sc}_{s}$, $\mathsf{Sc}_{a}$, $\mathsf{Sc}_{c}$ for classifiers
represented by tabular representations.

Since the recent results on the tractability of computing SHAP scores for
deterministic and decomposable circuits (d-DNNFs) (Arenas et al., 2021, 2023)
considering boolean classifiers, then from Proposition 7 and (Arenas et al.,
2023), it is the case that,

######  Proposition 11.

The computation of SHAP scores $\mathsf{Sc}_{s}$ is in P for classifiers
represented by non-boolean DDBCs.

(Observe that non-boolean d-DNNFs (Arenas et al., 2023) consider non-boolean
features, but the set of classes is still binary, i.e.
${\mathcal{K}}=\\{0,1\\}$.)

##  7 Similarity-Based SHAP

This section outlines a first step towards addressing the issues with SHAP
scores reported in earlier work, and observed in the tool SHAP (Lundberg &
Lee, 2017). Instead of running SHAP with the original training data and the
original classifier, the similarity-based SHAP (referred to as sSHAP) replaces
the original classifier by the similarity function, and reorganizes training
data accordingly. In terms of running time complexity, the impact of the
modifications to SHAP are negligible. More importantly, sSHAP will be
approximating $\mathsf{Sc}_{s}$, since the underlying characteristic funtion
is $\upsilon_{s}$. In practice, sSHAP is built on top of the SHAP tool
(Lundberg & Lee, 2017).

As noted earlier in Section 5, the use of $\upsilon_{s}$ does not guarantee
the non-existence of the issues reported in earlier work (Huang & Marques-
Silva, 2024), since it is known that even boolean classifiers exhibit a number
of issues related with the relative order of feature importance procuding
misleading information. Nevertheless, another question is whether
$\upsilon_{s}$ can serve to correct SHAP scores (obtained with $\upsilon_{e}$)
in classifiers for which the reported issues rely on non-boolean
classification.

### Difference in SHAP scores for example DT.

Figure 3 shows the similarity function $\zeta_{4,b}$ for the classifier
$\kappa_{4,a}$ shown in Figure 1.

BDT/.style= for tree= l=1.5cm,s sep=1.15cm, if n children=0circle,
draw=midblue,text=midblue,edge= my edge , edge=thick, , BDT [$x_{1}$,
label=[yshift=-6.875ex]1 [$x_{4}$, label=[yshift=-6.875ex]2, edge
label=node[midway,left,xshift=-0.5pt] $\in\\{0\\}$ [$x_{2}$,
label=[yshift=-6.875ex]4, edge label=node[midway,left,xshift=-1.5pt]
$\in\\{1\\}$ [$x_{3}$, label=[yshift=-6.875ex]6, edge
label=node[midway,left,xshift=-1.5pt] $\in\\{0\\}$ [0,
label=[yshift=-5.25ex]8, edge label=node[midway,left,xshift=-0.5pt]
$\in\\{0\\}$, rectangle, fill=tred1!10 ] [0, label=[yshift=-5.25ex]9, edge
label=node[midway,right,xshift=-0.575pt] $\in\\{1\\}$, rectangle,
fill=tred1!10 ] ] [$x_{3}$, label=[yshift=-6.875ex]7, edge
label=node[midway,right,xshift=0.25pt] $\in\\{1\\}$ [0,
label=[yshift=-5.25ex]10, edge label=node[midway,left,xshift=-0.5pt]
$\in\\{0\\}$, rectangle, fill=tred1!10 ] [0, label=[yshift=-5.25ex]11, edge
label=node[midway,right,xshift=-0.575pt] $\in\\{1\\}$, rectangle,
fill=tred1!10 ] ] ] [0, label=[yshift=-5.25ex]5, edge
label=node[midway,right,xshift=-0.5pt] $\in\\{0,2\\}$, rectangle,
fill=tred1!10 ] ] [1, label=[yshift=-5.25ex]3, edge
label=node[midway,right,xshift=0.5pt] $\in\\{1\\}$, rectangle, fill=tgreen1!10
] ]

Figure 3: Characteristic function $\zeta_{4,b}$ for DT of Figure 1, given
instance $((1,1,1,1),1)$.

Given the obtained characteristic function, Table 4 shows the computed SHAP
scores, obtained with both SHAP (Lundberg & Lee, 2017) and sSHAP. (Given the
simple classifiers being considered, both SHAP and sSHAP obtain the exact SHAP
scores.)

Classifier | $\operatorname*{\mathsf{Sc}}(1)$ | $\operatorname*{\mathsf{Sc}}(2)$ | $\operatorname*{\mathsf{Sc}}(3)$ | $\operatorname*{\mathsf{Sc}}(4)$ | Rank
---|---|---|---|---|---
$\kappa_{4,a}$ | 0.000 | 0.111 | 0.056 | -0.500 | $\langle 4,2,3,1\rangle$
$\zeta_{4,b}$ | 0.500 | 0 | 0 | 0 | $\langle 1,2:3:4\rangle$
Table 4: SHAP scores for $\kappa_{4,a}$ and $\zeta_{4,b}$.

For this concrete example and instance, the results confirm that the new
characteristic function $\upsilon_{s}$ enables obtaining SHAP scores that are
not misleading. As we shown next, the same situation is observed for other
classifiers.

### Difference in SHAP scores for example classifiers.

To validate the improvements obtained with $\upsilon_{s}$ with respect to
$\upsilon_{e}$, we studied the non-boolean classifiers reported in (Huang &
Marques-Silva, 2024)101010From (Huang & Marques-Silva, 2024), we consider (i)
the two DTs of case study 2 (Fig. 3 in (Huang & Marques-Silva, 2024)),
referred to as cs02a and cs02b; (ii) the two DTs of case study 3 (Fig. 5 in
(Huang & Marques-Silva, 2024)), referred to as cs03a and cs03b; and (iii) the
two DTs of case study 4 (Fig. 8 in (Huang & Marques-Silva, 2024)), referred to
as cs04a and cs04b. Moreover, for cs02a, cs02b, cs03a and cs03b there exist 16
instances, whereas for cs04a and cs04b there exist 24 instances (because of a
discrete but non-boolean domain for one of the features.) . For each
classifier, each of the possible instances is analyzed, and the SHAP scores
produced by the tools SHAP and sSHAP are recorded. If an irrelevant feature is
assigned an absolute value larger than some other relevant feature, then a
mismatch is declared. Table 5 summarizes the results obtained with the two
tools, where columns _SHAP-FRP mismatch_ shown the number of mismatches
obtained with SHAP, and column _sSHAP-FRP mismatch_ shows the number of
mismatches obtained with sSHAP111111A more extensive comparison is unrealistic
at present; we would have to be able to compute exact SHAP scores, and this is
only computationally feasible for very simple ML models, e.g. restricted
examples of DTs..

DT | SHAP-FRP mismatch | sSHAP-FRP mismatch
---|---|---
cs02a | 11 | 0
cs02b | 4 | 0
cs03a | 5 | 0
cs03b | 4 | 0
cs04a | 15 | 0
cs04b | 4 | 0
Table 5: Comparison of empirical SHAP vs. empirical sSHAP.

As can be concluded, SHAP produces several mismatches. In contrast, sSHAP
produces no mismatch. It should be noted that both tools are approximating the
SHAP scores given the respective characteristic functions, i.e. the computed
scores are not necessarily the ones dictated by (8).

As noted earlier, $\upsilon_{s}$ consists of replacing the original classifier
by a new boolean classifier. Hence, from (Huang & Marques-Silva, 2024), such
boolean classifiers can also produce misleading information. Nevertheless,
given the results above and other experiments, in the cases where
$\upsilon_{s}$ was used, we were unable to observe issue I8 (as proposed in
(Huang & Marques-Silva, 2024)):

$\displaystyle\forall(j\in{\mathcal{F}}).$
$\displaystyle\left([\mathsf{Relevant}(j)\land(\operatorname*{\mathsf{Sc}}(j)=0)]\lor\right.$
$\displaystyle~{}\left.[\mathsf{Irrelevant}(j)\land(\operatorname*{\mathsf{Sc}}(j)\not=0)]\right)$

As a result, given the observed experimental results, we make the following
conjecture:

######  Conjecture 1.

For the characteristic function $\upsilon_{s}$, issue I8 is not observed.

In the case that the above conjecture holds, another open question is whether
the use of $\upsilon_{s}$ also prevents more flexible variants of issue I8
from being observed.

##  8 Conclusions

Recent work demonstrated the existence of classifiers for which the exact SHAP
scores do not respect relative feature importance. This paper presents
additional evidence, and argues that similar problems occur for SHAP scores
defined in terms of baselines (Janzing et al., 2020; Sundararajan & Najmi,
2020). More importantly, the paper argues that the identified issues with SHAP
scores result from the characteristic functions used in earlier work. As a
result, the paper devises several properties which characteristic functions
must respect in order to compute SHAP scores that do not exhibit those issues.
Complexity-wise, the paper argues that the proposed characteristic functions
are as hard to compute as the characteristic functions used in earlier works
studying the complexity of SHAP scores (Van den Broeck et al., 2021; Arenas et
al., 2021; Van den Broeck et al., 2022; Arenas et al., 2023), or harder.
Finally, the paper proposes simple modifications to the tool SHAP (Lundberg &
Lee, 2017), thereby obtaining SHAP scores that respect some of the proposed
properties.

##  9 Impact Statements

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Afchar et al. (2021) Afchar, D., Guigue, V., and Hennequin, R.  Towards rigorous interpretations: a formalisation of feature attribution.  In _ICML_ , pp. 76–86, 2021.
  * Arenas et al. (2021) Arenas, M., Barceló, P., Bertossi, L. E., and Monet, M.  The tractability of SHAP-score-based explanations for classification over deterministic and decomposable boolean circuits.  In _AAAI_ , pp. 6670–6678, 2021.
  * Arenas et al. (2023) Arenas, M., Barceló, P., Bertossi, L. E., and Monet, M.  On the complexity of SHAP-score-based explanations: Tractability via knowledge compilation and non-approximability results.  _J. Mach. Learn. Res._ , 24:63:1–63:58, 2023.  URL http://jmlr.org/papers/v24/21-0389.html.
  * Biradar et al. (2023) Biradar, G., Izza, Y., Lobo, E., Viswanathan, V., and Zick, Y.  Axiomatic aggregations of abductive explanations.  _CoRR_ , abs/2310.03131, 2023.  doi: 10.48550/arXiv.2310.03131.  URL https://doi.org/10.48550/arXiv.2310.03131.
  * Campbell et al. (2022) Campbell, T. W., Roder, H., Georgantas III, R. W., and Roder, J.  Exact Shapley values for local and model-true explanations of decision tree ensembles.  _Machine Learning with Applications_ , 9:100345, 2022.
  * Darwiche (2023) Darwiche, A.  Logic for explainable AI.  In _LICS_ , pp. 1–11, 2023.
  * Darwiche & Marquis (2002) Darwiche, A. and Marquis, P.  A knowledge compilation map.  _J. Artif. Intell. Res._ , 17:229–264, 2002.  doi: 10.1613/jair.989.  URL https://doi.org/10.1613/jair.989.
  * Dubey (1975) Dubey, P.  On the uniqueness of the shapley value.  _International Journal of Game Theory_ , 4:131–139, 1975\.
  * Fryer et al. (2021) Fryer, D. V., Strümke, I., and Nguyen, H. D.  Shapley values for feature selection: The good, the bad, and the axioms.  _IEEE Access_ , 9:144352–144360, 2021.
  * Huang & Marques-Silva (2023) Huang, X. and Marques-Silva, J.  The inadequacy of shapley values for explainability.  _CoRR_ , abs/2302.08160, 2023.  doi: 10.48550/arXiv.2302.08160.  URL https://doi.org/10.48550/arXiv.2302.08160.
  * Huang & Marques-Silva (2024) Huang, X. and Marques-Silva, J.  On the failings of shapley values for explainability.  _International Journal of Approximate Reasoning_ , pp. 109112, 2024\.  ISSN 0888-613X.  doi: https://doi.org/10.1016/j.ijar.2023.109112.  URL https://www.sciencedirect.com/science/article/pii/S0888613X23002438.
  * Huang et al. (2023) Huang, X., Cooper, M. C., Morgado, A., Planes, J., and Marques-Silva, J.  Feature necessity & relevancy in ML classifier explanations.  In _TACAS_ , pp. 167–186, 2023.
  * Ignatiev et al. (2020) Ignatiev, A., Narodytska, N., Asher, N., and Marques-Silva, J.  From contrastive to abductive explanations and back again.  In _AIxIA_ , pp. 335–355, 2020.
  * Janzing et al. (2020) Janzing, D., Minorics, L., and Blöbaum, P.  Feature relevance quantification in explainable AI: A causal problem.  In _AISTATS_ , pp. 2907–2916, 2020.
  * Kumar et al. (2021) Kumar, I., Scheidegger, C., Venkatasubramanian, S., and Friedler, S. A.  Shapley residuals: Quantifying the limits of the Shapley value for explanations.  In _NeurIPS_ , pp. 26598–26608, 2021.
  * Kumar et al. (2020) Kumar, I. E., Venkatasubramanian, S., Scheidegger, C., and Friedler, S. A.  Problems with Shapley-value-based explanations as feature importance measures.  In _ICML_ , pp. 5491–5500, 2020.
  * Lundberg & Lee (2017) Lundberg, S. M. and Lee, S.  A unified approach to interpreting model predictions.  In _NeurIPS_ , pp. 4765–4774, 2017.
  * Marques-Silva (2022) Marques-Silva, J.  Logic-based explainability in machine learning.  In _Reasoning Web_ , pp. 24–104, 2022.
  * Merrick & Taly (2020) Merrick, L. and Taly, A.  The explanation game: Explaining machine learning models using Shapley values.  In _CDMAKE_ , pp. 17–38, 2020.
  * Mothilal et al. (2021) Mothilal, R. K., Mahajan, D., Tan, C., and Sharma, A.  Towards unifying feature attribution and counterfactual explanations: Different means to the same end.  In _AIES_ , pp. 652–663, 2021.
  * Roth (1988) Roth, A. E.  _The Shapley value: essays in honor of Lloyd S. Shapley_.  Cambridge University Press, 1988.
  * Shapley (1953) Shapley, L. S.  A value for $n$-person games.  _Contributions to the Theory of Games_ , 2(28):307–317, 1953.
  * Strumbelj & Kononenko (2010) Strumbelj, E. and Kononenko, I.  An efficient explanation of individual classifications using game theory.  _J. Mach. Learn. Res._ , 11:1–18, 2010.  URL https://dl.acm.org/doi/10.5555/1756006.1756007.
  * Strumbelj & Kononenko (2014) Strumbelj, E. and Kononenko, I.  Explaining prediction models and individual predictions with feature contributions.  _Knowl. Inf. Syst._ , 41(3):647–665, 2014.  URL https://doi.org/10.1007/s10115-013-0679-x.
  * Sundararajan & Najmi (2020) Sundararajan, M. and Najmi, A.  The many shapley values for model explanation.  In _ICML_ , pp. 9269–9278, 2020.
  * Valiant (1979) Valiant, L. G.  The complexity of enumeration and reliability problems.  _SIAM J. Comput._ , 8(3):410–421, 1979.  doi: 10.1137/0208032.  URL https://doi.org/10.1137/0208032.
  * Van den Broeck et al. (2021) Van den Broeck, G., Lykov, A., Schleich, M., and Suciu, D.  On the tractability of SHAP explanations.  In _AAAI_ , pp. 6505–6513, 2021.
  * Van den Broeck et al. (2022) Van den Broeck, G., Lykov, A., Schleich, M., and Suciu, D.  On the tractability of SHAP explanations.  _J. Artif. Intell. Res._ , 74:851–886, 2022.  doi: 10.1613/jair.1.13283.  URL https://doi.org/10.1613/jair.1.13283.
  * Wäldchen et al. (2021) Wäldchen, S., MacDonald, J., Hauch, S., and Kutyniok, G.  The computational complexity of understanding binary classifier decisions.  _J. Artif. Intell. Res._ , 70:351–387, 2021.  doi: 10.1613/JAIR.1.12359.  URL https://doi.org/10.1613/jair.1.12359.
  * Watson et al. (2021) Watson, D. S., Gultchin, L., Taly, A., and Floridi, L.  Local explanations via necessity and sufficiency: unifying theory and practice.  In _UAI_ , volume 161, pp. 1382–1392, 2021.
  * Yan & Procaccia (2021) Yan, T. and Procaccia, A. D.  If you like Shapley then you’ll love the core.  In _AAAI_ , pp. 5751–5759, 2021.
  * Young (1985) Young, H. P.  Monotonic solutions of cooperative games.  _International Journal of Game Theory_ , 14:65–72, 1985\.
  * Young et al. (2019) Young, K., Booth, G., Simpson, B., Dutton, R., and Shrapnel, S.  Deep neural network or dermatologist?  _CoRR_ , abs/1908.06612, 2019.  URL http://arxiv.org/abs/1908.06612.
  * Yu et al. (2023a) Yu, J., Farr, G., Ignatiev, A., and Stuckey, P. J.  Anytime approximate formal feature attribution.  _CoRR_ , abs/2312.06973, 2023a.  doi: 10.48550/ARXIV.2312.06973.  URL https://doi.org/10.48550/arXiv.2312.06973.
  * Yu et al. (2023b) Yu, J., Ignatiev, A., and Stuckey, P. J.  On formal feature attribution and its approximation.  _CoRR_ , abs/2307.03380, 2023b.  doi: 10.48550/arXiv.2307.03380.  URL https://doi.org/10.48550/arXiv.2307.03380.

##  Appendix A Proofs

See 1

###### Proof.

If a characteristic function is strongly class independent, it suffices to
restrict the choices of $\mu$ to surjective functions to make it weakly class
independent. ∎

See 2

###### Proof.

(Sketch) We only consider $\upsilon_{a}$. (The proof for $\upsilon_{c}$ and
$\upsilon_{n}$ follows from Proposition 4.)
It is plain that $\Delta_{a}(i,{\mathcal{S}})\in\\{-1,0,1\\}$, given the
possible values that $\upsilon_{a}$ can take. In fact, it is the case that
$\Delta_{a}(i,{\mathcal{S}})\in\\{0,1\\}$. If a set
${\mathcal{S}}\subseteq{\mathcal{F}}$ is a WAXp, then a proper superset is
also a WAXp; hence it is never the case that $\Delta_{a}(i,{\mathcal{S}})=-1$.
Since every $\Delta_{a}(i,{\mathcal{S}})\geq 0$, then $\mathsf{Sc}_{a}(i)\geq
0$. ∎

See 4

###### Proof.

We consider each case separately:

  1. 1.

By definition, it is plain that
$\upsilon_{a}({\mathcal{S}})+\upsilon_{n}({\mathcal{S}})=1$, for any
${\mathcal{S}}\subseteq{\mathcal{F}}$, because it must be the case that either
$\upsilon_{s}({\mathcal{S}})=1$ or $\upsilon_{s}({\mathcal{S}})<1$, but not
both. Given the values that $\upsilon_{a}({\mathcal{S}})$ can take, it is also
plain that
$\Delta_{a}(i,{\mathcal{S}})\in\\{\scalebox{0.7125}[1.0]{$-$}1,0,1\\}$.
Moreover, if $\Delta_{a}(i,{\mathcal{S}})=\scalebox{0.7125}[1.0]{$-$}1$, then
$\Delta_{n}(i,{\mathcal{S}})=1$. If $\Delta_{a}(i,{\mathcal{S}})=1$, then
$\Delta_{n}(i,{\mathcal{S}})=\scalebox{0.7125}[1.0]{$-$}1$. Also, if
$\Delta_{a}(i,{\mathcal{S}})=0$, then $\Delta_{n}(i,{\mathcal{S}})=0$. Thus,
for any $i\in{\mathcal{F}}$ and ${\mathcal{S}}\subseteq{\mathcal{F}}$,
$\Delta_{n}(i,{\mathcal{S}})=\scalebox{0.7125}[1.0]{$-$}\Delta_{a}(i,{\mathcal{S}})$.
Hence, the result follows.

  2. 2.

Since
$\forall({\mathcal{S}}\subseteq{\mathcal{F}}).\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})\leftrightarrow\neg\mathsf{WAXp}({\mathcal{S}}$,
by definition, then we have
$\forall(i\in{\mathcal{F}}),\forall({\mathcal{S}}\subseteq({\mathcal{F}}\setminus\\{i\\}))$,

$\displaystyle\Delta_{a}(i,{\mathcal{S}})=1$ $\displaystyle\Leftrightarrow$
$\displaystyle\neg\mathsf{WAXp}({\mathcal{S}})\land\mathsf{WAXp}({\mathcal{S}}\cup\\{i\\})$
$\displaystyle\Leftrightarrow$
$\displaystyle\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})\land\neg\mathsf{WAXp}({\mathcal{F}}\setminus({\mathcal{S}}\cup\\{i\\}))$
$\displaystyle\Leftrightarrow$
$\displaystyle\mathsf{WCXp}({\mathcal{F}}\setminus{\mathcal{S}})\land\neg\mathsf{WAXp}(({\mathcal{F}}\setminus\\{i\\})\setminus{\mathcal{S}})$
$\displaystyle\Leftrightarrow$
$\displaystyle\Delta_{c}(i,({\mathcal{F}}\setminus\\{i\\})\setminus{\mathcal{S}})=1$

Now, let
$\Phi(i):=\\{{\mathcal{S}}\subseteq({\mathcal{F}}\setminus\\{i\\})\,|\,\Delta_{a}(i,{\mathcal{S}})=1\\}$.
Then, by construction,
$\mathsf{Sc}_{a}(i)=\sum_{{\mathcal{S}}\in\Phi(i)}\varsigma(|{\mathcal{S}}|)$
(because $\Delta_{a}=0$ otherwise) and, by the equivalence above,
$\mathsf{Sc}_{c}(i)=\sum_{{\mathcal{S}}\in\Phi(i)}\varsigma(|{\mathcal{F}}\setminus\\{i\\})\setminus{\mathcal{S}}|)$.
However, it is immediate to prove that
$\varsigma(|{\mathcal{S}}|)=\varsigma(|{\mathcal{F}}\setminus\\{i\\})\setminus{\mathcal{S}}|)$,
and so the two sums are also equal. This proves the result. ∎

See 5

###### Proof.

For a characteristic function to respect strong class independence, the SHAP
scores must not change if the classes are mapped using some function $\mu$. By
hypothesis, for any point $\mathbf{x}\in\mathbb{F}$, the resulting classifier
will predict $\mu(c)$ iff the original classifier predicts $c$. This means the
resulting similarity functions are the same for the two classifiers, and so
the SHAP scores $\mathsf{Sc}_{t}$, $t\in\\{s,a,c,n\\}$, remain unchanged. ∎

See 6

###### Proof.

First, we consider $\upsilon_{a}$.
Let $i\in{\mathcal{F}}$ be an irrelevant feature.
It is plain that $\Delta_{a}(i,{\mathcal{S}})\in\\{-1,0,1\\}$, given the
possible values that $\upsilon_{a}$ can take. However, as argued above,
$\Delta_{a}(i,{\mathcal{S}})\in\\{0,1\\}$, since if a set
${\mathcal{S}}\subseteq{\mathcal{F}}$ is a WAXp, then a proper superset is
also a WAXp; hence it is never the case that $\Delta_{a}(i,{\mathcal{S}})=-1$.
We are interested in the sets
${\mathcal{S}}\subseteq({\mathcal{F}}\setminus\\{i\\})$ for which
$\Delta_{a}(i,{\mathcal{S}})=1$, since these are the only ones that contribute
to making $\mathsf{Sc}_{a}(i)\not=0$. For $\Delta_{a}(i,{\mathcal{S}})=1$, it
must be the case that $\upsilon_{a}({\mathcal{S}})=0$ and
$\upsilon_{a}({\mathcal{S}}\cup\\{i\\})=1$. However, this would imply that $i$
would be included in some AXp (Huang et al., 2023). But $i$ is irrelevant, and
so it is not included in any AXp. Hence, there exists no set
${\mathcal{S}}\subseteq({\mathcal{F}}\setminus\\{i\\})$ such that
$\Delta_{a}(i,{\mathcal{S}})=1$, and so $\mathsf{Sc}_{a}(i)=0$.
Let $\mathsf{Sc}_{a}(i)=0$.
An analysis similar to the above one allows concluding that there exist no
sets ${\mathcal{S}}$ such that $\Delta_{a}(i,{\mathcal{S}})=1$. Hence, it is
never the case that $\upsilon_{a}({\mathcal{S}})=0$ and
$\upsilon_{a}({\mathcal{S}}\cup\\{i\\})=1$. Thus, $i$ is not included in any
AXp, and so it is irrelevant.
For $\upsilon_{c}$ and $\upsilon_{n}$, it suffices to invoke Proposition 4;
hence, the features for which $\mathsf{Sc}_{a}(i)=0$ are exactly the ones for
which $\mathsf{Sc}_{c}(i)=0$ and $\mathsf{Sc}_{n}(i)=0$.
This concludes the proof that $\mathsf{Sc}_{t}$, with $t\in\\{a,c,n\\}$, does
not mislead. ∎

See 8

###### Proof.

From (Van den Broeck et al., 2021, 2022), it is known that computing SHAP
scores is polynomially equivalent to computing the expected value. In the
boolean case, and so in the case of $\upsilon_{s}$, this is polynomially
equivalent to model counting. Furthermore, model counting for DNF and CNF
formulas is #P-complete (Valiant, 1979). Thus, computing the SHAP scores using
$\upsilon_{s}$ is #P-hard. ∎

See 9

###### Proof.

We reduce the problem of feature relevancy to the problem of computing the
SHAP scores $\mathsf{Sc}_{t}$, with $t\in\\{a,c,n\\}$. Since feature relevancy
is NP-complete for d-DNNF circuits (Huang et al., 2023), this proves that
computing the SHAP scores $\mathsf{Sc}_{t}$, with $t\in\\{a,c,n\\}$ is NP-
hard.
Given an explanation problem we can decide feature membership as follows. We
compute the SHAP score for each feature $i\in{\mathcal{F}}$. Moreover, since
$\upsilon_{t}$, $t\in\\{a,c,n\\}$ are comopliant with feature (ir)relevancy,
then $\mathsf{Sc}_{t}(i)=0$ iff feature $i$ is irrelevant. Hence, if we could
compute the SHAP scores in polynomial-time, then we could decide feature
relevancy in polynomial-time, and so computing the SHAP-scores for d-DNNFs is
NP-hard.
Now, since DDBCs generalize d-DNNFs (Arenas et al., 2023), then computing the
SHAP-scores for DDBCs is also NP-hard. ∎

##  Appendix B Limitations of SHAP Scores Based on Baselines

We focus on BShap (Sundararajan & Najmi, 2020); similar analyzes could be made
for other baselines (Janzing et al., 2020; Sundararajan & Najmi, 2020).

Throughout this section, the baseline is a point $\mathbf{w}\in\mathbb{F}$.
Furthermore, for each ${\mathcal{S}}\subseteq{\mathcal{F}}$, let
$\mathbf{x}^{{\mathcal{S}}}_{b}$ be such that
$x^{{\mathcal{S}}}_{b,i}=\textnormal{ITE}(i\in{\mathcal{S}},v_{i},w_{i})$.

Given $\mathbf{w}\in\mathbb{F}$, the BShap characteristic function
$\upsilon_{b}$ is defined by
$\upsilon_{b}({\mathcal{S}})=\kappa(\mathbf{x}^{{\mathcal{S}}}_{b})$, for
${\mathcal{S}}\subseteq{\mathcal{F}}$.

### Remarks about baselines.

Analysis of the definition of BShap (Sundararajan & Najmi, 2020) allows
proving the following results.

######  Proposition B.1.

The following holds:

  1. 1.

BShap is only well-defined if all the domains are boolean, i.e.
$\mathbb{F}=\\{0,1\\}^{m}$.

  2. 2.

BShap is only well-defined when $\mathbf{w}=\neg\mathbf{v}$.

###### Proof.

By contradiction, let us consider $i\in{\mathcal{F}}$, such that either
$|\mathbb{D}_{i}|>2$ or $w_{i}=v_{i}$. Then there exists a point
$\mathbf{z}\in\mathbb{F}$ such that $z_{i}\not\in\\{v_{i},w_{i}\\}$. By
construction, for each ${\mathcal{S}}\subseteq{\mathcal{F}}$,
$\mathbf{x}^{{\mathcal{S}}}_{b}$ is different from $\mathbf{z}$. Thus,
$\upsilon_{b}$ and so $\mathsf{Sc}_{b}$ do not depend on $\kappa(\mathbf{z})$.
Therefore, we can use the value of $\kappa(\mathbf{z})$ to change the AXps
(and CXps) without modifying the BShap scores. As there are at least
$2^{(|{\mathcal{F}}|-1)}$ such points $\mathbf{z}$, it is plain that
constructing counterexample is simple. ∎

### BShap also misleads.

The following notation is used ${\mathcal{S}}\subseteq{\mathcal{F}}$, let
$\mathbf{v}^{{\mathcal{S}}}$ be defined by
$\textnormal{ITE}(i\in{\mathcal{S}},v_{i},\neg{v_{i}})$, with
$i\in{\mathcal{F}}$.

For ${\mathcal{S}}\subseteq{\mathcal{F}}$, then
$\upsilon_{b}({\mathcal{S}})=\kappa(\mathbf{v}^{{\mathcal{S}}})$.

######  Proposition B.2.

$\upsilon_{b}$ misleads.

###### Proof.

Let $\kappa(x_{1},x_{2})=\textnormal{ITE}(x_{1}=1,1,2x_{2})$, and instance
$(\mathbf{v},c)=((1,1),1)$.
It is plain that feature 1 influences both selecting the prediction 1 and
changing the prediction to some other value. In contrast, feature 2 has not
influence in either setting or changing the prediction of class 1.
It is also plain that the set of AXps is $\\{\\{1\\}\\}$, and also that
$\kappa(x_{1},x_{2})=1$ iff $x_{1}=1$.
However, if we compute $\mathsf{Sc}_{b}$, we get $\mathsf{Sc}_{b}(1)=0$ and
$\mathsf{Sc}_{b}(2)=1$, which is of course misleading.
To confirm the SHAP scores, we proceed as follows.
$\upsilon_{b}(\emptyset)=\kappa(0,0)=0$,
$\upsilon_{b}(\\{1\\})=\kappa(1,0)=1$, $\upsilon_{b}(\\{2\\})=\kappa(0,1)=2$,
and $\upsilon_{b}(\\{1,2\\})=\kappa(1,1)=1$.
Thus,
$\Delta_{b}(1,\emptyset)=\upsilon_{b}(\\{1\\})-\upsilon_{b}(\emptyset)=1$,
$\Delta_{b}(1,\\{2\\})=\upsilon_{b}(\\{1,2\\})-\upsilon_{b}(\\{2\\})=-1$,
$\Delta_{b}(2,\emptyset)=\upsilon_{b}(\\{2\\})-\upsilon_{b}(\emptyset)=2$,
$\Delta_{b}(2,\\{1\\})=\upsilon_{b}(\\{1,2\\})-\upsilon_{b}(\\{2\\})=0$.
And finally,
$\mathsf{Sc}_{b}(1)=\nicefrac{{(\Delta_{b}(1,\\{2\\})+\Delta_{b}(1,\emptyset))}}{{2}}=0$,
$\mathsf{Sc}_{b}(2)=\nicefrac{{(\Delta_{b}(2,\\{1\\})+\Delta_{b}(2,\emptyset))}}{{2}}=1$.
∎