On Learning Sparse Boolean Formulae for Explaining AI Decisions
On Learning Sparse Boolean Formulae for Explaining AI Decisions
复制标题
关于学习稀疏布尔公式来解释人工智能决策
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Michael Francis
中科院分区：
文献类型：
--
作者：
Susmit Jha;Vasumathi Raman;Alessandro Pinto;T. Sahai;Michael Francis
在这篇文章中，我们考虑了从通过主动查询可以将这些例子标记为正或负的先知而获得的例子中学习布尔公式的问题。这个问题在机器学习和形式化方法领域都受到了关注，并且在一般情况下以及在许多限制下，它被证明具有指数最坏情况的复杂性。在本文中，我们专注于学习稀疏布尔公式，这些公式只依赖于原子命题总词汇表中的一小部分(但未知)。我们提出了一个有效的算法来学习这些给定置信度的稀疏布尔公式。这种稀疏性假设的动机是挖掘人工智能(AI)算法做出的决策的解释问题，其中对个别决策的解释可能依赖于算法所有输入的一小部分但未知的子集。我们演示了我们的算法在自动生成这些决策的解释中的使用。这些解释将使智能系统对人类用户更容易理解和负责，便于更容易的审计，并在故障情况下提供诊断信息。该方法将人工智能算法视为一个黑盒预言，具有广泛的适用性和对特定人工智能算法的无关性。我们在一系列不同的案例研究中展示了我们方法的实际有效性。
In this paper, we consider the problem of learning Boolean formulae from examples obtained by actively querying an oracle that can label these examplesz as either positive or negative. This problem has received attention in both machine learning as well as formal methods communities, and it has been shown to have exponential worst-case complexity in the general case as well as for many restrictions. In this paper, we focus on learning sparse Boolean formulae which depend on only a small (but unknown) subset of the overall vocabulary of atomic propositions. We propose an efficient algorithm to learn these sparse Boolean formulae with a given confidence. This assumption of sparsity is motivated by the problem of mining explanations for decisions made by artificially intelligent (AI) algorithms, where the explanation of individual decisions may depend on a small but unknown subset of all the inputs to the algorithm. We demonstrate the use of our algorithm in automatically generating explanations of these decisions. These explanations will make intelligent systems more understandable and accountable to human users, facilitate easier audits and provide diagnostic information in the case of failure. The proposed approach treats the AI algorithm as a black-box oracle; hence, it is broadly applicable and agnostic to the specific AI algorithm. We illustrate the practical effectiveness of our approach on a diverse set of case studies.