The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits

• URL: http://arxiv.org/abs/2007.14045v3
• Date: Sat, 3 Apr 2021 16:34:05 GMT
• Title: The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
• Authors: Marcelo Arenas, Pablo Barcel\'o Leopoldo Bertossi, Mika\"el Monet
• Abstract summary: We show that the SHAP-score can be computed in time over the class of decision trees. We also establish the computational limits of the notion of SHAP-score.
• Score: 2.8682942808330703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Scores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP-score, a version of the Shapley value that can help explain the result of a learned model on a specific entity by assigning a score to every feature. While in general computing Shapley values is a computationally intractable problem, it has recently been claimed that the SHAP-score can be computed in polynomial time over the class of decision trees. In this paper, we provide a proof of a stronger result over Boolean models: the SHAP-score can be computed in polynomial time over deterministic and decomposable Boolean circuits. Such circuits, also known as tractable Boolean circuits, generalize a wide range of Boolean circuits and binary decision diagrams classes, including binary decision trees, Ordered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). We also establish the computational limits of the notion of SHAP-score by observing that, under a mild condition, computing it over a class of Boolean models is always polynomially as hard as the model counting problem for that class. This implies that both determinism and decomposability are essential properties for the circuits that we consider, as removing one or the other renders the problem of computing the SHAP-score intractable (namely, #P-hard).

Related papers

• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• On the Tractability of SHAP Explanations under Markovian Distributions [0.1578515540930834]
  The SHAP framework is one of the most widely utilized frameworks for local explainability of ML models. Despite its popularity, its exact computation is known to be very challenging, proven to be NP-Hard in various configurations. Recent works have unveiled positive complexity results regarding the computation of the SHAP score for specific model families.
  arXiv  Detail & Related papers  (2024-05-05T13:56:12Z)
• Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases [3.386124605656362]
  We adapt Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in time. We present applications to databases through database provenance, and an effective implementation of this algorithm within the Provable system.
  arXiv  Detail & Related papers  (2024-01-12T10:34:31Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  We study the problem of model selection in offline RL with value function approximation. We propose the first model selection algorithm for offline RL that achieves minimax rate-optimal inequalities up to logarithmic factors. We conclude with several numerical simulations showing it is capable of reliably selecting a good model class.
  arXiv  Detail & Related papers  (2022-11-03T17:32:34Z)
• Exact Shapley Values for Local and Model-True Explanations of Decision Tree Ensembles [0.0]
  We consider the application of Shapley values for explaining decision tree ensembles. We present a novel approach to Shapley value-based feature attribution that can be applied to random forests and boosted decision trees.
  arXiv  Detail & Related papers  (2021-12-16T20:16:02Z)
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption [127.439030701253]
  Probabilistic sentential decision diagrams are a class of structured-decomposable circuits. We propose a new scheme based on a partial closed-world assumption: data implicitly provide the logical base of the circuit. Preliminary experiments show that the proposed approach might properly fit training data, and generalize well to test data, provided that these remain consistent with the underlying logical base.
  arXiv  Detail & Related papers  (2021-07-26T12:01:56Z)
• Accurate Shapley Values for explaining tree-based models [0.0]
  We introduce two estimators of Shapley Values that exploit the tree structure efficiently and are more accurate than state-of-the-art methods. These methods are available as a Python package.
  arXiv  Detail & Related papers  (2021-06-07T17:35:54Z)
• On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results [2.552090781387889]
  In Machine Learning, the $mathsfSHAP$-score is used to explain the result of a learned model on a specific entity by assigning a score to every feature. We prove that the $mathsfSHAP$-score can be computed in time over deterministic and decomposable circuits.
  arXiv  Detail & Related papers  (2021-04-16T10:22:32Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  We present a model-agnostic explanation method for image classification based on a hierarchical extension of Shapley coefficients. Unlike other Shapley-based explanation methods, h-Shap is scalable and can be computed without the need of approximation. We compare our hierarchical approach with popular Shapley-based and non-Shapley-based methods on a synthetic dataset, a medical imaging scenario, and a general computer vision problem.
  arXiv  Detail & Related papers  (2021-04-13T13:11:02Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  Probabilistic sentential decision diagrams are logic circuits where the inputs of disjunctive gates are annotated by probability values. We develop the credal sentential decision diagrams, a generalisation of their probabilistic counterpart that allows for replacing the local probabilities with credal sets of mass functions. For a first empirical validation, we consider a simple application based on noisy seven-segment display images.
  arXiv  Detail & Related papers  (2020-08-19T16:04:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.