Explaining Predictive Uncertainty with Information Theoretic Shapley Values
Authors: David Watson
Joshua O'Hara
Niek Tax
Richard Mudd
Ido Guy
Venue: NeurIPS 2023 poster (2023)
Keywords: Explainable AI
interpretable ML
feature attributions
information theory
Shapley values
TL;DR: We propose and study novel methods for explaining predictive uncertainty with Shapley values

Abstract: Researchers in explainable artificial intelligence have developed numerous methods for helping users understand the predictions of complex supervised learning models. By contrast, explaining the $\textit{uncertainty}$ of model outputs has received relatively little attention. We adapt the popular Shapley value framework to explain various types of predictive uncertainty, quantifying each feature's contribution to the conditional entropy of individual model outputs. We consider games with modified characteristic functions and find deep connections between the resulting Shapley values and fundamental quantities from information theory and conditional independence testing. We outline inference procedures for finite sample error rate control with provable guarantees, and implement efficient algorithms that perform well in a range of experiments on real and simulated data. Our method has applications to covariate shift detection, active learning, feature selection, and active feature-value acquisition.

Explaining Predictive Uncertainty with Information Theoretic Shapley Values
David Watson King's College London david. watson@kcl... ac.
Joshua O'Hara King's College London
Niek Tax Meta, Central Applied Science
Richard Mudd Meta, Central Applied Science
Ido Guy
Meta, Central Applied Science
Abstract
Researchers in explainable artificial intelligence have developed numerous meth- ods for helping users understand the predictions of complex supervised learning models. By contrast, explaining the uncertainty of model outputs has received relatively little attention. We adapt the popular Shapley value framework to explain various types of predictive uncertainty, quantifying each feature's s contribution to the conditional entropy of individual model outputs. We consider games with modified characteristic functions and find deep connections between the resulting Shapley values and fundamental quantities from information theory and condi- tional independence testing. We outline inference procedures for finite sample error rate control with provable guarantees, and implement efficient algorithms that perform well in a range of experiments on real and simulated data. Our method has applications to covariate shift detection, active learning, feature selection, and active ceature-value acquisition.
Introduction
Machine learning (ML) algorithms can solve many prediction tasks with greater accuracy than classical methods. However, some of the most popular and successful algorithms, such as deep neural networks, often produce models with millions of parameters and complex nonlinearities. The resulting "black box" is essentially unintelligible to humans. Researchers in explainable artificial intelligence (XAI) have developed numerous methods to help users better understand the inner workings of such models (see Sect. 2).
Despite the rapid proliferation of XAI tools, the goals of the field have thus far been somewhat narrow. The vast majority of methods in use today aim to explain model predictions, i.c. point estimates. But these are not necessarily the only model output of interest. Predictive uncertainty can also vary widely across the feature space, in ways that may have major impact on model performance and human decision making- Such variation makes it risky to rely on the advice of black box, especially when generalizing to new environments, Discovering the source of uncertainty can be an important first step toward reducing it.
Quantifying predictive uncertainty has many applications in ML. For instance, it is an essential subroutine any task that involves exploration, e.g. active learning [1]] 36). multi-armed bandits
773 40), and reinforcement learning more generally (55 76). Other applications of predictive
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

uncertainty quantification include detecting covariate shift [77] and adversarial examples [70], as well as classification with reject option [23] Our method aims to expand the scope of XAI these varied domains by explaining predictive uncertainty via feature attributions.
Knowing the impact of individual features local uncertainty can help drive data collection and model design. It can be used to detect the source of suspected covariate shift, select informative features, and test for heteroskedasticity, Our attribution strategy makes use of the Shapley value framework for XAI 88 74 49 9 a popular approach inspired by cooperative game theory, which we adapt by altering the characteristic function and augment with inference procedures for provable error rate control. The approach is fully model-agnostic and therefore not limited to any particular function class.
Our main contributions are threefold: (1) We describe modified variants of the Shapley value algorithm that can explain higher moments of the predictive distribution, thereby extending its explanatory utility beyond mere point estimates. We provide an information theoretic interpretation of the resulting measures and study their properties. (2) We introduce a split conformal inference procedure for Shapley variables with finite sample coverage guarantees. This allows users to test the extent which attributions for a given feature are concentrated around zero with fixed type I error control. (3) We implement model-specific and model-agnostic variants of our method and illustrate their performance in range of simulated and real-world experiments, with applications to feature selection, covariate shift detection, and active learning.
2
Related Work
XAI has become major subfield of machine learning in recent years. The focus to date has overwhelmingly been on explaining predictions in supervised learning tasks, most prominently via feature attributions [64 44 75,, rule lists [65] 38 [71], and counterfactuals [84 (50 34]. Despite obvious differences between these methods, all arguably share the same goal of identifying minimal conditions sufficient alter predictions in some pre-specified way [87. Resulting explanations should be accurate, simple, and relevant for the inquiring agent [86].
Quantifying inductive uncertainty is fundamental problem in probability theory and statistics, although machine learning poses new challenges and opportunities in this regard [3Ú]. The classical literature this topic comes primarily from Bayesian modeling [2I] and information theory [3], which provide a range of methods for analyzing the distribution of random variables. More recent has expanded the toolkit for practitioners.
work conformal inference 822 4
Important application areas for these methods include active learning (AL) and covariate shift detection. In AL, the goal is to selectively query labels for unlabeled instances aimed to maximize classifier improvement under a given query budget. Methods often select instances on which the model has high epistemic (as opposed to alcatoric) uncertainty [67). as for example in BatchBALD (36). This is especially valuable when labels are sparse and costly to collect while unlabeled data is widely available. In covariate shift detection, the goal is to identify samples that are abnormal relative to the in-distribution observations that the classifier has seen during training. It is well-known that neural networks can be overconfident (22). yielding predictions with unjustifiably high levels of certainty on test samples. Addressing this issue is an active area of research, and a variety of articles take perspective of quantifying epistemic uncertainty 30 [56]. In safety-critical applications, the degree of model uncertainty can be factored into the decision making, for example by abstaining from prediction altogether when confidence is sufficiently low 23
Very little work has been done on explaining predictive uncertainty. A notable exception is the CLUE algorithm 3 42), model-specific method designed for Bayesian deep learning, which generates counterfactual samples that are maximally similar to some target observation but optimized for minimal conditional variance. This contrasts with our feature attribution approach, which is model-agnostic and thereby the first to make uncertainty explanations available to function classes beyond Bayesian deep learning models.
Predictive uncertainty is often correlated with prediction loss, and therefore explanations of model errors are close relatives of our method. LossSHAP [45] is an extension of Lundberg and Lee 44 's SHAP algorithm designed to explain the pointwise loss of supervised learner (e.g., squared error or cross entropy). Though this could plausibly help identify regions where the model is least certain
2

---

about predictions, it requires a large labelled test dataset, which may not be available in practice. By contrast, our method only assumes access to some unlabelled dataset of test samples, which is especially valuable when labels are slow or expensive to collect. For instance, LossSHAP is little help in learning environments where covariate shift is detectable before labels are known [94]. This common, for example, in online advertising [37]. where an impression today may lead to conversion next week but quick detection (and explanation) covariate shift is vital.
Previous authors have explored information theoretic interpretations of variable importance measures; see [6. Sect. 8.3] for a summary. These methods often operate at global resolutions g.g. Sobol' indices 57 and SAGE [T5] whereas our focus is on local explanations. Alternatives such as INVASE [00 must be trained alongside the supervised learner itself and are therefore not model- agnostic. L2X [O]. REAL-X [32]. and SHAP-KL [33] provide post-hoe local explanations, but they require surrogate models to approximate a joint distribution over the full feature space. Chen et al. [1 propose an information theoretic variant of Shapley values for graph-structured data, which we examine more closely in Sect.
Background
Notation. We use uppercase letters to denote random variables (e-g.. X) and lowercase for their values (e.g., v). Matrices and sets of random variables are denoted by uppercase boldface type (e.g., X) and vectors by lowercase boldface (e.g., x). We occasionally use superscripts to denote samples, e.g. x(1) is the 2th row of X. Subscripts index features subsets thereof, e.g. Xş {X, hjes and 5 (a))) Ijes, where 5 S [d] = (1.....d) d). We define the complementary subset S = [d]].5.
Information Theory. Let p. q be two probability distributions over the same o-algebra of events. Further, let p. g be absolutely continuous with respect to some appropriate measure. We make use of several fundamental quantities from information theory [3), such as entropy (p). cross entropy H)p,q), KL-divergence D PkL(p (P || q), and mutual information I [X;; Y) (all formally defined in Appx. B.I]. We use shorthand for the (conditional) probability mass/density function of the random variable Y, e.g. py|x; p(Y X5 xs). We speak interchangeably of the entropy of random variable and the entropy of the associated mass/density function: local conditional entropy to distinguish it from its global counterpart, H( X), which requires marginalization over the joint space X' x y
(Y z) HH (py We call this the
Shapley Values. Consider supervised learning model f trained on features X E X' C TRd to predict outcomes E ) C TR. We assume that data are distributed according to some fixed but unknown distribution D. Shapley values are a feature attribution method in which model predictions decomposed as a sum: f(x) = Φn Σラ= Φ(j, x). where Φo is the baseline expectation (i.e., Φo = [x))( and x(j,x) denotes the Shapley value of feature at point x. To define this quantity, we require a value function
2|4| x Rd + R that quantifies the payoff associated with subsets S S [d] for particular sample. This characterizes cooperative game, in which each feature acts as a player. common choice for defining payoffs in XAI is the following [83
49 9
n0 x) = ED [f()
Xs xs}
where we marginalize over the complementary features 5 in accordance with reference distribution D. For any value function v. we may define the following random variable to represent j's marginal contribution to coalition S at point x:
(S. = [ xS,
Then j's Shapley value is just the weighted mean of this variable over all subsets:
|S| (d- 1)! [A..
oo(jx))
Σ
d!
SCMNG
It is well known that Eq. Iis is the unique solution to the attribution problem that satisfies certain desir- able properties, including efficiency, symmetry, sensitivity, and linearity [74] (for formal statements of these axioms, see Appx. B.2)
3

---

4 Alternative Value Functions
To see how standard Shapley values can fall short, consider a simple data generating process with X, Z ~ U(0, 1)² and Y ~ [X(, 2²). Since the true conditional expectation of Y is X, this feature will get 100% of the attributions in a game with payoffs given by vi-- However, just because Z receives zero attribution does not mean that it adds no information to our predictions on the contrary, we can use Z to infer the predictive variance of and calibrate confidence intervals accordingly. This sort of higher order information is lost in the vast majority of XAI methods.
We consider information theoretic games that assign nonzero attribution Z in the example above, and study the properties of resulting Shapley values. We start in an idealized scenario in which we have: (i) oracle knowledge of the joint distribution D; and (ii) unlimited computational budget, thereby allowing complete enumeration of all feature subsets.
INVASE [90] a method for learning a relatively small but maximally informative subset of features S C [d] using the loss function D (KI(PY)x |l px)x)) + AJS), where À is a regularization penalty. Jethani al. 33'ss SHAP-KL adapts this loss function to define new game:
(KL == (Py Il py|xs):
which can be interpreted 11 times the excess number of bits one would need on average to describe samples from Y x given code optimized for Y
Xs.
Chen et al. make similar proposal, replacing KL-divergence with cross entropy:
UCE(S, x) == -P
This value function is closely related to that of LossSHAP 45), which for likelihood- based loss functions can be written:
wr. (r x) = -log = y xs);
where y denotes the true value of Y the point x. As Covert al. [6] point out, this is equivalent to the pointwise mutual information Xy:: up to an additive constant. However, uz requires true labels for Y. which may not be available when evaluating feature attributions on test set. By contrast, vCE averages over y, thereby avoiding this issue: UCF(S, x) = - -Ey| (S, x)]. We reiterate that in all cases we condition on some fixed value of x and not marginalize over the feature space X. This contrasts with global feature attribution methods like SAGE [15], which can be characterized by averaging Uz over the complete joint distribution p(X, Y).
It is evident from the definitions that UKL and UCE are equivalent to an additive constant not depending on S. namely H (py|x). This renders the resulting Shapley values from both games identical (all proofs in Appx.
Proposition 4.1. For all features j [d], coalitions S S [d]]i), and samples x Dx
A AKL(S,j,x x) ACE(S.)
1 plu x) log ply xs, dy. ply xs)
This quantity answers the question: if the target distribution were Pylx, how many more bits of information would we get on average by adding zj to the conditioning event xs? Resulting Shapley values summarize each feature's 's contribution in bits the distance between Y's fully specified local posterior distribution p(Y x) and the prior p(Y).
Proposition 4.2. With e E (UKL, VCE), Shapley values satisfy Ej= Φolj.)) x)
DxI(PY ll py).
We introduce two novel information theoretic games, characterized by negative and positive local conditional entropies:
== -H xs). UH, HY xs).
All propositions in this section can be adapted to the classification setting by replacing the integral with summation over labels y.

