SHAP-XRT: The Shapley Value Meets Conditional Independence Testing
Authors: Jacopo Teneggi
Beepul Bharti
Yaniv Romano
Jeremias Sulam
Venue: Accepted by TMLR ()

Abstract: The complex nature of artificial neural networks raises concerns on their reliability, trustworthiness, and fairness in real-world scenarios. The Shapley value---a solution concept from game theory---is one of the most popular explanation methods for machine learning models. More traditionally, from a statistical perspective, feature importance is defined in terms of conditional independence. So far, these two approaches to interpretability and feature importance have been considered separate and distinct. In this work, we show that Shapley-based explanation methods and conditional independence testing are closely related. We introduce the \textbf{SHAP}ley E\textbf{X}planation \textbf{R}andomization \textbf{T}est (SHAP-XRT), a testing procedure inspired by the Conditional Randomization Test (CRT) for a specific notion of local (i.e., on a sample) conditional independence. With it, we prove that for binary classification problems, the marginal contributions in the Shapley value provide lower and upper bounds to the expected $p$-values of their respective tests. Furthermore, we show that the Shapley value itself provides an upper bound to the expected $p$-value of a global (i.e., overall) null hypothesis. As a result, we further our understanding of Shapley-based explanation methods from a novel perspective and characterize the conditions under which one can make statistically valid claims about feature importance via the Shapley value.

Published in Transactions on Machine Learning Research (12/2023)
SHAP-XRT: The Shapley Value Meets Conditional Independence Testing
Jacopo Teneggi"
jtenegg I @rjhu. edu
Deportment of Computer Science, Johns Hopkins University Mathematical Institute for Data Science (MINDS), Johns Hopkins University
Beepul Bharti'
bbhartil @rjhu. edu
Department of Biomedical Engineering, Johns Hopkins University Mathematical Institute for Data Science (MINDS), Johns Hopkins University
Yaniv Romano
yromano Mtenhniinnccc
Departments of Electricol Engineering and of Computer Science, Technion -sruel Institute of Technology
Jeremias Sulam
jsulam I @rjuu. edu
Deportment of Biomedical Engineering, Johns Hopkins University
Mathematical Institute for Data Science (MINDS), Johns Hopkins University
(*) Equal contribution
Reviewed OpenReview: http:p//pperrrrrre...a////ommmma
Abstract
The complex nature of artificial neural networks raises concerns on their reliability, trust- worthiness, and fairness in weal-world scenarios. The Shapley value-a a solution concept from game theory-is one of the most popular explanation methods for machine learning models. More traditionally, from a statistical perspective, feature importance is defined terms of conditional independence. So far, these two approaches to interpretability and feature importance have been considered separate and distinct. In this work, we show that Shapley-based explanation methods and conditional independence testing closely related. We introduce the SHAPley EX explanation Randomization Test (SHAP-XRT), testing procedure inspired by the Conditional Randomization Test (CRT) for a specific notion of local (i.e., on sample) conditional independence. With it, we prove that for binary classification problems, the marginal contributions in the Shapley value provide lower and upper bounds to the expected p-values of their respective tests. Furthermore, we show that the Shapley value itself provides an upper bound to the p-value of global (i.e., overall) null hypothesis. As a result, we further our understanding of Shapley-based explanation methods from novel perspective and characterize the conditions under which one can make statistically valid claims about feature importance via the Shapley value.
1 Introduction
Deep learning models have shown remarkable success in solving wide range of problems, from computer vision and natural language processing, to reinforcement learning and scientific research (LeC'n et al., 2015). These exciting results have come hand-in-hand with an increase in the complexity of these models, mostly based on neural networks. While these systems consistently set the state-of-the-arl. in many tasks, our understanding of their specific mechanisms remains intuitive at best. In fact, as neural networks keep getting deeper and wider, they also become opaque (or unintelligible) transparency usually referred the black-bor problem: the predictions of deep learning model are not readily interpretable, entailing theoretical, societal, and regulatory issues (Zednik, 2021; Tomsett et al.,
both developers and users. This lack of

---

Published in Transactions on Machine Learning Research (12/2023)
2018; Shin, 2021). For example, certain regulations may require companies and organizations who rely on autonomous systems to provide explanations of their decisions (e.g., what lead a model to reject a loan application) (Casey et al., 2019; Kaminski & Malgieri, 2020; Hacker et al., 2020). Finally, it is still unclear whether a loss of interpretability is unavoidable to increase performance (Rudin, 2019).
These concerns on the reliability and trustworthiness of machine learning have motivated recent efforts on explaining predictions. A distinction exists between inherently interpretable models and explanation methods. The former are designed to provide predictions that can be understood by their users. For example, rule-based systems and decision trees are considered inherently interpretable because it is possible to trace prediction through the specific rules or splits Icarned by the model. On the other hand, when models are not explicitly designed in an interpretable fashion (e.g,, deep neural networks), we usually rely on a-posteriori explanation methods to find the most important features towards a prediction. These methods assign an importance score to every feature (or groups thereof) in the input, and the resulting scores can be presented to a user as an explamation of the prediction. Explanation methods have been widely adopted given their easy implementation and their ability to explain any model, i.e. they can be model-agnostic. Since the introduction of CAM (Zhou et al., 2016), DeepLift (Shrikumar et al., 2017), and LIME (Ribeiro et al., 2016), the explainability literature has witnessed remarkable growth, and various approaches have been proposed to identify important features (Selvaraju et al., 2017; Lundberg & Lee, 2017: Chen et al., 2018; Covert et al., 2021; Kolek et al., 2021; Jiang et al., 2021; Kolek et al., 2022; Teneggi et al., 2022a; Mosca et al., 2022) with varying degrees of success (Adebayo et al., 2018; Shah et al., 2021).
The SHAP framework (Lundberg & Lee, 2017) unifies several existing methods while providing explanations that satisfy some desirable theoretical properties. More precisely, it brings the Shapley value (Shapley, 1951) a solution concept from game theory (Owen, 2013) to bear in the interpretation of machine learning predictors. In cooperative game theory, solution concept is a formal rule that describes the strategy that each player will use when participating in a game. For Transfer Utility (TU) games, the Shapley value is the only solution concept that satisfics the propertics of additivity, mullity, symmotry, and lincarity, and it can be derived axiomatically." 1 In the context of explainability, the SHAP framework considers a TU game represented by the predictive model, where every feature in the input is a player in the game, and it computes their Shapley values as mcasure of feature importance. 2 We remark that the axiomatic characterization of the Shapley value implies that it is the only explanation method that satisfies these theoretical properties. The most important limitation of the Shapley value is its exponential computational cost in the number of players (i.e., the input dimension), which quickly becomes intractable for several applications of interest. Thus, most Shapley-based methods rely on various strategies to approximate them (Chen et al., 2023), some with finite-sample, non-asymplotic, and efficiency guarantees (Chen et al., 2018; Lundberg el al., 2020; Teneggi et al., 2022a). An alternative approach to relax some of the axioms. This yields several other explanation methods based on feature's marginal contribution, such as semivalues (Dubey et al., 1981) and random order values (Frye et al., 2020b).
While theoretically appealing, and often useful in practice, this Shapley-based approach to interpretability remains questionable:
What does il meon for feature to receive a large Shapley value?
Previous works have explored the connection between feature selection and the Shapley value (Cohen et al., 2007; Fryer et al., 2021; Rozemberezki et al., 2022) as well some statistical implications of large (or small) Shapley values (Owen & Prieur, 2017; Hooker, 2007; Ma & Tourani, 2020; Verdinelli & Wasserman, 2021; 2023). However, a general and precise connection between the Shapley value and statistical importance has been missing. In particular, it is unclear how to provide false positive rate control (i.c., to control the Type error) when feature selection is performed on the basis of Shapley values. This is a fundamental issue as explanation methods are increasingly used in high-stakes scenarios to inform decision making, especially in medicine (Zoabi et al., 2021; de Almeida et al., 2022; Liu & Xie, 2020). For example, consider a clinical setting where a predictor is used to support diagnosis and treatment. Given each feature's Shapley value,
In TU game, players can exchange their utility without incurring in any cost. Herein, we will implicitly refer the Shapley value of feature according to the definition of SHAP attribution in Lundberg & Lee (2017).
2

---

Published in Transactions on Machine Learning Research (12/2023)
which ones should we deem important? If patient's age, blood pressure, weight, and height receive Shapley values of 0.30, 0.15, 0.35, and 0.20, respectively, which should we report? We could decide to report the most important feature (i.e., weight). This choice will likely underreport findings and potentially mislead the clinician. Symmotrically, reporting all features with a positive Shapley value would be uninformative with respect to the decision process of the model. This example shows the lack of a rigorous way to perform statistically-valie feature selection by means of the Shapley value, and how overlooking this question could lead to potentially harmful consequences in real-world scenarios.
In this paper, we show how relating the Shapley value to statistical notions of conditional independence provides principled way to select important features. Indeed, the statistics literature has a rich history of studying variable selection problems (Blum & Langley, 1997; James et al., 2013; Guyon & Elisseeff, 2003), for example, via conditional independence testing and controlled variable selection (Candes et al., 2018). That is, a feature is unimportant it is independent of response once conditioned on the remaining features. In other words, knowing the value of an unimportant feature does not provide any more information about the response when the rest of the data is known. The Conditional Randomization Test (CRT) (Candes et al., 2018) is a conditional independence test that does not make any assumptions on the conditional distribution of the response given the features, while assuming that the conditional distribution of the features is known instead. This setting is particularly useful in applications where unlabeled data may be abundant compared to labeled data (e.g,, genomics research, as shown in (Candes et al., 2018; Sesia et al., 2021; Sesia & Sun, 2022), or imaging data (Nguyen et al., 2019)). While the original CRT procedure is computationally intractable for large models, fast and efficient alternatives have been recently proposed, such as the the Holdout Randomization Test. (HRT) by Tansey et al. (2022) and the Distilled Conditional Randomization Test (DCRT) by Liu et al. (2022).
We remark that in this paper we consider feature importance with respect to the response of a fixed predictive model on an individual sample. This differs from the traditional statistical setting in which one analyzos features with respect to an observed responso at the population level. Nonetheless, this notion of interpretability is important in many scenarios. For example, one may wish to understand the important features for a model that computes credit scores (Demajo et al., 2020; Bücker et al., 2022), or one may need to verify that the important features for the prediction of an existing, complex model agree with prior-knowledge (Burns et al., 2020; Jiang et al., 2021; Fong & Vedaldi, 2017).
1.1 Related work
Previous works have explored granting the Shapley value with some statistical notion of importance. For example, Owen & Prieur (2017) and Verdinelli & Wasserman (2021; 2023) study the Shapley value for correlated variables in the context of ANalysis Of VAriance (ANOVA) (Hooker, 2007) and Leave Out COvariates (LOCO) (Lei et al., 2018) procedures, respectively. Importantly, Verdinelli & Wasserman (2021) preciscly raise the issuc of the lack of statistical meaning for large (or small) Shapley values when features are correlated. Information theoorttitteeetcccccoo interpretations of the Shapley value have also been proposed. SAGE (Covert et al., 2020) translates the Shapley value from local (i.c., on a sample) to global (i.e., over a population) feature importance, and shows connections to mutual information. Most recently, (Watson et al., 2023) propose modified Shapley value with precise between the true response and the features. In the context of data attribution methods, Ghorbani et al. (2020) define the Distributional Shapley value to include information about the underlying data distribution into the original Shapley value. Finally, and most closely to this work, Ma & Tourani (2020) try and deploy ideas of conditional independence to the Shapley value for cansal inference on data generated by a Bayesian network. Our work differs from these, as we now summarize.
properties to study the independence
1.2 Contributions
In this paper, we will show that for machine learning models, computing the Shapley value of a given input feature amounts to performing a series of conditional independence tests for specific feature importance definitions. This is different from Watson et al. (2023) in that we do not assume the predictor to be the true conditional distribution of the response given the features. As we will shortly demonstrate, the computed
3

---

v), which are defined as Published in Transactions on Machine Learning Research (12/2023)
game-theoretic quantities provide upper and lower bounds to the p-values of their respective tests. This novel connection provides several popular explanation techniques with a well-defined notion of statistical importance, We demonstrate our results with simulated as well as real imaging data. We stress that we do not wish to introduce a novel explanation method for model predictions. Our aim is instead to expand our fundamental understanding of the Shapley value when applied to machine learning models, particularly as its use for the interpretation of predictive models continues to grow (Moncada- Torres et al., 2021; Zoabi et al., 2021; Liu et al., 2021). These novel insights should inform the design of explanation methods to guarantee the responsible use of machine learning models.
2 Background
Before presenting the contribution of this work, we briefly introduce the necessary notation and general definitions. Herein, we will denote random variables and random vectors with capital letters (e.g., X), their realizations with lowercase letters (e.g., X = x) and random matrices with bold capital letters (e.g., X). Let X, be some input and response domains, respectively, such that (X,Y) D is a random sample from an unknown distribution DD over X' x y. We set ourselves within the classical binary classification setting. Given X' C IR",, y = {0, 1}, the task is to estimate the binary response on a sample X by means of predictor f: X' - y that approximates the conditional expectation of the response an input, i.e. (x) 2 B[Y X zr]. We will not concern ourselves with this learning problem. Instead, we assume are given a fixed predictor which we wish to analyze. More preciscly, for an input E IR", we want to understand the importance of the features in x, iee. Ti, with respect to the value of f(x). This question will be formalized by means of the Shapley value, which we now define.
2.1 The Shapley value
In game theory (see, e.g., (Peleg & Sudhölter, 2007)), the tuple ([n), v) represents an n-person cooperative game with players [n] = {l,..... nu and characteristic function v P(n) + Rt, where P(n) the power set of [n]. For any subset of players C S [n], the characteristic function outputs a nonnegative score v(C) that represents the utility accumulated by the players in C. Furthermore, one typically assumes v(0) = 0. A Transfer Utility (TU) game is one where players can exchange their utility without incurring any cost. Given TU game ([n), v), solution concept is formal rule that assigns to every player in the game a reward that is commensurate with their contribution. In particular, there exists a unique solution concept that satisfies the axioms of additivity, nullity, symmetry, and linearity (Shapley, 1951) (see Appendix B for details on the axioms). This solution concept is the set of Shapley values, Φr (m]] (( follows.
Definition 1 (Shapley value). Given an n-person TU game ([n), v), the Shapley value of player j E [n] is
()([m], = Σ we - -ocloCC (5}) r(C)).
(1)
where we = 1/n- ((c)) (( That is, (1[(1, v) is the average marginalized contribution of the jth player over all subsets (i.e., coalitions) of players.
2.2 Explaining model predictions with the Shapley value
Definition 1 shows how to compute the Shapley value for players in a TU game, and is not immediately clear how this would apply to machine learning models. To this end, let f(x) be the prediction of a learned model on a new sample E R" For any set of features C S [n], denote Ie E glCl the entries of in the subset C' (analogously, z E BB- for -C = [m] C, the complement of C). We will refer to
İ = Ixc, X-cl E E.
(2)
as the random vector that is equal to x in the features in C' and that takes a random reference value in its complement -C. Following Lundberg & Lee (2017), we let X be sampled from its conditional distribution
4

---

Published in Transactions on Machine Learning Research (12/2023)
given 20; i.c. X-c Xc zc.3 Note that, in this way, X-c is independent of the response f(x by construction, For the sake of simplicity, we write Xe ~ Dxc=se Then, for a predictor and every subset C C [n], f(Xc) is a random variable whose source of randomness is the random reference value. This way, with abuse of notation, one can define the TU game (x. f), where every feature in the sample x is a player in the game, Therefore, analogous to Definition 1, the Shapley value of feature j E [n] is
0z(2,))=
Σ we (Eff((CCU))) f(Xc)). CC
(3)
We note that (x, f) can be negative, i.c. feature j has an overall negative contribution to the prediction of the model. This differs from the game-theoretical setting where feature attributions are usually considered nonnegative. In the context of explainability, we look for a subset C* S [u] (e.g,, the smallest subset) such that zC- are the observed features that contributed the most towards f(z).
We remark two main differences between the original definition of the Shapley value from game theory (Equation (1)) and its translation to machine learning models (Equation (3)) in common settings: (i) the characteristic function e can predict sets of players, whereas the predictive model f typically has fixed input domain X' C R" (e.g., for a convolutional neural network);" and (ti) the characteristic function v is usually not data-dependent, while in this machine learning setting the model ʃ was trained on samples from a specific distribution D. As a result, given a subset of features C' S [n], one cannot simply predict on the partial input vector #e E IR CI because ((x) is not defined. Instead, the missing features in the complement of C must be masked with a reference value that does not contain any information about the response in order simulate their absence. Furthermore, this reference value must come from the same data distribution D the model was trained on, hence the need to sample from the conditional distribution X-c XCc = IC (Frye et al., 2020a; Aas el al., 2021). Both the need to approximale the conditional distribution as well as the exponential number of summands in Equation (3) make the exact computation of Shapley values intractable in general.
2.3 The Conditional Randomization Test (CRT)
Before introducing our novel conditional independence testing procodure, we provide a brief summary of feature importance from the perspective of conditional independencee Given random variables X,Y, and Z we say that X is independent of Y given Z (succinctly, X TT Y Z) if (X Y, Z) _ (X 2), where á indicates equality in distribution. Put into words, knowing Y does not provide any more information about X in the presence of Z. Recall that for each j E [n], X, E IR is a random variable that corresponds to the tth feature in X, and X-, E R -j = [m] \ {i} is its complement. Then, the CRT procedure by Candes et al. (2018) implements a conditional independence Lest. for the null hypothesis
HRT Y 11 X1 X-
(4)
which can be directly rewritten a
CRT : (X = (Y Xx-)).
(5)
Let x ~ X2 X-j, k 11=1,.. I,.., K be K null duplicates of Xj. x are called nulls because, by construction, they are conditionally independent of the response Y given X-j. Under HCRT for any choice of test statistic T(X,, Y. X-)), the random variables T(X,, T(X,,Y,X-) X.X_)). X. exchangeable (Berrett et al., 2020). Then, DCRT the p-value returned by the CRT is valid: under H > PiPşRT < a] < a, Ya E [0 (see Candes et al., 2018, Lemma F.1). For completeness, Algorithm C.1 summarizes the CRT procedure.
(K), ,Y,_,) are ii.d., hence
Herein, we not touch upon the discussion on obserwational vs. interventional Shapley values, and we refer the interested reader to (Sundararajan & Najmi, 2020; Chen et al., 2020; Merrick & Taly, 2020; Janzing et al., 2020).
"When C = [m]. f f(Xc) is simply the prediction f(z), which is not random. As noted in Jain et al. (2022); Covert et al. (2022); Teneggi et al. (2022b): Deep Sets (Zaheer et al., 2017) and Transformers (Vaswani al., 2017) architoctures do not suffer from this limitation.
6 Note that Equation (5) equivalent F
(X, v,x-,) E (X, x-1)-
5

---

Published in Transactions on Machine Learning Research (12/2023)
3 Hypothesis testing via the Shapley value
Given the above background, will now show that the Shapley value for machine learning explainability (Equation (3) is tightly connected with conditional independence testing. Formally, we present the SHAPley EXplanation Randomization Test (SHAP-XRT): a novel modification of the CRT that thaf-differently from the original motivation in Candes et al. (2018) evaluates conditional independence of the response of a deterministic model f on an individual sample X =,, X ~ Dx. That is, SHAP-XRT, akin to the CRT, provides a permutation- based p-value to test for the conditional independence of two distributions without making any assumptions on the conditional distribution of the prediction of the model, while requiring access to the conditional distribution of the data. Differently from the CRT, the distributions considered by SHAP-XRT are built on top of single observation instead of over a population, and the response is a deterministic function of the input rather than a random variable. As we will present shortly, there is a fundamental difference between the Shapley value and SHAP-XRT; the former computes the average marginal contribution of a feature by differences of conditional expectations, whereas the latter provides a p-value for a test of equality in distribution.
3.1
The Shapley Explanation Randomization Test (SHAP-XRT)
Going back to our motivating example of an automated system in a clinical setting, we would like to deploy ideas of conditional independence testing to report the most important features for the model's prediction on patient. For example, we might be interested in knowing whether the response of the model on a specific patient is independent of age when their blood pressure and weight are collected. This way, we could provide precise statistical guarantees on the generated explanations, such as Type I error control. More precisely, this is equivalent to testing for the independence of the response of a model f on a feature Tj, j E [n]] when the features in IC, C S [m] {i} are observed (e.g., j = age and C = (blood pressure, weight)). We now formalize this question by means of our novel SHAP-XRT null hypothesis.
Definition 2 (SHAPley EXplanation Randomization Test). Let X' T and f: X' + [0, 1] be a fixed predictor for a binary response Y E {0, 1} on an input X E X such that (X,Y) ~D) D. Given a new sample
x= x, X ~ Dx, a feature j E [n]. and subset of features C S [n] \ (i). denote Xc = jrc,X-cl the corresponding random vector where X-c c is sampled from its conditional distribution given X = TC- Then, the SHAP-XRT null hypothesis is
S-RTT f(icu()) - f(Xc).
(6)
H.C.C
Recall that Xout and Xe are random vectors equal to in the features in (U and C, respectively, and that take unimportant random reference values in their complements (Equation (2)). Then, the SHAP-XRT mull hypothesis is equivalent to
(s(XcuGs) ( (Xou))= =ouGs) - (f(Ec))Xee xx==c))
which precisely asks whether the distribution of the response of the model changes when feature j is added to the subset C.
(()) cUG) CUt) R and x(()) E Lxn the random matrices containing I duplicates of Xouts and Xc, respectively, such that Your) = (XCu))) and Ya = f(Xc) are the predictions of the model. Algorithm 1 implements the SHAP-XRT testing procedure and it computes the respective p-value, P). statistic T on the response of the model, e.g. the mean. We now formally state the validity of this test.
How should one test for this null hypothesis? Denote Xouo) = (X xo= (X
....,... (..........
&S-XRT for any choice of test
Theorem 1 (Validity of & Under the null hypothesis H $5.C
S-RRR SR.TRT the p-value returned by the SHAP-XRT procedure-is valid for any choice of test statistic T, i.c. Plp S a) S a, Va E [0.1].
We defer the brief proof to Appendix A.I.
6

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm Shapley Explanation Randomization Test (SHAP-XRT)
procedure SHAP-XRT f: IR" ++ +00, sample x Ii" feature j [n], subset C [n] {i), test statistic T, number of null draws K N, number of reference samples L I4)
Sample X Xougs) ~ ((
Your) + =((cu()))
Compute the test statistic t T(Ycu())
for k 4-1, 1,....,, K do
Sample Xe -Dxc=so)"
(k)
C + f(Xc)
Compute the null statistic ((6) )()
end for
return A (one-sided) p-valuc
X-XTT Pj.
1 [
118
K +1
k=1
end procedure
We remark that the p-value returned by the SHAP-XRT procedure akin to other conditional independence tests is one-sided. Rejecting H implies that in the presence of the features in C, the observed value of feature j is important in the sense that f ((co()) is often larger (i.e., closer to 1), or stochastically greater, than f(Xc). If one desires to reject HSSXET for features whose s(Xcuu)) is often smaller than f(Xc), it suffices to use 1 1-1 in lien of f. Note that the SHAP-XRT procedure encompasses multi-class classification settings where g : R - AM predicts one of M classes and f(x) g(x), m E [M]. Furthermore, H.j.C can be generalized to any predictor f X + y for arbitrary domains, but we consider binary classification in this work.
We stress that contrast with the CRT null hypothesis (Equation (4)), H is defined locally on a specific input rather than over a population. Differently from the Interpretability Randomization Test (IRT) by Burns et al. (2020) (i) HS-XRT asks for the conditional independence of the response with respect to single feature E [n] rather than collection of subsets of features, and (ii) it allows to condition arbitrary subsets C' S [n] \ {5} of features instcad of restricting to C' = -j, i.c. all features but j.
Finally, let us make a remark about the involved distributions. Recall that the SHAP-XRT procedure is defined locally on a sample x. Intuitively, under the null H...C H-XRRT, the distribution of the response of the
model f is independent of zι (the observed value of the jth feature in x) conditionally on Xç = IC. Since f is a deterministic function of its input, it is natural to ask when the random variable ((Xcup) has a degenerate distribution. Suppose that for each C C [m] {i}, X-c Xc = &G is not degenerate (e.g., is not constant), otherwise f f(Xou()) is trivially degenerate. For -j (i.c., all features but the 7th onc), Xcutst because C' = [m] by definition of the complement set -(C (i}) is empty, ie. no reference value is sampled. Tt. follows that for this choice of C, s(Xout)) is point mass at f(x), and SHAP-XRT retrieves the IRT procedure (Burns et al., 2020).
3.2 Connecting the Shapley value and the SHAP XRT conditional independence test
We now draw precise connection between the SHAP-XRT testing procedure and the Shapley value for machine learning explainability. This novel relation furthers our fundamental understanding of Shapley-based explanation methods, and, importantly, clarifies under which conditions one can (and cannot) make statistically valid claims about feature importance. We stress that-as as we will discuss- this conditional independence interpretation is not intended to overcome the well-known computational limitations of the Shapley value replace existing methods. Rather, it offers previously overlooked perspective, and it.
7

---

Published in Transactions on Machine Learning Research (12/2023)
suggests new strategies develop more powerful, statistically well-grounded alternatives. To begin with, let T in the SHAP-XRT procedure be the identity and set 1= 1 (we will discuss the effect of L. on our results later). Then, for a sample 2, feature j E [ml, and a subset C' S [m]] \ {i), the SHAP-XRT test and null statistics become = ff f(Xcu()) and i == f(Xc), respectively. Denote
3 = ((oum))-
(8)
the random marginal contribution of feature j to the subset C such that P
PJ.
EEp L and
SHAP 1AC
= ,
(9)
are the expected p-value of the SHAP-XRI procedure and the expected marginal contribution, respectively. Note the expectations are over both Xeu(j) and Xe. This is to take into account the randomness in the draw of test statistic t. Then, it is easy to see that the Shapley value of feature j can be rewritten as
SHAP $1(2,)== = E WC 3.0
(10)
CEM))
S-XRT We now show that each summand SHAP can be used to construct both upper and lower bounds to Pj.C 1.C
Theorem 2. Let X C R", and f X + [0.1] be fized predictor for binary response Y E {0.1) on an imput X E X such that (X,Y)= ~ D. Given a sample = x, X ~ Dxx, a feature j E [n], and a subset C C [m] \ Li, define Nj == [(Xouts)) - s(Xc) such that Pj.C p = E and SHAP = [[[T,c]] Then, 75.C
K
0 S Pj.C
S-XRT
S
K + 1
1.C
SHAP
(11)
and furthermore, if 3,0 < 0
SHAP
K + (1+ SHAPP) S
S-XRT Pj,C
$
(12)
where K 22. 1 is the number of draws of null statistic in the SHAP-XRT procedure.
We defer the proof of this result to Appendix A.2. We note that the theorem above is presented in expectation, and an analogous saipee result can be derived by means of concentration inequalities by estimating Yj.C with an empirical mean (as long as it is computed over samples independent of f)- We now discuss the meaning of Theorem 2 and its behavior as function of K and L in the SHAP-XRT procedure, i.e. the number of draws of null statistic and the number of random reference values sampled al each iteration, respectively.
Behavior of Equations (11) and (12) as a function of K. As K - oo, i.c. as the number of draws of mull statistic the SHAP-XRT procedure goes to infinity, K/(K + +1) - 1, and Equations (11) and (12)
become
0 <
8-XRT P3.C
< 1 - 7/.C
11-70
SHAP
and
SHAP < (15,0
S-XRT 1 P/.C
(13)
respectively, Furthermore, we remark that the coefficient K((K+1) in the bounds above is a mild requirement in practical scenarios. In particular, in order to expect to reject H-RXRT
0.j.C at level a for SHAP = 1, it suffices 72,0
for K to grow as (1 aa/a (e.g, a = 0.05 = K 1219).
Bchavior of XS-XRT as a function of L. Rocall that the number of samples of reference values over which the test and null statistics are computed in the SHAP-XRT procedure. So far, we presented our results for L = 1 and T being the identity. These choices were instrumental for showcasing the connection between the SHAP-XRT test and the Shapley value. Here, we discuss the behavior of the SHAP-XRT p-value as L increases. First note that if L > 1, the test statistic T cannot simply be the identity because T is function that maps RL + R. The SHAP-XRT procedure is valid for any choice of test statistic, T, and so for L>> 1, choices of mean, median, quantile, max, etc, are all valid. For example, let T be the mean and in the limit SHAP >0] 11 I. xc, 1 E.f( (X and ī E[f(Xc)]- Then, 5S-XRT (1/(K 1))
8

---

Published in Transactions on Machine Learning Research (12/2023)
Pice1-9i We
Pic Yic
0.5
0.0 -/3
Figure 1: Pictorial representation of the upper and lower bounds f as function of SHAP in Theorem 2 (as K + oo). For critical level a (e.g., = 0.20 in the figure) the bounds indicate under what conditions one can expect to reject, or to fail to reject, the mull hypothesis HS-XRT by means of SHAP. #0.C
13 described
1gC0"
The result above provides a novel understanding of the Shapley value from SHAP conditional independence testing perspective. In particular, it shows that each summand Tj.C (i.e., the expected marginal contribution of leature to subset C)) in the Shapley value of feature j provides a lower and an upper bound to рj,C S-XIT the expected p-value of its corresponding SHAP-XRT test (i.e., the test which asks whether the distribution of the response of the model is conditionally independent of j when the features in C' are present). Until now, it was unclear whether the marginal contributions carried any statistical meaning. Theorem preciscly characterizes under which conditions one can (and cannot) use them to make statistically valid claims about feature importance. In particular, given a critical level a in the SHAP-XRT test, we can identify three separate conditions:
Implications of Theorem 2
SHAP > 1 - a) can provide sufficient evidence against the null 1. large positive contributions (i.e., 1j.C' hypothesis H.j.C and
expect to reject it.
SHAP - ava) cannot provide sufficient evidence against the mull 2. large negative contributions (i.e., 1j hypothesis Hoj.C and so one should not expect to be able to reject it.
3. small contributions (i.e., - SHAP make any statistically valid claims.
I ,,CC
S ax) are noninformative, and so one cannot expect
Figure 1 illustrates the bounds (when K + oo) and the three regimes described above.
3.3 The Shapley value as a global hypothesis test
The results presented so far study the statistical meaning of each summand (i.e., contribution) the Shapley value. However, the overall Shapley value and not just its individual summands is used in practice to explain model predictions. Since every summand is linked to the p-value of specific local hypothesis test, a naive approach would be compare all p-values to level a, where rejecting at least one hypothesis implies feature j is important with respect to some subset C' S [n] \ (i). However, this approach is known to inflate the Type error, and corrections are required (i.e., Bonferroni correction (Shaffer, 1995)). Instead, we ask whether the Shapley value is inherently linked to a global hypothesis test.? 7 If so, what is the null hypothesis of this test? and what notion of importance does convey? We now move onto answering these questions, for which we first introduce the definition of a global hypothesis test.
Given k null hypotheses Ho......, Ho, with their respective p-values pi, PE, the global null hypothesis is defined as Hg = n Ho,; and it is true if and only if every individual null hypothesis is true (Hommel, 1983). Several classical procedures exist for global hypothesis lesting, both based on the ordering of the p-values of the individual tests (Hommel et al., 2011) and on ways of combining them (Tippett et al., 1931; Pearson, 1933; Fisher, 1948). More powerful alternatives have been recently proposed to overcome some of the limitations of these long- esndssssall methods, and, importantly, make no assumptions the dependency structure of the individual vavuuu (Heard & Rubin-Delanchy, 2018; Futschik et al., 2019; Wilson, 2019; Vovk & Wang, 2020; Liu & Xie, 2020).
Here, the global is used according its meaning in the statistical theory literature, and not in the machine learning explainability literature.
9

---

Published in Transactions on Machine Learning Research (12/2023)
With the above background, now show how to aggregate all SHAP- -RTT tests for feature j E [n]] into global SHAP-XRT null hypothesis test, provide a valid p-value for it, and finally highlight its relation to the Shapley value of feature j. Recall that there exists a SHAP-XRT test with null hypothesis O,3.C' C [n] {j}. Using all these tests, we can define the global null hypothesis
HS-RRT for each
Ho. = n
S-XRT
(14)
CEMNG
which is false as soon as one of the b.j.C hypotheses is false. Put into words, rejecting Ho. implies that feature j is important (i.e., it has effect the distribution of the response of the model) with respect to at least one subset C [n] (j}. This way, Ho.; tests for global notion of importance of feature j over all possible conditioning subsets. We remark that this is possible precisely because from other conditional independence tests allows to condition on arbitrary subsets of features. We now provide a valid p-value for this global test.
Lemma 1. In the setting of Definition 2, and under the global null hypothesis Ho.j (Equation (14)) the random variable
PJ =
Σ
Wc
(15)
CCMIV(
is a valid p-value, i.e. Plβ S sa, Ya 1].
This statement follows directly from (Vork & Wang, 2020, Proposition 9) and its proof is included Appendix A.3. We remark that the choice of weights not unique as long as they belong lo the simplex. Here, we use the same weights as the Shapley value's (i.e., uniform distribution over all possible subsets), as this will allow us show that overall Shapley value of feature indeed provides an upper bound to the expected p-value for the global SHAP-XRT test. Alternative weighting finetions-whie semivalues (Dubey et al., 1981; Wang & Jia, 2023) and random order values (Frye et al., 2020b) subject of current research (Kwon & Zou, 2022) and we consider the study of their statistical meaning as future work.
give rise to
Corollary 1. Denote Pj- = E[py] the expected p-value for the global null Ha.j. Then,
Pj S 2 (1 (1-11111 K K+1 (1(.))))
K
(16)
where (I, is the Shapley value of feature j [m].
The proof is included in Appendix A.4. This result shows that the Shapley value itself, and not only its summands, provides an answer to statistical test. A straightforward implication of this result is that, given desired significance level a, one can expect to reject Ho., when (z, 2 / )). In simple terms,
large positive Shapley value, (5(x. f) z 1, implies that there exists at least one C C [m] \ {i} for which S-RT is small and HS O.j.C. is expected to be rejected. This result grants the Shapley its expected p-value, Po...C value statistical meaning by demonstrating that is linked to a global hypothesis test.
The natural questions that remain are then: (i) when ( f) R 1 which tests, amongst. NogIMN HS-XRT U.j.C are being rejected? and (M) similarly, do large negative Shapley values, dy(x, f) s -1, carry any statistical meaning? We answer these questions with the following corollary in a similar fashion to Theorem 2.
Corollary 2. For feature j E [n], if 0, f) 2 - CE (0,1), then AC S [n] (1)
S-XRT FGC
<
K
T -
(17)
K +
where w- minegia/V) we. Farthermore, if 0z f) < -1 with w, then VC S [m] \ {
1
1+K (E-
S-XRT Pj.
(18)
K 1
10

---

Published in Transactions on Machine Learning Research (12/2023)
pfc Mi
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
02:- -
-x-
0.0
0.0
Yic 0.8
0.6
1.0
-0.4
-0.2
Vic
(a)
(b)
Figure 2: Demonstration of the upper and lower bounds of XRT for the test H.J.C =(Xcu())) f(Xc)
Pj.C" with j 1, C = {3, 4, 5, 6} for the known response function experiment. (a) Displays the upper bound with 02 = 2 for all samples with Y3Cc 2 0. (b) Displays the lower bound with 82 = -2 for all samples with 7/,C < O.
The proof is included in Appendix A.5, and we now provide few remarks. Firstly, Corollary 2 grants large positive (i.e, (I. f) f)()) s 1) and large negative (i.e., Ø, (z, f) ~ -1) Shapley values with statistical meaning. Recall from Corollary that one can expect to reject the global null Ho, for large positive values of (y f)- This means that al least one of the SHAP-XRS null hypotheses of feature j is expected to be false. In other words, there exists at least one subset C S [n] {i} such that j affects the distribution of the response of the model when the features in C are present. Corollary 2 makes this statement more precise. In fact, it shows that all SHAP-XRT tests needs to have small p-values, and one should expect to reject all tests. Symmetrically, it shows that for large negalive Shapley values, one cannot expect to reject any SHAP-XRT null hypothesis for feature j. That is, feature j does not contribute to the distribution of the response of the model given any subset C' S [>]] {/}-
Secondly, Corollary offers a statistical interpretation of the exponential cost of the Shapley value. Note that for the upper bound in Equation (17) not to be vacuous (i.e., less than 1) and for the lower bound in Equation (18) to hold (i.e., all contributions be negative), e must be smaller than w (i.e., w-e - 6 w for Equation (17), and w for Equation (18) by construction). For features, the weights we in the Shapley value assign uniform distribution over all possible 2 subsets C C [ni] \ (j}. It follows that w is = 0( (-=)) n4772 ) by Stirling's approximation. Then, e needs to decay exponentially fast with n for the bounds to be informative. This is a well-known limitation of the Shapley value in practical high-dimensional settings. We remark that studying under which settings the computational cost of the Shapley value can be reduced is subject of ongoing research that is orthogonal to the contribution of this paper (Chen et al., 2019; Lundberg et al., 2020; Teneggi et al., 2022a). Rather, Corollary 2 shows the statistical implications of the exponential number of subsets one needs to account for when computing the Shapley value of feature j.
the inverse of the central binomial coefficient, i.e. w = ((=))
Finally, Corollaries and 2 open the door to variations of the Shapley value inspired by more sophisticated and powerful ways of combining p-values other than averaging, which may provide more effective in practice while guaranteeing false positive rate control. We consider these potential extensions part of future work.
4 Experiments
We now present three experiments, of increasing complexity, that showcase how the SHAP-XRT procedure can be used in practice to explain machine learning predictions, contextualizing the Shapley value from a statistical viewpoint. All code to reproduce experiments will be made publicly available.
Known response function We first study a case where both the distribution of the data and the ground- truth function are known. Let E N such that X' C 2d and denote X = _X Xa] E Rdd the concatenation of vectors X, = 1..,1.X,,3) E IR? We define the ground-truth function f(X) = S(0T x) where $ is the sigmoid function R and 0 [8,, ....................... A2dl E 2d For E [d), Xt,1 ~ ~N(1, 1) and X ~ ~N(3, 1/4) if X,, >3 3 and 1)), otherwise. We set =3 and let. 0 12d with the exception that 0g 2. We concern ourselves
with the mull hypothesis H8-XRT, f(Xcu()) d f(Xc) with j (1,2) and C = ((2, 1), 2). (3, 1), (3.2)).
8 ((()) = 1/(1+6-))
11

