The Inadequacy of Shapley Values for Explainability

Xuanxiang Huang, João Marques-Silva

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:

  1. 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.
  2. 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.
  3. Truth Table Enumeration: For small models (3-4 variables), the authors exhaustively analyzed every possible Boolean function.
  4. d-DNNF Circuits: For larger models, "deterministic decomposable negation normal form" circuits were used to enable tractable exact calculations.
Table 1: Truth table and corresponding logical and game-theoretic explanations for a 3-variable Boolean function.

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

Abstract

This paper develops a rigorous argument for why the use of Shapley values in explainable AI (XAI) will necessarily yield provably misleading information about the relative importance of features for predictions. Concretely, this paper demonstrates that there exist classifiers, and associated predictions, for which the relative importance of features determined by the Shapley values will incorrectly assign more importance to features that are provably irrelevant for the prediction, and less importance to features that are provably relevant for the prediction. The paper also argues that, given recent complexity results, the existence of efficient algorithms for the computation of rigorous feature attribution values in the case of some restricted classes of classifiers should be deemed unlikely at best.
BibTeX
@misc{huang2023inadequacy,
  author = {Xuanxiang Huang and João Marques-Silva},
  title = {{The Inadequacy of Shapley Values for Explainability}},
  year = {2023},
  eprint = {2302.08160},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.08160},
}
Figure