The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
On the Tractability of SHAP Explanations
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Unified Approach to Interpreting Model Predictions
Lundberg, S., & Lee, S.-I. (2017) · arXiv · doi:10.48550/arxiv.1705.07874 · Cited by 23,707
Gauriat, C.-M., Pencolé, Y., Ribot, P., & Brouillet, G. (2024) · HAL (Le Centre pour la Communication Scientifique Directe) · doi:10.4230/oasics.dx.2024.27 · Cited by 12,586
From local explanations to global understanding with explainable AI for trees
Lundberg, S. M., Erion, G., Chen, H., DeGrave, A., Prutkin, J. M., Nair, B., Katz, R., Himmelfarb, J., Bansal, N., & Lee, S.-I. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-019-0138-9 · Cited by 10,551
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
Rendle, S. (2010) · 2010 IEEE International Conference on Data Mining · doi:10.1109/icdm.2010.127 · Cited by 3,189
Explaining prediction models and individual predictions with feature contributions
Štrumbelj, E., & Kononenko, I. (2014) · Knowledge and Information Systems · doi:10.1007/s10115-013-0679-x · Cited by 2,286
(2001) · Cited by 1,932
Datta, A., Sen, S., & Zick, Y. (2016) · 2016 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2016.42 · Cited by 728
Darwiche, A., & Marquis, P. (2002) · Cited by 602
The explanation game: Explaining machine learning models using shapley values
Merrick, L., & Taly, A. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-57321-8_2 · Cited by 277
The Shapley Value: Essays in Honor of Lloyd S. Shapley.
Cubitt, R., & Roth, A. E. (1991) · The Economic Journal · doi:10.2307/2233574 · Cited by 248
Problems with Shapley-value-based explanations as feature importance measures
Kumar, I. E., Venkatasubramanian, S., Scheidegger, C., & Friedler, S. (2020) · arXiv · doi:10.48550/arxiv.2002.11097 · Cited by 228
Performing Bayesian inference by weighted model counting
Sang, T., Bearne, P., & Kautz, H. (2005) · Cited by 209
Feature relevance quantification in explainable AI: A causal problem
Janzing, D., Minorics, L., & Blöbaum, P. (2019) · arXiv · doi:10.48550/arxiv.1910.13413 · Cited by 207
Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation MethodsPreprint
Slack, D., Hilgard, S., Jia, E., Singh, S., & Lakkaraju, H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.02508 · Cited by 203
Skolemization for Weighted First-Order Model CountingPreprint
den Broeck, G. V., Meert, W., & Darwiche, A. Y. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.5378 · Cited by 68
Symmetric Weighted First-Order Model Counting
Beame, P. W., den Broeck, G. V., Gribkoff, E., & Suciu, D. M. (2015) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/2745754.2745760 · Cited by 61
Self-citationTreewidth in Verification: Local vs. Global
Ferrara, A., Pan, G., & Vardi, M. Y. (2005) · Lecture notes in computer science · doi:10.1007/11591191_34 · Cited by 49
Causality-based Explanation of Classification Outcomes
Bertossi, L., Li, J., Schleich, M., Suciu, D. M., & Vagena, Z. (2020) · doi:10.1145/3399579.3399865 · Cited by 43
Self-citationWhat to Expect of Classifiers? Reasoning about Logistic Regression with Missing Features
Khosravi, P., Liang, Y., Choi, Y., & den Broeck, G. V. (2019) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/377 · Cited by 38
Gade, K., Geyik, S. C., Kenthapadi, K., Mithal, V., & Taly, A. (2020) · ACM Conference on Fairness, Accountability, and Transparency (FAccT) · doi:10.1145/3351095.3375664 · Cited by 36
Liang, Y., & den Broeck, G. V. (2019) · AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) · doi:10.1609/aaai.v33i01.33014277 · Cited by 34
On Tractable Computation of Expected PredictionsPreprint
Khosravi, P., Choi, Y., Liang, Y., Vergari, A., & den Broeck, G. V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.02182 · Cited by 28
Cited by
A., S., & R., S. (2023) · Decision Analytics Journal · doi:10.1016/j.dajour.2023.100230 · Cited by 432
Interpretable Machine Learning for Personalized Medical Recommendations: A LIME-Based Approach
Wu, Y., Zhang, L., Bhatti, U. A., & Huang, M. (2023) · Diagnostics · doi:10.3390/diagnostics13162681 · Cited by 74
Maarif, M. R., Saleh, A. R., Habibi, M., Fitriyani, N. L., & Syafrudin, M. (2023) · Information · doi:10.3390/info14050265 · Cited by 58
Metadata
- Authors
- Van den Broeck, G., Lykov, A., Schleich, M., & Suciu, D.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2022-06-23
- Volume
- 74
- Pages
- 851-886
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W3175110185
- Cited by
- 469
- References
- 23
- FWCI
- 27.22
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.