Searching for explanations of black-box classifiers in the space of semantic queries

Abstract

Deep learning models have achieved impressive performance in various tasks, but they are usually opaque with regards to their inner complex operation, obfuscating the reasons for which they make decisions. This opacity raises ethical and legal concerns regarding the real-life use of such models, especially in critical domains such as in medicine, and has led to the emergence of the eXplainable Artificial Intelligence (XAI) field of research, which aims to make the operation of opaque AI systems more comprehensible to humans. The problem of explaining a black-box classifier is often approached by feeding it data and observing its behaviour. In this work, we feed the classifier with data that are part of a knowledge graph, and describe the behaviour with rules that are expressed in the terminology of the knowledge graph, that is understandable by humans. We first theoretically investigate the problem to provide guarantees for the extracted rules and then we investigate the relation of “explanation rules for a specific class” with “semantic queries collecting from the knowledge graph the instances classified by the black-box classifier to this specific class”. Thus we approach the problem of extracting explanation rules as a semantic query reverse engineering problem. We develop algorithms for solving this inverse problem as a heuristic search in the space of semantic queries and we evaluate the proposed algorithms on four simulated use-cases and discuss the results.

1. Introduction

The opacity of deep learning models raises ethical and legal [26] concerns regarding the real-life use of such models, especially in critical domains such as medicine and judicial, and has led to the emergence of the eXplainable Artificial Intelligence (XAI) field of research, which aims to make the operation of opaque AI systems more comprehensible to humans [55,74]. While many traditional machine learning models, such as decision trees, are interpretable by design, they typically perform worse than deep learning approaches for various tasks. Thus, in order to not sacrifice performance for the sake of transparency, a lot of research is focused on post hoc explainability, in which the model to be explained is treated as a black-box. Approaches to post hoc explainability vary with regard to data domain (images, text, tabular), form of explanations (rule-based, counterfactual, feature importance etc.), scope (global, local) [31] and application domain [42]. In this work we focus on global explanations, which attempt to explain the general function of a black-box regardless of data, as opposed to local explanations which attempt to explain the prediction of a classifier on a particular data sample. Specifically, we attempt to extract rules which simulate the behaviour of a black-box by considering semantic descriptions of samples, in addition to external knowledge. For example such a rule might be “Images depicting animals and house-hold items are classified as domestic animals”, where the semantic description of an image might be “This image depicts an elephant next to a chair” and external knowledge might contain information such as “elephants are animals” and “chairs are household items”. We do this by utilizing terminological, human-understandable knowledge expressed in the form of ontologies and knowledge graphs, taking advantage of the reasoning capabilities of the underpinning description logics [5]. Such extracted rules might be very useful for an end user to understand the reasons behind why an opaque model is making its decisions, especially when combined with other forms of explanations, such as local contrastive explanations [75].

Our approach to global rule-based explanations assumes that we are given a set of data samples with semantic descriptions linked to an external knowledge. The explanations will be presented in the terminology provided by the external knowledge. We call such a set of samples an explanation dataset. For example, a semantic description for an image might refer to the objects it depicts and relationships between them, such as scene graphs from visual genome [39], or COCO [49]. The external knowledge utilized could be an existing knowledge base, such as WordNet [52], ConceptNet [67], DBpedia [45], and even domain specific knowledge such as SNOMED-CT [69] for the medical domain, or it could be a knowledge base curated specifically for that explanation dataset. Given such a set of semantically enriched data, we then compute global rule-based explanations characterizing the output of a black-box classifier. We approach the problem as a query reverse engineering (QRE) problem by utilizing the close relationship between definite rules and conjunctive queries.

Utilizing external knowledge to boost transparency of opaque AI is an active research area which has produced important results in recent years [1–3,15,17,18,23,24,57,64,65,71,78,82]. Specifically, knowledge graphs (KG) [34] as a scalable common understandable structured representation of a domain based on the way humans mentally perceive the world, have emerged as a promising complement or extension to machine learning approaches for achieving explainability. A particular aspect which might be improved by utilizing knowledge graphs, especially for generalized global explanations, is the form of the produced explanations. When the feature space of the classifier is sub-symbolic raw data, then providing explanations in terms of features might lead to unintuitive, or even misleading results [54,61,63]. On the other hand, if there is underlying knowledge of the data, then explanations can be provided by using the terminology of the knowledge. For example, if a black-box classified every image depicting wild animals in the class zoo, a rule of the form “If an image depicts a giraffe or a zebra or $\dots$ then it is classified as a zoo”, might be more intuitive than for example sets of pixel importances. Furthermore, by exploiting external knowledge, the form can be further condensed and lead to simpler explanations which are semantically identical, such as “If an image depicts a wild animal then it is classified as a zoo”. This approach to explainability mitigates some of the typical pitfalls of post hoc XAI, and transfers potential sources of erroneous or misleading explanations to the level of the data and the knowledge (instead of the explainability algorithm), which are easier to control in most settings. For instance, a typical pitfall of post hoc XAI mentioned in [63], is that explanations often do not make sense, or are incomplete (leaving out information to be understandable). In our approach, the explanations make as much sense as the terminology used in the knowledge graph, and are as informative as the explanation dataset.

There are many related rule-based explanation methods (both global and local) in recent literature. Many approaches rely on statistics in order to generate lists of IF-THEN rules which mimic the behaviour of a classifier [30,44,53,62,80], while others extract rules in the form of decision trees [16,84] or First-Order Logic expressions [13]. Rules have been argued to be the preferred method of presenting explanations to humans, as they are close to the way humans reason [4,31,58]. There are also related works that utilize ontologies for the purpose of explainability, and we build on these ideas in our work. In [15] the authors utilize ontologies, expressed in the Description Logic $\mathcal{EL}$ , to enhance explanations of black-box classifiers produced in the form of decision trees. The authors conducted a user evaluation from which they concluded that users prefer decision trees extracted with the presence of an ontology than those without. In [17] the authors present a framework quite similar to our own. They also approach the problem of extracting explanations as a query reverse engineering problem, but there is no emphasis on the data utilized from producing the explanations compared to our notion of an explanation dataset. Their work is also preliminary as they do not present any algorithms for extracting the desired queries.

Query Reverse Engineering (QRE) is the problem of reverse-engineering a query from its output [72]. This is typically presented as a way for an end-user unfamiliar with a query language such as SQL to formulate a query by simply providing examples of what they expect to see in the query results. This is also usually approached as an interactive process; the user is continually providing more examples and marking answers of the query as desired or undesired. QRE has been extensively studied for relational databases and the language of relational algebra or SQL [51]. In this work we assume data is stored in a Knowledge Base and queries are formulated in the language of Conjunctive Queries. We also assume that we know the exact desired output of the query, without the need for a user to continually provide examples. Although conjunctive queries have the same expressivity as select-project-join relational queries using only equality predicates, adapting existing works to fit our framework is not easy or even desirable. Some common obstacles include i) the assumption of a dynamic labeling of individuals as positive/negative by an end-user [9,47,76], ii) the (often implicit) exclusion of the self-join operation, which would limit the expressivity of queries in ways undesirable to us [9,47,72,76], and iii) foreign/primary key constraints [81].

In the setting of conjunctive queries over Knowledge Bases, referred to as Semantic Query Answering or Ontology Mediated Querying [10,11,28,59,73], QRE has been under-explored. Recent work focuses on establishing theoretical results, such as the existence of solutions and the complexity of computing them [7,19,32,36,56]. The authors in [3] present a few algorithms alongside complexity results but the algorithms are limited to tree-shaped queries. One recent article [12], along with some theoretical results, presents two algorithms computing minimally complete and maximally sound solutions to the closely related Query Separability problem. We consider these algorithms unsuitable in the context of explainability, since the solutions computed essentially amount to one large disjunction of positive examples. In this work we focus on practical QRE over KBs and we present several algorithms which either have polynomial complexity or have worst-case exponential complexity but can be efficient in practice. We employ heuristics to limit the number of computations, we take care to limit the size of queries, since their intended use is that of explanations presented to users, and we provide (approximate) solutions even when a exact solution does not exist.

Our contributions:

Following our previous work in the area [19], we here present a framework for extracting global rule-based explanations of black-box classifiers, using exemplar items, external terminology and underlying knowledge stored in a knowledge graph and defining the problem of explanation rule extraction as a semantic query reverse engineering problem over the knowledge graph (see Section 3).

We propose practical algorithms which approximate the semantic query reverse engineering problem by using heuristics, which we then use to generate explanations in the context of the proposed framework (see Section 4).

We implement the proposed algorithms and show results from experiments explaining image classifiers on CLEVR-Hans3, Places365 and MNIST. We also compare our work with existing post-hoc, rule-based explanation methods on baseline tabular data employing the Mushroom dataset (see Section 5).

2. Background

2.1. Description logics

Let $\mathcal{V}=⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ be a vocabulary, where $\mathsf{CN}$ , $\mathsf{RN}$ , $\mathsf{IN}$ are mutually disjoint finite sets of concept names (atomic concepts), role names (atomic roles) and individual names, respectively. Atomic concepts and roles can be combined into complex concepts or roles using appropriate constructors. The set of available constructors for constructing complex concepts and roles, along with their syntax and semantics defines a Description Logics (DL) dialect. A list of common constructors is provided in Table 1, which are the constructors used by the $\mathcal{SHROIQ}$ dialect, which underpins the Web Ontology Language OWL 2. Note that the table defines also the two special concept names ⊤ and ⊥ that may belong to $\mathsf{CN}$ , representing the universal and empty concept, respectively.

Concepts and roles (either atomic or complex) are used to form terminological and assertional axioms, as shown in Table 2. Then, a DL knowledge base, simply a knowledge base, (KB) over a DL dialect $\mathcal{L}$ and a vocabulary $\mathcal{V}$ is a pair $\mathcal{K}=⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ , where $\mathcal{T}$ is a set of terminological axioms (also called TBox), and $\mathcal{A}$ a set of assertional axioms (also called ABox) using the constructors of $\mathcal{L}$ and elements of $\mathcal{V}$ . We will call an ABox containing only assertions of the form $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ and $\mathit{r}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ , where $\mathit{C}\in \mathsf{CN}$ , $\mathit{r}\in \mathsf{RN}$ , $\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{IN}$ , i.e. not involving complex expressions and (in)equality assertions, an atomic ABox.

The semantics of DL KBs are defined in the standard model-theoretic way using interpretations. In particular, given a non-empty domain Δ, an interpretation $\mathcal{I}=\mathrm{(}{\mathrm{\Delta }}^{\mathcal{I}}\mathrm{,}{·}^{\mathcal{I}}\mathrm{)}$ assigns a set ${\mathit{C}}^{\mathcal{I}}\subseteq {\mathrm{\Delta }}^{\mathcal{I}}$ to each atomic concept $\mathit{C}\in \mathsf{CN}$ , a set of pairs ${\mathit{r}}^{\mathcal{I}}\subseteq {\mathrm{\Delta }}^{\mathcal{I}}\times {\mathrm{\Delta }}^{\mathcal{I}}$ to each atomic role $\mathit{r}\in \mathsf{RN}$ , and an element ${\mathit{a}}^{\mathcal{I}}\in \mathrm{\Delta }$ to each individual $\mathit{a}\in \mathsf{IN}$ . Table 1 shows also the semantics of the listed constructors. An interpretation $\mathcal{I}$ is a model of a KB $\mathcal{K}$ iff it satisfies all axioms in $\mathcal{T}$ and all assertions in $\mathcal{A}$ , i.e. iff it satisfies the expression in the last column of Table 2 for the respective axioms.

The underlying DL dialect $\mathcal{L}$ determines the expressivity of a knowledge base. Most classical DL dialects can be seen as fragments of first-order logic (FOL) by viewing atomic concepts and roles as unary and binary predicates respectively. In this paper we refer only to DL dialects that are fragments of first-order logic, and hence can be translated to first-order logic theories. We will denote the translation of such a $\mathcal{K}$ to the respective first order logic theory by $\mathsf{FOL}\mathrm{(}\mathcal{K}\mathrm{)}$ . E.g. the FOL translation of the DL concept $\exists \mathit{r}.\mathit{C}$ is an expression of the form $\exists \mathit{x}.\mathrm{(}\mathit{r}\mathrm{(}\mathit{y}\mathrm{,}\mathit{x}\mathrm{)}\wedge {\mathit{\varphi }}_{\mathit{C}}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{)}$ , where ${\mathit{\varphi }}_{\mathit{C}}\mathrm{(}\mathit{x}\mathrm{)}$ is the FOL translation of concept C. For more details see [5].

Table 1

DL syntax and semantics

Name	Syntax	Semantics
Top	⊤	${\mathrm{\Delta }}^{\mathcal{I}}$
Bottom	⊥	∅
Complement	$\neg \mathit{C}$	${\mathrm{\Delta }}^{\mathcal{I}}\setminus {\mathit{C}}^{\mathcal{I}}$
Intersection	$\mathit{C}\sqcap \mathit{D}$	${\mathit{C}}^{\mathcal{I}}\cap {\mathit{D}}^{\mathcal{I}}$
Union	$\mathit{C}\bigsqcup \mathit{D}$	${\mathit{C}}^{\mathcal{I}}\cup {\mathit{D}}^{\mathcal{I}}$
Existential quantification	$\exists \mathit{r}.\mathit{C}$	$\{\mathit{a}\in {\mathrm{\Delta }}^{\mathcal{I}}|\exists \mathit{b}.\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}\wedge \mathit{b}\in {\mathit{C}}^{\mathcal{I}}\}$
Value restriction	$\forall \mathit{r}.\mathit{C}$	$\{\mathit{a}\in {\mathrm{\Delta }}^{\mathcal{I}}|\forall \mathit{b}.\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}\to \mathit{b}\in {\mathit{C}}^{\mathcal{I}}\}$
At-least number restriction	$⩾\mathit{n}\mathit{r}.\mathit{C}$	$\{\mathit{a}\in {\mathrm{\Delta }}^{\mathcal{I}}\mid |\{\mathit{b}\in {\mathrm{\Delta }}^{\mathcal{I}}\mid \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}\wedge \mathit{b}\in {\mathit{C}}^{\mathcal{I}}\}|⩾\mathit{n}\}$
At-most number restriction	$⩽\mathit{n}\mathit{r}.\mathit{C}$	$\{\mathit{a}\in {\mathrm{\Delta }}^{\mathcal{I}}\mid |\{\mathit{b}\in {\mathrm{\Delta }}^{\mathcal{I}}\mid \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}\wedge \mathit{b}\in {\mathit{C}}^{\mathcal{I}}\}|⩽\mathit{n}\}$
Nominal	$\{\mathit{a}\}$	$\{{\mathit{a}}^{\mathcal{I}}\}$
Inverse role	${\mathit{r}}^{-}$	$\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in {\mathrm{\Delta }}^{\mathcal{I}}\times {\mathrm{\Delta }}^{\mathcal{I}}\mid \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}\}$
Role composition	$\mathit{r}\circ \mathit{s}$	${\mathit{r}}^{\mathcal{I}}\circ {\mathit{s}}^{\mathcal{I}}$

Table 2

Terminological and assertional axioms

Name	Syntax	Semantics
Concept inclusion	$\mathit{C}⊑\mathit{D}$	${\mathit{C}}^{\mathcal{I}}\subseteq {\mathit{D}}^{\mathcal{I}}$
Concept equivalence	$\mathit{C}\equiv \mathit{D}$	${\mathit{C}}^{\mathcal{I}}={\mathit{D}}^{\mathcal{I}}$
Role inclusion	$\mathit{r}⊑\mathit{s}$	${\mathit{r}}^{\mathcal{I}}\subseteq {\mathit{s}}^{\mathcal{I}}$
Role equivalence	$\mathit{r}\equiv \mathit{s}$	${\mathit{r}}^{\mathcal{I}}={\mathit{s}}^{\mathcal{I}}$
Concept assertion	$\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$	${\mathit{a}}^{\mathcal{I}}\in {\mathit{C}}^{\mathcal{I}}$
Role assertion	$\mathit{r}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$	${\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}}^{\mathcal{I}}\in {\mathit{r}}^{\mathcal{I}}$
Individual equality	$\mathit{a}=\mathit{b}$	${\mathit{a}}^{\mathcal{I}}={\mathit{b}}^{\mathcal{I}}$
Individual inequality	$\mathit{a}\ne \mathit{b}$	${\mathit{a}}^{\mathcal{I}}\ne {\mathit{b}}^{\mathcal{I}}$

2.2. Conjunctive queries

Given a vocabulary $\mathcal{V}$ , a conjunctive query (simply, a query) q is an expression of the form $\{⟨{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{k}}⟩|\exists {\mathit{y}}_1\dots \exists {\mathit{y}}_{\mathit{l}}.\mathrm{(}{\mathit{c}}_1\wedge \cdots \wedge {\mathit{c}}_{\mathit{n}}\mathrm{)}\}$ , where $\mathit{k}\mathrm{,}\mathit{l}\mathrm{,}\mathit{n}⩾0$ , ${\mathit{x}}_{\mathit{i}}$ , ${\mathit{y}}_{\mathit{i}}$ are variable names, the ${\mathit{c}}_{\mathit{i}}$ s are distinct, each ${\mathit{c}}_{\mathit{i}}$ is an atom $\mathit{C}\mathrm{(}\mathit{u}\mathrm{)}$ or $\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}$ , where $\mathit{C}\in \mathsf{CN}$ , $\mathit{r}\in \mathsf{RN}$ , $\mathit{u}\mathrm{,}\mathit{v}\in \mathsf{IN}\cup \{{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{k}}\}\cup \{{\mathit{y}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{l}}\}$ and all ${\mathit{x}}_{\mathit{i}}$ , ${\mathit{y}}_{\mathit{i}}$ appear in at least one atom. The vector $⟨{\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{k}}⟩$ is the head of q, its elements are the answer variables, and $\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}$ is the body of q ( $\mathsf{body}\mathrm{(}\mathit{q}\mathrm{)}$ ). Generally, in the relevant literature, conjunctive queries are defined such that the body must be nonempty ( $\mathit{n}⩾1$ ) but we allow empty bodies in the sense that we do not impose any constraints that the answers of the query must satisfy, i.e. all individuals are answers. As we will see, this is a natural extension that conforms to all other definitions we use from the existing literature, without needing any special adjustments. The set $\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}$ is the set of all variables appearing in q.

On conjunctive queries one can apply substitutions, which map variables to other variables or individual names. More formally, a substitution θ is a finite set of mappings of the form $\{{\mathit{z}}_1\mapsto {\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{z}}_{\mathit{n}}\mapsto {\mathit{u}}_{\mathit{n}}\}$ where ${\mathit{z}}_{\mathit{i}}$ is a variable name, ${\mathit{u}}_{\mathit{i}}$ is either an individual name or a variable name distinct from all ${\mathit{z}}_{\mathit{i}}$ s, and the variables ${\mathit{z}}_{\mathit{i}}$ are distinct. A substitution may contain at most one mapping for a variable. The conjunctive query $\mathit{q}\mathit{\theta }$ resulting from applying θ on q is obtained from q by replacing all occurrences of z in q by u for each $\mathit{z}\mapsto \mathit{u}\in \mathit{\theta }$ . Any variables not mapped by θ remain unchanged.

Since in this paper we are interested in classifying single items, we focus on queries having a single answer variable. For convenience, we will also assume that all arguments of all ${\mathit{c}}_{\mathit{i}}$ in a query are variables, and we call such queries single answer variable queries, or SAV queries for short. For simplicity, in the rest of the paper, by saying query we will mean SAV query, and we will write a (SAV) query q as $\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}$ , considering always x as the answer variable, essentially identifying the query by its body. This will allow us to treat queries as sets, and write e.g. ${\mathit{q}}_1\cup {\mathit{q}}_2$ ; this query represents the query that has the same head as ${\mathit{q}}_1$ and ${\mathit{q}}_2$ (i.e. $⟨\mathit{x}⟩$ ), and body the union of the bodies of ${\mathit{q}}_1$ and ${\mathit{q}}_2$ . Similarly, we will write e.g. ${\mathit{q}}_1\subseteq {\mathit{q}}_2$ , meaning $\mathsf{body}\mathrm{(}{\mathit{q}}_1\mathrm{)}\subseteq \mathsf{body}\mathrm{(}{\mathit{q}}_2\mathrm{)}$ , and $\mathit{c}\in \mathit{q}$ meaning $\mathit{c}\in \mathsf{body}\mathrm{(}\mathit{q}\mathrm{)}$ . Following the above assumptions, all definitions that follow will be stated only for SAV queries, although more general formulations for general conjunctive queries might exist.

Given a KB $\mathcal{K}=⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ , a SAV query q and an interpretation $\mathcal{I}$ of $\mathcal{K}$ , a match for q is a mapping $\mathit{\pi }:\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}\to {\mathrm{\Delta }}^{\mathcal{I}}$ such that $\mathit{\pi }\mathrm{(}\mathit{u}\mathrm{)}\in {\mathit{C}}^{\mathcal{I}}$ for all $\mathit{C}\mathrm{(}\mathit{u}\mathrm{)}\in \mathit{q}$ , and $\mathrm{(}\mathit{\pi }\mathrm{(}\mathit{u}\mathrm{)}\mathrm{,}\mathit{\pi }\mathrm{(}\mathit{v}\mathrm{)}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}$ for all $\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}\in \mathit{q}$ . Then, $\mathit{a}\in \mathsf{IN}$ is an answer for q in $\mathcal{I}$ if there is a match π for q such that $\mathit{\pi }\mathrm{(}\mathit{x}\mathrm{)}={\mathit{a}}^{\mathcal{I}}$ . For queries with empty bodies it obviously holds that $\mathsf{ans}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{I}\mathrm{)}=\mathsf{IN}$ . Finally, $\mathit{a}\in \mathsf{IN}$ is a certain answer for q over $\mathcal{K}$ if in every model $\mathcal{I}$ of $\mathcal{K}$ there is a match π for q such that $\mathit{\pi }\mathrm{(}\mathit{x}\mathrm{)}={\mathit{a}}^{\mathcal{I}}$ . The set of certain answers to q is denoted by $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{K}\mathrm{)}$ . Naturally, when the query body is empty it holds that $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{K}\mathrm{)}=\mathsf{IN}$ . Because obtaining the set of certain answers of a query over some KB typically requires reasoning with the axioms of the underlying TBox, such queries are characterized in the literature as semantic queries.

