# Shaping Up SHAP: Enhancing Stability through Layer-Wise Neighbor Selection

Gwladys Kelodjou1, Laurence Rozé2, Véronique Masson1, Luis Galárraga1,
Romaric Gaudel1, Maurice Tchuente3, Alexandre Termier1

###### Abstract

Machine learning techniques, such as deep learning and ensemble methods, are
widely used in various domains due to their ability to handle complex real-
world tasks. However, their black-box nature has raised multiple concerns
about the fairness, trustworthiness, and transparency of computer-assisted
decision-making. This has led to the emergence of local post-hoc
explainability methods, which offer explanations for individual decisions made
by black-box algorithms. Among these methods, Kernel SHAP is widely used due
to its model-agnostic nature and its well-founded theoretical framework.
Despite these strengths, Kernel SHAP suffers from high instability: different
executions of the method with the same inputs can lead to significantly
different explanations, which diminishes the utility of post-hoc
explainability. The contribution of this paper is two-fold. On the one hand,
we show that Kernel SHAP’s instability is caused by its stochastic neighbor
selection procedure, which we adapt to achieve full stability without
compromising explanation fidelity. On the other hand, we show that by
restricting the neighbors generation to perturbations of size 1 – which we
call the coalitions of Layer 1 – we obtain a novel feature-attribution method
that is fully stable, efficient to compute, and still meaningful.

##  1 INTRODUCTION AND RELATED WORK

Modern machine learning techniques, including deep learning and ensemble
methods, have become invaluable tools in diverse fields such as healthcare and
banking due to their power to handle complex real-world tasks. Yet, their
“black-box” nature has raised concerns about their fairness and
trustworthiness, which in turns has motivated the interest in explainability.
Local post-hoc explainability is concerned with providing a posteriori
explanations for the decisions of black-box algorithms on single instances.
Notable approaches in this line are LIME (Ribeiro, Singh, and Guestrin 2016),
SHAP (Lundberg and Lee 2017), and Grad-CAM (Selvaraju et al. 2017), which
compute explanations that take the form of feature attribution scores. A
feature attribution explanation assigns a contribution score to each of the
model’s input features. This tells users how (positively or negatively) and
how much an input feature influenced the black box’s answer on a target
instance.

Among the explainability methods based on feature attribution, SHAP is
particularly popular because its attribution scores, the SHAP values, are
inspired by the well-founded Shapley values (Shapley et al. 1953) from
coalitional game theory. In practice, and due to the exponential complexity of
the exact calculation, SHAP implementations typically compute approximations
of the theoretical SHAP values. For instance, the widely used Kernel SHAP –
SHAP’s model-agnostic flavor – estimates the attribution scores by solving a
linear regression on a random sample of neighbor instances, constructed by
perturbing the target instance.

While local post-hoc explanations based on perturbations are widely used to
explain black-box models (LIME also falls in this category), this class of
methods are known to suffer from instability. (Zhou, Hooker, and Wang 2021)
argue that a key property of any explanation technique is its stability or
reproducibility, defined as the method’s ability to deliver the same results
under the same conditions across multiple executions. They therefore propose a
framework to determine the number of perturbation points required to ensure
stable explanations with LIME. (Visani et al. 2022) introduced two metrics to
quantify the stability of LIME explanations: the Variable Stability Index,
which measures the variation of the explanatory features, and the Coefficient
Stability Index, which captures the variation of the coefficients associated
to the explanatory features. (Visani, Bagli, and Chesani 2020) offer a
framework that allows users to choose the level of stability and fidelity for
LIME explanations.

We highlight the difference between stability and the criterion called
robustness introduced by (Alvarez-Melis and Jaakkola 2018). An explanation
method is robust if similar, but not identical, inputs entail similar
explanations. (Alvarez-Melis and Jaakkola 2018) quantify robustness as the
maximum change in explanations obtained when small perturbations are applied
to a given instance. They demonstrate that state-of-the-art methods (including
LIME and SHAP) do not satisfy this robustness criterion. Stability and
robustness are different concepts, however stability is a necessary condition
for robustness.

While stability has been well studied for LIME, and stable improvements of
LIME have been proposed, this is not the case for SHAP. In this paper, we show
that the Kernel SHAP’s estimator also suffers from stability issues, which
stems from its stochastic neighbor selection. Given the popularity of Kernel
SHAP, such instability diminishes the utility of SHAP, not to mention its
potential impact on the trust in post-hoc explainability approaches. We list
the contributions of this paper in the following.

  * •

Our first contribution is an alternative procedure for choosing the neighbors
of a target instance in Kernel SHAP so that stability is improved.

  * •

Our second contribution is a thorough experimental study of the stability but
also the fidelity of Kernel SHAP under different neighbor selection
procedures. It shows that our proposed neighbor selection approach achieves
stability without hurting explanation fidelity.

  * •

Our third contribution is a theoretical study of a novel approximation of the
SHAP values, which relies on neighbors generated from simple perturbations –
called the _layer-1 neighbors_. We demonstrate that the obtained scores meet
the main properties of attribution methods based on coalitional game theory.
This means that our approach is an attribution method in itself, which
provides scores that are stable and faster to compute than the SHAP values
while retaining their good properties.

The remainder of this paper is organized as follows: Section 2 provides an
overview of SHAP and Kernel SHAP. Section 3 brings to light the instability
issues of Kernel SHAP. In Section 4, we present our approach for improving the
stability of Kernel SHAP. Section 5 provides an evaluation of our proposed
method. Subsequently, in Section 6, we conduct a theoretical analysis on the
properties of our attribution method based on layer-1 neighbors. Building on
this analysis, the latter part of Section 6 presents a new round of
experiments comparing attributions of the exact-SHAP values with those of
layer-1. Section 7 concludes the paper, summarizing our findings and
suggesting future research directions.

##  2 BACKGROUND

In this section, we review the definitions of Shapley and SHAP values.

### Shapley Values

The Shapley value is a mathematical concept from game theory that was
introduced by (Shapley et al. 1953) first to allocate performance credit
across coalition game players. It is used to evaluate the fair share of a
player in a cooperative game (Ghorbani and Zou 2019). Suppose that we have a
cooperative game with $M$ players numbered from $1$ to $M$, and let $N$ denote
the set of players: $N=\\{1,2,\cdots,M\\}$. A coalitional game is a tuple
$\langle N,v\rangle$ where $v:2^{N}\rightarrow\mathbb{R}$ is a function such
that $v(\emptyset)=0$ (Strumbelj and Kononenko 2010). Subsets of $N$ are
coalitions and $v$ returns a value for each coalition $S\,(S\subseteq N)$. So,
for each coalition $S$, $v(S)$ represents the reward that arises when the
players in the subset $S$ participate in the game. $v(S)$ can be seen as the
worth of coalition $S$. The set $N$ is also a coalition, and we call it the
grand coalition. Thus $v(N)$ is the total payoff and the goal is to split it
among the players in a fair way. Fair allocations must be based on each
player’s contribution to the profit. The marginal contribution of a player $j$
to a coalition $S$ is defined as the additional value generated by including
$j$ in the coalition: $v(S\cup\\{j\\})-v(S)$. However, the marginal
contribution of a player depends on the composition of the coalition. To
determine the player’s overall contribution, it is necessary to consider all
possible subsets of players. Then, the Shapley value $\phi_{j}(v)$ of player
$j$ for a game $v$ is calculated as a weighted average of marginal
contributions to the coalitions to which that player belongs (Ruiz,
Valenciano, and Zarzuelo 1998):

$\phi_{j}(v)=\sum_{S\subseteq
N\backslash\\{j\\}}\frac{|S|!(|N|-|S|-1)!}{|N|!}[v(S\cup\\{j\\})-v(S)]$ (1)

(Shapley et al. 1953) proved that this value is the unique allocation of the
grand coalition which satisfies the following axioms: Efficiency, Symmetry,
Dummy and Additivity.

In recent years, the concept of Shapley value has become a popular technique
for interpreting machine learning models (Song, Nelson, and Staum 2016;
Ghorbani and Zou 2019; Lundberg and Lee 2017). In this setting, the players
are the features used by the model and the gain is the model’s prediction. The
aim is therefore to assign each feature an importance value that represents
its effect on the model’s prediction. Let $f$ be the predictive model to be
explained, and $N=\\{1,2,\cdots,M\\}$ be a set representing $M$ input
features. $f$ maps an input feature vector $x=[x_{1},x_{2},\cdots,x_{M}]$ to
an output $f(x)$ where $f(x)\in\mathbb{R}$ in regression and
$f(x)\in[0,1]^{|C|}$ in classification, where $C$ is a finite set of labels.
Shapley’s equation thus becomes:

$\displaystyle\phi_{j}(f,x)=\sum_{S\subseteq
N\backslash\\{j\\}}\frac{|S|!(|N|-|S|-1)!}{|N|!}[f_{S\cup\\{j\\}}(x_{S\cup\\{j\\}})-f_{S}(x_{S})]$

(2)

where $x_{S}$ represents the sub-vector of $x$ restricted to the feature
subset $S$, and $f_{S}(x_{S})$ is the model output restricted to the feature
subset $S$. To compute Shapley values, we need to define how to calculate
$f_{S}(x_{S})$ because most models cannot handle arbitrary patterns of missing
input values. There are several approaches to do so. Here we will look at how
SHAP (Lundberg and Lee 2017) works.

### SHAP values

SHAP values (Lundberg and Lee 2017) are defined as the coefficients of an
additive surrogate explanation model which is a linear function of binary
features:

$g(z^{\prime})=\phi_{0}+\sum_{i=1}^{M}\phi_{i}z^{\prime}_{i}$ (3)

Here, $z^{\prime}\in\\{0,1\\}^{M}$ is a binary vector representing a coalition
of features, where $z^{\prime}_{i}=1$ when the $i$-th feature is observed and
$z^{\prime}_{i}=0$ otherwise. The values $\phi_{i}\in\mathbb{R}$ correspond to
the feature attribution values.

For example, a coalition $z^{\prime}=[1,0,0,1]$ simply represents the
coalition $S=\\{x_{1},x_{4}\\}$ if we assume that $M=4$. Equation (4) gives
the Shapley’s values, where $|z^{\prime}|$ is the number of $1$s in vector
$z^{\prime}$, and $z^{\prime}\setminus i$ is equals $z^{\prime}$ with
$z^{\prime}_{i}=0$.

$\phi_{i}(f,x)=\sum_{z^{\prime}\in\\{0,1\\}^{M}}\frac{|z^{\prime}|!(M-|z^{\prime}|-1)!}{M!}[f_{x}(z^{\prime})-f_{x}(z^{\prime}\setminus
i)]$ (4)

In Equation (4), $f_{x}(z^{\prime})=E[f(z)\,|\,z_{S}=x_{S}]$ with $S=\\{i\in
N\,|\,z^{\prime}_{i}=1$} and $z_{S}$ the sub-vector of $x$ restricted to the
feature subset $S$.

SHAP values satisfy three desirable properties: local accuracy, missingness
and consistency (Lundberg and Lee 2017), which are equivalent to those of the
Shapley value (regarding local accuracy and consistency). These properties
provide a strong mathematical foundation for the SHAP values. The exact
computation of the SHAP values is exponential in the number of features, so
numerous approaches have been proposed to approximate them. We are interested
here in Kernel SHAP, which is the main model-agnostic variant of SHAP.

#### Kernel SHAP.

It is a linear-regression-based approximation of the SHAP values. The idea is
to find a surrogate function $g$ like in Equation (3) by solving a weighted
least squares problem with weighting kernel $\pi_{x}$:

$\textit{arg
min}_{g}\sum_{z^{\prime}\in\\{0,1\\}^{M}}\pi_{x}(z^{\prime})(g(z^{\prime})-f_{x}(z^{\prime}))^{2}$
(5)
$\pi_{x}(z^{\prime})=\frac{M-1}{C_{M}^{|z^{\prime}|}|z^{\prime}|(M-|z^{\prime}|)}$
(6)

where $g$ in Equation (5) is defined as in Equation (3). We note that the
values $\pi_{x}(z^{\prime})=\infty$ when $|z^{\prime}|\in\\{0,M\\}$. This
enforces constraints (i) $\phi_{0}=f_{x}(\emptyset)=E[f(x)]$ for the intercept
of $g$ and (ii) $\sum_{i=1}^{M}\phi_{i}=f(x)-f_{x}(\emptyset)$ for the sum of
the coefficients – the latter being the local accuracy constraint. To
approximate the SHAP values, Kernel SHAP samples a subset of coalitions and
then uses the sample to solve Equation (5). The size of the sample used to
learn Kernel SHAP is called the budget. Given a budget, the sampling is guided
by the coalition weights ($\pi_{x}$, also called Shapley Kernel). The weight
assigned to each coalition is determined by the number of features involved in
that coalition (denoted as $|z^{\prime}|$ and representing the number of $1s$
in $z^{\prime}$). From now we refer to Kernel SHAP simply as SHAP, and use the
terms neighbor and coalition interchangeably.

Layer $i$ is defined as the set of coalitions having $i$ features present or
$i$ features absent (or $M-i$ features present). All the coalitions within the
same layer have the same weight. Table 1 is an example of some coalitions and
their corresponding layers for $M=4$. As $i$ approaches
$\lfloor\frac{M}{2}\rfloor$, the weight assigned to the coalitions within that
layer decreases. Consequently, the sampling procedure progresses
incrementally, starting from lower-level layers and gradually moving towards
higher-level layers. Specifically, this involves generating first the
coalitions with $1$ or $M-1$ features included. If the budget is not
exhausted, then coalitions with $2$ or $M-2$ features included are generated,
and so on.

Layer |  | Coalition
---|---|---
$1$ |  | $1\quad 0\quad 0\quad 0$
$1$ |  | $0\quad 1\quad 1\quad 1$
$2$ |  | $1\quad 1\quad 0\quad 0$
$2$ |  | $0\quad 0\quad 1\quad 1$
Table 1: Examples of coalitions and their corresponding layers for $M=4$. The
first coalition is in Layer 1, as it contains only one feature. The second
coalition is still in Layer 1 as it lacks only one feature. In the last two
cases, two features are present or absent, hence the instances belong to Layer
2.

Based on the allocated budget, a layer may be either fully enumerated or not.
A layer is considered complete if all possible coalitions within that layer
have been enumerated. Conversely, if there are coalitions belonging to the
layer that have not been generated, we will refer to it as an incomplete
layer. When focusing on a specific layer, there are two options: either fully
explore that layer and then move on to the next layer, or switch to random
sampling mode on all the other unexplored layers. For a layer to be fully
explored, two conditions must be met:

  1. 1.

The remaining budget must be sufficient to generate all the instances of that
layer.

  2. 2.

The weight of the layer (sum of the weights of all instances within the layer)
must be significant enough to justify its exploration. Specifically, the
weighted probability of drawing an instance of that layer must be greater than
the probability of randomly selecting any instance.

The third column in Table 2 provides an example of SHAP’s layer-wise
exploration and illustrates how SHAP switches to random selection after layer
2, despite having enough budget to fully explore layer 3. The fourth column of
the table will be explained in Section 4.

Layer | Size | SHAP |  ST-SHAP (Our method)
---|---|---|---
$1$ | $30$ | $30$ |  $30$
$2$ | $210$ | $210$ |  $210$
$3$ | $910$ | $960$ |  $910$
$4$ | $2730$ |  $50$
$5$ | $6006$ |  $0$
$6$ | $10010$ |
$7$ | $12870$ |

Table 2: SHAP and ST-SHAP (our method) neighbor selection process for $M=15$
and budget = $1200$. The column “Size” is the number of coalitions in the
layer, whereas the columns “SHAP” and “ST-SHAP” denote the number of
coalitions from a layer materialized by the two different generation
processes.

Finally, similarly to LIME, SHAP offers the option to control the complexity
of the explanation. This can be achieved by specifying the number of features
to include, i.e. the number of non-zero coefficients provided by the linear
explainer. This step ensures the interpretability of the explanation (Ribeiro,
Singh, and Guestrin 2016; Poursabzi-Sangdeh et al. 2021). To summarise, Kernel
SHAP is a method for approximating the SHAP values using a reduced number of
coalition samples. It relies on a weighted linear regression, where the
coefficients of the solution are estimates of the SHAP values. To build the
weighted linear model, a set of coalitions is sampled, prioritizing lower-
level layers whenever possible, and randomly drawing from deeper layers when
the budget allows it. For each coalition, the prediction is obtained using a
black-box predictive function $f_{x}$, and the weight is computed using the
Shapley Kernel (Equation (6)). Finally, the weighted linear model is fitted
using the weighted coalitions and their corresponding predictions.

