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:
- Fully-Factorized Distributions: Features are assumed to be independent.
- Naive Bayes Distributions: Features exhibit a simple dependency on a central "parent" variable.
- 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