CS Paper Radar

ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes

David Rundel, R. Teal Witter, Santo M. A. R. Thies, Matthias Feurer, Fabian Fumagalli, Bernd Bischl

cs.LG stat.ML ·submitted 2026-11-04 21:56 UTC · v1

Abstract

Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations. Recently, ShaplEIG has shown that adaptively selecting the coalitions to evaluate substantially improves sample efficiency over classical estimators. This, however, comes at the cost of a sequential procedure that, in every iteration, refits a Gaussian process surrogate of the game and selects the coalition with the largest expected information gain about the Shapley values. The resulting computational overhead limits its applicability to costly games with low evaluation budgets. We present fast adaptive Shapley value estimation with Odd Gaussian Processes (ShapleyOG) to overcome this limitation. ShapleyOG leverages the fact that Shapley values depend only on the odd component of the game, and we show that under paired sampling a Gaussian process surrogate on this component alone yields the same Shapley value posterior and coalition selection criterion from half as many observations. Moreover, ShapleyOG refits the surrogate only on a sparse schedule and efficiently updates the selection criterion in between, and it extends quadrature-based computation schemes to the prior covariance of the Shapley values, which allows for exact or cheaper approximate computation. In extensive experiments on diverse games, ShapleyOG matches the estimation accuracy of ShaplEIG while reducing its overhead by up to three orders of magnitude. As a result, it outperforms state-of-the-art non-adaptive estimators at equal total computation time already when a single evaluation takes a tenth of a second and a budget of a few thousand evaluations suffices, thereby widening the regime in which adaptive coalition selection is applicable and pays off.

Comment
Preprint under review

Closest papers

Nearest neighbours by meaning across the whole index.

RelShap: Relationally Consistent Shapley Explanations

cs.LG ·2026-08-11 ·Seungeun Lee, Joao Fonseca, Julia Stoyanovich
code/data similarity 0.64
Abstract

Machine learning pipelines commonly flatten relational data into single-table representations, discarding structural constraints. Widely used Shapley value-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations. We propose RelShap, a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations. The framework is estimator-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties. Functional dependencies further induce equivalence classes over feature coalitions, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not. Our code is available at: https://github.com/duneag2/relshap.

0.24

Rethinking Least-Core Computation in Contextual-Distractor Games

cs.LG cs.GT ·2026-10-05 ·Hiroshi Kera, Toshinori Yamauchi, Sai Ganesh Nagarajan
unusual similarity 0.63
Abstract · 12 + 19 pages, 0 + 7 figures, 5 + 8 tables

Game-theoretic attribution explains a model by assigning credit to its features or training examples. The least core has attracted interest as an alternative to Shapley-style averaging because it can expose players that cause substantial harm in rare, high-value contexts. However, least-core allocations are generally nonunique, and the choice of allocation can affect the resulting explanation. In this study, we investigate how payoff selection and coalition sampling affect least-core attribution. Our experiments show that selector choice matters for distinguishing useful and harmful contributions, and that sampling can degrade harmful-player identification across the tested selectors even when useful players remain well identified. These observations motivate efficient computation with all coalition constraints and a well-defined selector. We introduce entropic least core (ELC), a smooth approximation whose unique minimizer follows a continuous path along the temperature to the nucleolus, a classical refinement of the least core. Our experiments show that ELC approximates the nucleolus faster than an LP-based nucleolus solver while retaining small payoff errors, with further GPU acceleration at larger problem sizes. In the tested full-coalition contextual-distractor games, ELC matches the minimum-norm selector in identification accuracy and more accurately ranks distractors by harm.

0.58

Exact power indices for plurality-voting ensembles

cs.LG cs.DScs.GT ·2026-10-13 ·Ilie Sarpe, Theofanis Georgakopoulos, Aristides Gionis
top venue similarity 0.62
Abstract · Extended version of a work accepted at NeurIPS 2026. 59 pages, 9 figures, 11 tables

