Proceedings

Updates on the Complexity of SHAP Scores

Xuanxiang Huang, Joao Marques-Silva

Download BibTeX Cite

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. Main Track. Pages 403-412.

https://doi.org/10.24963/ijcai.2024/45

Keywords

  • AI Ethics, Trust, Fairness: ETF: Explainability and interpretability
  • AI Ethics, Trust, Fairness: ETF: Trustworthy AI
  • Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning
  • Machine Learning: ML: Explainable/Interpretable machine learning

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.

Xuanxiang Huang, and Joao Marques-Silva. 2024. Updates on the Complexity of SHAP Scores. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24. IJCAI, 403–412. https://doi.org/10.24963/ijcai.2024/45
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards