Review Comment:
###Summary of the paper###
The problem of explaining the behaviour of machine learning models has recently drawn considerable attention in AI research. This interest stems from the fact that very efficient classes of these models, such as deep learning classifiers, do not provide explanations of how/why they take decisions leading to the classification of data samples. For this reason, a great variety of approaches have been proposed to provide understandable and meaningful explanations for the behaviour of such classification models.
This paper proposes to explain the behaviour of a blackbox classifier by using semantic annotations on the sample data, whose meaning is supported by an underlying ontology formulated using a Description Logic (DL). More precisely, the authors propose the following framework to explain the behaviour of a classifier:
 Given are: A classifier F, a set of data samples annotated with semantic descriptions from a vocabulary V and a DL ontology defined over V. For each data sample of interest, the assertional component of this ontology (the ABox) identifies it with a constant, states its classification according to F and contains formulas expressing the corresponding semantic annotations.
 Goal: To produce a set of rules expressed over V that explain the behaviour of F in an understandable and meaningful way.
Given a class C, an explanation rule R_C for C produced by the framework have the form:
R_C = Body(x,x_1,...,x_n) > C(x),
where Body is a conjunction of unary and binary predicates from V with parameters in {x,x_1,...,x_n}.
The idea is that R_C expresses sufficient conditions for an item to be classified in the class C. For this rule to be correct, it must be a logical consequence of the set of axioms in the underlying ontology.
Besides the proposed framework, the other main contributions of the paper are:
 A suite of algorithms to compute (approximate) explanation rules. These algorithms are based on the fact that finding a correct rule R_C can be reduced to finding a conjunctive query Q_C whose certain answers w.r.t. the ontology are all positive instances of C.
 Experiments are conducted to evaluate the quality of the queries produced by the algorithms, in terms of how accurate they represent the behaviour of the classifier.
###General Evaluation###
The topic considered in the paper is interesting and of relevance for this journal. However, there are several aspects that (in my opinion) make this paper far from ready for publication. Basically, it is written in a very informal way and there is a lack of precision in many definitions. In addition, one of its most important claims does not seem to be justified at all, or its justification is deferred to either a Workshop paper or an additional paper that does not appear to have been peerreviewed. I have also found several inconsistencies with the experiment and their results.
I describe all my concerns below. I believe that to make this paper ready for acceptance would require more than a Major Revision. Therefore, I propose the paper to be rejected.
###Main Problems###
a) The goal of the paper or the problem it aims to solve is:
...given a set of exemplars and their semantic descriptions find *intuitive* and *understandable* semantic queries that have as certain answers exactly this set out of all the exemplars on the explanation data sets... (see for instance: page 5, line 47).
I am not convinced that this is well justified in the paper:
 Given that the underlying reverse engineering problem have already been investigated in the literature, the properties of being *intuitive* and *understandable* seem to be a distinctive and relevant aspect of the paper's contribution. However, I could not find a formal or convincing argument that supports this in the paper. All this seems to be discussed in the paper at a very informal level. In particular [53] and [46] are cited in these discussions. On the one hand, this submission appears to be the extended version of [53] which is a Workshop paper. For this reason, I believe that any discussion in this regard appearing in [53] should actually be provided here. On the other hand, it is not clear what kind of manuscript [46] is. Has it been peerreviewed? The bibliography entry gives no clue about it and what I could find in DBLP looks like a shorter version of this submission.
 The experiments are not designed to analyse this aspect of the provided solution, and there is no formalisation of what *intuitive* and *understandable* means. For example, one possibility could be to define reasonable properties, either of a syntactic or a semantic nature, that *intuitive* and *understandable* queries are required to satisfy. Once this is done, it provides a formal criteria that can be used to evaluate how good the queries produced by the provided algorithms are.