---

Published in Transactions on Machine Learning Research (12/2023)
Model
CNN
Power at = -0.05
0.8
FCN
0.6
0.4
0.2
0.0
10a
104
10a
1/6P
1/d (b)
1/d-10 2/0-12
m
a
(a)
Figure 3: Estimation of the power of 1 - C C at level 0.05 for a simple CNN and a simple FCN on a synthetic dataset of images. (a) Displays power as a function of the number of samples m used for training, with fixod
noise level o² 1/d2, while (b) shows power as function of the level of the noise in the test dataset while training
320 x 10 samples with fixed noise level o² = 1/d2. We set K = 100 x 100 and L = 1 in the SHAP-XRT procedure.
That is, we are aiming to detect when X1,2 (i.e., feature j = (1) increases the value of f(X (Xcut)t relative to f(Xc) in the presence of (X2,X3) (i.e., the features in C {2,, (2, 2), (3, 1), (3, (3)2) Using the SHAP for 1000 samples. In Figure 2a, SHAP and display the upper bound for all samples with SHAP 2 O, we plot XRR as a function of 7g,C
SHAP-XRT procedure with K = 100, we calculate P and 1/.C
7,
K SHAP To demonstrate the validity of the lower bound, we keep the experiment the same U =1 K+I 7jC
except that now 8₂ 2. In Figure 2b, for all samples with 7, SHAP 0, we plot Pi,C S-RRT as function of 1
SHAP and display the lower bound Fj,C S.XIT = र+W (1+ (7,55)A)))) Figure F.3 shows the gap between performing conditional independence (esting by means of marginal contributions (7 SHAP) SHAP-XRT p-values (f),C as a function of the significance level a by estimating P
SHAP 2 21-a a S-XRT < a).
Synthetic image data We now present a case where the distribution of the data is known, but we can only estimate the response through some learned model. Let X' C Rdrxds d, E N be images composed of an r x 8 grid of non-overlapping patches of d x d pixels, such that Xi, E Rdxd is the patch in the (th-row and jthlcolumn. We consider a synthetic dataset of images where the response Y E {0, is positive if the input image X E Re contains at least one instance of a larget signal Io E Rdxd Denote images in dxd as vectors in IR,, D = d, and let v ~ NO0 o2ID) be random noise. Define an important distribution I Hp + e for some target signal Fo E IR. and its unimportant complement I = u, such that XL, aij" I + (1 az,)) Ie and aij ~ Bernoulli()) are independent Bernoulli random variables with parameter 17. Then, (X) = = 3(i,5) E [r] x [s] Xi, I. In particular, we let d 7, y= = and zo be cross (an example is presented in Figure F.l.). Furthermore, we set 17 7 1 (1/2) such that P[Y = 0] = P = 1] 1/2. Figure F.1 shows some example images and their respective labels for different noise levels 2²_ We train a Convolutional Neural Network (CNN) and a Fully Connected Network (FCN) to predict the response Y (see Appendix D.1 for further details). Recalling that the power of a test is defined as 1 8 Pfreject Ho Ho is false], we estimate the power of performing conditional independence testing via Shapley coefficients at a chosen level a by evaluating IP[ - ((.).c S a HS-XRR (,(e.)). is false] on a test dataset of 320 samples. We remark that HSSXRT (. is false for all patches Xi,j I such that V(i',j") E C, X(y'nne Is. Figure 3 shows an estimate of the power of 1 -Y.J).c for both models as a function of number of samples shown during training (Figure 3a), and noise in the test data (Figure 3b) over 5 independent training realizations.
Real image data Finally, we revisit an experiment from Teneggi et al. (2022a) the BBBC041 dataset (Ljosa et al., 2012), which comprises 1425 images of healthy and infected human blood smears of size 1200 x 1600 pixels. The objective of this experiment is to showcase how Theorem 2 translates to real-world scenario where the same object of interest receives two different Shapley values, and how this affects the p-values of the individual SHAP-XRT null hypotheses. Here, the task is to label positively images that contain at least one trophozoite- an infectious type of cell. We apply transfor-learning to a ResNet18 (He et al., 2016) pretrained on ImageNet (Deng et al., 2009) (see Appendix D.2 for further details). After training, our model achieves a validation accuracy greater than 99%. Computing the exact Shapley value for each
12

---

Published in Transactions on Machine Learning Research (12/2023)
Inpur Image
Input Image
(1,3)
(1.90
(2.4)
(4 (1.2
3.
11,2
(a)
(b)
Figure Demonstration of Shapley value (Øj) and the p-values of their respective hypothesis tests, PyC,, for two images of the BBBC041 dataset. Here, each feature is a quadrant, and important regions are those containing trophozoites (indicated by ground-truth green bounding box).
pixel is intractable, hence we take approach similar to that of h-Shap (Teneggi et al., 2022a) and define features quadrants in order to compute the p-value of each SHAP-XRI mull hypothesis. Since there are 4 quadrants, cach Shapley value (øj) comprises only 8 marginal contributions (15.c) that can be computed exactly without any need for approximation. We extend the original implementation of h-Shap to return the SHAP-XRT tests that reject (or fail to reject) their respective mulls, thus assigning a collection of p-values to every quadrant. We note that this experiment, we use the unconditional expectation over the training set mask features-as it commonly done popular Shapley-bard caaplcy-basod explanation methods. Figure F.2 shows the reference value used for masking and some example masked inpuls. Figure presents the two examples. The first, Figure 4a, depicts case where there exists only 1 cell in the upper right quadrant, i.e. 2. Thus, this quadrant receives a Shaplcy value Φ2 ~ 1. Naturally, all p-values are approximately zero (as also guaranteed by Corollary 2). This implies that the quadrant j = 2 is statistically important in the sense that all SHAP-XRT null hypotheses are rejected. On the other hand, in Figure 4b, there are two quadrants that contain sick cells, i.e. j = 3, 4, and d3 R 04 R 0.5 by symmetrr. Based on our theoretical results, Φa and 6e can be decomposed in the sum of terms that bound the p-values of their respective SHAP-XRI tests. As can be seen, j 4 is indeed statistically important in that half of the null hypotheses are rejected (i.c., all tests 0,4.C such that & C). However, the bound in Corollary shows that Shapley value of 04 R 0.5 is not large enough to reject the global null Ho.4 even if it is clearly false. These results highlight the suboptimality of the Shapley value from a statistical testing perspective, which motivates future work to develop more powerful alternatives. We expand on this experiment in Appendix E.
5 Conclusion
The Shapley value and conditional hypothesis testing appear as two unrelated approaches to local (i.e., sample specific) interpretability of machine learning models. In this work, we have shown that the two are tightly connected in that the former involves the computation of specific conditional hypothesis tests, and that every summand in the Shapley value can be used to bound the p-values of such tests. For the first time, this perspective grants the Shapley value with precise statistical meaning. We presented numerical experiments synthetic and real data of increasing complexity to depict our theoretical results in practice. We hope that this work will enable the further and precise understanding of the mcaning of (very popular) game theoretic quantities in the context of statistical learning. Restricting the Shapley value to an a-priori subset of null hypotheses may prove successful in devising useful algorithms in certain scenarios, and alternative ways other than the weighted arithmetic mean which is employed by the Shapley value may yield powerful procedures combine SHAP-XRT's piii'sppvee valuus to test for global null hypotheses.
Acknowledgments
The authors thank the anonymous reviewers who helped improve the clarity and presentation of this manuscript. This research was supported by the NSF CAREER Award CCF 2239787. Y. R. was supported by the Israel Science Foundation (grant No. 729/21). Y. R. also thanks the Career Advancement Fellowship, Technion, for providing research support.
13

---

Published in Transactions on Machine Learning Research (12/2023)
References
Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features dependent: More accurate approximations to shapley values. Artificial Intelligence, 298:103502, 2021.
Julius Adebayo, Justin Gilmer, Michael Muelly, lan Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in neural information processing systems, 31, 2018.
Thomas Berrett, Yi Wang, Rina Foygel Barber, and Richard Samworth. The conditional permutation test for independence while controlling for confounders. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(1):115-197, 2020.
Rajendra Bhatia and Chandler Davis. A better bound on the variance. The american mathematical monthly, 107(4):353-355) 2000.
Avrim Blum and Pat Langley. Selection of relevant. features and examples in machine learning. Artificial intelligence, 271-2)):44-- 1997.
Michael Bücker, Gero Szepannek, Alicja Gosiewska, and Przemyslaw Biecek. Transparency, auditability, and explainabilily of machine learning models in credit scoring. Journal of the Operational Research Suciely, 73 (1):70-90, 90, 2022.
Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, pp. 47 57, 2020. Collin Burns, Jesse Thomason, and Wesley Tansey. Interpreting black box models via hypothesis testing.
Emmanuel Candes, Yingying Fan, Lucas Janson, and Jinchi Lv. Panning for gold: 'model-x' knockoffs for high dimensional controlled variable selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(3):551-55) 2018.
Bryan Casey, Ashkon Farhangi, and Roland Vogl. Rethinking explainable machines: The gdpr's' right to explanation dobate and the rise of algorithmic audits in enterprise. Berkeley Tech. LJ, 34:143, 2019.
Hugh Chen, Joseph D Janizck, Scott Lundberg, and Su-In Lec. True to the model or true to the data? arXiv preprinl 200: 1 16234, 2020.
Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. Algorithms to estimate shapley value feature attributions. Nature Machine Intelligence, pp. 1-12, 2023.
Jianbo Chen, Le Song, Martin J Wainwright, and Michael Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. arXie preprint arXiv:1006 180.00060,,,, 2018.
Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. In International Conference on Learning Represenlations, 2019.
Shay Cohen, Gideon Dror, and Eytan Ruppin. Feature selection via coalitional game theory. Newral Computation, 19(7):1939-13)) 1961, 2007.
lan Covert, Scott M Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. Advances in Neural Information Processing Systems, 33:17212-17223, 2020.
Ian Covert, Scott Lundberg, and Su-In Lee. Explaining by removing: A unified framework for model explanation. Journal of Machine Learning Research, 22(209):1 90, 2021.
Ian Covert, Chanwoo Kim, and Su-In Lee. Learning to estimate shapley values with vision transformers. arXiv preprint arXiv:2206. 05282, 2022.
Bernardo de Almeida, Franziska Reiter, Michacla Pagani, and Alexander Stark. Decpstarr predicts enhancer activity from dna sequence and enables the de novo design of synthetic enhancers. Nature Genetics, 54(5): 613 62-, 2022.
14

