On the Tractability of SHAP Explanations
- URL: http://arxiv.org/abs/2009.08634v2
- Date: Sun, 31 Jan 2021 00:41:39 GMT
- Title: On the Tractability of SHAP Explanations
- Authors: Guy Van den Broeck, Anton Lykov, Maximilian Schleich, Dan Suciu
- Abstract summary: SHAP explanations are a popular feature-attribution mechanism for explainable AI.
We show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model.
Going beyond fully-factorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting.
- Score: 40.829629145230356
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Explaining Text Similarity in Transformer Models [52.571158418102584]
Recent advances in explainable AI have made it possible to mitigate limitations by leveraging improved explanations for Transformers.
We use BiLRP, an extension developed for computing second-order explanations in bilinear similarity models, to investigate which feature interactions drive similarity in NLP models.
Our findings contribute to a deeper understanding of different semantic similarity tasks and models, highlighting how novel explainable AI methods enable in-depth analyses and corpus-level insights.
arXiv Detail & Related papers (2024-05-10T17:11:31Z) - On the Tractability of SHAP Explanations under Markovian Distributions [0.1578515540930834]
The SHAP framework is one of the most widely utilized frameworks for local explainability of ML models.
Despite its popularity, its exact computation is known to be very challenging, proven to be NP-Hard in various configurations.
Recent works have unveiled positive complexity results regarding the computation of the SHAP score for specific model families.
arXiv Detail & Related papers (2024-05-05T13:56:12Z) - Collaborative Learning with Different Labeling Functions [7.228285747845779]
We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the $n$ data distributions.
We show that, when the data distributions satisfy a weaker realizability assumption, sample-efficient learning is still feasible.
arXiv Detail & Related papers (2024-02-16T04:32:22Z) - Generalizing Backpropagation for Gradient-Based Interpretability [103.2998254573497]
We show that the gradient of a model is a special case of a more general formulation using semirings.
This observation allows us to generalize the backpropagation algorithm to efficiently compute other interpretable statistics.
arXiv Detail & Related papers (2023-07-06T15:19:53Z) - VCNet: A self-explaining model for realistic counterfactual generation [52.77024349608834]
Counterfactual explanation is a class of methods to make local explanations of machine learning decisions.
We present VCNet-Variational Counter Net, a model architecture that combines a predictor and a counterfactual generator.
We show that VCNet is able to both generate predictions, and to generate counterfactual explanations without having to solve another minimisation problem.
arXiv Detail & Related papers (2022-12-21T08:45:32Z) - A $k$-additive Choquet integral-based approach to approximate the SHAP
values for local interpretability in machine learning [8.637110868126546]
This paper aims at providing some interpretability for machine learning models based on Shapley values.
A SHAP-based method called Kernel SHAP adopts an efficient strategy that approximates such values with less computational effort.
The obtained results attest that our proposal needs less computations on coalitions of attributes to approximate the SHAP values.
arXiv Detail & Related papers (2022-11-03T22:34:50Z) - On Computing Relevant Features for Explaining NBCs [5.71097144710995]
It is the case that modelagnostic explainable AI (XAI) can produce incorrect explanations.
PI-explanations also exhibit important drawbacks, the most visible of which is arguably their size.
This paper investigates the complexity of computing sets of relevant features for Naive Bayes classifiers (NBCs) and shows that, in practice, these are easy to compute.
arXiv Detail & Related papers (2022-07-11T10:12:46Z) - An Imprecise SHAP as a Tool for Explaining the Class Probability
Distributions under Limited Training Data [5.8010446129208155]
An imprecise SHAP is proposed for cases when the class probability distributions are imprecise and represented by sets of distributions.
The first idea behind the imprecise SHAP is a new approach for computing the marginal contribution of a feature.
The second idea is an attempt to consider a general approach to calculating and reducing interval-valued Shapley values.
arXiv Detail & Related papers (2021-06-16T20:30:26Z) - Predictive Coding Approximates Backprop along Arbitrary Computation
Graphs [68.8204255655161]
We develop a strategy to translate core machine learning architectures into their predictive coding equivalents.
Our models perform equivalently to backprop on challenging machine learning benchmarks.
Our method raises the potential that standard machine learning algorithms could in principle be directly implemented in neural circuitry.
arXiv Detail & Related papers (2020-06-07T15:35:47Z) - A Theory of Usable Information Under Computational Constraints [103.5901638681034]
We propose a new framework for reasoning about information in complex systems.
Our foundation is based on a variational extension of Shannon's information theory.
We show that by incorporating computational constraints, $mathcalV$-information can be reliably estimated from data.
arXiv Detail & Related papers (2020-02-25T06:09:30Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.