Choose your Data Wisely: A Framework for Semantic Counterfactuals

As the field of eXplainable AI (XAI) research matures, the desiderata for explanations become more clear. Some of these are difficult to quantify, such as understandability, trust, and informativeness Hoffman et al. (2018). For counterfactual explanations specifically, there are additional requirements, namely feasibility and actionability Poyiadzi et al. (2020), minimality/proximity, and flip-rate/accuracy/validity Verma et al. (2020). In this work, we propose a framework for generating counterfactual explanations, that guarantees optimal flip-rate, minimality, feasibility, and actionability. Furthermore, we argue that by utilizing knowledge graphs, the explanations become more understandable, informative, and trustworthy - which we quantify in a user study.

Explanations based on low-level features, such as pixel brightness or sound frequency, have not proven to be particularly helpful or trustworthy to users Rudin (2019). These numeric representations of real-world phenomena appear rather cryptic to humans, who choose intuitive, high-level criteria when describing the factors that direct their decisions; criteria such as, how “furry” a dog is or how “dry” a cough sounds when determining a dog breed or a respiratory issue, respectively. Low-level features may be useful information for machine predictions, but not for human-readable explanations.

Fortunately, there is no mathematical difference between a vector representing low-level characteristics (eg. pixel values) and one representing semantically rich features Browne and Swift (2020). This makes it feasible to create systems that provide counterfactual explanations in terms of semantic features instead of low-level characteristics. This argument has been grounded both theoretically and practically, by the community. Browne and Swift (2020) demonstrates the equivalence between counterexamples and adversarial examples in cases where higher-level semantics are not employed. Additionally, recent works provide explanations by incorporating the semantics of inputs in various ways. For instance, Goyal et al. (2019) uses the intermediate output of a classifier as a form of higher-level information about the input image. Akula et al. (2020) deduces an image’s semantic concepts (xconcepts) by clustering the outputs of these features and presuming that elements of the same cluster are semantically similar. Meanwhile, Vandenhende et al. (2022) employs an external neural network to create semantic embeddings of these features, regarding proximate embeddings as semantically equivalent. All of the above algorithms use different methods of approximating the semantic distance of the elements depicted in images.

In our work, we build on these ideas and propose a framework for semantic counterfactuals, where the semantics are defined in knowledge graphs Hogan et al. (2021). This allows for providing explanations using structured, human-understandable terms. Furthermore, the framework does not require access to the model under investigation, contrarily to the above techniques which require accessing the layers of a model, circumventing its black-box nature. This white-box access to AI models may be the case in many research scenarios but in the real world, the convenience of tapping into the inner workings of a trained model is unlikely to exist. Black box explanations have been criticised by the community Rudin (2019), in favour of inherently interpretable models, however since black box models are still prevalent in both academia and the industry, attempting to explain their predictions is still an important problem to solve. Our proposed solution to the problem mitigates a lot of the criticism, as long as the data and the knowledge graphs are chosen wisely.

Specifically, by considering explanations at the level of abstraction of the knowledge graph, this technique centralizes the possible sources of errors solely toward the data, instead of the explainability algorithm. This transforms typical pitfalls of post hoc XAI, such as misleading explanations, to a considerably easier and more intuitive problem. For instance, a pixel-level explanation algorithm, such as a saliency map, explaining why a dog is a labrador and not a golden retriever, would produce a map lighting the body of the dog as an explanation. Due to the ambiguity of such a pixel-level explanation, it may not be apparent which characteristics of the animal’s body were vital for its classification - let alone identifying it as an erroneous explanation. In contrast, a semantic explanation would express explicitly that “the dog’s coat has to be red to be classified as a labrador”. The clarity that such an explanation provides is not only more informative but easily exposes possible biases - such as an uneven number of red-coated labradors in the data. Knowing that this bias can only be arising from the data and not the algorithm, makes the resolution straightforward. Namely, choosing data and knowledge which are semantically representative of the classes we want to discern. This is how we can replace the hard problem of algorithmic errors in explainability with the more manageable problem of improper data.

