Good Counterfactuals and Where to Find Them: A Case-Based Technique for Generating Counterfactuals for Explainable AI (XAI) | Keane & Smyth, 2020
Counterfactuals (CGs) have potential because:
- "technically, these counterfactual cases can be generated by permuting problem-features until a class-change is found" (1)
- "psychologically, they are much more causally informative than factual explanations" (1)
- "legally, they are GDPR-compliant"
But finding good counterfactuals is hard, e.g. CFs that have sparsity and plausibility.
Their proposal uses analogical reasoning from a given case-base of good counterfactuals:
We propose a new case-based approach for generating counterfactuals, using novel ideas about the counterfactual potential and explanatory coverage of a case-base. The new technique re- uses patterns of good counterfactuals, present in a case-base, to generate analogous counterfactuals that can explain new problems and their solutions. (1)
Approach:
- Case-based reasoning systems can already easily produce counterfactual explanations
- This is more tricky where an opaque ML model is involved, e.g. a neural network
- Here predictions "have to be explained by finding case-based explanations from a twinned CBR system." (2)
- The main author has a paper publication on this twin-approach
- "In this context, we assess how many “good” counterfactuals are available in a given case-base (i.e., ones that are easily comprehended by people). So, we systematically map the topology of “good” counterfactuals in different case-bases, what we call their counterfactual potential (see section 2)." (2)
- In most case-bases there are not really "good" counterfactuals
- "This leads us to the novel notion of explanatory coverage by analogy to predictive coverage [22, 23, 24], from which we develop and evaluate a new case-based technique for counterfactual generation in XAI" (2)
Counterfactual Explanation: Promise, Problems & Prospects
Promise: good section; but no notes.
Problems: 1. prolixity 2. sparsity 3.plausibility.
Prolixity
Prolix: very long, drawn out. A problem with CF generation algorithms is that many CFs may be produced; but which one is best? It is not useful to throw 1000 CFs as a human to explain a prediction. To tackle this, methods try to find a CF that switches the system output while making minimal changes to features (see sparsity) E.g. see the paper by Wachter et al. Mothilal et al. (2019) additionally try to give more diverse CFs.
Sparsity
The authors consistently write "sparcity" but I've never seen that spelling.
Modify the fewest amount of features.
Working definition: "good" CFs have <= 2 feature changes.
"This definition allows us to develop the novel idea of the counterfactual potential of case-bases, based on quantifying the “good” counterfactuals they contain" (4)
Plausibility
The proposed CFs should be valid data points given domain and causal constraints. E.g. if you are refused a loan, it is completely useless to hear "You would have received the loan if you earned a million dollars more"; or tell a woman that her changes would be better if she changed her gender to male.
This problem is the least solved and is the focus of this paper's contribution.
Here, we propose that, rather than generating counterfactuals by “blind” random perturbation, an XAI system should use the training-data/case-base to find suitable counterfactuals; as these counterfactuals are “real experiences” from the problem domain, they have an inherent plausibility. (5)
(As a sidenote, modern CF methods do not just "blindly" generate CFs, but e.g. use gradient information to do a smarter directed search for CFs by framing it as an optimization problem).
This approach is very intuitive to me! However, this does assume that such good CFs are available in the case base:
However, this leads us to another question: namely, how many good counterfactuals are “naturally” available in case-bases or, more simply, what is their counterfactual potential. (5)
This potential can be determined by computing the feature-differences in all pairwise comparisons of cases in the case-base. If these comparisons show there are many “good” counterfactuals then the potential is high, if not then it is low. (5)
Experiment 1: Plotting Counterfactual Potential
For 20 datasets. Does this method even factor in a change in class label? It seems to consider all pairs of cases, also the ones with the same class?
Ah no, not true: "We compared all pairings of test cases (one side of a decision boundary) to training cases (on the other side of a decision boundary) calculating the the number of feature differences found in each." (6)
-> Notice the "the the"? It's on a linebreak. I read this cool post by Matt Might about how we are blind to this mistake, and that he runs scripts to filter this specific mistake out of his texts. I actually found it again: Matt Might calls it the "lexical illusion": https://matt.might.net/articles/shell-scripts-for-passive-voice-weasel-words-duplicates/
Ok so something that's good to notice here is that CF-generation methods typically construct hypothetical scenarios. In this case, they check whether there are non-hypothetical actual counterfactual cases in the case base (which could be the basis for further generation of "hypothetical" counterfactuals).
Turns out all datasets have <1% "good" counterfactuals, most none.
Case-based technique for good counterfactuals
So the first results actually suggest that a case-based approach does not show that much promise, because the case base has a very limited amount of "good" counterfactuals.
Perhaps this explains why the dominant technique in the literature uses perturbation, where synthetic counterfactuals are generated “blindly” from problem-cases and labelled using the available machine-learning model, without reference to other known cases in the training set [21, 30, 43, 44, 45, 46]. In contrast to these approaches, we believe that counterfactuals need to be explicitly grounded in known cases (aka the training data), to ensure plausibility.
Explanatory Competence
Just as the fundamental unit of (predictive) competence is a relation of the form solves(c, c') to indicate that case/example c can be used to solve some target/query c', so too the basic unit of explanatory competence is explains(c, c') indicating that some case c can be used to explain the solution of c'; in this work, the explanatory cases (c) are the counterfactuals of c'. Accordingly, the explanatory competence of a case-base C can be represented by a coverage set (Eq. 1) and degree of explanatory competence can be estimated as the size of the coverage set as a fraction of the case-base (Eq. 2). (8)
When assessing the counterfactual potential a strict criterion of <= feature changes was used. If you slightly relax this with a tolerance for what counts as "similar", you find way more cases that can serve as explaining cases.
A pairing of a case with a good counterfactual (so a symmetric relation) is called an "explanation case" (XC) in this paper (8).
Each XC is associated with a set of match-features (m), the features that are the same between the query and counterfactual (using a specified tolerance), and a set of difference-features (d), the ≤2 features that differ between the query and counterfactual. (8)
This should improve the "explanatory competence". I guess the point of the matching tolerance is that this allows generation of good counterfactuals in the local neighbourhood of existing good counterfactuals.
So the main difference with explanatory competence and the counterfactual potential is that the latter expresses the baseline explanatory competence that occurs "naturally" in a data set.
Explanation of Case-based approach
We have a new case p for which we want to find a counterfactual p'.
- Identify XC case xc(x, x') whose query is most similar to p
- Query is a "query case" right? So just find the most similar case with the same label from the case base.
- Because x' is a good counterfactual for x, and p is similar to x, we expect x' to also be a decent starting point as a counterfactual for p.
- Note that the difference between x and x' is determined by the difference features
- In order to construct counterfactual p' for p, we should therefore look to adjust the difference features of xc(x, x')! This is a type of analogical reasoning, I reckon.
- Construct new counterfactual p'
- For the match features of xc(x, x'), copy the values of p to p'
- For the difference features of xc(x,x'), take the values of x' instead into p'.
- This guarantees no more than two features are changed and that thus by construction p' is a "good" counterfactual to p (according to the authors definition)
- This does not yet guarantee p' is a valid counterfactual, because the class label may be the same. Get the class label for the new hypothetical case p' by running it through your ML classifier. If it is a different class, use p' as the CF. If it is not, run the following adaptation step.
- Adapt the proposed CF by adjusting the value of the difference features
- The authors do not want to adjust the match features because then, by their definition, the counterfactual will change more features and be "bad".
- Option is to perturb feature values in a smart way until their is a class change
- Strategy from authors is 1) iterate over nearest neighbours of old proposed CF p' until you find one with a class change and 2) use the difference features of this neighbour for p'.
- Fails if none of the nearest neighbours produce a class change
I have summarized a bit and my summary has less bullet points, just FYI.
In the results section, they actually sneakily introduce another method called "closest" which picks the CF with closest distance to query, if both the reuse ánd adaptation step produce a good counterfactual.
Advantages of this approach:
- "Note that the primary contribution of explanation cases is to identify and distinguish between common combinations of features (match-features and difference-features) that tend to participate in good counterfactuals. Depending on the domain this may reflect some important relationships (causal or otherwise) that exist within the feature-space. In other words, the XCs tell us about which features should be changed (or held constant) when generating new counterfactuals in the feature space near a query case." (10)
- Because the CF values are based on real cases, the resulting CFs should be more plausible
- The adaptation step may be useful even if a good CF is found, because the resulting adapted (hypothetical) CF may be closer to the decision boundary as well
In a multi-class scenario, you could adapt to just an other class.
Evaluating Explanation Competence
See graph. But for most data sets results follow a similar pattern. The baseline explanatory competence is quite low, on average 11% with tolerance. Average for retrieving and reusing cases: 40%. With the adaptation step, coverage is on average around 94%! So this means that the method works even if the counterfactual potential is very low originally.
The quality of the explanation is measured by a proxy of relative counterfactual distance.
we can use the distance between the query and the generated counterfactual as a proxy for the utility of the explanation, on the grounds that counterfactuals which are closer to a query are more likely to serve as more useful explanations. Since counterfactual distance will vary from dataset to dataset, reflecting the nature of the feature space, in this analysis we present a relative counterfactual distance (RCF) measure by dividing the counterfactual distances of the synthetic counterfactuals by the baseline counterfactual distance for the dataset. Thus, if RCF>1, then it indicates that the synthetic counterfactual is farther from the query that the average baseline counterfactual distance. (12)
Readings on case-based reasoning and explainability
- Leake, D.B.: CBR in context: The present and future. Case-based reasoning: Experiences, lessons, and future directions, pp.3-30 (1996)
- Kolodner, J.: Case-based reasoning. Morgan Kaufmann (2014)
- Leake, D. and McSherry, D.: Introduction to the special issue on explanation in case-based reasoning. Artificial Intelligence Review, 24(2), 103-108 (2005)
- Schoenborn, J. M., & Althoff, K. D. Recent Trends in XAI: A broad overview on current approaches, Methodologies and Interactions. In Case-Based Reasoning for the Explanation of intelligent systems (XCBR) Workshop (2019).
On black box systems:
- Kenny, E.M. and Keane, Mark T.: Twin-systems to explain neural networks using case-based reasoning. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI-19) pp. 326-333 (2019)
- Keane, M. T., & Kenny, E. M.: How Case-Based Reasoning Explains Neural Networks. In Bach, K., Marling, C.(eds.). Case-based reasoning research and development: 27th International Conference (ICCBR-19) Otzenhausen, Germany,.Springer, Berlin (2019)
- Nugent, C., and Cunningham, P.: A case-based explanation system for black-box sys- tems. Artificial Intelligence Review, 24(2), 163-178 (2005)