Abstract
Shapley values are widely considered the gold standard for feature attribution in Explainable AI (XAI). This paper challenges this status by demonstrating that Shapley values frequently assign high importance to logically irrelevant features while ignoring essential ones. Through exact computation on Boolean functions and benchmark datasets, the authors identify systemic pitfalls where game-theoretic importance diverges from logical necessity, warning against the uncritical use of these metrics.
Introduction
In the field of Explainable AI (XAI), two primary paradigms exist for understanding model decisions: feature selection and feature attribution. Feature selection focuses on identifying a minimal, "irreducible" set of features sufficient to guarantee a prediction—a logic-based approach. Conversely, feature attribution, dominated by game-theoretic Shapley values (and the SHAP library), assigns numerical importance scores to every feature.
Despite their popularity, there is no formal guarantee that a high Shapley value corresponds to a feature that is logically "relevant." A feature is irrelevant if its value cannot change the prediction for a specific instance. This research proves that Shapley values frequently violate the basic intuition of relevancy, potentially leading users to focus on "dead weight" variables.
Methodology
The authors bridge the gap between game theory and formal logic by defining Abductive Explanations (AXp)—the smallest set of features that, if fixed, force the model to return the same prediction. To evaluate the reliability of Shapley values, the study employed several rigorous techniques:
- Exact Computation: Rather than relying on the approximations used in the SHAP library, the authors used specialized algorithms to compute exact Shapley values for Boolean functions.
- Pitfall Identification: Four specific issues (I1–I4) were defined to categorize failures. For instance, Issue I1 occurs when an irrelevant feature receives a non-zero score, and Issue I2 occurs when an irrelevant feature is ranked as more important than a relevant one.
- Truth Table Enumeration: For small models (3-4 variables), the authors exhaustively analyzed every possible Boolean function.
- d-DNNF Circuits: For larger models, "deterministic decomposable negation normal form" circuits were used to enable tractable exact calculations.
The study utilized six datasets from the Penn Machine Learning Benchmarks (PMLB), including corral, mux6, and xd6, to train Read-once Decision Trees (RODTs), which were then converted into d-DNNF circuits for formal analysis.
Key Insights and Results
The research reveals a fundamental "relevancy conflict." A feature is logically relevant if it belongs to at least one AXp for a prediction. However, Shapley values do not respect this property.
Ubiquity of Errors
The analysis of 4-variable Boolean functions showed that 99.67% of functions contained at least one instance where an irrelevant feature was given a non-zero Shapley value (Issue I1). Furthermore, in over 61% of these functions, an irrelevant feature was ranked as more important than a relevant one (Issue I2).
Real-World Data Failure
On the xd6 dataset, the majority of top-ranked features were provably irrelevant in 25.8% of instances. Additionally, in approximately 11.9% of cases, a feature necessary for the prediction was assigned a Shapley value of exactly zero (Issue I3).
SHAP vs. Exact Shapley
A critical finding for practitioners is that the SHAP library—the most common implementation—rarely matches exact Shapley values. In testing, SHAP produced the correct feature ranking in only 3.53% of instances.
Conclusion
The authors argue that creating a perfect attribution measure that respects logical relevancy is likely computationally "hard" (NP-complete). While exact methods like d-DNNFs are feasible for small-to-medium models, they face complexity barriers at scale. This work serves as a warning: Shapley values can be provably misleading, and high attribution scores do not necessarily imply logical necessity. Future research is required to find tractable, logically sound alternatives or to identify model classes where Shapley values remain reliable.
Summary updated