On the Tractability of SHAP Explanations

Guy Van den Broeck, Anton Lykov, Maximilian Schleich, Dan Suciu

Abstract

Shapley Additive Explanations (SHAP) have become a standard for interpreting complex machine learning models. However, the computational cost of calculating these values is often overlooked. This paper, presented at AAAI-21, provides a rigorous theoretical analysis of the computational complexity of SHAP. We establish that while SHAP is tractable for specific model classes under feature independence, it becomes #P-hard for logistic regression and settings involving feature dependencies or empirical distributions. These findings suggest that the exact computation of SHAP is often fundamentally intractable for many practical applications.

Introduction

As machine learning models are increasingly deployed in high-stakes environments like healthcare and finance, the need for interpretability has never been greater. SHAP, based on Shapley values from cooperative game theory, is one of the most popular frameworks for assigning "credit" to input features for a specific prediction.

Despite its widespread adoption, the mathematical definition of SHAP involves calculating the expected value of a model over all possible subsets of features—an operation that is inherently exponential. This research addresses a critical gap in the field: identifying which combinations of model types and data distributions allow for efficient (polynomial-time) SHAP calculations and which are computationally impossible at scale.

Methodology

The authors utilize computational complexity theory to categorize the "hardness" of computing SHAP values. The analysis is structured across three distinct data distribution settings that reflect both theoretical ideals and practical implementations:

  1. Fully-Factorized Distributions: Features are assumed to be independent.
  2. Naive Bayes Distributions: Features exhibit a simple dependency on a central "parent" variable.
  3. Empirical Distributions: The distribution is defined by the training dataset itself, a common approach used in tools like KernelSHAP.

The study employs reductions, demonstrating that if an efficient algorithm existed for SHAP in certain settings, it would also solve famously hard problems such as #SAT or the Number Partitioning Problem.

Key Insights and Tractability Analysis

The Expected Value Equivalence

A primary contribution of the paper is the proof that, under the assumption of independent features, computing SHAP is exactly as hard as computing the model's expected value ($E[F]$). This means that if a model's average output can be calculated efficiently, its SHAP explanations are also tractable.

The Logistic Regression Paradox

One of the most surprising findings is that logistic regression—often considered a "simple" or "interpretable" model—is #P-hard to explain with SHAP, even under uniform or independent distributions. The intractability stems from the non-linear sigmoid function, which transforms the task of averaging model outputs into a complex counting problem.

The Impact of Feature Dependency

The research highlights that feature dependency is a "tractability killer." Even a minimal degree of dependency, such as that found in a Naive Bayes setup, renders SHAP computation NP-hard, even for trivial models that only consider a single feature.

The Empirical Distribution Trap

Many practitioners use the training dataset as a background distribution (the "empirical distribution"). The authors prove that computing exact SHAP values in this setting is #P-hard. This implies that popular implementations like KernelSHAP cannot be scaled to provide exact values for large datasets without significant computational overhead.

Summary of Results

The following table summarizes the tractability map established by the authors:

Model Class Feature Distribution Complexity
Linear Regression / Decision Trees Independent Tractable (Polynomial Time)
d-DNNF Circuits Independent Tractable (Polynomial Time)
Logistic Regression Independent #P-hard
Any Model (even trivial) Naive Bayes NP-hard
Any Model Empirical (Dataset) #P-hard

Additionally, the paper notes that the popular TreeSHAP algorithm, in its original formulation, was not strictly correct for certain distributions, and the general problem it attempts to solve is fundamentally #P-hard.

Conclusion and Future Directions

This work establishes that exact SHAP explanations are often computationally out of reach. While practitioners frequently rely on approximations (such as Monte Carlo sampling), these methods may require a prohibitive number of samples to converge or may provide unreliable results.

Future research should focus on:

  • Identifying specific "tractable" probabilistic models (e.g., Sum-Product Networks) that might allow for efficient SHAP even with dependencies.
  • Investigating the complexity of approximating SHAP within guaranteed error bounds.
  • Developing new explanation metrics designed specifically for computational efficiency without sacrificing the axiomatic strengths of the Shapley value.

Summary updated

Abstract

SHAP explanations are a popular feature-attribution mechanism for explainable AI. They use game-theoretic notions to measure the influence of individual features on the prediction of a machine learning model. Despite a lot of recent interest from both academia and industry, it is not known whether SHAP explanations of common machine learning models can be computed efficiently. In this paper, we establish the complexity of computing the SHAP explanation in three important settings. First, we consider fully-factorized data distributions, and show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model. This fully-factorized setting is often used to simplify the SHAP computation, yet our results show that the computation can be intractable for commonly used models such as logistic regression. Going beyond fully-factorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting: computing SHAP explanations of trivial classifiers over naive Bayes distributions. Finally, we show that even computing SHAP over the empirical distribution is #P-hard.
BibTeX
@inproceedings{broeck2021tractability,
  author = {Guy Van den Broeck and Anton Lykov and Maximilian Schleich and Dan Suciu},
  title = {{On the Tractability of SHAP Explanations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=OqzeCVNTMIy},
}
Figure