An Odd Estimator for Shapley Values

AI summary

Overview

Research area: Explainable AI and machine learning — specifically the estimation of Shapley values for model-agnostic attribution.

Technical level: Advanced. The paper works with game-theoretic set functions, weighted least squares regression, Fourier (Walsh) bases, and computational complexity analysis, though the central insight is stated simply.

Scope: The paper proves that Shapley values depend only on the odd component of a value function, uses that fact to explain why paired sampling works, and introduces a consistent estimator called OddSHAP that regresses only on odd-order Fourier terms.

What This Paper Is About

Computing exact Shapley values requires summing over exponentially many coalitions, so practical systems approximate them by fitting a structured surrogate function and returning that surrogate's exact Shapley values. Existing surrogate methods either require too many samples for acceptable accuracy or become computationally prohibitive when they try to capture higher-order interactions, as PolySHAP does. The authors show that half of the function — the even component — is irrelevant to the Shapley value, that paired sampling implicitly discards it, and that restricting regression to the odd subspace yields a more accurate and more efficient estimator.

Key Contributions

1. A general theoretical justification for paired sampling. Using the fact that Shapley values depend exclusively on the odd component of the value function, the authors prove (Theorem 3.2) that under paired sampling the weighted least squares projection decouples into independent odd and even objectives. They also prove Corollary 3.3, that under the unanimity basis and paired sampling an order-k fit with odd k yields the same Shapley values as an order-(k+1) fit, which confirms a conjecture of Fumagalli et al. (2026) and generalizes the k=1 case.

2. The OddSHAP estimator. A consistent estimator that performs polynomial regression only on a sparse selection of odd-order Fourier basis functions, using a gradient boosted tree proxy (via ProxySPEX) to identify high-impact interactions.

3. Fourier reformulation of the regression. The unanimity basis used by KernelSHAP, LeverageSHAP, and PolySHAP does not split cleanly into odd and even parts; in the Fourier basis a basis function is odd exactly when its interaction order is odd, which makes the odd subspace directly selectable.

4. Empirical state-of-the-art accuracy at larger budgets. On eight value functions with budgets of roughly 100d samples, OddSHAP attains the best average rank (1.50) among ten compared estimators, ahead of RegressionMSR (2.62).

Main Findings

• Shapley values ignore the even component. Every set function decomposes uniquely as f = f_odd + f_even, with f_odd(S) = (f(S) − f(Sᶜ))/2 and f_even(S) = (f(S) + f(Sᶜ))/2, and φ_i(f) = φ_i(f_odd) for all players i.

• Paired sampling is an even-odd decomposition. Pairing each sampled coalition S with its complement Sᶜ, combined with the symmetric weights the estimators already use, orthogonalizes the regression objective so the odd and even components are fit separately. This explains an empirically effective but previously unexplained heuristic.

• Odd-order fits reach the same frontier as one order higher. For odd k, the Shapley values of the order-k unanimity fit equal those of the order-(k+1) fit under paired sampling, because going from odd k to k+1 adds terms that only affect the even component. This extends Mayer and Wüthrich (2025), who covered interactions of at most degree 2.

• Fourier regression is consistent. Solving the weighted, boundary-constrained regression in the Fourier basis over any set of coalitions containing all singletons recovers the true Shapley values (Theorem 3.5), and the unanimity and Fourier restricted classes coincide on terms of order at most k (Lemma 3.4).

• OddSHAP has the best average rank. In Table 1, with budgets of approximately 100d samples, average ranks are: OddSHAP 1.50, RegressionMSR 2.62, LeverageSHAP 3.25, PolySHAP-3 3.25, Proxy 5.00, PermutationSampling 5.62, FFD-RD 5.75, SVARM 6.75, MSR 7.75, FFD-RD-Corrected 8.50, and FourierSHAP 9.12. RegressionMSR reports a lower MSE than OddSHAP on the DistilBERT and ViT16 value functions.

• Polynomial complexity instead of combinatorial cost. PolySHAP's regression costs O(|T|²m), which becomes O(d^{2k}m) for all terms up to order k. OddSHAP instead sets the candidate support size to |T_odd| = ⌈m/η⌉ − d, so the number of regression variables scales with the sampling budget rather than with d^k, with the regression itself costing O(|T|² m/2).

• Halving the regression rows. Because paired sampling lets the odd targets f_odd(S) be precomputed for one representative of each pair, complementary samples can be dropped and the regression solved on m/2 rows.

• Reliability in high dimensions. On the largest benchmark, Crime (d = 101) with m = 11126, OddSHAP reports MSE 1.3 × 10⁻¹, compared with 5.6 × 10⁻¹ for RegressionMSR, 7.5 × 10⁻¹ for LeverageSHAP, 5.3 × 10⁰ for Proxy, and 1.9 × 10² for FourierSHAP.

• Accuracy is budget-dependent. The abstract and Section 5.1 state that OddSHAP achieves state-of-the-art accuracy at larger sampling budgets. When m < d·η, the method falls back to TreeSHAP values of the gradient boosted tree proxy rather than running the odd regression.

Methodology in Plain English

The starting point is a simple algebraic observation: split any value function into the part that changes sign when you swap a coalition with its complement (the odd part) and the part that does not (the even part). Shapley values only care about the first part. So there is no reason to spend samples or computation modeling the second.

