A Formal Foundation for Knowledge Integration of Defficent Information in the Semantic Web

A Formal Foundation for Knowledge Integration of Defficent Information in the Semantic Web 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. Maintenance of logical robustness in Information Integration represents a major challenge in the envisioned Semantic Web. In this framework, it is previsible unprecise information (with respect to an ontology) is retrieved from some resources. The sound integration of such information is crucial to achieve logical soundness. We present a datadriven approach to classify that knowledge by means of the cognitive entropy of the possible robust ontology extensions and data. 1 Introduction Knowledge Integration is a major issue in both Knowledge and Data Engineering (KDE) and Artificial Intelligence fields. Therefore, it has to be solved in one of the current projects where both fields come together, the Semantic Web (SW). In this framework, there are many situations where defficent information obstructs the use of trustworthy reasoning systems [1]. Even, it can suggest the revision of the intensional component of the Knowledge Database, namely the ontology. In Ontological Engineering, an accurate classification of the objects is a main goal. It considers that the individuals involved in such data will remain well classified when they fall in the most specific classes of the concept taxonomy. A solution for that classification may be to introduce provisional concepts or notions for classifying individuals. Since the insertion of a notion of this kind is mainly data-driven, the notion is initially located in lower levels of the taxonomy of concepts. This is like that because very little is known about its definition, as well as how to subclassify their elements. In any way, we need to build a robust extension of the ontology to trustworthy work with the new concepts. The subject of this paper is to present a method to insert concepts which have been induced by defficent information, into an ontology. Since data that suggests the revision is unprecise (up to certain degree), the user is not interested in to obtain a definition of the new concept. That is, one only aims to provisionally classify facts waiting for more precise information. This data-driven approach is investigated here. The method proposed for ontological insertion lies in extending Supported by project TIN2004-03884 of Spanish Ministry of Education and Science, cofinanced by FEDER founds. the ontology to provisionally classify the individuals. The extension preserves main features of ontology source, and it can be considered as a robust extension (lattice categoricity [2], [3]). The main benefit of the method lies in the fact of it is fully formalized and it is semi-automated, assisted by automated reasoning systems. There is other use case requiring this kind of ontological insertion. When the ontology engineer identifies a set of specific data (that is, facts on most specific concepts of the ontology) with the extension of a new concept, since he/she has not a formal definition of the concept, the place of the ontology in which it has to be inserted is not specified. This fact typically occurs in settings where ontology engineer detects language poorness in the ontology. This point of view gives rise to user-driven approaches that we have formalized in [2]. The remainder of the paper is organized as follows. In the next section we present a simple example to illustrate the problem. In section 3 the formalization of robust ontology extension is outlined. A kind of extension is the extension by insertion of an undefinition (sect. 4). The method is applied to solve the problem of the example. Finally, some final remarks about the approach are given in section 5. 2 A Motivating Example In order to understand the problem as well as its solution, let us suppose that a Geographical Information System (GIS) launches agents for finding, in the SW, information about several geographical objects in United States. Suppose that the data set Δfound by the agents is: Overlap(West, Mount Elbert) PartOf(Mount Elbert,Colorado) ProperPartOf(Miami, F lorida) ProperPartInverse(F lorida, Miami) PartialOverlaps(Basin of Missouri River, W est) Overlaps(Basin of Platte River, Nebraska) TangentialProperPart(Mount Elbert, GreatPlains) Discrete(Colorado, Basin of Missouri River) PartOf(Colorado, West) ProperPart(East, Colorado) PartOf(Miami, F lorida) Overlaps(East, Miami) Overlaps(West, Colorado) Discrete(West, Georgia) Part(East, Georgia) Note that several facts do not provide the most specific spatial relation that it might be expressed by the ontology. That is the case of the fact Overlaps(Basin of P latte River, Nebraska). Both regions are overlapping, however there is no information about what level of overlapping relates these regions. Since the GIS deals with concepts representing underspecify spatial relations such as Overlaps, or PartOf, ..., it is hard to classify individual regions in an accurate way. They would be classified to work within a set of specific spatial-relations/concepts, a jointly exhaustive set of pairwise disjoint (JEPD) concepts to get the exhaustive intended classification. The problem can be stated as: Given a set Δof facts with respect to an ontology O, where the most specific information on some individuals can not entailed, to design an provisional robust extension of O to provisionally classify these concepts. The ontology for the running example is Region Connection Calculus (RCC), designed for (mereotopological) Qualitative Spatial Reasoning (QSR)[7]. The relations of RCC are used in both GIS and spatial databases [9]. More information on RCC can be found in [7]. The jointly exhaustive and pairwise disjoint (JEPD) set of binary relations depicted in figure 1 (right-bottom) is denoted by RCC8. The complexity of RCC8 to solve Constraints Satisfaction Problems (CSP) has been deeply studied by J.R. Renz and B. Nebel [11]. Other calculus to take into account is RCC5. It is basedontheset{DR,PO,PP,PPi,EQ}. It is less precise but more manageable than RCC8. Therefore, RCC8 represents the most specific spatial relationships in RCC. The remaining relations of RCC can be regarded as unprecise.The special interest of authors in this ontology lies in its role as meta-ontology for visual cleaning [4]. 3 Extending Ontologies with Backward Compatibility The study of ontology revision covers a very broad spectrum of theories and techniques. It encompasses logical and engineering methods, including theories from the fields of KDE and Knowledge Representation and Reasoning. A typical case of the need of ontology revision occurs when ontology engineer detects that new data are not accurately specified/classified with respect to the current information. A first solution may be to insert some provisional concept(s) (notion(s)) classifying that unprecise information and to expect that new conditions will allow us to refine information for obtaining a right classification. Actually, it involves an extension of ontology. For instance the existence of ground literals (instances) of an abstract concept (i.e. they are non-direct instances) can be a methodological problem in ontology design. Thus, it is better to consider a new concept that provisionally represents a notion. As we have already commented, such a concept will not have subclasses; thus, it will be located at the ground level of the taxonomy of concepts. It is necessary to point out that ontology evolution must obey basic accepted principles such as backward compatibility, while it is possible. In [3] a weak form of backward compatibility, useful for the aim of this paper, is introduced. In fact, it has been used for other kind of extensions in [2]. Considering an ontology as a pair (T,E) where T is the axioms set and Eis a equational characterization of the intended lattice of concepts, (the skeleton), we say that an ontology is lattice categorical (l.c.) if the lattice determined by T, and denoted by L(T,C), is unique. Cdenotes the set of concepts of T.Thetheory RCC is an example of l.c. theory. The only possible lattice structure exhibited by the models of RCC is that of figure 1, and a skeleton Eis computed in [3]. In [3] and [2] we replaced completeness by lattice categoricity to facilitate the design of feasible methods for extending ontologies with logical soundness. The extension is defined as follows. Given (T1,E 1),(T2,E 2), two ontologies of this 12345678 910 1211 13 14 15 16 PP PO TPP EQ EC DCTPPi NTPPi PPi PiP O CDR NTPP 0 aba b a b a b a bb a ab a b Fig. 1. The skeleton E(left) for the lattice of RCC (right) kind with respect to the sets of concepts C1and C2respectively, we say that (T2,E 2)isalattice categorical extension of (T1,E 1)ifL(T1,C1)⊆L(T2,C2) and L(T2,C2)|=E1. 3.1 Cognitive Support Once the notion of lattice categorical extension has been introduced, some functions for selecting the best l.c. extension have to be designed. Suppose that Δ={h1,...h n}is a set of facts on concepts in C. The user aims to classify some of individuals appearing in Δby means of specific concepts. We can suppose, to simplify the notation, that every fact explicit in Tbelongs to Δ. The cognitive support of Cwith respect to Δ,Tand L,is supL T,Δ(C):=|{a∈U(Δ):∃i[Ci≤C∧T∪Δ|=Ci(a)]}| |U(Δ)| where U(Δ):={a:existsC∈C[C(a)∈Δ]}is the universe determined by Δ. That is, the cognitive support estimates the number of facts on the concept Cthat Tentails (normalized by the size of U(Δ)). The computation is trivial for lattice categorical theories, [2]: supL T,Δ(C)= |C|Δ T |U(Δ)|where |C|Δ:= |{a: C(a)∈Δ}| and |C|Δ T:= |{a∈U(Δ):T∪Δ|=C(a)}|. Suppose now that Δis compounded by facts on atoms of the lattice of concepts (that is, about the most specific concepts). In this case, since J={C1,...,C n} is a JEPD, supT,Δ(.) is a probability measure. In general, if Jis a JEPD set of concepts in L,andΔis compounded by instances on concepts falling in the cone of some element of J,thensupT,Δ(.) is a probability measure on J. Finally, the cognitive entropy of Jis CH(J)=− C∈J supT,Δ(C)logsupT,Δ(C) This entropy is the key parameter used in the user-driven approach [2]. 4 Data-Driven Ontology Revision for Defficent Data A defficent classification of data induces the insertion of subconcepts for refining the classification of individuals which initially were misclassified. As it is already commented, the new concepts will fall in the bottom level. Therefore, we aim to extend JL, the JEPD set of concepts which are the atoms of the lattice L(T,C). The following definition formalizes the notion of insertion of a concept with certain degree of unprecision as subconcept of a given concept C.Ithastobe determined whether there is a l.c. extension of the ontology with an (atomic) subconcept μC of C.Intuitively,themeaningofμC(a) is “the concept afalls in the concept C, but we do not know more specific information about a”. Formally, Definition 1. Let (T,E0)be an ontology and C∈C. We say that the ontology admits an undefinition at C(TwC) if there is a l.c. extension of T,(T,E), such that 1. Tis l.c. with respect to C∪{μC},(whereμC /∈C). 2. {μC}is an atom in the lattice L=L(T,C∪{μC}). 3. There is not Csuch that μC <LC<LC. Note that, in above conditions, JL[μC]:=JL∪{μC}is a JEPD set for L(see fig. 2, left). This requirement represents, in fact, that we have not any additional information about μC. For example, in figure 2 right, the relation μC(a, b)means “the regions aand bare connected, but it is unknown if they overlap or they are externally connected”. The notation T|=μC(a)meansT|=C(a) and, for all D< LC,T|=D(a). In other words, C(a) is the most specific knowledge on aentailed by T.Itiseasy to see that Proposition 1. Whatever two extensions of Tby undefinition at Chave equivalent lattice skeletons modulo completion. Such a skeleton of the extension is denoted by E[μC]. We also consider the iteration of this kind of extensions, namely E[μC1,...,μC k]. Corollary 1. E[{μC :C∈C ∧ TwC}]is unique (modulo database completion axioms). For the example, this kind of extensions for RCC have to be investigate. JEPD μ (empty concept) D D 12345 8 910 1211 13 14 15 16 0 PP PO TPP EQ DCTPPi PPi PiP O CDR NTPP 6 NTPPi EC 7 μC Fig. 2. The ontology admits an undefinition in the concept C(connection)(right) 4.1 Inserting Provisional Spatial Relationships in RCC As we have already commented, the JEPD set named RCC8 is the representation of a precise classification for RCC. Theorem 1. There are exactly eight extensions by undefinition of the lattice of RCC by insertion of a new relation Dsuch that RCC8∪{D}is a JEPD set. Such new relations can be mereotopologically interpreted [6]. The lattices of the extensions are detailed at [3]. For example, the lattice depicted in fig. 1 (right) has a skeleton E[μC]. The next step consists in deciding which is the best l.c. extension to classify data. Suppose that Δ={h1,...h n}is the set of facts. Assume that the user believes that the set of misclassified elements is I={a1,...,ak}⊆U(Δ) (according with user’s ontology). In this case, the problem is not due to a new concept, because he/she has not decided yet an insertion. Such elements are not falling on atomic concepts (T|=C(a) for any C∈J L), because the user has not an specific definition of them, that is, he has got only unprecise information (as instances of upper concepts). It is easy to provide an extension by undefinition with complete classification of data. For each ai∈I,letCi∈Csuch that T|=μCi(ai). Any extension by undefinition at the set {Ci:i=1,...k}classifies every element of U(Δ)with a concept of the JEPD set JT:= J∪{μC1,...,μCk}. Note also, that if we do not require Ciis the most specific one, the extension is not unique. Definition 2. Let Tbe an extension by undefinition of Tas defined in 1. The support of μC is defined as suppT,Δ(μC)=|{a∈U(Δ):a∈I∧T∪Δ|=μC(a)}| |U(Δ)| That is, the support of μC uses the number of elements for such that Tproves they belong to C.InthiswaysuppT,Δ is also a probability measure on JT. EQ NTPPiOμμPPi EC DC μDRTPPNTPPPPμPμPO TPPi PP PPi PPi O DR C (East,Miami) (West,Colorado) (West,Mount−Elbert) (Platte−River,Nebraska) (Missouri−RIver,West) (Miami,Florida) (East,Colorado) (Mount−Elbert,Colorado) (Georgia, East) (Colorado,West) (Mount−Elbert,Great_Plains ) (Florida,Miami) (West,Georgia) (Colorado,Missouri−River) Fig. 3. Classification of data according to E[μP P, μP, μP P i, μO, μDR] Note that this computation is equivalent to consider the support with respect to the theory T+{μC(a):T∪Δ|=μC(a)}. To simplify the notation, we finally consider throughout that Tis that theory. Theorem 2. The extension above defined exhibits the maximum cognitive entropy among every possible extension by undefinition classifying U(Δ). Sketch of proof: If T is other extension, then some aiof Iare classified with respect to a concept which is not the most specific one w.r.t. T.Thus,theresult follows by the convexity of the function plogp. A l.c. extension by undefinition with maximum entropy gives little information on new concepts. This option is a cautious solution to the problem, because strong requirements for the new concepts are not been imposed. The extension of RCC for the running example will be a combination of some of the eight extensions. We are interested to find an extension by undefinition of RCC that classifies the data and exhibits higher entropy. According to data and th. 2, the selected extension has skeleton (fig. 3): E[μPP, μP, μP Pi, μO, μDR]. This l.c. extension has maximum entropy (by above theorem), 1.566. For example, E[μP,μPPi,μO,μDR], shows entropy 1.326. 5 Closing Remarks and Related Work A formalization of integration of unprecise data with respect to an ontology has been investigated, as well as a method to insert new concepts in an ontology with backward compatibility and preserving a weak form of completeness. Note that reasoning services -that we need in order to build the extension with maximum entropycan be non-decidable for first order theories. However, it is feasible for ontologies expressed in several (decidable) Description Logics, or considering the skeleton (a DL theory) as basis theory. In [2] we formalize the insertion of a concept (possibly in a upper level) that will remain well defined once the appropriate extension is selected. In that case, the computation of the (conditional) entropies is easier than the entropies defined on this paper. The approach of this paper is different because it is not necessary user decision on new concepts. Possibly, both procedures should be combined in several situations like document enrichment tasks [10]. Entropy is usually considered for associating data and concepts of an ontology (see e.g. [5] ). J. Calmet and A. Daemi also use entropy for revising or comparing ontologies [8], based on the concept taxonomy. However it is unusual to consider the provability as a parameter. Finally, note that, although the method is fully formalized, the cognitive soundness of the extensions will depend of the human decision. Moreover, the iteration of the method can produce the existence of many provisional concepts without intentional component. It may be unadvisable in some cases. References 1. Alonso-Jim´enez, J.A., Borrego-D´aaz, J., Ch´avez-Gonz´alez, A.M., Mart´nn-Mateos, F.J.: Foundational Challenges in Automated Data and Ontology Cleaning in the Semantic Web. IEEE Intelligent Systems 21(1), 42–52 (2006) 2. Borrego-D´ıaz, J., Ch´avez-Gonz´alez, A.M.: Controlling Ontology Extension by Uncertain Concepts Through Cognitive Entropy. Uncertain Reasoning for the Semantic Web, URSW 2005, CEUR 173, 56–66 (2005) 3. Borrego-D´ıaz, J., Ch´avez-Gonz´alez, A.M.: Extension of Ontologies Assisted by Automated Reasoning Systems. In: Moreno D´ıaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2005. LNCS, vol. 3643, pp. 253–257. Springer, Heidelberg (2005) 4. Borrego-D´ıaz, J., Ch´avez-Gonz´alez, A.M.: Visual Ontology Cleaning: Cognitive Principles and Applicability. In: Sure, Y., Domingue, J. (eds.) ESWC 2006. LNCS, vol. 4011, pp. 317–331. Springer, Heidelberg (2006) 5. Brewster, C., Alani, H., Dasmahapatra, S., Wilks, Y.: Data Driven Ontology Evaluation, Int. Conf. Lang. Resources and Evaluation (2004), http://eprints. ecs.soton.ac.uk/archive/00009062/01/BrewsterLREC-final.pdf 6. Ch´avez-Gonz´alez, A.: Mereotopological Automated Reasoning for Ontology Cleaning, Ph.D. Thesis, University of Seville (2005) 7. Cohn, A.G., Bennett, B., Gooday, J.M., Gotts, N.M.: Representing and Reasoning with Qualitative Spatial Relations about Regions. In: Stock, O. (ed.) Spatial and Temporal Reasoning, ch. 4, Kluwer, Dordrecth (1997) 8. Daemi, A., Calmet, J.: From Ontologies to Trust through Entropy. In: Proc. of the Int. Conf. on Advances in Intelligent Systems - Theory and Applications (2004) 9. Grohe, M., Segoufin, L.: On First-Order Topological Queries. ACM Trans. Comput. Log. 3(3), 336–358 (2002) 10. Motta, E., Buckingham, S., Domingue, J.: Ontology-driven document enrichment: principles, tools and applications. Int. J. Human-Computer Studies 52(6), 1071– 1109 (2000) 11. Renz, J.R., Nebel, B.: On the Complexity of Qualitative Spatial Reasoning: A Maximal Tractable Fragment of the Region Connection Calculus. Artificial Intelligence 108, 69–128 (1999)