Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: [Strength]
1. This paper rigorously proved the non-parametric estimater of the value function for kernel-based method.
2. Extensive experiments verified the effectiveness and robustness of the proposed methods.

[Weakness]
1. The method provided in this paper is only applicable to the kernel-based method.
2. The paper only considered the conditional/marginal expectation-based Shapley value, while lacked of discussion for baseline value-based Shapley value (BShap) [cite 1]. 

[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.
questions: N/A
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: - The authors proposed a feature attribution method for explaining kernel methods. 
- Some analysis has been provided to demonstrate the robustness of the proposed methods. 
- Experiments are carried out to show the effectiveness of the method.
strengths_and_weaknesses: Strengths:
- The robustness of the method under local perturbation has been rigorously verified, which is quite important in such explanation methods. 
Weaknesses:
- The proposed method falls short of computational complexity. It seems not practical. 
- The established theorem is relatively straightforward. It is obvious from the definition. 
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. 
- Only applicable to kernel methods.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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.
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.

### Strengths:

- 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.)
- The method enables regularization of explanations during training, which is generally difficult to achieve with Shapley values due to the cost of their calculation.
- The background section is overall very nicely written.

### Weaknesses:

- 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.
- 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.
- 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.
- 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? 
- 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). 

A couple small things:
- 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$
- 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.

There are a couple related works that seem like they should/could have been discussed here:
- 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
- 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
- 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

[1] Covert et al., "Explaining by removing: a unified approach to model explanation" (2021)

[2] Erion et al., "Improving permeance of deep learning models with axiomatic attribution priors and expected gradients" (2021)

[3] Wang et al., "Shapley explanation networks" (2021)
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:

1. 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? 
2. $\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? 

About the robustness results:
- 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?
- 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?

limitations: There are no negative societal impacts to this work.

As 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.
review_title: null

Meta-review: metareview: The authors propose a novel method for calculating Shapley value for kernel-based models. The paper includes both a theoretical analysis and extensive experimental evaluation. A majority of reviewers are in support of accepting the paper and the rebuttal/discussion period helped to clear out (most of) the reviewers' concerns.
confidence: Certain
Decision: Accept