Let $\mathcal{K}$ be a knowledge base over a vocabulary $\mathcal{V}$ , and $\mathcal{Q}$ the (possibly infinite) set of all SAV queries over $\mathcal{V}$ . We can partially order $\mathcal{Q}$ using query subsumption: A SAV query ${\mathit{q}}_2$ subsumes a SAV query ${\mathit{q}}_1$ (we write ${\mathit{q}}_1{⩽}_{\mathit{S}}{\mathit{q}}_2$ ) iff there is a substitution θ s.t. ${\mathit{q}}_2\mathit{\theta }\subseteq {\mathit{q}}_1$ and θ leaves variable x unchanged. If ${\mathit{q}}_1$ , ${\mathit{q}}_2$ are mutually subsumed, they are syntactically equivalent ( ${\mathit{q}}_1{\equiv }_{\mathit{S}}{\mathit{q}}_2$ ). $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ implies $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{K}\mathrm{)}\subseteq \mathsf{cert}\mathrm{(}{\mathit{q}}^{\prime }\mathrm{,}\mathcal{K}\mathrm{)}$ , since a match π for the variables of q can be composed with θ to produce a match $\mathit{\pi }\mathit{\theta }$ for the variables of ${\mathit{q}}^{\prime }$ . Let q, ${\mathit{q}}^{\prime }$ be queries s.t. ${\mathit{q}}^{\prime }\subseteq \mathit{q}$ . If ${\mathit{q}}^{\prime }$ is a minimal subset of q s.t. ${\mathit{q}}^{\prime }{\equiv }_{\mathit{S}}\mathit{q}$ , then ${\mathit{q}}^{\prime }$ is a condensation of q. If that minimal ${\mathit{q}}^{\prime }$ is the same as q, then q is condensed [27]. Intuitively, syntactically equivalent queries always have the same certain answers, and a condensation of some syntactically equivalent queries is the most compact query (not containing redundant atoms) that is syntactically equivalent to the rest.

Given the queries ${\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{n}}$ , a query least common subsumer $\mathsf{QLCS}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{n}}\mathrm{)}$ of them is defined as a query q for which ${\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{n}}{⩽}_{\mathit{S}}\mathit{q}$ , and for all ${\mathit{q}}^{\prime }$ s.t. ${\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{n}}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ we have $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ . The query least common subsumer can be seen as the most specific generalization of ${\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{,}\dots \mathrm{,}{\mathit{q}}_{\mathit{n}}$ , and it is unique up to syntactical equivalence. We should note that this notion of query least common subsumer is different from the usual notion of least common subsumer of concepts which has been extensively studied for various description logic expressivities [6,14,21,40].

2.3. Graphs

A SAV query q can be viewed as the directed labeled graph $⟨\mathit{V}\mathrm{,}\mathit{E}\mathrm{,}{\ell }_{\mathit{V}}\mathrm{,}{\ell }_{\mathit{E}}⟩$ (a query graph), where $\mathit{V}=\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}$ is the set of nodes, $\mathit{E}=\{⟨\mathit{u}\mathrm{,}\mathit{v}⟩|\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}\in \mathit{q}\}\subseteq \mathit{V}\times \mathit{V}$ is the set of edges, ${\ell }_{\mathit{V}}:\mathit{V}\to 2^{\mathsf{CN}}$ with ${\ell }_{\mathit{V}}\mathrm{(}\mathit{u}\mathrm{)}=\{\mathit{C}|\mathit{C}\mathrm{(}\mathit{u}\mathrm{)}\in \mathit{q}\}$ is the node labeling function, and ${\ell }_{\mathit{E}}:\mathit{E}\to 2^{\mathsf{RN}}$ with ${\ell }_{\mathit{E}}\mathrm{(}⟨\mathit{u}\mathrm{,}\mathit{v}⟩\mathrm{)}=\{\mathit{r}|\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}\in \mathit{q}\}$ is the edge labeling function. The answer variable is not explicitly identified since it is assumed to be always x. A SAV query is connected, if the corresponding query graph is connected.

In the following, it will be useful to also treat atomic ABoxes as graphs. Similarly to the case of SAV queries, an atomic ABox $\mathcal{A}$ can be represented as the graph $⟨\mathit{V}\mathrm{,}\mathit{E}\mathrm{,}{\ell }_{\mathit{V}}\mathrm{,}{\ell }_{\mathit{E}}⟩$ (an ABox graph), where $\mathit{V}\subseteq \mathsf{IN}$ is the set of nodes, in particular the subset of all individual names occurring in $\mathcal{A}$ , $\mathit{E}=\{⟨\mathit{a}\mathrm{,}\mathit{b}⟩|\mathit{r}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{A}\}\subseteq \mathit{V}\times \mathit{V}$ is the set of labeled edges, ${\ell }_{\mathit{V}}:\mathit{V}\to 2^{\mathsf{CN}}$ with ${\ell }_{\mathit{V}}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{C}|\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\in \mathcal{A}\}$ is the node labeling function, and ${\ell }_{\mathit{E}}:\mathit{E}\to 2^{\mathsf{RN}}$ with ${\ell }_{\mathit{E}}\mathrm{(}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}=\{\mathit{r}|\mathit{r}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{A}\}$ is the edge labeling function.

Given two graphs ${\mathit{G}}_1=⟨{\mathit{V}}_1\mathrm{,}{\mathit{E}}_1\mathrm{,}{\ell }_{{\mathit{V}}_1}\mathrm{,}{\ell }_{{\mathit{E}}_1}⟩$ , ${\mathit{G}}_2=⟨{\mathit{V}}_2\mathrm{,}{\mathit{E}}_2\mathrm{,}{\ell }_{{\mathit{V}}_2}\mathrm{,}{\ell }_{{\mathit{E}}_2}⟩$ , a homomorphism $\mathit{h}:{\mathit{G}}_1\to {\mathit{G}}_2$ is defined as a function from ${\mathit{V}}_1$ to ${\mathit{V}}_2$ that preserves edges and labels. More specifically it is such that: i) if $⟨\mathit{a}\mathrm{,}\mathit{b}⟩\in {\mathit{E}}_1$ then $⟨\mathit{h}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{h}\mathrm{(}\mathit{b}\mathrm{)}⟩\in {\mathit{E}}_2$ , ii) ${\ell }_{{\mathit{V}}_1}\mathrm{(}\mathit{a}\mathrm{)}\subseteq {\ell }_{{\mathit{V}}_2}\mathrm{(}\mathit{h}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}$ , and iii) ${\ell }_{{\mathit{E}}_1}\mathrm{(}⟨\mathit{a}\mathrm{,}\mathit{b}⟩\mathrm{)}\subseteq {\ell }_{{\mathit{E}}_2}\mathrm{(}⟨\mathit{h}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{,}\mathit{h}\mathrm{(}\mathit{b}\mathrm{)}⟩\mathrm{)}$ . If there exists a homomorphism from ${\mathit{G}}_1$ to ${\mathit{G}}_2$ , we will write for simplicity ${\mathit{G}}_1\to {\mathit{G}}_2$ . When ${\mathit{G}}_1$ and ${\mathit{G}}_2$ are query graphs we will make the additional assumption that h preserves the answer variable, i.e. $\mathit{h}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{x}$ . If h is a bijection whose inverse is also a homomorphism, then h is an isomorphism. It is easy to see that the query graph of ${\mathit{q}}_1$ is homomorphic to the query graph of ${\mathit{q}}_2$ iff ${\mathit{q}}_2{⩽}_{\mathit{S}}{\mathit{q}}_1$ .

2.4. Rules

A (definite) rule is a FOL expression of the form $\forall {\mathit{x}}_1\dots \forall {\mathit{x}}_{\mathit{n}}\mathrm{(}{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{m}}\Rightarrow {\mathit{c}}_0\mathrm{)}$ , where ${\mathit{c}}_{\mathit{i}}$ are atoms and ${\mathit{x}}_1\mathrm{,}\dots \mathrm{,}{\mathit{x}}_{\mathit{n}}$ are all the variables appearing in the several ${\mathit{c}}_{\mathit{i}}$ . The atoms ${\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{m}}$ are the body of the rule, and ${\mathit{c}}_0$ its head. A rule over a vocabulary $\mathcal{V}=⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ is a rule where each ${\mathit{c}}_{\mathit{i}}$ is either $\mathit{C}\mathrm{(}\mathit{u}\mathrm{)}$ , where $\mathit{C}\in \mathsf{CN}$ , or $\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}$ , where $\mathit{r}\in \mathsf{RN}$ . Assuming that ${\mathit{c}}_0$ is of the form $\mathit{D}\mathrm{(}\mathit{x}\mathrm{)}$ , where $\mathit{D}\in \mathsf{CN}$ , and that x appears in the body of such a rule, we will say that the rule is connected, if its body, seen as a SAV query is connected. A rule is usually written as ${\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{m}}\to {\mathit{c}}_0$ .

2.5. Classifiers

A classifier is viewed as a function $\mathit{F}:\mathcal{D}\to \mathcal{C}$ , where $\mathcal{D}$ is the classifier’s domain (ex. images, audio, text), and $\mathcal{C}$ is a set of class names (ex. “Dog”,“Cat”).

3. Framework

3.1. A motivating example

Integration of artificial intelligence methods and tools with biomedical and health informatics is a promising area, in which technologies for explaining machine learning classifiers will play a major role. In the context of the COVID-19 pandemic for example, black-box machine learning audio classifiers have been developed, which, given audio of a patient’s cough, predict whether the person should seek medical advice or not [41]. In order to develop trust and use these classifiers in practice, it is important to explain their decisions, i.e. to provide convincing answers to the question “Why does the machine learning classifier suggest to seek medical advice?”. There are post hoc explanation methods (both global and local) that try to answer this question in terms of the input of the black-box classifier, which in this case is audio signals. Although this information could be useful for AI engineers and developers, it is not understandable to most medical experts and end users, since audio signals themselves are obscure sub-symbolic data. Thus, it is difficult to convincingly meet the explainability requirements and develop the necessary trust to utilize the black-box classifier in practice, unless explanations are expressed in the terminology used by the medical experts (using terms like “sore throat”, “dry cough” etc).

In the above context, suppose we have a dataset of audio signals of coughs which have been characterized by medical professionals by using standardized clinical terms, such as “Loose Cough”, “Dry Cough”, “Dyspnoea”, in addition to a knowledge base in which these terms and relationships between them are defined, such as SNOMED-CT [69]. For example, consider such a dataset with coughs from five patients $\mathsf{p}\mathsf{1}\mathrm{,}\mathsf{p}\mathsf{2}\mathrm{,}\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}$ (obviously in practice we may need a much more extended set of patients) with characterizations from the medical experts: “ $\mathsf{p}\mathsf{1}$ has a sore throat”, “ $\mathsf{p}\mathsf{2}$ has dyspnoea”, “ $\mathsf{p}\mathsf{3}$ has a sore throat and dyspnoea”, “ $\mathsf{p}\mathsf{4}$ has a sore throat and a dry cough”, “ $\mathsf{p}\mathsf{5}$ has a sore throat and a loose cough”. We also have available relationships between these terms as defined in SNOMED-CT like “Loose Cough is Cough”, “Dry Cough is Cough”, “Cough is Lung Finding”, and “Dyspnoea is Lung Finding”.

Now assume that a black-box classifier predicts that $\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}$ , and $\mathsf{p}\mathsf{5}$ should seek medical advice, while $\mathsf{p}\mathsf{1}$ and $\mathsf{p}\mathsf{2}$ should not. Then we can say that: on this dataset, if a patient has a sore throat and a lung finding then it is classified positively by the specific classifier, i.e. the classifier suggests “seek medical advice”. Depending on the characteristics of the dataset itself and its ability to cover interesting examples, such an extracted rule could help the medical professional understand why the black-box is making decisions in order to build necessary trust, but also it could help an AI engineer improve the model’s performance by indicating potential biases. Importantly, even though we cannot know that the black-box classifier is actually using the semantics that are used to describe the data, this approach gives a user control over what information they want to examine the classifier for. For example, a system developer and a medical professional would use different semantic annotations because explanations are useful to them at different levels of abstraction. In a more concrete example, in our experiments on the Visual Genome dataset (Section 5.3) we employ the WordNet general-purpose ontology [52], but another end user could easily swap it for another general-purpose ontology such as ConceptNet [66]. Importantly, this plug-and-play approach allows for the improvement of the terminology used in the explanations as the external ontologies improve over time. Another indication of the usefulness of ontologies comes from [15] in which the authors examine the understandability of explanations extracted with the aid of an ontology. Conducting a user study, the authors conclude that the users find explanations that utilize domain knowledge provided by the ontology more understandable.

The utilization of such datasets and knowledge is the main strength of the proposed framework, but it can also be its main weakness. Specifically, erroneous labeling during the construction of the dataset could lead to misleading explanations, as could biases in the data. For example, if the length of the recordings of the coughs were also available to us, and every instance of “Sore Throat” also had a short length recording, then we would not be able to distinguish between these two characteristics, and the resulting explanations would not be useful.

3.2. Explaining opaque machine learning classifiers

Explanation of opaque machine learning classifiers is based on a dataset that we call Explanation Dataset (see Fig. 1), containing exemplar patterns, that are actually characteristic examples from the set of elements that the unknown classifier takes as input. Machine learning classifiers usually take as input element features (like the cough audio signal mentioned in the motivating example). The explanation dataset additionally contains a semantic description of the exemplars in terms that are understandable by humans (like “dry cough” mentioned in the motivating example). Taking the output of the unknown classifier (the classification class) for all the exemplars, we construct the Exemplar Data Classification information (see Fig. 1) thus we know the exact set of exemplars that are classified by the unknown classifier to a specific class (like the “seek medical advice” class mentioned in the motivating example). Using the knowledge represented in the Exemplar Data Semantic Description (see Fig. 1), we define the following reverse semantic query answering problem: “given a set of exemplars and their semantic description find intuitive and understandable semantic queries that have as certain answers exactly this set out of all the exemplars of the explanation dataset”. The specific problem is interesting, with certain difficulties and computationally very demanding [3,11,19,20,59]. Here, by extending a method presented in [48] we present an Explainer (see Fig. 1) that tries to solve this problem, following a Semantic Query Heuristic Search method, that searches in the Semantic Query Space (the set containing all queries that have non-empty certain answer set) for queries that are solutions to the above problem.

Fig. 1.

A framework for explaining opaque machine learning classifiers.

Introductory definitions and interesting theoretical results concerning the above approach are presented in [48]. Here, we reproduce some of them and introduce others, in order to develop the necessary framework for presenting the proposed method.

A defining aspect is that the rule explanations are provided in terms of a specific vocabulary. To do this in practice, we require a set of items (exemplar data) which can: a) be fed to a black-box classifier and b) have a semantic description using the desired terminology. As mentioned before, here we consider that: a) the exemplar data has for its items all the information that the unknown classifier needs in order to classify them (the necessary features), and b) the semantic data descriptions are expressed as Description Logics knowledge bases (see Fig. 1).

Definition 1 ([19]).

Let $\mathcal{D}$ be a domain of item feature data, $\mathcal{C}$ a set of classes, and $\mathcal{V}=⟨\mathsf{IN}\mathrm{,}\mathsf{CN}\mathrm{,}\mathsf{RN}⟩$ a vocabulary such that $\mathcal{C}\cup \{\mathsf{Exemplar}\}\subseteq \mathsf{CN}$ . Let also $\mathsf{EN}\subseteq \mathsf{IN}$ be a set of exemplars. An explanation dataset $\mathcal{E}$ in terms of $\mathcal{D}$ , $\mathcal{C}$ and $\mathcal{V}$ is a tuple $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ , where $\mathcal{M}:\mathsf{EN}\to \mathcal{D}$ is a mapping from the exemplars to the item feature data, and $\mathcal{S}=⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ is a DL knowledge base over $\mathcal{V}$ such that $\mathsf{Exemplar}\mathrm{(}\mathit{a}\mathrm{)}\in \mathcal{A}$ iff $\mathit{a}\in \mathsf{EN}$ , the elements of $\mathcal{C}$ do not appear in $\mathcal{S}$ , and $\mathsf{Exemplar}$ and the elements of $\mathsf{EN}$ do not appear in  $\mathcal{T}$ .

Intuitively, an explanation dataset contains a set of exemplar data (i.e. characteristic items in $\mathcal{D}$ which can be fed to the unknown classifier) semantically described in terms of a specific vocabulary $\mathcal{V}$ ; the semantic descriptions are in the knowledge base $\mathcal{S}$ . Each exemplar data item is represented in $\mathcal{S}$ by an individual name; these individual names make up the set of exemplars $\mathsf{EN}$ , and each one of them is mapped to the corresponding exemplar data item by $\mathcal{M}$ . Because the knowledge encoded in $\mathcal{S}$ may involve also other individuals, the $\mathsf{Exemplar}$ concept exists to identify exactly those individuals that correspond to exemplar data within the knowledge base. Given a classifier $\mathit{F}:\mathcal{D}\to \mathcal{C}$ and a set of individuals $\mathcal{I}\subseteq \mathsf{EN}$ , the positive set (pos-set) of F on $\mathcal{I}$ for class $\mathit{C}\in \mathcal{C}$ is $\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathcal{I}\mathrm{,}\mathit{C}\mathrm{)}=\{\mathit{a}\in \mathcal{I}:\mathit{F}\mathrm{(}\mathcal{M}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}=\mathit{C}\}$ . Based on the classifier’s prediction on the exemplar data for a class (i.e. the pos-set) we can produce explanation rules by grouping them according to their semantic description in the explanation dataset.

Definition 2 ([19]).

Let $\mathit{F}:\mathcal{D}\to \mathcal{C}$ be a classifier, $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ an explanation dataset in terms of a domain $\mathcal{D}$ and a set of classes $\mathcal{C}$ , and an appropriate vocabulary $\mathcal{V}=⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ (with $\mathcal{C}\subseteq \mathsf{CN}$ ). Given a concept $\mathit{C}\in \mathcal{C}$ , a connected rule of the form $$\begin{array}{c}\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}{\mathit{c}}_1\mathrm{,}{\mathit{c}}_2\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\to \mathit{C}\mathrm{(}\mathit{x}\mathrm{)}\end{array}$$ where ${\mathit{c}}_{\mathit{i}}$ is an atom $\mathit{D}\mathrm{(}\mathit{u}\mathrm{)}$ or $\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}$ , where $\mathit{D}\in \mathsf{CN}$ , $\mathit{r}\in \mathsf{RN}$ , and u, v are variables, is an explanation rule of F for class C over $\mathcal{E}$ . We denote the above rule by $\mathit{\rho }\mathrm{(}\mathit{F}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}$ , or simply by ρ whenever the context is clear. We may also omit $\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}$ from the body, since it is a conjunct of any explanation rule. The explanation rule ρ is correct if and only if $$\begin{array}{rl}\mathsf{FOL}\mathrm{(}\mathcal{S}& \cup \{\mathsf{Exemplar}⊑\underset{\mathit{a}\in \mathsf{EN}}{{\displaystyle ⨆}}\{\mathit{a}\}\}\cup \{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}|\mathit{a}\in \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}\left\}\mathrm{\right)}\vDash \mathit{\rho }\end{array}$$ where $\mathsf{FOL}\mathrm{(}\mathcal{K}\mathrm{)}$ is the first-order logic translation of the DL knowledge base $\mathcal{K}$ .

Note that in the above, the argument of $\mathsf{FOL}\mathrm{(}·\mathrm{)}$ is a KB, i.e. a set of DL axioms, in particular all axioms originally in S plus the technical axiom $\mathsf{Exemplar}⊑{⨆}_{\mathit{a}\in \mathsf{EN}}\{\mathit{a}\}$ , to force the interpretation of $\mathsf{Exemplar}$ to be contained in the interpretation of the elements of $\mathsf{EN}$ , and the assertions $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ . (Note that because $\mathsf{EN}$ is a set of individuals, the expression ${⨆}_{\mathit{a}\in \mathsf{EN}}\{\mathit{a}\}$ makes use of the union and nominal DL constructors (one-of constructor) to form a concept by enumerating its members.)

Explanation rules describe sufficient conditions (the body of the rule) for an item to be classified in the class indicated at the head of the rule by the classifier under investigation. The correctness of a rule indicates that the rule covers every $\mathit{a}\in \mathsf{EN}$ , meaning that for each exemplar of $\mathcal{S}$ , either the body of the rule is not true, or both the body and the head of the rule are true. Of course we cannot know if the classifier is using the particular semantics, however, depending on the explanation dataset, explanation rules can provide useful information that can indicate potential biases of the classifier, that are expressed in the desired terminology.

Example 1.