---

Published in Transactions on Machine Learning Research (12/2023)
Lara Marie Demajo, Vince Vella, and Alexici Dingli. Explainable ai for interpretable credit scoring. arXiv preprinl ar Xrx::2002. 037449, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 255, leee, 2009.
Pradeep Dubey, Abraham Neyman, and Robert James Weber. Value theory without efficiency. Mathematics of Operalions Research, ((1):122-128) 1981.
R. A. Fisher. Questions and answers. The American Statistician, 2(5):30 31, 1948. ISSN 00031305. URL http:///www..jsoorr orttsrree/eaab//1165.......
Ruth C. Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful perturbation. In Proceedings of the IEEE international conference on computer vision, pp. 3429-3437, 2017.
Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and llya Feige. Shapley explainability on the data manifold. arXiv preprint arXiv:2006.012: 2020a.
Christopher Frye, Colin Rowat, and Nya Feige. Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability. Advances in Neural Information Processing Systems, 33:1229 1239, 2020b.
Daniel Fryer, Inga Strümke, and Hien Nguyen. Shapley values for feature selection: The good, the bad, and the axioms. IEEE Access, 9:144352 411443222-4460,, 2021.
Andreas Futschik, Thomas Taus, and Sonja Zehetmayer. An omnibus test for the global null hypothesis. Statistical methods in medical research, 28(8)22292-200) 2019.
Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In International Conference on Machine Learning, pp. 3535 3544. PMLR, 2020.
Isabelle Guyon and André Elisseeff. An introduction to variable and feature selection. Journal of machine learning research, 3 -182, 2003.
Philipp Hacker, Ralf Krestel, Stefan Grundmann, and Felix Naumann. Explainable ai under contract and tort law: legal incentives and technical challenges. Artificial Intelligence and Law, 28(4):415-430) 2020.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on compuler vision and pattern recognilion, pp. 770 778, 2016.
Nicholas A Heard and Patrick Rubin-Delanchy. Choosing between methods of combining-values Biometrika, 105(1):239 246, 2018
Gerhard Hommel. Tests of the overall hypothesis for arbitrary dependence structures. Biometrical Journal, 25(5):423-49)) 1983.
Gerhard Hommel, Frank Bretz, and Willi Maurer. Multiple hypotheses testing based on ordered p values a historical survey with applications to medical research. Journal of biopharnaceutical statisties, 21(4): 595 609, 2011.
Giles Hooker. Generalized functional anova diagnostics for high-dimensional functions of dependent variables. Journal of Computational and Graphical Statistics, 16(3):709 732, 2007.
Saachi Jain, Hadi Salman, Eric Wong, Pengchuan Zhang, Vibhav Vineet, Sai Vemprala, and Aleksander Madry. Missingness bias in model debugging. arXiv preprint xrXiv:2204088945, 2022.
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013.
15

