Introduction

Over the past decade, Artificial Intelligence and in particular Deep Neural Networks have accomplished impressive achievements in various tasks such as Image Recognition and Natural Language Processing in numerous domains like medicine, finance, arts, and many more. In order to tackle challenging problems, the models become deeper and deeper and their structure complexity is constantly rising, making them inherently opaque. While traditional machine learning models, such as decision trees, are interpretable by design, modern deep neural networks are hard to explain due to their complex architecture and operation. This opacity raises ethical and legal concerns regarding the real-life use of such models and has lead to the emergence of eXplainable Artificial Intelligence (XAI), to make the operation of opaque AI systems more comprehensible to humans [1,2,3,4]. XAI is already a major topic in many events of the AI community and is constantly engaging more researchers due to its immediate and important effect on the application of AI systems.

Knowledge Graphs (KG) and Description Logics (DL) offer an advanced, adaptable and interpretable framework of high expressiveness that can be employed to explain complex neural networks exploiting years of research and improvement on the area. Knowledge graphs [5], 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 [4].

In this paper, we introduce a novel explainability framework for representing model-agnostic knowledge graph-based explanations, as conjunctive queries (resulting to explanations like "animals in images with household items are classified as domestic animals"), approaching the task as a Query Reverse Engineering (QRE) problem, deriving the explanation-queries from the respective outputs of the model. We discuss the creation of appropriate datasets for our methods, and we propose algorithms to compute such explanations. Additionally, we investigate evaluation methods and metrics, and finally, we evaluate the methodology and algorithms experimenting with data from the CLEVR-Hans3 [6] dataset, extracting explanations for deep learning models.

Related Work

Approaches to explainability vary with regard to data domain (images, text, tabular), form of explanations (rule-based, counterfactual, feature importance etc.), and scope (global, local) [3]. Closely related to this work are global rule-based explanation methods. These attempt to extract rules based on the predictions of a black-box classifier on a dataset. Many of these methods are based on statistics [7,8] or extracting rules from decision trees [9,10], while others are based on logics [11,12]. Extensionally related to this work are also global prototype explanation methods [13,14] which present specific representative samples from a dataset as explanations of black-box classifiers.

A key feature of the algorithms proposed in Section 5 is the computation of the Least Common Subsumer (LCS). This problem has been extensively studied for various decription logic expressivities [15,16,17,18]. Furthermore, this work makes use of the strong theoretical and practical results in the area of semantic query answering [19,20,21,22] for evaluating and applying the proposed algorithms in a practical setting.

Numerous works have addressed the Query Reverse Engineering problem, both for knowledge bases and traditional databases [23,24,25], and tools have been developed to offer an easy and user friendly way to perform QRE on knowledge bases [26]. The key difference between these works and ours is that we are able to find an approximate solution in cases where there is no exact answer, thanks to the heuristic approach of our algorithms (for more details see Section 5).

Background

Let 𝒱 = ⟨CN, RN, IN⟩ be a vocabulary, with CN, RN, IN mutually disjoint finite sets of concept, role and individual names, respectively. Let also 𝒯 and 𝒜 be a terminology (TBox) and an assertional database (ABox), respectively, over 𝒱 using a Description Logics (DL) dialect ℒ, i.e. a set of axioms and assertions that use elements of 𝒱 and constructors of ℒ. The pair ⟨𝒱, ℒ⟩ is a DL-language, and 𝒦 = ⟨𝒯 , 𝒜⟩ is a knowledge base (KB) over this language. The semantics of KBs are defined in the standard way using interpretations [27]. Given a domain ∆, an interpretation ℐ = (∆ ℐ , • ℐ ) assigns a set 𝐶 ℐ ⊆ ∆ ℐ to concept 𝐶, a set 𝑟 ℐ ⊆ ∆ ℐ × ∆ ℐ to role 𝑟, and an object 𝑎 ℐ ∈ ∆ to individual 𝑎. ℐ is a model of an ABox 𝒜 iff 𝑎 ℐ ∈ 𝐶 ℐ for all 𝐶(𝑎) ∈ 𝒜, and (𝑎 ℐ , 𝑏 ℐ ) ∈ 𝑟 ℐ for all 𝑟(𝑎, 𝑏) ∈ 𝒜. ℐ is a model of a TBox 𝒯 if it satisfies all axioms in 𝒯 .

Given a vocabulary 𝒱, a conjunctive query (simply, a query) 𝑞 is an expression { ⟨𝑥 1 , . . . 𝑥 𝑘 ⟩ | ∃𝑦 1 . . . ∃𝑦 𝑙 .(𝑐 1 ∧ . . . ∧ 𝑐 𝑛 ) }, where 𝑘, 𝑙 ≥ 0, 𝑛 ≥ 1, 𝑥 𝑖 , 𝑦 𝑖 are variable names, each 𝑐 𝑖 is an atom 𝐶(𝑢) or 𝑟(𝑢, 𝑣), where 𝐶 ∈ CN, 𝑟 ∈ RN, 𝑢, 𝑣 ∈ IN ∪ {𝑥 𝑖 } 𝑘 𝑖=1 ∪ {𝑦 𝑖 } 𝑙 𝑖=1 and all 𝑥 𝑖 , 𝑦 𝑖 appear in at least one atom. The vector ⟨𝑥 1 , . . . 𝑥 𝑘 ⟩ is the head of 𝑞, its elements are the answer variables, and {𝑐 1 , . . . , 𝑐 𝑛 } is the body of 𝑞. If 𝑞 has no answer variables it is boolean, and if its body is a singleton, it is atomic. In this paper we focus on non-boolean queries having one answer variable and in which all arguments or all 𝑐 𝑖 are variables, which are called instance queries. For simplicity we write instance queries as 𝑞 = {𝑐 1 , ..., 𝑐 𝑛 }, considering always 𝑥 as the answer variable. Given a KB 𝒦, a query 𝑞 and an interpretation ℐ of 𝒦, an individual 𝑎 ∈ IN is an answer to 𝑞 in ℐ if it there is a successful variable substitution, substituting 𝑎 ℐ for 𝑥. This is formally defined as a match, a mapping 𝜋 : VN(𝑞) → ∆ ℐ such that 𝜋(𝑢) ∈ 𝐶 ℐ for all 𝐶(𝑢) ∈ 𝑞, and (𝜋(𝑢), 𝜋(𝑣)) ∈ 𝑟 ℐ for all 𝑟(𝑢, 𝑣) ∈ 𝑞. Furthermore, it is a certain answer iff it is an answer under all interpretations that are models of 𝒦. The set of certain answers to 𝑞 is cert(𝑞, 𝒦). In some DL dialects, determining the certain answers to a query can be reduced to determining the answers of a special model, called the canonical model [28] [29] 𝒞 𝒯 ,𝒜 of 𝒦 = ⟨𝒯 , 𝒜⟩. In the dialect we use for our experiments, called Horn 𝒮ℋℐ𝒬, this process is even simpler since we can guarantee that the canonical model is finite.

Consider a vocabulary 𝒱 = ⟨CN, RN, IN⟩, a knowledge base 𝒦 = ⟨𝒯 , 𝒜⟩, where 𝒯 is the TBox and 𝒜 the ABox of 𝒦 using a DL dialect ℒ on 𝒱, and the set 𝒬 of all (conjunctive) queries over 𝒱. Let 𝑄 ⊆ 𝒬 be a set of queries over 𝒦. With a slight abuse of notation, we write cert(𝑄, 𝒦) to denote the set of all answers to the queries of 𝑄, i.e. cert(𝑄, 𝒦) = ∪ 𝑞∈𝑄 cert(𝑞, 𝒦). We can partially order 𝒬 using query subsumption: A query 𝑞 2 subsumes a query 𝑞 1 (we write 𝑞 1 ≤ 𝑆 𝑞 2 ) iff there is a substitution 𝜃 s.t. 𝑞 2 𝜃 ⊆ 𝑞 1 . If 𝑞 1 , 𝑞 2 are mutually subsumed, they are syntactically equivalent (𝑞 1 ≡ 𝑆 𝑞 2 ).

