On the Tractability of SHAP Explanations
Authors: Guy Van den Broeck, Anton Lykov, Maximilian Schleich, Dan Suciu6505-6513
AAAI 2021 | Conference 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 fullyfactorized 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,1 Anton Lykov,1 Maximilian Schleich,2 Dan Suciu2 1 University of California, Los Angeles 2 University of Washington, Seattle |
| Pseudocode | No | The paper focuses on theoretical complexity analysis and does not include pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the methodology described, as it is a theoretical complexity analysis. |
| Open Datasets | No | The paper is theoretical and does not use or provide public access information for a dataset used for training. |
| Dataset Splits | No | The paper is theoretical and does not describe dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe the hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, such as hyperparameters or training settings. |