##  3 REASON FOR INSTABILITY

In this section we illustrate the instability of Kernel SHAP with an example
and hypothesize on the reasons of this instability. To quantify stability, we
compute explanations for the same instance multiple times under the same
configuration and compute the Jaccard coefficient of the sets of features with
non-zero coefficients in the explanations – in the same spirit as in the state
of the art (Visani, Bagli, and Chesani 2020). If $S_{1},\dots,S_{n}$ denote
those sets, this corresponds to:

$J(S_{1},S_{2},\cdots,S_{n})=\frac{|S_{1}\cap S_{2}\cap\cdots\cap
S_{n}|}{|S_{1}\cup S_{2}\cup\cdots\cup S_{n}|}$ (7)

The coefficient ranges between 0 and 1, and values closer to 1 denote better
stability. Figure 1 illustrates the instability of Kernel SHAP on the Dry Bean
dataset for three explanations computed on the instance and run with identical
parameters. We note that the four relevant features are not the same in these
three executions. Moreover, the Jaccard coefficient obtained for $20$
explanations (on the same instance) is $0.74$ (with a budget set to $200$).
Further results on the instability of Kernel SHAP are presented in Section 5.

(a) Input instance

(b) Execution 1

(c) Execution 2

(d) Execution 3

Figure 1: Illustration of the instability of SHAP on an instance from the
DryBean dataset. The explanation size is 4, so each explanation computation
yields four features with non-zero values.

We believe that the main source of instability in SHAP explanations lies in
the way coalitions are generated. As seen in the previous section, Kernel
SHAP’s neighbor strategy introduces a lot of randomness in the process. The
generation of coalitions used to fit the linear model involves layer-wise
filling whenever possible, followed by random sampling (see Table 2). In
practice only the lower-level layers are fully explored, whereas the higher
layers are (sub-)sampled from a large and diverse population based on the
remaining budget. Those samples can be very different across multiple
executions of Kernel SHAP on the same instance. We believe that this
stochastic process is the primary source of Kernel SHAP’s instability.

##  4 IMPROVING KERNEL SHAP STABILITY

Our goal is to reduce the variability in explanations across multiple
executions of Kernel SHAP on the same instance, and if possible, to achieve
complete determinism. Our idea to enhance stability is to drop Kernel SHAP’s
condition $2$ when filling a layer (see Section 2, condition $2$ to fully
explore a layer), that is, fill the layers in increasing order as long as
there is still enough budget. Unlike SHAP, if the budget is not sufficient to
fill a layer, random generation only takes place in that layer. Then, to
eliminate variability completely, we can set the budget in a way that only
complete layers are considered.

Let us consider the case where $M=15$ depicted in Table 2, which illustrates
SHAP’s neighbor generation process for 7 layers. To generate elements of the
first layer, we consider the cases where only one feature is included and the
cases where only 1 feature is excluded. We can easily enumerate all possible
coalitions within this layer, resulting in exactly $2\cdot C_{15}^{1}=30$
coalitions. If the allocated budget is $30$, we can be sure that the same 30
coalitions will be generated every time we run SHAP. In that line of thought
budgets of $30$ or $240$ ($30+210$) guarantee full determinism in SHAP because
they entail complete layers.

Now, if the budget is $1200$ as in the example, SHAP will saturate layers 1
and 2 (with $30$ and $210$ neighbors respectively), which leaves us with a
remaining budget of $1200-210-30=960$ instances. SHAP will sample those
instances from all the remaining layers, whereas we propose to saturate layer
$3$ with $910$ neighbors and sample the remaining $50$ neighbors randomly from
layer $4$. As our experiments show, such an approach, that we call ST-SHAP
(i.e., Stable SHAP), mitigates the deleterious effects of sub-sampling in the
stability of the explanations. This is so because we restrict the random
sampling of neighbors to a smaller and less diverse universe, i.e., layer $4$
in ST-SHAP vs. layers $3$ to $7$ in SHAP.

##  5 EXPERIMENTS

We conduct a series of experiments to verify the effectiveness of ST-SHAP at
mitigating the instability of SHAP.

#### Environment.

The experiments were conducted on a computer with a 12th generation Intel-i7
CPU (14 cores with HT, 2.3-4.7 GHz Turbo Boost) We used the official SHAP
implementation provided by the authors (Lundberg and Lee 2017). ST-
SHAP111https://github.com/gwladyskelodjou/st-shap is based on this
implementation. We used the scikit-learn python library222https://scikit-
learn.org/ to fit the black-box models.

#### Datasets.

We use several datasets from the UCI machine learning data repository and
other popular real-world datasets, namely: Boston (Harrison Jr and Rubinfeld
1978) and Movie, which are regression datasets, and Credit(Yeh 2016), Adult
Income333We use a reformatted version released by the authors of SHAP.(Becker
and Kohavi 1996), DryBean444https://doi.org/10.24432/C50S4B, Spambase,
HELOC555https://community.fico.com/s/explainable-machine-learning-
challenge?tabset-158d9=3, and Wisconsin Breast Cancer Database, which are
classification datasets. Table 3 summarizes the information about datasets.

Dataset | Size | #features | Task | Explanation size
---|---|---|---|---
Movie | 505 | 19 | Regression | 4
Boston | 506 | 13 | Regression | 4
DryBean | 13611 | 16 | Classification | 4
Credit | 30000 | 23 | Classification | 4
Adult Income | 32561 | 12 | Classification | 4
Spambase | 4601 | 57 | Classification | 4
HELOC | 10459 | 23 | Classification | 4
WDBC | 569 | 30 | Classification | 4

Table 3: Summary of datasets used in our experiments. The Explanation size
indicates the number of non-zero coefficients returned by the linear model in
the explanation. Each explanation consists of four non-zero coefficients
representing the most important or significant features (the absolute value of
each coefficient indicates the magnitude or degree of importance of the
feature). All other features in the explanation have a zero coefficient.

#### Black-box models.

We also use various black-box models, including Support Vector Machine (SVM),
Random Forest (RF), Logistic Regression (LR), and Multi-layer Perceptron
(MLP). For each dataset, we randomly select 10 instances from the test set.
Finally, we compute the explanation 20 times for each explained instance to
derive the corresponding Jaccard value.

#### Metrics.

We evaluate stability by measuring the evolution of the Jaccard coefficient
(Equation 7) as we change the budget. We test budgets that lead to complete
layers for layers $1$ to $3$, as well as budgets that do not: {$10$, $20$,
$30$, $40$, $50$, $60$, $70$, $80$, $90$, $100$, $200$, $500$, $1000$,
$2000$}.

(a) Boston

(b) Dry Bean

(c) HELOC

(d) Spambase

Figure 2: Evolution of the Jaccard coefficient for SHAP and ST-SHAP on Boston,
DryBean, HELOC, and Spambase datasets. The vertical lines represent the
budgets that result in a complete layer.

The Figure 2.a presents the results obtained with the Boston dataset. We
report the average Jaccard coefficient among the 10 instances for each of the
studied budgets. Layers 1, 2 and 3 become complete when the budgets are $26$,
$182$ and $754$ respectively. We can see that, for ST-SHAP, the Jaccard
coefficient equals $1.0$ when the budget corresponds to complete layers. This
indicates a complete absence of variability. We also notice that ST-SHAP’s
stability outperforms SHAP’s as we approach budgets with complete layers. In
addition to these observations, we highlight in Figure 2.b with the Dry Bean
dataset that ST-SHAP is generally more stable than SHAP, even on incomplete
layers. Figure 2.d showcases results for Spambase dataset, a larger dataset.
For complete layers, only layers 1 and 2 have been calculated, as layer 3
requires a budget of $61826$. Budgets for incomplete layers remain unchanged.
The same trends are noted as for the previous datasets.

The results presented cover one regression and three classification datasets,
while the results for the other datasets can be found in Appendix 2. Similar
observations apply to these datasets.

Since stable explanations of low fidelity are as useless as unstable
explanations, we examine the impact of our method on the fidelity of the
explanations.

