Titre :

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

Auteur(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]

Titre de la revue :

Journal of Machine Learning Research

Pagination :

1--58

Éditeur :

Microtome Publishing

Date de publication :

2023

ISSN :

1532-4435

Mot(s)-clé(s) en anglais :

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

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Commentaire :

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