RKHS-SHAP: Shapley Values for Kernel Methods
Authors: Siu Lun Chau
Robert Hu
Javier Gonzalez
Dino Sejdinovic
Venue: NeurIPS 2022 Accept (2022)
Keywords: Kernel Methods
Shapley Values
Explainable AI

Abstract: Feature attribution for kernel methods is often heuristic and not individualised for each prediction. To address this, we turn to the concept of Shapley values (SV), a coalition game theoretical framework that has previously been applied to different machine learning model interpretation tasks, such as linear models, tree ensembles and deep networks. By analysing SVs from a functional perspective, we propose RKHS-SHAP, an attribution method for kernel machines that can efficiently compute both Interventional and Observational Shapley values using kernel mean embeddings of distributions. We show theoretically that our method is robust with respect to local perturbations - a key yet often overlooked desideratum for consistent model interpretation. Further, we propose Shapley regulariser, applicable to a general empirical risk minimisation framework, allowing learning while controlling the level of specific feature's contributions to the model. We demonstrate that the Shapley regulariser enables learning which is robust to covariate shift of a given feature and fair learning which controls the SVs of sensitive features. 

RKHS-SHAP: Shapley Values for Kernel Methods
Siu Lun Chau Department of Statistics University of Oxford
Robert Hu Amazon London
Javier Gonzalez Microsoft Research Cambridge
Dino Sejdinovic
School of Computer and Mathematical Sciencest University of Adelaide
Abstract
Feature attribution for kernel methods often heuristic and not individualised for each prediction. To address this, we turn to the concept of Shapley values (SV), a coalition game theoretical framework that has previously been applied to different machine learning model interpretation tasks, such as linear models, tree ensembles and deep networks. By analysing SVs from a functional perspective, we propose RKHS-SHAP, attribution method for kernel machines that can efficiently compute both Interventional and Observational Shapley values using kernel mean embeddings of distributions. We show theoretically that method is robust with respect to local perturbations- - key yet often overlooked desideratum for consistent propose Shapley regulariser, applicable to
model interpretation. Further, general empirical risk minimisation framework, allowing learning while controlling the level of specific feature's 's contributions to the model. We demonstrate that the Shapley regulariser enables learning which is robust to covariate shift of a given feature and fair learning which controls the SVs of sensitive features.
Introduction
Machine learning model interpretability is critical for researchers, data scientists, and devel- opers to explain, debug and trust their models and understand the value of their findings. A typical way to understand model performance to attribute importance scores to each input fea-
50 = Age
+117
ture [5]. These scores be computed either for an entire dataset to explain the model's overall be-
+0.11
haviour (global) compute individually for each single prediction (local).
0 Insulin
35.6
46.29
Understanding feature importances in reproducing kernel Hilbert space (RKHS) methods such as kernel ridge regression and support vector machines often require the study of kernel lengthscales across dimen- sions [44 Chapter 5]. The larger the value, the less relevant the feature is to the model. Albeit straightfor- ward, this approach comes with three shortcomings: (1) It only provides global feature importances and cannot be individualised each single prediction.
10.0
35 SkinThickness
4000
Prognancies
40:03
72 BloodPressure 1003
04
85
85
07
08
09
10
11
Figure 1: An example RKHS- SHAP pro- viding local explanations to why a kernel logis- tie model predicts this patient to be diabetic. [ RKHS-SHA provides more granular level of explanation than studying lengthscales across di- mensions.
Work mainly done while the authors were with the
Department of Statisties, University of Oxford
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

This explanation is limited as global importance does
not necessarily imply local importance (33)) In safety critical domain such medicine, understand- ing individual prediction is arguably more important than capturing the general model performance. See Fig [ for an example of local explanation. (2) The tuning of lengthscales often requires a user- specified grid of possible configurations and is selected using rross-validations. This pre-specification thus injects substantial amount of human bias to the explanation task. (3) Lengthscales across kernels acting on different data types, such as binary and continuous variables, are difficult to compare and interpret.
To address this problem we turn to the Shapley value (SV) 35 literature, which has become central many model explanation methods in recent years. The Shapley value was originally concept used in game theory that involves fairly distributing credits to players working coalition. Strumbelj and Kononenko [40] were one of the first to connect SV with machine learning explanations by casting predictions coalition games, and features as players. Since then, variety of SV based explanation models were proposed. For example, LINEARSHAN
40 for linear models, TREESHAP (24] for tree ensembles and DEEPSHAP [23] for deep networks. Model agnostic methods such as DATA- SHAPLEY [13], SAGE 9 and KERNELSHAP 2
(3 were also proposed. However, to the best of our knowledge, an SV-based local feature attribution framework suited for kernel methods has not been proposed.
While could still apply model-agnostic KERNEL kernel machines, we show that by representing distributions as elements in the RKHS through kernel mean embeddings [38] 27 we can compute Shapley values more efficiently by circumventing the need to sample and estimate an exponential amount of densities required to compute the value functions, an essential compo- nent for Shapley value computation. We call this approach RKHS-SHAL to distinguish it from KERNELSHAP. Through the lens of RKHS, we study Shapley values from functional perspective and prove that our method is robust with respect to local perturbations under mild assumptions, which is an important yet often neglected criteria for explanation models as discussed in Hancox-LA 177. In addition, a Shapley regulariser based on RKHS -HAPP is proposed for the empirical risk minimisation framework, allowing the modeller to control the degree of feature contribution during the learning. We also discuss its application to robust learning to covariate shift of a given feature and fair learning while controlling contributions from sensitive features. We summarise our contributions below:
1.
We propose IKHS-SHAL model specific algorithm to compute Shapley values efficiently for kernel methods by circumventing the need to sample and fit from an exponential number of densities.
2. We prove that the corresponding Shapley values are robust to local perturbations under mild assumptions, thus providing consistent explanations for the kernel model.
3. We propose a Shapley regulariser for the empirical risk minimisation framework, allowing the modeller to control the degree of feature contribution during the learning.
The paper is outlined as follows: In section 2 we provide an overview of Shapley values and kernel methods. In section 3 we introduce RKHS-SHAP and show robustness of the algorithm. Shapley regulariser is introduced in section 4. Section 5 provides extensive experiments. We conclude our work in section 6.
2 Background Materials
Notation. We denote X, Y as random variables (rv) with distribution p(X, Y) taking values in the d-dimensional instance space X' C dRd and the label space y (could be in IR or discrete) respectively. We use D {l....,dd d} to denote the feature index set of X and S C D to denote the subset of features of interests. Lower case letters are used to denote observations from corresponding rvs.
2.1 The Shapley Value
The Shapley value was first proposed by Shapley [35 to allocate performance credit across coalition game players in the following sense: Let v: {0. 1 + F be coalition game that returns a score for each coalition S C Dg. where D, (1, ..., d} represents a set of players. Assuming the grand
'The kernel in KERNELSHAP refers the estimation procedure is not related RKHS kernel methods.

---

coalition Dg is participating and one wished to provide the 1th player with a fair allocation of the total profit v(Dg). 9), how should one do it? Surely this is related to each player's marginal contribution to the profit with respect to a coalition S. i.e. U)) v(S). Shapley (35] proved that there exists a unique combination of marginal contributions that satisfies a set of favourable and fair game theoretical axioms, commonly known as efficiency, null player; symmetry and additivity. This unique combination of contributions is later denoted as the Shapley value. Formally, given a coalition game v, the Shapley value for player is computed the following,
Φ5(1)
1 d
Σ SCDMM
( d (15)) (
Choosing v for ML explanation In recent years, the Shapley value concept has become popular for feature attribution in machine learning. SHAP [23]. SHAPLEY EFFECT (37, DATA-SHAPLEY [T] and SAGE (9] are all examples that cast model explanations as coalition games by choosing problem- specific value functions v. Denote f : X + )' as the machine learning model of interest. Value functions for local attribution on observation x often take the form of the expectation of with respect to some reference distribution r(Xs= | Xx = xs), where S C D is some coalition of features in analogous to the game theory setting, such that:
V2,s( (f) = [X mg (fgrl))aa (ff(f Xs:
(2)
where {as, } } denotes the concatenation of the arguments. We wrote f as the main argument of to highlight its interpretation as a functional indexed by local observation x and coalition S. When set to be marginal distribution, i.e r(Xs= X = rs) = p(Xs=). the value function is denoted as the Interventional value function by Janzing et al. (0) Observational value function [33, on the other hand, set the reference distribution to conditional distribution p(Xg-- Xs = rs). Other choices of reference distributions will lead to Shapley values with specific properties, e.g., better locality of explanations [14] or incorporating causal knowledge
[8]. In this work we shall restrict our attention to marginal and conditional cases as they are the two most commonly adopted choices in the literature.
Definition 1. Given model f. local observation x. and coalition set S C D, the Interventional and Observational value functions are denoted by (f) == Exge [f((fzg xg= })] and U00 (f) =
Exge [f(f }) Xg = xs)-
The right choice of y has been long-standing debate in the community. While Janzing et al. 20
argued from a causal perspective that (T) is the correct notion to represent missingness of features in an explanation task, Frye et al. [ argued that computing marginal expectation ignores feature correlation and leads to unrealistic results since one would be evaluating the value function outside the data- mata-mmaiffod. This controversy was further investigated by Chen et al. [6]. where they argued that the choice of y is application dependent and the two approaches each lead to an explanation that either true to the model (marginal expectation) or true to the data (conditional expectation). When the context is clear, we denote the Shapley value of the jth feature of observation x at f as (f, and use a superscript to indicate whether is Interventional of4) (f) or Observational (000 (ʃ)-
Computing Shapley values. While Shapley values can be estimated directly from Eq. ① us- ing a sampling approach [40]. Lundberg and Lee [23 proposed KERNELSHAP, a more effi- cient algorithm for estimating Shapley values in high dimensional feature spaces by casting Eq. ( as a weighted least square problem. Similar to LIME 33 for each data x, model f. and feature coalition S. KERNELSHAP places a linear model Ug (S) 32,0 + Eies Be, to ex- plain the value function (f)s(f), which corresponds solving the following regression problem: min............ EsgD (u, (f)2 where w(S) (1s
d-1 is carefully chosen
weighting such that the regression coefficients recover Shapley values. In particular, one set w(0) = w(D)= oo to effectively enforce constraints 3,.0 = p (f) and EieD Sa,i (f) V2 (f). Denoting each subset 5 C D using the corresponding binary vector z E {0, 1)d, and with an abuse of notation by setting V. ;= v.s and w(z)= := w(() for S [j z 1}, we can express
the Shapley values B_ : [Be,0.... 3r,a] as B_ = (Z 1)) Wv, where Z E Eg² xd is the binary matrices with columns {2, 1= W is the diagonal matrix with entries ww w(z.) and
3

---

v= (x (1) E R²'x1 the vector of evaluated value functions, which is often estimated using sampling and data imputations. We shall explain the pathology of this approach in detail later in Section 3 In practice, instead of evaluating at all 2 combinations, one would subsample the coalitions- 2 ~ w(2) for computational efficiency (8]
Model specific Shapley methods. KERNELSHAP provides efficient model-agnostic estimations of Shapley values. However, by leveraging additional structural knowledge about specific models, one could further improve computational performance. This leads to a variety of model-specific approxi- mations, most of which relies on utilising their specific structure to speed up computation of value functions. For example, LLNEARSHAL [40) explain linear models using model coefficients directly. TREESHAP (4 provides an exponential reduction in complexity compared to KERNELSHAP by exploiting the tree structure. DEEPSHAP 223, on the other hand, combines DEFPLIFT KG with Shapley values and uses the compositional nature of deep networks improve efficiencies. However, to the best of our knowledge, kernel method specific Shapley value approximation has not been studied. Later in Section 3 we will show that, under a mild structural assumption on the RKHS, kernel methods can be used to speed up the computation in KERNELSHAP by estimating value functions analytically, thus circumventing the need for estimating and sampling from an exponential number of densities.
Related work on kernel-based Shapley methods. Da Veiga [O''s work on tackling global sen- sitive analysis by proposing the kernel-based maximum mean discrepancy as value function, is conceptually most similar to ours. However, there are multiple key differences in our contributions. Firstly, their method is designed for global explanation, while ours is for local. Secondly, similar to interventional SV, they do not consider any conditional distributions, thus leading to completely different estimation procedures and thus novelty. Lastly, their method is on understanding the input/outputs relationship of numerical simulation model, while ours focuses on understanding specific RKHS models learnt from a machine learning task, e.g. kernel ridge regression and kernel logistic regression.
2.2 Kernel Methods
Kernel methods are one of the pillars of machine learning, as they provide flexible yet principled ways to model complex functional relationships and come with well-established statistical properties and theoretical guarantees.
Empirical Risk Minimisation. Recall in the supervised learning framework, we are learning a function f X - y' from a hypothesis space H. such that given a training set (x, [<T, 9/: ) sampled identically and independently from p. the following empirical risk is minimised: f arg men N. Σm Eyy, f(x:))
+ + +XyS((f), where y y> + R is the loss function, Ω H - IR a regularisation function and ' a scalar controlling the level of regularisation. Denote A: : X' X - IR a positive definite kernel with feature map V. for input æ E X and H4 the corresponding RKHS. If we pick H4 as hypothesis space, then the Representer theorem [39 tells us that the optimal solution
takes the form of f = Ei=1 a,k(,, x;) = V ax where Vx = [w',. ..,,], is the feature matrix defined by stacking feature maps along columns. If É is the squared loss then the above optimisation
is known as kernel ridge regression and a can be recovered in closed form a = (Kxx + 7y
where Kxx = V x Vx is the kernel matrix. If E is the logistic loss, then the problem is known as kernel logistic regression, and a can be obtained using gradient descent.
Kernel embedding of distributions. An essential component for RKHS SASS- is the embedding of both marginal and conditional distribution of features into the RKHS 38 27). thus allowing one to estimate the value function analytically. Formally, the kernel mean embedding (KMF) of marginal distribution Px is defined as 'x == x [Wx] fxx v²dPx((2) (x) and the empirical estimate can be obtained as j 7. Ei th..- Furthermore, given another kernel g y x y - R with feature map why of RKHS Hy. the conditional mean embedding (CMB) of the conditional distribution Py|x== is defined as μy|X== == E[ |X- = x] = Sy d UydPy|x=x(1))
One way to understand CME to view as an evaluation of a vector-valued(VV) function HYJx X + Hy such that (z)x(x)) = Hy|x= which minimises the following risk function Ep(x,r)lllyy- - XY)xx (3), [16). Let ((H,) be the space of bounded linear operators from H. to

---

itself. Denote r. : x'x X -
L(Hg) as the operator-valued kemel such that [x x²) k(x, x')1 with 1 the identity operator on Hg. We denote Hr, as the corresponding vector-valued RKHS. By utilising the VV-Representer theorem (26). we could minimises the following empirical risk:
βyix= = arg min
Σ 1 - X + ny mylxaxil
(vy EHr,
where 7j > 0 is a regularisation parameter. This leads the following empirical estimate of the CME, i.e. py x Vy (Kxx + + where Vy := [v...l. and V/x :- [..... are feature matrices. Intuitively, this essential turns CME estimation to a regression problem from to the vector-valued labels thy Please see Micchelli and Pontil (26] and Grünewääler et al. []6] for further discussions on vector-valued RKHSs and CMEs. In fact, when using mmite-dimensional feature maps, such as in the with running Random Fourier Features 32 and Nyström methods [45] for scalability, one could reduce the computational complexity of evaluating empirical CME from (nz)) to O(b²) + (bbnn [27 where b is the dimension of the feature map and often can be chosen much smaller than n 21
3 RKHS-SHAP
While KERNELSHAP is model agnostic, by restricting our attention to the class of kernel methods, faster Shapley value estimation can be derived. We assume our RKHS takes a tensor product structure, i.e. H/- Øi= i= Hy(e), where ((() is the kernel for each dimension i E D. This structural assumption allows us to decompose the value functionals into tensor products of embeddings and feature maps, thus we can estimate them analytically, as later shown in Prop. 2 Tensor product RKHSs are commonly used in practice, as they preserve universalities of kernels from individual dimension [22] thus providing a rich function space. Note that this assumption is not essential within our framework. Namely, for a non- produrouut kernel, one can still evaluate the value functions using tools from conditional mean embeddings and utilise our interpretability pipeline without conditional density estimation. We show this in Appendix C In the following, we will lay out the disadvantage of existing sampling and data imputation approach and show that by estimating the value functionals as elements in the RKHS, we can circumvent the need for learning and sampling from an exponential number of conditionals densities thus improving the computational efficiency in the estimation.
Estimating value functions by sampling. Estimating the Observational value function 50 (f) is
typically much harder than the Interventional value function (f) as it requires integration with respect to the unknown conditional density p(Xs= Xs). Therefore, estimating OSVs often boils down to a two-stage approach: (1) Conditional density estimation and (2) Monte Carlo averaging over imputed data, as shown in Aas et al. [. where they considered using multivariate Gaussian and Gaussian Copula for density estimation. Recently, an alternate way to estimate observational regression
value functions is proposed by Frye et al. 13 where they formulate the estimation problem and compute the value function using a masked neural network directly without making any distributional assumption. This method shares conceptual similarities to ours but uses very different tools for the estimation. We highlight such diffcrences in the appendix B
Once the conditional density function p(Xs= Xs) for each S C D is estimated, the observational value function at the hh observation 2; can then be computed by taking averages of m Monte Carlo samples from the estimated conditional density, i.e. m Σド= ((aras where {
is the concatenation of xis with the jth sample se from p(Xg- = zis). Note further that the Monte Carlo samples cannot be reused for another observation FA their conditional densities are different. In other words, n X m Monte Carlo samples are required for each coalition S if one wishes to compute Shapley values for all n observations. This is clearly not desirable. In the spirit of Vapnik's s principle as our goal is to estimate conditional expectations that lead to Shapley values, are not going solve harder and more general problem of conditional density estimation as an intermediate step, but instead utilise the arsenal of kernel methods to estimate the conditional expectations directly. Further discussion on comparing complexity of RKHS-SHAP with density estimation methods can be found in Appendix A
When solving problem. try to avoid solving more general one an intermediate step.
43 Section 1.9]
5

---

Estimating value functions using mean embeddings. If our model f lives in Hy. both the marginal and conditional expectation can be estimated analytically without any sampling or density estimation. We first show that the Riesz representations BQ of both Interventional and Observational value functionals exist and are well-defined in Hy. In the following, for simplicity, we will denote the functional and its corresponding Riesz representer using the same notation. For example, we will write Vs,s( (f) = (f, Ps,s) Hy when the context is clear. Given a vector of n instances x, we denote the corresponding vector of value functions as Vx (f) (V,,s(f)) can be found in the Appendix D
All proof' of this paper
Proposition 2 (Riesz representations of value functionals). Denote k as the product kernel of d bounded kernels klt) : x(6) x X60 + R, where X is the domain of the 1th feature for i E D. Riesz representations of the Interventional and Observational value functionals then exist and can be written as V
(1) +Vas @ pXgee and (0) = Vas 8 Xx=xx where Das == DiES Date,
Mx == El
ies Va(o] and pxgee (x = El iES" P200) Xx = xs].
The corresponding finite sample estimators ( and 110) are then obtained by replacing the corre- sponding KME and CME components with their empirical estimators. As a result, given f xxa trained on dataset (x. y), Prop. 2 allows us to estimate the value functionals analytically since (l = (f", tazg @ Dxge) and 26 (f*) = (f" thag @ ( This corresponds to the direct non- con-aaamettric estimators of value functions given in the following proposition, which circumvent the need for sampling or density estimation.
a,s
a,
Proposition 3. Given x' E Rn a vector of instances and f f= xxa, the empirical estimates of the (00 TT(()
functionals can be computed as, 1 2.)) (f) a x
x, a aTk(o, respectively, where
x Kxxx' 3
T and K(0) Kxaxx OEsKxxx, 1n is the all-one vector with length n, O the Hadamard product and Eg = Kx (Kxxxs + +nnl)=
1 n diag(K Xg 1n) In)
Finally, to obtain the Shapley values with these value functions, we deploy the same least square approach as KERNELSHAP.
Proposition 4 and all n input can be computed as B = (Z W - WV where V..- = (f).
Given f E Hy and u, Shapley values B E Bdxn for all d features
Estimating value functions with specitic models. To the best of our knowledge, TreeSHAP 24 was the only machine learning model-specific SV algorithm computing conditional expectations using the properties of the model (tree in this case) directly, rather than relying on some sort of sampling procedure and density estimation. However, it is unclear how to validate the assumptions about feature distribution in TreeSHAP, which are specified as "the distribution generated by the tree", as discussed by Sundararajan and Najmi (41). In comparison, RKHS- SHAP does not pose assumptions on the underlying feature distribution and computes the corresponding conditional expectations via mean embeddings analytically. However, one should note that each of these model specific algorithm are only designed to explain specific models, therefore not informative to compare, e.g. TreeSHAP values with EKHS-SHAL values, as they are explaining different models.
3.1 Robustness of RKHS-SHAP
Robustness of interpretability methods is important from both epistemic and ethical perspective, as discussed in Hancox-Li 17 On the other hand, Alvarez-Melis and Jaakkola [2 showed empirically that Shapley methods when used with complex non-linear black-box models such neural networks, yield explanations that vary considerably for some neighbouring inputs, even if the deep network gives similar predictions at those neighbourhoods. In light of this, we analyse the Shapley values obtained from our proposed RKHS-SHAP and show that they are robust. To illustrate this, we first formally define the Shapley functional,
Proposition 5 (Shapley functional). Given value functional v indexed by input x and coalition S, the Shapley functional Φz,i : HH + E such that (2,((f) gives the 7th Shapley values of x on f. has the following Riesz representation in the RKHS: Φz,i 1/2 Esgo(() (1=1) (Va Vx,s)
Analogously, we denote (1 and (0) as the Interventional Shapley functional (ISF) and Observa- tional Shapley functional respectively (OSF). Using the functional formalism, now show that

---

given f E Hy, when || 22111 < 8 for 8 > 0, the difference in Shapley values at and z' will be arbitrarily small for all features i.e. (8z,; ox is small Vi D. This corresponds to the following,
(3) where we use Cauchy-Schwar for the last line. Therefore, for given f with fix RKHS norm, the key to show robustness lies into bounding the Shapley functionals. In the following theorem, we make two assumptions: (1) the base kernels k(*) for each dimension i E D are bounded, and (2) the (population) conditional mean embedding functions gx Xx belong to the vector- RKHSs Hrx; for all coalitions S S D. therefore have finite norms. This assumption is also adopted in Park and Muandet (29] Theorem 4.5].
102,(() - Px ((,))
ow ,)12 = II I0 - Oar allie
Theorem 6 (Bounding Shapley functionals). Let k be product kernel with d bounded kernels (x, S M for all E D. Denote Mp supscD D M|SI Mr supscD ge llfx and Ls supscp Ilbas U2 Ilu.. Let ő O, assume (x(0) - 1x 12 < 8 for all features i E D, then differences of the Interventional and Observational Shapley functionals for feature at observation
x, x' can be bounded |10 - - 1l.. 42MyLs and 11020 o S M,ss If k is the RBF kernel with lengthscale 1, then
11 -
of S $4(1 4111- exp(- exp((
11010
of S 8Mr(1 exp(-d6/211))
Therefore, as long as ll is small, EKHS-SHAY will return robust Shapley values with respect to small perturbations. Notice the Shapley functionals do not depend on f and can be estimated separately purely based on data. We will show in the next section how this key property allows us to use the functional itself to aid in learning of f. This enables us to enforce particular structural constraints on f via an additional regularisation term.
Shapley regularisation
Regularisation is popular in machine learning because it allows inductive bias to be injected to learn functions with specific properties. For example, classical L1 and Le regularisers are used to control the sparsity and smoothness of model parameters. Manifold regularisation [4], the other hand, exploits the geometry of the distribution of unlabelled data to improve learning in a semi-supervised setting, whereas Pérez-Suay et al. [1 and Li et al. [22] adopted a kernel dependence regulariser to learn functions for fair regression and fair dimensionality reduction. In the following, we propose a new Shapley regulariser based the Shapley functionals, which allows learning while controlling the level of specific feature's 's contributions to the model.
Let A be specific feature whose contribution we wish to regularise, f the function we wish to learn, and (f) the Shapley value of A at a given observation 2;. Our goal is to penalise the mean squared magnitude of (0r,,A() (f)) -==1 in the ERM framework, which corresponds to sin, Σi=1 Elys. fx:)) + \y| 1/, + As Σn= (f))) where é is some loss function and Xy and Äs control the level of regularisations. If we replace the population Shapley functional with the finite sample estimate from Prop. [ and utilise the Representer theorem, we can rewrite the optimisation in terms of a.
Formulation
Proposition 7. The above optimisation can be rewritten as, miDAER" Σi= E(y,, Kz Aya Kxx + A T ac To regularise the Interventional SVs (ISV-REG) of A, we set SA= - E S -KL,,, For regularising Observational SVs (OSV-REG), we set ÇA = + KSSJAA Kx
Kx,S, where Sy's are coalitions sampled from psv (8) d 1/d-1 (0) (0)
[s|
In particular, closed form optimal dual weights (K2 + X5 + A CACT) Kxxy can be recovered when is the squared loss.
Choice of regularisation. Similar to the feature attribution problem, the choice of regularising against ISVs or OSVs is application dependent and boils down to whether one wants to take the correlation of A with other features into account or not.
7

---

We demonstrate specific properties of experiments, because these properties are best illustrated under fully controlled environment. For example, to highlight the merit of paauttionallasumptionn SHAP, we need groundtruth conditional expectations of value functions for verification, but they are not available in real-world data because we do not observe the true data generating distribution. Nonetheless, model interpretability is practical problem, we have also ran several larger scales (n = 50000, 1.8 x 10%) real-world explanation tasks using RKHS- SHAP and reported our findings made 01 Estimating ISVs
(ii Run time analysii
Robustness experiment
RKHS445V
RKISS-OV GSHAN-SSV
hose o
2:
Ligit seconds
0.0
12
1.0
(i) Estimating OSVs
10
2: 0.5
1.0
2.0
16.0
20.0
100.6
150.0
500.0
1000.0 1500.0 3000.0 s000.0
0.5
0.5
3.0
1.5
2.0
2.5
Namber of dats
Shapley Reguleristionn
(a) RKHS-SHAP experiments
(b) ISG experiments
Figure 2: (a) RKHS-SHAY Estimation Shapley values using data from the Banana distribution. Run time analysis in log scale also reported.
(b) ISV-REG: RMSEs of fry on noisy test data at different noise level o'. All scores are averaged over 10 runs and sd is reported.
ISV-REG VSV-REG can be used to protect the model when covariate shift of variable A is expected to happen at test time and one wishes to downscale A's contribution during training instead of completely removing this (potentially useful) feature. Such situation may arise if, e.g., different measurement equipment or process is used for collecting observations of A during test time. ISV is well suited for this problem as dependencies across features will be broken by the covariate shift at test time.
OSV-REG On the other hand, OSV-REG can find its application in fair learning learning function that fair with respect to some sensitive feature A. There exist a variety of fairness notions one could consider, such as, e.g. Statistical Parity, Equality of Opportunity and Equalised Odds 77.. In particular, we consider the fairness notion recently explored in the literature [9] 25 that uses Shapley values, which are becoming bridge between Explainable AI and fairesss, given that they can detect biased explanations from biased models. In particular, Jain et al. [19] illustrated that if a model is fair against sensitive feature A, A should have neither positive contribution towards the prediction. This corresponds to A having SVs with negligible magnitudes. Simply removing A from the training doesn't 't make the model fair, contributions of A might enter the model via correlated features, therefore it is important to take feature correlations into account while regularising. Hence, it is natural to deploy OSV-REG for fair learning.
negative
Experiments
and Shapley regularisers using four synthetic
value function estimation RKHS-
in Appendix E for complete empirical demonstration. All code and implementations publicly available 3.
In the first two experiments, we evaluate RKHS-SHAP methods against benchmarks on estimating Interventional and Observational SVs on canana-shaped distribution with nonlinear dependen- cies 34] The setup allows us to obtain closed- expressions for the ground truth ISVs and OSVs, yet the conditional distributions among features are challenging to estimate using any stan- dard parametric density estimation methods. We also present run time analysis to demonstrate empirically that mcan embedding based approaches are significantly more efficient than sampling based approaches. Finally, the last two experiments applications of Shapley regularisers in robust modelling to covariate shifts and fair learning with respect to a sensitive feature.
In the following, we denote RKHS- -SV and RKHS -IV as the OSV and ISV obtained from RKHS- algorithm SERNELSHAP
SHAP. As benchmark, we implement the model agnostic sampling-bate from the Python package shap 23 We denote the ISV obtained from KERNELSHAP as KSHAP-ISV. As shap does not offer monel-agnostic OSV algorithm, we implement the approach from Aas et al. 11 (described in Section 3), where OSVs are estimated using Monte Carlo samples from fitted multivariate Gaussians. We denote this approach as GSHAP-OSV. We fit a kernel ridge regression on each of our experiments. Lengthscales of the kemel are selected using median heuristic [12] and
8

---

regularisation parameters are selected using cross-validation. Further implementation details and real world data illustrations are included in Appendix E
5.1 RKHS-SHAP experiments
Estimating Shapley values from Banana data. We consider the following 2d- Banana distribution B(b-1, .e) from Sejdinovic et al. [4] Sample Z [(0, diag(e, 1)) and transform the data by setting X1 = Z1 and X₂ = b- (z} v) + Zz. Regression labels are obtained from fuuth (X) = b- 'Xx 2) X2- This formulation allows us compute the true ISVs and OSVs in closed forms, i. (ftuh) = (x? - v), (fmun)))) = X2, @ (0) (Juath) = (33-'((7 -v) - -22) and Φ (0) (fmm)) = (xx u)). In the following we will simulate 3000 data points from B(b-1 10) with b E [1, 10, 20, 50, 100). where smaller values of b correspond to more nonlinearly clongated distributions. We choose as our metric since the true Shapley values for each experiment are scaled according to 6. Figure 2a(i) and 2a(ii) demonstrate R² scores of estimated ISVs and OSVs in contrast with groundtruths SVs across different configurations. We that RKHS-ISV and KSHAP-ISV give exactly the same R² scores across configurations. This is not surprising as the two methods are mathematically equivalent. While in KSHAP-ISV one averages over evaluated {f {f(²)) with z being the imputed data, RKHS-ISV aggregated feature maps of the imputed data first before evaluating f. i.e - = (J. ;- d(xx;)) 1)H,) H. (ʃ, jxx Ht However, it is this subtle difference in the order of operations contribute to a significant computational speed difference as we later show in Experiment 2. In the case of estimating OSVs, we see RKHS-OSV is consistently better than GSHAP-OSV at all configurations. This highlights the merit of RKHS-OSY as no density estimation is needed, thus avoiding any potential distribution model misspecification which happens in GSHAP-OSV.
Experiment 1:
Experiment 2: Run time analysis. In this experiment we sample n data points from ((1, 10) where E [100, 500, 1000, 1500, 3000, 5000] and record the 1og seconds required to complete each algorithm. In practice, as the software documentation of shap suggests, one is encouraged to subsample their data before passing to the KERNELSHAF algorithm as the background sampling distribution to avoid slow run time. As this approach speeds up computation at the expense of estimation accuracy since less data is used, for fair comparison with our -KHS-SHAP method which utilises all data, we pass the whole training set to the KERNELSHAP algorithm. Figure (iii illustrates the run time across methods. We note that the difference in runtime between the two sampling based methods KSHAP-ISV and GSHAP-OSV can be attributed to a different software implementation, but observe that they are both significantly slower than RKHS-ISV and R RKHS-OSV. RKHS-OSV is slower than RKHS-ISV as it involves matrix inversion when computing the empirical CME. In practice, one can trivially subsample data for RKHS-SHAP to achieve further speedups like in the shap package, but one can also deploy a range of kernel approximation techniques as discussed in Section
5.2 Shapley regularisation experiments
For the last two experiments we will simulate 3000 samples from X N Σ) with diag (E) = 1s and Σ,,5 Σg,4 = 0.9, O otherwise, therefore feature X, and XG will be highly correlated. We set our regression labels as (x) = 33 with 3 [1, 2, 3, 4, 10), enforcing Xs to be the most influential feature. We use 70% of our data for training and 30% for testing.
Experiment 3: Protection against covariate shift using ISV-REG. For this experiment, we inject extra mean zero Gaussian noise to the most influential feature X; in the testing set, i.c. X = X5 + o' N (0, 1) for o' E [0, 0.1, 0.5, 1, 1.5). We assume that there is an expectation for covariate shift in X5 to occur test time, due to e.g. a change in the measurement precision hence, we train our model freg using ISV-REG at different regularisation level X, for X E [0, 0.5. 1.5, 2, 2.5). We then compare RMSEs when no covariate shift is present (a' = 0) against RMSEs at different noise levels. The results are shown in Figure 2b] We see that when no regularisation is applied, RMMES increase rapidly as o' increases, indicating our standard unprotected kernel ridge regressor is sensitive to noises from Xg. As the Shapley regularisation parameter increases, the RMSE of the noiseless case gradually increases too, but RMSEs of the noisy data are much closer to the noiseless case, exhibiting robustness to the covariate shift.

---

ISV-Reg
ISV-Reg
Experiment 4: Fair learning with OSV-REG At last, we demonstrate the use of Shapley regulariser enable fair learning. In this context, we will see, OSV-REC is the appropriate reg- ulariser. Consider X5 as some sensitive feature which we would like to minimise its contribution during the learning of f. Recall X4 highly correlated to X5 so it contains sensitive informa- tion from X5 as well. Figure demonstrates how distributions of ISVs and OSVs of X4 and X5 changes as A increases. As regularisation increases, the SVs of Xs becomes more centered at O, indicating lesser contribution to the model freg- Similar behavior be seen from the distribution of o oxx,1 (freg) but not
0.0
-20
20
20
0
(freg) x.
x (freg)
(1)
OSV-Reg
OSV-Reg
Denaty
0.2
from ( This illustrates how V-R- will propagate unfair- through correlated feature X4 while VSV-REG can take them into account by minimising the contribution of sensitive information during learning.
0.0
-20
0
20
-20
20
(freg)
4x. (freg)
Conclusion, limitations, and future directions
Figure 3:
Distributions of SVs sen- sitive fcature Xs and correlated fea- ture Xa obtained from V-RG and V- different regularisation parameters. Colour intensity repre- sents the strength of regularisation.
In this work, we proposed more accurate and more efficient algorithm compute Shapley values for kernel methods, termed EKHS-SHAL We proved that the corresponding local attribu- tions are robust to local perturbations under mild assumptions, desirable property for consistent model interpretation. Furthermore, we proposed the Shapley regulariser which allows learning while controlling specific feature contribution to the model. We suggested two applications of this regulariser and concluded our work with synthetic experiments demonstrating specific aspects our contributions. Extensive real-world data explanations are provided in Appendix E.2 for empirical demonstration.
While our methods currently only are applicable functions arising from kernel methods, fruitful direction would be to extend the applicability to more general models using the same paradigm. would also be interesting to extend our formulation kernel-based hypothesis testing, and for example, to interpret results from two-sample tests.
Acknowledgements
The authors would like to thank Shahine Bouabid for helpful comments. SLC is supported by the EPSRC and MRC through the OxWaSP CDT programme EP/L016770/1. DS is supported in part by Tencent AI Lab and in part by the Alan Turing Institute (EP//510012/1)..
10

---

References
[1] Kjersti Aas, Martin Jullum, and Anders Løland. Explaining individual predictions when features are dependent: More accurate approximations to shapley values. arXiv preprint a90iv: 10464, 2019.
[2] David Alvarez-Melis and Tommi S Jaakkola. On the robustness of interpretability methods. arXiv preprini arXiv: /806.08099 2018.
[3] Anonymous Author(s). https:/ //t///ounnnmmuuuuu.o sopen..cciaice//t/RiiSSSSt 2022.
[4] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(11), 2006.
[5] Diogo Carvalho, Eduardo M Pereira, and Jaime S Cardoso. Machine learning interpretability; A survey methods and metrics. Electronics, 8(8):832, 2019.
[6] Hugh Chen, Joseph D Janizek, Scott Lundberg, and Su-In Lee. True the model true the data? arXiv preprint crXiv:2006.1625: 2020.
[7] Sam Corbett-Daviee and Sharad Goel. The measure and mismeasure of fairness: A critical review of fair machine learning. arXiv preprint arXiv:/800 (00.000000000 2018.
[8] Ian Covert and Su-In Lee. Improving kernelshap: Practical shapley value estimation using linear regression. International Conference on Artificial Intelligence and Statistics, pages 3457-3465. PMLR, 2021.
[9] Ian Covert, Scott Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. Advances in Neural Information Processing Systems, 33, 2020.
[10] Sébastien Da Veiga. Kernel-based anova decomposition and shapley effects appliccain to global sensitivity analysis. arXiv preprint arXiv:2101.05487, 2021.
[11] Diabetes dataset from Kaggle.com. https: : htww//www.../ http://wwww.gg...../e com//datassta/mmtthhii
diabetes data aattaa-serrreeuurreoooooo..ooee
2022.
[12] Seth Flaxman, Dino Sejdinovic, John Cunningham, and Sarah Filippi. Bayesian learning of kernel embeddings. arXiv preprint 1rXiv:1603.0216 2016.
[13] Christopher Frye, Damien de Mijolla, Laurence Cowton, Megan Stanley, and Ilya Feige. Shapley-based explainability on the data manifold. arXiv preprint arXiv:2006.01272, 2020.
[14] Sahra Ghalebikesabi, Lucile Ter-Minassian, Karla DiazOrdaz, and Chris C Holmes. On locality of local explanation models. Advances in Neural Information Processing Systems, 34, 2021.
[15] Amirata Ghorbani and James Zou. Data shapley: Equitable valuation data for machine learning. In International Conference Machine Learning, pages 1242-2251 PMLR, 2019.
[16] Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, and Mas- similano Pontil. Conditional mean embeddings as regressors-supplemenne 1205v:2255.4650 2012.
arXiv preprint
[17] Leif Hancox-Li. Robustness in machine learning explanations: does it matter? In Proceedings of the 2020 conference on fairnes, accountability, and transparency, pages 640-647, 2020.
[18] Tom Heskes, Evi Sijben, Ioan Gabriel Bucur, and Tom Claassen. Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models. Advances in neural information processing systems, 33:4778 4789, 2020.
[19] Aditya Jain, Manish Ravula, and Joydeep Ghosh. Biased models have biased explanations. arXiv preprint 2012, 2020.
[20] Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature relevance quantification in explainable ai: A causal problem. In International Conference on Artificial Intelligence and Statistics, pages 2907-2916, PMLR, 2020.

---

[21] Z. Li, J.-F. Ton, D. Oglic, and D. Sejdinovic. Towards A Unified Analysis of Random Fourier Features. In International Conference on Machine Learning (ICML), pages PMLR 97:3905- 3914, 2019.
[22] Zhu Li, Adrian Perez-Suay, Gustau Camps- Valls, and Dino Sejdinovic. Kernel dependence regularizers and gaussian processes with applications to algorithmic faimess. arXiv preprint arXiv:1911.04322. 2019.
[23] Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. In Advances in neural information processing systems, pages 4765-4774, 2017.
[24] Scott M Lundberg, Gabriel G Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv: /002.0/880..3330 802.03888, 2018.
[25] Masayoshi Mase, Art Owen, and Benjamin B Seiler. Cohort shapley value for algorithmic fairness. arXiv preprint arXiv:2105.07166: 2021.
[26] Charles A Micchelli and Massimiliano Pontil. On learning vector-valued functions. Neural computation, 17(1):177-204, 2005.
[27] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf. Kernll mean embedding of distributions: review and beyond. arXiv preprint 2016.
[28] League of Legends Interpretability Demonstration, httpo///ttttt/////mmeemeerrrggie 1o/ /o/shap/
h00066748822220000000222//200110 html 2022.
[29] Junhyung Park and Krikamol Muandet. A measure-theoretic approach to kernel conditional mean embeddings. arXiv preprint arXiv:2002.03689, 2020.
[30] Vern I Paulsen and Mrinal Raghupathi. An introduction to the theory of reproducing kernel Hilbert spaces, volume 152. Cambridge university press, 2016.
[31] Adrián Pérez-Suay, Valero Laparra, Gonzalo Mateo-Gareía, Jordi Muñoz-Marí, Luis Gómez- Chova, and Gustau Camps- Valls. Fair kernel learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 339-355. Springer, 2017.
[32] Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3, page 5. Citeseer, 2007.
[33] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should I trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1135-1144 114,, 2016.
[34] Dino Sejdinovic, Heiko Strathmann, Maria Lomeli Garcia, Christophe Andrieu, and Arthur Gretton. Kernel adaptive metropolis-hastie hastings. In International conference on machine learning. pages
PMLR, 2014.
[35] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28): 307-317, 1953.
[36] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference Machine Learning, pages 3145-3153. PMLR, 2017.
[37] Eunhye Song, Barry L Nelson, and Jeremy Staum. Shapley effects for global sensitivity analysis: Theory and computation. SIAM/ASA Journal on Uncertainty Quantification. 4(1):1060-1083, 2016.
[38] Le Song, Kenji Fukumizu, and Arthur Gretton. Kernel embeddings of conditional distributions: unified kernel framework for nonparametric inference graphical models. IEEE Signal Processing Magazine, 30
12

---

[39] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
[40] Erik Strumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41(3):647-665, 2014.
[41] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International Conference on Machine Learning, pages 9269-9278. PMLR, 2020.
[42] Zoltán Szabó and Bharath K Sriperumbudur. Characteristic and universal tensor product kernels. The Journal of Machine Learning Research, 18(1):8724-8752, 2017.
[43] Vladimir N. Vapnik. The nature of statistical learning theory. Springer- Verlag New York, Inc., 1995.
[44] Christopher K Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
[45] Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. Nyström method random fourier features: A theoretical and empirical comparison. Advances in neural information processing systems, 25:476 15:476-484, 2012.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes] See [3]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes] See experiment section.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Experiments.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "Pja6xWdaSkc", "reviewer": "Reviewer_xJQh", "summary": "This paper proposed a novel method for calculating Shapley value for kernel-based models. The conditional expectation-based kernel method suffers from the error caused by the sampling-based conditional expectation estimation, while this paper utilize the property of kernel method provided non-parametric estimater of the value function of Shapley value directly. They theorectically showed the robustness of RKHS-SHAP. They also propose Shapley regulariser which could control specific features' contributions to the model. Extensive experiments verified their methods.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strength]\n1. This paper rigorously proved the non-parametric estimater of the value function for kernel-based method.\n2. Extensive experiments verified the effectiveness and robustness of the proposed methods.\n\n[Weakness]\n1. The method provided in this paper is only applicable to the kernel-based method.\n2. The paper only considered the conditional/marginal expectation-based Shapley value, while lacked of discussion for baseline value-based Shapley value (BShap) [cite 1]. \n\n[cite 1] Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In International Conference on Machine Learning, pages 9269–9278. PMLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "EFtuInxqJe", "reviewer": "Reviewer_YvsH", "summary": "- The authors proposed a feature attribution method for explaining kernel methods. \n- Some analysis has been provided to demonstrate the robustness of the proposed methods. \n- Experiments are carried out to show the effectiveness of the method.", "questions": "- Since kernel methods are differentiable, one can use gradient based methods for understanding kernel methods. How is that compared to Shapley based methods? ", "limitations": "- Computational complexity. \n- Only applicable to kernel methods. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The robustness of the method under local perturbation has been rigorously verified, which is quite important in such explanation methods. \nWeaknesses:\n- The proposed method falls short of computational complexity. It seems not practical. \n- The established theorem is relatively straightforward. It is obvious from the definition. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "BQkeSBmKUYh", "reviewer": "Reviewer_iFp9", "summary": "This paper considers the calculation of Shapley value explanations in the context of kernel models. The idea is to leverage the structure of such models to generate better Shapley value estimates (e.g., more accurate or faster), similar to what TreeSHAP enables for tree ensembles.\n\nThe main technical insight has to do with how held-out features are handled. Rather than estimating $\\mathbb{E}[f(X_{s^c}, x_s) | X_s = x_s]$ by sampling values from $p(X_{s^c} \\mid X_S = x_S)$, or estimating $\\mathbb{E}[f(X_{s^c}, x_s)]$ by sampling from $p(X_{s^c})$, the authors suggest using the underlying kernels to calculate the conditional mean embedding (CME) or kernel mean embedding (KME) for the held-out features (possibly conditioned on the observed ones). This may lead to more reliable and/or faster estimate of the value function (aka coalitional game), and the authors then suggest using KernelSHAP's weighted least squares algorithm for the final Shapley value approximation.", "questions": "If I understand correctly, the authors may have understated the computational cost of their approach, as well as the difficulty of achieving reliable CME estimates with realistic datasets. To elaborate:\n\n1. Whether you're estimating interventional or observational Shapley values, each coalition/subset will require a separate evaluation of the value function (coalitional game). And for each evaluation, you'll need to estimate $\\mu_{X_{s^c} \\mid X_s = x_s}$ or $\\mu_{X_{s^c}}$, which seems like a potentially expensive operation. (Well, the KME can be calculated once per feature, but not the CME.) Thus, RKHS-SHAP does not seem like it offers any run-time benefits, in fact it may make the estimation even slower. Am I missing something? \n2. $\\mu_{X_{s^c} \\mid X_s = x_s}$ is not a simple thing to estimate, it would seem to require that you filter for examples in your dataset where $X_s = x_s$. In a high-dimensional dataset, or a dataset with continuous features, wouldn't the number of matching rows be very small, particularly for $s$ with large cardinality? Furthermore, if you somehow are able to find matching rows that help you estimate $\\mu_{X_{s^c} \\mid X_s = x_s}$, couldn't you use the same rows to directly estimate $\\mathbb{E}[f(X_{s^c}, x_s) | X_s = x_s]$ even for non-kernel models? It seems like this trick only works in settings where, by assumption, you could reliably estimate the conditional expectation of the model output. (By the way, this approach for estimating the conditional expectation is discussed in Sundararajan et al., 2020.) Is this right, or am I missing something? \n\nAbout the robustness results:\n- Similar to my point under \"weaknesses,\" can you elaborate on whether you believe this result is somehow specific to RKHS-SHAP, or just a property of Shapley values applied to kernel models?\n- Could you comment on whether the constants in the robustness bounds are actually small? If not, these results may be meaningless. E.g., we could establish robustness bounds for Shapley values with arbitrary models whose predictions lie within a bounded range - are these results more useful than that?\n", "limitations": "There are no negative societal impacts to this work.\n\nAs for methodological limitations, I believe those are primarily in the speed and reliability of the CME estimation (as discussed above). If my concerns are accurate, then I don't think these points are currently adequately discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I should mention that I'm not an expert in kernel methods, so apologies in advance if I misunderstood any key parts of the method.\n\n### Strengths:\n\n- This paper is the first to my knowledge that develops a Shapley value approach specifically for kernel methods. The insights appear new and possibly useful in practice. The results are non-trivial and seem to require a strong understanding of kernel methods, which is not currently well represented in the explainable AI literature. (On the other hand, the key techniques may be inaccessible to many readers, but this is perhaps inevitable.)\n- The method enables regularization of explanations during training, which is generally difficult to achieve with Shapley values due to the cost of their calculation.\n- The background section is overall very nicely written.\n\n### Weaknesses:\n\n- I may be wrong on this, but I think the authors could say more about how expensive it is to estimate $\\mu_{X_{s^c} \\mid X_s = x_s}$ repeatedly throughout the KernelSHAP WLS approximation for different coalitions $s$. I've elaborated on this in the \"questions\" section below.\n- Again I may be wrong on this, but I think the paper understates the difficulty of estimating $\\mu_{X_{s^c} \\mid X_s = x_s}$. I've elaborated on this in the \"questions\" section below.\n- The robustness results do not seem to be a property of RKHS-SHAP, but of Shapley values themselves when applied to kernel models for which the authors' assumptions hold. It's an interesting result and non-trivial to show, but it perhaps shouldn't be claimed to be related to RKHS-SHAP.\n- In discussing the conditional expectation estimate in Section 3, the authors write that they \"utilise the arsenal of kernel methods to estimate the conditional expectations directly.\" I believe this is very similar (except for the focus on kernels) to the second method introduced by Frye et al. 2020 that has a very similar motivation - the supervised surrogate model. That method is easier to train than the conditional generative model, does not require Monte Carlo sampling, and has no risk of off-manifold examples because it bypasses the generative modeling task. Perhaps this deserves some discussion? \n- I thought the paper's exposition could greatly benefit from disentangling the two main elements of estimating Shapley values (and where RHKS-SHAP is helpful): 1) handling predictions with held-out features, and 2) accurately approximating Shapley values. Section 2 made it sound like this work would present a significant improvement over KernelSHAP (see lines 114-130), which led me to believe the improvement had to do with 2). Ultimately, it had to do with 1), which I don't understand as really being part of KernelSHAP. The main idea behind KernelSHAP is approximating Shapley values via weighted least squares, and the authors actually re-use this part. What's modified here is the sampling trick for handling held-out features, which isn't unique to KernelSHAP and also used by other Shapley value methods (e.g., IME). \n\nA couple small things:\n- On line 125, the formula for the closed-form solution to the WLS problem solved by KernelSHAP seems a bit informal due to the presence of $\\infty$ entries in $W$\n- It may be helpful to say explicitly that the interventional and observational coalitional games can be estimated via the KME/CME specifically because of the model's linear dependence on the features $\\psi_x$. Of course, what we really want is the expectation of the model's output, and it's a unique property of such methods that we can get that via the expectation of the $\\psi_x$ component.\n\nThere are a couple related works that seem like they should/could have been discussed here:\n- The various ways of estimating $\\mathbb{E}[f(X) \\mid X_s = x_s]$ are discussed in a recent review paper [1], including parametric assumptions, generative modeling, and several more. The conditional generative model is not, I think, widely understood as a viable approach\n- The idea of \"attribution priors\" [2] has been discussed as a way to regularize models' dependencies during training, although it's mainly used with gradient-based methods rather than Shapley values. Regularizing explanations is a natural idea, but Shapley values are somewhat unique in making this intractable\n- ShapNets [3] also provide a fast Shapley value calculation, albeit for a specific modified DNN architecture, and one of the motivations was to enable explanation regularization. RKHS-SHAP provides something similar, but for kernel models\n\n[1] Covert et al., \"Explaining by removing: a unified approach to model explanation\" (2021)\n\n[2] Erion et al., \"Improving permeance of deep learning models with axiomatic attribution priors and expected gradients\" (2021)\n\n[3] Wang et al., \"Shapley explanation networks\" (2021)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept