Updates on the Complexity of SHAP Scores

Xuanxiang Huang; Joao Marques-Silva

IJCAI 2024poster3 citations

Updates on the Complexity of SHAP Scores

Abstract

SHAP scores represent one of the most widely used methods of explainability by feature attribution, as illustrated by the explainable AI tool SHAP. A number of recent works studied the computational complexity of the exact computation of SHAP scores, covering a comprehensive range of families of classifiers. This paper refines some of the existing complexity claims, including families of classifiers for which the computation of SHAP scores is computationally hard and those for which there exist polynomial-time algorithms.

AI Ethics, Trust, Fairness: ETF: Explainability and interpretabilityAI Ethics, Trust, Fairness: ETF: Trustworthy AIKnowledge Representation and Reasoning: KRR: Computational complexity of reasoningMachine Learning: ML: Explainable/Interpretable machine learning

BibTeX

@inproceedings{ijcai2024p45,
  title     = {Updates on the Complexity of SHAP Scores},
  author    = {Huang, Xuanxiang and Marques-Silva, Joao},
  booktitle = {Proceedings of the Thirty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-24}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Kate Larson},
  pages     = {403--412},
  year      = {2024},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2024/45},
  url       = {https://doi.org/10.24963/ijcai.2024/45},
}