Plurality-voting ensembles aggregate the predictions of multiple base classifiers and output the most voted class, with ties typically broken at random. Despite the simple aggregation rule, attributing the impact of each base classifier to the ensemble's predictions is far from straightforward. That is, a single base classifier's impact depends on how it interacts with the votes of all other classifiers in the ensemble, for example, in resolving ties, and not only on its own predictions. We address the attribution problem using established tools from cooperative game theory, studying the Banzhaf and Shapley power indices for new games modeling plurality voting and random tie-breaking, for binary and multiclass classification settings. Computing power indices is, in general, intractable. Surprisingly, our methods, collectively named ENPOWER, enable the exact computation of Banzhaf and Shapley values in linear time for the binary classification setting and in low-degree polynomial time for the multiclass setting. The algorithms in ENPOWER rely on new combinatorial formulations of the Banzhaf and Shapley indices, yielding closed-form solutions for the binary case and ordinary generating function representations for the multiclass case. We validate empirically the methods in ENPOWER demonstrating their high applicability, providing attribution values not captured by existing methods. We apply the attribution of ENPOWER to: ensemble pruning and prompt-based ensembling of vision-language models.

0.40

Leverage-Enhanced Sampling Owen Method for Explainable Artificial Intelligence

cs.GT cs.LG ·2026-11-16 ·Jing Liu, Elena Parilina, Chi Zhao
similarity 0.61
Abstract · 25 pages, 6 figures

Recently, the Shapley value has been widely applied in machine learning for feature importance analysis and model explainability. The multilinear extension of games proposed by Owen (1972) expresses the Shapley value as the integral of partial derivatives along the main diagonal of the cube. Direct evaluation of this integral requires exponential-time computation of the partial derivatives. To improve computational efficiency, we propose a sampling-based estimation strategy within Owen's multilinear extension framework, combining stratified sampling with coalition leverage scores. Experimental results demonstrate that the proposed method significantly reduces computational costs while maintaining explanation accuracy.

0.42

Shapley Value Estimation for Multi-Site Data with Blockwise-Missing Features

cs.LG stat.ML ·2026-09-14 ·Siqi Li, Wangxuan Fan, Yiming Li, Doudou Zhou, Molei Liu
similarity 0.60
Abstract

Shapley value (SV)-based methods are the prevailing framework for feature attribution in machine learning, yet existing population-level Shapley estimators generally assume that observations used to evaluate the coalitional game are fully observed under a common feature space. This assumption is routinely violated in multi-site studies across biomedicine, social science, and environmental monitoring, where institutions record different features under different protocols, producing systematic blockwise missingness across sources. We first show that the standard remedy of imputing missing features before computing Shapley values introduces systematic, coalition-dependent bias into the resulting attributions. We then propose \textbf{FUSHAP} (\textbf{Fu}sion \textbf{Sh}apley \textbf{A}ttribution from \textbf{P}artially-observed data), a method that leverages partially-observed auxiliary sites to reduce the variance of a preliminary single-site Shapley estimate without imputation. A permutation-based screening step detects and excludes sites whose data distributions are incompatible with the target population. In synthetic experiments, FUSHAP achieves $3$--$8\times$ lower MSE than the single-site estimator and $2$--$3\times$ lower MSE than imputation baselines without incurring imputation-induced bias, and the screening procedure identifies misaligned sites with $82\%$ power at moderate misalignment and $100\%$ for strong misalignment. On multi-site air quality and multi-center clinical data, FUSHAP reduces MSE by approximately $3$--$7\times$ relative to the single-site estimator; in the clinical application, standard imputation can increase MSE above the single-site baseline.

0.23

CASI: Credit Assignment via Set Intervention for Agentic Retrieval

cs.AI cs.IRcs.LG ·2026-10-14 ·Xinyi Cheng, Tianfu Zhang, Jiwen Li, Xuesen Zhang, Shihao Yu +3 more
similarity 0.59
Abstract · 19 pages, 2 figures, 8 tables