Let be 𝑞 an instance query and 𝑞 ′ ⊆ 𝑞. If 𝑞 ′ is a minimal subset of 𝑞 s.t. 𝑞 ′ ≤ 𝑆 𝑞, then 𝑞 ′ is a condensation of 𝑞 (cond(𝑞)). If that minimal 𝑞 ′ is the same set as 𝑞, then 𝑞 is condensed [30].

Explaining Opaque ML Classifiers

We are now ready to define and explain the operation of machine learning (ML) classifiers. In this section we only consider boolean classifiers in our definitions, that classify individuals to two classes, but the generalization from boolean to multi-class classifiers is considered trivial. Definition 1. Given a set 𝒟 ⊆ IN, a classifier F defined on 𝒟 is a mapping from 𝒟 to {0, 1}, i.e. F : 𝒟 → {0, 1}. We call 𝒟 the domain of the classifier and with F(𝒟) we denote the set of all elements of 𝒟 that are classified to 1, i.e.

F(𝒟) = {𝑎 ∈ 𝒟 | F(𝑎) = 1}.

Note that deep neural networks typically classify objects, taking as input other sources of information (images, etc) not included in their semantic description in 𝒦. On the other hand, knowledge graphs usually contain this information in the form of datatype properties of objects. Throughout the theoretical analysis we omit this information from 𝒦, for simplicity, however for the evaluation we compute F(𝒟) from images of objects (see Section 6 for details). Definition 2. Let 𝒟 ⊆ IN and F be a classifier on 𝒟, 𝒦 a KB over a vocabulary 𝒱 = ⟨CN, RN, IN⟩. A query 𝑞 over 𝒱, is a FO-explanation (first-order explanation), or simply an explanation, of F over 𝒦, iff cert(𝑞, 𝒦) = F(𝒟).

Explanations of ML classifiers do not always exist. Moreover, they are not always unique or helpful in practice. In the following, we introduce the notion of approximate explanations , in order to relax the demand to exactly match the output of the classifier. A query 𝑞, is an approximate FO-explanation, or simply an approximate explanation of F, over 𝒦, iff cert(𝑞, 𝒦) ∩ F(𝒟) ̸ = ∅.

Of special interest are approximate explanations that guarantee that all their answers are classified by F as positive. A query 𝑞, is an under-FO-explanation, or simply an under-explanation, of F over 𝒦, iff it is an approximate explanation of F and cert(𝑞, 𝒦) ⊆ F(𝒟).

Of interest are also approximate explanations for which all individuals classified by F as positive are in their answer set. A query 𝑞, is an over-FO-explanation, or simply an over-explanation, of F over 𝒦, iff it is an approximate explanation of F and F(𝒟) ⊆ cert(𝑞, 𝒦). In most cases multiple approximate explanations exist, so we need to find a way to evaluate them. In the following paragraph we propose a set of evaluation metrics for such explanations.

Explanation Evaluation Metrics

We can define similarity measures that take into account the syntactical form of the queries, their certain answers over any ABox, or their certain answers over a specific knowledge base. For the syntactic similarity of two queries, there is a lot of work in the area (see for example the work on query refinement and graph distance). For answer-based similarity for any ABox, it is not obvious how to define similarity measures, since it is difficult to consider all ABoxes or to capture all the TBox information by checking the syntax. The case of answer-based similarity for a specific knowledge base is more intuitive and can be addressed using either the well-known Jaccard similarity coefficient defined on sets, or other popular metrics from the area of machine learning like precision and recall. So, we define the following three similarity measures on 𝒬 for a query-explanation 𝑞 of a classifier F over a specific knowledge base 𝒦 and a set 𝒟 ⊆ IN as follows:

