Can regression-adjusted Monte Carlo estimators improve Shapley value approximation accuracy?

A flexible fit replaces the linear model

Probabilistic values, including Shapley values, Banzhaf values and semi-values, summarize how much a player or feature contributes by averaging its marginal contribution over random subsets of the other players. The weight placed on each subset size is set by a vector p; Shapley values use one particular weighting, Banzhaf values another. Exact computation can take exponential time, so practical work estimates these values from a limited number of evaluations of the value function v.

Prior work followed two routes. Monte Carlo methods sample subsets and average reweighted marginal contributions. Regression methods fit a linear model to the sampled values of v and then return the probabilistic values of that fitted model. The paper's move is to keep the regression formulation but allow the fitted function to come from any family whose probabilistic values can be computed efficiently. A tree ensemble such as XGBoost is the motivating case, because tree structures admit exact probabilistic value computation.

This matters because a linear fit can only capture the part of v that is linear in the subset indicators. If the underlying value function has interactions or other nonlinear structure, the fitted model is misspecified and the resulting estimates inherit that error. Swapping in a more expressive function family targets exactly that source of error, while the sampling step still controls how many expensive evaluations of v are needed.

Cross-fitting buys unbiasedness at a runtime cost

Fitting a model on the same samples used to form the final estimate introduces a bias, because the model has already seen the data it is being scored on. The paper addresses this with cross-fitting: with k folds, it trains k functions, each on a (k−1)/k fraction of the samples, and corrects each function on the held-out 1/k. With k≥2 the resulting estimates are unbiased.

The cost is explicit. With k=1 the method trains a single function on all m samples, which is the cheapest version. The experiments use k=10 for both Linear MSR and Tree MSR, so each function is trained on 90% of the samples. The all-samples version runs 1.1–5.8× faster with the linear function class and 2.6–9.9× faster with the tree function class.

Accuracy does not uniformly favor cross-fitting. The cross-fit estimator is more accurate in 53 of 112 dataset–weighting pairs for the linear class, so the two versions are nearly interchangeable there; with Shapley weights, cross-fitting is the only difference between Linear MSR and Leverage SHAP. For the tree class, cross-fitting wins in 90 of 112 pairs, where the all-samples version's error is typically 1.8× larger. The authors' recommendation follows from this split: use the all-samples version when runtime dominates, and cross-fitting otherwise.

Error reductions depend on which value is estimated

The headline numbers come from experiments across eight datasets. For Shapley values, the paper reports error up to 11× lower than Permutation SHAP, described as the most popular Monte Carlo method; 6.5× lower than Kernel SHAP, the most popular linear regression method; and 3.4× lower than Leverage SHAP, the prior state-of-the-art Shapley value estimator. These are comparisons of estimation error against the same target values, not of downstream model accuracy.

The gap widens for general probabilistic values. For values beyond Shapley, the paper reports error 390× lower than the best estimator from prior work. This larger factor should be read in its own setting: general probabilistic values lack the efficiency property that lets Shapley values pin down an additive constant exactly, so prior regression estimators must estimate that constant from the whole value function, adding a separate error source. The paper's framing is that its approach handles this generality directly.

A separate experiment on small datasets with neural network models, where true probabilistic values can feasibly be computed, reports that Tree MSR produces mean error 243× lower than the best prior estimator, averaged over all probabilistic values. That figure comes from a different ground-truth setup and a different dataset subset than the eight-dataset comparison, so it should not be merged with the 11× and 390× numbers.

Tree MSR leads most clearly when samples are plentiful

The paper reports that Tree MSR gives the best performance, often by several orders of magnitude when m is large, where m is the number of value function evaluations. The advantage is therefore not a fixed multiplier that holds everywhere; it grows with the sampling budget, which is consistent with the mechanism, since a more expressive fitted function has more to gain from additional samples.

Noise experiments point the same way. When error is plotted against noise magnitude, Tree MSR gives the best performance, often by several orders of magnitude especially when the noise magnitude is small. These plots average error over small datasets (n<30) for the neural network ground truth and over large datasets (n≥30) for the regression forest ground truth, with mean error over 10 runs.

The practical reading is that the method's edge is largest in the regime where a practitioner can afford many evaluations of v and the value function is not close to linear. Where the budget is tight, the sampling noise in the regression step and the cost of training k tree models both weigh against it.

The evidence spans eight tabular datasets

The eight datasets range from 12 to 101 features: Adult (12), Forest Fires (13), Real Estate (15), Bike Sharing (16), Breast Cancer (30), Independent (60), NHANES (79) and Communities (101). They come from shap.datasets, the UCI ML Repository, OpenML and sklearn.datasets, under licenses including CC-BY 4.0, MIT and public domain.

This scope matters for transfer. All eight are tabular feature-attribution settings with modest feature counts, and the value function is the model prediction using a subset of features. The paper also discusses data attribution and data valuation as applications of probabilistic values, where v is the model loss when training on a subset of data, but the reported experiments are the tabular feature-attribution ones. Readers should not assume the measured error reductions carry over unchanged to settings where evaluating v requires retraining a model.

The choice hinges on runtime versus accuracy

The paper's own decision rule is narrow and concrete. If runtime dominates, use the all-samples version with k=1, which is 1.1–5.8× faster for the linear class and 2.6–9.9× faster for the tree class. If accuracy matters more, use cross-fitting, which is unbiased and more accurate in 90 of 112 dataset–weighting pairs for the tree class.

The second choice is the function family. Linear MSR and Leverage SHAP coincide under Shapley weights apart from cross-fitting, so the linear variant is essentially a reframing of an existing estimator rather than a new accuracy ceiling. The accuracy gains the paper reports come from the tree-based variant, and they are largest when m is large and noise is small.

The most useful takeaway is therefore conditional rather than universal: the regression-adjustment idea pays off when the fitted function family can represent structure that a linear fit misses, and when the evaluation budget is large enough for that extra capacity to be learned. Under those conditions the reported Shapley error can be 3.4× lower than the prior state of the art; outside them, the cheaper all-samples linear version remains a reasonable default.

Sources used in this answer