Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values

all the considered Monte Carlo baselines could potentially benefit from the same learned function $f$.

We agree with this point, and actually view it as a strength rather than a weakness of our approach. We selected MSR as our “baseline” estimator because, in addition to being simple to implement, it is

1. unbiased (contrasting with Kernel SHAP and Leverage SHAP), and

2. computationally efficient in the sense that every function evaluation $v(S)$ is used to update every estimate (contrasting with Permutation SHAP and MC).

As far as we know, MSR uniquely satisfies these two properties among probabilistic value estimators.

the paper lacks experiments demonstrating that the proposed Monte Carlo method is the most effective when paired with the learned $f$.

Since the main contribution of our work is the regression adjustment technique (learning an $f$ for which we can compute probabilistic values exactly), considering a wide variety of alternative baseline estimators is outside the scope of the paper. That being said, we just ran some experiments with MC as the baseline; please see below.

On the other hand, while the proposed Monte Carlo method appears novel, it is unclear whether it achieves faster convergence rate either empirically or theoretically compared to the existing baselines.

For fixed sample budgets, Tree MSR achieves an average error that is $1.75\times$ lower than the prior best estimator, Leverage SHAP, across eight popular datasets (Table 1). As for convergence rate, we explore how accurately the estimators recover the true Shapley values (Figure 2) and probabilistic values (Figure 3) as a function of sample size. From these figures, we conclude that, for most datasets, Tree MSR does gives faster convergence empirically. We justify this finding theoretically in Theorem 2.1, where we show the performance of our estimator depends on how well the (randomly) learned $f$ fits $v$.

I suggest that the authors include more details on the implementation of treeMSR. After examining the provided code, I found that the features used are binary; the baseline is the zero vector, and the explicand is the one vector. This important information is missing in the paper.

We will add more details! One note: In the interventional setting where we apply Tree Prob, a point is fully specified by the binary indicator of which features come from the “explicand” and which come from the “baseline”. Since the tree-based model can learn in a scale-invariant and shift-invariant way with respect to these features, it actually suffices to only consider binary inputs. We make this clear in the updated version of the paper.

In the proof of theorem 2.1, the randomness involved in learning $f$ is not accounted. As a result, the stated result applies only to the specific Monte Carlo method defined in Eq. (3). The current statement of theorem 2.1 may therefore be misleading.

We can add a comment reminding the reader that f itself is a random function. Since independent samples are used to fit $f$ (line 3-4 in Algorithm 1) and to approximate Shapley values (line 6-7) the statement of Theorem 2.1 is true regardless of the outcome of f.

Typos

Thank you!

Why not combine $\mathcal{S}^\text{train}$ and $\mathcal{S}^\text{test}$ for both learning and approximating, given that they are drawn from the same distribution?

Good question! Our variance analysis in the proof of Theorem 2.1 relies on independence between the final estimate and the learned function $f$. We use $\mathcal{S}^\text{train}$ to learn the function $f$, and then $\mathcal{S}^\text{test}$ for the samples used to build the final estimate.

Could the authors provide results of substituting other Monte Carlo baselines in both linearMSR and treeMSR?

Yes! We compare several Shapley value estimators in the small sample regime $m=10n$ on the four small datasets below.

Dataset: Adult (n=12)

Dataset: Forest Fires (n=13)

Dataset: Real Estate (n=15)

Dataset: Bike Sharing (n=16)

While Tree MC is quite good, we generally find that Tree MSR gives error about an order of magnitude smaller. We believe this is due to the differences in the final regression-adjusted estimate: each sample is used for every estimate in MSR, whereas each sample is only used for one estimate in MC.

Thank you for your positive review!

Depending on how the performance is measured, improvement may not be drastic as compared to highly optimized alternatives.

While it doesn’t give SOTA in every setting, our Tree MSR achieves an average error $1.75 \times$ lower than the prior best Shapley value estimator, Leverage SHAP, on eight common datasets.

