Abductive and Contrastive Explanations for Bayesian Networks and their Computational Complexity

Abstract

Contrastive and abductive explanations are types of explanations that can be used to explain a classification by a classifier. An abductive explanation is a minimal subset of input variables that guarantees the observed classification. A contrastive explanation is a minimal subset of input variables that, when changed, could lead to another predicted class. We show that computing these types of explanations for Bayesian network classifiers (Bayesian networks used as classifiers) is NP-hard for contrastive explanations and co-NP-hard for abductive explanations. We define a number of subproblem for finding contrastive and abductive explanations. For contrastive explanations, we find that the problems of computing any contrastive explanation is already NP-hard for Bayesian networks where inference can be applied in polynomial time. We propose a number of simple algorithms that are able to solve the different subproblems by computing inference for multiple subsets of evidence. Lastly we propose an algorithm that can compute abductive and contrastive explanations more efficiently and reduces redundant calculations by looking at the internal structure and values of the Bayesian network. The algorithm solves a more general problem: finding all assignments to a given set of evidence nodes that satisfy a constraint on a hypothesis node. Finding contrastive and abductive explanations is a special case of the algorithm.