Research map / Learning theory and algorithms / Prediction and decision losses
Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GEM-FIX, which estimates the Möbius representation of explanation games via regularized regression, yielding linear-time Shapley values and detection of significant high-order feature interactions.
Problem
Shapley-value explanations of black-box models typically assume inessential explanation games (additive characteristic function), which limits quantifying feature interactions; exact Shapley computation is exponential in features.
Approach
Estimate the Möbius representation of the explanation game with a regression over sampled coalitions (Kernel SHAP-style samples), relaxing the inessential-game assumption; a Gram-matrix identity (inner product = 2^|S∩S'|-1) and a representation of Shapley values in terms of the |S+| coefficients make computation polynomial in samples, and sparsity on the coefficients reveals significant high-order
Key results
- On synthetic games, GEM-FIX estimates Shapley values more accurately than Kernel SHAP, especially with few samples.
- In the synthetic interaction experiment over 120 datasets, second-order interactions had 236 TP vs 4 FN out of 240 total, while fourth-order recovery was weaker (160 TP, 80 FN).
- On textual sentiment masking, GEM-FIX keeps predictions stable when significant portions of reviews are masked, with execution time on par with Kernel SHAP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate Shapley values with GEM-FIX instead of Kernel SHAP | Cooperative-game simulation · Essential games | Absolute Shapley-value deviation | Helped |
| Use GEM-FIX-LR instead of the regularized GEM-FIX formulation (ablation) | GEM-FIX · Cooperative-game simulation | Shapley-value estimation availability | Hurt |
| Use GEM-FIX to identify influential features | Synthesized datasets · Three synthesized datasets | Average rank of influential features | Mixed |
| Use GEM-FIX for interaction detection | Synthetic datasets with known interaction terms · Second-order interactions | True positives: 236 | Helped |
| Use GEM-FIX for interaction detection | Synthetic datasets with known interaction terms · Third-order interactions | True positives: 228 | Helped |
| Use GEM-FIX for interaction detection | Synthetic datasets with known interaction terms · Fourth-order interactions | False negatives: 80 | Hurt |
| Use GEM-FIX to estimate Shapley values instead of other Shapley-value methods | Random-forest models on tabular datasets · Five tabular datasets | Deviation from exact Shapley values | Helped |
| Mask words identified as least important by GEM-FIX | Pre-trained BERT sentiment model · Three textual datasets | Prediction deviation after masking | Helped |
Surprising findings
- On tabular data, GEM-FIX is more accurate at small sample sizes, but other methods overtake it as sample size grows.
- GEM-FIX-LR cannot produce estimates when the player count exceeds 13.
Limitations
- Interaction detection can become time-intensive as the number of significant interactions grows.
- Overlapping interactions cause higher false positives in second-order detection and higher false negatives in fourth-order detection.
- Does not quantify uncertainty of Shapley estimates or the sample size needed.
Experimental setup
Datasets: synthetic cooperative games synthetic binary-feature interaction datasets five real-world tabular datasets three textual sentiment review datasets
Benchmarks: synthetic cooperative games synthetic influential-feature datasets synthetic interaction detection five tabular datasets sentiment analysis word-masking
Metrics: absolute deviation from exact Shapley value average rank of influential features true positives/false positives/false negatives for interacti prediction deviation after masking words execution time
Baselines: Kernel SHAP Unbiased SHAP Sampling SHAP Bivariate SHAP LIME MAPLE SHAP-L2
Builds on: Kernel SHAP Möbius transform for cooperative games Shapley interaction index
Closest papers by meaning
- Support Vector-based Estimation of Multilinear Games for Feature Selection and Explanation (AAAI 2025 · similarity 0.89)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.89)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.88)
- Explaining Probabilistic Models with Distributional Values (ICML 2024 · similarity 0.87)
- Learning to Understand: Identifying Interactions via the Möbius Transform (NeurIPS 2024 · similarity 0.86)
- Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.