On the Explanatory Power of Decision Trees

Understand

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.