Suppose we have the problem described in the motivating example of Section 3.1 with black-box classifiers predicting whether a person should seek medical advice based on audios of their cough, and that we are creating an explanation dataset in order to explain the respective classifiers. The vocabulary used should be designed so that it will produce meaningful explanations to the end-user, which in our case would probably be a doctor or another professional of the medical domain. In this case, it should contain concepts for the different medical terms like the findings (cough, sore throat, etc.), and according to the definition of the explanation dataset, the class categories (seek medical advice, or not) and the concept $\mathsf{Exemplar}$ as concept names ( $\mathsf{CN}$ ). Additionally, a role linking patients to the respective findings should exist in the role names ( $\mathsf{RN}$ ), and the patients as well as the findings themselves would be the individual names ( $\mathsf{IN}$ ). Following this, we create the vocabulary ( $\mathcal{V}$ ) as shown below: $$\begin{array}{c}\mathsf{IN}=\{\mathsf{p}\mathsf{1}\mathrm{,}\mathsf{p}\mathsf{2}\mathrm{,}\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}\mathrm{,}\mathsf{s}\mathsf{1}\mathrm{,}\mathsf{s}\mathsf{2}\mathrm{,}\mathsf{s}\mathsf{3}\mathrm{,}\mathsf{s}\mathsf{4}\mathrm{,}\mathsf{s}\mathsf{5}\mathrm{,}\mathsf{s}\mathsf{6}\mathrm{,}\mathsf{s}\mathsf{7}\mathrm{,}\mathsf{s}\mathsf{8}\}\\ \begin{array}{rl}\mathsf{CN}=& \{\mathsf{DryCough}\mathrm{,}\mathsf{LooseCough}\mathrm{,}\mathsf{Cough}\mathrm{,}\mathsf{SoreThroat}\mathrm{,}\mathsf{LungFinding}\mathrm{,}\mathsf{Finding}\mathrm{,}\mathsf{Dyspnoea}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{,}\\ & \mathsf{NoMedicalAdvice}\mathrm{,}\mathsf{Exemplar}\}\end{array}\\ \mathsf{RN}=\{\mathsf{hasFinding}\}\end{array}$$ Having the domain $\mathcal{D}$ (audio signals), the set of classes $\mathcal{C}$ ( $\mathsf{MedicalAdvice}\mathrm{,}\mathsf{NoMedicalAdvice}$ ), and the vocabulary $\mathcal{V}$ we can now define the explanation dataset $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ . The set of exemplars ( $\mathsf{EN}$ ) in our case contains the patient individuals of $\mathsf{IN}$ , so $\mathsf{EN}=\{\mathsf{p}\mathsf{1}\mathrm{,}\mathsf{p}\mathsf{2}\mathrm{,}\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}\}$ . The mapping $\mathcal{M}$ of the explanation dataset links these exemplars to the respective audio of each patient. The only thing that is missing from our explanation dataset is the knowledge base $\mathcal{S}$ consisting of an ABox $\mathcal{A}$ and a TBox $\mathcal{T}$ . The ABox contains information regarding the patient audio characterizations from the medical professionals (“ $\mathsf{p}\mathsf{1}$ has a sore throat”, “ $\mathsf{p}\mathsf{2}$ has dyspnoea”, “ $\mathsf{p}\mathsf{3}$ has a sore throat and dyspnoea”, “ $\mathsf{p}\mathsf{4}$ has a sore throat and a dry cough”, “ $\mathsf{p}\mathsf{5}$ has a sore throat and a loose cough”) as well as the assertions regarding the exemplar status of individuals, while the TBox contains relationships between the medical terms as defined in SNOMED-CT, as shown below: $$\begin{array}{c}\begin{array}{rl}\mathcal{A}=& \{\mathsf{Exemplar}\mathrm{(}\mathsf{p}\mathsf{1}\mathrm{)}\mathrm{,}\mathsf{Exemplar}\mathrm{(}\mathsf{p}\mathsf{2}\mathrm{)}\mathrm{,}\mathsf{Exemplar}\mathrm{(}\mathsf{p}\mathsf{3}\mathrm{)}\mathrm{,}\mathsf{Exemplar}\mathrm{(}\mathsf{p}\mathsf{4}\mathrm{)}\mathrm{,}\mathsf{Exemplar}\mathrm{(}\mathsf{p}\mathsf{5}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{1}\mathrm{,}\mathsf{s}\mathsf{1}\mathrm{)}\mathrm{,}\\ & \mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{2}\mathrm{,}\mathsf{s}\mathsf{2}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{s}\mathsf{3}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{s}\mathsf{4}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{s}\mathsf{5}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{s}\mathsf{6}\mathrm{)}\mathrm{,}\\ & \mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{5}\mathrm{,}\mathsf{s}\mathsf{7}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathsf{p}\mathsf{5}\mathrm{,}\mathsf{s}\mathsf{8}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathsf{s}\mathsf{1}\mathrm{)}\mathrm{,}\mathsf{Dyspnoea}\mathrm{(}\mathsf{s}\mathsf{2}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathsf{s}\mathsf{3}\mathrm{)}\mathrm{,}\\ & \mathsf{Dyspnoea}\mathrm{(}\mathsf{s}\mathsf{4}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathsf{s}\mathsf{5}\mathrm{)}\mathrm{,}\mathsf{DryCough}\mathrm{(}\mathsf{s}\mathsf{6}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathsf{s}\mathsf{7}\mathrm{)}\mathrm{,}\mathsf{LooseCough}\mathrm{(}\mathsf{s}\mathsf{8}\mathrm{)}\}\end{array}\\ \begin{array}{rl}\mathcal{T}=& \{\mathsf{LooseCough}⊑\mathsf{Cough}\mathrm{,}\mathsf{DryCough}⊑\mathsf{Cough}\mathrm{,}\mathsf{Cough}⊑\mathsf{LungFinding}\mathrm{,}\mathsf{LungFinding}⊑\mathsf{Finding}\mathrm{,}\\ & \mathsf{Dyspnoea}⊑\mathsf{LungFinding}\mathrm{,}\mathsf{SoreThroat}⊑\mathsf{Finding}\}\end{array}\end{array}$$ Now suppose that a black-box classifier F predicts that $\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}$ , and $\mathsf{p}\mathsf{5}$ should seek medical advice, while $\mathsf{p}\mathsf{1}$ and $\mathsf{p}\mathsf{2}$ do not need to (same as the motivating example of Section 3.1). The explanation rule $$\begin{array}{c}{\mathit{\rho }}_1:\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{z}\mathrm{)}\mathrm{,}\mathsf{LungFinding}\mathrm{(}\mathit{z}\mathrm{)}\to \mathsf{MedicalAdvice}\mathrm{(}\mathit{x}\mathrm{)}\end{array}$$ for that classifier based on the explanation dataset $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ is a correct rule, as well as the explanation rule $$\begin{array}{c}{\mathit{\rho }}_2:\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{Cough}\mathrm{(}\mathit{y}\mathrm{)}\to \mathsf{MedicalAdvice}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\end{array}$$ while the rules $$\begin{array}{c}{\mathit{\rho }}_3:\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathit{y}\mathrm{)}\to \mathsf{MedicalAdvice}\mathrm{(}\mathit{x}\mathrm{)}\text{and}\\ {\mathit{\rho }}_4:\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{Dyspnea}\mathrm{(}\mathit{y}\mathrm{)}\to \mathsf{MedicalAdvice}\mathrm{(}\mathit{x}\mathrm{)}\end{array}$$ are not correct, since $\mathsf{FOL}\mathrm{(}{\mathcal{S}}^{\prime }\mathrm{)}\vDash {\mathit{\rho }}_1$ and $\mathsf{FOL}\mathrm{(}{\mathcal{S}}^{\prime }\mathrm{)}\vDash {\mathit{\rho }}_2$ , but $\mathsf{FOL}\mathrm{(}{\mathcal{S}}^{\prime }\mathrm{)}⊭{\mathit{\rho }}_3$ and $\mathsf{FOL}\mathrm{(}{\mathcal{S}}^{\prime }\mathrm{)}⊭{\mathit{\rho }}_4$ , where ${\mathcal{S}}^{\prime }=\mathcal{S}\cup \{\mathsf{Exemplar}⊑\{\mathit{a}|\mathit{a}\in \mathsf{EN}\}\cup \{\mathsf{MedicalAdvice}\mathrm{(}\mathit{a}\mathrm{)}|\mathit{a}\in \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{)}\}$ .

As mentioned in Section 2, a SAV query is an expression of the form $\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}$ , an expression that resembles the body of explanation rules. By treating the bodies of explanation rules as queries, the problem of computing explanations can be solved as a query reverse engineering problem [19].

Definition 3 ([19]).

Let $\mathit{F}:\mathcal{D}\to \mathcal{C}$ be a classifier, $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ an explanation dataset in terms of $\mathcal{D}$ , $\mathcal{C}$ and an appropriate vocabulary $\mathcal{V}$ , and $\mathit{\rho }\mathrm{(}\mathit{F}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}$ : $\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}{\mathit{c}}_1\mathrm{,}{\mathit{c}}_2\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\to \mathit{C}\mathrm{(}\mathit{x}\mathrm{)}$ an explanation rule. The SAV query $$\begin{array}{c}{\mathit{q}}_{\mathit{\rho }}\doteq \{\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}{\mathit{c}}_1\mathrm{,}{\mathit{c}}_2\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}\end{array}$$ is the explanation rule query of explanation rule ρ.

This query reverse engineering problem follows the Query by Example paradigm or QbE. This term refers to reverse engineering queries that contain some positive examples in their answer set but not any negative examples and is widely used in the related literature [7,17,32,36,51,56,85]. We give a short formal definition of QbE adapted from [56].

Definition 4 (Query by Example).

Given a DL knowledge base $\mathcal{S}=⟨\mathit{T}\mathrm{,}\mathit{A}⟩$ , two sets ${\mathit{S}}^{+}\mathrm{,}{\mathit{S}}^{-}\subseteq \mathsf{IN}$ and a query language $\mathcal{Q}$ . Is there a query $\mathit{q}\in \mathcal{Q}$ such that ${\mathit{S}}^{+}\subseteq \mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}$ and ${\mathit{S}}^{-}\cap \mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}=\varnothing$ ?

In our case, ${\mathit{S}}^{+}$ would be $\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ and ${\mathit{S}}^{-}=\mathsf{EN}\setminus \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ , while $\mathcal{Q}$ , the language of conjunctive queries.

The relationship between the properties of explanation rules and the respective queries allows us to detect and compute correct rules based on the certain answers of the respective explanation rule queries, as shown in Theorem 1.

Theorem 1 ([19]).

Let $\mathit{F}:\mathcal{D}\to \mathcal{C}$ be a classifier, $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ an explanation dataset in terms of $\mathcal{D}$ , $\mathcal{C}$ and an appropriate vocabulary $\mathcal{V}$ , $\mathit{\rho }\mathrm{(}\mathit{F}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}$ : $\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}{\mathit{c}}_1\mathrm{,}{\mathit{c}}_2\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\to \mathit{C}\mathrm{(}\mathit{x}\mathrm{)}$ an explanation rule, and ${\mathit{q}}_{\mathit{\rho }}$ the explanation rule query of ρ. The explanation rule ρ is correct if and only if $$\begin{array}{c}\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}\mathcal{S}\mathrm{)}\subseteq \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}\end{array}$$

Proof.

Let $\mathcal{S}=⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ . Because by definition $\mathsf{Exemplar}\mathrm{(}\mathit{a}\mathrm{)}\in \mathcal{A}$ iff $\mathit{a}\in \mathsf{EN}$ and $\mathsf{Exemplar}$ does not appear anywhere in $\mathcal{T}$ , we have $$\begin{array}{rl}\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}\mathcal{S}\mathrm{)}& =\mathsf{cert}\mathrm{(}\{\mathsf{Exemplar}\mathrm{,}{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}\mathrm{,}⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩\mathrm{)}\\ & =\mathsf{EN}\cap \mathsf{cert}\mathrm{(}\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}\mathrm{,}⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩\mathrm{)}\\ & =\mathsf{cert}\mathrm{(}\{\mathsf{Exemplar}\}\mathrm{,}⟨\{\mathsf{Exemplar}⊑\underset{\mathit{a}\in \mathsf{EN}}{{\displaystyle ⨆}}\{\mathit{a}\}\}\mathrm{,}\mathcal{A}⟩\mathrm{)}\cap \mathsf{cert}\mathrm{(}\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}\mathrm{,}⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩\mathrm{)}\\ & =\mathsf{cert}\mathrm{(}\{\mathsf{Exemplar}\mathrm{,}{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}\mathrm{,}⟨\mathcal{T}\cup \{\mathsf{Exemplar}⊑\underset{\mathit{a}\in \mathsf{EN}}{{\displaystyle ⨆}}\{\mathit{a}\}\}\mathrm{,}\mathcal{A}⟩\mathrm{)}\\ & =\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}⟨\mathcal{T}\cup \{\mathsf{Exemplar}⊑\underset{\mathit{a}\in \mathsf{EN}}{{\displaystyle ⨆}}\{\mathit{a}\}\}\mathrm{,}\mathcal{A}⟩\mathrm{)}\end{array}$$

Because by definition C does not appear anywhere in $\mathcal{S}$ ), we have also that $\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}\mathcal{S}\mathrm{)}=\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}{\mathcal{S}}^{\prime }\mathrm{)}$ , where ${\mathcal{S}}^{\prime }=\mathcal{S}\cup \{\mathsf{Exemplar}⊑{⨆}_{\mathit{a}\in \mathsf{EN}}\{\mathit{a}\}\}\cup \{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}|\mathit{a}\in \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}\}\}$ , since the assertions $\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}$ are not involved neither in the query nor in $\mathcal{S}$ and hence have no effect.

By definition of a certain answer, $\mathit{e}\in \mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{K}\mathrm{)}$ iff for every model $\mathcal{I}$ of $\mathcal{K}$ there is a match π s.t. $\mathit{\pi }\mathrm{(}\mathit{x}\mathrm{)}={\mathit{e}}^{\mathcal{I}}$ and $\mathit{\pi }\mathrm{(}\mathit{u}\mathrm{)}\in {\mathit{D}}^{\mathcal{I}}$ for all $\mathit{D}\mathrm{(}\mathit{u}\mathrm{)}\in \mathit{q}$ and $\mathrm{(}\mathit{\pi }\mathrm{(}\mathit{u}\mathrm{)}\mathrm{,}\mathit{\pi }\mathrm{(}\mathit{v}\mathrm{)}\mathrm{)}\in {\mathit{r}}^{\mathcal{I}}$ for all $\mathit{r}\mathrm{(}\mathit{u}\mathrm{,}\mathit{v}\mathrm{)}\in \mathit{q}$ .

Assume that ρ is correct and let $\mathit{e}\in \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}\mathcal{S}\mathrm{)}$ . We have proved that also $\mathit{e}\in \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}{\mathcal{S}}^{\prime }\mathrm{)}$ . Because ρ is correct, by Def. 3 it follows that every model $\mathcal{I}$ of ${\mathcal{S}}^{\prime }$ is also a model of ρ. Because the body of ${\mathit{q}}_{\mathit{\rho }}$ is the same as the body of ρ, π makes true both the body of ρ and the head of ρ, which is $\mathit{C}\mathrm{(}\mathit{x}\mathrm{)}$ , hence ${\mathit{e}}^{\mathcal{I}}\in {\mathit{C}}^{\mathcal{I}}$ . It follows that $\mathit{C}\mathrm{(}\mathit{e}\mathrm{)}$ is true in $\mathcal{I}$ . But the only assertions of the form $\mathit{C}\mathrm{(}\mathit{e}\mathrm{)}$ in ${\mathcal{S}}^{\prime }$ are the assertions $\{\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}|\mathit{a}\in \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}\}$ , thus $\mathit{e}\in \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ .

For the inverse, assume that $\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}\mathcal{S}\mathrm{)}\subseteq \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ , equivalently $\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}{\mathcal{S}}^{\prime }\mathrm{)}\subseteq \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ . Thus if $\mathit{e}\in \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{\rho }}\mathrm{,}\mathcal{S}\mathrm{)}$ then ${\mathit{e}}^{\mathcal{I}}\in {\mathit{C}}^{\mathcal{I}}$ . Since this holds for every model $\mathcal{I}$ of ${\mathcal{S}}^{\prime }$ and the body of ${\mathit{q}}_{\mathit{\rho }}$ is the same as the body of ρ, it follows that $\mathcal{I}$ is also a model of ρ, i.e. ρ is correct.  □

Theorem 1 shows a useful property of the certain answers of the explanation rule query of a correct rule ( $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\subseteq \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ ) that can be utilized in order to identify and produce correct rules. Intuitively, an explanation rule is correct, if all of the certain answers of the respective explanation rule query are mapped by $\mathcal{M}$ to data which is classified in the class indicated at the head of the rule. However, it is obvious that according to the above we can have correct rules that barely approximate the behaviour of the classifier (e.g. an explanation rule query with only one certain answer that is in the pos-set of the classifier), while other correct rules might exactly match the output of the classifier (e.g. a query q for which $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}=\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ ). Thus, it is useful to define a recall metric for explanation rule queries by comparing the set of certain answers with the pos-set of a class C: $$\begin{array}{c}\mathsf{recall}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}={\displaystyle \frac{|\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\cap \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}|}{|\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}|}}\mathrm{,}\end{array}$$ assuming that $\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}\ne \varnothing$ .

Example 2.

Continuing Example 1, we can create the explanation rule queries of the respective explanation rules of the example as follows: ${\mathit{q}}_1\mathrm{(}\mathit{x}\mathrm{)}=\{\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{z}\mathrm{)}\mathrm{,}\mathsf{LungFinding}\mathrm{(}\mathit{z}\mathrm{)}\}$ as the explanation rule query of ${\mathit{\rho }}_1$ , ${\mathit{q}}_2\mathrm{(}\mathit{x}\mathrm{)}=\{\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{Cough}\mathrm{(}\mathit{y}\mathrm{)}\}$ as the explanation rule query of ${\mathit{\rho }}_2$ , ${\mathit{q}}_3\mathrm{(}\mathit{x}\mathrm{)}=\{\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}\mathit{y}\mathrm{)}\}$ as the explanation rule query of ${\mathit{\rho }}_3$ , and ${\mathit{q}}_4\mathrm{(}\mathit{x}\mathrm{)}=\{\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}\mathrm{,}\mathsf{Dyspnoea}\mathrm{(}\mathit{y}\mathrm{)}\}$ as the explanation rule query of ${\mathit{\rho }}_4$ .

For the above queries we can retrieve their certain answers over our knowledge base $\mathcal{S}$ , and get $\mathsf{cert}\mathrm{(}{\mathit{q}}_1\mathrm{,}\mathcal{S}\mathrm{)}=\{\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}\}$ , $\mathsf{cert}\mathrm{(}{\mathit{q}}_2\mathrm{,}\mathcal{S}\mathrm{)}=\{\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}\}$ , $\mathsf{cert}\mathrm{(}{\mathit{q}}_3\mathrm{,}\mathcal{S}\mathrm{)}=\{\mathsf{p}\mathsf{1}\mathrm{,}\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}\}$ , and $\mathsf{cert}\mathrm{(}{\mathit{q}}_4\mathrm{,}\mathcal{S}\mathrm{)}=\{\mathsf{p}\mathsf{2}\mathrm{,}\mathsf{p}\mathsf{3}\}$ .

With respect to the classifier F of Example 1, for which $\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{)}=\{\mathsf{p}\mathsf{3}\mathrm{,}\mathsf{p}\mathsf{4}\mathrm{,}\mathsf{p}\mathsf{5}\}$ , we see, as the theorem states, that for the correct rules ${\mathit{\rho }}_1$ and ${\mathit{\rho }}_2$ it holds that $\mathsf{cert}\mathrm{(}{\mathit{q}}_1\mathrm{,}\mathcal{S}\mathrm{)}\subseteq \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{)}$ and $\mathsf{cert}\mathrm{(}{\mathit{q}}_2\mathrm{,}\mathcal{S}\mathrm{)}\subseteq \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{)}$ , while for rules ${\mathit{\rho }}_3$ and ${\mathit{\rho }}_4$ that are not correct, it holds that $\mathsf{cert}\mathrm{(}{\mathit{q}}_3\mathrm{,}\mathcal{S}\mathrm{)}⊈\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{)}$ , and $\mathsf{cert}\mathrm{(}{\mathit{q}}_4\mathrm{,}\mathcal{S}\mathrm{)}⊈\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathsf{MedicalAdvice}\mathrm{)}$ , respectively.

The explanation framework described in this section provides the necessary expressivity to formulate accurate rules, using a desired terminology, even for complex problems [19]. However, some limitations of the framework, like only working with correct rules, can be a significant drawback for explanation methods built on top of that. An explanation rule query might not be correct due to the existence of individuals in the set of certain answers which are not in the pos-set. By viewing these individuals as exceptions to a rule, we are able to provide as an explanation a rule that is not correct, along with the exceptions which would make it correct if they were omitted from the explanation dataset; the exceptions could provide useful information to an end-user about the classifier under investigation. Thus, we extend the existing framework by introducing correct explanation rules with exceptions, as follows:

Definition 5.

Let $\mathit{F}:\mathcal{D}\to \mathcal{C}$ be a classifier, $\mathcal{E}=⟨\mathcal{M}\mathrm{,}\mathcal{S}⟩$ an explanation dataset in terms of $\mathcal{D}$ ,  $\mathcal{C}$ where $\mathcal{S}$ is a knowledge base $\mathcal{S}=⟨\mathcal{A}\mathrm{,}\mathcal{T}⟩$ , $\mathsf{EN}$ the set of exemplars of $\mathcal{E}$ , and let $\mathsf{EX}$ be a subset of $\mathsf{EN}$ . An explanation rule $\mathit{\rho }\mathrm{(}\mathit{F}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}$ is correct with exceptions $\mathsf{EX}$ for class C if the rule $\mathit{\rho }\mathrm{(}\mathit{F}\mathrm{,}{\mathcal{E}}^{\prime }\mathrm{,}\mathit{C}\mathrm{)}$ is correct for class C, where ${\mathcal{E}}^{\prime }=⟨\mathcal{M}\mathrm{,}{\mathcal{S}}^{\prime }⟩$ , and ${\mathcal{S}}^{\prime }$ is the knowledge base ${\mathcal{S}}^{\prime }=⟨{\mathcal{A}}^{\prime }\mathrm{,}\mathcal{T}⟩$ , and ${\mathcal{A}}^{\prime }=\mathcal{A}\setminus \{\mathsf{Exemplar}\mathrm{(}\mathit{a}\mathrm{)}|\mathit{a}\in \mathsf{EX}\}$ .

Since we allow exceptions to explanation rules, it is useful to define a measure of precision of the corresponding explanation rule queries as $$\begin{array}{c}\mathsf{precision}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}={\displaystyle \frac{|\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\cap \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}|}{|\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}|}}\end{array}$$ if $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\ne \varnothing$ and $\mathsf{precision}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}=0$ otherwise.

