Abstract
Recent work has shown that not only decision trees (DTs) may not be interpretable but also proposed a polynomialtime algorithm for computing one PIexplanation 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 multivalued variants, there exist polynomialtime algorithms for computing one PIexplanation. In addition, the paper also proposes a polynomialtime 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.
Original language  English 

Title of host publication  Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning 
Editors  Meghyn Bienvenu, Gerhard Lakemeyer, Esra Erdem 
Place of Publication  Marina del Rey CA USA 
Publisher  Association for the Advancement of Artificial Intelligence (AAAI) 
Pages  356367 
Number of pages  12 
ISBN (Electronic)  9781956792997 
DOIs  
Publication status  Published  2021 
Event  International Conference on the Principles of Knowledge Representation and Reasoning 2021  Online Duration: 3 Nov 2021 → 12 Nov 2021 Conference number: 18th https://proceedings.kr.org/2021/#fullpapers (Proceedings) 
Publication series
Name  Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021 

Publisher  International Joint Conferences on Artificial Intelligence 
ISSN (Electronic)  23341033 
Conference
Conference  International Conference on the Principles of Knowledge Representation and Reasoning 2021 

Abbreviated title  KR 2021 
Period  3/11/21 → 12/11/21 
Internet address 

Keywords
 Explainable AI
 Explanation finding
 diagnosis
 causal reasoning
 abduction KR and machine learning
 inductive logic programming
 knowledge acquisition Knowledge representation languages