Abduction-Based Explanations for Machine Learning Models

By Alexey Ignatiev, Nina Narodytska, Joao Marques-Silva. 2018

307 citations recorded by the source corpus.

The growing range of applications of Machine Learning (ML) in a multitude of settings motivates the ability of computing small explanations for predictions made. Small explanations are generally accepted as easier for human decision makers to understand. Most earlier work on computing explanations is based on heuristic approaches, providing no guarantees of quality, in terms of how close such solutions are from cardinality- or subset-minimal explanations. This paper develops a constraint-agnostic solution for computing explanations for any ML model. The proposed solution exploits abductive reasoning, and imposes the requirement that the ML model can be represented as sets of constraints using some target constraint reasoning system for which the decision problem can be answered with some oracle. The experimental results, obtained on well-known datasets, validate the scalability of the proposed approach as well as the quality of the computed solutions.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Computing Optimal Decision Sets with SAT (2020, background): “Hence the rising interest in explainable artificial intelligence (XAI) [4, 14, 16, 18, 22, 23, 26, 29, 30, 36–38, 42, 43, 48, 49, 52], including research programs [3, 24] and legislation [17, 21].”
On Explaining Decision Trees (2020, methodology): “ndancy.Hence, we need at most m calls to an NP oracle to decide explanation-redundancy,where m is the number of features. (This high-level procedure was proposed in earlier work in more general terms [29].) However, the special structure of a DT, makes the problem far simpler, and can be solved in p”
On Relating Explanations and Adversarial Examples (2019, methodology): “Given some target prediction π ∈ K, one can devise representations for the formula FM,π , (M→π) [52, 23].”
Globally-Consistent Rule-Based Summary-Explanations for Machine Learning Models: Application to Credit-Risk Evaluation (2019, unknown): “The only example in the literature that does not seem to suffer the same problems as the above works is that of Ignatiev et al. (2019), done in parallel to our work (see Rudin and Shaposhnik 2019, for an earlier version of this manuscript).”
Three Modern Roles for Logic in AI (2020, background): “Another set of ,butusingSAT-basedtechniquesinsteadofcompilingintotractablecircuits;see,e.g.,[39,40,43,48,58,82,84]. the average decision robustness (over all possible instances) [80].”
Towards Trustable Explainable AI (2020, methodology): “Recent work [ Shih et al. , 2018; Ignatiev et al. , 2019a ] proposed a principled approach to computing provably correct explanations (at the expected cost of lower scalability), which is fundamentally different from the heuristic methods.”