Obviously, if the precision of a rule query is 1, then it represents a correct rule, otherwise it is correct with exceptions. Furthermore, we can use the Jaccard similarity between the set of certain answers of the explanation rule query and the pos-set, as a generic measure which combines $\mathsf{recall}$ and $\mathsf{precision}$ to compare the two sets of interest as: $$\begin{array}{c}\mathsf{degree}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{E}\mathrm{,}\mathit{C}\mathrm{)}={\displaystyle \frac{|\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\cap \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}|}{|\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\cup \mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}|}}.\end{array}$$

Example 3.

The rules ${\mathit{\rho }}_3$ and ${\mathit{\rho }}_4$ of Example 2 that are not correct; they are correct with exceptions. Table 3 shows the precision, recall, and degree metrics of the explanation rule queries of Example 2 along with the exceptions $\mathsf{EX}$ of the respective rules.

Table 3

Metrics and exceptions of the example explanation rules and the respective explanation rule queries

Rule	Query	Recall	Precision	Degree	Exceptions ( $\mathsf{EX}$ )
${\mathit{\rho }}_1$	${\mathit{q}}_1$	1.0	1.0	1.0	{}
${\mathit{\rho }}_2$	${\mathit{q}}_2$	0.67	1.0	0.67	{}
${\mathit{\rho }}_3$	${\mathit{q}}_3$	1.0	0.75	0.75	{p1}
${\mathit{\rho }}_4$	${\mathit{q}}_4$	0.33	0.5	0.25	{p2}

It can often be useful to present a set of rules to the end user instead of a single one. This could be, for example, because the pos-set cannot be captured by a single correct rule but only by a set of correct rules. This is a strategy commonly employed by other rule based systems such as those we employed in Section 5 to compare our algorithms to, namely RuleMatrix [53] and Skope-Rules [80]. The metrics already defined for a single query can be expanded to a set of queries $\mathit{Q}=\{{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{,}\dots {\mathit{q}}_{\mathit{n}}\}$ , by simply expanding the definition of certain answers for a set of queries to $\mathsf{cert}\mathrm{(}\mathit{Q}\mathrm{,}\mathcal{S}\mathrm{)}={\bigcup }_{\mathit{i}=1}^{\mathit{n}}\mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{i}}\mathrm{,}\mathcal{S}\mathrm{)}$ .

As we have previously mentioned, we do not have any formal guarantees that the semantics expressed in the explanations extracted by the reverse engineering process are linked to the ones used by the classifier. In [63] the author proposes the term “summary of predictions” for approaches such as ours, that are independent of the classifier features, and the explanations are produced by summarizing the predictions of the classifier. We nevertheless use the term explanation to be consistent with the existing literature. The measures we defined in this section provide some confidence about the existence of a link between the semantics of the classifier and those of the explanations. Assuming that the explanations produced are of high quality (high precision, low recall, short in length) and that the explanation dataset is constructed in a way that takes into account possible biases, it is reasonable to assume that there is at least some correlation between the semantics that the explanation presents with those that the classifier is using.

Unfortunately, as the semantic descriptions become richer, it is more likely that a query that perfectly separates the positive and negative individuals exists since the space of queries that can be expressed using the vocabulary of the descriptions becomes larger. This could lead to rules with high precision (and possibly high degree) that do not hold for new examples which could be perceived as a form of overfitting. This resembles the curse of dimensionality of machine learning, where the plethora of features leads to overfitting models when there is a lack of sufficient data. It would be helpful to have some statistical measures after the reverse engineering process that express how likely it is that the query(ies) perform well by coincidence, rather than due to a link between the semantics expressed in the explanation dataset and the ones used by the classifier. Computing such measures is far from trivial due to the complex structure of the Query Space [19]. In this work, we employ some alternatives in our experiments. Namely, using a holdout set in order to check how well the rules produced generalize (Mushrooms experiment, Section 5.1), and employing other XAI methods to cross-reference the explanations produced (Visual Genome experiment, Section 5.3). We consider a thorough examination of such methods to be out of the scope of this work.

4. Computation of explanations

From Section 3, we understand that the problem that we try to solve is closely related to the query reverse engineering problem, since we need to compute queries given a set of individuals. However, since in most cases there is not a single query that fits our needs (have as certain answers the pos-set of the classifier), we need to find (out of all the semantic queries that have a specific certain answer set) a set of queries that accurately describe the classifier under investigation. Therefore, the problem can also be seen as a heuristic search problem. The duality of rules and queries within our framework, reduces the search of correct rules (with exceptions) to the search of queries that contain elements of the pos-set in their certain answers. Reverse engineering queries for subsets of $\mathsf{EN}$ is challenging for the following reasons:

The subsets of $\mathsf{EN}$ for which there exists a correct rule query ( $\{\mathit{I}|\mathit{I}\subseteq \mathsf{EN}\mathrm{,}\text{there exists }\mathit{q}\text{ s.t. }\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}=\mathit{I}\}$ ) can potentially be exponentially many ( $2^{|\mathsf{EN}|}$ ).

The Query Space i.e. the set containing all queries that have non-empty certain answer set ( $\{\mathit{q}|\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}\cap \mathsf{EN}\ne \varnothing \}$ ) can potentially be infinite [19].

For any subset I of $\mathsf{EN}$ , the number of queries s.t. $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}=\mathit{I}$ can be zero, positive or infinite.

Computing the certain answers of arbitrary queries can be exponentially slow, so it is computationally prohibitive to evaluate each query under consideration while exploring the query space.

The difficulties described above are addressed in the following ways:

• In this paper, we only consider knowledge bases of which the TBox can be eliminated (such as RL [38]; see also the last paragraph of this section). This enables us to create finite queries that contain all the necessary conjuncts to fully describe each individual. We are then able to merge those queries to create descriptions of successively larger subsets of $\mathsf{EN}$ .

• We do not directly explore the subsets of $\mathsf{EN}$ for which there exists a correct rule query, and the computation of certain answers is not required for the algorithms. Instead, we explore the Query Space blindly, but heuristically. We create queries that are guaranteed to be within the Query Space and are also guaranteed to contain heuristically selected individuals in their certain answers, without knowing their exact certain answers. The heuristic we employ, aids us in selecting similar individuals to merge. Intuitively, this helps us create queries that introduce as few as possible unwanted certain answers.

• We are not concerned with the entire set of queries with non-empty sets of certain answers, but only with queries which have specific characteristics in order to be used as explanations. Specifically, the queries have to be short in length, with no redundant conjuncts, have as certain answers elements of the pos-set of the class under investigation, and as few others as possible.

• One of the proposed algorithms guarantees that given a set I, if a query q exists s.t. $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{S}\mathrm{)}=\mathit{I}$ , then it will find at least one such query. If there do not exist such queries then, since the computation of certain answers is not involved in the algorithms, the result of the heuristic search will be a “good guess” of queries which have similar certain answer sets to I. If there exist infinite such queries, then we do not have a guarantee that we have found the shortest, most understandable one, however the proposed algorithms take care to create queries with few variables (see Alg. 2 and Section 4.3.2).

In the following we describe the proposed algorithms for computing explanations. The core algorithm, which is outlined as Alg. 1 and we call KGrules-H, takes as input an atomic ABox $\mathcal{A}$ and a set of individual names I, and produces a list of queries. It is assumed that both $\mathcal{A}$ and I are obtained from an explanation dataset $\mathcal{E}$ . In particular, I is a subset of the respective $\mathsf{EN}$ corresponding to a pos-set of a classifier F to be explained for some class C, i.e. $\mathsf{pos}\mathrm{(}\mathit{F}\mathrm{,}\mathsf{EN}\mathrm{,}\mathit{C}\mathrm{)}$ , and $\mathcal{A}$ is an atomic ABox containing all the available knowledge about the individuals in I encoded in the knowledge base of $\mathcal{E}$ . The output queries are intended to serve as explanation rule queries for class C. An outline of how KGrules-H is used to generate explanations is shown in Fig. 2.

Algorithm 1:

KGRules-H

Fig. 2.

Visualization of how KGrules-H is integrated into our framework.

The algorithm starts by initializing an empty list of queries S, and by creating an initial description for each individual in I in the form of a most specific query (MSQ). A detailed definition of a MSQ is given in Section 4.1; intuitively, an MSQ of an individual a for an ABox $\mathcal{A}$ is a SAV query q that captures the maximum possible information about a and is such that $\mathit{a}\in \mathsf{cert}\mathrm{(}\mathsf{MSQ}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}\mathrm{)}$ . Given these descriptions, one for each individual, which are added in a set L, the algorithm then tries to combine the elements of L in order to generate more general descriptions. In particular, at each iteration of the while loop, it selects two queries from L and merges them. The queries to be merged are selected based on their dissimilarity; two most similar queries are selected and merged. The intuition is that by merging relatively similar queries, the resulting queries will continue to be “as specific as possible” since they will generalize out the limited dissimilarities of the original queries. In Section 4.2 we discuss how dissimilarity is estimated, and in Section 4.3 we describe two alternative approaches for merging queries. Given two queries ${\mathit{q}}_{\mathit{A}}$ , ${\mathit{q}}_{\mathit{B}}$ that have been selected as most similar, the algorithm merges them by constructing a new SAV query $\mathit{q}=\mathsf{Merge}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}{\mathit{q}}_{\mathit{B}}\mathrm{)}$ such that $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}\supseteq \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}\mathcal{A}\mathrm{)}\cup \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{B}}\mathrm{,}\mathcal{A}\mathrm{)}$ . The newly created query replaces the ones it was merged from in L, and is also appended to S. Once the queries to be merged have been exhausted, Alg. 1 terminates by returning the list S which will contain $|\mathit{I}|-1$ SAV queries, the results of each merging step in order of creation. Thus, the queries can be considered to be in S in some decreasing order of “specificness”, although the actual order depends on the order the elements in L are considered.

If the queries in S have subsets of I as their certain answers, given that we have assumed that I is the pos-set of a classifier for some class C, the queries can be treated as candidate explanation rule queries for C. In this case, the queries can be interpreted as explanation rule queries, converted to the respective explanation rules, and presented as explanations. In general, however, there is no guarantee that the certain answers of a merged query will be a subset of I. In this case, which is the typical case, the computed explanation rules will be rules with exceptions. The queries produced will differ with respect to the metrics introduced in Section 3. Specifically, the queries produced early on, which are the result of few merges are expected to have low recall but high precision, with the inverse holding for queries produced in the later iterations. The importance placed on each metric can be different for each end user, therefore there is no single best query produced by Alg. 1. Instead, metrics for each query should be produced and presented to the end user to let them rank the explanations according to their preferences. This is the methodology we have employed in Section 5. For each experiment conducted we present a selection of queries, each performing better for a different metric.

In Section 4.3 we prove some optimality results for one of the merging methods, the query least common subsumer (QLCS). In particular, if there is a correct explanation rule (without exceptions), then we are guaranteed to find the corresponding explanation rule query, using the QLCS. This optimality property does not hold for the Greedy Matching operation defined in Section 4.3.2, nor for Alg. 3.

As mentioned above, Alg. 1 works on the assumption that all available knowledge about the relevant individuals I is encoded in a (finite) atomic ABox $\mathcal{A}$ . This is essential for the computation of the MSQs. Given that the knowledge base associated with an explanation dataset is in general of the form $⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ , this assumption means that if the original knowledge involves a non-empty TBox $\mathcal{T}$ , it has to be eliminated before applying Alg. 1. In particular, TBox elimination is the process of expanding a given ABox by applying the axioms of a given TBox, so that the TBox in eventually not needed, in the sense that all certain answers of the original knowledge can now be obtained only from the expanded ABox. Because TBox elimination is not alwayws possible, this poses certain restrictions on the applicability of Alg. 1, namely that if the original knowledge of the explanation dataset is indeed of the form $⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ with $\mathcal{T}\ne \varnothing$ , it should be possible, as outlined above, to be transformed through TBox elimination to an equivalent w.r.t. query answering finite assertional-only knowledge base ${\mathcal{A}}^{\prime }$ , such that $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩\mathrm{)}=\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}⟨\varnothing \mathrm{,}{\mathcal{A}}^{\prime }⟩\mathrm{)}$ for any q. For knowledge bases that this is possible, the standard approach for TBox elimination is materialization and is typically performed by first encoding the axioms in $\mathcal{T}$ as a set of inference rules generating ABox assertions, and then iteratively applying them on the knowledge base until no more assertions can be generated. Materialization is possible, e.g. for Description Logic Programs and the Horn- $\mathcal{SHIQ}$ DL dialect. Finite materialization may not be possible even for low expressivity DL dialects, such as DL-Lite. [25,37]

4.1. Most specific queries

As mentioned above, intuitively, a most specific query (MSQ) of an individual a for an atomic ABox $\mathcal{A}$ encodes the maximum possible information about a provided by $\mathcal{A}$ . It is defined as a least query in terms of subsumption which has a as a certain answer; in particular, a query q is a MSQ of an individual a for an atomic ABox $\mathcal{A}$ iff $\mathit{a}\in \mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}$ and for all ${\mathit{q}}^{\prime }$ such that $\mathit{a}\in \mathsf{cert}\mathrm{(}{\mathit{q}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{)}$ we have $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ .

Following the subsumption properties, MSQs are unique up to syntactical equivalence. In Alg. 1 it is assumed that $\mathsf{MSQ}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ represents one such MSQ of a for $\mathcal{A}$ . Since $\mathcal{A}$ is finite, a MSQ is easy to compute. This can be done by viewing $\mathcal{A}$ as a graph, taking the connected component of that graph that contains node a, and converting it into a graph representing a query by replacing all nodes (which in the original graph represent individuals) by arbitrary, distinct variables, taking care to replace node a by variable x.

Theorem 2.

Let $\mathcal{A}$ be a finite atomic ABox over a vocabulary $⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ , a an individual in $\mathsf{IN}$ , and $\mathsf{conn}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ the connected component of the ABox graph of $\mathcal{A}$ containing a. Let also q be a SAV query with query graph G. If there exists an isomorphism $\mathit{f}:\mathit{G}\to \mathsf{conn}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ such that $\mathit{f}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{a}$ , then q is an MSQ of a for  $\mathcal{A}$ .

Proof.

Let $\mathcal{I}$ be the interpretation such that ${\mathrm{\Delta }}^{\mathcal{I}}=\mathsf{IN}$ , ${\mathit{a}}^{\mathcal{I}}=\mathit{a}$ for all $\mathit{a}\in \mathsf{IN}$ , ${\mathit{C}}^{\mathcal{I}}=\{\mathit{a}|\mathit{C}\mathrm{(}\mathit{a}\mathrm{)}\in \mathcal{A}\}$ , for all $\mathit{C}\in \mathsf{CN}$ , and ${\mathit{r}}^{\mathcal{I}}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}|\mathit{r}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathcal{A}\}$ for all $\mathit{r}\in \mathsf{RN}$ . Clearly, $\mathcal{I}$ is a model of $\mathcal{A}$ , and it is easy to see that $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}={\mathsf{ans}}_{\mathcal{I}}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}$ for any query q, where ${\mathsf{ans}}_{\mathcal{I}}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}$ are the answers to q under the interpretation $\mathcal{I}$ . Because of this identity, we can, without loss of generality, restrict ourselves to this $\mathcal{I}$ w.r.t. $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}$ .

Since f exists, we can construct for q the match $\mathit{\pi }:\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}\to \mathsf{IN}$ , such that $\mathit{\pi }\mathrm{(}\mathit{u}\mathrm{)}={\mathit{f}\mathrm{(}\mathit{u}\mathrm{)}}^{\mathcal{I}}$ . It follows that $\mathit{\pi }\mathrm{(}\mathit{x}\mathrm{)}=\mathit{a}$ , and so $\mathit{a}\in \mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}$ . Let ${\mathit{q}}^{\prime }$ be a query with query graph ${\mathit{G}}^{\prime }$ such that $\mathit{a}\in \mathsf{cert}\mathrm{(}{\mathit{q}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{)}$ . Since a is a certain answer of ${\mathit{q}}^{\prime }$ , ${\mathit{G}}^{\prime }$ must be homomorphic to $\mathcal{A}$ by a homomorphism g such that $\mathit{g}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{a}$ . Since homomorphisms preserve edges and ${\mathit{q}}^{\prime }$ is connected, the image of ${\mathit{G}}^{\prime }$ under g is a subgraph of $\mathsf{conn}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ . Then $\mathit{h}=\mathit{g}\circ {\mathit{f}}^{-1}$ is a homomorphism from ${\mathit{G}}^{\prime }$ to G with $\mathit{h}\mathrm{(}\mathit{x}\mathrm{)}=\mathit{x}$ . Thus, $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ .  □

Since $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ implies that $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}\subseteq \mathsf{cert}\mathrm{(}{\mathit{q}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{)}$ , the MSQ of a has as few as possible certain answers other than a. This is desired since it implies that the initial queries in Alg. 1 do not have any exceptions (certain answers not in the pos-set), unless this cannot be avoided. Therefore, the iterative query merging process of constructing explanations starts from an optimal standpoint.

Example 4.

Continuing the previous examples, Fig. 3 shows the graphs of the MSQs of $\mathsf{p}\mathsf{3}$ and $\mathsf{p}\mathsf{4}$ , constructed by materializing the TBox, and then extracting the connected components of $\mathsf{p}\mathsf{3}$ and $\mathsf{p}\mathsf{4}$ from the new ABox.

Fig. 3.

The MSQs of $\mathsf{p}\mathsf{3}$ and $\mathsf{p}\mathsf{4}$ represented as graphs.

For use with Alg. 1, we denote a call to a concrete function implementing the above described approach for obtaining $\mathsf{MSQ}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ by $\mathrm{\text{G}}\mathrm{\text{RAPH}}\mathrm{\text{MSQ}}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ . We should note that the result of $\mathrm{\text{G}}\mathrm{\text{RAPH}}\mathrm{\text{MSQ}}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ will be a MSQ, but in general it will not be condensed, and thus may contain redundant atoms and variables.

4.2. Query dissimilarity

At each iteration, Alg. 1 selects two queries to merge in order to produce a more general description covering both queries. To make the selection, we use a heuristic which is meant to express how dissimilar two queries are, so that at each iteration the two most similar queries are selected and merged, with the purpose of generating an as least generic as possible more general description. Given two queries ${\mathit{q}}_1$ , ${\mathit{q}}_2$ with respective graph representations ${\mathit{G}}_1=\mathrm{(}{\mathit{V}}_1\mathrm{,}{\mathit{E}}_1\mathrm{,}{\ell }_{{\mathit{V}}_1}\mathrm{,}{\ell }_{{\mathit{E}}_1}\mathrm{)}$ and ${\mathit{G}}_2=\mathrm{(}{\mathit{V}}_2\mathrm{,}{\mathit{E}}_2\mathrm{,}{\ell }_{{\mathit{V}}_2}\mathrm{,}{\ell }_{{\mathit{E}}_2}\mathrm{)}$ , we define the query dissimilarity heuristic between ${\mathit{q}}_1$ and ${\mathit{q}}_2$ as follows: $$\begin{array}{c}\mathsf{QueryDissimilarity}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}={\displaystyle \sum }_{{\mathit{v}}_1\in {\mathit{V}}_1}\underset{{\mathit{v}}_2\in {\mathit{V}}_2}{min}{\mathsf{diss}}_{{\mathit{q}}_1{\mathit{q}}_2}\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{)}+{\displaystyle \sum }_{{\mathit{v}}_2\in {\mathit{V}}_2}\underset{{\mathit{v}}_1\in {\mathit{V}}_1}{min}{\mathsf{diss}}_{{\mathit{q}}_2{\mathit{q}}_1}\mathrm{(}{\mathit{v}}_2\mathrm{,}{\mathit{v}}_1\mathrm{)}\end{array}$$ where $$\begin{array}{rcl}{\mathsf{diss}}_{{\mathit{q}}_1{\mathit{q}}_2}\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{)}& =& |{\mathit{L}}_1\mathrm{(}{\mathit{v}}_1\mathrm{)}\setminus {\mathit{L}}_2\mathrm{(}{\mathit{v}}_2\mathrm{)}|\\ & & +{\displaystyle \sum }_{\mathit{r}\in \mathit{R}}\{max\mathrm{(}{\mathsf{indegree}}_{{\mathit{G}}_1}^{\mathit{r}}\mathrm{(}{\mathit{v}}_1\mathrm{)}-{\mathsf{indegree}}_{{\mathit{G}}_2}^{\mathit{r}}\mathrm{(}{\mathit{v}}_2\mathrm{)}\mathrm{,}0\mathrm{)}\\ & & +max\mathrm{(}{\mathsf{outdegree}}_{{\mathit{G}}_1}^{\mathit{r}}\mathrm{(}{\mathit{v}}_1\mathrm{)}-{\mathsf{outdegree}}_{{\mathit{G}}_2}^{\mathit{r}}\mathrm{(}{\mathit{v}}_2\mathrm{)}\mathrm{,}0\mathrm{)}\}\mathrm{,}\end{array}$$ R is the set of all role names appearing in the edge labels of the two graphs, and ${\mathsf{indegree}}_{\mathit{G}}^{\mathit{r}}\mathrm{(}\mathit{v}\mathrm{)}$ ( ${\mathsf{outdegree}}_{\mathit{G}}^{\mathit{r}}\mathrm{(}\mathit{v}\mathrm{)}$ ) is the number of incoming (outcoming) edges e in node v of graph G with $\mathit{r}\in \ell \mathrm{(}\mathit{e}\mathrm{)}$ .