To exploit this, the authors need a basis whose functions are cleanly odd or even. The Fourier basis they use satisfies χ_T(S) = (−1)^{|S ∩ T|}, which is odd exactly when the interaction size |T| is odd. They then establish that solving the same weighted, boundary-constrained regression that KernelSHAP and PolySHAP use, but in the Fourier basis, still returns the true Shapley values — so the reformulation is safe.

The remaining problem is that there are combinatorially many odd Fourier terms; there are, for instance, "d choose 3" distinct third-order interactions. OddSHAP therefore screens candidates with a proxy: it fits a LightGBM gradient boosted tree to the sampled coalitions and extracts the odd-size Fourier interactions with the largest magnitudes, following ProxySPEX. The number of retained terms is tied to the budget by a sample-to-variable ratio η (the experiments use η = 10), so the model grows with available data rather than with dimension. Finally, it solves the weighted least squares problem restricted to singleton terms plus the selected odd interactions, using a strictly constrained formulation with a projection onto the subspace orthogonal to the boundary constraints rather than KernelSHAP's numerically unstable pseudo-infinite weights. Shapley values of the fitted odd function are then read off as −2 Σ β_T/|T| over selected odd terms containing each player.

Evaluation spans eight value functions and local explanations of 30 randomly selected predictions, with pairs sampled at equal probability over coalition sizes and budgets m ranging from d + 1 to min(2^d, 20000).

Why This Matters

Impact on research. Paired sampling has been a widely used but theoretically opaque trick in Shapley value estimation. The paper replaces folklore with a structural explanation, proving the underlying decoupling in general rather than for low-order interactions only, and thereby also settles a conjecture about order-k fits. It further shows that the choice of basis — unanimity versus Fourier — is not merely a representational preference but determines whether irrelevant even terms can be discarded at all.

Real-world applications of Shapley value attribution:

• Feature importance and local explanations in deployed models, so users can see which inputs drove a given prediction.
• Data valuation, quantifying how much each training point contributes to model performance.
• Causal inference, estimating the effect of variables in structural causal models.
• High-stakes decision support in healthcare, finance, and criminal justice, the domains the paper names as motivating the need to understand model decisions.

Industry relevance. The dominant practical cost in Shapley estimation is the number of times the black-box value function must be queried, and those queries can range from a model prediction to estimating conditional distributions to retraining a model entirely. OddSHAP is designed to spend those queries more efficiently and to keep the post-processing overhead polynomial in the budget, so it is most useful in exactly the regime where attribution is most expensive: model-agnostic settings with dozens to hundreds of features and no accessible structure.

Future Directions

• Small-budget behavior. At larger budgets OddSHAP leads, but RegressionMSR remains stronger on some individual value functions (DistilBERT and ViT16 in Table 1) and the algorithm falls back to TreeSHAP on the proxy when m < d·η. How to improve the low-budget regime is left open.

• Sensitivity to the screening subroutine. OddSHAP's support set is produced by ProxySPEX on a gradient boosted tree proxy with maximum depth 10. How the choice of proxy, depth, and interaction detector affects final accuracy is not resolved here.

• Tuning the sample-to-variable ratio. The method is governed by η, fixed at 10 in the experiments, which trades the number of regression variables against estimation variance. The optimal setting across dimensions and value functions is not established.

• Beyond the Fourier-and-GBT combination. The authors present the odd-subspace perspective as a general principle and note existing specialized exact methods for K-nearest neighbor, graph neural networks, Gaussian processes, linear models, and decision trees. Whether odd-only fitting can be combined with those structural approaches, or with other sparse Fourier learners such as SPEX and FourierSHAP, is an open question.

Target Audience

Researchers and practitioners in explainable AI who work on Shapley value estimation or feature attribution, particularly those already familiar with KernelSHAP, LeverageSHAP, or PolySHAP and interested in the regression-based view of these estimators. The paired-sampling theorem is also relevant to readers studying the theory of cooperative games and set-function decompositions, while the algorithm details — budget scaling, tree-based interaction screening, constrained regression — make the paper useful to engineers implementing attribution pipelines on high-dimensional models. Readers without prior exposure to Shapley value approximation will find the technical sections demanding, though the odd/even intuition itself is accessible.

Authors’ abstract

The Shapley value is a ubiquitous framework for attribution in machine learning, encompassing feature importance, data valuation, and causal inference. However, its exact computation is generally intractable, necessitating efficient approximation methods. While the most effective and popular estimators leverage the paired sampling heuristic to reduce estimation error, the theoretical mechanism driving this improvement has remained opaque. In this work, we provide an elegant and fundamental justification for paired sampling: we prove that the Shapley value depends exclusively on the odd component of the set function, and that paired sampling orthogonalizes the regression objective to filter out the irrelevant even component. Leveraging this insight, we propose OddSHAP, a novel consistent estimator that performs polynomial regression solely on the odd subspace. By utilizing the Fourier basis to isolate this subspace and employing a proxy model to identify high-impact interactions, OddSHAP overcomes the combinatorial explosion of higher-order approximations. Through an extensive benchmark, we find that OddSHAP achieves state-of-the-art estimation accuracy at larger sampling budgets.