The framework is presented using the formalism of Description Logics (DLs) Baader et al. (2003). Even though we do not make full use of the expressive power and reasoning capabilities of DLs, they are used as a way of future-proofing the framework, which could be extended in the future for more expressive knowledge than what is presented here. In this work, we make certain assumptions about the structure of DL knowledge bases. Specifically, given a vocabulary $\mathcal{V}=\langle{\mathsf{CN,RN,IN}}\rangle$ where $\mathsf{CN,RN,IN}$ are mutually disjoint finite sets of concept, role and individual names, we consider $\mathcal{K}=\langle{\mathcal{A},\mathcal{T}}\rangle$ to be a knowledge base, where the ABox $\mathcal{A}$ is a set of assertions of the form $C(a)$ and $r(a,b)$ where $C\in\mathsf{CN}$, $r\in\mathsf{RN}$ and $a,b\in{\mathsf{IN}}$, and the TBox $\mathcal{T}$ is a set of terminological axioms of the form $C\sqsubseteq{D}$ where $C,D\in{\mathsf{CN}}$ or $r\sqsubseteq{s}$ where $r,s\in{\mathsf{RN}}$. The symbol ‘$\sqsubseteq{}$’ denotes inclusion or subsumption. For example, a concept name (in $\mathsf{CN}$) could be $\mathsf{Dog}$, an individual name (in $\mathsf{IN}$) could be the (unique) name of a specific dog, for example $\mathsf{snoopy\_42}$, and a role name (in $\mathsf{RN}$) could be a relation, such as “$\mathsf{eating}$”. Then an ABox could contain the assertion $\mathsf{Dog(snoopy\_42)}$, indicating that $\mathsf{snoopy\_42}$ is a $\mathsf{Dog}$, and a TBox could contain the axiom $\mathsf{Dog}\sqsubseteq{\mathsf{Animal}}$, representing the fact that all dogs are animals (where $\mathsf{Animal}$ is also a concept name in $\mathsf{CN}$). In such a knowledge base, both the ABox and the TBox can be represented as labeled graphs. An ABox $\mathcal{A}$ can be represented as the graph $\langle V,E,\ell_{V},\ell_{E}\rangle$ (an ABox graph), where $V=\mathsf{IN}$ is the set of nodes, $E=\{\langle a,b\rangle\mid r(a,b)\in\mathcal{A}\}\subseteq\mathsf{IN}\times\mathsf{IN}$ is the set of labeled edges, $\ell_{V}:V\rightarrow 2^{\mathsf{CN}}$ with $\ell_{V}(a)=\{C\mid C(a)\in\mathcal{A}\}$ is the node labeling function, and $\ell_{E}:E\rightarrow 2^{\mathsf{RN}}$ with $\ell_{E}(a,b)=\{r\mid r(a,b)\in\mathcal{A}\}$ is the edge labeling function. A TBox $\mathcal{T}$ that only contains hierarchies of concepts and roles, can be represented as a directed graph $\langle{V,E}\rangle$ (a TBox graph) where $V=\mathsf{CN}\cup{\mathsf{RN}}\cup{\{\top\}}$ the set of nodes. The set of edges $E$ contains an edge for each axiom in the TBox, in addition to edges from atoms appearing only on the right side of subsumption axioms, and atoms that don’t appear in the TBox, to the $\top$ node: $E=\{\langle{a,b}\rangle{}\mid a\sqsubseteq{b}\in{\mathcal{T}}\}\cup\{\langle{a,\top}\rangle\mid c\sqsubseteq{a}\in{\mathcal{T}}\wedge{a\sqsubseteq{d}}\not\in{\mathcal{T}\wedge{c,d\in{\mathsf{CN}\cup{\mathsf{RN}}}}}\}\cup\{\langle{a,\top}\rangle\mid{a\not\in{sig(\mathcal{T})}}\}$. This is abusive notation, in that the symbol $\top$ is overloaded and symbolizes both the universal concept and the universal role. Finally, we consider classifiers to be functions $F:\mathcal{D}\rightarrow{\mathcal{C}}$, where $\mathcal{D}$ is the domain of the classifier and $\mathcal{C}$ is the set of names of the classes.

The first step for attempting to understand a black box is to choose what data to feed it. In this work we explore the merits of feeding it data for which there is available information in a knowledge base. This data comes in the form of what we call exemplars, that are described as individuals in the underlying knowledge, and can be mapped to the feature domain of the classifier. Such semantic information that describes exemplars can be acquired from knowledge graphs available on the web (for example wordnet Miller (1995)), it can be extracted using knowledge extraction methods (such as scene graph generation), or, ideally, it can be provided by domain experts. A motivating example would be a set of X-rays that have been thoroughly described by medical professionals, and using standardized medical terminology their characterizations have been encoded in a description logics knowledge base. Having such a set of exemplars allows us to provide explanations in terms of the underlying knowledge instead of being constrained by the features of the classifier.

Intuitively, an explanation dataset contains items for which we have available semantic information, alongside a feature representation that can be fed to the classifier. The concept name $\mathsf{Exemplar}$ is used to flag those individuals that can be mapped by $\mathcal{M}$ to the domain of the classifier, and it does not appear in the TBox to avoid complications that could arise from reasoning. In this context, counterfactual explanations have the form of semantic edits that are applied on an ABox corresponding to an explanation dataset. Specifically, given an exemplar and a desired class, we are searching for a set of edits that when applied on the ABox lead to the exemplar being indistinguishable from any exemplar that is classified to the desired class.

For example, consider an image classifier $F$ that classifies to the classes $\mathcal{C}=\{\mathsf{WildAnimal,DomesticAnimal}\}$, and two exemplars $e_{1},e_{2}$ each classified to a different class: $F(e_{1})=\mathsf{WildAnimal}$ and $F(e_{2})=\mathsf{DomesticAnimal}$. The connected components of each exemplar in the ABox graph might be:

	$\displaystyle\mathcal{A}_{e_{1}}=\{\mathsf{Exemplar}(e_{1}),\mathsf{depicts}(e_{1},a),\mathsf{depicts}(e_{1},b),$
	$\displaystyle\mathsf{isIn}(a,b),\mathsf{Animal}(a),\mathsf{Forest}(b)\}$

	$\displaystyle\mathcal{A}_{e_{2}}=\{\mathsf{Exemplar}(e_{2}),\mathsf{depicts}(e_{2},c),\mathsf{depicts}(e_{2},d),$
	$\displaystyle\mathsf{isIn}(c,d),\mathsf{Animal}(c),\mathsf{Bedroom}(d)\}$

