Explaining AI Decisions Using Efficient Methods for Learning Sparse Boolean Formulae
Explaining AI Decisions Using Efficient Methods for Learning Sparse Boolean Formulae
复制标题
使用学习稀疏布尔公式的有效方法解释人工智能决策
DOI：
10.1007/s10817-018-9499-8
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Francis, Michael
中科院分区：
文献类型：
--
作者：
Jha, Susmit;Sahai, Tuhin;Raman, Vasumathi;Pinto, Alessandro;Francis, Michael
在本文中，我们考虑的问题，学习布尔公式的例子，通过积极查询的甲骨文，可以标记这些例子，无论是积极的或消极的。这个问题在机器学习和形式化方法社区都受到了关注，并且在一般情况下以及许多限制条件下，它已被证明具有指数最坏情况复杂度。在本文中，我们专注于learningsparseBoolean公式只依赖于一个小的（但未知的）子集的整体词汇的原子命题。我们提出了两个算法，第一，基于二分搜索的汉明空间，第二，基于随机行走的布尔超立方体，学习这些稀疏布尔公式与给定的信心。这种稀疏性假设的动机是挖掘人工智能（AI）算法所做决策的解释问题，其中对单个决策的解释可能取决于算法所有输入的一个小但未知的子集。我们展示了使用这些算法自动生成这些决定的解释。这些解释将使智能系统对人类用户更容易理解和负责，便于更容易的审计，并在故障情况下提供诊断信息。所提出的方法将AI算法视为黑盒预言机，因此，它对特定的AI算法具有广泛的适用性和不可知性。我们表明，这两个算法所需的例子的数量只增长与原子命题的词汇量的大小几何。我们说明了我们的方法在不同的案例研究的实际效果。
In this paper, we consider the problem of learning Boolean formulae from examples obtained by actively querying an oracle that can label these examples 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 learningsparseBoolean formulae which depend on only a small (but unknown) subset of the overall vocabulary of atomic propositions. We propose two algorithms—first, based on binary search in the Hamming space, and the second, based on random walk on the Boolean hypercube, 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 these algorithms 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 show that the number of examples needed for both proposed algorithms only grows logarithmically with the size of the vocabulary of atomic propositions. We illustrate the practical effectiveness of our approach on a diverse set of case studies.
登录
查看更多内容
基于马尔可夫决策过程生成解释
DOI：
--
发表时间：
2009
期刊：
Mexican International Conference on Artificial Intelligence
影响因子：
--
作者：
F. Elizalde;L. Sucar;J. Noguez;A. Reyes
通讯作者：
A. Reyes
从反应式程序的动态观察中自动合成规范
DOI：
--
发表时间：
1997
期刊：
International Conference on Tools and Algorithms for Construction and Analysis of Systems
影响因子：
--
作者：
Bernard Boigelot;Patrice Godefroid
通讯作者：
Patrice Godefroid
贝叶斯网络中最相关的解释
DOI：
10.1613/jair.3301
发表时间：
2011
期刊：
J. Artif. Intell. Res.
影响因子：
--
作者：
Changhe Yuan;Heejin Lim;Tsai
通讯作者：
Tsai
关于学习稀疏布尔公式来解释人工智能决策
DOI：
--
发表时间：
2017
期刊：
NASA Formal Methods
影响因子：
--
作者：
Susmit Jha;Vasumathi Raman;Alessandro Pinto;T. Sahai;Michael Francis
通讯作者：
Michael Francis
通过查询修正理论：Horn、只读一次和奇偶校验公式
影响因子：
14.4
作者：
J. Goldsmith;R. Sloan;Balázs Szörényi;György Turán
通讯作者：
György Turán