在实际应用中，人工智能的广泛使用引发了对系统可信度的担忧，尤其是关键领域。可解释人工智能（XAI）旨在向用户提供模型决策的解释。针对布尔分类器，文献中提出了归纳解释（abductive explanations）和对比解释（contrastive explanations），它们分别从不同角度揭示分类结果。一般情况下，计算任意布尔分类器的解释是一个计算上困难的问题。
一种常见的缓解方式是先将分类器编译成易于查询的形式，例如有序二叉决策图（OBDD），从而在该表示上快速生成解释。然而，我们证明，即使在 OBDD 这种知识编译图谱中最易处理的子类上，若干重要的归纳解释类别仍然是难以计算的，包括最短归纳解释以及考虑解释者偏好的归纳解释。
为了解决这一瓶颈，我们提出使用分类器的双轨编码的恰当编译形式。该表示能够在多项硬实例上实现归纳解释的多项式时间计算，从而恢复编译表示带来的效率优势。
点评