To assess fidelity, we compare the outputs of the black-box model with those
of the SHAP and ST-SHAP linear approximation models. For this purpose, we use
the $R^{2}$ statistic for regression tasks (using the Boston and the Movie
datasets) and the accuracy for classification tasks (for other datasets). In
both cases the metrics assess the quality of the linear approximation provided
by SHAP or ST-SHAP at “adhering” to the black box’s outcomes – so the higher
they are the better. This form of fidelity is referred as _adherence_ in the
literature (Visani, Bagli, and Chesani 2020; Gaudel et al. 2022).

(a) Boston

(b) Dry Bean

(c) HELOC

(d) Spambase

Figure 3: Adherence ($R^{2}$-Score for Boston and Accuracy for others) vs.
budget size for Boston, DryBean, HELOC, and Spambase dataset.

Figure 3.a was formed by taking the average $R^{2}$-score obtained for each
budget. Each $R^{2}$-score is obtained by comparing the results of SHAP (resp.
ST-SHAP) on the set of coalitions used to train the linear explainer. From
this figure, it can be observed that the fidelity of ST-SHAP is comparable to
SHAP’s. It is also noteworthy that the fidelity is generally high, even for
small budgets (e.g., by considering only the neighbors in Layer 1). Figure 3.b
illustrates the fidelity comparison between SHAP and ST-SHAP on the Dry Bean
dataset. The results demonstrate a generally good fidelity for both methods,
with ST-SHAP sometimes outperforming SHAP. Furthermore, for both methods,
fidelity tends to decrease with an expanding budget. This trend can be
attributed to the heightened diversity of entities from upper layers as the
budget increases, challenging the linear regression with a more diverse set of
entities. Depending on the black box, this can make the optimization problem
more challenging, resulting in lower fidelity compared to a regression trained
on the first layers. In Figure 3.d, presenting results for the Spambase
dataset, it can be observed that ST-SHAP generally exhibits better fidelity
than SHAP.

The results for the remaining datasets are provided in Appendix $2$. These
datasets yield the same conclusions. Additional experiments comparing the
exact SHAP values with the coefficients obtained with ST-SHAP show that the
approximation quality of the SHAP values by ST-SHAP is as good as that of
Kernel SHAP (see Appendix 2).

Our experiments on stability and fidelity led us to conclude that our layer-
wise strategy to complete layers of coalitions in SHAP reduces variability
satisfactorily, leading to stability. This stability is maximal (Jaccard score
of 1.0) when the budget guarantees fully complete layers. Moreover, our
methods do not have an impact on the adherence of the explanations. This means
that users can now choose which layers to use depending on the available time
and computing resources, since a larger number of coalitions translates into
longer execution times. After examining the stability and fidelity results, we
note that learning a surrogate on the coalitions of Layer 1 not only offers
complete stability and interesting fidelity, but it is also very fast to
compute because there are only $2M$ of such coalitions (where $M$ is the total
number of features). This makes Layer 1 a potentially interesting choice when
learning attribution scores. In the following, we conduct a theoretical study
of the attribution scores obtained with such a strategy.

##  6 FIRST LAYER ATTRIBUTION ANALYSIS

In this section, we investigate the attribution values obtained using
exclusively the coalitions from Layer 1. These attribution values are of
particular interest because they are the cheapest to compute. We first
characterize these attribution values, and demonstrate their good theoretical
properties, then we show to which extent they align with the exact SHAP values
on real datasets, and finally we compare the execution times.

### Theoretical Analysis

In order to simplify the notations, we use $N=\\{1,\cdots,M\\}$ the set of all
features and we extend $f$ on $\mathcal{P}(N)$ as shown by Equation (8).
$\mathds{1}_{S}\in\\{0,1\\}^{M}$ is defined by $(\mathds{1}_{S})_{i}=1$ if
$i\in S$ and 0 otherwise, with $S$ a coalition of features.

$\begin{array}[]{rl}f:\mathcal{P}(N)&\rightarrow\mathbb{R}\\\ S&\mapsto
f_{x}({\mathds{1}}_{S})\end{array}$ (8)

Coalitions of Layer 1 are of two types: coalitions with a single feature
present (a single $1$) and coalitions with a single feature absent (a single
$0$). In terms of marginal contribution, this amounts to averaging the
individual contribution $f(\\{j\\})-f(\emptyset)$, and the effect of removing
the feature from the input: $f(N)-f(N\backslash\\{j\\}),\;\forall j\in N$.

By also satisfying the local accuracy constraint (Lundberg and Lee 2017),
i.e., $\sum^{M}_{i=1}{\phi_{i}}=f(x)-f(\emptyset)$, we obtain Theorem 2, which
expresses a closed form for the attribution values of ST-SHAP when restricted
to Layer 1. The proof is given in Appendix 1.

######  Theorem 1 (attribution values with Layer 1).

For any feature $j$, the attribution value $\phi_{j}$ computed by ST-SHAP when
filling exactly Layer 1 is:

$\phi_{j}=\tilde{\phi}_{j}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)$
(9)

where for any $i$,
$\tilde{\phi}_{i}=\frac{f(\\{i\\})-f(\emptyset)+f(N)-f(N\backslash\\{i\\})}{2}$.

Given

  * •

$f(\\{i\\})-f(\emptyset)$ denoted by $\Delta_{i\emptyset}$

  * •

$f(N\setminus\\{i\\})-f(\emptyset)$ denoted by $\Delta_{\bar{i}\emptyset}$

  * •

$f(N)-f(N\setminus\\{i\\})$ denoted by $\Delta_{N\bar{i}}$

  * •

$f(N)-f(\emptyset)$ denoted by $\Delta$

We aim to solve the system of equations given by Equation (LABEL:eq:sysEq),
with two constraints: maintaining local accuracy,
$\sum_{i=1}^{M}{\phi_{i}}=\Delta$, and missingness, $\phi_{0}=f(\emptyset)$.

$\left\\{\begin{aligned} &\phi_{1}=f(\\{1\\})-\phi_{0}\\\ &\hskip
28.45274pt\vdots\\\ &\phi_{M}=f(\\{M\\})-\phi_{0}\\\
&\sum_{\begin{subarray}{c}j=1\\\ j\neq
1\end{subarray}}^{M}\phi_{j}=f(N\backslash\\{1\\})-\phi_{0}\\\
&\sum_{\begin{subarray}{c}j=1\\\ j\neq
2\end{subarray}}^{M}\phi_{j}=f(N\backslash\\{2\\})-\phi_{0}\\\ &\hskip
28.45274pt\vdots\\\ &\sum_{\begin{subarray}{c}j=1\\\ j\neq
M\end{subarray}}^{M}\phi_{j}=f(N\backslash\\{M\\})-\phi_{0}\\\
\end{aligned}\right.$ (10)

The goal is to solve the minimization problem:

$\textit{arg}\min_{\phi}\mathcal{L}(\bm{\phi})$ (11)

where $\mathcal{L}(\bm{\phi})$ is defined by:

$\displaystyle\mathcal{L}(\bm{\phi})=\sum_{i=1}^{M}\left(\phi_{i}-\Delta_{i\emptyset}\right)^{2}+\sum_{i=1}^{M}{\left(\left(\sum_{j=1;j\neq
i}^{M}\phi_{j}\right)-\Delta_{\bar{i}\emptyset}\right)^{2}}$ (12)
$\displaystyle=\sum_{i=1}^{M}\left(2\phi_{i}^{2}-2(\Delta_{N\bar{i}}+\Delta_{i\emptyset})\phi+\Delta_{N\bar{i}}^{2}+\Delta_{i\emptyset}^{2}\right)$
(13)

To solve this, we use the method of the Lagrange multiplier, resulting in:

$\textit{arg}\min_{\bm{\phi},\lambda}\mathcal{L^{\prime}}(\bm{\phi},\lambda)=\mathcal{L}(\bm{\phi})+\lambda(\sum_{i=1}^{M}{\phi_{i}}-\Delta)$
(14)

This is solved when

$\frac{\partial\mathcal{L}^{\prime}}{\partial\bm{\phi}}=0\;\;\;\text{and}\;\;\;\frac{\mathcal{L}^{\prime}}{\partial\lambda}=0$

The new equations are:

$\displaystyle\frac{\partial
L^{\prime}}{\partial\phi_{i}}=0=4\phi_{i}-2\Delta_{N\bar{i}}-2\Delta_{i\emptyset}+\lambda$
(15)

with $4\phi_{i}=2\Delta_{N\bar{i}}+2\Delta_{i\emptyset}-\lambda$

$\displaystyle\frac{\partial
L^{\prime}}{\partial\lambda}=0=\Delta-\sum_{i=1}^{M}{\phi_{i}}$ (16)

Adding up the $n$ equations (28), leads to a value for $\lambda$:

$\lambda=\frac{\sum_{j=1}^{M}{(2\Delta_{N\bar{j}}+2\Delta_{j\emptyset})-4\sum_{j=1}^{M}{\phi_{j}}}}{M}$
(17)

We can now plug Equation (32) into Equation (28), leading to our definition of
$\phi_{j}$ for any $j\in N$

$\phi_{j}=\tilde{\phi}_{j}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)$
(18)