---

The former subscript stands for information gain; the latter for entropy. Much like UCB. these value functions can be understood as weighted averages of LossSHAP payoff's over y, however this time with expectation over slightly different distribution: (S, x) -e x) = Y (S, x)] The marginal contribution of feature j to coalition S is measured in bits of local conditional mutual information added or lost, respectively (note that Aıg - -A))-
Proposition 4.3. For all features j E [d], coalitions 5 _ [4][},, and samples x ~ Dx
Ara(S, 1(Y;,) xs).
This represents the decrease in Y's uncertainty attributable to the conditioning event Ij when already know Xş. This quantity is similar (but not quite equivalent) to the information gain, a common optimization objective in tree growing algorithms [6] 62]. The difference again lies in the fact that we do not marginalize over X, but instead condition on a single instance. Resulting Shapley values summarize each feature's is contribution in bits the overall local information gain.
Proposition 4.4. Under UIG, Shapley values satisfy Ej=1 (j. x) = I(Y:)).
In the classic game Vo, out-of-coalition features are eliminated by marginalization. However, this will not generally work in our information theoretic games. Consider the modified entropy game, designed to take d-dimensional input:
Un (S, x) ED (PYY Xs x5
This game is not equivalent to vи. as shown in the following proposition. Proposition 4.5. For all coalitions S C [d] and samples x Dx:
(n( - Un- (S,x) = (xI.PIXxxx... Il pr(xs).
The two value functions will tend to diverge when out-of-coalition features X inform our predictions about Y, given prior knowledge of xs. Resulting Shapley values represent the difference in bits between the local and global conditional entropy.
Proposition 4.6. Under uH-, Shapley values satisfy Ej=1 OH (j.x) !Y x)
H! X).
In other words, Φn- (j, x) is j's contribution to conditional entropy at a given point, compared to a global baseline that averages over all points.
These games share an important and complex relationship to conditional independence structures. We distinguish here between global claims of conditional independence, e.g. Y .LI X Z, and local or context-specific independence (CSI), e.g. Y TT X z. The latter occurs when X adds no information about Y under the conditioning event Z = ? (see Appx. B. for example).
Theorem 4.7. For value functions {UKL, UCB, VIG, un }, have:
(a) Y IL X Xs + sup X (S. = 0. x) x. 0.
(b) Y YLL,, X3 (S.
(c) The set of distributions such that A (S,j. = OAY OOYOOA x is Lebesgue measure zero.
Item (a) states that Y is conditionally independent of X, given Xş if and only if j makes no contribution to S at any point x. Item (b) states that the weaker condition of CSI is sufficient for zero marginal payout. However, while the converse does not hold in general, item (c) states that the set of counterexamples is small in a precise sense-namely. has Lebesgue measure zero. A similar result holds for so-called unfaithful distributions in causality [72] 921, in which positive and negative effects cancel out exactly, making impossible detect certain graphical structures. Similarly, context-specific dependencies may be obscured when positive and negative log likelihood ratios cancel out as we marginalize over y' Measure zero events are not necessarily harmless, especially when working with finite samples. Near violations may in fact be quite common due to statistical noise [80] Together, these results establish powerful, somewhat subtle link between conditional independencies and information theoretic Shapley values. Similar results are lacking for the standard value function vo- to-with the notable exception that conditional independence implies zero marginal payout [66] an inevitable byproduct of the failure account for predictive uncertainty.
5

---

5 Method
The information theoretic quantities described in the previous section are often challenging to calculate, as they require extensive conditioning and marginalization. Computing some ((2)) such quantities per Shapley value, as Eq. [ requires, quickly becomes infeasible. (See [8] for an in in-depth analysis of the time complexity of Shapley value algorithms.) Therefore, we make several simplifying assumptions that strike balance between computational tractability and error rate control.
First, we require some uncertainty estimator h X' + IRz-- Alternatively, we could train new estimators for each coalition [8]; ; however, this can be impractical for large datasets and/or complex function classes. In the previous section, we assumed access to the true data generating process. In practice, we must train on finite samples, often using outputs from the base model f. In the regression setting, this may be a conditional variance estimator, as in heteroskedastic error models [35]; in the classification setting. we assume that f outputs a pmf over class labels and write fy IR + [0. 1] to denote the predicted probability of class E V. Then predictive entropy is estimated via the plug-in formula h4 (x) := EyEy f (x) log fy (x), where the subscript stands for total.
In many applications, we must decompose total entropy into epistemic and alcatoric components- -ie., uncertainty arising from the model or the data, respectively. We achieve this via ensemble methods, These may be decision trees, in random forest [68] or subsets of neural network nodes, in Monte Carlo (MC) dropout 200 Let fy (x) be the conditional probability estimate for class y given sample x for the 8th basis function. Then aleatoric uncertainty given by hx(xx == 2 Σ Σ
using a set of B basis functions, { ,..., f
Ewey (x) log (x). Epistemic uncertainty is simply
b=1
(x) Alternative methods may be appropriate for specific the difference [28). (x) == (x(x)) - ha
function classes, e.g. Gaussian processes (63) or Bayesian deep learning models [51]. We leave
the choice of which uncertainty measure to explain up to practitioners. In what follows, we use the
generic (xx) to signify whichever estimator is of relevance for given application.
We are similarly ecumenical regarding reference distributions. This has been the subject of much debate in recent years, with authors variously arguing that D should be simple product of marginals 31: or that the joint distribution should be modeled for proper conditioning and marginalization M: or else that structural information should be encoded quantify causal effects (25). Each approach
makes sense in certain settings g 85 so we leave it up to practitioners to decide which is most appropriate for their use case. We stress that information theoretic games inherit all the advantages
and disadvantages of these samplers from the conventional XAI setting, and acknowledge that attributions should be interpreted with caution when models are forced to extrapolate to off- manifold data [26]. Previous work has shown that no single sampling method dominates, with performance varying as a function of data type and function class [53]; see 9 for a discussion.
Finally, we adopt standard methods to efficiently sample candidate coalitions. Observe that the distribution on subsets implied by Eq. iiducess symmetric pmf on cardinalities |S$] E ( d-1 that places exponentially greater weight at the extrema than it does at the center. Thus while there are over 500 billion coalitions at d = 40, we can cover 50% of the total weight by sampling just over 0. 0.1% of these subsets (i.e., those with cardinality < 9 or 2 30). To reach 90% accuracy requires just over half of all coalitions. In fact, under some reasonable conditions, sampling O(n) coalitions is asympiotically optimal, up to a constant factor 88) We also employ the paired sampling approach of Covert and Lee [1| to reduce variance and speed up convergence still further.
These methods could in principle be extended our revised games. However, existing algorithms are typically either designed for local inference, in which case they are ill-suited to make global claims about feature relevance, require global value functions upfront, unlike the local games we consider here. As an alternative, we describe a method for aggregating local statistics for global inference. Specifically, we test whether the random variable o(j, x) tends concentrate around zero for given j. We take that provides the following finite sample coverage guarantee.
Several authors have proposed inference procedures for Shapley values 88 69 93
conformal approach [82 4T
Theorem 5.1 (Coverage). Partition n training samples {(x(1) ) D into two equal- sized subsets I,, In where I, is used for model fitting and Iz for computing Shapley values. Fix
"The additive decomposition of total uncertainty into epistemic and aleatoric components has recently been challenged [8) While alternative formulations are possible. we stick with this traditional view, which is widely used in deep ensembles and related methods for probabilistic ML (39 56 60)

---

target level E. (0, 1) and estimate the upper and lower bounds of the Shapley distribution from the empirical quantiles. That is, let qio be the Eth smallest value of Φ ), E I2. { [[n/2+ 1)a/22]) and let qui be the uth smallest value of the same set, for u =
Then for any test sample x x D. we have:
((o(ixx(tt)) E quil) 21-a.
Moreover, if Shupley values have a continuous joint distribution, then the upper bound on this probability is 1 - a + 2/ + 2).
Note that this is not a conditional coverage claim, insomuch as the bounds are fixed for a given Xj and do not vary with other feature values. However, Thm. T provides PAC-style guarantee that Shapley values do not exceed a given (absolute) threshold with high probability, or that zero falls within the (1 - a.) 100% confidence interval for given Shapley value. These results decisions about feature selection, since narrow intervals around zero are necessary (but not sufficient) evidence of uninformative predictors. This result is most relevant for tabular or text data, where features have some consistent meaning across samples; it is less applicable to image data, where individual pixels have no stable interpretation over images.
inform
Experiments
Full details of all datasets and hyperparameters can be found in Appx. C along with supplemental experiments that did not fit in the main text. Code for all experiments and figures can be found in our dedicated GitHub repository We use DeepSHAP sample out-of-coalition feature values in neural network models, and THP for hoosted ensembles. Alternative samplers are compared in separate simulation experiment below. Since our goal is explain predictive entropy rather than information, we use the value function Uz- throughout, with plug-in estimators for total, epistemic, and/or aleatoric uncertainty.
6.1 Supervised Learning Examples
First, we perform a simple proof of concept experiment that illustrates the method's performance on image, text, and tabular data.
Image Data. We examine binary classifiers on subsets of the MNIST dataset. Specifically, we train deep convolutional neural nets to distinguish vs. 7, vs. 8, and 4 vs. 9. These digit pairs tend to look similar in many people's handwriting and are often mistaken for one another. We therefore expect relatively high uncertainty in these examples, and use a variant of DeepSHAP visualize the pixel-wise contributions to predictive entropy, as estimated via MC dropout. We compute attributions for epistemic and aleatoric uncertainty, visually confirming that the former identifies regions of the image that most increase or reduce uncertainty (see Fig. A))
Applying our method, find that epistemic uncertainty is reduced by the upper loop of the as well as by the downward hook on the 7. By contrast, uncertainty is increased by the odd angle of the 8 and its small bottom loop. Aleatoric uncertainty, by contrast, is more mixed across the pixels, reflecting irreducible noise.
Text Data. We apply a transformer network to the IMDB dataset, which contains movie reviews for some 50,000 films. This is sentiment analysis task, with the goal of identifying positive vs. negative reviews. We visualize the contribution of individual words the uncertainty of particular predictions as calculated using the modified DeepSHAP pipeline, highlighting how some tokens tend to add or remove predictive information.
We report results for two high-entropy examples in Fig. 33. In the first review, the model appears confused by the sentence "This is not Great Cinema but was most entertained," which clearly conveys some ambiguity in the reviewer's sentiment. In the second example, the uncertainty comes from several sources including unexpected juxtapositions such "laughing and crying", well as "liar lou will love this movie."
7

---

Epistemic Uncertainty
Input
Uneeraiint
9
9
9
Nicoe KonEaa sonderfal actrose and here she's graat momttyy like Bos Chaplis in The Thin Rad Lase and be very good here laog Uraal Cerme
entertared Liven
days
8
9
WOW feally
newreed died.
ise leaghing and srrag sonaii Bla slcuad ABl losos and loan froegleallic Arsasess voe astal will disuly lave 6BM 3oose under amtosner you Lied laz you will lose munis. givee
7
Figure 1: A. MNIST examples. We highlight pixels that increase (red) and decrease (blue) predictive uncertainty in digit classification tasks (1 vs. 7, vs. 8, and vs. 9). B. Reviews from the IMDB dataset, with tokens colored by their relative contribution to the entropy of sentiment predictions.
A
B
Figure 2: A. Mean absolute error (MAE) as a function of sample size, with autocorrelation fixed p 0.5. B. MAE as a function of autocorrelation with sample size fixed at 2000. Shading represents standard errors across 50 replicates.
Tabular Data. We design a simple simulation experiment, loosely inspired by 0. in which Shapley values under the entropy game have closed form solution (see Appx. for details). This allows us to compare various approaches for sampling out-of-coalition feature values. Variables X are multivariate normally distributed with Toeplitz covariance matrix Egy = pli-šl and d dimensions. The conditional distribution of outcome variable Y is Gaussian, with mean and variance depending on x. We exhaustively enumerate all feature subsets at varying sample sizes and values of the autocorrelation parameter p.
For imputation schemes, compare KemelSSHA,, maximum likelihood, copula methods, empirical samplers, and ctree (see (54) for definitions of each, and a benchmark study of conditional sampling strategies for feature attributions). We note that this task is strictly more difficult than computing Shapley values under the standard top since conditional variance must be estimated from the residuals of preliminary model, itself estimated from the data. No single method dominates throughout, but most converge on the true Shapley value as sample size increases. Predictably, samplers that take conditional relationships into account tend to do better under autocorrelation than those that do not.
6.2 Covariate Shift and Active Learning
To illustrate the utility of our method for explaining covariate shift, we consider several semi-synthetic experiments. We start with four binary classification datasets from the UCI machine learning repository 117 BreastCancer, Diabetes, Ionosphere, and Sonar-ane and make a random 80/20 train/test split on each. We use an XGBoost model 12] with 50 trees to estimate conditional probabilities and the associated uncertainty. We then perturb random feature from the test set, adding a small amount of Gaussian noise to alter its underlying distribution. Resulting predictions have a large degree of entropy, and would therefore be ranked highly by an AL acquisition function. We compute information theoretic Shapley values for original and perturbed test sets. Results are visualized in Fig.
Our method clearly identifies the source of uncertainty these datapoints, assigning large positive or negative attributions to perturbed features in the test environment. Note that the distribution shifts

---

EreonE-avee sveer
Ireeeptei
Stear
00
Doma
Shapkoy
0.0
-02
-10
305
150
200
-.0
0.0
130
13
0.0
02
Feature
Figure 3: Information theoretic Shapley values explain the uncertainty of predictions on original and perturbed test sets. Our method correctly attributes the excess entropy the perturbed features.
are fairly subtle in each case, rarely falling outside the support of training values for given feature. Thus we find that information theoretic Shapley values can used in conjunction with covariate shift detection algorithms to explain the source of the anomaly, in conjunction with AL algorithms to explain the exploratory selection procedure.
6.3 Feature Selection
Another application of the method some but not all variables. For this experiment, we modify the classic Friedman benchmark [I9], which was originally proposed to test the performance of nonlinear regression methods under signal sparsity. Outcomes are generated according to:
feature selection tool when heteroskedasticity driven by
Y 10
+ 20( 0.5) + 10X4 5X, + Ex.
with input features ~ (0, 1)20 and standard normal residuals ~ NoO,, 12). To adapt this DGP to our setting, we scale Y to the unit interval and define:
Z s0 (xx7) 20(X; 0.5)² 10X, + 50 +
with e, (O0, Y2), where Y denotes the rescaled version of Y. Note that Z's conditional variance depends exclusively on the first five features, while its conditional mcan depends only on the second five. Thus with f(x) E[Z x] and h(x) ViZ x), should expect Shapley values for to concentrate around zero for (Xo.... X10), while Shapley values for should do the same for (X1.....5k),
draw 2000 training samples and fit f using XGBoost with 100 trees. This provides estimates of both the conditional mean (via predictions) and the conditional variance (via observed residuals Eg). We fit a second XGBoost model with the same hyperparameters to predict log (22). Results reported
test set of size 1000. We compute attributions using TreeSHAP 45 and visualize results in Fig. 4A. We find that Shapley values are clustered around zero for unimportant features in each model, demonstrating the method's promise for discriminating between different modes of predictive information. In a supplemental experiment, we empirically evaluate our conformal coverage guarantee this same task, achieving nominal coverage Appx.
0.1 for all features (see
As an active feature-value acquisition example, use the same modified Friedman benchmark, but this time increase the training sample size to 5000 and randomly delete some proportion of cells in the design matrix for X. This simulates the effect of missing data, which may arise due entry errors or high collection costs. XGBoost has native methods for handling missing data at training and test time, although resulting Shapley values are inevitably noisy. We refit the conditional variance estimator h and record feature rankings with variable missingness.
The goal in active deature-valus acquisition is to prioritize the variables whose values will best inform future predictions subject budgetary constraints. Fig. 4B shows receiver operating characteristic (ROC) curves for a feature importance ranking task as the frequency of missing data increases from zero to 50%. Importance is estimated via absolute Shapley values. Though performance degrades with increased missing data, as expected, we find that our method reliably ranks important features above unimportant ones in all trials. Even with fully half the data missing, we find an AUC of 0.682, substantially better than random.

---

Figure 4: A. Results for the modified Friedman benchmark experiment. The conditional mean depends on (Xs...., .i....,,1oo, while the conditional variance relies on (X1,...,,3 B. ROC curves for a feature ranking task with variable levels of missingness. The proposed value function gives informative results for feature-value acquisition.
7 Discussion
Critics have long complained that Shapley values (using the conventional payoff function vo)
difficult to interpret in XAL. not always clear what even means to remove features [43 2]. and large/small attributions are neither necessary
sufficient for importand/uimpoorann predictors, respectively [5] 229] In an effort to ground these methods in classical statistical notions, several authors have analyzed Shapley values in the context of ANOVA decompositions 24 6 conditional independence tests (47 (8). with mixed results. Our information theoretic approach provides another window into this debate. With modified value functions, show that marginal payoff's (S, j) have an unambiguous interpretation as a local dependence measure. Still, Shapley values muddy the waters somewhat by averaging these payoff's over coalitions.
There has been a great deal of interest recent years on functional data analysis, where the goal to model not just the conditional mean of the response variable E[Y x), but rather the entire distribution P(Y x), including higher moments. Distributional regression techniques have been developed for additive models [66], gradient boosting machines (79). random forests [27]. and neural density estimators [58]. Few if any XAI methods have been specifically designed to explain such models, perhaps because attributions would be heavily weighted toward features with significant impact on the conditional expectation, thereby simply reducing to classic measures. Our method provides possible way to disentangle those attributions and focus attention higher moments. Future work will explore more explicit connections to the domain of functional data.
One advantage of our approach is its modularity. We consider range of different information theoretic games, each characterized by a unique value function. We are agnostic about how to estimate the relevant uncertainty measures, fix reference distributions, sample candidate coalitions. These are all active areas of research in their own right, and practitioners should choose whichever combination of tools works best for their purpose.
However, this flexibility does not come for free. Computing Shapley values for many common function classes is #a-hard, even when features are jointly independent [81] Modeling dependen- cies to impute values for out-of-coalition features is statistical challenge that requires extensive marginalization. Some speedups can be achieved by making convenient assumptions, but these may incur substantial errors in practice. These are familiar problems feature attribution tasks. Our method inherits the same benefits and drawbacks.
8 Conclusion
We introduced a range of methods to explain conditional entropy in ML models, bringing together existing work on uncertainty quantification and feature attributions. We studied the information theoretic properties of several games, and implemented our approach in model-specific and model- agnostic algorithms with numerous applications. Future work will continue to examine how XAI can go beyond origins in prediction to inform decision making in areas requiring an exploration- exploitation trade-off, such bandits and reinforcement learning.
10

---

Acknowledgments and Disclosure of Funding
We thank Matthew Shorvon for his feedback on an earlier draft of this paper. We also grateful to the reviewers for their helpful comments.
References
Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features dependent: More accurate approximations to Shapley values. Artif. Intell., 298:103502, 2021.
[2] Julius Adebayo, Justin Gilmer, Michael Muelly, Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. In Advances in Neural Information Processing Systems, volume 31, 2018.
[3] Javier Antorán,
Umang Bhatt. Tameem Adel, Adrian Weller, and José Miguel Hernández-Lobato. Getting CLUE: A method for explaining uncertainty estimates. In International Conference on Learning Representations, 2021.
[4] Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics, 51(1):149 178, 2023.
[5] Blair Bilodcau, Natasha Jaques, Pang Wei Koh, and Been Kim. Impossibility theorems for feature attribution. arXiy preprint, 2212.1 18770, 2022.
[6] Sebastian Bordt and Ulrike Luxburg. From Shapley values generalized additive models and back. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206, pages 709-745, 2023.
[7] Craig Boutilier, Nir Friedman, Moises Goldszmidt, and Daphne Koller. Context-specific independence in Bayesian networks. Proceedings of The 12th Conference on Uncertainty in Artificial Intelligence, 1996.
[8] Hugh Chen, Joseph D. Janizek, Scott Lundberg, and Su-In Lee. True to the model or true to the data? arXiv preprint, 2006.16234 2020.
[9] Hugh Chen, Ian C. Covert, Scott M. Lundberg, and Su-In Lec. Algorithms to estimate Shapley value feature attributions. arXiv preprint, 2207.07605, 2022.
[10] Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information- theoretic perspective model interpretation. Proceedings of the 35th International Conference on Machine Learning, pages 883-892, 2018
[11] Jianbo Chen, Le Song. Martin Wainwright, and Michael I. Jordan, L-Shapley and C-Shapley: Efficient model interpretation for structured data. In International Conference on Learning Representations, 2019.
[12] Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 785-794, 2016.
[13] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, Hoboken, NJ, second edition, 2006.
[14] Ian Covert and Su-In Lec. Improving kemelSHAP: Practical Shapley value estimation using linear regression. In Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130, pages 3457-3465, 2021.
[15] Ian Covert, Scott M. Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. Advances Neural Information Processing Systems, volume 33, pages 17212- 17223, 2020.
[16] Ian Covert, Scott M. Lundberg, and Su-In Lec, Explaining by removing: A unified framework for model explanation. J. Mach. Learn. Res., 22(209):1 1-90,, 2021.
[17] Dheeru Dua and Casey Graff. UCT machine learning repository, 2017. URL URI htt.::t:///archve.icc.. uci edu/m1
[18] Yoav Freund, I Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine learning, 28(2):133-18) 168, 1997.
[19] Jerome H. Friedman. Multivariate adaptive regression splines. The Annals of Statistics. 19(1): 67. 1991.
11

---

[20] Yarin Gal and Zoubin Ghahramani. Dropout as Bayesian approximation: Representing model uncertainty in deep learning. In Proceedings The 33rd International Conference on Machine Learning, volume 48, pages 1050-1059, 2016.
[21] Andrew Gelman, John B. Carlin, Hal S. Stern, David B. Dunson, Aki Vehtari, and Donald Rubin. Bayesian data analysis. Chapman & Hall, New York, 1995.
[22] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the International Conference on Machine Learning, pages 1321-1330. PMLR, 2017.
[23] Kilian Hendrickx, Lorenzo Perini, Dries Van der Plas, Wannes Meert, and Jesse Davis, Machine learning with reject option: A survey, arXiv preprint arXiv:2107.1122 2021.
[24] Andrew Herren and P. Richard Hahn. Statistical aspects of SHAP: Functional ANOVA for model interpre- tation. arXiv preprint, 29980, 2022.
[25] Tom Heskes, Evi Sijhen, Toan Gabriel Bucur, and Tom Claassen. Causal Shapley values: Exploiting causal knowledge to explain individual predictions complex models. In Advances Neural Information Processing Systems, 2020.
[26] Giles Hooker, Lucas Mentch, and Siyu Zhou. Unrestricted permutation forces extrapolation: variable importance requires at least one more model, or there is no free variable importance. Statistics and Computing, (6):22 2021.
[27] Torsten Hothorn and Achim Zeileis. Predictive distribution modeling using transformation forests. J. Comput. Graph. Stat.,
2021.
[28] Neil Houlsby. Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference leamingg arXiv preprint, 1112.5745, 2011.
[29] Xuanxiang Huang and Joao Marques-Silva. The inadequacy of Shapley values for explainability. arXiv preprint, 2302.08160, 2023.
[30] Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning: an introduction to concepts and methods. Mach. Learn., 110:457-506, 2021.
[31] Dominik Janzing, Lenon Minorics, and Patrick Blocbaum. Feature relevance quantification in explainable Al: A causal problem. In Proceedings of the 23rd International Conference on Artificial Intelligence and Stutistics, volume 108, pages 2907-2916, Online, 2020.
[32] Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs, and Rajesh Ranganath. Have we learned to explain?: How interpretability methods can learn to encode predictions in their interpretations. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 1459-1467, 2021.
[33] Neil Jethani, Adriel Saporta, and Rajesh Ranganath. Don't be fooled: label leakage in explanation methods and the importance of their quantitative evaluation. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, pages 9995,, 2023.
[34] Moir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnosit counterfactual explanations for consequential decisions. In The 23rd International Conference Artificial Intelligence and Statistics, volume 108, pages 895-905, 2020.
[35] Robert Kaufman. Heteroskedasticity in regression. SAGE, London, 2013.
[36] Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. BatchBALD: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in neural information processing systems, 32, 2019.
[37] Sofia Ira Ktena, Alykhan Tejani. Lucas Theis. Pranay Kumar Myana, Deepak Dilipkumar, Ferene Huszár, Steven Yoo, and Wenzhe Shi. Addressing delayed feedback for continuous training with neural networks in CTR prediction. In Proceedings of the 13th ACM Conference on Recommenndr Systems, pages 187-195, 2019.
[38] Himabindu Lakkaraju. Ece Kamar, Rich Caruana, and Jure Leskovec. Faithful and customizable explana- tions of black box models. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 13 131-138 2019.
[39] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems. volume 30, 2017.
12

---

[40] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, Cambridge, 2020.
[41] Jing Lei, Max G'Sell, Alessandro Rinaldo. Ryan Tibshirani, and Larry Wasserman. Distribution-Fre Free Predictive Inference for Regression. Journal the American Statistical Association, 113(523):1094 1111, jul 2018.
[42] Dan Ley, Umang Bhatt, and Adrian Weller. Diverse, global and amortised countcrfactual explanations for uncertainty estimates. Pruceedings of the AAAI Conference on Artificial Intelligence, 36(7):7390-773999 2022.
[43] Zachary Lipton. The mythos of model interpretability. Commun. ACM, 61(10):36 43, 2018.
[44] Scott M. Lundberg and Su-In Lec. A unified approach to interpreting model predictions. In Advances in Newral Information Processing Systems, pages 4765-4774, 2017.
[45] 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. Nat. Mach. Intell., 2(1):56-67, 2020.
[46] Christoph Luther, Gunnar König, and Moritz Weestr.Wnnruup... Efficient SAGE estimation via causal structure learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statisticx, 2023.
[47] Sisi Ma and Roshan Tourani. Predictive and causal implications of using shapley value for model interpretation. In Proceedings of the 2020 KDD Workshop on Causal Discovery, pages 23-38, 2020.
[48] Christopher Meek. Strong completeness and faithfulness in Bayesian networks. In Proceedings of The 11th Conference on Uncertainty in Artificial Intelligence, 1995.
[49] Luke Merrick and Ankur Taly. The explanation game: Explaining machine learning models using shapley values. In CD-MAKE, pages 17-38. Springer, 2020.
[50] Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference Fairness, Accountability, and Transparency, pages 607 617, 2020.
[51] Kevin Murphy. Probabilistic Machine Learning: An Introduction. The MIT Press, Cambridge, MA, 2022.
[52] Masashi Okamoto. Distinctness of the eigenvalues of quadratic form in multivariate sample. The Annals of Statistics, 1(4):763 - 765, 1973.
[53] H. B. Olsen, Ingrid Glad, Martin Jullum, and Kjersti Aas. Using shapley values and variational autoencoders to explain predictive models with dependent mixed features. Journal of Machine Learning Research, 23(213), 2022.
[54] Lars Henry Berge Olsen, Ingrid Kristine Glad, Martin Jullum, and Kjersti Aas. A comparative study of methods for estimating conditional Shapley values and when to use them. arXiv preprint, 2305.095366 2023.
[55] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. Advances in neural information processing systems, 29, 2016.
[56] Yaniv Ovadia, Emily Fertig, Jie Ren, 7achary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
[57] Art B. Owen. Sobol' indices and Shapley value. SIAM/ASA Journal on Uncertainty Quantificatio,, 2(1): 245-251, 255,25,,25 2014.
[58] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshmi- narayanan. Normalizing flows for probabilistic modeling and inference. J. Mach. Learn. Res., 22(5 1-64, 2021.
[59] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Stiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: an imperative style, high high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024 8035, 2019.
13

---

[60] Apostolos F. Psaros, Xuhui Meng. Zongren Zou, Ling Guo, and George Em Karniadakis. Uncertainty quantification in scientific machine learning: Methods, metrics, and comparisons, J. Compud. Phys., 477: 111902, 2023.
[61] John R. Quinlan, Induction of decision trees. Mach. Learn, 1(1):81-106, 1986.
[62] John Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo, CA, 1993.
[63] Carl Edward Rasmussen Christopher K.I. Williams, Gaussian processes for machine learning. The MIT Press, Cambridge, MA, 2006.
[64] Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135-1144, 2016.
[65] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. explanations. 32(1115527 2018
Anchors: High figh-precision model-agnostic
[66] Robert A. Rigby and D. M. Stasinopoulos. Generalized additive models for location, scale and shape. Journal of the Royal Statistical Society: Series (Applied Statisticx), 54(3):00-555, 2005.
[67] Burr Setlle. Active learning literature survey. Technical Report 1648, University of Wisconsin- Madison, 2009.
[68] Mohammad Hossein Shaker and Eyke Hüllermeier. Alcatoric and epistemic uncertainty with random forests. In Michael R. Berthold, Ad Feelders, and Georg Krempl, editors, Advances in Intelligent Data Analysis XVIII, pages 444-456, Cham, 2020. Springer International Publishing.
[69] Dylan Slack, Anna Hilgard, Sameer Singh, and Himabindu Lakkaraju. Reliahle post hoc explanations: Modeling uncertainty in explainability. In Advances in Neural Information Processing Systems, volume 34, pages 9391-9404, 2021.
[70] Lewis Smith and Yarin Gal. Understanding measures of uncertainty for adversarial example detection. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pages 1059, 2018.
[71] Kacper Sokol and Peter Flach. LIMEtree: Interactively customisable explanations based on local surrogate multi-output regression trees. arXiv preprint, 2005.0 01466, 2020.
[72] Peter L. Spirtes, Clark N. Glymour, and Richard Scheines. Causation, Prediction, and Search. The MIT Press, Cambridge, MA, 2nd edition, 2000.
[73] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret experimental design. In Proceedings of the 27th International Conference on Machine Learning, 2010.
[74] Mukund Sundararajan and Amir Najmi. The many Shapley values for model explanation. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[75] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of the 34th Internutional Conference Machine Learning Volume 70, page 3319-3328, 2017.
[76] Richard Sutton and Andrew G. Barto. Reinforcement learning: An introduction. The MIT Press, Cambridge, MA, 2nd edition, 2018
[77] Natasa Tagasovska and David Lopez-Paz. Singlc-model uncertainties for deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[78] Jacopo Teneggi, Beepul Bharti, Yaniv Romano, and Jeremias Sulam. From Shapley back Pearson: Hypothesis testing via the Shapley value. arXiv preprint, 2207.07038, 2022.
[79] Janek Thomas, Andreas Mayr, Bernd Bischl, Matthias Schmid, Adam Smith. and Benjamin Hofner. Gradi- ent boosting for distributional regression: Faster tuning and improved variable selection via noncyclical updates. Statistics and Computing, 28(3):673-687 2018.
[80] Caroline Uhler, Garvesh Raskutti, Peter Buhlmann, and Bin Yu. Geometry of the faithfulnees assumption in causal inference. The Annals of Statistics, 41(2):436 463, 2013.
14

---

[81] Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the tractability of SHAP explanations. In Proceedings the AAAI Conference on Artificial Intelligence, volume 35, 2021.
[82] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer, New York, 2005.
[83] Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. J. Mach. Learn. Res., 11:1-18, 2010. ISSN 1532-4435.
[84] Sandra Wachter, Brent Mittelstadt, Chris Russell. Counterfactual explanations without opening black box: Automated decisions and the GDPR. Harvand J. Law Technol., 31(2):841-887, 2018.
[85] David S. Watson. Conceptual challenges for interpretable machine learning. Synthese, 200(2)65,, 2022.
[86] David S Watson and Luciano Floridi. The explanation game: formal framework for interpretable machine learning. Synthese, 198:9211 1-9242, 2021.
[87] David S. Watson, Limor Gultchin, Ankur Taly, and Luciano Floridi. Local explanations via necessity and sufficiency: Unifying theory practice. Minds Mach., 32(1):185 218, 2022.
[88] Brian Williamson and Jean Feng. Efficient nonparametric statistical inference on population feature importance using shapley values. Proceedings of the 37th International Conference Machine Learning, pages 10291-10291, 2020.
[89] Lisa Wimmer, Yusuf Sale, Paul Hofman, Bernd Bischl. Eyke Hüllermeier. Quantifying aleatoric and epistemic uncertainty in machine learning: Are conditional entropy and mutual information appropriate mcasures? In Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 2282-2292, 2023.
[90] Jinsung Yoon, James Jordon, and Mihacla van der Schaar. INVASE: Instance-wiig variable selection using neural networks. In International Conference on Learning Representations, 2019.
[91] Jiji Zhang and Peter L. Spirtes. Strong faithfulness and uniform consistency in causal inference. In Proceedings of The 19th Conference on Uncertainty in Artificial Intelligence, 2003.
[92] Jiji Zhang and Peter L. Spirtes. The three faces of faithfulness. Synthese, 193(4):001 1334))0001-0222,001
[93] Xingyu Zhao, Wei Huang, Xiaowei Huang, Valentin Robu, and David Flynn. Baylime: Bayesian local interpretable model-agnostic explanations. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence, pages 887 896, 2021.
[94] Indre Zliobaite. Change with delayed labeling: When is detectable? In 2010 IEEE International Conference on Data Mining Workshops, pages 650. IEEE, 2010.
15

---

A Proofs
Proof of Prop. 4.1
Substituting UKE into the definition of Ao(S,),x) gives:
(kI(S, = - (DrI(PVIx prixgie,) (pv ll prixs))
Rearranging and using the definition of KL-divergence, we have:
(sI(S, E
[log<(y xx logp(y xs)] E log ply x) log xs,
Cleaning up in steps:
Axt(S, [logp(y x) p(y xs) log (x) + log p(y [xs
E [logply xs, log p(U xs)] Y
- p(y x) log ply Xe, xg, dy-
p(u xs)
Substituting ves into the definition of (. gives: H
AcB (S, (pY xx. pYing,,)) (pyix.PYixs) Rearranging and using the definition of entropy, have:
(plxxx:PYxs)
E logoppy xs)] E x
- logply x,)
Yix
E [logp(v) x,) - log plu xs)]
Yix
p(y x) log ply xs, 22)) ply xs)
dy.
Proof Prop. 4.2
Since Shapley value (5.(1, J. x) is just the expectation of (S, x) under a certain
distribution on coalitions S S [d]][i} (see Eq. []. it follows from Prop. 4.1 that feature attributions will be identical under u and ucr. To show that resulting Shapley values sum to the KL-divergence between p(Y x) and p(Y), we exploit the efficiency property:
Σ (xIlj.x) vxu(ld]xx) (0, ==1
-Px ll px + DRI(PYix 1l pv)
(xz(Pvix ll pr).
The last step exploits Gibbs's incquality, according to which (xz(p () 2 0, with DRL ll g) 0 q.
Proof of Prop. 4.3
Substituting into the definition of (S, gives:
Are(S.j.x) = HYYY xs, + H(Y xs)
H(Y (xs) H(Y xs,
I(Y xs)
= =s ply, Øy xss log
p xxs)
dy.
ply xs) p(a, xs)
In the penultimate line, we exploit the equality X(Y; H(Y) - H(Y X), by which we define mutual information (see Appx. B.I
We once again rely efficiency and the definition of mutual information in terms of marginal and conditional entropy:
Proof of Prop. 4.4
xialixx) vva((d), (0, x)
=-H(Y xx + H(V)
=H(Y) - -IY xx)
=(Y)xx).
16

---

Proof of Prop. 4.5
Let b(S, x) denote the gap between local conditional entropy formulae that take |S]- and d-dimensional imput, respectively. Then have:
b(S, x) -us(S, UH- (8.x)
- H(Y xs)
E
[H(Y
X)
Xs Xs]
Xzixs
E
[log xs)]
E
[logply xx,
Vlss
Xg..lxe
E X Vxs
[logp(y] xg, log xs)
JagJs I/ p(xg.U xs) log ply xx, dxg dy
p(u xx)
= Dxu(plY Xx) p(Y xs)).
Proof of Prop. 4.6
Exploiting the efficiency property, we immediately have:
Σ ob (J.x) = u ([d] UHz (0,x) x)
H(Y x) T. [ xx]
Dx
H(Y x) H(Y X).
By contrast, Shapley values for the original entropy game sum H(Y x) HY) (=(Y)=-A0 -));x)). Thus whereas the baseline for empty coalition S = is the prior entropy H(Y) under ey,, the corresponding baseline for the d-dimensional version uy- the global posterior entropy H(Y IX).
Proof of Thm. 4.7
Begin with item (a). Note that the conditional independence statement 1t 1L Xs holds iff, for all points (x. 3) ~ D. we have:
p(y xs, = ply xs) and p(y. | xs) = ply xxs) p(ay xs).
The former guarantees that marginal payouts evaluate zero for {UKZ, tcg); the latter does the same for E (ViG, Vx) J. This follows because the log ratio in each formula evaluates to zero when numerator and denominator are equal.
Of course, conditional independence is also sufficient for zero marginal payout with more familiar value functions such as But item (a) makes an additional claim-that the converse holds as well, i.c. that conditional independence is necessary for marginal payout all x. This follows from the definitions value functions themselves. Observe:
ply xg,
xx
AKL(S,).))]
=
IE (x.9))/
log
ply xs)
ply xg, log
E Dx
Y|x8.a5
p(y xs)
|Y|x))]]
By Gibbs's 's incquality, the -ivviveeeeecc hetween two distributions is zero iff they are equal, so setting this value zero for all satisfies the first definition of conditional independence above. For the latter, we simply point out that:
[A, IYY; Xs).
xxxxx
Since conditional mutual information equals zero iff the relevant variables conditionally independent, this satisfics the second definition above.
Item (b) states that CSI, which is strictly weaker than standard conditional independence, is also sufficient for zero marginal payout at a given point x. This follows directly from the sufficiency argument above.
The converse relationship is more complex, however. Call distribution conspiratorial there cxists some S.j. x such that A, (S.j.x) j.) ) = A Y L. X, xs for some e E (UKL,, VCE, vra, uH) )- Such distributions are named because the relevant probabilities must coordinate in a very specific way guarantee summation to marginalize over Vi As concrete example, consider the following data generating process:
X Bem(0.5), Z Bem(0.5), Y (0. + 0.4X - -0.2Z).
17