I found Fig. 1(b) confusing. The Correlated and Community data points do not appear to satisfy the unbiasedness property. Why do they seem so biased? In theory, the estimated values should be distributed both above and below the true value, so that the deviations cancel out on average. Why is this not observed in the figure?

Figure 1(b) shows the true Shapley values vs. estimates produced by the standard MSR estimator on one random run. The multiple points for each dataset (e.g. for Correlated and Community) correspond to different features in the dataset. While the estimated Shapley value for each individual feature is unbiased, there is substantial correlation between the estimates for different features, leading to this clustering. The correlation is due to the fact that every function evaluation $v(S)$ is used to estimate the Shapley value for every feature. Large values of $v(S)$ in particular can have substantial impact. To observe unbiasedness, we would need to re-run the same experiment with different random seeds. If we do so, we see that the estimates for Correlated and Communities do not consistently appear on one side of the diagonal line.

While the computational advantage of MSR is its “maximum reuse”, this property comes with a cost in variance and correlation. We view Regression MSR as a fix: The variance of Regression MSR depends on $[ f(S) \approx v(S) ]^2$ rather than $[v(S)]^2$ like standard MSR. So, even if some $v(S)$ is large, we can still get remarkably accurate estimators provided $f(S) \approx v(S)$.

Thank you for your detailed comments! We respond below:

It would be helpful if the authors could provide a more detailed derivation of Equation (5) in the appendix, including a formal proof of its unbiasedness and an analysis of its variance.

These derivations are provided in proof of Theorem 2.1 (Appendix A). We show that $\tilde{\phi}_i$ is unbiased in the equation under Line 370, and analyze its variance in Equation (7). In response to your comment, and that of Reviewer z7xn, we will make this analysis clear in the main body of the updated paper.

to what extent does the use of linear versus non-linear models influence the quality of the estimated probabilistic values? Could shallow neural networks serve as effective approximators in this context? A more detailed analysis of how the choice of impacts estimation error would strengthen the paper.

A crucial component of our proposed Regression MSR estimator is that the probabilistic values of the approximation $f$ need to be efficiently computable. (Otherwise, we would be stuck with the initial problem of estimating the probabilistic values of $f$.)

We are aware of two primary function classes with this property:

• The coefficients of linear functions are always their probabilistic values. (This can directly be seen directly in Equation (1) with the probabilistic constraint that $\sum_{\ell=0}^{n-1} {n-1 \choose ell} p_\ell = 1$.)

• We show in Appendix C how the probabilistic values of (multiple) decision trees can be computed efficiently. A special case of this was known for Shapley values, and basically follows from the “case”-like structure of trees.

The issue with neural networks is that computing their Shapley values is generally slow, requiring O(2^n) time even when the network is shallow or has few parameters.

it would be helpful to clarify whether the estimator has similar time complexity to the Maximum Sample Reuse method. A discussion or empirical comparison of the time complexity (or runtime) would improve the clarity of the contribution.

Great question! In our experience, the dominating cost is computing $m$ function evaluations of $v$. Here’s one way to see why: If $v$ is as expressive as a shallow neural network, this time complexity is already $O(m n^2)$ and likely much higher. (A single fully connected layer between $n$ nodes requires $O(n^2)$ operations, repeated for each of the $m$ different $n$-dimensional inputs.)

Beyond the time to get evaluations of $v$, the additional computational step of Regression MSR is fitting the function $f$:

• When $f$ is linear, solving a linear system with $m$ equations and $n$ rows takes $O(mn^2)$ time. In practice, this is very fast due to excellent linear algebra libraries. Note: Kernel SHAP and Leverage SHAP have this same time complexity because they are also solving a linear system of the same size.

• When $f$ is tree-based model, fitting the function requires roughly $O(T * m * n)$ time where $T$ is the number of trees. In practice, we use the default $T=100$ for XGBoost. Due to its extensive optimizations, fitting XGboost is remarkably fast in practice.