It can be noted that with such a formula, the three properties: Linearity,
Symmetry, and Efficiency are verified (see Appendix 1). Therefore, the
proposed attribution method belongs to the LES family of attribution scores
(Ruiz, Valenciano, and Zarzuelo 1998; Chameni Nembua and Andjiga 2008; Radzik
and Driessen 2013), which also includes the Shapley values. LES values are
based on marginal contributions, providing feature contributions and
interpretations very close to the Shapley values (Condevaux, Harispe, and
Mussard 2022).

### Layer 1 versus Shapley values

We observed that the attribution values derived solely from the coalitions
within Layer 1 are more straightforward to calculate and fulfill the three
axioms of the LES family of attribution scores, also called LES values (Ruiz,
Valenciano, and Zarzuelo 1998; Condevaux, Harispe, and Mussard 2022). Now, let
us compare these values with the actual SHAP values (computed by materializing
all coalitions) using various datasets. This comparison is based on the
following considerations:

  * •

We include all the features in the explanation, meaning that the explanation
size is $M$, i.e., the number of features in the target dataset.

  * •

We use the Kendall rank correlation coefficient to compare the rankings of the
features within the explanation. This coefficient ranges from -1 to 1. Values
close to $1$, indicate that the Layer 1’s attribution ranks are in agreement
with the actual SHAP values.

  * •

To compare the disparity between the actual SHAP values and the Layer 1
attribution scores, we use the coefficient of determination, $R^{2}$. While
mainly used to evaluate wellness of fit for machine learning models, we remark
that it is suitable in our context. If we consider the SHAP values as the
“real” values and the Layer 1 scores as the “predicted” values designed to fit
the real values, the $R^{2}$ measures the proportion of the variance of the
real SHAP values “explained” by the Layer 1 attribution scores. When the
$R^{2}$ coefficient is 1 then both sets of scores agree, whereas values closer
to 0 suggest that our approximation is as good as the naive attribution that
assigns the same value to all features. Values smaller than 0 denote a
performance below the naive baseline.

We use the same datasets (specifically those for which the computation of the
exact SHAP values is feasible) and black-box models of Section 5. The
experiments are conducted on the whole test set (except for Credit dataset, in
which only $10$ random instances on the test set are used, due to high
execution time required to compute the actual SHAP values) and we report
averages and medians. Table 4 reports the corresponding results. We observe
from Kendall’s coefficient that the features ranks are almost the same between
Layer 1’s attribution scores and the exact SHAP values. The magnitudes of
those scores also remain very similar as shown by the $R^{2}$ scores in a
majority of cases. This makes Layer 1 attribution scores a very appealing
choice for very large datasets: they are stable and very fast compute to while
still agreeing with the exact SHAP values.

|  | Kendall $\tau$ |  |  $R^{2}$-Score
---|---|---|---|---
|  | SVM | RF | MLP |  | SVM | RF | MLP
Boston | Mean | $0.95$ | $0.91$ | $0.959$ |  | $0.98$ | $0.99$ | $0.99$
Median | $0.97$ | $0.92$ | $0.97$ |  | $0.99$ | $0.99$ | $0.99$
Adult | Mean | $0.7$ | $0.68$ | $0.87$ |  | $1.0$ | $0.65$ | $0.41$
Median | $0.6$ | $0.7$ | $0.9$ |  | $1.0$ | $0.77$ | $0.69$
Dry Bean | Mean | $0.86$ | $0.75$ | $0.84$ |  | $-0.07$ | $0.74$ | $0.75$
Median | $0.9$ | $0.76$ | $0.88$ |  | $0.51$ | $0.79$ | $0.8$
Movie | Mean | $1.0$ | $0.89$ | $0.85$ |  | $1.0$ | $0.99$ | $0.95$
Median | $1.0$ | $0.96$ | $0.86$ |  | $1.0$ | $0.99$ | $0.95$
Credit | Mean | $0.84$ | $0.64$ | $0.79$ |  | $0.94$ | $0.02$ | $0.81$
Median | $0.89$ | $0.71$ | $0.81$ |  | $0.98$ | $0.21$ | $0.83$

Table 4: Kendall’s $\tau$ and $R^{2}$-Score between the SHAP values and the
attributions scores of ST-SHAP from the coalitions of Layer 1.

### Execution times

The runtime of ST-SHAP Layer 1 is significantly more efficient compared to the
computation of exact SHAP values, with complexities of $O(M)$ and $O(2^{M})$
respectively.

Considering that the standard Kernel SHAP is recommended with a budget of
$2000$ ($2*M+2^{11}$), utilizing ST-SHAP Layer 1 shows to be up to one order
of magnitude faster than Kernel SHAP666It is also up three orders of magnitude
faster than computing the exact SHAP values.. This is so because the budget is
significantly lower than $2000$ as outlined in Appendix 2.

##  7 CONCLUSION

In this paper, we have investigated the instability issues of the Kernel SHAP
estimator and proposed a novel neighbor selection approach that achieves full
stability. Our experimental results demonstrate that our approach does not
compromise fidelity. We have also conducted a theoretical analysis of the
coefficients obtained by applying ST-SHAP on the neighbors of Layer 1. We
define those scores formally and show experimentally that they remain very
close to the actual SHAP values. This makes this approach an attribution
method in itself, that incurs faster computation while retaining most of the
desirable properties of attribution scores.

## References

  * Alvarez-Melis and Jaakkola (2018) Alvarez-Melis, D.; and Jaakkola, T. S. 2018.  On the Robustness of Interpretability Methods.  In _Proceedings of the 2018 ICML Workshop in Human Interpretability in Machine Learning_ , 66–71. Stockholm, Sweden: ICML.
  * Becker and Kohavi (1996) Becker, B.; and Kohavi, R. 1996.  Adult.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C5XW20.
  * Chameni Nembua and Andjiga (2008) Chameni Nembua, C.; and Andjiga, N. G. 2008.  Linear, efficient and symmetric values for TU-games.  _Economics Bulletin_ , 3(71): 1–10.
  * Condevaux, Harispe, and Mussard (2022) Condevaux, C.; Harispe, S.; and Mussard, S. 2022.  Fair and Efficient Alternatives to Shapley-based Attribution Methods.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 309–324. Springer.
  * Gaudel et al. (2022) Gaudel, R.; Galárraga, L.; Delaunay, J.; Rozé, L.; and Bhargava, V. 2022.  s-LIME: Reconciling locality and fidelity in linear explanations.  In _International Symposium on Intelligent Data Analysis_ , 102–114. Springer.
  * Ghorbani and Zou (2019) Ghorbani, A.; and Zou, J. 2019.  Data shapley: Equitable valuation of data for machine learning.  In _International conference on machine learning_ , 2242–2251. PMLR.
  * Harrison Jr and Rubinfeld (1978) Harrison Jr, D.; and Rubinfeld, D. L. 1978.  Hedonic housing prices and the demand for clean air.  _Journal of environmental economics and management_ , 5(1): 81–102.
  * Lundberg and Lee (2017) Lundberg, S. M.; and Lee, S.-I. 2017.  A unified approach to interpreting model predictions.  _Advances in neural information processing systems_ , 30.
  * Poursabzi-Sangdeh et al. (2021) Poursabzi-Sangdeh, F.; Goldstein, D. G.; Hofman, J. M.; Wortman Vaughan, J. W.; and Wallach, H. 2021.  Manipulating and Measuring Model Interpretability.  In _Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems_ , CHI ’21. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450380966.
  * Radzik and Driessen (2013) Radzik, T.; and Driessen, T. 2013.  On a family of values for TU-games generalizing the Shapley value.  _Mathematical Social Sciences_ , 65(2): 105–111.
  * Ribeiro, Singh, and Guestrin (2016) Ribeiro, M. T.; Singh, S.; and Guestrin, C. 2016.  ” Why should i trust you?” Explaining the predictions of any classifier.  In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , 1135–1144.
  * Ruiz, Valenciano, and Zarzuelo (1998) Ruiz, L. M.; Valenciano, F.; and Zarzuelo, J. M. 1998.  The family of least square values for transferable utility games.  _Games and Economic Behavior_ , 24(1-2): 109–130.
  * Selvaraju et al. (2017) Selvaraju, R. R.; Cogswell, M.; Das, A.; Vedantam, R.; Parikh, D.; and Batra, D. 2017.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In _Proceedings of the IEEE international conference on computer vision_ , 618–626.
  * Shapley et al. (1953) Shapley, L. S.; et al. 1953.  A Value for n-Person Games.  In Kuhn, H. W.; and Tucker, A. W., eds., _Contributions to the Theory of Games (AM-28), Volume II_ , 307–318. Princeton University Press, Princeton.  ISBN 978-1-4008-8197-0.
  * Song, Nelson, and Staum (2016) Song, E.; Nelson, B. L.; and Staum, J. 2016.  Shapley effects for global sensitivity analysis: Theory and computation.  _SIAM/ASA Journal on Uncertainty Quantification_ , 4(1): 1060–1083.
  * Strumbelj and Kononenko (2010) Strumbelj, E.; and Kononenko, I. 2010.  An efficient explanation of individual classifications using game theory.  _The Journal of Machine Learning Research_ , 11: 1–18.
  * Visani, Bagli, and Chesani (2020) Visani, G.; Bagli, E.; and Chesani, F. 2020.  OptiLIME: Optimized LIME Explanations for Diagnostic Computer Algorithms.  In _Proceedings of the CIKM 2020 Workshops co-located with 29th ACM International Conference on Information and Knowledge Management_ , volume 2699 of _CEUR Workshop Proceedings_.
  * Visani et al. (2022) Visani, G.; Bagli, E.; Chesani, F.; Poluzzi, A.; and Capuzzo, D. 2022.  Statistical stability indices for LIME: Obtaining reliable explanations for machine learning models.  _Journal of the Operational Research Society_ , 73(1): 91–101.
  * Yeh (2016) Yeh, I.-C. 2016.  default of credit card clients.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C55S3H.
  * Zhou, Hooker, and Wang (2021) Zhou, Z.; Hooker, G.; and Wang, F. 2021.  S-lime: Stabilized-lime for model explanation.  In _Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining_, 2429–2438.

##  Appendix A Appendix 1

### Proof of Theorem 1

In this Section, we prove Theorem 1, which we express again, hereafter, in a
longer form:

######  Theorem 2 (attribution values with Layer 1).

For any feature $j$, the attribution value $\phi_{j}$ computed by ST-SHAP when
filling exactly the layer 1 is:

$\displaystyle\phi_{j}$
$\displaystyle=\tilde{\phi}_{j}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)$
(19)

where for any $i$,
$\tilde{\phi}_{i}=\frac{f(\\{i\\})-f(\emptyset)+f(N)-f(N\backslash\\{i\\})}{2}$,
$f$ the predictor, and $N=\\{1,2,\cdots,M\\}$ the set of features.

###### Proof.

If we denote

  * •

$f(\\{i\\})-f(\emptyset)$ by $\Delta_{i\emptyset}$

  * •

$f(N\setminus\\{i\\})-f(\emptyset)$ by $\Delta_{\bar{i}\emptyset}$

  * •

$f(N)-f(N\setminus\\{i\\})$ by $\Delta_{N\bar{i}}$

  * •

$f(N)-f(\emptyset)$ by $\Delta$

In our problem, we have two constraints :

  * •

local accuracy : $\sum_{i=1}^{M}{\phi_{i}}=\Delta$

  * •

missingness : $\phi_{0}=f(\emptyset)$

We want to solve the system of equations given by (LABEL:eq:sysEq):

$\left\\{\begin{aligned} &\phi_{1}=f(\\{1\\})-\phi_{0}\\\
&\phi_{2}=f(\\{2\\})-\phi_{0}\\\ &\hskip 28.45274pt\vdots\\\
&\phi_{M}=f(\\{M\\})-\phi_{0}\\\ &\sum_{\begin{subarray}{c}j=1\\\ j\neq
1\end{subarray}}^{M}\phi_{j}=f(N\backslash\\{1\\})-\phi_{0}\\\
&\sum_{\begin{subarray}{c}j=1\\\ j\neq
2\end{subarray}}^{M}\phi_{j}=f(N\backslash\\{2\\})-\phi_{0}\\\ &\hskip
28.45274pt\vdots\\\ &\sum_{\begin{subarray}{c}j=1\\\ j\neq
M\end{subarray}}^{M}\phi_{j}=f(N\backslash\\{M\\})-\phi_{0}\\\
\end{aligned}\right.$ (20)

Therefore, our goal is to solve the minimization problem

$\textit{arg}\min_{\phi}\mathcal{L}(\bm{\phi})$ (21)

where:

$\displaystyle\mathcal{L}(\bm{\phi})=\sum_{i=1}^{M}\left(\phi_{i}-\Delta_{i\emptyset}\right)^{2}+\sum_{i=1}^{M}{\left(\left(\sum_{j=1;j\neq
i}^{M}\phi_{j}\right)-\Delta_{\bar{i}\emptyset}\right)^{2}}$ (22)
$\displaystyle=\sum_{i=1}^{M}(\phi_{i}-\Delta_{i\emptyset})^{2}+\sum_{i=1}^{M}(\Delta-\phi_{i}-\Delta_{\bar{i}\emptyset})^{2}\;\;\;\text{[due
to the local accuracy requirement]}$ (23)
$\displaystyle=\sum_{i=1}^{M}(\phi_{i}-\Delta_{i\emptyset})^{2}+\sum_{i=1}^{M}(\Delta_{N\bar{i}}-\phi_{i})^{2}\;\;\;[\text{Because}\;\;\Delta-\Delta_{\bar{i}\emptyset}=\Delta_{N\bar{i}}]$
(24)
$\displaystyle=\sum_{i=1}^{M}\left(2\phi_{i}^{2}-2(\Delta_{N\bar{i}}+\Delta_{i\emptyset})\phi+\Delta_{N\bar{i}}^{2}+\Delta_{i\emptyset}^{2}\right)$
(25)

The minimization of $\mathcal{L}$ is constrained by
$\sum_{i=1}^{M}{\phi_{i}}-\Delta=0$. To solve this, we can use the method of
the Lagrange multiplier i.e., we minimize instead:

$arg\min_{\bm{\phi},\lambda}\mathcal{L^{\prime}}(\bm{\phi},\lambda)=\mathcal{L}(\bm{\phi})+\lambda(\sum_{i=1}^{M}{\phi_{i}}-\Delta)$
(26)

This is solved when

$\frac{\partial\mathcal{L}^{\prime}}{\partial\bm{\phi}}=0\;\;\;\text{and}\;\;\;\frac{\mathcal{L}^{\prime}}{\partial\lambda}=0$

If we rearrange the terms we can see that
$\mathcal{L^{\prime}}(\bm{\phi},\lambda)$ has the following form:

$\mathcal{L^{\prime}}(\bm{\phi},\lambda)=\sum_{i=1}^{M}\left(2\phi_{i}^{2}-(2\Delta_{N\bar{i}}+2\Delta_{i\emptyset}-\lambda)\phi_{i}+\Delta_{N\bar{i}}^{2}+\Delta_{i\emptyset}^{2}\right)-\lambda\Delta$
(27)

Hence,

$\displaystyle\frac{\partial
L^{\prime}}{\partial\phi_{i}}=0=4\phi_{i}-2\Delta_{N\bar{i}}-2\Delta_{i\emptyset}+\lambda\;\;\therefore\;\;4\phi_{i}=2\Delta_{N\bar{i}}+2\Delta_{i\emptyset}-\lambda$
(28) $\displaystyle\frac{\partial
L^{\prime}}{\partial\lambda}=0=\Delta-\sum_{i=1}^{M}{\phi_{i}}$ (29)

We need to get rid of $\lambda$ to solve for $\phi_{i}$. If we add up the $n$
equations of the form $\frac{\partial L}{\partial\phi_{i}}=0$ (Equation 28),
we get:

$\displaystyle
4\sum_{j=1}^{M}{\phi_{j}}=\sum_{j=1}^{M}{(2\Delta_{N\bar{j}}+2\Delta_{j\emptyset})}-M\lambda$
(31)
$\displaystyle\lambda=\frac{\sum_{j=1}^{M}{(2\Delta_{N\bar{j}}+2\Delta_{j\emptyset})-4\sum_{j=1}^{M}{\phi_{j}}}}{M}$
(32)

We can now plug Equation 32 into Equation 28:

$\displaystyle
4\phi_{i}=2\Delta_{N\bar{i}}+2\Delta_{i\emptyset}-\left(\frac{\sum_{j=1}^{M}{(2\Delta_{N\bar{j}}+2\Delta_{j\emptyset})-4\sum_{j=1}^{M}{\phi_{j}}}}{M}\right)$
(34) $\displaystyle
4\phi_{i}=2\Delta_{N\bar{i}}+2\Delta_{i\emptyset}-\frac{\sum_{j=1}^{M}{\left(2\Delta_{N\bar{j}}+2\Delta_{j\emptyset}\right)-4\Delta}}{M}$
(35) $\displaystyle
4\phi_{i}=2\Delta_{N\bar{i}}+2\Delta_{i\emptyset}+4\frac{\Delta}{M}-\frac{\sum_{j=1}^{M}{\left(2\Delta_{N\bar{j}}+2\Delta_{j\emptyset}\right)}}{M}$
(36)
$\displaystyle\phi_{i}=\frac{f(\\{i\\})-f(N\setminus\\{i\\})}{2}-\frac{\Delta}{2}+\frac{\Delta}{M}-\frac{\sum_{j=1}^{M}{f(j)-f(N\setminus\\{j\\})}}{2M}+\frac{M\Delta}{2M}$
(37)

meaning for any $i\in N$

$\displaystyle\phi_{i}$
$\displaystyle=\tilde{\phi}_{i}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{j=1}^{M}\tilde{\phi}_{j}\right)$
(38)

