On the Computational Tractability of the (Many) Shapley Values
This work addresses the problem of efficiently computing Shapley-based explanations for machine learning practitioners, providing both tractability and intractability results that clarify the feasibility of different variants across models and distributions, though it is incremental in extending prior complexity analyses.
The paper analyzed the computational complexity of various Shapley value variants, including Conditional, Interventional, and Baseline SHAP, showing that Interventional and Baseline SHAP can be computed in polynomial time for certain models under Hidden Markov Model distributions, but are intractable for many neural networks and tree ensembles.
Recent studies have examined the computational complexity of computing Shapley additive explanations (also known as SHAP) across various models and distributions, revealing their tractability or intractability in different settings. However, these studies primarily focused on a specific variant called Conditional SHAP, though many other variants exist and address different limitations. In this work, we analyze the complexity of computing a much broader range of such variants, including Conditional, Interventional, and Baseline SHAP, while exploring both local and global computations. We show that both local and global Interventional and Baseline SHAP can be computed in polynomial time for various ML models under Hidden Markov Model distributions, extending popular algorithms such as TreeSHAP beyond empirical distributions. On the downside, we prove intractability results for these variants over a wide range of neural networks and tree ensembles. We believe that our results emphasize the intricate diversity of computing Shapley values, demonstrating how their complexity is substantially shaped by both the specific SHAP variant, the model type, and the distribution.