Introduction

In collaborative contexts, multiple independently created ontologies often need to be brought together in order to enable their interoperability. These ontologies have an impaired collaborative functionality, due to heterogeneities coming from the decentralized nature of their acquisition, differences in scopes and application purposes and mismatches in syntax and terminology.

We present an approach to building a combined knowledge body for a set of domain ontologies, which captures and exposes various relations holding between the concepts of the domain ontologies, such as their relative generality or specificity, their shared commonality or their complementarity. This can be very useful in a number of real-life scenarioss, especially in collaborative platforms. Let us imagine a project which includes several partners, each of which has its own vocabulary of semantically structured terms that describes its activity. The proposed framework would allow every party to keep its ontology and work with it, but query the combined knowledge body whenever collaboration is necessary. Examples of such queries can be: "which concept of a partner P 1 is closest to my concept A", or "give me those concepts of all of my partners which are equally distant to my concept B", or "find me a concept from partner P 2 which is a strong subsumer of my concept C", or "what are the commonality and specificity between my concept A and my partner's concept D".

We situate our approach in a fuzzy framework, where every domain concept is represented as a fuzzy set of the concepts of a particular reference ontology. This can be seen as a projection of all domain source concepts onto a common semantical space, where distances and relations between any two concepts can be expressed under fixed criteria. In contrast to the original instance-representation, we can apply methods of fuzzy logical reasoning in order to characterize the relationship between concepts from different ontologies. In addition, the fuzzy representations allow for quantifying the degree to which a certain relation holds.

The paper is structured as follows. Related work is presented in the next section. Background in the field of fuzzy sets, as well as main definitions and problems from the ontology matching domain are overviewed in Section 3. We present the concept fuzzification algorithm in Section 4, before we discuss how the combined knowledge body can be constructed in Section 5. Experimental results and conclusions are presented in Sections 6 and 7, respectively.

Related Work

Fuzzy set theory generalizes classical set theory [19] allowing to deal with imprecise and vague data. A way of handling imprecise information in ontologies is to incorporate fuzzy reasoning into them. Several papers by Sanchez, Calegari and colleagues [4], [5], [13] form an important body of work on fuzzy ontologies where each ontology concept is defined as a fuzzy set on the domain of instances and relations on the domain of instances and concepts are defined as fuzzy relations.

Work on fuzzy ontology matching can be classified in two families: (1) approaches extending crisp ontology matching to deal with fuzzy ontologies and (2) approaches addressing imprecision of the matching of (crisp or fuzzy) concepts. Based on the work on approximate concept mapping by Stuckenschmidt [16] and Akahani et al. [1], Xu et al. [18] suggested a framework for the mapping of fuzzy concepts between fuzzy ontologies. With a similar idea, Bahri et al. [2] propose a framework to define similarity relations among fuzzy ontology components. As an example of the second family of approaches, we refer to [8] where a fuzzy approach to handling matchinging uncertainty is proposed. A matching approach based on fuzzy conceptual graphs and rules is proposed in [3]. To define new intra-ontology concept similarity measures, Cross et al. [6] model a concept as a fuzzy set of its ancestor concepts and itself, using as a membership degree function the Information Content (IC) of concept with respect to its ontology.

Crisp instance-based ontology matching, relying on the idea that concept similarity is accounted for by the similarity of their instances, has been overviewed broadly in [7]. We refer particularly to the Caiman approach which relies on estimating concepts similarity by measuring class-means distances [10].

Background and Preliminaries

In this section, we introduce basics from fuzzy set theory and discuss aspects of the ontology matching problem.

Fuzzy Sets

A fuzzy set A is defined on a given domain of objects X by the function

µ A : X −→ [0, 1],(1)

which expresses the degree of membership of every element of X to A by assigning to each x ∈ X a value from the interval [0, 1] [19]. The fuzzy power set of X, denoted by F(X, [0, 1]), is the set of all membership functions µ : X −→ [0, 1]. We recall several fuzzy set operations by giving definitions in terms of Gödel semantics [15]. The intersection of two fuzzy sets A and B is given by a t-norm function T (µ A (x), µ B (x)) = min(µ A (x), µ B (x)). The union of A and B is given by S(µ A (x), µ B (x)) = max(µ A (x), µ B (x)) where S is a t-conorm. The complement of a fuzzy set A, denoted by ¬A, is defined by the membership function µ ¬A (x) = 1 − µ A (x). We consider the Gödel definition of a fuzzy implication

µ A→B (x) = 1, if µ A (x) ≤ µ B (x), µ B (x), otherwise.

