Provably Precise, Succinct and Efficient Explanations for Decision Trees
This work addresses the need for interpretable and rigorous explanations in high-risk applications using decision trees, though it is incremental as it builds on existing rigorous explanation methods.
The paper tackles the problem of generating explanations for decision trees that are both succinct and provably precise, proposing methods to compute δ-relevant sets that trade off explanation size for precision, with experimental results showing practical efficiency in computing these sets.
Decision trees (DTs) embody interpretable classifiers. DTs have been advocated for deployment in high-risk applications, but also for explaining other complex classifiers. Nevertheless, recent work has demonstrated that predictions in DTs ought to be explained with rigorous approaches. Although rigorous explanations can be computed in polynomial time for DTs, their size may be beyond the cognitive limits of human decision makers. This paper investigates the computation of δ-relevant sets for DTs. δ-relevant sets denote explanations that are succinct and provably precise. These sets represent generalizations of rigorous explanations, which are precise with probability one, and so they enable trading off explanation size for precision. The paper proposes two logic encodings for computing smallest δ-relevant sets for DTs. The paper further devises a polynomial-time algorithm for computing δ-relevant sets which are not guaranteed to be subset-minimal, but for which the experiments show to be most often subset-minimal in practice. The experimental results also demonstrate the practical efficiency of computing smallest δ-relevant sets.