Degree A Jaccard distance-based similarity measure, it's obvious that the degree of an (exact) explanation is equal to 1. deg(𝑞, F) = |cert(𝑞,𝒦)∩F(𝒟)| |cert(𝑞,𝒦)∪F(𝒟)| Precision A similarity measure inspired by the precision of ML classifiers, it's obvious that the precision of an under-explanation is equal to 1. pre(𝑞, F) = |cert(𝑞,𝒦)∩F(𝒟)|

|cert(𝑞,𝒦)|

Recall A similarity measure inspired by the recall of ML classifiers, it's obvious that the recall of an over-explanation is equal to 1. rec(𝑞, F) = |cert(𝑞,𝒦)∩F(𝒟)| |F(𝒟)|

Computing Explanations

In this section we describe in detail the proposed algorithms, and introduce the concept of an Explanation Dataset, which plays a key role for effectively utilizing the proposed algorithms in a practical setting.

Algorithms

In order to unify explanations we use the notion of the least common subsumer (LCS). Given two queries 𝑞 1 , 𝑞 2 , their least common subsumer LCS(𝑞 1 , 𝑞 2 ) is defined as the query 𝑞 for which 𝑞 1 , 𝑞 2 ≤ 𝑆 𝑞 and ∀𝑞 ′ : 𝑞 1 , 𝑞 2 ≤ 𝑆 𝑞 ′ ⇔ 𝑞 ≤ 𝑆 𝑞 ′ . The least common subsumer is the most specific generalization of 𝑞 1 , 𝑞 2 .

In order to manipulate queries and compute explanations, we use the representation of interpretations and queries as labeled graphs. For interpretations, each element 𝑎 ℐ ∈ ∆ ℐ is represented by a node with a label which contains every concept 𝐶 ∈ CN for which 𝑎 ℐ ∈ 𝐶 ℐ . Two nodes 𝑎 ℐ , 𝑏 ℐ are connected with an edge with label 𝑟 if (𝑎 ℐ , 𝑏 ℐ ) ∈ 𝑟 ℐ . This graph can be described by a triple (𝑉, 𝐸, 𝐿) where 𝑉 = ∆ ℐ are the nodes 𝑎 ℐ , 𝐸 ⊆ ∆ ℐ × RN × ∆ ℐ are the edges (𝑎 ℐ , 𝑟, 𝑏 ℐ ), and 𝐿 : 𝑉 → 2 CN is the labeling function 𝐿(𝑎 ℐ ) = {𝐶, 𝐷, . . . } of the nodes. The graph representation for queries is defined in the same way, but with nodes corresponding to variables and labels and edges to the conjuncts containing those variables.

These representations are useful because a lot of the concepts we have presented so far can be rephrased in terms of homomorphisms between labeled graphs. Given two labeled graphs

𝐺 1 = (𝑉 1 , 𝐸 1 , 𝐿 1 ), 𝐺 2 = (𝑉 2 , 𝐸 2 , 𝐿 2 ), a mapping ℎ : 𝑉 1 → 𝑉 2 is called a homomorphism iff it respects the structure of 𝐺 1 , or more formally: (i) ∀𝑣 ∈ 𝑉 1 , 𝐿 1 (𝑣) ⊆ 𝐿 2 (ℎ(𝑣)) and (ii) ∀𝑢, 𝑣 ∈ 𝑉 1 , (𝑢, 𝑟, 𝑣) ∈ 𝐸 1 ⇒ (ℎ(𝑢), 𝑟, ℎ(𝑣)) ∈ 𝐸 2 .

If such a mapping exists we say that 𝐺 1 is homomorphic to 𝐺 2 and we write 𝐺 1 → 𝐺 2 .

A match 𝜋 can now be rephrased as a homomorphism from the query graph of 𝑞 to the interpretation graph of 𝐼, and 𝑎 is an answer to 𝑞 if there is such a homomorphism with 𝜋(𝑥) = 𝑎 ℐ and a certain answer if there is a homomorphism to the canonical model with 𝜋(𝑥) = 𝑎 𝒞 𝒯 ,𝒜 . Subsumption can also be described in terms of homomorphisms since its definition implies that

𝐺 𝑞 1 → 𝐺 𝑞 2 ⇔ 𝑞 2 ≤ 𝑆 𝑞 1