(2)

Ontologies, Heterogeneity and Ontology Matching

An ontology consists of a set of semantically related concepts and provides in an explicit and formal manner knowledge about a given domain of interest [7]. We are particularly interested in ontologies, whose concepts come equipped with a set of associated instances, defined as it follows.

Definition 1 (Crisp Ontology). Let C be a set of concepts, is a ⊆ C ×C, R a set of relations on C, I a set of instances, and g : C → 2 I a function that assigns a subset of instances from I to each concept in C. We require that is a and g are compatible, i.e., that is a(A , A) ↔ g(A ) ⊆ g(A) holds for all A , A ∈ C. In particular, this entails that is a has to be a partial order. With these definitions, the quintuple O = (C, is a, R, I, g) forms a crisp ontology.

Above, a concept is modeled intensionally by its relations to other concepts, and extensionally by a set of instances assigned to it via the function g. By assumption, every instance can be represented as a real-valued vector, defined by a fixed number of variables of some kind (the same for all the instances in I).

Ontology heterogeneity occurs when two or more ontologies are created independently from one another over similar domains. Heterogeneity may be observed on linguistic or terminological, on conceptual or on extensional level [7]. Ontology matching is understood as the process of establishing relations between the elements of two or more heterogeneous ontologies. Different matching techniques have been introduced over the past years in order to resolve different types of heterogeneity [9].

Instance-based, or extensional ontology matching gathers a set of approaches around the central idea that ontology concepts can be represented as sets of related instances and the similarity measured on these sets reflects the semantic similarity between the concepts that these instances populate.

Crisp Concept SimilaritiesConsider the ontologies O 1 = (C 1 , is a 1 , R 1 , I 1 , g 1 ) and O ref = (X, is a ref , R ref , I ref , g ref ).

We rely on the straightforward idea that determining the similarity sim(A, x) of two concepts A ∈ C 1 and x ∈ X consists in comparing their instance sets g 1 (A) and g ref (x). For doing so, we need a similarity measure for instances i A and i x , where i A ∈ g 1 (A) and i x ∈ g ref (x).

We have used the scalar product and the cosine s(i

A , i x ) = i A ,i x i A i x .

Based on this similarity measure for elements, the similarity measure for the sets can be defined by computing the similarity of the mean vectors corresponding to class prototypes [10]:

sim proto (A, x) = s 1 |g 1 (A)| |g1(A)| j=1 i A j , 1 |g ref (x)| |g ref (x)| k=1 i x k .(3)

Note that other approaches of concept similarity can be employed as well, like the variable selection approach in [17]. In the context of our study, we have used the method that both works best and is less complex. A hierarchical application of the similarity measure for the concepts of two ontologies is presented in [17].

A Hierarchical Algorithm for Concept Fuzzification

Let Ω = {O 1 , ..., O n } be a set of (crisp) ontologies that will be referred to as source ontologies defined as in Def. 1. The set of concepts C Ω = n i=1 C i will be referred to as the set of source concepts. The ontologies from the set Ω are assumed to share similar functionalities and application focuses and to be heterogeneous in the sense of some of the heterogeneity types described in Section 3.2. A certain complementarity of these resources can be assumed: they could be defined with the same application scope, but on different levels, treating different and complementary aspects of the same application problem.

Let

O ref = (X, is a ref , R ref , I ref , g ref ) be

an ontology, called a reference ontology whose concepts will be called reference concepts. In contrast to the source ontologies, the ontology O ref is assumed to be a less application dependent, generic knowledge source. As a consequence of Def. 1, the ontologies in Ω and O ref are populated.

The fuzzification procedure that we propose relies on the idea of scoring every source concept by computing its similarities with the reference concepts, using the similarity measure (3). A source concept A will be represented by a function of the kind

µ A (x) = score A (x), ∀x ∈ X,(4)

where score A (x) is the similarity between the concept A and a given reference concept x. Since score takes values between 0 and 1, (4) defines a fuzzy set. We will refer to such a fuzzy set as the fuzzified concept A denoted by A.

In order to fuzzify the concepts of a source ontology O 1 , we propose the following hierarchical algorithm. First, we assign score-vectors, i.e. fuzzy membership functions to all leaf-node concepts of O 1 . Every non-leaf node, if it does not contain instances (documents) of its own, is scored as the maximum of the scores of its children for every x ∈ X. If a non-leaf node has directly assigned instances (not inherited from its children), the node is first scored on the basis of these instances with respect to the reference ontology, and then as the maximum of its children and itself. To illustrate, let a concept A have children A and A and let the non-empty function g * (A) represent the instances assigned directly to the concept A. We compute the following similarity scores for this concept w.r.t. the set X :

