📊 statistics

An Odd Estimator for Shapley Values

This paper introduces OddSHAP, a novel Shapley value estimator that achieves state-of-the-art accuracy by theoretically proving that paired sampling filters out irrelevant even components of the set function, thereby enabling efficient polynomial regression solely on the odd subspace.

Original authors: Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fabian Fumagalli, Landon Butler, Justin Singh Kang, Kannan Ramchandran, R. Teal Witter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a complex machine, like a self-driving car or a medical diagnosis tool, and it makes a decision. You want to know: Which specific parts (features) of the input were responsible for that decision?

In the world of machine learning, the "Shapley value" is the gold-standard math tool used to answer this. It fairly divides the "credit" for a decision among all the input features. However, calculating the exact Shapley value is like trying to count every single grain of sand on a beach to see how much each grain contributed to the total weight. It's mathematically possible but computationally impossible for complex problems because there are too many combinations to check.

This paper introduces a new, smarter way to estimate these values called OddSHAP. Here is how it works, explained through simple analogies.

1. The Problem: The "Too Many Combinations" Trap

To figure out how much a feature matters, you usually have to test the machine with every possible mix of features turned on and off.

The Old Way: Imagine you are trying to guess the flavor of a soup by tasting every possible combination of ingredients. If you have 100 ingredients, the number of combinations is astronomical. You can't taste them all.
The Current Best Way: Scientists use a trick called "paired sampling." Instead of tasting a random bowl of soup, they taste a bowl and its exact opposite (everything missing is added, everything added is missing). This helps cancel out some noise, but nobody knew why it worked so well until now.

2. The Big Discovery: The "Odd" Secret

The authors of this paper discovered a fundamental mathematical rule: The Shapley value only cares about the "odd" parts of the story.