, where 𝐺 𝑞 is the graph of query 𝑞.

In order to calculate the LCS we use an extension of the Kronecker product of graphs to labeled graphs. Given two labeled graphs 𝐺 1 = (𝑉 1 , 𝐸 1 , 𝐿 1 ), 𝐺 2 = (𝑉 2 , 𝐸 2 , 𝐿 2 ) the Kronecker product 𝐺 = 𝐺 1 × 𝐺 2 of those graphs is: 𝐺 = (𝑉, 𝐸, 𝐿), 𝑉 = 𝑉 1 × 𝑉 2 (Cartesian product of sets),

((𝑢 1 , 𝑟, 𝑣 1 ) ∈ 𝐸 1 , (𝑢 2 , 𝑟, 𝑣 2 ) ∈ 𝐸 2 ) ⇔ ((𝑢 1 , 𝑢 2 ), 𝑟, (𝑣 1 , 𝑣 2 )) ∈ 𝐸, 𝐿((𝑣 1 , 𝑣 2 )) = 𝐿 1 (𝑣 1 ) ∩ 𝐿 2 (𝑣 2 )

As with the Kronecker product of unlabeled graphs, it holds that 𝐻 → 𝐺 1 , 𝐺 2 ⇔ 𝐻 → 𝐺 1 × 𝐺 2 , this implies that the graph of LCS(𝑞 1 , 𝑞 2 ) is 𝐺 𝑞 1 × 𝐺 𝑞 2 , with the node (𝑥, 𝑥) becoming the new answer variable and the other nodes of 𝐺 𝑞 1 × 𝐺 𝑞 2 are renamed arbitrarily. Calculating the LCS using the Kronecker product involves 𝑂(𝑛 2 𝑚 2 ) operations, where

𝑛 = |𝑉 1 |, 𝑚 = |𝑉 2 |.

Even though the Kronecker product between two queries computes the LCS, the query it produces is not minimal with respect to the number of variables. Since these queries are intended to be shown to humans as explanations, the minimization of the number of variables is imperative. However, condensing a query is coNP-complete [30]. For this reason, we utilize Algorithm 1 which removes redundant conjuncts and variables, however without a guarantee of producing a fully condensed query.

For each pair of variables present in a query, Algorithm 1 checks if unifying the two variables is equivalent to deleting one of the two, in which case the variable and conjuncts are deleted. Verifying the correctness of Algorithm 1 amounts to verifying the claim of line 6. By unifying variable 𝑣 𝑗 with 𝑣 𝑖 , all conjuncts of the form 𝐶(𝑣 𝑗 ) become 𝐶(𝑣 𝑖 ) and all conjuncts of the forms 𝑟(𝑣 𝑗 , 𝑣 𝑘 ), 𝑟(𝑣 𝑘 , 𝑣 𝑗 ), 𝑟(𝑣 𝑗 , 𝑣 𝑗 ) become respectively 𝑟(𝑣 𝑖 , 𝑣 𝑘 ), 𝑟(𝑣 𝑘 , 𝑣 𝑖 ), 𝑟(𝑣 𝑖 , 𝑣 𝑖 ). Line 6 checks that those conjuncts are already present in the query and therefore that unifying 𝑣 𝑗 with 𝑣 𝑖 is equivalent to deleting 𝑣 𝑗 . Unifying two variables of 𝑞 produces a query that is subsumed by 𝑞, while deleting a variable produces a query that subsumes 𝑞, therefore Algorithm 1 produces syntactically equivalent queries. For the complexity of 1 refer to the appendix. We can also use the graph representation of the canonical model to introduce the notion of the most specific query (MSQ) of an individual 𝑎. That is the query that contains as much information as possible about 𝑎, it is the least query in terms of subsumption that has that 𝑎 as a certain answer and it can be constructed by converting the connected component of the graph of 𝒞 𝒯 ,𝒜 that contains 𝑎 into a query graph with the node of 𝑎 𝒞 𝒯 ,𝒜 becoming the answer variable. Every query that has 𝑎 as a certain answer must be homomorphic to that connected component and therefore to the MSQ as well.