Large language models increasingly generate multiple retrieval actions jointly, while downstream systems often provide only one reward for the resulting set. Broadcasting this reward provides a valid score-function gradient estimator for the expected set-level objective, but does not determine a coalition-dependent within-set attribution. We introduce CASI (Credit Assignment via Set Intervention for Agentic Retrieval), which constructs the missing counterfactual information through snapshot-grounded set intervention: generate and retrieve once, hold replayable snapshot components fixed, and evaluate alternative subsets under common conditions. Shapley aggregation converts these marginals into within-set credit, which bounded zero-sum advantage shaping incorporates into policy optimization. For m >= 4, singleton, leave-one-out, and full-set endpoints do not generally determine the Shapley allocation; under additive set values, extra coalition evaluations are redundant. In a five-action sponsored-search setting, exhaustive auction replay over 1,200 requests reveals substantial coalition dependence. Under the training-time evaluator, CASI achieves the highest median cosine similarity to a replay-defined Shapley reference among evaluated credit rules; under a sensitivity backend, CASI does not outperform Singleton. Across five independent training runs, CASI-trained policies achieve higher held-out auction-replay set value than Singleton- or Broadcast-trained policies. In a randomized seven-day production A/B test on 10% of traffic, the CASI-trained policy yields an observed 3.51% lift in the primary advertiser-value metric over production control.

0.23

Closed-Form Predicate-Level Shapley Attribution for Sliding-Window Aggregates

cs.DB ·2026-08-24 ·Pouya Khani, Ira Assent
similarity 0.57
Abstract · submitted to IEEE Access

Streaming engines report sliding-window aggregates in real time, but they do not explain \emph{why} an aggregate takes its current value. A natural target is the Shapley value from cooperative game theory, which axiomatically distributes an aggregate among the tuples in the window. Practitioners, however, ask predicate-level questions (e.g., how much a region or customer tier contributed to an average or variance spike). Exact Shapley computation is exponential in the window size, and existing estimators discard the massive overlap between consecutive windows. We show that for SUM, COUNT, AVG, and population/sample variance, exact predicate-level Shapley values admit closed forms in three additively maintained summaries per predicate (count, sum, and sum of squares), with coefficients that depend only on two running harmonic numbers. Attribution therefore reduces to $O(1)$ summary updates per slide for registered predicates, with no coalition enumeration. Overlapping and compositional predicates are answered exactly via atomic refinement of Boolean signatures. We further characterize the phenomenon: every moment-polynomial aggregate admits such a form, while MAX, MIN, and quantiles provably do not at any fixed moment order. Experiments match brute-force Shapley values to floating-point precision on over $10{,}000$ windows, sustain $\approx\!2\,μ$s per slide up to $N=10^6$ ($3{,}200\times$ faster than per-window recomputation of the same formulas), and explain a nighttime fare spike on 2.9M NYC taxi trips at $\approx\!1.8$M summary updates per second.

0.54

Why Is SHAP Not a Reliable Standalone Explanation Framework for Malware Detection?

cs.CR ·2026-09-04 ·Seyedreza Mohseni, Edward Raff, Manas Gaur
positiontheory similarity 0.57
Abstract

Machine learning is widely used for malware detection, but its decisions must be explained. An analyst needs to know whether a model has learned genuine malicious behavior or only dataset-specific patterns \cite{gaur2021semantics}. SHapley Additive exPlanations (SHAP) is the standard tool for this, backed by formal properties such as local accuracy, missingness, and consistency. We argue that these guarantees are insufficient for reliable malware interpretation. We claim SHAP explains a chosen feature-coalition game, not malware behavior in the data. That game is fixed only after the analyst selects the feature players, the missing feature rule, the background distribution, and the simplified input mapping. In static Portable Executable feature spaces, groups such as byte histograms, byte-entropy, strings, headers, sections, imports, and data-directories are not independent signals but are jointly shaped by file structure, packing, compiler behavior, and family conventions. We prove that this dependence makes conditional SHAP dilute a model's feature credit by a factor of $1/m$ across $m-1$ redundant features, attributes importance to features the model never uses, and even reverses the sign of an unused feature's attribution when the data distribution changes; interventional SHAP, meanwhile, queries off-manifold coalitions that no real executable would exhibit. Experiments on EMBER-2018, EMBER-2024, and BODMAS with fixed LightGBM and XGBoost detectors confirm these effects. We therefore position SHAP as a limited diagnostic that requires an explicitly stated data distribution and domain validation, not a standalone account of malware behavior.

0.11