Think of a value function (the machine's logic) as a song. This song has two types of notes:

Even Notes: These are symmetrical. If you flip the song upside down, it sounds the same. In math terms, these are patterns that cancel each other out when calculating Shapley values. They are "irrelevant noise" for this specific calculation.
Odd Notes: These are asymmetrical. If you flip them, they change. These are the only notes that actually matter for the Shapley value.

The Analogy: Imagine you are trying to measure the weight of a specific person standing on a scale, but the scale is also weighing a giant, symmetrical cloud of fog that surrounds them. The fog is heavy, but it's perfectly balanced (even), so it doesn't push the scale down more on the left or right. The "OddSHAP" insight is realizing you can just ignore the fog entirely and focus only on the person.

3. The Solution: OddSHAP

The authors built a new estimator called OddSHAP that uses this "Odd vs. Even" insight to save time and improve accuracy.

How it works: Instead of trying to learn the entire song (the whole machine logic), OddSHAP uses a clever sampling trick (paired sampling) to automatically filter out the "Even" notes. It then builds a model using only the "Odd" notes.
The Proxy Trick: To find the most important "Odd" notes without checking every single one, it uses a "proxy" model (a fast, simple decision tree) to act like a scout. The scout quickly identifies the few high-impact interactions (the loudest "Odd" notes) and ignores the rest.
The Result: It solves a much smaller math problem. It's like trying to solve a puzzle by only looking at the pieces that have a unique shape, ignoring the thousands of identical square pieces that don't help solve the picture.

4. Why It's Better

The paper tested this method against many other top-tier methods on various datasets (like predicting house prices, diagnosing cancer, or analyzing text).

Accuracy: When given enough data (a large "budget"), OddSHAP is the most accurate method available. It beats the previous best methods, especially for complex deep learning models (like those used in image recognition).
Efficiency: It avoids the "combinatorial explosion." While other methods get bogged down trying to calculate too many combinations, OddSHAP cuts straight to the relevant ones.
Explaining the Mystery: The paper also finally explains why the old "paired sampling" trick worked so well. It turns out that pairing samples was accidentally doing exactly what OddSHAP does on purpose: it mathematically cancels out the "Even" noise, leaving only the useful "Odd" signal.

Summary

OddSHAP is a new tool for explaining AI decisions. It realizes that to understand why a decision was made, you don't need to analyze every possible scenario. You only need to analyze the specific, asymmetrical patterns that actually drive the outcome. By ignoring the symmetrical "noise," it calculates the answer faster and more accurately than ever before.

Note on Limitations: The paper notes that while this method is excellent for complex, deep-learning models, it is slightly less efficient than some older, rigid methods when dealing with simple, tree-based models (like standard decision trees) where the "noise" is naturally very low. However, for the broad, complex problems where AI is most mysterious, OddSHAP is the new state-of-the-art.

Technical Summary: An Odd Estimator for Shapley Values

Problem Statement

The Shapley value is the standard framework for attribution in machine learning, used for feature importance, data valuation, and causal inference. However, its exact computation is generally intractable due to the exponential number of coalitions ( $2^d$ ) required for evaluation. While approximation methods exist, the most effective estimators often rely on "paired sampling" (sampling a coalition $S$ and its complement $S^c$ ), a heuristic that empirically improves accuracy but lacks a rigorous theoretical justification for why it works, particularly regarding higher-order interactions. Furthermore, existing higher-order polynomial regression methods (e.g., PolySHAP) face a scalability bottleneck where computational cost grows quadratically with the size of the polynomial basis, limiting their application in high-dimensional settings.

Methodology

The authors propose OddSHAP, a novel estimator that leverages a fundamental structural property of the Shapley value: it depends exclusively on the odd component of the value function $f$ .

Theoretical Foundation

Odd-Even Decomposition: Any set function $f$ can be uniquely decomposed into an odd component ( $f_{odd}$ ) and an even component ( $f_{even}$ ), where $f_{odd}(S) = -f_{odd}(S^c)$ and $f_{even}(S) = f_{even}(S^c)$ .
Shapley Value Property: The authors prove that $\phi_i(f) = \phi_i(f_{odd})$ for all players $i$ . The even component contributes zero to the Shapley value.
Mechanism of Paired Sampling: The paper provides the first general theoretical justification for paired sampling. By sampling pairs $(S, S^c)$ with symmetric weights, the weighted least squares regression problem orthogonalizes (decouples) into independent optimization problems for the odd and even components. Since the even component is irrelevant, paired sampling effectively isolates the signal required for Shapley values. This resolves a conjecture that paired sampling with an order- $k$ fit (for odd $k$ ) is equivalent to an order- $(k+1)$ fit.

Algorithm Design: OddSHAP

To exploit this insight while avoiding the combinatorial explosion of fitting all higher-order terms, OddSHAP operates in the Fourier basis rather than the unanimity basis.

Fourier Basis Advantage: In the Fourier basis, a basis function $\chi_T$ is odd if and only if the cardinality $|T|$ is odd. This allows for a clean separation of odd and even terms, unlike the unanimity basis.
Two-Stage Process:
1. Interaction Screening: A Gradient Boosted Tree (GBT) proxy model is fitted to the sampled coalitions. Using a method like ProxySPEX, the algorithm extracts a sparse set of high-impact odd-order Fourier coefficients. This avoids the need to fit all possible interactions.
2. Odd Regression: A weighted least squares regression is performed strictly on the selected odd-order Fourier terms (plus linear terms), constrained to match the value function on the empty and full sets.
Efficiency: By restricting the regression to the odd subspace and using a proxy to select terms, the method achieves polynomial time complexity relative to the sampling budget, bypassing the $O(d^k)$ scaling of fixed-order polynomial methods.

Key Contributions

Theoretical Unification of Paired Sampling: The paper proves that paired sampling implicitly decouples the regression objective into odd and even components, providing a rigorous explanation for its empirical success and generalizing previous findings limited to low-order interactions.
The OddSHAP Estimator: A consistent estimator that performs polynomial regression solely on a sparse selection of odd-order Fourier basis functions. It filters out irrelevant even components and identifies high-impact interactions via a proxy model.
State-of-the-Art Performance: Extensive benchmarks demonstrate that OddSHAP achieves superior estimation accuracy compared to existing methods (including RegressionMSR, LeverageSHAP, and PolySHAP) under larger sampling budgets, particularly in high-dimensional settings.

Experimental Results

The authors evaluated OddSHAP on eight value functions ranging from $d=14$ (DistilBERT) to $d=101$ (Crime dataset), covering deep learning (image and text) and tabular domains.

Accuracy: OddSHAP consistently achieved the lowest Mean Squared Error (MSE) and the best average rank across benchmarks, particularly when the sampling budget $m$ was sufficient to detect interactions ( $m > \eta \cdot d$ ).
Comparison with FFD: OddSHAP outperformed the Fixed-Budget Fractional Factorial Design (FFD-RD) on deep learning architectures (ViT, DistilBERT), where higher-order interactions are significant. Conversely, FFD-RD performed slightly better on tree-based tabular datasets where higher-order interactions decay rapidly, validating the domain-specific trade-offs.
Ablation Studies:
- Paired vs. Non-Paired: Paired sampling consistently outperformed non-paired sampling.
- Odd vs. All Interactions: Under paired sampling, including even interactions provided no benefit and slightly degraded performance by consuming the interaction budget with mathematically canceling terms.
- Sparsity: Incorporating a moderate number of odd interactions (controlled by the regression variable factor $\eta$ ) significantly reduced error compared to linear baselines, though overfitting occurred with too many interactions.

Significance and Claims

The paper claims that OddSHAP offers a flexible-budget framework that adapts robustly across diverse interaction structures. Its primary significance lies in:

Resolving an Open Conjecture: It provides the fundamental theoretical mechanism explaining why paired sampling works, moving beyond empirical observation to structural proof.
Scalability: It retains the expressive power of higher-order approximations without incurring their prohibitive combinatorial costs by restricting the model to the odd subspace.
Robustness: Unlike methods relying on rigid truncation assumptions (like FFD), OddSHAP remains effective in complex deep learning domains where high-order interactions are non-negligible, while maintaining competitiveness in sparse tabular domains.

The authors note limitations, specifically that the algorithm's runtime scales cubically with the budget due to the quadratic regression cost on selected interactions, and that paired sampling reduces the effective number of independent samples, potentially inflating variance. However, they conclude that the method represents a state-of-the-art approach for Shapley value estimation in model-agnostic settings.