02/02/2021

On the Tractability of SHAP Explanations

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

Keywords:

Abstract Paper Similar Papers

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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949004
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 9:41 
 0
 0
 0
 0
 4:25 
 0
 0
 0
 0
 16:23 
 0
 0
 0
 0
 2:43 
 0
 0
 0
 0
 15:02 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 14:24 
 0
 0
 0
 0
 18:58 
 0
 0
 0
 0
 2:59 
 0
 0
 0
 0
 20:19 
 0
 0
 0
 0
 16:56 
 0
 0
 0
 0
 13:10 
 0
 0
 0
 0
 4:46 
 1
 1
 0
 0
 5:46 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 5:09 
 0
 0
 0
 0
 14:38 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 8:38 
 0
 0
 0
 0
 15:00 
 0
 0
 0
 0
 2:58 
 0
 0
 0
 0
 14:20 
 0
 0
 0
 0
 3:07 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 17:50 
 0
 0
 0
 0
 10:40 
 0
 0
 0
 0
 3:04 
 0
 0
 0
 0
 11:15 
 0
 0
 0
 0
 9:28 
 0
 0
 0
 0
 4:41 
 0
 0
 0
 0
 14:48 
 0
 0
 0
 0
 8:04 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 3:32 
 0
 0
 0
 0
 6:15 
 0
 0
 0
 0
 16:38 
 0
 0
 0
 0
 14:31 
 0
 0
 0
 0
 10:11 
 0
 0
 0
 0
 4:52