For generating explanations of black-box classifiers, we propose Algorithm 2, which generates candidate approximate explanations for sets of individuals, by utilizing a heuristic for disjointness which is discussed later in this section. For generating explanations, Algorithm 2 first populates a list with the MSQ of each individual. Then it removes the two least disjoint (according to the heuristic) queries and replaces them with their LCS (computed as the Kronecker product) only if it has fewer variables than a pre-set threshold, after it is minimized with Algorithm 1. The LCS of the two least disjoint queries is also added to the set of candidate explanations to be returned. This process is repeated until there are fewer than two queries left to check for disjointness.

For heuristically approximating disjointness between two queries we use Algorithm

Explanation Dataset

The connecting component between our work and machine learning classifiers which drives this explanation framework is the explanation dataset. It is essentially a semantically enriched dataset compatible with the classifier under investigation. It consists of data that can be fed to the classifier (e.g. images for image classifiers) along with semantic descriptions of this data expressed with description logics. The additional information of this enriched dataset allows us to produce explanations for the classifiers exploiting the algorithms mentioned in Section 5.1.

There isn't a standard procedure for the semantic enrichment of data, so we need to find a way to create these explanation datasets. Thankfully, enriched datasets already exist within the premises of machine learning like the Visual Genome [31] or the CLEVR [32] datasets, which contain images along with metadata for each image, such as annotations or sets of questionsanswers. It is usually easy to express these metadata in a description logic, in most cases mapping them to individuals, concepts, roles and axioms. Such an example is the creation of an explanation dataset from the CLEVR-Hans3 dataset [6] shown in 6.1.

Experiments and Discussion

Explanation Dataset Creation

CLEVR-Hans3 [6] is a confounded image classification dataset, designed to evaluate algorithms that detect and fix biases of classifiers. It consists of CLEVR [32] images divided into three Algorithm 3: DISJ Input: A pair of queries 𝑞 1 = (𝑉 1 , 𝐸 1 , 𝐿 1 ), 𝑞 2 = (𝑉 2 , 𝐸 2 , 𝐿 2 ) for which to calculate a very rough estimate of how disjoint they are. Output: The estimate of the disjointness. 1 disj ← 0 2 For every variable in 𝑞 1 find how much it differs in terms of labels and number of edges from its closest match in 𝑞 2 :

3 foreach 𝑣 1 ∈ 𝑉 1 do 4 min_diff ← +∞ 5 foreach 𝑣 2 ∈ 𝑉 2 do 6 diff ← |𝐿 1 (𝑣 1 ) ∖ 𝐿 2 (𝑣 2 )| 7 for 𝑟 ∈ RN do 8 diff ← diff + max {|{(𝑣 1 , 𝑟, 𝑢 1 ) ∈ 𝐸 1 , 𝑢 1 ∈ 𝑉 1 }| − |{(𝑣 2 , 𝑟, 𝑢 2 ) ∈ 𝐸 2 , 𝑢 2 ∈ 𝑉 2 }|, 0} 9 diff ← diff + max {|{(𝑢 1 , 𝑟, 𝑣 1 ) ∈ 𝐸 1 , 𝑢 1 ∈ 𝑉 1 }| − |{(𝑢 2 , 𝑟, 𝑣 2 ) ∈ 𝐸 2 , 𝑢 2 ∈ 𝑉 2 }|, 0} end min_diff ← min(min_diff, diff) end disj ← disj + min_diff end

Repeat the above but with 𝑞 1 and 𝑞 2 reversed. return disj classes, of which two are confounded. The membership of a class is based on combinations of objects' attributes and relations. 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.