The intuition behind the above dissimilarity measure is that the graphs of queries which are dissimilar consist of nodes with dissimilar labels connected in dissimilar ways. Intuitively, we expect such queries to have dissimilar sets of certain answers, although there is no guarantee that this will always be the case. In order to have a heuristic that can be computed efficiently, we do not examine complex ways in which the nodes may be interconnected, but only examine the local structure of the nodes by comparing their indegrees and outdegrees. The way in which we compare the nodes of two query graphs is optimistic; we compare each node with its best possible counterpart —the node of the other graph which it is the most similar to. Note that ${\mathsf{diss}}_{{\mathit{q}}_1{\mathit{q}}_2}\mathrm{(}{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2\mathrm{)}$ does not equal ${\mathsf{diss}}_{{\mathit{q}}_2{\mathit{q}}_1}\mathrm{(}{\mathit{v}}_2\mathrm{,}{\mathit{v}}_1\mathrm{)}$ . The first quantity expresses how many conjuncts of ${\mathit{q}}_1$ containing ${\mathit{v}}_1$ do not appear in ${\mathit{q}}_2$ containing ${\mathit{v}}_2$ . This is best illustrated using a short example.

Example 5.

Let ${\mathit{q}}_1=\{\mathit{C}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathit{D}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathit{r}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{11}\mathrm{)}\mathrm{,}\mathit{r}\mathrm{(}{\mathit{y}}_{12}\mathrm{,}\mathit{x}\mathrm{)}\mathrm{,}\mathit{s}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{11}\mathrm{)}\}$ , ${\mathit{q}}_2=\{\mathit{C}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathit{E}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathit{r}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{21}\mathrm{)}\mathrm{,}\mathit{r}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{23}\mathrm{)}\}$ and assume that we are comparing variable x of ${\mathit{q}}_1$ with variable x of ${\mathit{q}}_2$ . As far as concepts are concerned, $\mathit{C}\mathrm{(}\mathit{x}\mathrm{)}$ appears in both ${\mathit{q}}_1$ and ${\mathit{q}}_2$ , while $\mathit{D}\mathrm{(}\mathit{x}\mathrm{)}$ only appears in ${\mathit{q}}_1$ , so one concept conjunct is missing from ${\mathit{q}}_2$ . Moreover, x appears in one “outgoing” r conjunct in ${\mathit{q}}_1$ and in two outgoing r conjuncts in ${\mathit{q}}_2$ , so no outgoing conjuncts are missing from ${\mathit{q}}_2$ . Also, x appears in one “ingoing” r conjunct in ${\mathit{q}}_1$ but in no “ingoing” r in ${\mathit{q}}_2$ conjuncts, so one more conjunct is missing. Finally, the s conjunct of x is missing from ${\mathit{q}}_2$ , giving us a total of three missing conjuncts from ${\mathit{q}}_2$ , therefore $\mathsf{diss}{\mathit{q}}_1{\mathit{q}}_2\mathrm{(}{\mathit{x}}_1\mathrm{,}{\mathit{x}}_2\mathrm{)}=3$ .

Using an efficient representation of the queries, it is easy to see that $\mathsf{QueryDissimilarity}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ can be computed in time $\mathit{O}\mathrm{(}|\mathsf{var}\mathrm{(}{\mathit{q}}_1\mathrm{)}|·|\mathsf{var}\mathrm{(}{\mathit{q}}_2\mathrm{)}|\mathrm{)}$ .

4.3. Query merging

The next step in Alg. 1 is the merging of the two most similar queries that have been selected. In particular, given a query ${\mathit{q}}_{\mathit{A}}$ for some individuals ${\mathit{I}}_{\mathit{A}}$ , i.e. a query such that ${\mathit{I}}_{\mathit{A}}\subseteq \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}\mathcal{A}\mathrm{)}$ , and a query ${\mathit{q}}_{\mathit{B}}$ for some individuals ${\mathit{I}}_{\mathit{B}}$ , i.e. a query such that ${\mathit{I}}_{\mathit{B}}\subseteq \mathsf{cert}\mathrm{(}{\mathit{q}}_{\mathit{B}}\mathrm{,}\mathcal{A}\mathrm{)}$ , the purpose is to merge the two queries to produce a more general query q for ${\mathit{I}}_{\mathit{A}}\cup {\mathit{I}}_{\mathit{B}}$ . The necessary condition that such query must satisfy is ${\mathit{I}}_{\mathit{A}}\cup {\mathit{I}}_{\mathit{B}}\subseteq \mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}$ . In the context of Alg. 1 the queries ${\mathit{q}}_{\mathit{A}}$ , ${\mathit{q}}_{\mathit{B}}$ may be MSQs of some individuals, or results of previous query merges.

4.3.1. Query least common subsumer

Our first approach for merging queries is using the query least common subsumer (QLCS). In the next few paragraphs we will present how to construct such a query from two SAV queries which will make apparent that the QLCS of two SAV queries always exists. As mentioned in Section 2, a QLCS is a most specific generalization of two queries. By choosing to use $\mathsf{QLCS}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}{\mathit{q}}_{\mathit{B}}\mathrm{)}$ (since QLCS is unique up to syntactical equivalence, we assume that $\mathsf{QLCS}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}{\mathit{q}}_{\mathit{B}}\mathrm{)}$ represents one such QLCS for ${\mathit{q}}_{\mathit{A}}$ and ${\mathit{q}}_{\mathit{B}}$ ) in the place of $\mathsf{Merge}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}{\mathit{q}}_{\mathit{B}}\mathrm{)}$ in Alg. 1, and assuming that the input set of individuals is $\mathit{I}=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ , it should be obvious that the last query computed by Alg. 1 will be $\mathit{q}=\mathsf{QLCS}\mathrm{(}\mathsf{MSQ}\mathrm{(}{\mathit{a}}_1\mathrm{,}\mathcal{A}\mathrm{)}\mathrm{,}\mathsf{MSQ}\mathrm{(}{\mathit{a}}_2\mathrm{,}\mathcal{A}\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathsf{MSQ}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{,}\mathcal{A}\mathrm{)}\mathrm{)}$ . For any query ${\mathit{q}}^{\prime }$ such that $\mathsf{cert}\mathrm{(}{\mathit{q}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{)}\supseteq \mathit{I}$ , it will by definition hold that $\mathsf{MSQ}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{,}\mathcal{A}\mathrm{)}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ , $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}$ . Therefore, $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ , which implies that $\mathsf{cert}\mathrm{(}\mathit{q}\mathrm{,}\mathcal{A}\mathrm{)}\subseteq \mathsf{cert}\mathrm{(}{\mathit{q}}^{\prime }\mathrm{,}\mathcal{A}\mathrm{)}$ . This means that if there is an exact explanation rule query of I, that will be a QLCS of its MSQs, while if there is not, the computed QLCS explanation rule query will have the fewest possible exceptions. Thus, the main advantage of using the QLCS is that it guarantees “optimality” of the computed explanations.

To compute a QLCS we use an extension of the Kronecker product of graphs to labeled graphs. Given two labeled graphs ${\mathit{G}}_1=\mathrm{(}{\mathit{V}}_1\mathrm{,}{\mathit{E}}_1\mathrm{,}{\ell }_{{\mathit{V}}_1}\mathrm{,}{\ell }_{{\mathit{E}}_1}\mathrm{)}$ and ${\mathit{G}}_2=\mathrm{(}{\mathit{V}}_2\mathrm{,}{\mathit{E}}_2\mathrm{,}{\ell }_{{\mathit{V}}_2}\mathrm{,}{\ell }_{{\mathit{E}}_2}\mathrm{)}$ , which in our case will represent queries, their Kronecker product $\mathit{G}={\mathit{G}}_1\times {\mathit{G}}_2$ is the graph $\mathit{G}=\mathrm{(}\mathit{V}\mathrm{,}\mathit{E}\mathrm{,}{\ell }_{\mathit{V}}\mathrm{,}{\ell }_{\mathit{E}}\mathrm{)}$ , where $\mathit{V}={\mathit{V}}_1\times {\mathit{V}}_2$ , $\mathit{E}=\{⟨⟨{\mathit{u}}_1\mathrm{,}{\mathit{v}}_1⟩\mathrm{,}⟨{\mathit{u}}_2\mathrm{,}{\mathit{v}}_2⟩⟩|⟨{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2⟩\in {\mathit{E}}_1\mathrm{,}⟨{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2⟩\in {\mathit{E}}_2\mathrm{,}\text{ and }{\ell }_{{\mathit{E}}_1}\mathrm{(}⟨{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2⟩\mathrm{)}\cap {\ell }_{{\mathit{E}}_2}\mathrm{(}⟨{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2⟩\mathrm{)}\ne \varnothing \}\subseteq \mathit{V}\times \mathit{V}$ , ${\ell }_{\mathit{V}}:\mathit{V}\to 2^{\mathsf{CN}}$ with ${\ell }_{\mathit{V}}\mathrm{(}⟨{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2⟩\mathrm{)}={\ell }_{{\mathit{V}}_1}\mathrm{(}{\mathit{v}}_1\mathrm{)}\cap {\ell }_{{\mathit{V}}_2}\mathrm{(}{\mathit{v}}_2\mathrm{)}$ , and ${\ell }_{\mathit{E}}:\mathit{E}\to 2^{\mathsf{RN}}$ with ${\ell }_{\mathit{E}}\mathrm{(}⟨⟨{\mathit{u}}_1\mathrm{,}{\mathit{v}}_1⟩\mathrm{,}⟨{\mathit{u}}_2\mathrm{,}{\mathit{v}}_2⟩⟩\mathrm{)}={\ell }_{{\mathit{E}}_1}\mathrm{(}⟨{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2⟩\mathrm{)}\cap {\ell }_{{\mathit{E}}_2}\mathrm{(}⟨{\mathit{v}}_1\mathrm{,}{\mathit{v}}_2⟩\mathrm{)}$ .

Example 6.

Fig. 4 shows the Kronecker product of the query graphs of Example 4.

Fig. 4.

The Kronecker product of the MSQs of $\mathsf{p}\mathsf{3}$ and $\mathsf{p}\mathsf{4}$ .

As with the Kronecker product of unlabeled graphs, for any graph H, we have that $\mathit{H}\to {\mathit{G}}_1\mathrm{,}{\mathit{G}}_2$ if and only if $\mathit{H}\to {\mathit{G}}_1\times {\mathit{G}}_2$ [70]. Since we are interested in graphs representing SAV queries, we can assume that H, ${\mathit{G}}_1$ , ${\mathit{G}}_2$ are connected. Assuming that ${\mathit{G}}_1$ , ${\mathit{G}}_2$ represent two SAV queries ${\mathit{q}}_1$ , ${\mathit{q}}_2$ (with answer variable x), it will specifically hold that $\mathit{H}\to {\mathit{G}}_1\mathrm{,}{\mathit{G}}_2$ if and only if $\mathit{H}\to \mathsf{conn}\mathrm{(}⟨\mathit{x}\mathrm{,}\mathit{x}⟩\mathrm{,}{\mathit{G}}_1\times {\mathit{G}}_2\mathrm{)}$ , where $\mathsf{conn}\mathrm{(}⟨\mathit{x}\mathrm{,}\mathit{x}⟩\mathrm{,}{\mathit{G}}_1\times {\mathit{G}}_2\mathrm{)}$ is the connected component of ${\mathit{G}}_1\times {\mathit{G}}_2$ containing the pairs of answer variables node $⟨\mathit{x}\mathrm{,}\mathit{x}⟩$ . Let q be the query whose query graph is the connected component of ${\mathit{G}}_1\times {\mathit{G}}_2$ containing node $⟨\mathit{x}\mathrm{,}\mathit{x}⟩$ , with node $⟨\mathit{x}\mathrm{,}\mathit{x}⟩$ replaced by x (the answer variable of the new query) and all other nodes of that connected component replaced by distinct arbitrary variable names other than x. Since we allow SAV queries to have empty bodies, even if the node $⟨\mathit{x}\mathrm{,}\mathit{x}⟩$ is not labeled with any atoms it corresponds to a valid query that obviously subsumes ${\mathit{q}}_1$ and ${\mathit{q}}_2$ . Because homomorphisms between query graphs correspond to subsumption relations between the respective queries, and vice versa, it will hold that ${\mathit{q}}_1\mathrm{,}{\mathit{q}}_2{⩽}_{\mathit{S}}\mathit{q}$ and for any other query ${\mathit{q}}^{\prime }$ s.t. ${\mathit{q}}_1\mathrm{,}{\mathit{q}}_2{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ it will hold that ${\mathit{G}}_{{\mathit{q}}^{\prime }}\to {\mathit{G}}_1\mathrm{,}{\mathit{G}}_2$ , therefore ${\mathit{G}}_{{\mathit{q}}^{\prime }}\to {\mathit{G}}_1\times {\mathit{G}}_2$ and therefore $\mathit{q}{⩽}_{\mathit{S}}{\mathit{q}}^{\prime }$ . Computing ${\mathit{G}}_1\times {\mathit{G}}_2$ is therefore a concrete way to construct the QLCS.

For use with Alg. 1, we denote a call to the concrete function implementing that approach for computing $\mathsf{QLCS}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ by $\mathrm{\text{K}}\mathrm{\text{RONECKER}}\mathrm{\text{QLCS}}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ . The time complexity of $\mathrm{\text{K}}\mathrm{\text{RONECKER}}\mathrm{\text{QLCS}}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ is $\mathit{O}\mathrm{(}|\mathsf{var}\mathrm{(}{\mathit{q}}_1\mathrm{)}{|}^2·|\mathsf{var}\mathrm{(}{\mathit{q}}_2\mathrm{)}{|}^2\mathrm{)}$ , and the Kronecker product of the graphs ${\mathit{G}}_1$ , ${\mathit{G}}_2$ , contains $|{\mathit{V}}_1|·|{\mathit{V}}_2|$ nodes. Therefore, the final query constructed by Alg. 1 using $\mathrm{\text{K}}\mathrm{\text{RONECKER}}\mathrm{\text{QLCS}}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ to implement $\mathsf{Merge}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ will have $\mathit{O}\mathrm{(}{\mathit{m}}^{\mathit{n}}\mathrm{)}$ variables, where $\mathit{m}={max}_{\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}}|\mathsf{var}\mathrm{(}{\mathit{q}}_{\mathit{i}}\mathrm{)}|$ is the maximum variable count of the MSQs, and $\mathit{n}=|\mathit{I}|$ is the number of individuals in I. Constructing this query is by far the most expensive operation of the algorithm and dominates the running time with a complexity of $\mathit{O}\mathrm{(}{\mathit{m}}^{2\mathit{n}}\mathrm{)}$ . This makes the use of the above procedure for computing QLCS’s prohibitive for merging queries. However, the query obtained using the Kronecker product is in general not condensed, and in general will contain many redundant atoms and variables.

Example 7.

Fig. 5 shows the QLCS of the MSQs of Example 4, extracted from the Kronecker product of Example 6. It is obvious that the nodes with label $\{\mathsf{Finding}\}$ are redundant due to the presence of the nodes with label $\{\mathsf{SoreThroat}\mathrm{,}\mathsf{Finding}\}$ and $\{\mathsf{LungFinding}\mathrm{,}\mathsf{Finding}\}$ .

Fig. 5.

The QLCS of the MSQs of $\mathsf{p}\mathsf{3}$ and $\mathsf{p}\mathsf{4}$ produced by $\mathrm{\text{K}}\mathrm{\text{RONECKER}}\mathrm{\text{QLCS}}$ represented as a graph.

Removing the redundant parts of a query is essential not only for reducing the running time of the algorithm. Since these queries are intended to be shown to humans as explanations, ensuring that they are compact is imperative to improve comprehensibility. As mentioned in Section 2, the operation that compacts a query by creating a syntactically equivalent query by removing all its redundant parts is condensation. However, condensing a query is coNP-complete [27]. For this reason, we utilize Alg. 2, an approximation algorithm which removes redundant conjuncts and variables without a guarantee of producing a fully condensed query.

Algorithm 2:

ApproxQueryMinimize

Alg. 2 iterates through the variables of the input query, and checks if deleting one of them is equivalent to unifying it with another one. In particular, at each iteration of the main loop, the algorithm attempts to find a variable suitable for deletion. If none is found, the loop terminates. The inner loop iterates through all pairs of variables. At each iteration, variable ${\mathit{v}}^{\prime }$ is deleted if unifying it with v, by replacing all instances of ${\mathit{v}}^{\prime }$ in the query with v, produces no new conjuncts. By unifying variable ${\mathit{v}}^{\prime }$ with v, all conjuncts of the form $\mathit{C}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{)}$ become $\mathit{C}\mathrm{(}\mathit{v}\mathrm{)}$ and all conjuncts of the forms $\mathit{r}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{,}{\mathit{v}}^{″}\mathrm{)}$ , $\mathit{r}\mathrm{(}{\mathit{v}}^{″}\mathrm{,}{\mathit{v}}^{\prime }\mathrm{)}$ , $\mathit{r}\mathrm{(}{\mathit{v}}^{\prime }\mathrm{,}{\mathit{v}}^{\prime }\mathrm{)}$ become $\mathit{r}\mathrm{(}\mathit{v}\mathrm{,}{\mathit{v}}^{″}\mathrm{)}$ , $\mathit{r}\mathrm{(}{\mathit{v}}^{″}\mathrm{,}\mathit{v}\mathrm{)}$ , $\mathit{r}\mathrm{(}\mathit{v}\mathrm{,}\mathit{v}\mathrm{)}$ , respectively. If these conjuncts are already present, then removing them is equivalent to unifying ${\mathit{v}}^{\prime }$ with v. Alg. 2 is correct because removing a variable from query q produces a query that subsumes q, while unifying two variables of q produces a query that is subsumed by q. Therefore, Alg. 2 produces syntactically equivalent queries.

Example 8.

We can showcase an example of Alg. 2 detecting an extraneous variable in the QLCS of ${\mathit{q}}_1$ and ${\mathit{q}}_2$ from Example 7, running the main loop for $\mathit{v}={\mathit{y}}_1$ and ${\mathit{v}}^{\prime }={\mathit{y}}_2$ . The condition at line 3 first checks if the label of node ${\mathit{v}}^{\prime }$ , $\{\mathsf{Finding}\}$ , is a subset of the label of node v, $\{\mathsf{SoreThroat}\mathrm{,}\mathsf{Finding}\}$ , which is true. Then for every incoming edge to ${\mathit{v}}^{\prime }$ it checks if there is an edge incoming to v with the same label and origin. They both have one incoming edge from node x labeled with $\mathsf{hasFinding}$ so the second condition will also evaluate to true. Node ${\mathit{v}}^{\prime }$ has no incoming edges, so the third condition will also evaluate to true. Therefore, Alg. 2 will detect node ${\mathit{v}}^{\prime }$ as extraneous and delete it. Running the entire algorithm for this query will result in the query represented in Fig. 6 as a graph.

The main loop of Alg. 2 is executed at most $\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}$ times, since at each loop either a variable is deleted or the loop terminates. The inner loop checks all pairs of variables ( $\mathit{O}\mathrm{(}|\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}{|}^2\mathrm{)}$ ), and the if condition requires $\mathit{O}\mathrm{(}\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}\mathrm{)}$ set comparisons of size at most $|\mathsf{CN}|$ , and $2|\mathsf{RN}|$ comparisons of rows and columns of adjacency matrices. Treating $|\mathsf{CN}|$ and $|\mathsf{RN}|$ as constants, the complexity of Algorithm 2 is $\mathit{O}\mathrm{(}|\mathsf{var}\mathrm{(}\mathit{q}\mathrm{)}{|}^4\mathrm{)}$ .

Given the above, our first practical implementation of Alg. 1, uses $\mathrm{\text{G}}\mathrm{\text{RAPH}}\mathrm{\text{MSQ}}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ to implement $\mathsf{MSQ}\mathrm{(}\mathit{a}\mathrm{,}\mathcal{A}\mathrm{)}$ , and $\mathrm{\text{A}}\mathrm{\text{PPROX}}\mathrm{\text{Q}}\mathrm{\text{UERY}}\mathrm{\text{M}}\mathrm{\text{INIMIZE}}\mathrm{(}\mathrm{\text{K}}\mathrm{\text{RONECKER}}\mathrm{\text{QLCS}}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}{\mathit{q}}_{\mathit{B}}\mathrm{)}\mathrm{)}$ to implement $\mathsf{Merge}\mathrm{(}{\mathit{q}}_{\mathit{A}}\mathrm{,}{\mathit{q}}_{\mathit{B}}\mathrm{)}$ .

Regardless of the approximate query minimization described above, even if full query condensation could be performed, there is no guarantee that condensing the queries computed by Alg. 1 using QLCS as the merge operation, have meaningfully smaller condensations. This led us to two different approaches for further dealing with the rapidly growing queries QLCS produces.

The simplest approach to address this problem is to reject any queries produced by $\mathrm{\text{K}}\mathrm{\text{RONECKER}}\mathrm{\text{QLCS}}\mathrm{(}{\mathit{q}}_1\mathrm{,}{\mathit{q}}_2\mathrm{)}$ that, even after minimization, have variable counts higher than a pre-selected threshold. This strategy essentially introduces a weaker version of Alg. 1, without the guarantees of optimality, but with polynomial running time, which is outlined in Alg. 3, which we call KGrules-HT.

Fig. 6.

The minimized graph of the QLCS of Fig. 5.

Algorithm 3:

KGrules-HT

Alg. 3 is the same as Alg. 1 except that q is not added to L and S unless its variable count is less than or equal to an input threshold, t. This simple change reduces the complexity of the algorithm to polynomial in terms of $|\mathit{I}|$ and t. It should be noted that setting a very low threshold for t could potentially lead to all queries being rejected and the algorithm returning an empty set. The effects of t on the queries produced can vary significantly for different inputs and therefore different explanation datasets, thus t should be adjusted experimentally. It is also assumed that all MSQ’s created when initializing L have less than t variables.

If we let $\mathit{n}=|\mathit{I}|$ , calculating the query dissimilarity for all pairs of queries, costs $\mathit{O}\mathrm{(}{\mathit{n}}^2{\mathit{t}}^2\mathrm{)}$ operations. Using memoization limits the cost of calculating the dissimilarity through all iterations to $\mathit{O}\mathrm{(}{\mathit{n}}^2{\mathit{t}}^2\mathrm{)}$ . Each iteration of the main loop involves $\mathit{O}\mathrm{(}{\mathit{n}}^2\mathrm{)}$ operations for selecting ${\mathit{q}}_{\mathit{A}}$ , ${\mathit{q}}_{\mathit{B}}$ and $\mathit{O}\mathrm{(}{\mathit{t}}^4\mathrm{)}$ operations for calculating their QLCS. Thus, in total, Alg. 3 has a running time of $\mathit{O}\mathrm{(}{\mathit{n}}^3+{\mathit{n}}^2{\mathit{t}}^2+\mathit{n}{\mathit{t}}^4\mathrm{)}$ .

