Provably Precise, Succinct and Efficient Explanations for Decision Trees
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 {\delta}-relevant sets for DTs.
{\delta}-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 {\delta}-relevant sets for DTs. The paper further devises a
polynomial-time algorithm for computing {\delta}-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 {\delta}-relevant sets.