score A (x) = max{score A (x), score A (x), score g * (A) (x)}, ∀x ∈ X.(5)

Above, score g * (A) (x) conventionally denotes the similarity obtained for the concept A and a reference concept x by only taking into account the documents assigned directly to A. The algorithm is given in Alg. 1.

It is worth noting that assigning the max of all children to the parent for every x leads to a convergence to uniformity of the membership functions for nodes higher up in the hierarchy. Naturally, the functions of the higher level concepts are expected to be less "specific" than those of the lower level concepts. A concept in a hierarchical structure can be seen as the union of its descendants, and a union corresponds to taking the max (an approach underlying the single link strategy used in clustering).

The hierarchical scoring procedure has the advantage that every x-score will be larger for a parent node than those for any of its children, and it holds that µ A (x) → µ A (x) = 1 for all x and all children A of A. From computational viewpoint, the procedure which only scores the populated nodes is less expensive, compared to scoring all nodes one by one.

Building a Combined Knowledge Body

The construction of a combined knowledge body for a set of source ontologies aims at making explicit the relations that hold among their concepts, across these ontologies. To these ends, we apply the fuzzy set representations acquired in the previous section. In what follows, we consider two source ontologies O 1 and O 2 but note that all definitions can be extended for multiple ontologies. Let C Ω = {A 1 , ..., A |C1| , B 1 , ..., B |C2| } be the union of the concept sets of O 1 (the A-concepts) and O 2 (the B-concepts). We introduce several relations and operations that can be computed over C Ω and will be used for constructing a combined reduced knowledge body that contains the concepts of interest.

Fuzzy Concept Relations

The implication A → A holds for any A and A such that is a(A , A). We provide a definition for a fuzzy subsumption of two fuzzified concepts A and A based on the fuzzy implication (2). Definition 2 (Fuzzy Subsumption). The subsumption A is a A is defined and denoted in the following manner:

is a(A , A) = inf x∈X µ A →A (x)(6)

Equation ( 6) defines the fuzzy subsumption as a degree between 0 and 1 to which one concept is the subsumer of another. It can be shown that is a, similarly to its crisp version, is reflexive and transitive (i.e. a quasi-order). In addition, the hierarchical procedure for concept fuzzification introduced in the previous section assures that is a(A , A) = 1 holds for every child-parent concept pair, i.e. the crisp subsumption relation is preserved by the fuzzification process.

Taking the example of a collaborative platform from the introduction, computing the fuzzy is a between two concepts allows for answering a user query regarding generality and specificity of their partners concepts with respect to a given target concept.

We provide a definition of a fuzzy ontology which follows directly from the fuzzification of the source concepts and their is a relations introduced above. Definition 3 (Fuzzy Ontology). Let C be a set of (fuzzy) concepts, is a : C × C → [0, 1] a fuzzy is a-relationship, R a set of fuzzy relations on C, i.e., R contains relations r : C n → [0, 1], where n is the arity of the relation (for the sake of presentation, we only consider binary relations), X a set of objects, and φ : C → F(X , [0, 1]) a function that assigns a membership function to every fuzzy concept in C. We require that is a and φ are compatible, i.e., that is a(A , A) = inf x µ A →A (x) holds for all A , A ∈ C. In particular, it can be shown that this entails that is a is a fuzzy quasi-order. With these definitions, the quintuple

O = (C, is a, R, X , φ)

forms a fuzzy ontology.

Above, the set X is defined as a set of abstract objects. In our setting, these are the concepts of the reference ontology, i.e. X = X. The set C is any subset of C Ω . In case C = C 1 , where C 1 is the set of fuzzified concepts of the ontology O 1 , O defines a fuzzy version of the crisp source ontology O 1 . In case C = C Ω , O defines a common knowledge body for the two source ontologies. Note that the membership values of the reference concepts entail fuzzy membership values for the documents populating the reference concepts. However, we will work directly with the concepts scores in what follows.

Based on the subsumption relation defined above, we will define equivalence of two concepts in the following manner.

Definition 4 (Fuzzy θ-Equivalence). Fuzzy θ-equivalence between a concept A and a concept B, denoted by A θ B holds if and only if is a(A, B) > θ and is a(B, A) > θ, where θ is a parameter between 0 and 1.

The equivalence relation allows to define classes of equivalence on the set C Ω . In the collaborative framework described in the introduction, this can be used for querying concepts equivalent (up to a degree defined by the user) to a given user concept from the set of their partners concepts.

