An Odd Estimator for Shapley Values

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.

To trust AI in high-stakes decisions, we must understand how it makes choices. "Shapley values" explain AI by acting as a mathematical referee, fairly assigning credit to each piece of input data, but calculating them is prohibitively slow. Our paper reveals a fundamental shortcut: Shapley values only rely on the "odd" mathematical components of an AI’s inner workings, completely ignoring the "even" parts. Leveraging this discovery, we created OddSHAP, a new tool that filters out irrelevant "even" data to focus solely on the necessary "odd" signals. This allows OddSHAP to estimate AI decisions much faster and more accurately than existing methods, making complex models transparent without wasting computing power.