论文标题
计算必要和充分的解释
On the Computation of Necessary and Sufficient Explanations
论文作者
论文摘要
决定背后的完整原因是一个布尔公式，其特征是做出决定的原因。最近引入的概念具有许多应用程序，其中包括生成解释，检测决策偏见和评估反事实查询。完全理性的主要隐含物被称为该决定的充分原因，它们与所谓的PI解释和绑架性解释相对应。在本文中，我们将完全理由的主要含义称为决定的必要原因。我们通过语义证明了这一术语合理，并表明必要的原因与所谓的对比解释相对应。我们还研究了具有名义和数字特征的多级决策树和图形的完整原因计算，我们为此得出了有效的，封闭形式的完整原因。我们进一步研究了出于一系列完整原因的最短和充分理由的计算，其中包括派生的封闭式和句子决策图（SDD）的完整原因。我们提供了一种算法，该算法可以列举其在多项式时间内的最短理由。列举这类完全原因的最短理由，即使是出于单一的原因，也很难。对于这个问题，我们提供了一种算法，该算法在经验上似乎非常有效。
The complete reason behind a decision is a Boolean formula that characterizes why the decision was made. This recently introduced notion has a number of applications, which include generating explanations, detecting decision bias and evaluating counterfactual queries. Prime implicants of the complete reason are known as sufficient reasons for the decision and they correspond to what is known as PI explanations and abductive explanations. In this paper, we refer to the prime implicates of a complete reason as necessary reasons for the decision. We justify this terminology semantically and show that necessary reasons correspond to what is known as contrastive explanations. We also study the computation of complete reasons for multi-class decision trees and graphs with nominal and numeric features for which we derive efficient, closed-form complete reasons. We further investigate the computation of shortest necessary and sufficient reasons for a broad class of complete reasons, which include the derived closed forms and the complete reasons for Sentential Decision Diagrams (SDDs). We provide an algorithm which can enumerate their shortest necessary reasons in output polynomial time. Enumerating shortest sufficient reasons for this class of complete reasons is hard even for a single reason. For this problem, we provide an algorithm that appears to be quite efficient as we show empirically.