---

Published in Transactions on Machine Learning Research (12/2023)
Dominik Janzing, Lenon Minories, and Patrick Blöbaum. Feature relevance quantification in explainable ai: A causal problem. In International Conference on artificial intelligence and statistics, pp. 2907-2911 PMLR, 2020.
Peng-Taa Tao Jiang, Chang-Bin Zhang, Qibin Hou, Ming-Ming Cheng, and Yunchao Wei. Layercam: Exploring hicrarchical class activation maps for localization. IEEE Transactions on Image Processing, 30:5875-5888, 2021.
Margot E Kaminski and Gianclaudio Malgieri. Algorithmic impact assossments under the gdpr: producing lalti-layered explanations. International Data Privacy Law, pp. 19-28, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprint wrXix:142.69880 2014.
Stefan Kolck, Duc Anh Nguyen, Ron Levie, Joan Bruna, and Gitta Kutyniok. Cartoon explanations of image classifiers. arXiv preprint ar 1..:22100003488 2021.
Stefan Kolck, Duc Anh Nguyen, Ron Levie, Joan Bruna, and Gitta Kutyniok. A rato-distortion framework for explaining black-box model decisions. In International Workshop Extending Explainable Al Beyond Deep Models and Classifiers, pp. 91-115. Springer, 2022.
Yongchan Kwon and James Zou. Weightedshap: analyzing and improving shapley based feature attributions. arXiv preprint ar arx::2200 19429, 2022.
Yann LeCun, Yoshua Bengio, and GeofTrey Hinton. Deep learning. nature, 521 521(7553):438 444, 2015.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-frre predictive inference for regression. Journal of the American Statistical Association, 113(523):1004- 1111, 2018.
Molei Liu, Eugene Katsevich, Lucas Janson, and Aaditya Ramdas, Fast and powerful conditional randomization testing via distillation. Biometrika, 109 -233, 2022.
Ruishan Liu, Shemra Rizzo, Samuel Whipple, Navdeep Pal, Arturo Lopez Pineda, Michael Lu, Brandon Arnieri, Ying Lu, William Capra, Ryan Copping, et al. Evaluating eligibility criteria of oncology trials using real-world data and ai. Nature, 502(7855):629-633 2021.
Yaowu Liu and Jun Xic. Cauchy combination test: a powerful test with analytic p-value calculation under arbitrary dependency structures. Journal of the American Statistical Association, 115(529):393 402, 2020.
Vebjorn Ljosa, Katherine Sokolnicki, and Anne Carpenter. Annotated high-throughput microscopy image sets for validation. Nature methods, 9(7):637-637, 2012.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, 2(1):56-66 67, 2020.
Sisi Ma and Roshan Tourani. Predictive and causal implications of using shapley value for model interpretation. Tn Proceedings of the 2020 KDD Workshop on Causal Discovery, pp. 23 38. PMI.R, 2020.
Luke Merrick and Ankur Taly. The explanation game: Explaining machine learning models using shapley values. In Machine Learning and Knowledge Extraction: 4th IFIP TC 5, TC' 12, WG 8.4, WG 8.9, WG 12.9 International Cross-Domain Conference, CD-MAKE 2020, Dublin, Ireland, August 25-28, 2020, Proceedings 4, pp. 17 38. Springer, 2020.
Arturo Moncada- Torres, Marissa van Maaren, Mathijs P Hendriks, Sabine Siesling, and Gijs Geleijnse. Explainable machine learning can outperform cox regression predictions and provide insights in breast cancer survival. Scientific Reports, 11(1):1-13, 2021.
16

---