Then an explanation for exemplar $e_{1}$ and class $\mathsf{DomesticAnimal}$ would be the replacement of assertion $\mathsf{Forest}(b)$ with $\mathsf{Bedroom}(b)$, which would be symbolized $\langle{e_{2},\{e_{\mathsf{Forest}\rightarrow\mathsf{Bedroom}}\}}\rangle$ and it would be interpreted by a user as “If image $e_{1}$ depicted animal $a$ in a $\mathsf{Bedroom}$ instead of a $\mathsf{Forest}$, then the image would be classified as a $\mathsf{DomesticAnimal}$”. Of course there is no way to know if the image $e_{1}$ with the $\mathsf{Forest}$ replaced with a $\mathsf{Bedroom}$ would be classified to the target class, because we do not have a way to edit the pixels of the image and feed it to the classifier. The explanation however provides useful information to the user and can potentially aid in the detection of biases of the classifier. For example, after viewing this explanation, the user might choose to feed the classifier images depicting wild animals in bedrooms to see whether or not they are misclassified as domestic animals.

To provide more information to the end user, we can accumulate counterfactual explanations for multiple exemplars and the desired class and provide statistics about what changes tend to flip the prediction of the classifier, as a form of a “global” explanation. For example, one could ask “What are the most common semantic edits that when applied on exemplars depicting bedrooms lead to them to be classified as wild animals?”. To do this, we first compute the multiset $\mathcal{G}$ of all counterfactual explanations from each exemplar in the source subset to the target class , and then we show the end-user the importance of each atom for changing the prediction on the source exemplars to the target class, where

$$\mathsf{Importance}(y)=\frac{|\{e_{x\rightarrow{y}}\in{\mathcal{G}}\}|-|\{e_{y\rightarrow{x}}\in{\mathcal{G}}\}|}{|\mathcal{G}|}$$

where $,x,y\in{\mathsf{CN}}\text{, or }x,y\in{\mathsf{RN}}$.

Intuitively, the importance of an atom shows how often it is introduced (either via replacement or via insertion) as part of the semantic edits of a set of counterfactual explanations. A negative importance would indicate that the atom tends to be removed (either via replacement or via deletion of assertions). For example, one could gather all exemplars that are classified as $\mathsf{WildAnimal}$, along with their counterfactual explanations for target class $\mathsf{DomesticAnimal}$ and compute how important the presence (or absence) of a concept or a role is for distinguishing between the two classes.

Given an explanation dataset $\langle{\mathsf{EN}\rightarrow{\mathcal{D}},\langle{\mathcal{A},\mathcal{T}}\rangle}\rangle$, the first step for computing counterfactual explanations is to determine the edit operations on the ABox that transform the description of every exemplar to every other exemplar, thus this is a computation that has to be done $O(|\mathsf{EN}|^{2})$ times, but it only has to be done once for an explanation dataset. Ideally, each set of edit operations will be minimal as they are intended to be shown to users as explanations, which means that the problem to be solved is the exact graph edit distance problem Sanfeliu and Fu (1983).

For evaluating the proposed framework, we conducted four experiments, each with a different purpose. The first is a user study for comparing our work with a state-of-the-art image counterfactual system, which was performed on the CUB dataset Wah et al. (2011). The second is a demonstration of an intended use-case of the framework, where in order to explain a black-box classifier trained on the Places dataset Zhou et al. (2018), we utilize semantic information present in COCO Lin et al. (2014), the Visual Genome Krishna et al. (2017), and WordNet. In the third experiment we explore the use of a scene graph generator for producing semantic descriptions. For the final experiment, we generate explanations for a COVID-19 cough audio classifier trained on a subset of Coswara Sharma et al. (2020), showcasing that our approach is domain agnostic, and how it can provide useful explanations in such a critical application.

We have presented a novel explainability framework based on knowledge graphs. The explanations are guaranteed to be valid, and feasible, as they are always edits towards real data points. They are also guaranteed to be minimal, as they are the result of an edit distance computation, and actionable, provided the manual assignment of edit costs. Via the human study, we also show that counterfactual explanations in the context of the proposed framework, are understandable, and satisfactory to end-users. The main limitation of the framework, is its dependence on the explanation dataset, which ideally is curated by domain experts. For critical applications, such as medicine, we argue that it is worth the resources. For other applications, we have shown that using available semantically enriched datasets, such as the visual genome, or using automatic knowledge extraction techniques to construct the explanation dataset, such as scene graph generation, can lead to useful explanations. There are two directions we plan to further explore in future work. Firstly, we aim to extend the framework for more expressive knowledge, and to make use of theoretical results regarding description logics and reasoning. Secondly, we are experimenting with generative models, that can apply the semantic edits on a data sample, and generate a new sample that can be fed to the classifier.