b) Experiment 1 yields 100% fidelity for the two datasets of greatest size. It seems unlikely that this can be the case, unless the Mushroom dataset is not really a good choice for benchmarking:
 Note that only 123 mutually different items are required for Merging to yield the "empty query" (or a query with only TOP(x)) in your algorithms. This means that there would be no query capturing the exact behaviour of the classifier. Notice that 123 is really small w.r.t. 1000 and 4000, which are the sizes of the biggest datasets.
 The average length of a query is around 14, which is only a bit above the half of the number of categorical features considered in the experiment. Further, an MSQ representing an item is a conjunction of concept names and it can never have two concept names representing different values of the same categorical feature. Hence, it looks like having 100% fidelity implies that half the categorical features in the Mushroom dataset are irrelevant (already for the classifier) to separate positive and negative instances.
c) The knowledge base used in Experiment #2 is extremely simple. I do not really see how this illustrate one of the main claims of the paper. Namely, that really complex ontological knowledge is take into account to provide explanations. In this experiment, this knowledge can be easily integrated into the data. No real ontologybased logical entailment is needed.
###Additional Comments###
1. The presentation of technical notions defining the syntax and semantics of Description Logics is very poor. This should be formally introduced, since the use of background logical knowledge is supposed to make the results in this paper distinctive from other existing approaches. Some aspects in this regard are:
 There is no example illustrating the syntax and semantics of a DL. In particular, nothing is said about how the interpretation of concept and role names extend to complex formulas. There is no formal definition of what a TBox and an ABox are, nor a formal definition for the satisfaction of axioms in a TBox/ABox.
 The second sentence in line 43 (page 3) is not accurate. The fact that most DL dialects are fragments of FOL has also to do with the the available set of constructors and their semantics.
2. Considered queries and some related notions.
 The notion of substitution should be properly defined.
 While it follows from the definition of QLCS that it is unique (modulo syntactical equivalent), this is the case if it actually exists. Whether it always exists or not is, however, not really shown in the paper. Note that, assuming that all queries contain TOP(x) as an atom only ensures that a common subsumer exists, but this need not be the minimal. A formal proof of this should be provided.
 The set of nodes V of an ABox graph should not be IN, but the individual names occurring in the ABox. The set IN is the set of all available constants. This does not mean that all of them must be used in every ABox. This should also be made clear in other parts of the paper.
3. In page 7, is the expression $Examplar \sqsubseteq {a  a \in EN}$ correctly expressed in some DL syntax?
4. Theorem 1 seems to be correct. However, the proof is missing and deferred to [46] (see previous comments about [46]).
5. Nothing is said about the cases where it is not possible to exactly capture the behaviour of the classifier. Can you provide examples and/or theoretical characterisations for this? This can help to understand the limitations of the framework, beyond the insights that could have been provided in the experiments. Perhaps, the existing work on the reverse query engineering problem can shed some light into this?
6. More details should be provided about why the algorithm computes a set of queries instead of just one. More precisely, what is the intention of giving a set of queries to the user? How are they meant to be used? In particular, the intermediate queries obtained in the computation.
7. The GreedyCommonConjunct (Algorithm 4) and the threshold approximation are introduced as alternatives of using just QLCS, to avoid certain problems. However, there is no comparison between all these variants in the paper. Natural questions that arise from it are:
 Is the "exact query" property lost by using GreedyCommonConjunct instead of QLCS?
 What would be the difference between queries produced by using GreedyCommonConjunct and those generated by using QLCS, in terms of the quality measures defined in the paper?
 How much using the threshold approximation affects the quality of the queries?
###Typos###
 page 2, line 48: what does KG stand for? Knowledge graph?
 page 3, line 20: [[46]]
 page 3, line 47: has a missing comma. This also occurs in other places.
 page 4, line 17: ...and a model I of K...
 page 4, line 25: I think it should be $\equiv_S$.
 page 6, line 37: ... in terms of D, C and V...
 page 6, line 41: ... are in the knowledge base...
 page 7, line 11: ...of the DL knowledge base....
 page 9, line 22: ...knowledge base...
 page 9: there is a big space at the end of the page.
 page 10, l. 12: ...From section Section...
 p.11, l.2: ...a classifier F to be explained...
 p.11, l.35: ... to be in S...
 p.14, l.30: It should be ((u1,v1),(u2,v2)) because V=V1 x V2.
 p.18, l.8: Should not theta be initialized as {x > x}?
 p.20, l.4: ...explanations using Alg. 1
 p.21, l.45: TBox.
