On the Tractability of SHAP Explanations
Authors: Guy Van den Broeck, Anton Lykov, Maximilian Schleich, Dan Suciu
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Guy Van den Broeck EMAIL University of California 404 Westwood Plaza, Los Angeles, CA 90095, USA Anton Lykov EMAIL Maximilian Schleich EMAIL Dan Suciu EMAIL University of Washington 185 E Stevens Way NE, Seattle, WA 98195, USA |
| Pseudocode | Yes | Algorithm 1 Algorithm to compute value function v from Lundberg, Erion, and Lee (2018) procedure EXPVALUE(x, S, root = {left,right,feature,threshold,value}) |
| Open Source Code | No | The paper does not provide explicit statements about releasing source code for the methodology described, nor does it include links to a code repository. It mentions external tools and related work but not its own implementation. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity. It uses illustrative examples with hypothetical data but does not perform experiments on named or publicly available datasets, nor does it provide any links, DOIs, or citations to specific datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments using specific datasets, and therefore does not discuss training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and analyzes the computational complexity of SHAP explanations. It does not describe any experiments that would require specific hardware, and thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on the computational complexity of SHAP explanations, not on the practical implementation of algorithms or experiments. Therefore, it does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, analyzing the computational complexity of SHAP explanations. It does not describe any empirical experiments, and therefore no experimental setup details, hyperparameters, or training configurations are provided. |