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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On the Tractability of SHAP Explanations. https://app.cochat.ai/papers/10.1613/jair.1.13283
- The paper
- Van den Broeck, G., Lykov, A., Schleich, M., & Suciu, D. (2022). On the Tractability of SHAP Explanations. Journal of Artificial Intelligence Research. https://doi.org/10.1613/jair.1.13283
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.