---

What is the contribution of X to coalition S = 0 when X = 1 and Z = 1? In this case, we have neither global context-specific independence, ie. Y 1. X. Yet. evaluating the payofI's in KL-divergence game, we have:
Ply X = - log P(y X x=
( Σ
P(v)
0.4
0.6
0.5 log 0.6
+ 0.5
0.4
0.
In this case, we find that negative and positive values of the log ratio cancel out exactly we marginalize over y. (Similar examples can he constructed for all our information theoretic games.) This shows that CSI is sufficient but not necessary for (S,
0.
However, just because conspiratorial distributions are possible does mean that they are common. Item (c) states that the set all such distributions has Lebesgue measure zero. Our proof strategy here follows that of Meek [48], who demonstrates a similar result in the case of unfaithful distributions, i.e. those whose (conditional) independencies are not entailed by the data's 's underlying graphical structure. This is an important topic in the causal discovery literature (see, e.g.. [91 (2))
For simplicity, assume discrete state space X' x Y, such that the data generating process is fully parametrized by a table of probabilities T for each fully specified event. Fix some S, j such that Y JL X, xs. Let be the number of possible outcomes, y = {B/...., yc Define vectors p. q, of length such that, for cach c E [C]:
P(ye x5)
Pc P== p(ye x), qo p(ye 25) p(ye xs); re log
p(ye x8)
and stipulate that p(ye xxs= > O for all e E [C] to avoid division by zero Observe that these variables all deterministic functions of the parameters encoded in the probability table T. By the assumption of local conditional dependence. we know that |rl|o
Yet for our conspiracy to obtain, the data must satisfy
P p-r = 0. A well-known algebraic lemma of Okamoto [52) states that if a polynomial constraint is non- non-trivial (i.c., if there exists some settings for which it does not hold), then the subset of parameters for which it does hold has Lebesgue measure zero. The log ratio is not polynomial in T, but the difference q is. The latter also has a strietly positive Lo norm by the assumption of local conditional independence. Crucially, the resulting dot product intersects with our previous dot product zero That is, though differences are in general a non-injective surjective function of log ratios, we have a bijection at the origin whereby p.t r = 0 <> p q = O. Thus the conspiracy requires nontrivial constraints that are linear in p. thteesselees polynomial in the system parameters T we conclude that the set of conspiratorial distributions has Lebesgue measure zero.
Our proof is an application of the split conformal method (see 41 Thm. 2.2]). Whereas that method was designed bound the distance between predicted and observed outcomes for regression task, we adapt the argument to measure the concentration of Shapley values a given feature. To achieve this, we replace out-of-sample absolute residuals with out-of sample Shapley values and drop the symmetry assumption, which will not generally apply when features are informative. The result follows immediately from the exchangeability of Φ(j, x (++1)) and Φ(j. x ()), i E Iz, which is itself a direct implication the i.i.d. assumption. Since bounds are calculated so as to cover (1 - a) x 100% of the distribution, is unlikely that new samples will fall outside this region. Specifically, such exceptions occur with probability at most a. This amounts sort of PAC guarantee, i.c. that Shapley values will be within data-dependent interval with probability at least a. The interval can be trivially inverted compute an associated p- p-value.
Proof of Thm. 5.1
We identify three potential sources error in estimating upper and lower quantiles the Shapley distribution: (1) learning the conditional entropy model h from finite data; (2) sampling values for out-of-coalition features St (3) sampling coalitions S. Convergence rates as a function of (1) and (2) are entirely dependent on the selected subroutines. With consistent methods for both, conformal prediction bands are provably close to the oracle band (see 4I Thm. 8)). As for (3). Williamson and Feng [88] show that with efficient estimators for (1) and (2). as well as an extra condition on the minimum number of subsets, sampling (n)) coalitions asymptotically optimal, up to a constant factor.
B Addenda
This section includes extra background material on information theory and Shapley values.
B.1 Information Theory
Let p.g 4 be two probability distributions over the same a alagebrra of events. Further, let p. be absolutely continuous with respect to some appropriate measure. The entropy of is defined (p) == Epl- logp).
18

---

Le. the expected number of bits required encode the distribution The cross entropy of and is defined (p. q) Ep[- ll. i.e. the expected number of bits required encode samples from p using code optimized for 9. The KL-divergence between p and q defined as (xz(p || 9) == Ep [log p/1, i... the cost in bits modeling p with q. These three quantities are related by the formula (x q) (p. 4) - (p). The reduction in Y's uncertainty attributable to X is also called the mutual information, I(Y; (Y) HHY X). This quantity is nonnegative, with I(Y; X) 0 if and only if the variables independent.
specific value of X may increase uncertainty in Y, in which case the local posterior entropy exceeds the prior. Thus it is possible that H(Y (x) HYY for some R. For example, consider the following data generating process:
However, conditioning
X (0.), Y Bemn(035 0.25.X).
= 0) = 0.5, and P(Y = 1 X 1) 0.75. It easy to see that even though the marginal entropy H(Y) exceeds the global conditional entropy H(Y X), the
this case, we have P(Y- = 1) 0.7, P(Y
local entropy at X = 0 is larger than either quantity, HY | =0) > H(Y H(Y XX. In other words. conditioning the event X 0 increases uncertainty about Y.
Similarly, there may be cases in which I(Y; X Z) but I(Y; X 2) = 0. This is what Boutilier et al. 7 call context speccifc independence (CSI), For instance, X, 2 E {0, 1 and Y := max X, 2}, then we have 7 X Z. but Y X (Z = 1) since Y's value is determined as soon as we know that either parent is 1.
B.2
The Shapley Axioms
For completeness, we here list the Shapley axioms.
Efficiency.
Shapley values sum the difference in payoff' between complete and null coalitions:
Σ
= = x0,
Symmetry.
If two players make identical contributions to all coalitions, then their Shapley values are equal:
wS S [dM(i.) (i).x) v(S x)) <(i,x) x)..).
Sensitivity.
If player makes zero contribution to all coalitions, then its Shapley value is zero:
AS S [dM{) vSS (f)x)) v(S, x)  x) = 0.
Linearity. The Shapley value for a convex combination games can be decomposed into a convex combina- tion of Shapley values. For any a, b E R and value functions U1, 02 we have:
de +biog (i. advi (i. x) + bebu (j. x).
C Experiments
C.1 Datasets.
The MNIST dataset is available online The IMDB dataset is available Kaggle For the tabular data experiment Sect. we generate according to following process:
p(x) = 3 x. a o²(xx = exp(7> x): Y x Mx*~N((tnn (x(xx) ox)))
Coefficients 3, are independent Rademacher distributed random vectors of length 4.
The BreastCancer, Diabetes, Ionosphere, and Sonar datasets are all distributed in the mlbench package, which is available on CRAN
'Though the term "bit" technically reserved units of information measured with logarithmic base 2, we use the word somewhat more loosely to refer to any unit of information.
http: //wp:////nn..../ lecun, wwt.////wwwwc.ccccc.eee
19

---

Table 1: Estimated quantiles and nominal coverage at a = 0.1 for Shapley values from the conditional mean and conditional variance models. Results are averaged over 50 replicates.
Mean
Variance
Feulure
Coverage
Gn
Caverage
-0.150
-0.512
0.541
X2
-0.138
0.127
0.897
-0.409
0.588
0.900
X3
0.302
X4
-0.094
0.096
0,900
-0.477
1,025
0.898
X5
-0.149
0.093
0.904
0.266
0.324
0.901
X6
-4310
2.203
0.895
-0.041
0.057
0.904
X-
-4.9%
2.268
0.897
-0.047
0.103
0.902
Xg
4.588
4.134
0,900
0.052
0.129
0,900
X10
1.927
0.065
A
B
Ingun
Uscemaury
Uncemaony
Ispat
Man
Eptiteiic Uncetaintt
Unavtainty
Aleatore
7
8
8
8
9
9
4
9
9
6
6
-22
-23
06
01
62
Figure 5: Binary MNIST figure (A) and multiclass MNIST (B), featuring "Mean" column for standard SHAP outputs. For this column, red/blue pixels indicate features that increase/decrease the probability of the true class label. These values anticorrelated with epistemic uncertainty, as expected. The effect is more salient the binary setting, since probability mass is spread out over 10 classes in the multiclass model.
C.2 Models.
All neural network training was conducted in PyTorch [59] For the MNIST experiment, we train deep neural network with the following model architecture: (1) A convolutional layer with 10 filters of size 5 5. followed by max pooling of size 2 2, ReLU activation, and dropout layer with probability 0.3. (2) convolutional layer with 20 filters size X 5, followed by dropout layer, max pooling of size 2, ReLU activation, and a dropout layer with probability 0.3. (3) Fully connected (dense) layer with 320 imput features and 50 output units, followed by ReLU activation and a dropout layer. (4) Fully connected layer with 50 input features and 10 output units, followed by softmax activation. We train with batch size of 128 for 20 epochs learning rate of 0.01 and momentum 0.5. For Monte Carlo dropout, do 50 forward passes sample For the IMDB experiment, we use a pre-trained BERT model from the Hugging Face transformers library 8l All hyperparameters are set to their default values. All XGBoost models are trained with the default hyperparameters, with the number of training rounds cited in the text.
50 subnetworks.
C.3 Coverage
To empirically our conformal coverage guarantee, we compute quantiles for out-of-sample Shapley values on the modified Friedman benehmark. Results for conditional expectation and conditional variance are reported in Table with target level a = 0.1. Note that what constitutes a "small" or "large" interval is context-dependen The conditional variance model is fit to 2,, which has tighter range than Z, leading to smaller Shapley values on average. However, nominal coverage is very close to the target 90% throughout, illustrating how the conformal method can be used for feature selection and outlier detection.
20

---

C.4 Extended MNIST
We supplement the original MNIST experiment with extra examples, including mean column for the true label (Fig. [AA and augmenting the binary problem with the classic 10-class task (Fig. 3). We find that mean and entropy are highly associated in the binary setting, as the analytic formulae suggest, while the relationship somewhat more opaque in the 10-class setting, since we must average over larger set of signals.
21


Reviews:
[{"review_id": "dvds2U93xI", "reviewer": "Reviewer_2QPT", "summary": "Authors aim to explain uncertainty in model outputs by adapting Shapely value framework. In specific, authors try to explain predictive distributions through the lens of entropy, cross-entropy, KL and information gain. Authors offer some theoretic interpretation of the Shapley values adapted with these metrics and, through experiments, show the efficacy of the entropy based variant of Shapely values.", "questions": "1. In Section 6, even through the problems were explained in some detail, I find Section 6 and Appendix C to be lacking in details of methods used and their hyperparameters. Can you please include these details?\n\n2. Some parts of the paper refers to active-learning experiments in the experiments section, but it was not obvious to me how the experiments in the Section 6 are related to active learning. Can you clarify this? \n\n3. In Section 5, authors present computation of entropy (h_t) with a single point estimate and then computation of aleatoric entropy (h_a) with an ensemble of particles. It is not clear how h_t is estimated when we use an ensemble of particles. Can you clarify this?\n\n4. There is reference to script D in line 219. I don't think this was introduced before or referenced later. It would be useful to replace this with an appropriate term.", "limitations": "Please refer to the weakness section.\n\nI am willing to increase my score if authors provide more details about their experiments either in the main paper or the appendix.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. I would like to thank the authors for presenting their work in a very thoughtful manner. I find most of the paper to be clear and intuition which follows propositions and theorems to be very helpful. I like the how the paper introduces theory to offer intuition and make some simplifications to make the method more practical.\n\n2. With raising importance in uncertainty quantification in ML, the work presented in this paper is very relevant to the community. \n\n3. The paper not only presents theoretical analysis of the modified variants of the Shapley values but also offers empirical evidence of how their proposed method works beyond the assumptions made in the theoretical analysis. ", "weaknesses": "\nI might be missing something, but I am unable to understand the specific details of the experiments by reading the main paper and the appendix. (even the supplementary code didn't have much documentation). For example, I couldn't find the details of ensembles method used. What is the size of ensemble (`B` in Sec 5)? Which type of ensemble [5] is being used? What was the batch size how many training epochs were run? \n\nI think there is a line of work on uncertainty estimation and it's interpretation which is missing and might be useful. (A subset of these papers might be useful: [1] , [2], [3], [4])\n\n\n[1] From Predictions to Decisions: The Importance of Joint Predictive Distributions (https://arxiv.org/pdf/2107.09224.pdf)\n[2] Epistemic neural networks (https://arxiv.org/pdf/2107.08924.pdf)\n[3] Evaluating High-Order Predictive Distributions in Deep Learning (https://proceedings.mlr.press/v180/osband22a/osband22a.pdf)\n[4] Marginal and Joint Cross-Entropies & Predictives for Online Bayesian Inference, Active Learning, and Active Sampling (https://arxiv.org/pdf/2205.08766.pdf)\n[5] Ensembles for Uncertainty Estimation: Benefits of Prior Functions and Bootstrapping (https://arxiv.org/pdf/2206.03633.pdf)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer 2QPT (henceforth R1) for their attentive comments and overall positive assessment. We were especially pleased to find that R1 considered our presentation “very thoughtful” and judged “the paper to be clear and intuition which follows propositions and theorems to be very helpful.” We appreciate R1’s suggestion to review other methods for computing and interpreting predictive uncertainty in machine learning. We have incorporated these references into Sect. 2 (Related Work) and Sect. 7 (Discussion).\n\nR1 raises several important questions, which we address below.\n\nQ1. We agree that the presentation in Sect. 6 and Appx. C could be more thorough, and have amended the text to include previously excluded details. In particular, for our image data example, we train a neural network with the following model architecture: (1) A convolutional layer with 10 filters of size 5x5, followed by max pooling of size 2x2, ReLU activation, and a dropout layer with probability 0.3. (2) A convolutional layer with 20 filters of size 5x5, followed by a dropout layer, max pooling of size 2x2, ReLU activation, and a dropout layer with probability 0.3. (3) Fully connected (dense) layer with 320 input features and 50 output units, followed by ReLU activation and a dropout layer. (4) Fully connected layer with 50 input features and 10 output units, followed by softmax activation. We train with a batch size of 128 for 20 epochs at a learning rate of 0.01 and momentum 0.5. For Monte Carlo dropout, we do 50 forward passes to sample $B = 50$ subnetworks. This information has now been added to Appx. C.2. The XGBoost ensembles vary in size from $B = 50$ to $B = 100$, with details provided in Sect. 6. \n\nQ2. We thank R1 for pointing out that it may not be immediately clear how our experiments in Sect. 6 connect to the active learning (AL) setting we mention at several points throughout the text. The connection is strongest in Sect. 6.2 on covariate shift. Following several other authors (e.g., Sugiyama et al., 2007; Quiñonero-Candela et al., 2009), we see this task as basically continuous with AL, since an effective acquisition function will tend to prioritize anomalous samples that appear to be drawn from a different distribution than the training data. These will naturally have high epistemic uncertainty. It is common in the AL literature to use epistemic uncertainty to select for which instances to query the label. This is inherently the case in Query-by-Committee based methods, and has recently become more common also in the uncertainty sampling literature (e.g., Nguyen et al., 2022). We have rewritten the text in this subsection to clarify the connection between these tasks.\n\nQ3. We thank R1 for observing that our discussion in Sect. 5 is potentially ambiguous with respect to the role of individual basis functions $f^b, b \\in [B]$ in defining the total entropy $h_t$. This depends on how we construct the ensemble predictor $f_y(\\mathbf{x}) := p(y \\mid \\mathbf{x})$. The simplest method—widely used in, e.g., random forests and deep ensembles—is to average over the basis functions: $f_y(\\mathbf{x}) := B^{-1} \\sum_{b=1}^B f^b(\\mathbf{x})$. By contrast, in boosting models, predictions represent the sum (rather than the average) of basis model outputs. For more details on aggregating basis functions for probabilistic predictions in random forests, see (Malley et al., 2012); for more on deep ensembles, see (Lakshminarayanan et al., 2017); and for details on uncertainty quantification in gradient boosting, see (Malinin et al., 2021). We have expanded the text in Sect. 5 to include these references and resolve the ambiguity identified by R1.\n\nQ4. The reference distribution $\\mathcal{D}$ was introduced in Sect. 3, specifically the subsection on Shapley values. We have amended the text in Sect. 5 to remind readers of this connection.\n\nWe hope our comments have resolved all of R1’s concerns. If so, we invite them to revise their score upward :) \n\nReferences:\n\n-Sugiyama et al., 2007: https://jmlr.org/papers/v8/sugiyama07a.html \n\n-Quiñonero-Candela et al., 2009: https://mitpress.mit.edu/9780262545877/dataset-shift-in-machine-learning/ \n\n-Malley et al., 2012: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3250568/ \n\n-Lakshminarayanan et al., 2017: https://proceedings.neurips.cc/paper_files/paper/2017/file/9ef2ed4b7fd2c810847ffa5fa85bce38-Paper.pdf \n\n-Malinin et al., 2021: https://openreview.net/pdf?id=1Jv6b0Zq3qi\n\n-Nguyen et al. 2022: https://link.springer.com/article/10.1007/s10994-021-06003-9  \n\n"}, {"review_id": "PD0VKKLRFA", "reviewer": "Reviewer_DQBN", "summary": "This paper introduces a method for explaining the uncertainty in predictions made by DNNs. The authors extend the Shapley values from explaining the value of DNN outputs to explaining the uncertainty of the DNN outputs. Then, the authors demonstrate the close relationship between these Shapley values and the conditional independencies between inputs and outputs. Additionally, the authors provide a theoretical bound to support the coverage of the explanation obtained by the proposed method.", "questions": "1.\tFurther discussion is needed to clarify the motivation and advantages of explaining predictive uncertainty.\n2.\tIt is suggested that the authors perform a quantitative experiment to demonstrate the ability of the proposed method to accurately explain and estimate prediction variance.\n", "limitations": "The authors have discussed the limitation of the method.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper is well-organized and easy to follow. The authors also provide a thorough literature review.\n2.\tThe authors prove some propositions and theorems to support the reliability of the proposed definition of Shapley values in DNNs.\n3.\tIt is good that the authors recognize the presence of both epistemic and aleatoric uncertainty in the prediction of DNNs.\n", "weaknesses": "1.\tThe motivation behind investigating the Shapley values of inputs towards the uncertainty of predictions is not convincing. While the proposed information-theoretic Shapley value reveals which variables contribute to prediction uncertainty, it fails to explain which variables are responsible for correct/incorrect predictions. The original Shapley values defined on the model output can provide this information. On the other hand, the results in Figure 1 do not demonstrate the superiority of the proposed information-theoretic Shapley value. This is because the features that increase predictive uncertainty can also be considered as pixels with negative Shapley values toward the correct prediction. Therefore, the information-theoretic Shapley value does not offer significant additional insights or information.\n2.\tHow should I understand the Shapley values defined on the value functions $v_{KL}$ and $v_{CE}$? When using these value functions, the output $v(N)$ is always 0.\n3.\tIs the proposed information-theoretic Shapley value a local explanation for individual samples or a global explanation over all training samples? If it is a local explanation, what does the coverage of the explanation represent? If it is a global explanation, how is the value function defined over different samples?\n4.\tIn Figure 2, many perturbed inputs are assigned negative Shapley values for predictive uncertainty, which is perplexing. In my understanding, a negative contribution to the predictive uncertainty indicates that this feature is discriminative. However, the perturbed features are typically expected to be non-discriminative.\n5.\tThere is a lack of quantitative experiments to validate the accuracy of the proposed Shapley values in estimating the uncertainty/variance of the prediction. Figure 3(A) just provides qualitative results and Figure 3(B) focuses solely on the ranking of features. I suggest the authors conduct a quantitative experiment to show that the proposed method could precisely explain and estimate the variance of the prediction.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer DQBN (henceforth R2) for their time and feedback. We were pleased to see that R2 found our paper “well-organized and easy to follow”, but would like to clarify several points of potential confusion that were raised in the “Weaknesses” section.\n\nW1. R2 objects that our method “fails to explain which variables are responsible for correct/incorrect predictions.” This is true – and by design. R2 appears to be conflating “uncertainty” (our target) with “error” (not our target). A method such as LossSHAP (Lundberg et al., 2020), which seems closer to what R2 has in mind, would explain the pointwise loss, e.g. the squared residual of each prediction in a regression example. However, this requires labels. As noted throughout the manuscript, *our method is unique in handling cases where labels are unavailable*. This can occur, for instance, in clinical medicine or online advertising, where outcomes are delayed or expensive to collect. As we point out in Sect. 4, there is a close relationship between our proposed games and LossSHAP (using likelihood-based loss functions). Specifically, our games represent average LossSHAP values as we marginalize over $Y$ with respect to different conditional distributions. This is the best we can do without access to labels. Our experiments in covariate shift (Sect. 6.2), which can also be used to explain the selections of an acquisition function for an active learning algorithm, illustrate the utility of our information theoretic Shapley values in cases where LossSHAP is impossible to compute. \n\nBeyond simply removing the need for labels, a key motivation for explaining uncertainty rather than error is that throughout many areas in machine learning there exist methods that are based on uncertainty, and we may need to explain their behavior. A few examples: \nMany active learning algorithms select their queries based on (different notions of) uncertainty, and one may want to know “why did our active learning algorithm query those instances?”\nMany out of distribution (OOD) detection algorithms make their OOD assessments based on some notion of uncertainty, and one may want to know “why did our OOD method assess this instance to be out of distribution?”\nOur methods are uniquely well-suited to handle such questions.\n\nW2. We are unsure why R2 is under the impression that $v_{KL}$ and $v_{CE}$ are invariant functions that map all inputs to zero. This is false. Quoting from Sect. 4: $v_{KL}(S, \\mathbf{x})$ “can be interpreted as $-1$ times the excess number of bits one would need on average to describe samples from $Y \\mid \\mathbf{x}$ given code optimized for $Y \\mid \\mathbf{x}^S$.” The cross entropy value function has a similar interpretation, and is indeed equivalent up to an additive constant. In other words, these value functions measure the information gap between two conditional distributions for $Y$: one based on the complete vector $\\mathbf{x}$, and another based on the partial vector $\\mathbf{x}^S$. Large values can occur when informative features are excluded from $S$. To take an extreme example, consider a case in which $H(Y \\mid X) = 0$, $H(Y) > 0$, and $S = \\emptyset$. Then for all $\\mathbf{x}$, we have $v_{KL}(S, \\mathbf{x}) = v_{CE}(S, \\mathbf{x}) = H(Y)$. In general, these value functions can be made arbitrarily large by letting $Y$’s prior entropy tend toward infinity while its local posterior entropy tends toward zero.\n\nW3. Our proposed value functions compute exclusively *local* Shapley values, as we emphasize in several places throughout the manuscript, e.g. when contrasting against Covert et al.’s (2020) SAGE method in Sects. 2 and 4. However, we acknowledge that this may complicate the interpretation of Thm. 5.1 without further elaboration. Our coverage guarantee pertains not to an individual Shapley value $\\phi(j, \\mathbf{x})$ but rather to the set of all Shapley values for a single feature $X_j$. As we note in the manuscript, the motivation for bounding the spread of this set is that “These results can inform decisions about feature selection, since narrow intervals around zero are necessary (but not sufficient) evidence of uninformative predictors.” In other words, we aggregate local attributions to draw a global inference. This connects with the conditional independence results of Thm. 4.5, which license an interpretation of the marginal payoff function as a conditional dependence measure. We have updated Sect. 5 to make this point more explicit. See also our reply to R4, who raises some questions about this.\n\nW4. Negative Shapley values in this game correspond to feature values that decrease predictive uncertainty relative to a data-dependent baseline (i.e., the prior entropy $H(Y)$). Extremely low values following perturbation indicate over-confidence in the corresponding prediction, a common case of miscalibration under covariate shift (see, e.g., Ovadia et al., 2019). Identifying the sources of such miscalibration can inform decision making. We have added some text to Sect. 6.2 to clarify this point.\n\nW5. We appreciate R2’s suggestion to include a quantitative experiment to demonstrate our method’s ability to accurately explain predictive uncertainty. We have conducted a simulation in which this quantity can be calculated in closed form, and estimated the corresponding Shapley values using a range of different pipelines for imputing out-of-coalition feature values. See the comment to all reviewers above for more details on this experiment. \n\nReferences:\n\n-Lundberg et al., 2020: https://www.nature.com/articles/s42256-019-0138-9 \n\n-Covert et al., 2020: https://proceedings.neurips.cc/paper/2020/file/c7bf0b7c1a86d5eb3be2c722cf2cf746-Paper.pdf \n\n-Ovadia et al., 2019: https://proceedings.neurips.cc/paper_files/paper/2019/file/8558cb408c1d76621371888657d2eb1d-Paper.pdf "}, {"review_id": "2hNPEsh5fw", "reviewer": "Reviewer_yQq8", "summary": "I have previously reviewed this paper at another conference in which, after reviewers' discussion, it was a borderline reject, below my review is enriched with the previous conference discussions.\n\nThis work proposes calculating a modified Shapley value where the coalitional game represents the entropy of the predictive distribution. \nA high-scoring feature will increase the entropy, and a low-score feature will decrease it.\n\nSections 4 and 5 describe the properties of their value function, along with a couple of alternative value functions. They discuss how their value function connects to the notion of information gain, a decomposition of uncertainty into aleatoric and epistemic sources, and a PAC-like technique for testing if a feature's mean Shapley value is near zero. \n\nVarious experiments are performed to illustrate use cases and validate correctness.", "questions": "Since the paper was previously rejected and no major modifications have happened. Why would the authors expect the paper to be accepted this time?", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of using KL divergence and Entropy in combination with Shapley Values to attempt to quantify the individual importance of features is novel and potentially very useful. Not many papers have delved into the topic of attributing uncertainty to input features.\n\n - Nice job deriving properties from the two main coalitional games they discussed \n\n- Extensive set of tests given.", "weaknesses": "In the final discussion, the main reasons to reject were the following:\n\n - Developing metrics to verify the correctness of their results\n - Making their implementation consistent with the methods section. \n - Experimental Limitations: the experimental design is based on papers from Computer Vision, where pure covariate shift is identifiable. \n - Some missing discussions about related work", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer yQq8 (henceforth R3) for taking the time to read and comment on our manuscript (again!). We learned a great deal during the review process for ICML, incorporating reviewer feedback to improve the manuscript in numerous ways—an improvement widely acknowledged by reviewers, who revised their scores upward by 2-3 points on average. We strenuously object to the charge that “no major modifications have happened” since that submission. In fact, Sect. 4 was rewritten in its entirety, with major updates to our theoretical results (including the introduction of context-specific independence structures that went unmentioned in the previous manuscript). We added numerous references to our literature review, including further discussion on related methods such as LossSHAP and SAGE, and amended the experiments to more clearly implement our theory, computing explanations for both epistemic and aleatoric uncertainty under a range of function classes and sampling procedures, in addition to our recently added convergence experiments. We hope R3 will agree that this manuscript has come a long way since we submitted an initial draft to ICML some six months ago.\n\nWe reply to R3’s critiques as laid out in the “Weaknesses” section below:\n\nW1. We appreciate the suggestion, also made by other reviewers, to include more quantitative experiments to evaluate the soundness of our method. Toward that end, we have conducted a simulation experiment in which ground truth Shapley values can be calculated in closed form to see how our estimation procedures fare under a range of data generating processes and imputation methods for out-of-coalition feature values. Echoing results from other XAI studies (Olsen et al., 2023), we find that no single method dominates throughout. However, we tend to converge on true information theoretic Shapley values when sample sizes are large and dependencies between features are well modeled. See our comment to all reviewers above for more details.\n\nW2. Better aligning our methods and experiments section is one of the major changes we have made to the manuscript since the initial ICML submission. This includes expanding the experiments to cover cases of both epistemic and aleatoric uncertainty (as opposed to just total uncertainty), and comparing different methods for reference distribution sampling across different base algorithms. We would be open to adding new experiments to better align these sections if R3 has some specific suggestion(s) in mind? \n\nW3. We are somewhat confused by the claim that “the experimental design is based on papers from Computer Vision.” Sect. 6 includes just a single image data example—from the canonical MNIST—in addition to examples from natural language processing (Fig. 1B), and numerous tabular datasets (Figs. 2, 3). We have made a deliberate effort to include a diverse set of experiments spanning structured and unstructured data types, as well as classification and regression examples. We fail to see how our experimental design is limited to computer vision applications.\n\nW4. We have attempted to cover a wide body of literature in this manuscript, including papers on explainable AI, uncertainty quantification, information theory, and application areas such as active learning, covariate shift detection, feature selection, and classification with reject option. R2 specifically complimented our “thorough literature review”. Our bibliography spans some 80+ references, compared to 55 references in the earlier version of our work that was reviewed at ICML. In any event, we are happy to expand Sect. 2 or Sect. 7 with extra references if R3 has any specific titles in mind.\n\nWe hope this rebuttal goes some way toward addressing R3’s concerns, and kindly request that they consider revising upward :)"}, {"review_id": "t8mECsqaS7", "reviewer": "Reviewer_TWY9", "summary": "The paper aims to define Shapley values to decompose the conditional distribution of the outcome so to attribute the uncertainty of the outcome to individual variables. This aims to extend prior work, which has mainly focused on explaining the change in the conditional mean of the outcome.", "questions": "N/A", "limitations": "The authors discuss some limitations of their method.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The manuscript highlight how methods for explaining the conditional variance can have highly different results from those for explaining the conditional mean. This is nicely shown in the simulation results in Section 6.3 and Figure 3. The authors also nicely highlight how methods for explaining the conditional variance can be useful in many contexts, such as for model calibration.", "weaknesses": "1. There are a number of other papers that have studied how to explain the conditional variance of Y given X using Shapley values. For instance, Williamson and Feng 2020 use Shapley values to determine how well individual features predict Y using some user-defined scoring function V. If this scoring function is set to the deviance/KL divergence, then the resulting Shapley values are highly similar to those discussed in this paper. Moreover, this paper discusses how to efficiently perform statistical inference that sidestep computational issues that arise when considering every possible variable subset. The authors should put the current manuscript in context, given such existing works.\n\n2. The link between conditional independencies and the information theoretic Shapley values defined in this paper follows very directly from how the Shapley values were defined. I don't see why the authors state that this connection is \"deep\" or \"subtle\". Perhaps the authors can clarify why this connection is far from obvious.\n\n3. The proposed Shapley value is characterizing properties of the oracle distribution. Given the framing of the paper, the true target for statistical inference should be the Shapley value with respect to the oracle distribution. However, the result in Theorem 5.1 does not account for the uncertainty in estimating the oracle distribution and performs inference for a different target (seems to be the mean of the Shapley value of the estimated distribution). Moreover, it is not clear to me what the use case is for marginal coverage guarantees like that presented in Theorem 5.1. (Conditional coverage guarantees are ideal, but I agree that is unattainable.) I suggest better motivating (i) why are we doing statistical inference and (ii) what the target of statistical inference is.\n\n4. This framework seems most relevant for explaining the uncertainty of either a continuous outcome or a multi-class outcome. For binary outcomes, the mean-variance relationship suggests to me that the results from using more typical Shapley values will be highly similar to those using this new definition. However, many of the experiments in Section 6 deal with binary outcomes. First, the authors should compare their results to those from using Shapley values for explaining the conditional mean. Second, the author should consider additional experiments dealing with other types of outcomes, to really highlight the utility of their proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank TWY9 (henceforth R4) for their close reading and insightful feedback. \nWe respond to specific issues below.\n\nW1. We thank R4 for pointing us to Williamson & Feng (2020), a reference we had not previously come across. Their SPVIM method is an elegant frequentist alternative to the Bayesian procedure we cite in the original manuscript. However, we dispute the claim that “a number of other papers…have studied how to explain the conditional variance of Y given X using Shapley values”–we are unaware of any such works, and would appreciate the reference(s) that R4 has in mind. The cited W&F paper, for instance, does *not* explicitly do this. Rather, W&F provide a procedure for performing inference using various global measures of “predictiveness”. Though their method could in principle be applied to games that model conditional variance or information theoretic quantities, the authors do not study or implement any such examples. \n\nR4 is correct to point out that existing inference procedures could be applied to our information theoretic Shapley values, a point we also acknowledge in Sect. 5. However, this is orthogonal to our main goals in this paper. First, we propose a number of novel information theoretic Shapley values, which we motivate by their ability to describe conditional dependencies beyond the first moment and their applicability in settings where labels are unavailable. Second, we show that conformal inference can be used to test whether the set of local Shapley values for a single feature tends to concentrate around zero. This is different from testing whether a single local or global feature attribution is significantly far from zero. Of course, one could in principle evaluate global importance by running $n$ tests using a local inference procedure, or compute a global measure upfront instead of aggregating local ones. The former is inefficient by comparison, while the latter requires a global value function, as opposed to the local alternatives we consider here. We have amended the manuscript to better contextualize our contribution and acknowledge the work of W&F. \n\nW2. R4 objects that Thm. 4.5 is “obvious”. We are somewhat sympathetic to this complaint with regards to result (a), which we include primarily for completeness. As for results (b) and (c), we must respectfully disagree with R4’s judgment. That context-specific independence (CSI) is sufficient but not necessary for zero marginal payoff, and that counterexamples to the necessity claim under CSI are measure zero, came to us as something of a surprise. These results rely on carefully constructed examples and an algebraic lemma from the 1970s. If these points were immediately obvious to R4 upon reading the definitions, then we commend R4 for their intuitive command of information and measure theory. We have amended the abstract to avoid all talk of “deep connections”, but are comfortable with the claim in Sect. 4 that our results establish a “somewhat subtle link between conditional independencies and information theoretic Shapley values.” \n\nW3. We thank R4 for pressing us to better motivate our inference procedure in Thm. 5.1 and to clarify our statistical target. First, we reiterate that our primary goal is to define and study a number of local attribution methods based on information theoretic value functions. As a secondary benefit, we may aggregate local attributions to test whether Shapley values concentrate around zero, which is evidence of a globally uninformative predictor. This is useful and efficient when local attributions have already been computed. However, if a researcher’s only goal is to test global importance, then they are better off using global measures upfront. \n\nOur statistical targets in Thm. 5.1 are the upper and lower extrema of *the oracle band*. Let $P_j$ be the true distribution of Shapley values for feature $j$, i.e. $\\phi(j, \\mathbf{x}) \\sim P_j$, with corresponding quantile function $Q_j$. Then the oracle band for level $\\alpha$ is defined as $C^*_j(\\alpha) := \\big[Q_j(\\alpha / 2), Q_j(1 - \\alpha / 2)\\big]$. This band is *optimal* in the sense that it has the shortest length among all bands with valid coverage. Our previous version of this theorem relied on an implicit symmetry assumption to compute split conformal bands. Though symmetry holds for uninformative features, it may not hold in general and is inessential in practice. A more general solution is to report the empirical quantiles as estimated on $\\mathcal{I}_2$. Our modified result therefore reads: $\\mathbb{P} \\big( \\phi(j, \\mathbf{x}^{(n+1)}) \\in \\big[\\hat{Q}_j(\\alpha / 2), \\hat{Q}_j(1 - \\alpha / 2)\\big]  \\big) \\geq 1 - \\alpha$. We have updated our coverage experiments accordingly (PDF, Table 1). \n\nR4 inquires about sources of error for these estimates. We identify three: (i) estimating the target function $h$ from finite samples; (ii) sampling values for out-of-coalition features; and (iii) sampling coalitions. Convergence rates as a function of (i) and (ii) are entirely dependent on the selected subroutines. With consistent methods for both, conformal prediction bands are provably close to the oracle band (see Lei et al., 2018, Thm. 8). We have conducted new experiments to empirically evaluate consistency under a range of conditions (see PDF, Fig. 1). As for (iii), we defer to the results of W&F, who show that with efficient estimators for (i) and (ii), and an extra condition on the minimum number of subsets, sampling $m = \\Theta(n)$ coalitions is asymptotically optimal, up to a constant factor. \n\nW4. We thank R4 for the suggestion to compare our results against those of standard Shapley values to better understand how the two relate (PDF, Fig. 2). As expected, standard Shapley values for binary classification problems are highly predictive of information theoretic Shapley values. The relationship is somewhat less salient in the multiclass setting, as illustrated by our 10-class MNIST experiment (PDF, Fig. 2B). "}]

Author rebuttal:
We thank all the reviewers for their thoughtful comments and constructive feedback. Working through our replies has deepened our understanding of the material and helped us further refine our manuscript. 

We reply to all individual reviewer comments below. However, we open with one general note here, since it came up in multiple reviews. We appreciate the suggestion to include a quantitative experiment that demonstrates our method’s ability to accurately explain predictive uncertainty. We have designed a simulation experiment, loosely inspired by Aas et al. (2021), in which Shapley values under the entropy game have a closed form solution, and tested a range of methods for estimating these quantities in regression examples (see attached PDF, Fig. 1). As with previous work on Shapley value computation, the main considerations to keep in mind here are (i) the accuracy of the conditional entropy estimator (analogous to the base model in more classic XAI settings); (ii) the accuracy of the imputation method for estimating out-of-coalition feature values; and (iii) the coalition sampler. For this experiment, we simulate multivariate normal data with $d=4$ predictors and a Toeplitz covariance matrix with variable autocorrelation. The conditional log-variance of $Y$ is given by a linear function of $\mathbf{X}$. We estimate this conditional variance using multiple regression on the log squared residuals of a linear model for $\mathbb{E}[Y \mid \mathbf{X}]$, and exhaustively enumerate candidate coalitions (generally feasible with $d$ on the order of ~10). For imputation schemes, we compare KernelSHAP, maximum likelihood, copula methods, empirical samplers, and ctree (see Olsen et al., 2023 for definitions of each and a benchmark study of conditional sampling strategies for Shapley values). We note that this is strictly more difficult than the standard case, since $\text{Var}[Y \mid \mathbf{X}]$ is not directly observed but must be estimated from the data. No single method dominates throughout, but we show that under some combinations, we are able to converge on the true information theoretic Shapley value with existing imputation pipelines. This demonstrates both the accuracy of our method and its modularity with respect to reference distribution samplers. We thank the reviewers for pressing us on this point and encouraging us to add this valuable experiment to Sect. 6.

The attached PDF also includes some revised or expanded experiments, in reply to particular reviewer comments (see below).


References: 

-Aas et al., 2021: https://www.sciencedirect.com/science/article/pii/S0004370221000539 

-Olsen et al., 2023: https://arxiv.org/abs/2305.09536 

Meta-review: This paper is concerned with explaining the uncertainty of model outputs. The novelty lies primarily in proposing and studying a number of information theoretic value functions that are not in widespread use, and illustrating their applicability for settings that require uncertainty quantification (e.g., active learning and out-of-distribution detection). All reviewers agreed with this contribution and most found this useful. As the authors indicated the proposed Shapley values complement rather than supplant existing alternatives. With the raising importance of uncertainty quantification in ML, this work is very relevant to the community. The paper also provide a non-trivial theoretical analysis as acknowledge by the most critical reviewer. Finally, the authors provided a clear and solid rebuttal addressing the concerns raised by the reviewers. I would encourage the authors to incorporate the feedback to further strengthen the paper.

It should be noted that the paper was previously rejected by ICML. All pending issues have been taken into account and the work has been significantly improved (and expanded as requested).
Decision: Accept (poster)