On the Explanatory Power of Decision Trees
  Decision trees have long been recognized as models of choice in sensitive
applications where interpretability is of paramount importance. In this paper,
we examine the computational ability of Boolean decision trees in deriving,
minimizing, and counting sufficient reasons and contrastive explanations. We
prove that the set of all sufficient reasons of minimal size for an instance
given a decision tree can be exponentially larger than the size of the input
(the instance and the decision tree). Therefore, generating the full set of
sufficient reasons can be out of reach. In addition, computing a single
sufficient reason does not prove enough in general; indeed, two sufficient
reasons for the same instance may differ on many features. To deal with this
issue and generate synthetic views of the set of all sufficient reasons, we
introduce the notions of relevant features and of necessary features that
characterize the (possibly negated) features appearing in at least one or in
every sufficient reason, and we show that they can be computed in polynomial
time. We also introduce the notion of explanatory importance, that indicates
how frequent each (possibly negated) feature is in the set of all sufficient
reasons. We show how the explanatory importance of a feature and the number of
sufficient reasons can be obtained via a model counting operation, which turns
out to be practical in many cases. We also explain how to enumerate sufficient
reasons of minimal size. We finally show that, unlike sufficient reasons, the
set of all contrastive explanations for an instance given a decision tree can
be derived, minimized and counted in polynomial time.
