On Efficiently Explaining Graph-Based Classifiers - IRIT - Centre National de la Recherche Scientifique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

On Efficiently Explaining Graph-Based Classifiers

Résumé

Recent work has shown that not only decision trees (DTs) may not be interpretable but also proposed a polynomial-time algorithm for computing one PI-explanation of a DT. This paper shows that for a wide range of classifiers, globally referred to as decision graphs, and which include decision trees and binary decision diagrams, but also their multi-valued variants, there exist polynomial-time algorithms for computing one PI-explanation. In addition, the paper also proposes a polynomial-time algorithm for computing one contrastive explanation. These novel algorithms build on explanation graphs (XpG's). XpG's denote a graph representation that enables both theoretical and practically efficient computation of explanations for decision graphs. Furthermore, the paper proposes a practically efficient solution for the enumeration of explanations, and studies the complexity of deciding whether a given feature is included in some explanation. For the concrete case of decision trees, the paper shows that the set of all contrastive explanations can be enumerated in polynomial time. Finally, the experimental results validate the practical applicability of the algorithms proposed in the paper on a wide range of publicly available benchmarks.
Fichier principal
Vignette du fichier
paper.pdf (364.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03311514 , version 1 (01-08-2021)

Licence

Paternité

Identifiants

  • HAL Id : hal-03311514 , version 1

Citer

Xuanxiang Huang, Yacine Izza, Alexey Ignatiev, Joao Marques-Silva. On Efficiently Explaining Graph-Based Classifiers. 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021), Principles of Knowledge Representation and Reasoning, Incorporated (KR Inc.), Nov 2021, Hanoi (virtual), Vietnam. ⟨hal-03311514⟩
148 Consultations
44 Téléchargements

Partager

Gmail Facebook X LinkedIn More