Published in Transactions on Machine Learning Research (12/2023)
Edoardo Mosca, Ferene Szigeti, Stella Tragianni, Daniel Gallagher, and George Louis Groh. Shap-based explanation methods: A review for nlp interpretability. In COLING, 2022.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Ieml, 2010.
Tuan- Binn-Binhhaa Nguyen, Jérôme-Alexe Chevalier, and Bertrand Thirion. Ecko: Ensemble of clustered knockoffs for robust multivariate inference on firr data. In International Conference on Information Processing in Medical Imoging, pp. 454 466. Springer, 2019.
Art B Owen and Clémentine Prieur. On shapley value for measuring importance of dependent inputs. SIAM/ASA Journal on Uncertainty Quantificution, 5(1):986 1002, 2017.
Guillermo Owen. Game theory. Emerald Group Publishing, 2013.
Raymond EAC Paley and Antoni Zygmund. On some series of functions,(3) In Mathematical Proceedings of the Cambridge Philosophical Society, volume 28, pp. 190-205. Cambridge University Press, 1932.
Karl Pearson. On method determining whether a sample of size n supposed to have been drawn from a parent population having known probability integral has probably been drawn at random. Biometrika, pp. 379-410, 1933.
Bezalel Peleg and Peter Sudhölter. Introduction to the theory of cooperative games, volume 34. Springer Science Business Media, 2007.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 'why should i trust you?" explaining the predictions of any classifier. Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135 1144, 2016.
Benedek Rozemberezki, Lauren Watson, Péter Bayer, Hao-Tsung Yang, Olivér Kiss, Scbastian Nilsson, and Rik Sarkar. The shapley value in machine learning, arXiv preprint (kki::2202:0559, 2022.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206 215, 2019.
Ramprasaath Selvaraju, Michael Cogswell, Abhishok Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based based localization. In Proceedings of the IEFE international conference computer vision, pp. 618-626 6266 2017.
Matteo Sesia and Tianshu Sun. Individualized conditional independence testing under model-x with hetero- gencous samples and interactions. arXiv preprint arXio:2205. 00655, 2022.
Matteo Sesia, Stephen Bates, Emmanuel Candès, Jonathan Marchini, and Chiara Sabatti. False discovery rate control in gedomo-wide association studies with population structure. Proceedings of the National Academy of Sciences, (18(44)):11008811118 2021.
Juliet Popper Shaffer. Multiple hypothesis testing. Annual review of psychology, 46(1):561-584, 1995.
Harshay Shah, Prateek Jain, and Praneeth Netrapalli. Do input gradients highlight discriminative features? Advances in Neural Information Processing Systems, 34, 2021.
Lloyd Shapley. Notes on the N-person Game Rand Corporation, 1951.
Donghee Shin. The effects of explainability and causability on perception, trust, and acceptance: Implications for explainable ai. International Journal of Thanan-Computer Sludies, 146:102551, 2021.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference on machine learning, pp. 3145-300 3153. PMLR, 2017.
Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International conference machine learning, pp. 9269 9278. PMIR, 2020.
17

---

Published in Transactions on Machine Learning Research (12/2023)
Wesley Tansey, Victor Veitch, Haoran Zhang, Raul Rabadan, and David M Blei. The holdout randomization test for leature selection in black box models. Journal of Compulational and Grophical Stalislics, 31 (1): 151 151-162, 2022.
Jacopo Teneggi, Alexandre Luster, and Jeremias Sulam. Fast hierarchical games for image explanations. IEEE Transactions Pattern Analysis and Mochine Intelligence, pp. 1-11, 2022a. doi: 10.1109/ 10.1109/TPAMI. TPAMI. 2022.3189849.
Jacopo Teneggi, Paul H Yi, and Jeremias Sulam. Weakly supervised learning significantly reduces the number of labels required for intracranial hemorrhage detection head ct. ar preprinl. 1rX1v:221.119924 2022b.
Leonard Henry Caleb Tippett et al. The methods of statistics. The Methods of Statistics., 1931.
Richard Tomsett, Dave Braines, Dan Harborne, Alun Preece, and Supriyo Chakraborty. Interpretable to whom? a role-based model for analyzing interpretable machine learning systems. ar preprint 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkorcit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Atlention is all you need. Advances in newral information processing systems, 30, 2017.
Isabella Verdinelli and Larry Wasserman, Decorrelated variable importance. arXiv preprint arXiv:2111.108. 2021.
Isabella Verdinelli and Larry Wasserman. Feature importance: closer look at shapley values and loco. arXiv preprint 2cXit:2303.05981 2023.
Vladimir Vovk and Ruodu Wang. Combining p-values via averaging. Biometrika, 107(4):791-805 2020.
Jiachen Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In PMLR, 2023.
International Conference on Artificial Intelligence and Statistics, pp.
David S Watson, Joshua O'Hara, Nick Tax, Richard Mudd, and Ido Guy. Explaining predictive uncertainty with information theoretic shapley values. arXiv preprint arXiv:2306.00 230.5230 2023.
Danicl J Wilson. The harmonic mcan p-value for combining dependent tests. Proceedings of the National Academy of Sciences, 116(4):1155-1200, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in newral information processing systems, 30, 2017.
Carlos Zedník. Solving the black box problem: a normative framework for explainable artificial intelligence. Philosophy Techsnoloyy, 34(2):265 288, 2021.
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2921 2929, 2016.
Yazeed Zoabi, Shira Dezi-Rozov, and Noam Shomron. Machine learning- based prediction of covid-19 diagnosis based on symptoms. npj digital medicine, 4(1):1-5, 2021.
18

---

Published in Transactions on Machine Learning Research (12/2023)
A Proofs
We briefly summarize the notation used in this section. Recall that f: R" - [0, 1] is a fixed predictor for a binary response Y E {0,1} on some input X R= for an unknown distribution D such that (X, ~ D. For a sample X = 2, X Dx and each subset C S [x] denote Xc = (rc,X-c) E IR' the random vector that agrees with x in the features in C and that takes a reference value sampled from its conditional distribution X-c Xc øc in its complement -C [n] \ C. For brevity, we write Xc Dxc=xc Finally, for feature [n], and a subset C [n] \ {i} denote
T = ((Xcun)) s(Xc)
(19)
the random marginal contribution of feature j to subset C such that
S-XRT PJC
E
S-XRT
and
SHAP 7j.C
= 3T,]
(20)
are the expected p-value of the SHAP-XRT procedure and the expected marginal contribution, respectively.
A.1 Proof of Theorem 1
Here, we show that the p-value returned by the SHAP-XRT procedure is valid, i.c. under H-XXRT P S a Va E 10.
Proof. Recall that given sample X= = x, X ~ Dx, a feature E [n], and subset C' S [n] (i), the null hypothesis of the test is
S-RTT D.C.C
f(Xcu(() _ f(Xc).
(21)
Denote X Xouti), X the random matrices containing L 2 1 duplicates of Xout) and Xc, respectively, such that You() = f( ((Xc(()) and Ye = f(Xc) are the predictions of the model. By definition, under HRT
Yourh, POO
(KK
(22)
K 1, are i..dd hence exchangcable. It follows that for any choice of test statistic T, the random variables , ) are also exchangeable. We conclude that Pl I Sa s a, Va E [0, 1]. 7
A.2 Proof of Theorem 2
Here, we prove the bounds on the expected p-value of the SHAP-XRT procedure presented Theorem 2.
A.2.1 Useful inequalities
We start by including some known inequalities that will become useful in the proof of our theorem.
Proposition A.1 ZPaley-Zygmund's incquality Palcy & Zygmund (1932)). If Z is a nonnegative random variable with fivile variance, and 0 < 0 < 1, then
(1 (1-0) 2
PiZ > #E|Z| Z Vor(Z) + (1 -1- 2)
(23)
Proposition A.2 (Bhatia- Davis' inequality Bhatia & Davis (2000)). Z is bounded random variable in in,M), then
Var 2)) (M [[Z]) m)
(24)
19

---

Published in Transactions on Machine Learning Research (12/2023)
A.2.2 Lemmas
We present two lemmas that provide upper and lower bounds to the negative tail of Jyc. respectively. Note that J. E [-1,1] because E [0, 1]. Herein, we define the nonnegative random variable 2 = 1 - [j.c such that
B|Z] = - 73.C"
1-3
SHAP
and PI =0 = PIZ 2 11.
(25)
Lemma A.1 (Upper bound). By Markov's 's inequality, holds that
3 0] s - 72.0'
75.0 SHAP
(26)
Proof. Applying Markov's inequality to Z directly yields
PlC s 0] = 2 E =
SHAP 73.C
(27)
SHAP < O, by the Zygmunds and Bhatia- Daviia inequalities, it holds Lemma A.2 (Lower bound). If 15.0 thot
F 50 2 (1,.0 2.
(28)
Proof. Note that SHAP yields
1j.C
<0
1/E[Z] and let A 1/E[Z]. Then, the Paley-Zygmmnd's incquality
(1 2 SHAPY?
F 5
(29)
Var(1 - -3,c)) + (0,00
Since 1 - 7,30 E [0,2], the Ahatia-Davis inequality implies
Var(1 Tg,c) ( E[1 r ( I 5. 0)
(30)
= =(1+ + 7j.C
SHAP )(1 1j.C
SHAP)
(31)
1 SHAP).
(32)
Therefore,
2
(3,00
P[ 3.C 50 2
(33)
Var 19,0) + (1
SHAPYZ
(7SHAP)2
(7..0
SHAP)
(34)
SHAPP? + (HSHAP)
A.2.3 Proof of Equation (11)
Here, we show that
K
0 S
S-RRT P.C
SHAP
(35)
K+1
1.C
where K> 1 is the number of draws of null statistic in the SHAP-XRT procedure.
20

---

Published in Transactions on Machine Learning Research (12/2023)
Proof. Recall that in the setting of Theorem 2, the test statistic T is the identity and L 1 in the SHAP-XRT procedure. Then,
PJC =E
S-XRT
XRT
1+
1
(7th)
11
(36)
K
k=1
K
1
1+
B[1
2 t|
(37)
K ++
k=1
1
(1+ KPP((()))) 2()
(38)
+1
1
(1+
KTP J.C s 0)
(1= ((Xou()) ( = ((x())
(39)
K+1
1
(1 K(1K1 7/..C SHAP))
(from Lemma A.1)
(40)
+1
K
SHAP
(41)
K 1 1.C
which is the desired result.
A.2.4 Proof of Equation (12)
Here, we show that if SHAP
< 0
1.CC
K ++1 (1+ HH) S
PjC
S-RRT
S 1.
(42)
where K 2 1 is the number of draws of null statistic in the SHAP-XRT procedure.
Proof. Recall that in the setting of Theorem 2, the test statistic T is the identity and L 1 in the SHAP-XRI
procedure. Then, similar to above
S-XRT PJC
(1 + KPT 5J)
(43)
K +
K + (1 + (15,0 SHAP)2)
(from Lemma A.2)
(44)
which is the desired result.
A.3 Proof of Lemma 1 Here, we prove that
D9 2
Σ
S-XRT wc Pj.C
(45)
is a valid p-value for Ho. = NogMNO) H S-III H.,.C
Proof. The proof follows directly from (Vovk & Wang, 2020, Proposition 9). Note that the weights we 1/n ((i7)) -I
belong to -1 (i.e., we > 0, Σeς(IMi) we 1). Furthermore, note that 1/w = 1/ maxcgim](3 we Then, when (i.e., for at least. 2 features), the result follows by setting in (Vovk & Wang, 2020, Proposition 9).
A.4 Proof of Corollary 1
Here, we prove that the Shapley value of feature j can be used to test for global null hypothesis
Ho.
HJ.C
S-RTT
(46)
cCM\ND
21

---

Published in Transactions on Machine Learning Research (12/2023)
Proof. Given feature j [n], recall from Lemma that
Pj = - =2
E
we Pj.
S-TR
(47)
is the expected p-value for the global null Ho.j. Then,
Σ
wc .
SHAP 73,00
(48)
K 1
Σ
wc(1 - Pj.0'
- X-RRTT)
(from Theorem 2)
(49)
K
K x+
Σ
WC
Pj.
S-XRT
(50)
K
OC(NM
K
1
Pj
(51)
2
from which it follows
K K+I K+ (e.
K
Pj 22
1
(52)
which is the desired result.
0
A.5
Proof of Corollary 2
Here, we prove the bounds on the expected p-value of the global SHAP-XRT null hypothesis presented in Corollary 2.
A.5.1 Proof of Equation (17)
Here, we show that if (z EE (0, then AC C [n] \ {i}
K
PJC
S-RRT
S
K +
W
(53)
where ã mincg(/MM Wc.
Proof. Suppose d5(x, f) 21 1- E (0, and fix O* E [m] \ (f)
such that
o)(2,)) = Σ
we : wC- ',,0*
SHAP
SHAP
+ Σ
we
-
SHAP
2
1 -
(54)
CCMNM
CYC*
which implics
1 1 Eoto- We T/
SHAP
SHAP 3
2
(55)
WC.
Eose. we
SHAP max T,.C
1)
(56)
WC
(1 WC:) )
Σ WC 1)
(57)
WC-
CC
WC -
1 6
1
min WC-
(58)
WC-
Note that the last inequality follows from (wc- - t)/wo- being an increasing function of we- for > 0. Then,
K
min cC(N]M]
7.C
SHAP
PJC
S-XRT
<
(from Theorem 2)
(59)
w
+
W
22

---

Published in Transactions on Machine Learning Research (12/2023)
A.5.2 Proof of Equation (18) Here, we show that if (2 f) Σ -1+ e with c < w. ~ = minog(aM we, then AC - [n] \ {1)
S-XRT PJC
1+ K E - w
(60)
+1
Proof. Similarly to above, suppose (z, S -1 -1+,, EE (0, and fix C* E [m]
\ {o} such that
01(x,))= = Σ
WC
73C
SHAP
wc-
SHAP ",,.C*
+
Σ
WC
SHAP
S -1 +
(61)
Mg
which implics
SHAP
(62)
1j.C*
W
and SHAP
1,0*
<0 = << W. Then,
max (C()MM
1EC
SHAP
- 2
< 0 7
PIO
S-RRT
K
1
+
1 K
E
W
(from Theorem 2)
(63)
B Axioms of the Shapley value
Recall that the tuple ([n), v), [m] = f1....,,, mm, w: P(n) + R+ is an n-person TU game with characteristic function v, such that VC C [n], v(C) is the score accumulated by the players in the coalition C. Then, the Shapley values Φi Φr ([n). u)...,,ee ([x],))) of the game ([n], v) (see Definition 1) are the only solution concept
that satisfies the following axioms (Shapley, 1951):
Axiom (Additivity). The Shapley values sum up to the utility accumulated when all players participate in the game (i.e. the grand coalition of the game)
E [,((r)) v(n))).
(64)
Axiom 2 (Nullity). If a player does not contribute to any coalition, its Shapley value is 0
AC S [m] (i). cCU()) v(C) o ()), 0.
(65)
Axiom 3 (Symmetry). If the contributions of two players to any coalition are the same, their Shapley values are the same
AC C [m]] ki,k), ((C = = = d,([m], v) = de((n),
(66)
Axiom (Linearity). Given ([n]. v), (Im), v), the Shapley value of the union of the two games (iee de (5 U [)) is equal to the sum of the Shapley values of the individual games (i.e. ()([)) and (y respcctively)
Φ (11) [m], v) o, ((m], + oy (5mm).)) v).
(67)
Finally, we note that Axioms 2-4 can be replaced by fifth one, usually referred to balanced contribution (Fryer et al., 2021), although this is not necessary to derive the definition of the Shapley value.
C Algorithms
A Algorithm C.1 summarizes the CRT procedure by Candes et al. (2018).
23

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm C.1 Conditional Randomization Test
procedure (dT X= = (x("),... ,...., .(m)) E Rmxx, response Y = (y(1), ,..., E R", feature j E [n]] test statistic T, number of null draws K E EN)
Compute the test statistic, i T(2,, x,) for k < 1,.....t K do
Sample x X, x-,= = x() i I,..., m
x(() t (x ....., x/
Compute the null statistic, Z(k) + T(X, ,) end for return A (one-sided) p-value
(11511021)
CCRT
K +1
end procedure
D Experimental details
Before describing the experimental details, we note that all experiments an NVIDIA Quadro RTX 5000 with 16 GB of RAM memory private server with 96 CPU cores. All scripts were run on PyTorch 1..0.0, Python 3.8.13 and CUDA 10.2.
D.1 Synthetic image data
Here, we describe the model architectures and the training details for the synthetic image datasets. Recall that X' C gdrxds, d,r, E N are images composed of an r x grid of non-overlapping patches of x d pixels, such that Xz5 E Rdxd is the patch in the sth-row and jch-column.
We train a CNN with one filter with stride d, and a two-layer FCN with ReLU activation. Tn particular:
f CNN (X) S
Σ
(Wo.
(68)
and
FCN (X) = S (bi + ReLU (bo + X))),
(69)
where Su) = 1/(1+ is the sigmoid function, and (e)U(w) = [0, x] is the rectified linear unit (Nair & Hinton, 2010). We train both models for one epoch on m i.id. samples and a batch size of 64. We note that we use Adam (Kingma & Ba, 2014) with learning rate of 0.001, and SGD with learning rate of 0.01 for f CNN and f FCN respectively, to achieve optimal validation accuracy.
D.2 Real image data
Here, we present the details of the training process for the experiment on the BBBC041 dataset (Ljosa et al., 2012) (which publicly available al https://bbbc. wwwadisstitute.....mmmmm........ wtt.ttutte....eeeeeeeeee wrg. org/BBBC041). Recall that the dataset. comprises 1425 images of healthy and infected human blood smears. We split the original dataset into training and validation split using an 80/20 ratio, respectively. This way, we train our model on 589 positive and 608 negative images, and validate on 112 positive and 116 negative images.
We apply transfer learning to a ResNet18 (He et al., 2016) pretrained on ImageNet (Deng et al., 2009). We optimize all paramcters of the network for 25 epochs using binary-cross entropy loss and Adam optimizer, with a learning rate of 0.0001 and learning rate decay of 0.2 every 10 epochs. At training time, we augment the dataset with random horizontal flips.
24

---

Published in Transactions on Machine Learning Research (12/2023)
E Supplementary results for real image data experiment
input image
SHAP-XRT heatmap for == 9
SHAP-XRT heatmap for 8
10
y=13
13
(b)
(c)
Here, we revisit the real image data experiment presented in Section Instead of using 4 quadrants, we further subdivide them to obtain 16 features, j 1,.... 16, as displayed in Figure E.la. The input image contains 6 trophozoites that are highlighted with green bounding boxes. For each feature, we compute the p-values of all 2 SHAP-XRT null hypotheses. Figures E.lb and E. show the SHAP-XRT heatmaps for features j = (which contains a trophozoite) and 8 (which does not contain a trophozoite). respectively. In the heatmaps, each feature j' E [16] { is colored accordingly to the number of SHAP-XRT mull hypotheses HS-XRT j' E C that are rejected. That is, the higher number of tests are rejected such that j' E C, the stronger the color of Teature j'. Figure E.1b shows that for an important feature (i.e., a feature that does contain trophozoite), the heatmap concentrates on features that do not contain any trophozoites. This agrees with intuition that when C' does not contain any trophozoites, adding feature with trophozoite will affect the distribution of the output of the model. Symmetrically, when C already contains some trophozoites, adding another will not affect the distribution. Figure E.lc shoes that for an unimportant feature (i.e., a feature that does not contain a trophozoite), the heatmap is empty because no matter whether C contains a trophozoite, adding an empty feature will not affect the distribution of the response.
J.C
25

---

Published in Transactions on Machine Learning Research (12/2023)
F Figures
Here we include supplementary figures.
(b) l/d
X
(c) o² 1/d
(a) Signal æo-
(d) 0² = 1/d.
Figure F.1: (a) Target signal Fy: a cross of size x d pixcls, d = 7. (b), (c), (d) Examples of positive and
negative images with increasing levels of noise, a² = 1/d", 1/d2, and 1/d, respectively. Note that all images are normalized to have zero-mean and unit variance.
(a) Reference.
(b) Sample
X(D--
(d) X ((2,3,4)
Figure F.2: Some examples of masked inputs from the BBBCO41 dataset. Shows the unimportant. reference (i.c. the unconditional expectation over the training split) used to mask features. We verify that the reference image does not contain any signal by checking that the output of f is R 0. (b) Shows the original sample z; (c) and (d) show some masked versions of when conditioning on the sets C = {1} and
C (2,3, 3, 4), respectively.
10-1
10"2
Plyscc
0.00
0.25
0.50
0.75
1.00
Figure F.3: Estimation Fly SHAP 2 1-a a C.C
SRTT < a] as a function of significance level for PjC
2, C ((2,1), (2, (3, 1), (3. 2)} in the known response experiment. This evaluates the gap between performing conditional independence testing by means of marginal contributions or the SHAP-XRT p-values. Estimates computed over 100 independent draws of the SHAP-XRT p-values for fixed dataset of N = 5, 000 data points.
26


Reviews:
[{"review_id": "SODEssjydz", "reviewer": "Reviewer_u8L8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- This paper is well-written and well-structured, the methods are explained very clearly, and the experiments also make sense.\n- The idea of connecting Shapley Value and CIT to create an S-CIT method is very intriguing. While previous methods have explored this aspect, the approach in this paper relaxes the assumptions of previous methods and yields solid and fascinating results.\n- The experiments in this paper are also well done, including simulations, synthetic data, and real data. The experimental results strongly support the methods proposed in the paper.\n- I believe this paper can be accepted with minor revisions. I didn't find any issues with the methods in this paper, and I found the motivation and method of this paper to be very clear. \n\n**Weaknesses**\n- As for the contribution, I am only familiar with this topic and not very deeply. Therefore, please refer to the opinions of other reviewers regarding the contribution section.\n- I have a concern that the author mentioned in the introduction that the interpretability of deep neural network features is very poor. My understanding of features is that when dealing with high-dimensional data, we first need to use neural networks to extract features to obtain a representation Z=Embedding(X). I believe the poor interpretability arises from our lack of knowledge about the information contained in Z. However, I noticed that in this paper, the concept of features is directly in the observed space of X, which is different from my understanding.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this research, the authors explore the relationship between the Shapley value and conditional hypothesis testing to interpret machine learning models at the sample-specific level. Through their work, they demonstrate that these two methods are intricately connected, with the Shapley value involving the computation of specific conditional hypothesis tests, and each component of the Shapley value providing a means to bound the p-values of these tests. This novel perspective assigns a precise statistical interpretation to the Shapley value, shedding new light on its meaning. The authors conducted numerical experiments using synthetic and real data, offering practical evidence to complement their theoretical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is better to put footnote 6 into the main content to replace Eq. 5 since it is easier to understand.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "G12gOHQWRI", "reviewer": "Reviewer_Jf7B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As someone who reads about and uses Shapley values, I'm interested in this line of work and have suspected that such a connection with conditional independence testing exists. I'm glad the authors tackled this problem, and I'm mostly satisfied with their execution (some requests for changes are made below).\n\nSome assorted strengths:\n- The motivation for connecting Shapley values with conditional independence testing is well articulated.\n- The overview/introduction to Shapley values was easy to read and mostly comprehensive.\n- The SHAP-XRT hypothesis test is a non-trivial view to come to about what the Shapley value is \"really\" doing. The authors presented it in generality, where the conventional Shapley procedure emerges as a special case, and the connection with conditional independence testing via equality in distribution (vs equality in expectation, see eq. 6) was surprising to me.\n- The authors gave proper consideration to the test's validity. (I'm not an expert on this topic so I did not verify their proof.)\n- The results showing how the Shapley value bounds the tests' p-values, at least in the binary classification setting, was interesting and surprising to me.\n- The authors made an attempt to generalize their perspective beyond the Shapley value by mentioning other \"probabilistic values\" (e.g., Banzhaf). (As mentioned below, I wonder if the authors could have considered other extensions to their perspective.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work aims to understand Shapley values through a new perspective: their connection with existing, formal hypothesis tests for conditional feature independence. The view shared here is that Shapley values are related to a new, per-sample hypothesis test of conditional feature independence, which the authors call the \"Shapley Explanation Randomization Test\" (SHAP-XRT). In addition to being \"local\" (focused on a single prediction), the test is also based on a model rather than the underlying data distribution, and it tests for independence when conditioned on an arbitrary subset of features (vs the more common choice of all the remaining features). \n\nThis test is not used today, but the authors present it in some generality and make provable claims about the test's validity. Regarding the specific connection with Shapley values, they claim that the Shapley values in some cases provide upper and lower bounds on the test's p-value. They also consider how to reason jointly about the exponential number of tests that can be performed for each feature (a \"global\" hypothesis test, not meant in the conventional interpretability sense).\n\nFinally, the authors present a brief set of experiments demonstrating their theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some assorted points about related work:\n- In the introduction, perhaps \"interpretable models\" should be \"inherently interpretable models\" for clarity? \n- In the introduction, the authors write that the Shapley value properties may not be satisfied \"perturbation-based\" explanations. Many people think of SVs as a perturbation-based method, so I'm not sure I get this. Its properties aren't satisfied by any other method (this follows trivially from the axiomatic characterization), whether perturbation- or gradient-based.\n- In the introduction, when alluding to the various approximation strategies, the implication that many methods aren't provable is a bit surprising. For example, KernelSHAP, permutation sampling, TreeSHAP and LinearSHAP are all provably correct (in some cases asymptotically). Also, this is a somewhat sparse list of approximations, a more comprehensive discussion is provided in a recent review paper [1]. (This point also comes up later in section 2.2.)\n- In the related work, Data Shapley and its distributional version aren't exactly relevant here, as they're about data sample contributions rather than feature contributions.\n- In the related work, there are other papers that discuss information theoretic interpretations of the Shapley value. For example, SAGE [2], which is built on by Watson et al (2023), is based on an information-theoretic view that's more relevant to conditional independence testing. L-/C-Shapley [3] is another example, but that perspective is arguably more about efficient approximation than interpretation of the values.\n- In the related work, it could be worth mentioning the other explanation methods based on each feature's marginal contributions.\n\n[1] Chen et al, \"Algorithms to estimate Shapley value feature attributions\" (2023)\n\n[2] Covert et al, \"Understanding global feature contributions with additive importance measures\" (2020)\n\n[3] Chen et al, \"L-Shapley and C-Shapley: Efficient model interpretation for structured data\" (2019)\n\n\nAssorted presentation points:\n- In eq. 5, this looks like a valid way to rewrite eq. 4, but I wonder if it makes more sense to write via $Y$'s conditional distributions? I.e., $(Y \\mid X_j, X_{-j}) = (Y \\mid X_j)$? This seems more aligned with how Shapley values work, because $f$ approximates $p(Y \\mid X)$.\n- I personally found SHAP-XRT difficult to follow at first. I'm not sure how the clarity can be improved, but perhaps it could help to emphasize at the beginning of section 3.1 that the test is distinct from and not trivially related to the Shapley value.\n- One of the points of confusion about SHAP-XRT, which is perhaps a strength, is that it's formulated as a test of equality in distribution. This was confusing because the standard Shapley value is based on differences in conditional expectations. I wonder if the authors could point out this distinction earlier and more explicitly.\n- About Lemma 1 and the ensuing discussion: it seems like we could calculate the global p-value with arbitrary weighting schemes and find whether we reject it under any circumstance. This seems equivalent to testing each of the individual hypotheses, so it surely would require some form of correction. Is the idea then that you must fix your weighting in advance to avoid multiple hypothesis testing that requires corrections?\n\n\n\nThere were a couple ways in which I wondered how the authors' perspective could be broadened beyond the standard Shapley value:\n\n1. SVs are one of many methods based on a feature's marginal contributions to a coalitional game, see [2]; besides the Banzhaf value, this includes any \"semivalue\" (studied by Kwon & Zou, 2022), as well as any \"random-order value\" (studied by the asymmetric Shapley values paper). This could be mentioned with a small modification to the section on global testing.\n\n2. The current analysis is focused on a model $f$ rather than the underlying data distribution. However, it might not be unreasonable to assume that $f$ is close to the true conditional probability. In that case, could the SHAP-XRT be interpreted as a test of true conditional independence vs conditional independence via a model? This perspective is explored in most prior works that discuss information-theoretic interpretations, for example SAGE and [4].\n\n3. The analysis here focuses on Shapley values applied in a \"local\" setting, hence the need for a local conditional independence test (SHAP-XRT). But the Shapley value is also sometimes used \"globally,\" or across the entire dataset. For example, people heuristically calculate the mean absolute Shapley value, and SAGE provides a more principled global Shapley value via the model's loss. Could either of these correspond to a dataset-level version of the SHAP-XRT?\n\n[4] Covert et al, \"Explaining by removing: a unified framework for model explanation\" (2021)\n\n\nAbout the experiments: I paid more attention to the previous sections, but one detail that jumped out was the choice to use H-SHAP from Teneggi et al (2022) for the real data experiments. I'm not that familiar with the method, but based on my understanding it's not clear that the method actually calculates Shapley values: I thought it returned a subset of relevant features and therefore yielded only coarse approximations, so that it would be biased in most cases. With that in mind, why not use more established options like KernelSHAP or permutation sampling (Mitchell et al., 2022), which are consistent statistical estimators? It would be helpful to hear the authors' explanation for this.", "broader_impact_concerns": "No concerns about broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CqMfKpVYOg", "reviewer": "Reviewer_1xWV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n\nThe paper is very well written and polished.  The topic is of theoretical and practical importance.  The paper has a clear message, which is Shapley values are connected to conditional independence tests in a formal way.  The results may trigger further research.\n\n\n- Weaknesses\n\nWhile the bounds are conceptually meaningful, it's not immediately clear how practical they are.  Also see detailed comments for some minor suggestions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper aims to give statistical interpretations for Shapley values in the context of machine learning interpretability.  Here, the Shapley value of a feature given a data point is the expected contribution of the target feature to the label, averaged over a reference set of other features.  The authors first present a test for conditional independence of individual features, which is a local (i.e., fixing a data point) variant of standard tests used in ML interpretability.  The idea of the test is: fixing a data point and given a (target) feature and a set of other (reference) features, we want to see whether conditioned on the reference feature set, the label is independent of the target feature (which would mean the target feature is unimportant).  The main results are that (1) each individual term in the Shapley value corresponding to a feature bounds the p-value of the corresponding conditional independence test for the same feature, and (2) the Shapley value itself bounds the p-value of the \"joint\" test, where the null hypothesis is the intersection of the null hypotheses of all tests for the same feature with different reference sets.  The authors discuss how these bounds can be used in interpretability, and conduct experiments to support these claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(also putting some detailed comments here; authors can use their own judgment)\n\nIntroduction, medicine example with 0.30, 0.15, ...: I'm not sure I fully understand this example.  Without thinking too much I thought all 4 should be reported?  Or maybe the point is weight and height are correlated and the true causally important feature is the patient's weight?  In any case it might help to briefly explain here.\n\nFirst sentence in sec 2.1, \"game theory (Owen, 2013)\": maybe something like \"see, e.g., (Owen, 2013)\" would sound better?  Also it seems like you are talking exclusively about *cooperative* game theory, so might as well cite something more specific.\n\nEq (3): I guess \\phi_j can be negative here (whereas in coop game theory it's normally nonnegative)?  It might help to briefly comment on it here (e.g., intuitively an important feature has a Shapley value whose *absolute value* is large).\n\nSentence after eq (3): I guess there has to be some constraints on C^* (otherwise one would simply choose [n])?\n\nSec 3.1: it's good to be formal and precise, but I'd also say upfront how this is connected to CRT, which I imagine would be appreciated by experts.\n\nGeneral criticism on thm 2: while this is definitely an interesting result which carries important messages, it's not immediately clear to me how useful it can be in practice.  The reason is that one wouldn't normally expect \\gamma (the expected marginal) to be close to 1.  If, say, \\gamma is 1/2 (which is still quite large --- generally one would expect this quantity to decrease as n increases), then the best bound thm 2 can give is p <= 1/2, which wouldn't be particularly helpful.  So my interpretation of thm 2 is: only in extreme cases one can make statistical conclusions based on the expected marginals, and in those cases the importance of the corresponding feature is probably so clear that one wouldn't even need statistical guarantees.  I'm curious what the authors have to say about this.\n\n\"Implications of thm 2\" paragraph, \"\\gamma provides both a lower bound and an upper bound\": hmm, but (11) is meaningful when \\gamma > 0, and (12) is meaningful when \\gamma < 0, so the lb and ub are never simultaneously meaningful...\n\nCor 1 and cor 2: these results are somewhat similar to thm 2 in that one would need a really large Shapley value to say anything meaningful.  (Of course the results do carry conceptual messages.)\n\nSec 4, synthetic data: here the power of 1 - \\gamma is fairly impressive, but it's also clear that a patch with a cross given other patches with noise fully explains the label.  Ideally it would be nice to have a synthetic dataset that appears harder to explain.\n\nSec 4, real data: I like this part especially because it shows both the power and the limitations of the theory.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores the intersection of Shapley-based explanation methods and conditional independence testing, traditionally considered separate in the context of artificial neural networks (ANNs). The authors introduce the SHAPley-EXplanation Randomization Test (SHAP-XRT), demonstrating its relevance for local conditional independence. They establish that, for binary classification problems, Shapley values provide bounds for p-values in conditional independence tests. The work advances our understanding of Shapley-based methods, revealing conditions for statistically valid claims about feature importance using the Shapley value. 

 The reviewers raised several concerns on the the technical details and presentation, and these concerns were well addressed in the rebuttal. The updated manuscript was recommended for acceptance by all reviewers.
Decision: Accept (poster)