We propose a framework for generating counterfactual explanations of black-box classifiers, which answer the question “What has to change for this to be classified as X instead of Y?” in terms of given domain knowledge. Specifically, we identify minimal and meaningful “concept edits” which, when applied, change the prediction of a black-box classifier to a desired class. Furthermore, by accumulating multiple counterfactual explanations from interesting regions of a dataset, we propose a method to estimate a "global" counterfactual explanation for that region and a desired target class. We implement algorithms and show results from preliminary experiments employing CLEVR-Hans3 and COCO as datasets. The resulting explanations were useful, and even managed to unintendedly reveal a bias in the classifier's training set, which was unknown to us.
have a whole spectrum of plausible combinations as answers. The algorithm’s goal is to find
the one requiring the least amount of change, customized for that particular situation, while
also being feasible and actionable in the real world. A key element of counterfactuals is their
reliance on notions of distance and similarity [
There are many approaches to counterfactual explanations in recent literature. Poyiadzi et al.
[
The majority of AI today is data-driven, sub-symbolic machine learning. Models tend to be
convoluted, algebraic matrices that are dificult for humans to interpret. Knowledge graphs
[
To our knowledge, we are the first to explore global counterfactual explanations. • We propose and implement algorithms for generating explanations in this context, and show results from preliminary experiments.
For describing concepts and the relationships between them we use the notation from description
logics [
An overview of our framework is shown in Figure 1. In order to generate explanations for a
black-box classifier, we need a terminology in terms of which we express the explanations, in
addition to a set of testing items for the classifier. Specifically, we need a dataset, where for each
sample we require: a) features which can be fed to the classifier, and b) a semantic description of
the sample in the form of a set of concepts, in terms of which we will provide the explanations.
In the general case, this set of concepts is linked to external knowledge, in the form of a TBox.
Definition 1 (Explanation Dataset). Let : → [
Given an explanation dataset, we can answer the question “What has to change in order to be classified as X instead of Y? ” in terms of concepts (), instead of features (). In many cases, this leads to more intuitive explanations, especially in cases in which is sub-symbolic raw data (pixels, audio signals, etc), and is linked to useful knowledge. More specifically, the explanations which we generate will have the form of edits on a set of concepts, where the cost of each edit is determined by the distance between concepts in the TBox graph. Definition 2 (Concept Distance). Let CN be a set of atomic concepts, be a TBox for CN, and be the corresponding undirected TBox graph. The distance from concept A to concept B, where A, B ∈ CN ∪ {⊤} is defined as the length of the shortest path on from the vertex A to the vertex B, where A, B are the vertices corresponding to atomic concepts A, B. We write (A, B) to denote concept distance.
For example if we were given the TBox {Cat ⊑ Mammal, Dog ⊑ Mammal, Ant ⊑ Insect, Mammal ⊑ Animal, Insect ⊑ Animal}, then the concept distance from Cat to Dog would be 2, with the path on being Cat → Mammal → Dog. The concept distance from Cat to Ant would be 4 with the shortest path being Cat → Mammal → Animal → Insect → Ant. Finally, the concept distance from Cat to ⊤ would be 3 with the path Cat → Mammal → Animal → ⊤.
We will use the notion of concept distance for assigning cost to edit operations on sets of concepts. These edit operations will end up being part of the counterfactual explantions. Definition 3 (Concept Set Edit). Let CN be a set of atomic concept names, be a TBox for CN, and ⊆ CN be a set of concepts. A concept set edit on is any of: • Replacement of concept A ∈ with concept B ̸∈ . We write A→B() to denote replacement of A from with B. • Deletion of concept A ∈ from . We write A→⊤() to denote deletion of A from . • Insertion of concept B ̸∈ into . We write ⊤→B() to denote insertion of B into The cost of a concept set edit → is defined as the concept distance from to : (, ), where , ∈ CN ∪ {⊤}. The resulting set of concepts →() is called a transformation of .
As mentioned in Section 2, we allow for the assignment of positive weights to the undirected TBox graph. This is done to allow for the incorporation of additional constraints to better reflect the actionability and feasibility of changes in the real world. In this work, we do not systematically do this, as we consider it to be given. For example for a given application, it might be useful to make the deletion of an Animal concept (Animal→⊤) more costly than the replacement of a Cat concept with a Mammal concept (Cat→Mammal), so we would appropriately tweak the edge weights of the undirected TBox graph.
As is apparent from the notation →, we treat the deletion of concept A from a set as if being equivalent to its replacement with the universal concept ⊤, while the insertion of concept B is treated as if replacing a ⊤ concept with B. This entails that inserting or deleting a concept is more costly the further away it is from the ⊤ vertex in the TBox graph, which is a measure of how specific the concept is. Continuing the previous example, given a set , then inserting a Cat concept into the set would have a cost of (⊤, Cat) = 3, while inserting an Animal concept into the set would have a cost of (⊤, Animal) = 1. Using the concept set edit, we can define a concept set edit distance between sets of concepts, as the minimum cost of a set of concept set edits which when applied to the first set of concepts, transform it into the second. Definition 4 (Concept Set Edit Distance). Let CN be a set of concept names, be a TBox on CN and , ℬ be sets of concepts , ℬ ⊆ CN. The concept set edit distance from to ℬ is defined as the minimum cost of a set of concept edits which transform into ℬ.
Intuitively, the concept set edit distance represents the minimum cost of converting every concept present in the first set, into every concept present in the second. For example, given two sets of concepts = {Cat, Insect} and ℬ = {Animal}, and the TBox from the previous example, then their concept set edit distance will be (, ℬ) = min{[ (Cat, Animal) + (Insect, ⊤)], [ (Cat, ⊤) + (Insect, Animal)]} = min {(2 + 2), (3 + 1)} = 4.
In the context of our framework, the concept set edit distance is used to measure how conceptually similar two elements of an explanation dataset are and is one of the two key components for generating counterfactual explanations. The second component involves the black-box classifier which we want to explain. Specifically, we want counterfactual explanations to represent small conceptual changes (small concept set edit distance) which lead to large changes in the output of the classifier. For this reason, we define the significance of transforming an element of an explanation dataset into another.
Definition 5 (Significance of Transformation). Let be a classifier, be a TBox and = (, ), = (, ) be two elements of an explanation dataset for . The significance of transforming into is defined as: (, ) = | ()− ()| (,)
Significance of transformations is the measure we use to determine what constitutes a good
counterfactual explanation. The local explanations will have the form of a sequence of samples
of the explanation dataset (similarly to the approach by Poyiadzi et al. [
Definition 6 (Local Counterfactual Explanation). Let = {, } be an explanation dataset for a classifier , and = (, ) be a directed graph, where there is a 1-1 correspondence between elements of and the set of vertices . The set of edges contains an edge of weight 1/ (, ) for every ordered pair of elements , ∈ . Each edge (, ) also has as a label a sets of concept set edits which optimally transform into . A counterfactual explanation from element to a class is a path from the node corresponding to to any element for which ( ) = . Counterfactual explanations corresponding to a shortest path from to any are called optimal counterfactual explanations.
The shorter the distance of a path corresponding to a local counterfactual explanation, the better the explanation is considered since short distances represent significant transformations.
Finally, besides acquiring a local explanation on how a single sample should be changed for it to be classified in a specific class, we are also concerned with more general explanations which give us an overview of which type of edits are more likely to lead towards being predicted as a specific class, given a generalization of the initial sample. For example, a counterfactual explanation for a PhD student who is also a musician and was declined a loan might not be informative enough. This extension to global explanations would be able to answer the question “What do musicians usually change to have their loan accepted” and “What do PhD students usually change to have their loan accepted”, which combined with its local explanation might be useful for the user to better understand why the black-box is making these decisions. Definition 7 (Region of Explanation Dataset). Let CN be a set of concept names, be a set of concepts ⊆ CN, and = {, } be an explanation dataset. A region of with description is the subset ⊆ of the explanation dataset for which: (, ) ∈ ⇐⇒ ∀1 ∈ , ∃2 ∈ : 2 ⊑ 1
A region of an explanation dataset is a subset of it which satisfies specific constraints, it is essentially a query. For example given a region description = {Animal}, then the region will contain any samples (, ) of the explanation dataset which in their semantic description contain any concept which is included in Animal according to the TBox. Generalized counterfactual explanations will then be statistical measures on all optimal local counterfactual explanations from elements of a region. Specifically, they will measure how often a concept is introduced (either via replacement or insertion) and subtract how often they are removed. Definition 8 (Generalized Counterfactual Explanation). Let be a region of an explanation dataset, and be the multi set containing the labels of optimal local counterfactual explanations from each element of to the desired class. Given a set of concepts ⊆ CN, a generalized counterfactual explanation is an assignment of importance to every concept C ∈ . , where the importance of a concept C is defined as: |{→C∈ }|−|{ C→∈ }| , where ∈ CN ||
For example consider an explanation dataset for a classifier which determines if an image depicts a bedroom or a veterinarian’s ofice . A region of this explanation dataset with a description of {Animal} might contain three elements: (1, {Cat, Dog}), (2, {Insect}), (3, {Human, Sofa}). Let the first image be classified as veterinarian’s ofice , while the other two are classified as bedroom. The optimal local counterfactual explanations from each element to the class veterinarians ofice might have labels: 1 = ∅ (since 1 is already classified in the desired class), 2 = {⊤→Human, Insect→Cat} and 3 = {Human→Cat, Sofa→⊤}. Then the multiset containing the labels of all optimal counterfactual explanations will be = {⊤→Human, Insect→Cat, Human→Cat, Sofa→⊤}. Then, a generalized counterfactual explanation for this region would be: a) Cat with importance 23 = 23 − 1 .0N,be)gIantsievcetiamnpdoSrotafancweitinhdimicaptoerstatnhcaet − 13 = 0 − 13 , and c) Human with importance 0 = 13 − 3 the concept is usually removed, while positive importance that it is introduced.
For generating the proposed counterfactual explanations in practice, we need a classifier , an explanation dataset , and a TBox . There are three steps to computing explanations. The ifrst step is to create the graph mentioned in Definition 6, the second step is to find appropriate paths in this graph, and the third step (only for generalized counterfactual explanations) is to accumulate these paths and compute importance (from Definition 8). We show an outline of how we create the graph in Algorithm 1. For computing the concept distance between two concepts we find the shortest path on the undirected TBox graph using Dijkstra’s algorithm with a complexity of (|CN| + | | log |CN|). For computing Concept Set Edit Distance (Definition 4) from set of concepts to set of concepts ℬ, we first remove common elements from both sets, then we create a bipartite graph in (|||ℬ|), where each element of is connected with an edge to all elements of ℬ with a weight for each edge corresponding to the concept distance, and then we compute the minimum weight full matching of the bipartite graph by using an implementation of Karp’s algorithm[30] for the problem with a time complexity of (|||ℬ| log |ℬ|). Thus, to create the graph with Algorithm 1, the total time required will end up being (( + log )42 log ), where = |CN|, is the maximum cardinality of a set of concepts, is the size of the explanation dataset and is the size of the TBox. The creation of this graph is only done once per explanation dataset and TBox. To then compute local counterfactual explanations (Definition 6), we use Dijkstra’s algorithm to find the shortest path, on the already constructed graph (including edge costs and labels) 1.
The experimental objective we found was most in tune with counterfactual explanations was to
test a classifier for biases. For example, if we trained a classifier on a set of images that included
a "grey cube" in all the images of a specific class, would our counterfactual explanation result in
an "add a grey cube" answer when asked how should we alter an image for it to belong in that
class? This is precisely what we did with the CLEVR-Hans3 [
The goal when experimenting with this dataset was twofold. First, we observe some image
sequences representing local counterfactuals (ignoring the edit labels), to compare the results
with results generated by the implementation provided for FACE [
end Algorithm 1: Explanation Graph Construction
Data: A classifier , an explanation dataset , an undirected TBox Graph Result: Explanation Graph //the explanation graph will have a node for each element in the explanation dataset Initialize Directed Graph = ( = , = ∅); foreach (, ) ∈ do foreach (, ) ∈ ∖ {(, )} do
Initialize Graph = ( = ∪ , = ∅); foreach ∈ do foreach ∈ do //Compute concept distance using TBox graph (, ) = |ShortestPath( , , )| //Add an edge to with weight = ∪ {(, , )} end //Compute minimum weight full matching of the bipartite graph {(, )}, = MinFullMatch( ) //Concept Set Edit Distance (, ) = //Compute inverse significance
1 (,) (,) = | ()− ()| //Add an edge to the explanation graph with weight 1 and as a label the edits corresponding to the minimum weight full match
1 = ∪ {(, , (,) , {→ })} end end return G 5.1.1. Setting CLEVR-Hans3 is a dataset of images of sets of 3D geometric shapes which are split into three classes. For each image, information is provided regarding the objects which are present concerning their shape (Sphere, Cube, Cylinder), their size (Large, Small), their material (Metallic, Rubber) and their color (Blue, Yellow, Brown, Grey, Green, Purple, Cyan, Red). The three classes contain images that depict: a) a Large Cube and a Large Cylinder, b) a Small Metal Cube and a Small Sphere, and c) a Large Blue Sphere and a Small Yellow Sphere. Furthermore, the first two classes are confounded in the training set, with an intentionally added bias. For the first class, in the training set, the Large Cube is always Grey, while in the test set the color of the Large Cube is random. For the second class, the material of the Small Sphere is Metal in the training set, while in the test set the material of the Small Sphere is random. This means that we expect classifiers trained on the training set to be biased towards the confounding factor. As a classifier we trained a resnet34 [ 31] model which achieved 99% accuracy on the validation set (which is confounded), while for the test set the per-class F1 scores were class 0: 0.27, class 1: 0.54, class 2: 0.92. As expected the performance is poor for the confounded classes.
We created two explanation datasets, one from the training set (in order to be compared with
FACE which is intended to be run on the training set), and one from the test set in order to
attempt to detect the biases acquired in training. As a set of concept names CN, we defined a
concept for every combination of shape, size, material, and color (including the absence of any
of the above), leading to |CN| = 4 × 3 × 3 × 9 = 324. As a TBox, we added an inclusion axiom
from each concept in CN to any other concept with the same description where one element is
missing. For example GrayCube ⊑ Gray and GrayCube ⊑ Cube. This way we assigned sets of
concepts to each element in the dataset, based on the descriptions provided by the creators of
the dataset in the corresponding json files.
5.1.2. Local Counterfactuals
In Figure 2 we show local counterfactual explanations generated for three randomly selected
images (first column) which were classified in class 1 (Small Metal Cube, Small Sphere - where
the Small Sphere is always Metal only in the train set) with the target class being class 0
(Large Cube, Large Cylinder, where the Large Cube is always Grey only in the train set), at
ifrst using the FACE algorithm [
A first observation is that the bias of the classifier is immediately detected for the confounded
class 0. As mentioned previously, the confounding factor for class 0 is that the Large Cube
is always Grey in the train set. This is apparent from the first three bars of the plot on the
left, where the most important insertions seem to be the concepts: (Gray, GrayLargeCube,
GrayLarge). The reason for which GrayLargeCube has a larger importance than GrayLarge is
because, for some local counterfactuals, GrayLarge objects (which are not necessarily Cube)
might be removed, thus lowering the importance of this concept. Class 2 on the other hand
(Large Blue Sphere, Small Yellow Sphere) is not confounded, and the classifier is not expected
to be biased (test F1 score of 0.92). The most important removals seem to be: combinations of
Cube, Small, Metal - which makes sense since the source region contains images classified in
class 1 (Small Metal Cube, Small Sphere, where the Small Sphere is always Metal in the train
set). The most important insertions seem to be: Blue, Yellow, Sphere, and combinations of Blue,
Large, Sphere which coincides with the definition of the class.
5.2. COCO
As a second experiment, we decided to explore some more intuitive examples and thus decided
to take advantage of the COCO dataset [
classifier pre-trained on the PLACES dataset [ 32], provided by the creators of the dataset 3, for scene classification, and made predictions on the aforementioned subset of COCO. This is the black-box classifier for which we provide explanations. 5.2.2. Local Counterfactuals In the first row of Figure 5 we show a local counterfactual explanation for an image classified as a “Bedroom” to the target class “Playhouse”, which requires only one Concept Edit (⊤→Child).
This example is interesting because “Playhouse” is an erroneous prediction (the ground truth for the second image should be “Bedroom”), thus immediately we detect a potential bias of the classifier, that if a Child is added to an image of a “Bedroom” it might be classified as a “Playhouse”. Similarly, in the second row of Figure 5 we show a local counterfactual explanation for an image which is classified as “Bedroom” to the target class “Veterinarian’s Ofice”, and the resulting target image is an erroneous prediction. The resulting edit is simply to add a Cat. Finally, in Figure 6 we show a counterfactual explanation, where the path on the graph has two steps. The source image is classified as a “Bedroom” and the target class is “Computer Room”. This shows a smooth transition from the source image to the target class, by first adding a person (there are already two laptops in the source image), and then adding two more people and two more laptops. 5.2.3. Generalized Counterfactuals In Figures 7,8 we see two examples of generalized counterfactual explanations on the COCO dataset. As before, each bar’s numeric value shows the importance of the insertion (positive) or removal (negative) of that specific concept, in the process of transforming from a source region of an explanation dataset, to a target class.
Without revealing the source region and the target class for each figure, we can try to work out what those are, just by looking at the most frequent additions and removals. On the first (fig.7), which is the more trivial of the two, we see that the most common removals from the source images were concepts relevant to {furniture, bed, animal, carnivore, dog}, while the most common additions were the concepts {home appliance, refrigerator, white goods, consumer goods}. From this, we can assume that the source region was likely bedroom images (with a bias towards pets) and the target class was probably a kitchen. The true classes were, indeed, "bedroom" and "kitchen". On the second (fig.8), we see that most frequent removals revolved around {instrumentality, artifact, electronic, furniture, telecommunications, TV, broadcasting, kitchen} and the most common additions around {carnivore, animal, mammal, feline, cat, dog}. Knowing that we are dealing with a classifier of rooms and places, we’d probably guess a kitchen for the source and a location with domestic animals for the target. The actual classes were "bedroom" targeting "veterinarian", which raises an interesting question: why did we see "kitchen" instead of "bed" in the bedroom class? The answer is that no beds were actually removed, since veterinarian ofice images tend to include beds. On the other hand, our dataset contains a number of studio-apartment bedroom images which had part of the kitchen appearing in the photo - kitchens that are mostly missing from a vet’s ofice and had to be removed. Another thing to note is that those examples were not cherry-picked. During our experiments we could, most of the time, estimate the source region and target class by looking at the edit frequencies. Notably, the most confusing results were when we tested the "computer room" target and found out that the generalized counterfactual explanation was very often adding people, but never laptops or computers. After investigating what seemed like a bug, we realized that most images from our dataset which were classified as a "computer room" had no computers in them, but people working in lab-appearing rooms.
In our experiments we got interesting results, where both local and generalized counterfactual explanations seem to be informative, understandable and usable. In the CLEVR-Hans3 case (sec.5.1) we were able to detect the foreknown biases of the classifier, while in the COCO case (sec.5.2) we even detected unknown biases (for example the depiction of people was more important than that of laptops for the class “computer room”), and further insight into the classifier, which we had not thought about (for example that the classifier expects veterinarian’s ofices to depict beds among other objects). By comparing with the FACE algorithm (sec.5.1.2), we got a hint of the merits of considering explanations using high-level external terminology instead of low-level features, since even without stating the concept edits corresponding to counterfactual paths, we found the resulting images more intuitive and easy to compare with the source images.
An apparent drawback of the proposed framework, for it to be used in practice, is its reliance on the existence of semantically annotated data (i.e. an explanation dataset). Such datasets do exist for various domains, but they are not abundant. We have identified two ways of mitigating this drawback, which will be explored further in future work. The first is to semantically annotate data automatically by employing information extraction methods, such as object detection or scene-graph generation for images, or other methods which automatically link entities to knowledge (for instance from text to encyclopedic knowledge [33]). The second way of mitigating this drawback, which is more suited for decision-critical domains such as medicine, is to invest resources for the manual annotation and curation of explanation datasets. We believe that having data manually characterized by domain experts could improve user awareness and trust of the generated explanations.
We have introduced a novel framework for representing and computing counterfactual
explanations and have shown some preliminary results. There are many directions which we
plan to explore in future work. First of all we plan to expand this framework further into
Description Logics, to include roles and individuals, allow for more complex axioms in the TBox,
and to explore how this efects the resulting explanations, both theoretically and practically.
Furthermore, we plan to expand our evaluation framework to include datasets from multiple
domains and applications, focusing on those where explainability is imperative, such as medical
applications. We aim to experiment providing explanations for text, audio and tabular data.
Ideally, the evaluation framework will include human evaluators in the future. Finally, we aim
to study the properties of explanation datasets, as they are defined in our framework, and as
they have been approached in other works [
IEEE Computer Society, 2016, pp. 770–778. [32] B. Zhou, À. Lapedriza, A. Khosla, A. Oliva, A. Torralba, Places: A 10 million image database for scene recognition, IEEE Trans. Pattern Anal. Mach. Intell. 40 (2018) 1452–1464. [33] R. Mihalcea, A. Csomai, Wikify! linking documents to encyclopedic knowledge, in: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007, pp. 233–242.