Our second approach to overcome the problem posed by the rapidly growing size of the queries produced by QLCS was to consider a different merge operation, which is described in the following section.

4.3.2. Greedy matching

As already mentioned, the above described procedure for merging queries by computing a QLCS, often introduces too many variables that Alg. 2 can’t minimize effectively. A QLCS of ${\mathit{q}}_1$ , ${\mathit{q}}_2$ , if condensed, is optimal at producing a query that combines their certain answers while introducing few as possible new variables. However, the new variables that are introduced may still be too many. In practice, we may be able to afford some leniency in terms of certain answers and the loss of optimality that the QLCS provides, so we can explore alternative methods of unifying queries without the cost of increased variables.

One such method, is finding a common subquery, i.e. finding the common conjuncts of two queries ${\mathit{q}}_1$ , ${\mathit{q}}_2$ . Assuming that $|\mathsf{var}\mathrm{(}{\mathit{q}}_1\mathrm{)}|⩾|\mathsf{var}\mathrm{(}{\mathit{q}}_2\mathrm{)}|$ and that the variables of ${\mathit{q}}_1$ , ${\mathit{q}}_2$ are renamed apart except for the answer variable x, a matching θ is a 1-1 mapping from the variables of ${\mathit{q}}_2$ to the variables of ${\mathit{q}}_1$ . The common subquery q is formed by renaming the variables of ${\mathit{q}}_2$ according to the matching, and keeping the conjuncts also found in ${\mathit{q}}_1$ , i.e. $\mathit{q}={\mathit{q}}_1\cap {\mathit{q}}_2\mathit{\theta }$ .

Example 9.

Continuing the previous examples, we will find common subqueries of the MSQs of $\mathsf{p}\mathsf{3}$ and $\mathsf{p}\mathsf{4}$ . We can match the lung finding of $\mathsf{p}\mathsf{4}$ with the lung finding of $\mathsf{p}\mathsf{3}$ as well as their sore throat findings. This would be done by renaming ${\mathit{y}}_{21}$ to ${\mathit{y}}_{11}$ and ${\mathit{y}}_{22}$ to ${\mathit{y}}_{12}$ and then keeping the common conjuncts resulting in the query $\mathit{q}\mathrm{(}\mathit{x}\mathrm{)}=\{\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{11}\mathrm{)}\mathrm{,}\mathsf{SoreThroat}\mathrm{(}{\mathit{y}}_{11}\mathrm{)}\mathrm{,}\mathsf{Finding}\mathrm{(}{\mathit{y}}_{11}\mathrm{)}\mathrm{,}\mathsf{hasFinding}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_{12}\mathrm{)}\mathrm{,}\mathsf{LungFinding}\mathrm{(}{\mathit{y}}_{12}\mathrm{)}\mathrm{,}\mathsf{Finding}\mathrm{(}{\mathit{y}}_{12}\mathrm{)}\}$ . In our approach we evaluate the quality of matchings based on the number of conjuncts in the query they induce, which in this case is 7.

Finding the maximum common subquery belongs to a larger family of problems of finding maximal common substructures in graphs, such as the mapping problem for processors [8], structural resemblance in proteins [29] and the maximal common substructure match (MCSSM) [79]. Our problem can be expressed as a weighted version of most of these problems, since they only seek to maximize the number of nodes in the common substructure, which, in our case, corresponds to the number of variables in the resulting subquery. Since we want to maximize the number of common conjuncts, we could assign weights to variable matchings (y corresponds to z) due to concept conjuncts, and to pairs of variable matchings (y corresponds to z and ${\mathit{y}}^{\prime }$ corresponds to ${\mathit{z}}^{\prime }$ ) due to role conjuncts. This is an instance of the general graph matching problem. These problems are NP-hard and are therefore usually solved with approximation algorithms [22,46]. With Alg. 4, we introduce our own method for approximately solving this problem since we need to impose the additional restriction that the resulting query must be connected. Any conjuncts in the resulting query that aren’t connected to the answer variable do not influence the query’s certain answers, so we consider them extraneous.

Algorithm 4:

GreedyCommonConjuncts

Alg. 4 initializes an empty variable renaming θ. V and U contain the variables that have not been matched yet. At each iteration of the main loop, the algorithm attempts to match one of the variables of ${\mathit{q}}_2$ with one of the variables of ${\mathit{q}}_1$ . Only matches that conserve the connectedness of the induced query are considered (set S). If there are no such matches the main loop terminates. Otherwise, the match that adds the largest number of conjuncts to the induced query is selected. This match is added to θ and the corresponding variables are removed from V and U. Finally, the query q which consists of the common conjuncts of ${\mathit{q}}_1$ and ${\mathit{q}}_2$ is constructed, by renaming the variables of ${\mathit{q}}_2$ according to θ and keeping the conjuncts that also appear in ${\mathit{q}}_1$ .

An efficient implementation of Alg. 4 will use a max-priority queue to select at each iteration the match that adds the largest number of conjuncts to the induced query. The priority queue should contain an element for each pair of variables that can be matched, with the priority of the element being either 0 if the pair is not in S, and otherwise equal to the number of conjuncts it would add to the query. At each iteration some priorities may need to be updated. The time complexity of priority queues varies depending on their implementation. Implementations such as Strict Fibonacci Heaps have lower time complexity but perform worse in practice than simpler implementations with higher time complexities such as Binary Heaps. A Strict Fibonacci Heap implementation would have a time complexity of $\mathit{O}\mathrm{(}{\mathit{n}}^2{\mathit{m}}^2\mathrm{)}$ , where $\mathit{n}=|\mathsf{var}\mathrm{(}{\mathit{q}}_1\mathrm{)}|$ , $\mathit{m}=|\mathsf{var}\mathrm{(}{\mathit{q}}_2\mathrm{)}|$ , while a Binary Heap implementation $\mathit{O}\mathrm{(}{\mathit{n}}^2{\mathit{m}}^{2}log\mathrm{(}\mathit{n}\mathit{m}\mathrm{)}\mathrm{)}$ .

5. Experiments

We evaluated the proposed algorithms and framework by generating explanations for various classifiers, computing the metrics presented in Section 3, comparing with other rule-based approaches where possible, and discussing the quality and usefulness of the results.1

¹

All code and data are available at https://github.com/ails-lab/kgrules-h.

Specifically, we explored four use-cases: a) we are given a tabular dataset which serves as both the features of the classifier and the explanation dataset, b) we are given raw data along with curated semantic descriptions (ABox) but without a TBox, c) we are given curated semantic descriptions, along with a TBox, and d) we are only given raw data, so semantic descriptions need to be constructed automatically. The first use-case facilitated comparison of the proposed KGRules-H algorithm with other rule-based XAI approaches from literature, the second and third use-cases were more suitable for validating the usefulness of the proposed framework in its intended setting, while the fourth explored how KGRules-H could be utilized in a scenario in which semantic data descriptions are not available. For the first use-case we experimented on the Mushroom2

²

https://archive.ics.uci.edu/ml/datasets/mushroom

dataset which involves only categorical features. For the second use-case we used the CLEVR-Hans3 dataset [68] which consists of images of 3D geometric shapes in addition to rich metadata which we use as semantic data descriptions. For the third we constructed an explanation dataset from a subset of the Visual Genome [39] to explain a classifier trained on Places365 [83] for scene classification, while for the fourth we used MNIST [43] which contains images of handwritten digits, and no metadata.

The components needed for each experiment, were: a) a black-box classifier for which we provide rule-based explanations, b) an explanation dataset with semantic descriptions of exemplar data using the appropriate terminology and c) reasoning capabilities for semantic query answering, in order to evaluate the generated rules. As classifiers we chose widely used neural networks, which are provided as default models in most deep learning frameworks.

For constructing explanation datasets in practice, we identified two general approaches: a) the curated approach, and b) the automated information extraction approach. For the manual curated approach, the semantic descriptions of exemplar data were provided. In an ideal scenario, curated explanation datasets are created by domain experts, providing semantic descriptions which are meaningful for the task, and by using the appropriate terminology, lead to meaningful rules as explanations. In our experiments, we simulated such a manually curated dataset by using Visual Genome, which provides semantic descriptions for each image present in the dataset, using terminology linked to WordNet [52]. Of course, using human labor for the creation of explanation datasets in real-world applications would be expensive, thus we also experimented with automatically generating semantic descriptions for exemplar data. Specifically, for the automated information extraction approach we used domain specific, robust, feature extraction techniques and then provided semantic descriptions in terms of the extracted features. In these experiments, we automatically generated semantic descriptions for images in MNIST, by using ridge detection, and then describing each image as a set of intersecting lines.

For acquiring certain answers of semantic queries, which requires reasoning, we set up repositories on GraphDB.3

³

https://graphdb.ontotext.com/

For the case of the Mushrooms dataset we used the certain answers to measure fidelity, number of rules and average rule length and compared our approach with RuleMatrix [53] which implements scalable bayesian rule lists [80], Skope-Rules4

⁴

https://github.com/scikit-learn-contrib/Skope-Rules

and the closely related KGrules [19]. For CLEVR-Hans3, we mainly used the certain answers to explore whether our explainability framework can detect the foreknown bias of the classifier, while for Visual Genome we attempt to discover biases, by observing the best generated rule-queries with respect to precision, recall, and degree as defined in Section 3. Finally, for MNIST we observed quality and usability related properties of generated rule queries and their exceptions.

5.1. Mushrooms

The purpose of the Mushroom experiment was to compare our results with other rule-based approaches from the literature. Since other approaches mostly provide explanation rules in terms of the feature space, the explanation dataset was created containing only this information. We should note that this was only done for comparison’s sake, and is not the intended use-case for the proposed framework, in which there would exist semantic descriptions which cannot be necessarily represented in tabular form, and possibly a TBox.

5.1.1. Explanation dataset

The Mushroom dataset contains 8124 rows, each with 22 categorical features of 2 to 9 possible values. We randomly chose subsets of up to 4000 rows to serve as the exemplars of explanation datasets. The vocabulary $⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ used by the explanation datasets consisted of: an individual name for each index of a row included in the explanation dataset (in $\mathsf{IN}$ ), and a concept name for each combination of categorical feature and value (in $\mathsf{CN}$ ), giving us a total of $|\mathsf{CN}|=123$ . In this case, the set of exemplars ( $\mathsf{EN}$ ) coincided with the set of individual names. Then, for each feature and for each row, we added an assertion to the ABox, representing the value of the feature for the corresponding row. Thus, the knowledge base of an explanation dataset and its vocabulary had the form: $$\begin{array}{c}\mathsf{IN}=\{\mathsf{ro}{w}_1\mathrm{,}\mathsf{ro}{w}_2\dots \mathsf{ro}{w}_n\}\\ \mathsf{CN}=\{\mathsf{CapShapeBell}\mathrm{,}\mathsf{CapShapeConical}\mathrm{,}\mathsf{CapShapeConvex}\mathrm{,}\dots \mathrm{,}\mathsf{HabitatGrass}\mathrm{,}\mathsf{HabitatLeaves}\mathrm{,}\dots \}\\ \mathsf{RN}=\varnothing \\ \mathcal{A}=\{\mathsf{CapShapeFlat}\mathrm{(}\mathsf{ro}{w}_1\mathrm{)}\mathrm{,}\mathsf{CapSurfaceFibrous}\mathrm{(}\mathsf{ro}{w}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathsf{HabitatPaths}\mathrm{(}\mathsf{ro}{w}_n\mathrm{)}\}\end{array}$$

5.1.2. Setting

For this set of experiments, we used a simple multi-layer perceptron with one hidden layer as the black-box classifier. The classifier achieved $100\mathrm{\%}$ accuracy on train and test set in all experiments. After training, we generated explanations using Alg. 1 (in the case of tabular data, both merge operations outlined in Section 4.3 are reduced to a simple intersection of the concept assertions of the merged individuals), along with three other rule-based approaches from related literature, and compared them.

We split the dataset into four parts: 1) a training set, used to train the classifier, 2) a test set, used to evaluate the classifier, 3) an explanation-train set, used to generate explanation rules, and 4) an explanation-test set, used to evaluate the generated explanation rules. When running KGrules-H and KGrules, the explanation dataset was constructed from the explanation-train set. We experimented by changing the size of this dataset, from 100 to 4000 rows, and observed the effect it had on the explanation rules. On the explanation-test set, we measured the fidelity of the generated rules which is defined as the proportion of items for which classifier and explainer agree. We also measured the number of generated rules and average rule length. We used the proposed KGrules-H algorithm to generate explanations, and we also generated rules (on the same data and classifier) with RuleMatrix, Skope-rules and the closely related KGrules.

To compare with the other methods, which return a set of rules at their output, in this experiment we only considered correct rules we generated. To choose which rules to consider (what would be shown to a user), from the set of all correct rule-queries generated, we greedily chose queries starting with the one that had the highest count of certain answers on the explanation-train set, and then iteratively adding queries that provided the highest count of certain answers, not provided by any of the previously chosen queries. This is not necessarily the optimal strategy of rule selection for showing to a user (it never considers rules with exceptions), and we plan to explore alternatives in future work.

Finally, for all methods except for the related KGrules we measured running-time using same runtime on Google Colab,5

⁵

https://colab.research.google.com/

by using the “%%timeit”6

⁶

https://ipython.readthedocs.io/en/stable/interactive/magics.html#magic-timeit

magic command with default parameters. KGrules was not compatible with this benchmarking test, since it is implemented in Java as opposed to Python which is the implementation language provided for the other methods. In addition, KGrules implements an exhaustive exponential algorithm, so it is expected to be much slower than all other methods.

5.1.3. Results

The results of the comparative study are shown in Table 4. A first observation is that for small explanation datasets, the proposed approach did not perform as well as the other methods regarding fidelity, while for large ones it even outperformed them. This could be because for small explanation datasets, when the exemplars are chosen randomly, there are not enough individuals, and variety in the MSQs of these individuals, for the algorithm to generalize by merging their MSQs. This is hinted also from the average rule length, which is longer for both KGrules-H and KGrules for explanation dataset sizes 100 and 200, which indicates less general queries. Conversely, for explanation datasets of 600 exemplars and larger, the proposed approach performs similarly, in terms of fidelity, with related methods. Regarding running time, KGrules-H is the fastest except for the case of the largest explanation dataset, for which Skope-rules is faster. However, in this case Skope-rules’s performance suffers with respect to fidelity, whereas RuleMatrix and KGrules-H achieve perfect results. Furthermore, our proposed approach seems to generate longer rules than all other methods which on the one hand means that they are more informative, though on the other hand they are potentially less understandable by a user. This highlights the disadvantages constructing queries using the MSQs as a starting point. This was validated upon closer investigation, where we saw that the rules generated from the small explanation datasets were more specific than needed, as the low value of fidelity was due only to false negatives, and there were no false positives. Detecting redundant conjuncts might be done more efficiently for rules concerning tabular data, but for general rules, on which our approach is based, this task is very computationally demanding.

Table 4

Performance on the mushroom dataset

Size	Method	Fidelity	Nr. of rules	Avg. length	Time (seconds)
100	KGrules-H	92.70%	4	14	0.15
	KGrules	97.56%	11	5	-
	RuleMatrix	94.53%	3	2	3.65
	Skope-rules	97.01%	3	2	1.29
200	KGrules-H	93.40%	8	14	0.18
	KGrules	98.37%	11	5	-
	RuleMatrix	97.78%	4	2	3.65
	Skope-rules	98.49%	4	2	1.47
600	KGrules-H	99.60%	10	13.3	0.61
	KGrules	99.41%	13	4	-
	RuleMatrix	99.43%	6	1	7.69
	Skope-rules	98.52%	4	2	1.58
1000	KGrules-H	100%	9	14.2	1.67
	KGrules	99.58%	14	6.57	-
	RuleMatrix	99.90%	6	1.33	11.1
	Skope-rules	98.50%	4	2.25	2.95
4000	KGrules-H	100%	10	14.2	34.30
	KGrules	99.72%	16	5.81	-
	RuleMatrix	100%	7	1.43	43.00
	Skope-rules	96.85%	2	2	3.01

5.2. CLEVR-Hans3

The second set of experiments involved CLEVR-Hans3 [68], which is an image classification dataset designed to evaluate algorithms that detect and fix biases of classifiers. It consists of CLEVR [35] images divided into three classes, of which two are confounded. The membership of an image to a class is based on combinations of the attributes of the objects depicted. Thus, within the dataset, consisting of train, validation, and test splits, all train, and validation images of confounded classes will be confounded with a specific attribute. The rules that the classes follow are the following, with the confounding factors in parentheses: (i) Large (Gray) Cube and Large Cylinder, (ii) Small Metal Cube and Small (Metal) Sphere, (iii) Large Blue Sphere and Small Yellow Sphere (Fig. 7). This dataset provides sufficient and reliable information to create an explanation dataset, while the given train-test split contains intentional biases, which was ideal as a grounds for experimentation, as we could observe the extent to which the proposed explanation rules can detect them.

5.2.1. Explanation dataset

Fig. 7.

Image samples of the three classes of CLEVR-Hans3 along with the class rules and the confounding factors in parentheses.

We created an explanation dataset $\mathcal{E}$ using the test set of CLEVR-Hans3, consisting of 750 images for each class. By utilizing the descriptions of images provided as metadata, we defined a vocabulary $⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ , in which there was an individual name for each image and for each depicted object (in $\mathsf{IN}$ ), a concept name for each size, color, shape and material in addition to three concept names ( $\mathsf{Class}\mathsf{1}$ , $\mathsf{Class}\mathsf{2}$ , $\mathsf{Class}\mathsf{3}$ ) corresponding to the set of classes $\mathcal{C}$ and two indicative concept names $\mathsf{Image}$ and $\mathsf{Object}$ , as concept names (in $\mathsf{CN}$ ), and the role name (in $\mathsf{RN}$ ) $\mathsf{contains}$ which was used to link images to objects it depicts. We used the (unique) names of the image files of the test set as names for the exemplars ( $\mathsf{EN}$ ) of our explanation dataset, so the mapping $\mathcal{M}$ was straightforward (mapping the file name to the respective image). We then created the knowledge base $\mathcal{S}$ over this vocabulary, with the ABox containing the semantic description of all images and the respective objects, and the TBox containing certain rather trivial inclusion axioms. The sets $\mathsf{IN}$ , $\mathsf{CN}$ , $\mathsf{RN}$ and the TBox of our knowledge base and the respective vocabulary were the following: $$\begin{array}{c}\begin{array}{rl}\mathsf{IN}=& \{\mathsf{image}\mathsf{1}.\mathsf{png}\mathrm{,}\mathsf{object}{1}_1\mathrm{,}\mathsf{object}{2}_1\mathrm{,}\dots \mathrm{,}\mathsf{object}{N}_1\mathrm{,}\mathsf{image}\mathsf{2}.\mathsf{png}\mathrm{,}\mathsf{object}{1}_2\mathrm{,}\mathsf{object}{2}_2\mathrm{,}\dots \mathrm{,}\mathsf{image}\mathsf{2250.}\mathsf{png}\mathrm{,}\\ & \mathsf{object}{1}_{2250}\mathrm{,}\dots \mathrm{,}\mathsf{object}{M}_{2250}\}\end{array}\\ \begin{array}{rl}\mathsf{CN}=& \{\mathsf{Image}\mathrm{,}\mathsf{Object}\mathrm{,}\mathsf{Cube}\mathrm{,}\mathsf{Cylinder}\mathrm{,}\mathsf{Sphere}\mathrm{,}\mathsf{Metal}\mathrm{,}\mathsf{Rubber}\mathrm{,}\mathsf{Blue}\mathrm{,}\mathsf{Brown}\mathrm{,}\mathsf{Cyan}\mathrm{,}\mathsf{Gray}\mathrm{,}\mathsf{Green}\mathrm{,}\mathsf{Purple}\mathrm{,}\mathsf{Red}\mathrm{,}\\ & \mathsf{Yellow}\mathrm{,}\mathsf{Large}\mathrm{,}\mathsf{Small}\mathrm{,}\mathsf{Class}\mathsf{1}\mathrm{,}\mathsf{Class}\mathsf{2}\mathrm{,}\mathsf{Class}\mathsf{3}\}\end{array}\\ \mathsf{RN}=\{\mathsf{contains}\}\\ \mathcal{T}=\{\mathit{C}⊑\mathsf{Object}|\mathit{C}\notin \{\mathsf{Image}\mathrm{,}\mathsf{Object}\mathrm{,}\mathsf{Class}\mathsf{1}\mathrm{,}\mathsf{Class}\mathsf{2}\mathrm{,}\mathsf{Class}\mathsf{3}\}\}.\end{array}$$

5.2.2. Setting

For the experiments on CLEVR-Hans3 we used the same ResNet34 [33] classifier and training procedure as those used by the creators of the dataset in [68]. The performance of the classifier is shown in Table 5 and so is the confusion matrix which summarizes the predictions of the classifier indicating the differences between the actual and the predicted classes of the test samples. As expected, the classifier has lower values on some metrics regarding the first two classes, and this is attributed to the confounding factors and not the quality of the classifier, since it achieved $99.4\mathrm{\%}$ accuracy in the validation set. After training the classifier, we acquired its predictions on the test set and generated explanations for each class with Alg. 1 with $\mathsf{QLCS}$ as the merge operation. Afterwards, utilizing the reasoning capabilities of GraphDB, we loaded the knowledge base $\mathcal{S}$ of our explanation dataset, and obtained the certain answers of the corresponding explanation rule queries in order to evaluate the produced explanation rules. The evaluation was based on the metrics mentioned in Section 3, essentially comparing the certain answers of the explanation rule queries, with the corresponding exemplars of the pos-set of the classifier.

Table 5

Performance of the ResNet34 model on CLEVR-Hans3

True label	Test set metrics			Confusion matrix
	Precision	Recall	F1-score	Class 1	Class 2	Class 3
Class 1	0.94	0.16	0.27	118	511	121
Class 2	0.59	0.98	0.54	5	736	9
Class 3	0.85	1.00	0.92	2	0	748

5.2.3. Results

