Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Dear Reviewer m993,

Thank you for your time and feedback!

We would like to add some context to the importance of approximating Shapley values. In the explainable AI literature, Shapley values are the de facto method for providing explanations for machine learning predictions on tabular data. In particular, the original SHAP paper by Lundberg and Lee titled “A Unified Approach to Interpreting Model Predictions” has more than 25,000 citations. Further, the corresponding SHAP library (of which Kernel SHAP is probably the most widely utilized algorithm) has been used by more than 20,000 repositories, as reported by GitHub. As such, we believe Leverage SHAP has the potential for significant impact because of its superior empirical performance and its strong, non-asymptotic theoretical guarantees.

We note that gamma is often quite small in experiments. Since computing $\gamma$ requires writing down the entire (exponentially) large regression problem, we can only compute $\gamma$ for datasets with small $n$. For each of these datasets, we train a model 100 times (from different random initializations) which induces a different vector $b$. Then we compute $\gamma = \| \| A \phi - b\|\|_2^2 / \|\| A \phi \|\|_2^2$. For all datasets, we found that the 75th percentile of $\gamma$ was less than 2. Please see below for the full summary statistics.

Dear Reviewer 7UDD,

Thank you for your time and feedback! We address your concerns here and your questions in a comment below.

Corollary 4.1 [...] has a non-intuitive $\gamma$ term which is can be large and makes the approximation guarantees weaker.

We agree that the dependence on $\gamma$ is not ideal, although dependence on this quantity seems inherent to all regression-based algorithms, including Kernel SHAP. This is illustrated in Figures 5 and 6. As discussed in our response to Reviewer LX1d, it would be interesting to consider lower bounds for Shapley value estimation in future work: it may be that the dependence on $\gamma$ is unavoidable for any method that, like our method, only uses a near-linear number of value function evaluations.

Are there conditions under which $\gamma$ is guaranteed to be small?

This is an interesting question. $\gamma$ is known to equal $0$ for linear value functions, which covers e.g., the case when Shapley values are used for feature attribution in linear machine learning models (when the baseline is the all 0 vector). We are not sure if there are other more general conditions under which $\gamma$ can be bounded, but it is a nice question for future work.

We do note that gamma is often quite small in experiments. Since computing $\gamma$ requires writing down the entire (exponentially) large regression problem, we can only compute $\gamma$ for datasets with small $n$. For each of these datasets, we train a model 100 times (from different random initializations) which induces a different vector $b$. Then we compute $\gamma = \| \| A \phi - b\|\|_2^2 / \|\| A \phi \|\|_2^2$. For all datasets, we found that the 75th percentile of $\gamma$ was less than 2. Please see a comment below for all the summary statistics.

The experiments could include more baselines like…

Thank you for these suggestions. We address each paper below.

(Jethani et al., 2021)

The Fast SHAP algorithm (Jethani et al., 2021) is complementary to our setting because the algorithm is trained (using many many value function evaluations) to predict Shapley values for multiple explicands and baselines. In contrast, the algorithms we consider, like Kernel SHAP and our Leverage SHAP method, estimate the Shapley values for a single value function $v$ corresponding to a single explicand and baseline pair without any pretraining. Which algorithm to use depends a lot on the setting and if the expensive training cost of Fast SHAP can be amortized against enough Shapley value computations. We will add further discussion of this point to the next version of the paper.

(Mitchell et al., 2022b)

We have added a comparison to the permutation algorithm (Strumbelj & Kononenko, 2010 and Mitchell et al., 2022), which we present in a comment below. We find that Permutation SHAP sometimes outperforms Optimized Kernel SHAP but only very rarely does it outperform Leverage SHAP.

(Yang & Salman, 2019)

The only paper we could find with these two authors + year is the paper “A Fine-Grained Spectral Perspective on Neural Networks”, which we do not believe is relevant to Shapley value estimation. Perhaps you meant a different reference? Please let us know.

The technical novelty in proving the new theoretical results also appears to be limited...

We do not consider the proof of our Theorem 1.1 to be a main technical contribution of the paper. It is well known that leverage score sampling provides a sample complexity bound of $O(n \log n + n/\epsilon)$ for general active linear regression problems, of which the Shapley value estimation problem can be viewed as a special case. Such results date back to work by Sarlos (FOCS, 2006) and others: a good reference is the book Sketching as a Tool for Numerical Linear Algebra (Woodruff, 2014). While our result requires some extra work (to handle paired sampling and sampling without replacement), the proof is a straightforward generalization of this prior work. Theorem 1.1 from Shimizu et al. could likely be used as well since our paired-sampling distribution satisfies the $\ell_\infty$- independence condition in that paper. However, that result naively only applies to $k$-homogenous sampling distributions, which our distribution is not (since we do not sample a fixed number of rows from $A$). Modifying our approach to match the Shimizu result is likely possible, although ultimately it was simpler to just prove the guarantee we needed directly.

