Efficient Search for Diverse Coherent Explanations

By Chris Russell. 2019

278 citations recorded by the source corpus.

This paper proposes new search algorithms for counterfactual explanations based upon mixed integer programming. We are concerned with complex data in which variables may take any value from a contiguous range or an additional set of discrete states. We propose a novel set of constraints that we refer to as a "mixed polytope" and show how this can be used with an integer programming solver to efficiently find coherent counterfactual explanations i.e. solutions that are guaranteed to map back onto the underlying data structure, while avoiding the need for brute-force enumeration. We also look at the problem of diverse explanations and show how these can be generated within our framework.

Subfields: Artificial Intelligence, Information Systems and Management, Ocean Engineering, Safety, Robustness & Interpretability, Algorithms & Complexity

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

In Information Systems and Management

In Ocean Engineering

In Safety, Robustness & Interpretability

In Algorithms & Complexity

Citations in the corpus

Getting a CLUE: A Method for Explaining Uncertainty Estimates (2020, background): “Multiple counterfactual explanations can exist for any given input, as the functions we are interested in explaining are often non-injective (Russell, 2019).”
Explaining machine learning classifiers through diverse counterfactual explanations (2019, background): “Concurrently, a recent paper by Russell [28] develops an efficient algorithm to find diverse counterfactuals using integer programming for linear models.”
A survey of algorithmic recourse: definitions, formulations, solutions, and prospects (2020, methodology): “In the second camp, Russell [158] pursue a strategy whereby subsequent runs of the optimizer would prevent changing features in the same manner as prior explanations/recommendations.”
A historical perspective of explainable Artificial Intelligence (2020, methodology): “Soon after, the importance of diversity also in counterfactuals was acknowledged by (Russell, 2019), who correspondingly proposed a method to generate diversified counterfactuals for linear models.”
FACE: Feasible and Actionable Counterfactual Explanations (2019, unknown): “Russell [16] propose a Mixed Integer Programming (MIP) formulation to handle mixed data types to offer counterfactual explanations for linear classifiers that respect the original data structure.”
A Survey on the Explainability of Supervised Machine Learning (2020, background): “Russell (2019) proposes coherent counterfactual explanations for mixed data sets and proposes a concrete method for generating diverse counterfactuals based upon mixed integer programming.”
Counterfactual Explanations for Machine Learning: A Review (2020, background): “ able to generate multiple counterfactuals (generally diverse by some metric of diversity) for a single input datapoint, therefore they require to be run once per input to get several counterfactuals [26, 47, 57, 64, 82, 85, 95, 98]. Mahajan et al. [82]’s approach learns the mapping of datapoints to”
A Survey of Contrastive and Counterfactual Explanation Generation Methods for Explainable Artificial Intelligence (2021, methodology): “Alternatively, counterfactuals are viewed as ‘‘solutions that are guaranteed to map back onto the underlying data structure’’ [153].”
FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles (2019, methodology): “Counterfactual examples have been used in a variety of ML areas, such as reinforcement learning [23], deep learning [1], and explainable AI (XAI) [8, 13, 17, 18, 22, 24, 26, 28, 31, 35, 36].”
A comparison of instance-level counterfactual explanation algorithms for behavioral and textual data: SEDC, LIME-C and SHAP-C (2019, background): “) [53, 9, 45].”
Multi-Objective Counterfactual Explanations (2020, methodology): “Like many model-specific methods [15,20,24,28,33] their approach is limited to differentiable models.”
CERTIFAI: A Common Framework to Provide Explanations and Analyse the Fairness and Robustness of Black-box Models (2019, methodology): “As promising as the original method [15] and subsequent methods of generating counterfactuals [13, 14] are, they are also limited in that some only work for linear models, while others cannot deal with different data types.”
Preserving Causal Constraints in Counterfactual Explanations for Machine Learning Classifiers (2019, methodology): “Most CF generation methods rely on separate optimizations for each input, based on original features [16, 7], a latent representation [17], or using a generative adversarial network [18].”
The philosophical basis of algorithmic recourse (2020, background): “Counterfactual explanations have proven to be a popular framework for generating explanations[18, 29].”