Similarity Measures for Fuzzy Concepts

We propose several measures of closeness of two fuzzy concepts A and B. We begin by introducing a straightforward measure given by

ρ base (µ A , µ B ) = 1 − max x∈X |µ A (x) − µ B (x)|. (7)

We consider a similarity measure based on the Euclidean distance:

ρ eucl (µ A , µ B ) = 1 − µ A − µ B 2 ,(8)

where x 2 = x∈X |x| 2 1/2 is the 2 -norm. Several measures of fuzzy set compatibility can be applied, as well. Zadeh's partial matching index between two fuzzy sets is given by

ρ sup-min (µ A , µ B ) = sup x∈X T (µ A (x), µ B (x)).(9)

Finally, the Jaccard coefficient is defined by

ρ jacc (µ A , µ B ) = x T (µ A (x), µ B (x)) x S(µ A (x), µ B (x)) . (10)

It is required that at least one of the functions µ A or µ B takes a non-zero value for some x. T and S are as defined in Section 3.

The similarity measures listed above provide different information as compared to the relations introduced in the previous subsection. Subsumption and equivalence characterize the structural relation between concepts, whereas similarity measures closeness between set elements. The two types of information are to be used in a complementary manner within the collaboration framework.

Quantifying Commonality and Relative Specificity

The union of two fuzzy concepts can be decomposed into three components, each quantifying, respectively, the commonality of both concepts, the specificity of the first compared to the second and the specificity of the second compared to the first expressed in the following manner

S(A, B) = (AB) + (A − B) + (B − A).(11)

Each of these components is defined as follows and, respectively, accounts for:

AB = T (A, B) //

Several merge options can be provided to the user with respect to the values of these three components. In case AB is significantly larger than each of A − B and B −A, the two concepts can be merged into their union. In case one of A−B or B − A is larger than the other two components, the concepts can be merged to either A or B.

Experiments

We situate our experiments in the multimedia domain, opposing two complementary heterogeneous ontologies containing annotated pictures. We chose, on one hand, LSCOM [14] initially built in the framework of TRECVID 1 and populated with the development set of TRECVID 2005. Since this set contains images from broadcast news videos, LSCOM is particularly adapted to annotate this kind of content, thus contains abstract and specific concepts (e.g. Science Technology, Interview On Location). On the other hand, we used WordNet [11] populated with the LabelMe dataset [12], referred to as the La-belMe ontology. Contrarily to LSCOM, this ontology is very general, populated with photographs from daily life and contains concepts such as car, computer, person, etc. The parts of the two multimedia ontologies used in the experiments are shown in Figure 1. A text document has been generated for every image of the two ontologies, by taking the names of all concepts that an image contains in its annotation, as well as the (textual) definitions of these concepts (the LSCOM definitions for ities (applying the measures from Section 5.2 and the standard cosine measure). Apart from the classical Gödel subsumption defined in ( 6), we consider a version of it which takes the average over all x instead of the smallest value, given as is a mean (A , A) = avg x∈X µ A →A (x). The results for several intra-ontology concepts and several cross-ontology concepts are given in Table 1. Fig. 3 shows a fragment of the common fuzzy ontology built for LSCOM and LabelMe. The labels of the edges of the graph correspond to the values of the fuzzy subsumptions between concepts.

We will underline several shortcomings that need to be adressed in future work. Due to data heterogeneity, it appears that the fuzzy is a-structure is reflected better within one single ontology, as compared to cross-ontology relations which are more interesting. Additionally, some part of relations are expressed as subsumptional (e.g. torso is a person) which is a natural effect in view of the instance-representations. Indeed, the textual representation of images needs to be improved by accounting for the limitations discussed earlier in this section. Note that computing the common fuzzy ontology is inexpensive, once we have in hand the fuzzy representations of the source concepts made available by the hierarchical scoring algiorithm.

Conclusion and Open Ends

Whenever collaboration between knowledge resources is required, it is important to provide procedures which make explicit to users the relations that hold between different terms of these resources. In an attempt to solve this problem, we have proposed a fuzzy theoretical approach to build a common ontology for a set of source ontologies which contains these relations, as well as the degrees to which they hold, and can be queried upon need by different parties within a collaborative framework.

In future work, we will investigate the impact of the choice of a reference ontology onto the concept fuzzification and the quality of the constructed fuzzy common ontology. Additionally, the approach will be extended with elements of OWL 2, including relations and axioms between instances which is not covered by the ontology definition used in this work.