Instead, we consider the technical contribution of the paper to be the realization that 1) leverage score sampling can be directly applied to the Shapley value estimation problem and 2) this can be done in a computationally efficient way given the structure of the matrix $A$. The second point is important, as applying prior work on leverage scores directly would suggest the need to compute these scores, of which there are $2^n$ for the Shapley value estimation problem.

Typos

Fixed, thank you!

I thank the authors for clarifying my questions and appreciate the updates and responses to my review. I have updated my score based on the rebuttal.

Dear Reviewer LX1d,

Thank you for your time and feedback! We address your questions below.

It would be nice to have a fuller picture of the Shapley value problem from a broader approximation algorithms standpoint …

Computationally, the dominant cost in estimating Shapley values for applications like feature explanation is almost always computing the value function, $v(S)$. As such, our work and much of the prior work, focuses on reducing the number of sets for which the function might need to be evaluated to estimate $\phi_i$ for all $i$. The most relevant papers that propose methods for doing so are discussed in Section 1.1. For example, Strumbelj & Kononenko 2010 and Mitchell et al. 2024 reuse samples by selecting a random permutation $S_1 \subseteq S_2 \subseteq … \subseteq S_n$ and using $v(S_i)$ to evaluate both $v(S_{i+1}) - v(S_i)$ and $v(S_{i}) - v(S_{i-1})$ when computing a standard Monte Carlo estimate of the summation form of the Shapley values (our Equation 1). In general, the regression approach taken by KernelSHAP tends to be more efficient than alternative approaches like this, which is why we focus on improving that method.

Are there any computational inapproximability results?

This is an interesting question. As mentioned, since evaluating the value function, $v$, generally dominates the complexity of computing Shapley values, we believe a query complexity model would be a natural way to address this question – i.e., how many queries to to $v$ are required to estimate the Shapley values to some given level of accuracy? In this model, $\Omega(n)$ is a natural lower bound on the number of function evaluations needed to exactly compute the Shapley values, and we conjecture that this lower bound could be improved to $\Omega(n/\epsilon)$ to obtain a $(1+\epsilon)$-approximation in the sense provided in our paper.

Here’s an informal argument for the $\Omega(n)$ lower bound: Consider the special linear setting where the set function is given by $v(S) = \sum_{i \in S} \alpha_i$ for some set of weights $\alpha_1, \ldots, \alpha_n$. In this setting, it can be seen that the Shapley values are exactly equal to $\alpha_1, \ldots, \alpha_n$. So, we must learn these weights exactly to learn the Shapley values. If we query $v(S)$ for $< n$ choices of $S$, we obtain a linear system with more unknowns than equations, so cannot determine the values of $\alpha_1, \ldots, \alpha_n$.

As for obtaining a stronger lower bound, a natural starting point would be the $\Omega(n/\epsilon)$ lower bound proven for general active linear regression problems in the COLT 2019 paper “Active Regression via Linear-Sample Sparsification” by Chen and Price. This at least rules out a better algorithm based on linear regression – we will have to think more if it can be extended to a general sample complexity lower bound for Shapley value estimation. It’s a great question for future work!

But I am curious if the authors have an idea of a "dream result" under less restrictive but still reasonable structural assumptions…

Our $O(n \log n + n /\epsilon)$ guarantee is already quite close to what we conjecture is optimal, so we think of this guarantee as almost a “dream result”. We think it would interesting to consider if other problem "structure" can lead to even better sample complexity, although for now we have focused on the general problem. Shapley values are used for a wide variety of machine learning models and Shapley value estimation algorithms like KernelSHAP are often treated as a "black-box", so as a first step, it's important to obtain results that work without additional assumptions.

One additional “dream” would be to remove the $\gamma$ factor in the $\ell_2$-approximation guarantee. We believe this factor is inherent for regression-based approximation algorithms (as experimentally confirmed in Figures 5 and 6). However, we could imagine there is a non-regression-based algorithm that does not have a dependence on the quality of the optimal regression solution, as measured by $\gamma$.

One thing that was not totally clear to me from the experiments is whether Leverage SHAP strictly dominates Kernel SHAP at every point in the running time vs accuracy graph…

All of the regression-based methods (including Optimized Kernel SHAP and Leverage SHAP) need at least $n$ samples so that the approximate regression problem has full rank, hence all our experiments are run with $m \geq n$. In these experiments across all eight datasets, we find that Leverage SHAP always dominates Optimized Kernel SHAP (except for cases when both methods manage to obtain the exact Shapley values up to machine precision, as in Column 1 of Table 1). You are correct that the guarantee on Leverage SHAP requires $m = \Omega(n \log n)$, but the method can still be run for smaller values of $n$, and we find experimentally that its performance remains superior for all $m \geq n$.

Due to space constraints, we continue in a comment.