Tractability and Non-Approximability of SHAP-Score-Based Explanations
Marcelo Arenas, Pablo Barcelo, Leopoldo Bertossi, Mikael Monet; 24(63):1−58, 2023.
Abstract
Shapley values-based scores are commonly used to provide explanations for classification results in machine learning models. One such score is the Shap-score, which assigns a score to each feature in order to explain the outcome of a learned model on a specific entity. While computing Shapley values is generally a computationally challenging task, we present a positive result by showing that the Shap-score can be computed in polynomial time over deterministic and decomposable Boolean circuits using product distributions on entities. These circuits, which are studied in the field of Knowledge Compilation, encompass various classes such as binary decision trees, Ordered Binary Decision Diagrams (OBDDs), and Free Binary Decision Diagrams (FBDDs). Our positive result is applicable to binary classifiers as well as cases where each feature is associated with a finite domain of possible values.
Additionally, we establish the computational limits of the concept of Shap-score by proving that, under a mild condition, computing it over a class of Boolean models is as hard as the model counting problem for that class. This implies that both determinism and decomposability are crucial properties for the circuits we consider, as removing either of them makes the problem of computing the Shap-score intractable ($\\#P$-hard). Furthermore, we demonstrate that computing Shap-scores is $\\#P$-hard even over the class of propositional formulas in DNF. Given this negative result, we explore the existence of fully-polynomial randomized approximation schemes (FPRAS) for computing Shap-scores over this class. In contrast to the model counting problem for DNF formulas, which has an FPRAS, we prove that no such FPRAS exists (under widely believed complexity assumptions) for the computation of Shap-scores. Surprisingly, this negative result holds true even for the class of monotone formulas in DNF.
These techniques can be further extended to establish another significant negative result: under widely believed complexity assumptions, there is no polynomial-time algorithm that can determine, given a monotone DNF formula $\\varphi$ and features $x$ and $y$, whether the Shap-score of $x$ in $\\varphi$ is smaller than the Shap-score of $y$ in $\\varphi$.
[abs]