Title :

On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results

Author(s) :

Arenas, Marcelo [Auteur]
Pontificia Universidad Católica de Chile [UC]
Millennium Institute for Foundational Research on Data [IMFD]
Barceló, Pablo [Auteur]
Millennium Institute for Foundational Research on Data [IMFD]
Pontificia Universidad Católica de Chile [UC]
Bertossi, Leopoldo [Auteur]
Millennium Institute for Foundational Research on Data [IMFD]
Universidad Adolfo Ibáñez [Santiago]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]

Journal title :

Journal of Machine Learning Research

Pages :

1--58

Publisher :

Microtome Publishing

Publication date :

2023

ISSN :

1532-4435

English keyword(s) :

Explainable AI Shapley values SHAP score knowledge compilation FPRAS
Explainable AI
Shapley values
SHAP score
knowledge compilation
FPRAS

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, we prove a strong positive result stating that the SHAP-score can be computed in polynomial time over deterministic and decomposable Boolean circuits under the so-called product distributions on entities. Such circuits are studied in the field of Knowledge Compilation and 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). Our positive result extends even beyond binary classifiers, as it continues to hold if each feature is associated with a finite domain of possible values.Show less >

Language :

Anglais

Popular science :

Non

Comment :

Up to the formatting, this is the exact content of the paper in Journal of Machine Learning Research (JMLR)

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL