Deriving Explanations for Decision Trees: The Impact of Domain Theories

We are interested in identifying the complexity of computing explanations of various types for a decision tree, when the Boolean conditions used in the tree are not independent. When a domain theory indicating how the Boolean conditions occurring in the tree are logically connected is available, taking advantage of it is important to derive provably correct explanations. In this paper, we show that leveraging such a domain theory may have a strong impact on the complexity of generating explanations. While computing a subset-minimal abductive explanation (or a subset-minimal contrastive explanation) for an instance becomes NP-hard in presence of a domain theory, tractable restrictions exist. Especially, domain theories expressing the encoding of numerical attributes into Boolean conditions lead to tractable explanation problems for contrastive explanations