Updates on the Complexity of SHAP Scores
Authors: Xuanxiang Huang, Joao Marques-Silva
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. Moreover, this paper proves that the computational complexity of SHAP scores is #P-hard for these widely used families of random forest (RF) classifiers. |
| Researcher Affiliation | Academia | Xuanxiang Huang1 , Joao Marques-Silva2 1CNRS@CREATE, Singapore 2ICREA, University of Lleida, Spain |
| Pseudocode | Yes | Algorithm 1 Computation of SHAP scores for non-boolean DTs (Page 8) |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper focuses on theoretical analysis and proofs, and does not describe experiments that would require hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical analysis and proofs, and does not describe experiments that would require software dependencies. |
| Experiment Setup | No | The paper focuses on theoretical analysis and proofs, and does not describe an experimental setup. |