Research map / Learning theory and algorithms / Prediction and decision losses
KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions
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.
Shows that pairwise Shapley interaction indices (and conjectures higher orders) are the solution of a weighted least squares problem, and proposes KernelSHAP-IQ, a KernelSHAP extension for SII that outperforms sampling baselines for feature interactions.
Problem
Shapley Interaction Index (SII) and k-Shapley values lack a weighted least squares (WLS) characterization analogous to KernelSHAP's representation of the Shapley value, which hampers efficient approximation of higher-order feature interactions.
Approach
Characterizes SII of order k as the solution to a WLS problem over all subsets that yields the optimal k-additive approximation of a game via k-SII; proves this for SV and pairwise SII, conjectures it for higher orders, and builds KernelSHAP-IQ (inconsistent and consistent variants) on this representation.
Key results
- KernelSHAP-IQ and inconsistent KernelSHAP-IQ clearly outperform permutation sampling, SHAP-IQ and SVARM-IQ on the bike rental and california housing regression benchmarks.
- KernelSHAP-IQ and SVARM-IQ achieve state-of-the-art results for second-order SII on the language model task; KernelSHAP-IQ outperforms SVARM-IQ at order 3 on the LM.
- Pairwise SII is proven to be the solution of a WLS problem with weights mu_2; higher-order representations are only empirically validated as conjectures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KernelSHAP-IQ instead of permutation sampling, SHAP-IQ, or SVARM-IQ | SII estimation on bike rental (BR) and California Housing (CH) · BR and CH | approximation quality | Helped |
| Use KernelSHAP-IQ or SVARM-IQ instead of the other baselines | SII estimation for the language model (LM) · LM | approximation quality | Helped |
| Use KernelSHAP-IQ instead of SVARM-IQ | Order-3 SII estimation for the language model (LM) · LM | approximation quality | Helped |
| Use inconsistent KernelSHAP-IQ instead of sampling-based baselines | Low-budget SII estimation · Low-budget scenarios | approximation quality | Helped |
| Use inconsistent KernelSHAP-IQ instead of consistent KernelSHAP-IQ | SII estimation · SII ground-truth convergence | convergence to ground truth | Hurt |
| Use inconsistent KernelSHAP-IQ across approximation orders | SV estimation · SV ground-truth convergence | convergence to ground truth | Helped |
Surprising findings
- Inconsistent KernelSHAP-IQ empirically recovers the exact Shapley values for any approximation order k, though its higher-order estimates do not converge to SII.
- For k>2 the soft-constraint weights do not converge to SII weights for subsets outside the finite-weight range, so a corrected representation with separate residual handling is needed.
Limitations
- Higher-order (k>2) WLS representation is only empirically validated via conjectures, without rigorous proof.
- Iterative computation means higher-order estimates are affected by earlier low-quality estimates.
- Exponentially many interactions require human-centred post-processing for interpretation.
Experimental setup
Datasets: IMDB California Housing Bike rental Adult census
Benchmarks: SOUM LM bike rental california housing ViT CNN adult census
Metrics: MSE Prec@10
Baselines: Permutation sampling SHAP-IQ SVARM-IQ inconsistent KernelSHAP
Builds on: KernelSHAP Shapley Interaction Index k-Shapley values SHAP-IQ SVARM-IQ
Closest papers by meaning
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.92)
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.89)
- Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.88)
- Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection (AAAI 2025 · similarity 0.88)
- Support Vector-based Estimation of Multilinear Games for Feature Selection and Explanation (AAAI 2025 · similarity 0.87)
- Approximating the Shapley Value without Marginal Contributions (AAAI 2024 · similarity 0.87)
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.