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.
翻译:决策树(DTs) 包含可解释的分类。 DTs 已被提倡用于高风险应用, 但也被提倡用于解释其他复杂的分类。 然而,最近的工作表明, DTs 的预测应该以严格的方法加以解释。 虽然可以用多角度来为DTs计算严格的解释, 但其尺寸可能超出人类决策者的认知限度。 本文调查了与DTs 有关的 & delta} 数据集的计算方法。 $ delta} 相关数据集代表了简明和精确的解释。 这些数据集代表了严格解释的概略, 精确的概率是1, 因而能够将解释的大小转换为精确性。 该文件为DTs 的最小 {delta} 相关数据集提出了两种逻辑编码。 该文件进一步设计了计算 $delta} 相关数据集的多元时间算法, 这些计算方法不能保证是子- 最小的, 但实验结果显示在实践中最常见的子- 。 实验结果还表明计算最小 {delta} 相关数据集的实际效率。