We created our explanation dataset using the test set of CLEVR-Hans3, consisting of 750 images for each class. Exploiting the description of the images provided in json files, we constructed a vocabulary ⟨CN, RN, IN⟩, with all the images and the objects therein as individuals (IN), the concepts defining the size, color, shape, and material of each object, as well as two indicative concepts Image and Object as concept names (CN), and the role "contains(Image, Object)" indicating the existence of an object in a specific image as the only role name (RN). We then created a knowledge base 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 CN, RN and the Tbox of our knowledge base and the respective vocabulary are the following: CN = {Image, Object, Cube, Cylinder, Sphere, Metal, Rubber, Blue,Brown, Cyan, Gray, Green, Purple, Red, Yellow, Large, Small}, RN = {contains(Image, Object)}, 𝒯 = {x ⊑ Object} (where 𝑥 ̸ ∈ {Image, Object}).

Setting

For CLEVR-Hans3 we used the same classifier and training procedure as the one used by the creators of the dataset in [33]. The classifier is a deep CNN, specifically ResNet34 [34]. The performance of the classifier is shown in Table 1. After training the classifier we acquired its predictions on the test set and generated explanations for each class with Algorithm 2. We also loaded the explanation dataset in GraphDB1 for getting certain answers of queries, and evaluating explanations.

Results

The explanations generated for the classifier on the test set of CLEVR-Hans3 are shown in Table 2, where we show the query, the value of each metric and the numbers of positive and negative individuals. The term positive individuals refers to the certain answers of the query that are classified to the respective class, while the term negative individuals refers to the rest of the certain answers. In our representation of the queries in Table 2 we have omitted the answer variable x, along with all conjuncts of the form x contains y and conjuncts of the form Object(y), for brevity. The algorithm found an under-explanation (precision=1) and an over-explanation (recall=1) for each class, with the best explanation degree achieved for class 3, which lacks a confounding factor. Over-explanations and under-explanations are of particular interest since they can be translated into global rules which the classifier follows on the particular dataset. For instance the under-explanation 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.", while the over-explanation for the same class is translated into the rule "If the image does not contain a Large Cube then it is not classified to class 1". We can see that over-explanations tend to be more general, in order to include all the predictions of the classifier, while on the other side, under-explanations tend to be much more specific. That's why we find approximate explanations to be very useful for the general description of a classifier. Both over-and under-explanations tend to have low degree, while in general explanations with high degree provide us with a more accurate approximation of what the classifier has learned. So it is also useful to consider approximate explanations of high degree, even though they cannot be translated to rules like overand under-explanations.

It is interesting to note that the over-explanation produced for class 1 contains a Large Cube but not a Large Cylinder. This gives us the information 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 under-explanation that differ from the true rule 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 under-explanation by removing either of them from the query and examining its new performance. In Table 3 we can see that the gray color was essential for the under-explanation while the Large Metal Object was not, and in fact its removal improved the under-explanation and returned almost the entire class.

Another result that piqued our attention is the approximate explanation for class 3 which is the actual rule that describes this class. This explanation returns two negative individuals 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 shows us once again the large effect the confounding factor of class 1 had on the classifier.

Our overall results show that the classifier tends to emphasize low level information such as color and shape and ignores high level information such as texture and the combined presence of multiple objects. This is the reason why the confounding factor of class 1 had an important effect to the way images are classified, while the confounding factor of class 2 seems to have had

Conclusion

We introduced a theoretical framework for representing global explanations for ML classifiers in the form of conjunctive queries. We also developed algorithms for computing explanations for limited knowledge bases, and investigated some of their quality-related properties. Using CLEVR-Hans3, we were able to generate multiple explanations for a deep learning classifier.

In several cases, we found the explanations to be useful for detecting potential biases, and providing a more intuitive approach for evaluating classifiers besides performance metrics which are typically used.

One of the conclusions we can draw from our experiments is the importance of developing methods evaluating explanations, which we plan to explore in future work. The three metrics used in this paper are simple and intuitive, however none take under consideration the humanreadability factor which is crucial for explainability.

Finally, the quality and usefulness of explanations generated with the proposed methodology depends on the characteristics of the explanation dataset. Thus, in future work we also plan to investigate what constitutes a "good" explanation dataset, in addition to experimenting on more specialized domains in which explainability is critical, such as in medical applications.