Visual Ontology Cleaning: Cognitive Principles and Applicability

Visual Ontology Cleaning: Cognitive Principles and Applicability Joaqu´ın Borrego-D´ıaz and Antonia M. Ch´avez-Gonz´alez Departamento de Ciencias de la Computaci´on e Inteligencia Artificial. E.T.S. Ingenier´ıa Inform´atica-Universidad de Sevilla. Avda. Reina Mercedes s.n. 41012-Sevilla, Spain {jborrego, tchavez}@us.es Abstract. In this paper we connect two research areas, the Qualitative Spatial Reasoning and visual reasoning on ontologies. We discuss the logical limitations of the mereotopological approach to the visual ontology cleaning, from the point of view of its formal support. The analysis is based on three different spatial interpretations wich are based in turn on three different spatial interpretations of the concepts of an ontology. 1 Introduction It is commonly accepted that for achieving a satisfactory sharing of knowledge in the envisioned Semantic Web (SW), it will be necessary to build ontologies. They play a key role in the reasoning services for Knowledge Bases (KB) in the SW [17]. Practical management of ontologies, such as extension, refinement and versioning technologies will be essential tasks. From the point of view of the Knowledge Representation (KR) paradigm, ontology revision comes from the fact that the discourse domain may not be faithfully represented by an ontology (a well known working principle in KR). In many cases, end-users need to interact and transform the ontology. Even if the ontology designer thinks that the ontology is final, the end-user may think the opposite, or simply that the ontology is incorrect. In fact, it should be feasible to achieve the agreement designer-user. This agreement is essential for the assimilation of SW technologies into non-academic community portals, for example. Unfortunately, several reasons obstruct the agreement. The first one is that end users do not know the logical formalisms behind ontology web languages. Therefore, the user can not know hidden principles on which ontologies are built. It does not help to increase the understanding of technologies involved in SW tools. Anyway, this fact might not be important if he uses amenable technologies for representing/repairing the anomalies founded in its own ontology project. Visual encodings are very interesting for such pourposes. End-user preferences on visual representation are well known in other related fields such as Formal Concept Analysis or Data Engineering. The spatial Supported by project TIN2004-03884 of Spanish Ministry of Education and Science, cofinanced by FEDER founds. metaphor is a powerful tool in human information processing. The user will feel encouraged to repair the anomaly, although there exist some obstacles: on the one hand, visual reparation may not be corresponded by a logical reparation of the ontology source. This occurs if there is no a formal semantics for supporting the change; on the other hand, repairs can be logically complex. Domain experts often underestimate the amount of time required to produce an ontology, and consequently they build an ontology based on a large scope. The resulting conceptual ontologies are consequently a mix of both domain and task ontology concepts which are hard to manage [22]. Paraphrasing [23], visual cleaning of ontologies is important for future endusers of ontology debugging systems due mainly to three reasons: 1. It allows the user to summarize ontology contents. 2. User’s information is often fuzzily defined. Visualization can be used to help theusertogetanicerepresentation. 3. Finally, visualization can therefore help the user to interact with the information space. There is not a generally accepted representation mechanism that translates every possible changes in the visual representation into the specification of the ontology. In fact, this is an interesting problem in the design of visual reasoning tools. Current end-user tools are mostly based on facilitating the understanding of the ontology (see e.g. [14], [21]) facilitating very limited graphical changes to the user. In order to augment such features, we need formally sound mappings between (visual) representations and Knowledge Bases (KBs) (expressed, for example, in Description Logics). Note that such mappings have to translate logical notions for supporting the logical impact of arrangements on the spatial representation (for example, when new concepts are inserted). These issues are critical and we need to solve them in order to integrate solutions in systems for visual representation of information [14]. This goal is far away of being achieved for classical Information Visualization (IV) tools. IV is the use of computer-supported, interactive and visual representations of abstract data to amplify cognition [9]. The goal of Visual Ontology Cleaning (VOC) should be to reason spatially for visually debugging and repairing of ontologies . Therefore, it should have aditional features, different from classical user analysis, querying and navigation/browsing. A second limitation concerns to the scalability of debugging problem. It is hard to manage visual representations of large ontologies, although a broad spectrum of tools has been designed [14]. It is sometimes sufficent to locate which small portion of the ontology supports the anomaly. This task can be facilitated by Automated Reasoning Systems (ARS). ARS are useful both for debugging ontologies [1] [2][27] (although several foundational problems exist [4]), and for the computer-assisted evolution of robust ontologies [6] [7]. If an ARS find a proof of an anomalous result, it can recover an argument from the proof. An argument is a pair formed by a consistent portion of the KB and the entailed result (an ontological argument). In this case, it seems natural to consider the repairing of the self argument to cut such inference [3]. The argument is often a very small portion of the ontology, and therefore it is easily represented. Despite its modest size, it provides more useful information about the anomaly than the full ontology. Furthermore, the reparation is model-based. That is, the user keep in mind the intended model that ontology represents, and this model induces the changes. Therefore, argument repairing is a relatively easy task. Thus, for the pourposes of this paper, we might consider the ontological argument as the anomalous ontology. In this paper we investigate some KR issues behind the sound mereotopological representation of the conceptualization induced by small ontologies (namely the mentioned ontological arguments) [3]. The intended aim of such representation is the understanding and repairing of ontologies. Specifically, those considered as anomalous (although consistent) due to errors in the concept structure. In this paper the spatial representation and algorithmic repairing are described; we do not describe here the (future) implementation. The advantage of this approach is that visual reparation stage hides formal semantics that supports the change, facilitating in this way its use by non experts. The structure of the paper is as follows. The next section introduces a wellknown mereotopological approach to qualitative spatial reasoning. Section 4 is devoted to study whether the Mereotopological reasoning can be interpreted as an abstract metaontology. It is proved, using logical types (sect. 3) that such interpretation does not support the work with instances inaccurately classified. In sections 5,6 we suggest new approachs based on the representation of frontiers and vague regions, respectively. The paper concludes with some closing remarks about the presented framework. 2 Mereotopology and First Cognitive Principle The thesis that supports this paper is the following principle Main Cognitive Principle (MCP): If we aim to use spatial reasoning for cleaning ontologies, we have to provide a theory on spatial entities for translating the impact of spatial arrangements into revisions of the ontology source. In order to satisfy the MCP, a theory on Qualitative Spatial Reasoning (QSR) has to be selected. In this way, the following sub-principle is choosen: First Cognitive Principle (CP1): The concepts of a conceptualization associate to a clear ontology can be topologically represented by means of regular non-empty regions. That is, there is a model of the ontology whose universe is the bidimensional or tridimensional space, and that model interprets concept symbols as regions. It is evident that the represented knowledge will depend of topological relations. The starting-up of CP1 needs of a robust theory to reason with spatial regions. DC(x, y)↔¬C(x, y)(xis disconnected from y) P(x, y)↔∀z[C(z,x)→C(z,y)] (xis part of y) PP(x, y)↔P(x, y)∧¬P(y, x)(xis proper part of y) EQ(x, y)↔P(x, y)∧P(y, x)(xis identical with y) O(x, y)↔∃z[P(z,x)∧P(z,y)] (xoverlaps y) DR(x, y)↔¬O(x, y)(xis discrete from y) PO(x, y)↔O(x, y)∧¬P(x, y)∧¬P(y, x)(xpartially overlaps y) EC(x, y)↔C(x, y)∧¬O(x, y)(xis externally connected to y) TPP(x, y)↔PP(x, y)∧∃z[EC(z, x)∧EC(z,y)] (xis a tangential prop. part of y) NTPP(x, y)↔PP(x, y)∧¬∃z[EC(z,x)∧EC(z,y)] (xis a non-tang. prop. part of y) Fig. 1. Axioms of RCC ababab a bb a PO(a,b) TPPi(a,b) EC(a,b) TPP(a,b) NTPP(a,b) NTPPi(a,b)DC(a,b) EQ(a,b) a b ab ab Fig. 2. The relations of RCC8 Aditionally, the theory must facilitate the knowledge interchange between the ontology and spatial models. The selected theory is the well known Region Connection Calculus (RCC) [13]. RCC is a mereotopological approach to QSR; it describes topological features of spatial relationships. It has been used in several subfields of AI, for example, in GIS and spatial databases [24] [16]. In RCC, the spatial entities are non-empty regular sets. The ground relation is the connection,C(x, y), with intended meaning: “the topological closures of x and yintersect”. The basic axioms of RCC are ∀x[C(x, x)] ∀x, y[C(x, y)→C(y,x)] and a set of definitions on the main spatial relations (fig. 1), jointly with another set of auxiliary axioms (see [13]). The set of binary relations formed by the eight jointly exhaustive and pairwise disjoint (JEPD) relations given in figure 2 is denoted by RCC8. If this set is thought as a calculus for Constraint Satisfaction Problems (CSP), every set of basic relations is considered. This calculus has been deeply studied by J. Renz and B. Nebel in [26]. Other interesting calculus is RCC5, based on the set {DR,PO,PP,PPi,EQ}. Roughly speaking, the main difference between RCC5 and RCC8 is that the latter one allows one to represent knowledge that depends on topological frontiers, while the former one does not allow. The cognitive impact of this distinction on the spatial representation of a concept has to be discussed (as we will do, in fact). Nevertheless, it has been empirically constated that RCC8 is more adequate than RCC5 as a tool for representing topological relations discriminated by humans [19]. 3 Background: 1-Types in Ontologies For analyzing the first spatial interpretation showed in thi paper types are required. The use of types is a classic tool in Model Theory (see e.g. [11]). We succintly describe here their main features. Given a consistent ontology Σ,a 1-type is a (maximal) set of formulas {ϕk(x)}kfinitely satisfiable. That is, such that for any F⊆N(Ffinite), the theory Σ+{∃x k∈F ϕk(x)} is consistent. The ontology Σrealizes the type if that theory is consistent when F=N.Equivalently,Σrealizes the type if the theory Σ+{ϕk(a):k∈N}is consistent, being aa new constant symbol. For a correct definition of types it has to consider First Order Logic (FOL) formulas. Types contain formulas that can not be translated into DL. Nevertheless, general FOL formulas are not needed in the proof of Theorem 1 below. Only the constructors negation and intersection are needed. The set S(Σ)={p:pis a type of Σ}is the space of types for Σ.Fora concept C,letSΣ(C):={p∈S(Σ):C∈p}be the set of types containing C.It will be denoted by [C]ifΣhas been previously fixed. It is easy to see that [C]∩[D]=[C∧D]and[¬C]=S(Σ)[C] Given a model I|=Σand aan element of its universe, the type of ain I is [a]=tpI(a)={ϕ(x):I|=ϕ(a)}.FixedI, it will be denoted [a]. 4 RCC as a Meta-ontology (I): Strong Interpretation The use of RCC to visually represent the concepts turns RCC8 into an ontology on conceptual relations. The idea can be translated in different ways. The straightforward approach consists in interpreting the concepts as regions in some model of the theory. Thus, in the strong interpretation, the intended meaning of C(x,y)is:there exist a common element in the concepts x,yin some model Iof the ontology. Definition 1. (Strong Interpretation of RCC as a metaontology) Two concepts C1,C2of an ontology Σare Σ-connected (denoted by CΣ(C1,C2))if Σ|=C1C2≡⊥ The remaining RCC relations can be interpretated by means of its corresponding definition (depicted in fig. 1). Note that the strong interpretation works on abstract spatial encodings of Σ. That is, it does not work on a concrete spatial interpretation of concepts. The following result states a logical limitation of the strong interpretation of RCC as meta-ontology. Theorem 1. The strong interpretation does not discriminate RCC8 as ontological relations between concepts. Concretely, it has the following characterizations: 1. CΣ(C1,C2)⇐⇒ SΣ(C1)∩SΣ(C2)=∅ 2. DCΣ(C1,C2)⇐⇒ SΣ(C1)∩SΣ(C2)=∅ 3. PΣ(C1,C2)⇐⇒ SΣ(C1)⊆SΣ(C2) 4. PPΣ(C1,C2)⇐⇒ SΣ(C1)SΣ(C2) 5. EQΣ(C1,C2)⇐⇒ Σ|=C1≡C2. 6. OΣ(C1,C2)⇐⇒ CΣ(C1,C2) 7. POΣ(C1,C2)⇐⇒ SΣ(C1)∩SΣ(C2)=∅∧ SΣ(C1)⊆ SΣ(C2)∧ ∧SΣ(C2)⊆ SΣ(C1) 8. DRΣ(C1,C2)⇐⇒ DCΣ(C1,C2) 9. If C1,C2and R∈{EC,TPP,NTPP,TPPi,NTPPi},then¬RΣ(C1,C2). Proof. Let us only show three cases (the complete proof appears in [10]). (1) By definition, CΣ(C1,C2)meansΣ|=C1C2≡⊥.LetIbe a model whith C1I∩C2I=∅. By interpreting a new constant aas an element of the intersection, it certifies that Σ∪{(C1C2)(a)}is consistent. In fact, [a]∈[C1C2] therefore, [C1C2]=∅. Hence it holds SΣ(C1)∩SΣ(C2)=∅. The converse is trivial: if p∈SΣ(C1)∩SΣ(C2), any element realizing this type in a model Iis an element of C1IC2I.Thus,CΣ(C1,C1). (3) Assume proved (1) and (2). By definition of P,PΣ(C1,C2)means ∀C3(SΣ(C3)∩SΣ(C1)=∅→SΣ(C3)∩SΣ(C2)=∅)(†) We proceed to show that this condition is equivalent to SΣ(C1)⊆SΣ(C2) (thus, (3) will be proved): It suffices to show that the condition is necessary. Let us consider p∈SΣ(C1) (that is, C1∈p). Suppose, contrary to our claim, that p∈ SΣ(C2). Hence C2∈ p.Sincepis maximal, ¬C2∈p. Therefore, C1∈pand ¬C2∈p,thus p∈SΣ(C1)∩SΣ(C1¬C2) Then it follows that SΣ(C1)∩SΣ(C1¬C2)=∅.Consequently,by(†) SΣ(C2)∩SΣ(C1¬C2)=∅ From this, we obtain p∈[C1¬C2]andp∈[C2]. This is impossible because {C1¬C2,C2}can not be contained in a type (it is inconsistent). (5) Suppose proved from (1) to (4). By definition, EQΣ(C1,C2)is PΣ(C1,C2)∧PΣ(C2,C1) By (3), this is equivalent to SΣ(C1)⊆SΣ(C2)andSΣ(C2)⊆SΣ(C1). Therefore SΣ(C1)=SΣ(C2). Finally, the last condition is equivalent to Σ|=C1≡C2.Itistrivialtosee that it is sufficient. Let us see that it is necessary: Male Male Retraction Region of vague belonging Male RuPaul RuPaul R u P au l Fig. 3. Two kinds of representation of a problematic instance in the frontier (left, right) and solving by retraction the first one (middle) (right) Let I|=Σand asome realization of C1in I,I|=C1(a). Thus, [a]={φ:I|=φ(a)}∈SΣ(C1) So [a]∈SΣ(C2). Therefore, I|=∀x(C1(x)→C2(x)). In DLs, I|=C1 C2. Similarly, I|=C2C1holds. Thus, Σ|=C1≡C2. It sould be pointed out that the above interpretation might be not usable in practice. The connection between concepts is based on entailment. Therefore, it can have high algorithmic complexity when we deal with expressive description logics (the consistency of concepts and, hence, satisfiability, is EXPTIME-hard in ALC, cf. [8]). Strong connection reduces to subsumption (hence to a satisfiability problem): CΣ(C1,C2) if and only if Σ|=C1¬C2 Theorem 1 says that, thinking RCC as a metaontology, this theory can not represent frontier-sensitive knowledge. Nevertheless, sometimes it seems cognitively natural to consider the frontier of a concept as formed by elements in which the user has not confidence on its correct classification in the concept. This can occur when the user works with a notion, a rough idea of the concept that attempts to specify. The notion becomes in a concept when its behavior is constrained by new axioms that relate it with the former concepts. By allocating the problematic instances near of the frontier it will be easy to discard them by a simple topological movement (a retraction, see fig. 3). 5 RCC as Meta-ontology (II): Weak Interpretation As it has been commented, strong interpretation can be not advisable due to its computational complexity for ontological arguments of larger size. Other limitation is that our cognitive capability is reduced to RCC5. In this section a new interpretation is introduced. This is based on the following idea: if it were possible to represent RCC8-relations in visual encodings, the topological frontiers of the regions could be endowed of cognitive features. The following principle is useful for both the weak interpretation defined bellow and the vague interpretation defined in the next section (see figure 3). Second Cognitive Principle (CP2): The frontier of a spatial interpretation of a concept Crepresents the individuals with doubtful membership to C. The ontology RCC has been used as formal support for CP2 in ontology cleaning [3]. The idea is based on the translation of relations between concepts into spatial relationships among spatial representations of these concepts. It is, at the same time, based on studies about the relation between logical consistency of Constraint Satisfaction Problems in RCC and spatial consistency [25]. The main step of the cited cleaning cycle consists in a translation of logical information on conceptual relations of the ontology into a CSP on spatial relations. Solving this CSP, a spatial encoding of conceptual relations is obtained. This approach is useful to repair arguments suffering anomalies due to the conceptualization. It works with spatial interpretations. Definition 2. Aspatial interpretation Iof Σis a interpretation in the language of Σ, such that I:concepts(Σ)∪indiv(Σ)→Ω,whereΩis a T3 connected topological space such that I|=Σand for each C∈concepts(Σ),I(C) is an open regular set in Ωand for each a∈indiv(Σ),I(a)is a point. Aspatial model of Σis a spatial interpretation which is a model of Σ. The following theorem guarantees that the weak interpretation is useful for analysing knowledge bases in DL, since it preserves the consistency. Theorem 2. [10] The CSP associate to Σis spatially consistent if Σis consistent. Moreover, it is possible to obtain a spatial model on the plane formed by polygonal regions [25]. Once formalized the notion of spatial model, spatial arrangements can be formally justified and classified [10]. In figure 4 we present a simple example of visual repairing (of the ontology of Figure 7, left) following a cleaning cycle presented in [3] (see fig. 6). Note that, although one can think that the ontology source is correct, it is assumed that the end-user thinks it is anomalous (he thinks that it is an ontological argument that deficently classifies to Rupaul). The cycle is based on the following stages: 1. First, it builds a constraint satisfaction problem (CSP) on the spatial relational calculus RCC8 (or RCC5). The problem is solved obtaining a consistent scenario, represented in 2D. Facts of the Abox are added as points. 2. The user is requested to make reticular or topological arrangements on the graphical representation. Reticular arrangements represent refinements of relationships between concepts, and topological arrangements imply substitution of a relationship by another one, disjoint with the former one but cognitively near of that. The user must lastly think that she/he has a fair RCC8(5) representation. This gives a table of spatial constraints on notions of the provisional ontology. 3. A translation from RCC into DL is applied. In the resulting ontology, some relationships have changed and new concepts may have been induced. Fig. 4. Spatial representation of an anomalous argument (left) and the solution proposed (right) Man Female Rupaul Man Female NMan Female (Rupaul) Fig. 5. New Notion induced. The user has to interpret/discard it, because it transforms DRΣ(Man,Female)intoPO Σ(Man,Female) 4. Finally, the user interprets (or discards) the new objects (individuals or concepts) that the translation may induce (see Fig. 5). The result of the process is a new ontology modified according to the preferences of the user. The impact of this arrangement on the ontology is shown in fig. 7 (right). Furthermore, in complex or huge ontologies, it is convenient to use, for cleaning tasks, other relaxed spatial interpretations. Since the ontology we are representing is regarded as defective, it is possible to make a spatial characterization less detailed than the offered one by the CSP [3]. There is a natural relationship between strong and weak interpretations. Theorem 3. [10] The following conditions are equivalent: 1. CΣ(C1,C 2) 2. There is a spatial interpretation Iof Σsuch that I|=C(C1,C 2). 6 RCC as Meta-ontology (III): Vague Interpretation Strong and weak interpretation work with precise regions. In both cases, the interpretation of Cis a subset. The vague interpretation deals with the spatial interpretation of the concepts by vague regions. A vague region can be represented by means of two regular regions although there are other options such as egg-yolk [12], topological spaces with pulsation [10], rough sets, etc.