On Learning Sparse Boolean Formulae For Explaining AI Decisions

Susmit Jha , Vasumathi Raman, Alessandro Pinto, Tuhin Sahai, and Michael Francis. On Learning Sparse Boolean Formulae For Explaining AI Decisions, NASA Formal Methods, 2017

Download

Paper (pdf)  

Abstract

In this paper, we consider the problem of learning Boolean formulae from examples obtained by actively querying an oracle that can label examples as positive or negative. This problem has received attention in machine learning as well as formal methods, 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 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 proposed learning algorithm to automatically generate 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, and is therefore, broadly applicable and agnostic to the specific AI algorithm. We illustrate the practical effectiveness of our approach on a set of diverse case-studies.

BibTeX

To be published in Proceedings of NASA Formal Methods Symposium

 

@Inbook{Jha2017,
author="Jha, Susmit
and Raman, Vasumathi
and Pinto, Alessandro
and Sahai, Tuhin
and Francis, Michael",
editor="Barrett, Clark
and Davies, Misty
and Kahsai, Temesghen",
title="On Learning Sparse Boolean Formulae for Explaining AI Decisions",
bookTitle="NASA Formal Methods: 9th International Symposium, NFM 2017, Moffett Field, CA, USA, May 16-18, 2017, Proceedings",
year="2017",
publisher="Springer International Publishing",
address="Cham",
pages="99--114",
isbn="978-3-319-57288-8",
doi="10.1007/978-3-319-57288-8_7",
url="https://doi.org/10.1007/978-3-319-57288-8_7"
}