The explanation rules generated for the ResNet34 classifier using KGrules-H and QLCS as the merge operation, as outlined in Section 4.3.1, are shown in Table 6, where we show the rule, the value of each metric and the numbers of positive individuals. The term positive individuals refers to the certain answers of the respective explanation rule query that are also elements of the pos-set (they are classified in the respective class).

In our representation of explanation rule queries in Tables 6, 7 we have omitted the answer variable x, along with all conjuncts of the form x contains y and conjuncts of the form $\mathsf{Object}\mathrm{(}\mathit{y}\mathrm{)}$ , for brevity. In addition, the rules in the Table are not formally written, to make more visually clear the characteristics of the objects involved. For example, the rule of the first row (Best precision for class 1) would formally be written $\mathsf{Exemplar}\mathrm{(}\mathit{x}\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Large}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Cube}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Gray}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Large}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Cylinder}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Large}\mathrm{(}{\mathit{y}}_3\mathrm{)}\mathrm{,}\mathsf{Metal}\mathrm{(}{\mathit{y}}_3\mathrm{)}\to \mathsf{Class}\mathsf{1}\mathrm{(}\mathit{x}\mathrm{)}$ .

The algorithm found a correct rule ( $\text{precision}=1$ ) for each class, in addition to a rule query with recall = 1, whose certain answers are a superset of the positive set. The best degree was achieved for class 3, which lacks a confounding factor, meaning the classifier is not expected to be biased. Correct rule queries are of particular interest since they can be translated into guaranteed IF-THEN rules which the classifier follows on the particular dataset. For instance the highest recall correct rule query for class 1 is translated into the rule “If the image contains a Large Gray Cube, a Large Cylinder and a Large Metal Object then it is classified to class 1.”. This rule clearly shows the bias of the classifier, since it is the description of the class with the added confounding factor (the Large Cube is Gray). Similarly the (not correct) rule query with recall = 1 for the same class can be translated into the rule “If the image does not contain a Large Cube then it is not classified to class 1”, since the set of certain answers is a super set of the positive set. We observed that correct rule queries tend to be more specific than others, with the most general rules with exceptions being those with recall = 1. Other rules which were correct with exceptions, tended to lie somewhere in the middle with respect to how general or specific they are, but they were the ones which lead to the highest values of degree. By observing these results, we concluded that in practice, a set of rules, both correct and with exceptions, can give us a very clear picture of what the black-box classifier is doing. However, in order to not overwhelm an end-user with a large number of rules, we should develop a strategy to select which rules to show to the user. Here, as opposed to the Mushroom experiment (Section 5.1) the strategy we used was to show the highest recall, highest precision and highest degree rules, along with their exceptions if any, but as mentioned, we plan to explore additional strategies in the future, such as showing disjunctions of correct rules.

It is interesting to note that the rule query with recall = 1 produced for class 1 contained a Large Cube but not a Large Cylinder, which is also in the description of the class. This shows that in the training process the classifier learned to pay more attention to the presence of cubes rather than the presence of cylinders. The elements of the highest recall correct rule that differ from the true description of class 1 can be a great starting point for a closer inspection of the classifier. We expected the presence of a Gray Cube from the confounding factor introduced in the training and validation sets, but in a real world scenario similar insights can be reached by inspecting the queries. In our case, we further inquired the role that the Gray Cube and the Large Metal Object play in the correct rule by removing either of them from the query and examining its behavior. In Table 7 we can see that the gray color was essential for the correct rule while the Large Metal Object was not, and in fact its removal improved the rule and returned almost the entire class.

Another result that piqued our attention was the highest degree explanation for class 3 which is the actual rule that describes this class. This explanation was not a correct rule, since it had two exceptions, which we can also see in the confusion matrix of the classifier and we were interested to examine what sets these two individuals apart. We found that both of these individuals are answers to the query “y1 is Large, Gray, Cube”. This showed us once again the great effect the confounding factor of class 1 had on the classifier.

Our overall results show that the classifier tended to emphasize low level information such as color and shape and ignored higher level information such as texture and the combined presence of multiple objects. This was the reason why the confounding factor of class 1 had an important effect to the way images were classified, while the confounding factor of class 2 seemed to have had a much smaller one. Furthermore, the added bias made the classifier reject class 1 images, which however had to be classified to one of the other two classes (no class was not an option). Therefore one of the other classes had to be “polluted” by samples which were not confidently classified to a class. This motivates us to expand the framework in the future to work with more informative sets than the pos-set, such as elements which were classified with high confidence, and false and true, negatives and positives

Table 6

Optimal explanations with regard to the three metrics on CLEVR-Hans3

Metric	Explanation rules	Precision	Recall	Degree	Positives
Class 1
Best precision	y1 is Large, Cube, Gray.	1.00	0.66	0.66	83
	y2 is Large, Cylinder.
	y3 is Large, Metal.
Best recall	y1 is Large, Cube.	0.09	1.00	0.09	125
Best degree	y1 is Large, Cube, Gray.	1.00	0.66	0.66	83
	y2 is Large, Cylinder.
	y3 is Large, Metal.
Class 2
Best precision	y1 is Small, Sphere.	1.00	0.09	0.09	116
	y2 is Large, Rubber.
	y3 is Small, Metal, Cube.
	y4 is Small, Brown.
	y5 is Small, Rubber, Cylinder.
Best recall	y1 is Cube.	0.63	1.00	0.63	1247
Best degree	y1 is Metal, Cube.	0.78	0.8	0.65	1005
	y2 is Small, Metal.
Class 3
Best precision	y1 is Metal, Blue.	1.00	0.42	0.42	365
	y2 is Large, Blue, Sphere.
	y3 is Yellow, Small, Sphere.
	y4 is Small, Rubber.
	y5 is Metal, Sphere.
Best recall	y1 is Large.	0.42	1.00	0.42	878
	y2 is Sphere.
Best degree	y1 is Yellow, Small, Sphere.	0.99	0.85	0.85	748
	y2 is Large, Blue, Sphere.

Table 7

Two modified versions of the class 1 correct rule produced by removing conjuncts

Query	Positives	Negatives
y1 is Large, Cube. y2 is Large, Cylinder. y3 is Large, Metal.	108	547
y1 is Large, Cube, Gray. y2 is Large, Cylinder.	93	0

5.3. Visual genome and places

For the third set of experiments, we produced explanations of an image classifier trained on the Places365 dataset for scene classification. To do this, we constructed an explanation dataset from a subset of the visual genome, which includes a scene-graph for each image. Nodes of scene-graphs represent depicted objects, and edges represent relationships between them, while both edges and nodes are labeled with WordNet synsets. This allows us to encode the provided scene-graphs as an ABox, and to use the hyponym-hypernym hierarchy of WordNet as a TBox.

5.3.1. Explanation dataset

To construct the explanation dataset, we first selected the two most confused classes based on the confusion matrix of the classifier on the Places365 test set. These were “Desert Sand” and “Desert Road”. Then, we acquired the predictions of the classifier on the entirety of the visual genome dataset, and kept as expemplars the images for which the top prediction was one of the aformentioned classes. There were 273 such images. We defined a vocabulary $⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ , where the set of individual names $\mathsf{IN}$ contained a unique name for each image and for each depicted object, based on their visual genome IDs, while the mapping function was a dictionary linking image IDs ( $\mathsf{EN}$ ) to the corresponding image files. The size of $\mathsf{IN}$ was 6462. We initilized the set of concept names $\mathsf{CN}$ with two concepts: $\mathsf{Image}$ and $\mathsf{Object}$ and then added to $\mathsf{CN}$ all WordNet synsets that appear as node labels, in addition to all of their hypernyms. The size of $\mathsf{CN}$ was 1155. Similarly, the set of role names ( $\mathsf{RN}$ ) was initialized with the role $\mathsf{depicts}$ , which links images to their depicted objects, and then extended with the set of WordNet synsets that appear as edge labels in the selected images’ scene graphs, in addition to all of their hypernyms, totaling 226 role names. Using this vocabulary we constructed a knowledge base $⟨\mathcal{T}\mathrm{,}\mathcal{A}⟩$ . The ABox $\mathcal{A}$ was initialized with assertions of the form $\mathsf{Image}\mathrm{(}\mathsf{image}\mathrm{)}$ , $\mathsf{depicts}\mathrm{(}\mathsf{image}\mathrm{,}\mathsf{object}\mathrm{)}$ , encoding information about which images depict which objects. Then, based on the labels of the nodes of the scene-graphs of images we introduced concept assertions of the form $\mathit{SomeWordNetConcept}\mathrm{(}\mathsf{object}\mathrm{)}$ and based on the labels of the edges of scene-graphs we introduced role assertions of the form $\mathit{SomeWordNetRole}\mathrm{(}\mathsf{objectA}\mathrm{,}\mathsf{objectB}\mathrm{)}$ . Finally, the TBox $\mathcal{T}$ contained hierarchies of concepts and roles, based on the hypernym-hyponym relation from WordNet, encoded as $\mathit{hyponym}⊑\mathit{hypernym}$ . $$\begin{array}{c}\begin{array}{rl}\mathsf{IN}=& \{\mathsf{image}\mathsf{1}.\mathsf{png}\mathrm{,}\mathsf{object}{1}_1\mathrm{,}\mathsf{object}{2}_1\mathrm{,}\dots \mathrm{,}\mathsf{object}{N}_1\mathrm{,}\mathsf{image}\mathsf{2}.\mathsf{png}\mathrm{,}\mathsf{object}{1}_2\mathrm{,}\mathsf{object}{2}_2\mathrm{,}\dots \mathrm{,}\mathsf{image}\mathsf{2250.}\mathsf{png}\mathrm{,}\\ & \mathsf{object}{1}_{2250}\mathrm{,}\dots \mathrm{,}\mathsf{object}{M}_{2250}\}\end{array}\\ \mathsf{CN}=\{\mathsf{Image}\mathrm{,}\mathsf{Object}\mathrm{,}\mathsf{motorcycle}.\mathsf{n}\mathsf{.01}\mathrm{,}\mathsf{car}.\mathsf{n}\mathsf{.01}\mathrm{,}\mathsf{motor}\text{\_}\mathsf{vehicle}.\mathsf{n}\mathsf{.01}\mathrm{,}\dots \}\\ \mathsf{RN}=\{\mathsf{depicts}\mathrm{,}\mathsf{drink}.\mathsf{v}\mathsf{.01}\mathrm{,}\mathsf{eat}.\mathsf{v}\mathsf{.02}\mathrm{,}\mathsf{consume}.\mathsf{v}\mathsf{.02}\dots \}\\ \begin{array}{rl}\mathcal{T}=& \{\mathsf{motorcycle}.\mathsf{n}\mathsf{.01}⊑\mathsf{motor}\text{\_}\mathsf{vehicle}.\mathsf{n}\mathsf{.01}\mathrm{,}\mathsf{car}.\mathsf{n}\mathsf{.01}⊑\mathsf{motor}\text{\_}\mathsf{vehicle}.\mathsf{n}\mathsf{.01}\dots \mathrm{,}\mathsf{drink}.\mathsf{v}\mathsf{.02}⊑\mathsf{consume}.\mathsf{v}\mathsf{.02}\mathrm{,}\\ & \mathsf{eat}.\mathsf{v}\mathsf{.02}⊑\mathsf{consume}.\mathsf{v}\mathsf{.02}\dots \}.\end{array}\end{array}$$

5.3.2. Setting

As a black-box classifier in this set of experiments we used the ResNet50 classifier7

⁷

PyTorch model: http://places2.csail.mit.edu/models_places365/resnet50_places365.pth.tar.

provided by the official GitHub repository8

⁸

https://github.com/CSAILVision/places365

for models pretrained on Places365, which classifies images to 365 different classes.9

⁹

https://github.com/zhoubolei/places_devkit/blob/master/categories_places365.txt

The top1 error is $44.82\mathrm{\%}$ and the top5 error is $14.71\mathrm{\%}$ . As mentioned, we used the confusion matrix to select the two most confused classes to generate explanations for, which were “Desert Sand” and “Desert Road”. As a merge operation for Alg. 1 we used GreedyCommonConjuncts (Alg. 4), as the QLCS produced queries which could not be sufficiently minimized. Similarly with before, we loaded the knowledge of the explanation dataset in GraphDB, and after acquiring the certain answers of queries generated by Alg. 1, we validated their quality with respect to the precision, recall and degree metrics. After observing the best generated queries, we sought to further verify their accuracy for describing the black-box classifier, by looking into the black box to find out which parts of the image contributed to the prediction. We used a technique to generate heatmaps of pixel importance called Score-CAM[77]. Score-CAM is a white-box method for producing heatmaps that works by selectively masking areas of the input image and determining their importance to the prediction of the classifier.

5.3.3. Results

The best rule queries for each metric for each of the two classes is shown in Table 8. For simplicity of presentation, we have ommited conjuncts of the form $\mathsf{Exemplar}\mathrm{(}\mathsf{x}\mathrm{)}$ , $\mathsf{Image}\mathrm{(}\mathsf{x}\mathrm{)}$ , $\mathsf{depicts}\mathrm{(}\mathsf{x}\mathrm{,}\mathsf{y}\mathrm{)}$ and $\mathsf{Object}\mathrm{(}\mathsf{y}\mathrm{)}$ , where x is the answer variable. For both classes the generated queries have some unexpected conjuncts despite decent performance with respect to the three metrics. For example the conjunct $\mathsf{giraffe}.\mathsf{n}\mathsf{.01}\mathrm{(}\mathsf{y}\mathsf{3}\mathrm{)}$ appearing in the best correct rule for “Desert Road”, and the best degree rule for the same class being simply $\mathsf{Image}\mathrm{(}\mathsf{x}\mathrm{)}\mathrm{,}\mathsf{depicts}\mathrm{(}\mathsf{x}\mathrm{,}\mathsf{y}\mathsf{1}\mathrm{)}\mathrm{,}\mathsf{animal}.\mathsf{n}\mathsf{.01}\mathrm{(}\mathsf{y}\mathsf{1}\mathrm{)}$ . Furthermore, for “Desert Sand”, the concept $\mathsf{road}.\mathsf{n}\mathsf{.01}$ stands out. The concept $\mathsf{communicaton}.\mathsf{n}\mathsf{.02}$ has the hyopnyms $\mathsf{sign}.\mathsf{n}\mathsf{.02}$ and $\mathsf{written}\text{\_}\mathsf{communication}.\mathsf{n}\mathsf{.01}$ in the WordNet hierarchy which could refer to license plates and traffic signs. The second best query in terms of precision was $\mathsf{Image}\mathrm{(}\mathsf{x}\mathrm{)}$ , $\mathsf{depicts}\mathrm{(}\mathsf{x}\mathrm{,}\mathsf{y}\mathsf{1}\mathrm{)}$ , $\mathsf{depicts}\mathrm{(}\mathsf{x}\mathrm{,}\mathsf{y}\mathsf{2}\mathrm{)}$ , $\mathsf{depicts}\mathrm{(}\mathsf{x}\mathrm{,}\mathsf{y}\mathsf{3}\mathrm{)}.\mathsf{motor}\text{\_}\mathsf{vehicle}.\mathsf{n}\mathsf{.01}\mathrm{(}\mathsf{y}\mathsf{1}\mathrm{)}$ , $\mathsf{sky}.\mathsf{n}\mathsf{.01}\mathrm{(}\mathsf{y}\mathsf{2}\mathrm{)}$ , $\mathsf{road}.\mathsf{n}\mathsf{.01}\mathrm{(}\mathsf{y}\mathsf{3}\mathrm{)}$ , $\mathsf{along}.\mathsf{r}\mathsf{.01}\mathrm{(}\mathsf{y}\mathsf{1}\mathrm{,}\mathsf{y}\mathsf{3}\mathrm{)}$ . Again the concept $\mathsf{motor}\text{\_}\mathsf{vehicle}.\mathsf{n}\mathsf{.01}$ stands out.

Table 8

Optimal explanations with regard to the three metrics using the VG explanation dataset

Metric	Explanation rules	Precision	Recall	Degree	Positives
Desert Road
Best precision	y1 is field.n.01.	1.00	0.12	0.12	16
	y2 is natural_object.n.01.
	y3 is giraffe.n.01.
	y4 is body_part.n.01.
	y5 is woody_plant.n.01.
Best recall	y1 is organism.n.01	0.54	1.00	0.54	139
Best degree	y1 is animal.n.01	0.72	0.84	0.64	118
Desert Sand
Best precision	y1 is instrumentality.n.03	1.00	0.12	0.12	16
	y2 is road.n.01
	y3 is communication.n.02
	y4 is sky.n.01
	y5 is tree.n.01
Best recall	y1 is physical_entity.n.01	0.49	1.00	0.49	134
Best degree	y1 is instrumentality.n.01	0.92	0.56	0.56	76
	y2 is road.n.01

In Fig. 8 we present the saliency maps of three images from Visual Genome classified as “Desert Road” on the left and three classified as “Desert Sand” on the right. The saliency maps support the associations the queries highlighted, namely that images containing animals, especially giraffes, get classified as “Desert Road”, while images with roads and vehicles get classified as “Desert Sand”. Not all images exhibited such strong association. In Fig. 9 the classifier seems to be mostly influenced by the ground which is covered in dry grass. Given that the second highest value in the confusion matrix of this classifier was for the pair “Desert Sand”, “Desert Vegetation” we conjencture that some mistakes were made during the training of this classifier or several images in the training set of the Places365 dataset are mislabeled. The classifier may have been fed images that should be described as “Desert Road” but with the target label being “Desert Sand” and images that should be described as “Desert Vegetation” but with the target label being “Desert Road”. This would explain the weird associations exhibited and the conjuncts appearing in the explanations. The association of giraffes with the label “Desert Road” can be explained with mislabeled images depicting desert vegetation. This is still a wrongful association since giraffes can also populate grasslands such as in the top left image of Fig. 8.

We would like to point out that our method of producing explanations discovered these erroneous associations without asking from the end-user to manually inspect the heatmaps of a large number of images, rather than to read the best performing query for each one of our metrics. We believe that this provides a better user experience since it requires less effort for the initial discovery of suspect associations, which can then be thoroughly tested by examining other explanations such as heatmaps. Our method is also model-agnostic, while methods such as Score-CAM require access to the layers within a convolutional neural network.

Fig. 8.

Images from the visual genome dataset and their saliency maps produced by Score-CAM. Images on the left were classified as “Desert Road” and images on the right as “Desert Sand”.

Fig. 9.

An image classified as “Desert Road” exhibiting weaker association to the presence of a giraffe.

5.4. MNIST

For the fourth and final set of experiments we used MNIST, which is a dataset containing grayscale images of handwritten digits [43]. It is a very popular dataset for machine learning research, and even though classification on MNIST is essentially a solved problem, many recent explainability approaches experiment on this dataset (for example [60]). For us, MNIST was ideal for experimenting with automatic explanation dataset generation by using traditional feature extraction from computer vision. An extension to this approach would be using more complex information extraction from images, such as object detection or scene graph generation, for applying the explainability framework to explain generic image classifiers. This however is left for future work.

5.4.1. Explanation dataset

For creating the explanation dataset for MNIST, we manually selected a combination of 250 images from the test set, including both typical and unusual exemplars for each digit. The unusual exemplars were chosen following the mushroom experiment (Section 5.1), in which we saw that small explanation datasets do not facilitate good explanation rules when the exemplars are chosen randomly, so we aimed for variety of semantic descriptions. In addition, the unusual exemplars tended to be misclassified, and we wanted to see how their presence would impact the explanations.

Since there was no semantic information available that could be used to construct an explanation dataset, we automatically extracted descriptions of the images, by using feature extraction methods. Specifically, the images were described as a collection of intersecting lines, varying in angle, length and location within the image. These lines were detected using the technique of ridge detection [50]. The angles of the lines were quantized to 0, 45, 90 or 135 degrees, and the images were split into 3 horizontal (top, middle, bottom) and 3 vertical (left, center, right) zones which define 9 areas (top left, top center, $\dots \mathrm{,}$ bottom right). For each line we noted the areas it passes through. In Fig. 10 we show an example of an MNIST image, along with the results of the aforementioned information extraction procedure using ridge detection.

Fig. 10.

An example of a digit, the results of ridge detection, and the corresponding description.

Based on the selected images and the extracted information, we created our explanation dataset $\mathcal{E}$ . We constructed a vocabulary $⟨\mathsf{CN}\mathrm{,}\mathsf{RN}\mathrm{,}\mathsf{IN}⟩$ , with an individual for each image and each line therein as individual names ( $\mathsf{IN}$ ), the concepts defining the angle, location and length of each line, two indicative concepts $\mathsf{Image}$ and $\mathsf{Line}$ , as well as ten concepts (one for each digit) corresponding to the set of classes $\mathcal{C}$ , as concept names ( $\mathsf{CN}$ ), and the roles $\mathsf{contains}$ with domain $\mathsf{Image}$ , and range $\mathsf{Line}$ , indicating the existence of a line in a specific image, and the symmetric $\mathsf{intersects}$ with both domain and range $\mathsf{Line}$ , indicating that two lines intersect each other, as the role names ( $\mathsf{RN}$ ). To define the mapping $\mathcal{M}$ of the explanation dataset, after extracting the images and separating them into digits, we numbered them and named the Exemplars (and the corresponding file names) according to their digit and index. This also makes the images easy to retrieve. We then created the knowledge base $\mathcal{S}$ over this vocabulary, with the ABox containing the semantic description of all exemplar images and the respective lines, and the TBox containing certain rather trivial inclusion axioms. The vocabulary $\mathsf{IN}\mathrm{,}\mathsf{CN}\mathrm{,}\mathsf{RN}$ and the Tbox of our knowledge base are the following: $$\begin{array}{c}\begin{array}{rl}\mathsf{IN}=& \{\mathsf{test}\text{\_}\mathsf{zero}\mathsf{1}\mathrm{,}\mathsf{test}\text{\_}\mathsf{zero}\mathsf{1}\text{\_}\mathsf{line}\mathsf{0}\mathrm{,}\dots \mathrm{,}\mathsf{test}\text{\_}\mathsf{zero}\mathsf{1}\text{\_}\mathsf{line}\mathsf{7}\mathrm{,}\mathsf{test}\text{\_}\mathsf{zero}\mathsf{6}\mathrm{,}\mathsf{test}\text{\_}\mathsf{zero}\mathsf{6}\text{\_}\mathsf{line}\mathsf{0}\mathrm{,}\dots \mathrm{,}\mathsf{test}\text{\_}\mathsf{nine}\mathsf{979}\mathrm{,}\\ & \mathsf{test}\text{\_}\mathsf{nine}\mathsf{979}\text{\_}\mathsf{line}\mathsf{7}\mathrm{,}\dots \mathrm{,}\mathsf{line}{M}_{250}\}\end{array}\\ \begin{array}{rl}\mathsf{CN}=& \{\mathsf{Image}\mathrm{,}\mathsf{Line}\mathrm{,}\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{,}\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{,}\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{,}\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{,}\mathsf{TopLeft}\mathrm{,}\mathsf{TopCenter}\mathrm{,}\mathsf{TopRight}\mathrm{,}\mathsf{MidLeft}\mathrm{,}\\ & \mathsf{MidCenter}\mathrm{,}\mathsf{MidRight}\mathrm{,}\mathsf{BotLeft}\mathrm{,}\mathsf{BotCenter}\mathrm{,}\mathsf{BotRight}\mathrm{,}\mathsf{Short}\mathrm{,}\mathsf{Medium}\mathrm{,}\mathsf{Long}\}\end{array}\\ \mathsf{RN}=\{\mathsf{contains}\mathrm{,}\mathsf{intersects}\}.\\ \mathcal{T}=\{\mathit{C}⊑\mathsf{Line}|\mathit{C}\notin \{\mathsf{Image}\mathrm{,}\mathsf{Line}\}\}.\end{array}$$