The authors could add a summary table in the appendix comparing the proposed method with existing baselines (e.g., in terms of unbiasedness, variance, computational cost, use of surrogate models, and other relevant properties), which would help readers better understand the advantages and limitations of each method.

Great idea! We agree a summary table would be useful for the community. Please see below for an initial Shapley value estimator summary. We will continue to update, adding more estimators and properties, for the final version of the paper. Let $T_m$ be the time to evaluate the value function $v$ on $m$ different subsets.

Thank you for your careful reading! We appreciate your clarifying questions, and pointers to specific related works. We respond in detail below:

Equation (3) seems central to the proposed algorithm [...] Can you clarify its origin and provide some explanation?

The Maximum Sample Reuse (MSR) estimator described in Equation (3) was originally proposed to estimate Banzhaf values [WJ23]. Since then, it has been generalized to other probabilistic values, albeit with differing notations [KBMH24, LY24a, LY24b]. The key insight is that we can write the probabilistic values as

Compared to the first equation, the final equation makes it clear how $v(S)$ appears (albeit with a potentially different sign and weighting) in every probabilistic value. This observation naturally suggests the MSR estimator in Equation (3), where each $S$ is sampled, and reweighted, so that the estimator is right in expectation. We will update the paper to make this motivation clear.

I believe the main contribution of the article can be more readily accessible if consistency ($E[\hat{\phi}{i}] = \phi{i}$) and variance results are mentioned explicitly in the main body of the article.

We think this is a good suggestion, and will plan on including the consistency and variance directly in Theorem 2.1.

is the division between Monte Carlo and regression-based methods strictly correct? For instance, doesn’t KernelSHAP also involve Monte Carlo sampling, not just regression?

Good question! In our work, we distinguish between“Monte Carlo” methods that directly estimate the linear sum of probabilistic values, and “regression-based” methods that fit an approximation $f$ to the underlying game $v$, then compute the probabilistic values of $f$. While methods like KernelSHAP use random sampling to fit a linear function $f$ to $v$, the method ultimately computes $f$ via least squares regression and returns the Shapley values of $f$. (Since $f$ is a linear function, its Shapley values are simply the coefficients for each feature.) We will clarify this distinction in the updated paper..

in line 35, the first sentence appears without context, and the topic shifts abruptly right after. This is also seen in sections 1.1

Thank you for pointing out these writing discontinuities. We have smoothed out the transitions (Line 35 and Section 1.1 more broadly) in the new version.

Even though FastSHAP is not based on Monte Carlo, it is relevant. Also, Mitchell et al. show that Owen's halves can be effective, yet this article only discusses Owen’s method in the context of KernelSHAP. I understand that the relevant literature is vast but it does draw attention that the method is not compared to such prevalent works

Due to their widespread applications in interpretability, there is certainly a vast literature on estimating Shapley values, and probabilistic values more broadly. We will plan on expanding our discussion of prior work in the updated paper. We briefly discuss two methods mentioned by the reviewer here:

Fast SHAP is a method for learning a function $f$ that simultaneously fits multiple related games $v$. While it has a high overhead in sample complexity to learn $f$, Fast SHAP can give improved results when we want to estimate Shapley values for multiple, similar games simultaneously. In our setting, we are interested in estimating the Shapley values of a single game $v$. Due to these incomparable settings, we do not compare to Fast SHAP in our work, but have now highlighted the estimator in the updated related work section in response to your comment.

Owen’s and Owen’s halves are two Shapley value estimators. They both exploit a connection between Shapley values and the expectation of a continuous process. The “halves” augmentation is a kind of paired sampling (sometimes called “antithetical” sampling) that boosts performance. We chose not to compare to Owen’s or Owen’s halves estimators because they were shown in “Sampling Permutations for Shapley Value Estimation” to consistently perform worse than Permutation SHAP (what they call “MC-antithetic”) see e.g., their Figure 9. In our work, we find that Tree MSR already achieves an average $6\times$ improvement over Permutation SHAP. Nevertheless, we will plan on adding discussion of this prior work.