• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The Tractability of SHAP-Score-Based ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Communication dans un congrès avec actes
Title :
The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
Author(s) :
Arenas, Marcelo [Auteur]
Barceló, Pablo [Auteur]
Pontificia Universidad Católica de Chile [UC]
Bertossi, Leopoldo [Auteur]
Universidad Adolfo Ibáñez [Santiago]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Conference title :
AAAI 2021 - 35th Conference on Artificial Intelligence
City :
Virtual
Country :
France
Start date of the conference :
2021-02-02
HAL domain(s) :
Informatique [cs]
English abstract : [en]
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 SHAPscore, a version of the Shapley value that ...
Show more >
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 SHAPscore, 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).Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://hal.inria.fr/hal-03147623/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-03147623/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-03147623/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017