∎

###  LES properties of Layer 1 Explanations

To prove LES properties, we use the attribution values as expressed by
Equation (41).

Our approximation of the Shapley value can be considered as an attribution
method from the LES (Linearity, Efficiency, and Symmetry) family.

We show here that these three fundamental properties are verified.

#### Linearity.

The attribution method based on Layer 1 coalitions is linear if for any models
$f_{1},f_{2}$ with an example $x$, and for any
$\alpha_{1},\alpha_{2}\in\mathbb{R}$:
$\phi_{j}(x,\alpha_{1}f_{1}+\alpha_{2}f_{2})=\alpha_{1}\phi_{j}(x,f_{1})+\alpha_{2}\phi_{j}(x,f_{2})$.
We can proceed in two steps: (i) prove that $\phi_{j}(x,\alpha
f)=\alpha\phi_{j}(x,f)$ and then (ii)
$\phi_{j}(x,f_{1}+f_{2})=\phi_{j}(x,f_{1})+\phi_{j}(x,f_{2})$

$\phi_{j}=\tilde{\phi}_{j}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)$

where for any $i\in N$,

$\tilde{\phi}_{i}=\frac{f(\\{i\\})-f(\emptyset)+f(N)-f(N\backslash\\{i\\})}{2}.$

  * •

First, we want to prove that if $g=\alpha f$ then $\forall j\in N$,
$\phi_{j}(x,g)=\alpha\phi_{j}(x,f)$

Let assume : $g=\alpha f$ and let take $j\in N$ and $i\in N$, then:

$\displaystyle\tilde{\phi}_{i}(x,g)$
$\displaystyle=\frac{g(\\{i\\})-g(\emptyset)+g(N)-g(N\backslash\\{i\\})}{2}$
$\displaystyle=\frac{\alpha f(\\{i\\})-\alpha f(\emptyset)+\alpha f(N)-\alpha
f(N\backslash\\{i\\})}{2}$ $\displaystyle=\alpha\phi_{i}(x,f)$

$\displaystyle\phi_{j}(x,g)$
$\displaystyle=\tilde{\phi}_{j}(x,g)+\frac{1}{M}\left(g(N)-g(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}(x,g)\right)$
$\displaystyle=\alpha\tilde{\phi}_{j}(x,f)+\frac{1}{M}\left(\alpha f(N)-\alpha
f(\emptyset)-\sum_{i=1}^{M}\alpha\tilde{\phi}_{i}(x,f)\right)$
$\displaystyle=\alpha\left(\tilde{\phi}_{j}(x,f)+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}(x,f)\right)\right)$
$\displaystyle=\alpha\phi_{j}(x,f)$

  * •

Second, we want to prove that if $g=f_{1}+f_{2}$ then $\forall j\in N$,
$\phi_{j}(g,x)=\phi_{j}(x,f_{1})+\phi_{j}(x,f_{2})$
Let assume : $g=f_{1}+f_{2}$ and let take $j\in N$ and $i\in N$ then :

$\displaystyle\tilde{\phi}_{i}(x,g)$
$\displaystyle=\frac{g(\\{i\\})-g(\emptyset)+g(N)-g(N\backslash\\{i\\})}{2}$
$\displaystyle=\frac{f_{1}(\\{i\\})+f_{2}(\\{i\\})-(f_{1}(\emptyset)+f_{2}(\emptyset))+(f_{1}(N)+f_{2}(N))-(f_{1}(N\backslash\\{i\\})+f_{2}(N\backslash\\{i\\}))}{2}$
$\displaystyle=\frac{f_{1}(\\{i\\})-f_{1}(\emptyset)+f_{1}(N)-f_{1}(N\backslash\\{i\\})+f_{2}(\\{i\\})-f_{2}(\emptyset)+f_{2}(N)-f_{2}(N\backslash\\{i\\}))}{2}$
$\displaystyle=\tilde{\phi}_{i}(x,f_{1})+\tilde{\phi}_{i}(x,f_{2})$

$\displaystyle\phi_{j}(x,g)$
$\displaystyle=\tilde{\phi}_{j}(x,g)+\frac{1}{M}\left(g(N)-g(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}(x,g)\right)$
$\displaystyle=\tilde{\phi}_{j}(x,f_{1})+\tilde{\phi}_{j}(x,f_{2})+\frac{1}{M}\left(f_{1}(N)+f_{2}(N)-(f_{1}(\emptyset)+f_{2}(\emptyset))-\sum_{i=1}^{M}(\tilde{\phi}_{i}(x,f_{1})+\tilde{\phi}_{i}(x,f_{1}))\right)$
$\displaystyle=\tilde{\phi}_{j}(x,f_{1})+\frac{1}{M}\left(f_{1}(N)-f_{1}(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}(x,f_{1})\right)+\tilde{\phi}_{j}(x,f_{2})+\frac{1}{M}\left(f_{2}(N)-f_{2}(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}(x,f_{2})\right)$
$\displaystyle=\phi_{j}(x,f_{1})+\phi_{j}(x,f_{2})$

#### Efficiency.

We want to prove that $\sum_{i=1}^{M}\phi_{i}=f(N)-f(\emptyset)$

$\displaystyle\phi_{j}$
$\displaystyle=\tilde{\phi}_{j}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)$
$\displaystyle\sum_{j=1}^{M}\phi_{j}$
$\displaystyle=\sum_{j=1}^{M}\left(\tilde{\phi}_{j}+\frac{1}{M}\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)\right)$
$\displaystyle=\sum_{j=1}^{M}\tilde{\phi}_{j}+\left(f(N)-f(\emptyset)-\sum_{i=1}^{M}\tilde{\phi}_{i}\right)$
$\displaystyle=f(N)-f(\emptyset)$

#### Symmetry.

We want to show that

$\left(\left.\begin{aligned} &\forall j\in N\\\ &\forall k\in N\\\ &\forall
S\in\mathcal{P}(N),\;\textrm{with}\;\\{j,k\\}\notin
S\end{aligned}\right\\}\quad
f(S\cup\\{j\\})=f(S\cup\\{k\\})\right)\Rightarrow\phi_{j}=\phi_{k}$ (39)

Let assume :

$\left.\begin{aligned} \forall j&\in N\\\ \forall k&\in N\\\ \forall
S&\in\mathcal{P}(N),\;\textrm{with}\;\\{j,k\\}\notin S\\\
\end{aligned}\right\\}f(S\cup\\{j\\})=f(S\cup\\{k\\})$ (40)