5.4.2. Setting

For MNIST we used the example neural network provided by PyTorch10

¹⁰

https://github.com/pytorch/examples/tree/master/mnist

as the classifier to be explained. The classifier achieved 99.8% accuracy on the training set and 99.2% on the test set. On the explanation dataset, the accuracy is 73%, and a confusion matrix for the classifier on the explanation dataset is shown in Fig. 11. The performance of the classifier is poor when compared to the whole test set, due to the fact that we have included several manually selected exemplars, which are unusually drawn, but still valid as digits (based on our own judgement). Similarly to CLEVR-Hans3, we generated explanations for the predictions of the classifier on the exemplars using KGrules-HT (Alg. 3) and KGrules-H (Alg. 1) with Alg. 4 as the merge operation, and loaded the explanation dataset in GraphDB for acquiring certain answers. We also experimented with the QLCS as the merge operation, but the resulting queries mostly contained a large number of variables which could not be effectively minimized, which could be due to the complex connections between variables with a symmetric role.

Fig. 11.

Confusion matrix of the classifier on the explanation dataset for MNIST.

5.4.3. Results

For MNIST there does not exist a ground truth semantic description for each class, as was the case for CLEVR-Hans3, nor is there a pre-determined bias of the classifier, thus we could not easily measure our framework’s usefulness in this regard. Instead, since the explanation dataset was constructed automatically, we explored quality related features of the generated explanations.

For all digits the algorithm produced at least one correct rule (precision = 1) and a rule with exceptions with recall = 1. The highest degree of rule queries for each digit are shown as a bar-plot in Fig. 12a. In general, the values of the metric seem low, with the exception of digit 0, which would indicate that the algorithms did not find a single rule which approximates the pos-set to a high degree. For some of the digits, including 0, the highest degree rule is also a correct rule. For closer inspection, we show the best degree rule query for digit 0 which is the highest, and for digit 5 which is the lowest.

Fig. 12.

Metrics of generated rule queries for MNIST.

The explanation rule for digit 0 involved six lines, as indicated by the conjuncts $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_6\mathrm{)}$ . For five of the six lines, the explanation rule query included their location in the image, indicated by the conjuncts $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{BotRight}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{TopRight}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . For all six lines the explanation rule included information about their orientation, indicated by the conjuncts $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . Finally, the rule-query included the following conjuncts which show which lines intersect each other $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_3\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_4\mathrm{,}{\mathit{y}}_6\mathrm{)}$ . A rule query with so many conjuncts could potentially be difficult for a user to decipher, so in this case we found it useful to visualize the rules. The above rule is visualized in Fig. 13a. The visualization is clear and intuitive as an explanation for digits classified as zeroes, however visualization of rules will not be possible in all applications. This shows the importance of taking under consideration understandability when designing explaination pipelines, which in our case depends mostly on the vocabulary and expressivity of the underlying explanation dataset. In this case, the vocabulary used was itself somewhat obscure for users (sets of intersecting lines are not easy to understand by reading a rule), which could have been mitigated if the explanation dataset had been curated by humans and not created automatically. In this particular use-case it was not a problem however, since the visualization of rules was easy in most cases.

Fig. 13.

Visualizations of best recall correct rules for digits.

Fig. 14.

Misclassified digits that follow the best recall correct rules.

The highest degree explanation rule for digit 5, which was the lowest out of the best of all digits, again involved six lines indicated by the conjuncts $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_6\mathrm{)}$ . This time however, only three lines had information about their location in the image, indicated by the conjuncts $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , and five lines had information about their orientation $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . Furthermore, this rule-query included information about the size of two lines, indicated by the conjuncts $\mathsf{Medium}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . Finally, as with before, we get a set of conjuncts showing which lines intersect each other: $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_3\mathrm{,}{\mathit{y}}_5\mathrm{)}$ . This rule query is not easy to understand and it is even difficult to visualize, since there is not enough information about the location of each line, thus it is not actually usable. This was expected to an extent, due to the low value of the degree metric, but again highlights the importance of taking usability under consideration when choosing which rule-queries to show to a user.

Regarding correct rules, the algorithm produced several for each digit. Since the sets of certain answers of correct rule queries are subsets of the pos-set of each class, we measured the per class fidelity of the disjunction of all correct rules, as if giving a user a rule-set, similarly to the Mushroom experiment (Section 5.1). In Fig. 12c we show as a bar-plot the fidelity for each class. With the exception of digit one, the pos-sets of all digits were sufficiently covered by the set of correct rules. The failure for digit 1 was expected, since the descriptions of the exemplars classified as 1 contain few lines (for example consisting of a single large line in the middle) which tend to be part of descriptions of other digits as well (all digits could be drawn in a way in which there is a single line in the middle). This is a drawback of the open world assumption of DLs since we cannot guarantee the non-existence of lines that are not provided in the descriptions. The open world assumption is still desirable since it allows for incomplete descriptions of exemplars. In cases such as the medical motivating example used throughout this paper, a missing finding such as “Dyspnoea” does not always imply that the patient does not suffer from dyspnoea. It could also be a symptom that has not been detected or has been overlooked.

The highest recall of a single correct rule for each digit is shown as a bar-plot in Fig. 12b. Since correct rules are easily translated into IF-THEN rules, we expected them to be more informative than the highest degree ones, which requires looking at the exceptions to gain a clearer understanding of the rule. We investigate closer by analyzing the best correct rule for each digit.

For digit 0, the best correct rule was the same as the highest degree rule presented previously. In Fig. 14a we provide an example of a six misclassified as a 0, which follows this correct rule. Comparing the misclassified 6 with the visualizations for rules of the digits 0 (Fig. 13a) and 6 (Fig. 13f) we can see that this 6 might have been misclassified as a 0 because the closed loop part of the digit reaches the top of the image. According to the correct rule for 0, an image that contains two vertical semicircles in the left and right sides of the image is classified as a 0, and because of this peculiarity in the drawing of the misclassified six, the image (Fig. 13a) obeys this rule.

The best correct rule for digit 1 had the lowest recall out of all correct rules for other digits, which means that it returned a small subset of the positives. Specifically, this rule returned only two of the 30 individuals classified as the digit 1. It was still usable as an explanation however, as it only involved two lines $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{contains}\mathrm{(}\mathit{x}\mathrm{,}{\mathit{y}}_2\mathrm{)}$ , both of which were thoroughly described with regard to their location $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , their orientation $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , their length $\mathsf{Long}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ and the fact that they intersect $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_2\mathrm{)}$ . This rule is visualized in Fig. 13b.

For digit 2, the best correct rule query returned nine out of the 25 positives, three of which were missclassified by the classifier. This rule involved three lines, of which two had conjuncts indicating their location $\mathsf{BotRight}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{BotLeft}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , only one line contained information about its orientation and size $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Long}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , and the only other information was that $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_3\mathrm{)}$ . Note that for ${\mathit{y}}_2$ the only available information was that it intersects ${\mathit{y}}_3$ . This query is difficult to visualize, due to the missing information about two of the three lines, however it is still useful as an explanation. Specifically, ${\mathit{y}}_3$ represents a long diagonal line from the bottom left to the middle of the image, which is a characteristic of only the digits 2 and 7. Additionally, there is a line of any orientation in the bottom right of the image, which would differentiate it from a typical 7, and another line which intersects the long diagonal at any position. As is apparent also in the confusion matrix of the classifier on the explanation dataset (Fig. 11), the black-box often mixed up sevens with twos, and this explanation rule returns one of the sevens which is misclassified as a two, shown in Fig. 14d. This digit is not typically drawn, and from the rule query the information we get is that it might have been misclassified because of the existence of a line at the bottom right.

To investigate closer, the next correct rule which we analyze is that of highest recall for digit 7. This query returned only three of the 24 images which were classified as sevens, and all three were correct predictions by the classifier. The rule involved two intersecting lines ( $\mathsf{intersects}\mathrm{(}{y}_1\mathrm{,}{y}_2\mathrm{)}$ ), of which the first is described as $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Long}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ $\mathsf{TopLeft}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{TopRight}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ which is clearly the characteristic top part of the digit, while the second line is described as $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{y}_2\mathrm{)}\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{y}_2\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{y}_2\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{y}_2\mathrm{)}$ , $\mathsf{Long}\mathrm{(}{y}_2\mathrm{)}$ , which is the diagonal part of the digit. The description of the diagonal has a different description than the diagonal line which was part of the rule for digit 2. Instead of $\mathsf{BotLeft}\mathrm{(}\mathsf{y}\mathrm{)}$ , the rule contains a conjunct $\mathsf{MidRight}\mathrm{(}\mathsf{y}\mathrm{)}$ . This could be another hint as to why the 7 shown in Fig. 14d was not classified as correctly, as the digit appears to be leaning slightly to the right, which makes the diagonal pass through $\mathsf{BotLeft}$ , which is in the description of the diagonal for a digit 2 instead of $\mathsf{MidRight}$ which is for digit 7. To conclude if this is the case however would require investigating more rules, since the one presented covers only a subset of exemplars classified as digit 7.

For digit 3, the best correct explanation rule returned five of the 26 individuals which were classified as 3, including one misclassified 8. This rule involved seven different lines, thus it was not expected to be understandable by a user at a glance. However, there was plentiful information for each line in the rule, which made it possible to visualize. Specifically, regarding the location of the lines, the rule query contained the conjuncts $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{BotRight}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ . Regarding orientation, five of the seven lines had relevant conjuncts: $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ . Additionally, three lines had information about their size $\mathsf{Short}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Medium}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . Finally, the explanation rule contained conjuncts showing which lines intersect each other: $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_3\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_4\mathrm{,}{\mathit{y}}_6\mathrm{)}$ . This rule-query is visualized in Fig. 13c. An interesting aspect of this explanation, is that the two lines which are at the top center ( ${\mathit{y}}_1$ and ${\mathit{y}}_5$ ) do not have a specified orientation, while the other four lines are involved in more conjuncts in the explanation rule query and are described in more detail. This could be an indication of the importance of these lines for a digit to be classified as a 3. However, these lines could also be a part of other digits such as 5, which is the next digit which we analyze.

For the digit 5, the best correct rule query returned four of the 31 positives for the class of which one is a misclassified 3. It is a very specific query involving seven lines, all of which are described regarding their orientation $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , and their location $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{BotLeft}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{TopRight}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{BotRight}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ . There was no information about lines’ sizes, and there are five line intersections $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_3\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_6\mathrm{,}{\mathit{y}}_7\mathrm{)}$ . This query is visualized in Fig. 13e. An interesting aspect of this rule-query is the fact that it contains a misclassified 3 in its set of certain answers, specifically the three shown in Fig. 14c. In the context of the proposed framework, the 3 is misclassified because it obeys the correct rule for the digit 5. From comparing the visualization of the correct rule for the digit 5, and the misclassified 3, we can see that the digit obeys the rule because the top part of the three is vertically compressed, making it less distinguishable from a 5. This clearly shows us a potential flaw of the classifier.

For the digit 4, the best correct rule query returned five of the 22 positives all of which were correct predictions. The query involved three lines which were all well described regarding their orientation $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , and their location $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ . Two lines were also described with respect to their size $\mathsf{Medium}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Long}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , and there were two intersections of lines $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_3\mathrm{)}$ . This rule is visualized in Fig. 13d. This is a straight-forward description of the digit four, and as expected it covers only true positives.

For the digit 6, the best resulting correct rule involved the most variables (each representing a line) out of all correct rules. It returned four of the 18 positives for the class all of which were correct predictions. Of the eight lines described in the query, seven had information about their orientation $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_8\mathrm{)}$ . All lines were desribed with respect to their position $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{BotRight}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_8\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_8\mathrm{)}$ . Additionally four lines had a determined size $\mathsf{Short}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{Medium}\mathrm{(}{\mathit{y}}_8\mathrm{)}$ , and there were five intersections of lines $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_8\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_5\mathrm{,}{\mathit{y}}_8\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_6\mathrm{,}{\mathit{y}}_7\mathrm{)}$ . This rule is visualized in Fig. 13f, it is a straight-forward description of a digit 6.

For digit 8, the best correct rule query returned four of the 20 positives, all of which are classified correctly. It involved seven lines, of which five were described with respect to their orientation $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , six regarding their location $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{BotCenter}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ , and five regarding their size: $\mathsf{Medium}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_7\mathrm{)}$ . Finally, the rule query involved four intersections of lines $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_5\mathrm{,}{\mathit{y}}_7\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_6\mathrm{,}{\mathit{y}}_7\mathrm{)}$ . This rule is difficult to visualize due to the missing information (only four of the seven lines have information about both their location and orientation), and thus is not really useful as an explanation.

Finally, the best correct rule query for digit 9 returned five of the 15 positives, of which all were correct predictions by the classifier. It involved six lines which were all thoroughly described regarding their orientation $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{Line}\mathsf{0}\mathsf{deg}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{Line}\mathsf{45}\mathsf{deg}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Line}\mathsf{90}\mathsf{deg}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{Line}\mathsf{135}\mathsf{deg}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ , and their location $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_1\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_2\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{MidCenter}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{MidLeft}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{BotRight}\mathrm{(}{\mathit{y}}_4\mathrm{)}$ , $\mathsf{TopCenter}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{MidRight}\mathrm{(}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{MidLeft}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . Additionally, two lines were described regarding their size $\mathsf{Medium}\mathrm{(}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{Short}\mathrm{(}{\mathit{y}}_6\mathrm{)}$ . The query also contained three conjuncts which indicated intersections of lines $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_3\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_1\mathrm{,}{\mathit{y}}_5\mathrm{)}$ , $\mathsf{intersects}\mathrm{(}{\mathit{y}}_2\mathrm{,}{\mathit{y}}_6\mathrm{)}$ . This query is visualized in Fig. 13h, it is a straight-forward description of a digit 9.

5.5. Discussion

The proposed approach performed similarly with the state-of-the-art on tabular data, was able to detect biases in the CLEVR-Hans case, detect flaws of the classifier in the Visual Genome case, and provided meaningful explanations even in the MNIST case. In this framework, the resulting explanations depend (almost exclusively) on the properties of the explanation dataset. In an ideal scenario, end-users trust the explanation dataset, the information it provides about the exemplars and the terminology it uses. It is like a quiz, or an exam, for the black-box, which is carefully curated by domain experts. This scenario was simulated in the CLEVR-Hans3 and Visual Genome use-cases in which the set of rules produced by the proposed algorithms clearly showed in which cases the black-box classifies items in specific classes, highlighting potential biases acquired during training. The framework is also useful when the explanation dataset is created automatically by leveraging traditional feature extraction, as is shown in the MNIST use-case. In this case, we found the resulting queries to be less understandable than before, which stems mainly from the vocabulary used, since sets of intersecting lines are not easily understandable unless they are visualized. They are also subjectively less trustworthy, since there are usually flaws with most automatic information extraction procedures. However, since sets of correct rules sufficiently covered the sets of individuals, and rules with exceptions achieved decent performance regarding precision, recall and degree, if an end-user invested time and effort to analyze the resulting rules, they could get a more clear picture about what the black-box is doing.

We also found interesting the comparison of correct rules with those with exceptions. Correct rules are, in general, more specific than others, as they always have a subset of the pos-set as certain answers. This means that, even though they might be more informative, they tend to involve more conjuncts than rules with exceptions, which in extreme cases could impact understandability. On the other hand, rules with exceptions can be more general, with fewer conjuncts, which could positively impact understandability. Although, utilizing these rules should involve examining the actual exceptions, which could be a lot of work for an end-user, we believe that these exceptions themselves can be very useful in order to detect biases and investigate the behaviour of the model on outliers. In order to eliminate the complexity involved in the investigation of these exceptions, in the future we plan to further study the area and propose a systematic way of exploiting them. These conclusions were apparent in the explanations generated for the class 3 of CLEVR-Hans3 (Table 6), where the best correct rule was very specific, involved five objects and had a relatively low recall (0.42), while the best rule with exceptions was exactly the ground truth class description and had very high precision (0.99). So in this case a user would probably gain more information about the classifier if they examined the rule with exceptions along with the few false positives, instead of examining the best correct rule, or a set of correct rules.

Another observation we made, is the fact that some conjuncts were more understandable than others when they were part of explanation rules. For instance in MNIST, knowing a line’s location and orientation was imperative for understanding the rule via visualization, while conjuncts involving line intersections and sizes seemed not that important, regardless of metrics. This is something which could be leveraged either in explanation dataset construction (for example domain experts weigh concepts and roles depending on their importance for understandability), or in algorithm design (for example a user could provide as input concepts and roles which they want to appear in explanation rules). We are considering these ideas as a main direction for future work which involves developing strategies for choosing which rules are best to show to a user.

Finally, in the first experiment (Section 5.1), it is shown that KGrules-H can be used to generate explanations in terms of feature data similarly to other rule-based methods, even if it is not the intended use-case. An interesting comparison for a user study would be between different vocabularies (for example using the features vs using external knowledge). We note here that the proposed approach can always be applied on categorical feature data, since their transformation to an explanation dataset is straight-forward. This would not be the case if we also had numerical continuous features, in which case we would either require more expressive knowledge to represent these features, or that the continuous features be discretized. Another result which motivates us to explore different knowledge expressivities in the future, was the failure of the algorithms to produce a good (w.r.t. the metrics) explanation for the digit 1 in the MNIST experiment (Section 5.4). Specifically, it was difficult to find a query which only returns images of this digit, since a typical description of a “1” is general and tends to always partially describe other digits. This is something which could be mitigated if we allowed for negation in the generated rules, and this is the second direction which we plan to explore in the future.

6. Conclusions and future work

In this work we have further developed a framework for rule-based post hoc explanations of black-box classifiers. The explanations are expressed as Horn rules which use terms from a given vocabulary, instead of the classifier’s features. This allows for intuitive explanations even when the feature space of the classifier is too complex to be used within understandable rules (pixels, audio signals etc). The rules are also accompanied by theoretical guarantees regarding their correctness for explaining the classifier, given what we call an explanation dataset. The idea of the explanation dataset is at the core of our framework, as it is the probe we use to observe the black-box, by feeding it exemplar data and finding rules which explain its output. The explanation dataset also contains the knowledge from which the semantics of the rules are derived. The problem of finding such rules given an explanation dataset was approached as a search problem in the space of semantic queries, by starting with the most specific queries describing positively classified exemplars, and then progressively merging them using heuristic criteria. The queries are then approximately condensed, converted to rules and are shown to the end-user.

There are multiple directions towards which we plan to extend the framework in the future. First of all, we are currently investigating different strategies for choosing which explanation rules are best to show to a user such that they are both informative and understandable. To do this, we also plan to extend our evaluation framework for real world applications to include user studies. Specifically, we are focusing on decision critical domains in which explainability is crucial, such as the medical domain, and in collaboration with domain experts, we are developing explanation datasets, in addition to a crowd-sourced explanation evaluation platform. There are many interesting research questions which we are exploring in this context, such as what constitutes a good explanation dataset, what is a good explanation, and how can we build the trust required for opaque AI to be utilized in such applications.

Another direction which we are currently exploring involves further investigation of our framework in order to fully exploit its capabilities. In particular, the existence of exceptions might have a large impact on both understandability of the produced explanations, and their ability to approximate the behavior of the black-box model.

We believe that the systematic study of exceptions could provide useful information to the end-user regarding biases and outliers, and could drive the way towards incorporating local explanations to our framework. Stemming from this, we want to extend the framework, both in theory and in practice, to incorporate different types of explanations. This includes local explanations which explain individual predictions of the black-box, and counterfactual or contrastive explanations which highlight how a specific input should be modified in order for the prediction of the classifier to change. This extension is being researched with the end-user in mind, and we are exploring the merits of providing a blend of explanations (global, local, counterfactual) to an end-user.

A fourth and final direction to be explored involves extending the expressivity of explanation rules, in addition to that of the underlying knowledge. Specifically, the algorithms developed in this work require that if the knowledge has a non-empty TBox, it has to be eliminated via materialization before running the algorithms. Thus, we are exploring ideas for algorithms which generate explanation rules in the case where the underlying knowledge is represented with DL dialects in which the TBox cannot be eliminated, such as DL_Lite. Finally, regarding the expressivity of explanation rules, we plan to extend the framework to allow for disjunction, which is a straight-forward extension, and for negation, which is much harder to incorporate in the framework while maintaining the theoretical guarantees, which we believe are crucial for building trust with end-users.