Research map / Learning theory and algorithms / Prediction and decision losses
Towards Trustable SHAP Scores
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 replacing the expected-value characteristic function in SHAP with similarity-based characteristic functions (built on WAXp/WCXp predicates) so that Shapley-based feature attributions avoid known misleading cases, and modifies the SHAP tool into sSHAP.
Problem
Exact SHAP scores can be misleading for some classifiers and regression models, assigning non-zero importance to irrelevant features and more importance to irrelevant features than to relevant ones, so their attributions disagree with formal explanations.
Approach
Keep the Shapley value definition but change the characteristic function: use a similarity predicate (whether the model output stays the same) and derive WAXp-based (a), WCXp-based (c), and similarity (s) characteristic functions, giving Shapley scores that satisfy feature (ir)relevancy compliance and strong value independence, and that equal the Shapley-Shubik-style scores.
Key results
- On six non-boolean decision trees from prior work, SHAP produced 4 to 15 feature-relevancy mismatches per classifier, while sSHAP produced 0 mismatches.
- The new similarity-based characteristic functions are shown to satisfy strong value independence and feature (ir)relevancy compliance, and the WAXp-based and WCXp-based SHAP scores coincide.
- Computing the WAXp/WCXp-based SHAP scores is NP-hard for d-DNNF and DDBC classifiers, while the similarity-based scores are #P-hard for boolean CNF/DNF classifiers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the expected-value characteristic function with the similarity characteristic function | SHAP · cs02a | SHAP-FRP mismatch: 11 -> 0 | Helped |
| Replace the expected-value characteristic function with the similarity characteristic function | SHAP · cs02b | SHAP-FRP mismatch: 4 -> 0 | Helped |
| Replace the expected-value characteristic function with the similarity characteristic function | SHAP · cs03a | SHAP-FRP mismatch: 5 -> 0 | Helped |
| Replace the expected-value characteristic function with the similarity characteristic function | SHAP · cs03b | SHAP-FRP mismatch: 4 -> 0 | Helped |
| Replace the expected-value characteristic function with the similarity characteristic function | SHAP · cs04a | SHAP-FRP mismatch: 15 -> 0 | Helped |
| Replace the expected-value characteristic function with the similarity characteristic function | SHAP · cs04b | SHAP-FRP mismatch: 4 -> 0 | Helped |
| Use the similarity characteristic function instead of the original classifier's expected-value function | SHAP on the example DT · Example DT, feature attributions | feature-relevancy alignment | Helped |
Surprising findings
- Boolean classifiers can still yield misleading SHAP scores even under the similarity-based characteristic function, so the fix does not guarantee the absence of all known issues.
- The exact SHAP score for a running regression tree example gives 0 to a relevant feature 1 and a positive score 1/4 to irrelevant feature 2.
Limitations
- The similarity-based characteristic function may still produce misleading results for boolean classifiers, which is left as future work.
- Exact computation is only feasible for simple models; the empirical evaluation is limited to small decision trees.
- Computing the proposed SHAP scores is intractable (NP-hard or #P-hard) for many model classes.
Experimental setup
Datasets: decision trees from prior case studies (cs02a, cs02b, cs03a, cs03b, cs04a, cs04b)
Benchmarks: decision trees from prior case studies
Metrics: count of irrelevant-feature mismatches (SHAP-FRP mismatch)
Baselines: SHAP BShap
Builds on: SHAP abductive and contrastive explanations power indices for XAI Shapley-Shubik index
Closest papers by meaning
- On the Tractability of SHAP Explanations under Markovian Distributions (ICML 2024 · similarity 0.86)
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.85)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
- SHAP values via sparse Fourier representation (NeurIPS 2025 · similarity 0.85)
- RankSHAP: Shapley Value Based Feature Attributions for Learning to Rank (ICLR 2025 · similarity 0.84)
- X-Hacking: The Threat of Misguided AutoML (ICML 2025 · similarity 0.84)
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.