For $S=\emptyset$ we have $f(\\{j\\})=f(\\{k\\})$
For $S=N\backslash\\{j\\}$ we have $f(N)=f(N\backslash\\{j\\})$
For $S=N\backslash\\{k\\}$ we have $f(N)=f(N\backslash\\{k\\})$

We know that :

$\phi_{j}=\frac{f(\\{j\\})-f(N\backslash\\{j\\})}{2}-\frac{\sum_{i=1}^{M}f(\\{i\\})-f(N\backslash\\{i\\})}{2M}+\frac{f(N)-f(\emptyset)}{M}$
(41)

But

$f(\\{j\\})-f(N\backslash\\{j\\})=f(\\{j\\})-f(N\backslash\\{j\\})$

and the rest of the sum of $\phi_{j}$ do not depend on $j$, so
$\phi_{j}=\phi_{k}$

##  Appendix B Appendix 2

### Additional experiments on comparing SHAP and ST-SHAP

In this section, we present further results on the stability of Kernel SHAP
(called SHAP here), and our stability-enhancing approach, ST-SHAP.

(a) Jaccard

(b) VSI

(c) Adherence with the black-box

(d) Kendall $\tau$ with the exact SHAP values

(e) $R^{2}$-Score with the exact SHAP values

Figure 4: Comparison results between SHAP and ST-SHAP across various criteria
on the Boston dataset.

In Figure 4, we compare SHAP and ST-SHAP to evaluate the stability, fidelity,
and quality of approximation of the exact SHAP values. Figures 4.a and 4.b
depict stability outcomes assessed using two state-of-the-art metrics: the
Jaccard index and the Variable Stability Index (VSI), respectively. An initial
observation highlights a significant similarity between these two plots,
suggesting a certain equivalence between these metrics. This is the rationale
behind our decision to utilize Jaccard’s index for presenting the stability
results. Furthermore, it is noted that ST-SHAP achieves maximum stability
(both Jaccard and VSI at $1.0$) across complete layers. Additionally, as the
budget approaches completeness for a layer, stability also tends toward $1.0$
on ST-SHAP. Figure 4.c, on the other hand, depicts the results concerning
fidelity with respect to the black-box model. It is noticeable that ST-SHAP
performs better than SHAP, with peaks occurring over complete layers. This
leads us to conclude that our methods ST-SHAP do not have an impact on the
adherence of the explanations. Lastly, we conducted a comparison of the
approximation quality of the exact SHAP values using the SHAP and ST-SHAP
surrogates. Figure 4.d illustrates the outcomes based on Kendall’s
coefficient, revealing a similar ranking between the two methods and a
substantial agreement with the exact SHAP values. Regarding the disparities
between the SHAP and ST-SHAP coefficients relative to the actual SHAP values,
it is noticeable in Figure 4.e that both methods align closely and provide
effective approximations of the exact SHAP values.

(a) Jaccard

(b) VSI

(c) Adherence with the black-box

(d) Kendall $\tau$ with the exact SHAP values

(e) $R^{2}$-Score with the exact SHAP values

Figure 5: Comparison results between SHAP and ST-SHAP across various criteria
on the Movie dataset.

Figure 5 illustrates SHAP and ST-SHAP results on the Movie dataset. Stability
(Figures 5.a and 5.b) and fidelity (Figure 5.c) criteria have the same
observations as those on the Boston dataset. In terms of the precision in
approximating the exact SHAP values, Figure 5.d showcases a similar ranking,
with SHAP slightly better than ST-SHAP. Regarding the attribution coefficients
of both methods compared to the exact SHAP values, SHAP presents relatively
weaker performance for smaller budgets (as depicted in Figure 5.e), but
overall, both curves exhibit similar performance levels.

(a) Jaccard

(b) VSI

(c) Adherence with the black-box

(d) Kendall $\tau$ with the exact SHAP values

(e) $R^{2}$-Score with the exact SHAP values

Figure 6: Comparison results between SHAP and ST-SHAP across various criteria
on the Dry Bean dataset.

Figure 6 presents the comparison results between ST-SHAP and SHAP on the Dry
Bean dataset. Figures 6.a, 6.b, and 6.c share the same interpretation as their
counterparts in other datasets. As for the ranking quality (according to the
exact SHAP values) using Kendall’s coefficient in Figure 6.d, a general
similarity is noticed among all models, except for ST-SHAP with the MLP
function, which exhibits a lower ranking score than SHAP with MLP. Although
there are generally similar performances between the two methods on the R2
score compared to the exact SHAP values (as shown in Figure 6.e), weak
performances of SHAP in smaller budgets are observed, especially with the SVM
model.

(a) Jaccard

(b) Adherence with the black-box

(c) Kendall $\tau$ with the exact SHAP values

(d) $R^{2}$-Score with the exact SHAP values

Figure 7: Comparison results between SHAP and ST-SHAP across various criteria
on the Adult Income dataset.

Figure 7 illustrates SHAP and ST-SHAP results on the Adult Income dataset. We
observe that ST-SHAP is generally better on stability than SHAP (Figure 7.a on
Jaccard Index). With adherence metrics ranging from $0.95$ to $1.0$, we can
deduce that our approach ST-SHAP exhibits similar behavior to SHAP (Figure 7.b
on Adherence to black-box with $R^{2}$-Score). Figure 7.c depicts the Kendall
coefficient according to exact SHAP values, showing comparable performance
between both methods, with weaker performance on SHAP with SVM. ST-SHAP
slightly outperforms SHAP, particularly with peaks in complete layers. Moving
on to Figure 7.d, we show the outcomes in terms of $R^{2}$-score concerning
the exact SHAP values. The results generally exhibit similar trends, although
SHAP demonstrates weaker performance in smaller budget.

(a) Jaccard

(b) Adherence with the black-box

Figure 8: SHAP and ST-SHAP on the Credit dataset.

Figure 8 presents results from Kernel SHAP and ST-SHAP on the Credit dataset.
For the stability criterion (figure 8.a), the same interpretations apply as
for the other data sets. As the adherence (8.b) is between $0.97$ and $1.0$,
we can conclude that our approach behaves in a similar way to SHAP, and both
approaches exhibit good performance.

(a) Jaccard

(b) Adherence with the black-box

Figure 9: SHAP and ST-SHAP on the Spambase dataset.

(a) Jaccard

(b) Adherence with the black-box

Figure 10: SHAP and ST-SHAP on the HELOC dataset.

(a) Jaccard

(b) Adherence with the black-box

Figure 11: SHAP and ST-SHAP on the Breast Cancer Wisconsin (Diagnostic)
dataset.

### Comparison of execution times

Within this section, we compare execution times for Layer 1, including the
calculation of exact SHAP values, and for SHAP using a ’normal’ budget
(approximating the recommended budget for SHAP).

| ST-SHAP Layer 1 |  | Exact SHAP value |  | Kernel SHAP (budget = $2000$)
---|---|---|---|---|---
| SVM | RF | MLP |  | SVM | RF | MLP |  | SVM | RF | MLP
Boston | 0.003 | 0.032 | 0.007 |  | 0.22 | 0.154 | 0.17 |  | 0.083 | 0.087 | 0.06
Dry bean | 0.031 | 0.02 | 0.019 |  | 7.382 | 0.78 | 1.07 |  | 0.28 | 0.098 | 0.103
Adult | 0.014 | 0.01 | 0.008 |  | 1.663 | 0.099 | 0.103 |  | 0.64 | 0.067 | 0.067
Movie | 0.01 | 0.028 | 0.008 |  | 6.802 | 4.88 | 4.62 |  | 0.083 | 0.088 | 0.062

Table 5: Mean time taken for computation (in seconds) from ST-SHAP Layer 1 to
exact SHAP values. The calculations are carried out using the entire test set
for each dataset.

Table 5 presents the results obtained for the execution time. It is noticeable
that the runtime of ST-SHAP Layer 1 is significantly more efficient than that
required to compute the exact SHAP values. It is up to three orders of
magnitude faster than computing the exact SHAP values. Considering that the
standard Kernel SHAP is recommended with a budget of $2000$ ($2*M+2^{11}$),
utilizing ST-SHAP Layer 1 shows to be up to one order of magnitude faster than
Kernel SHAP. This is so because the budget is significantly lower than $2000$.
Moreover, as we saw previously, explanations calculated using only the
coefficients from Layer 1 are stable, exhibit good adherence to the black-box
model, and remain a good approximation of the exact SHAP value.