Ontology mapping is the process of linking corresponding terms from different ontologies. The mapping result can be used for ontology merging, agent communication, query answering, or for navigation on the Semantic Web.
Well-known approaches to the problem can be grouped into lexical, semantic, and structural ones, as terms may be mapped by a measure of lexical similarity, or they can be evaluated semantically, usually on the basis of semantic oriented linguistic resources, or considering the term positions in the ontology hierarchy. However even in the same group of approaches, different approaches are abundant in the literature. Examples of lexical approaches are [24] [19] while semantic and structural ones can be seen in [11] [21].
Individual approaches are not satisfactory to the problem. We assume that these approaches are complementary to each other and their combination produces better results than the individual ones. However, they produce different and probably conflicting results, which must be shared, compared, chosen and agreed. We propose a cooperative negotiation model, where agents apply individual mapping algorithms and negotiate on a final mapping result. We compared our model with three state of the art schema-based matching systems, namely Cupid [14], COMA [6], and S-Match [9]. The results, although preliminary, are promising, especially for what concerns precision and recall.
This paper is structured as follows. The next section comments on cooperative negotiation. Section 3 introduces the ontology mapping approaches. Section 4 presents our cooperative negotiation model. Section 5 presents the experiments using our model. Section 6 comments relevant related works. Finally, Section 7 presents the final remarks and the future works.
Negotiation is a process by which two or more parties make a joint decision [27]. It is a key form of interaction that enables groups of agents to arrive to mutual agreement regarding some belief, goal or plan [2]. Hence the basic idea behind negotiation is reaching a consensus [10].
Negotiation usually proceeds in a series of rounds, with every agent making a proposal at each round [26]. The process can be described as follows, based on [16]. One agent generates a proposal and other agents review it. If some other agent does not like the proposal, it rejects the proposal and might generate a counter-proposal. If so, the other agents (including the agent that generated the first proposal) review the counter-proposal and the process is repeated. It is assumed that a proposal becomes a solution when it is accepted by all agents.
Cooperative negotiation is a particular kind of negotiation where agents cooperate and collaborate to obtain a common objective. In cooperative negotiation, each agent has a partial view of the problem and the results are put together via negotiation trying to solve the conflicts posed by having only partial views [8].
This kind of negotiation has been currently adopted in resource and task allocation fields [3][20] [27]. In these approaches, the agents try to reach the maximum global utility that takes into account the worth of all their activities. In our approach the cooperative negotiation is a form of interaction that enables the agents to arrive to mutual agreement regarding the result of different ontology mapping approaches.
The ontology mapping process aims to define a mapping between terms of a source ontology and terms of a target ontology. The approaches for ontology mapping varies from lexical (see [24][19]) to semantic and structural levels (see [11]). Moreover, the mapping process can be grouped into data layer, ontology structure, or context layer.
At the lexical level, metrics to compare string similarity are adopted. One well-known measure is the Levenshtein distance or edit distance [17], which is given by the minimum number of operations (insertion, deletion, or substitution of a single character) needed to transform one string into another. Based on Levenshtein measure, [19] proposes a lexical similarity measure for strings, the String Matching (SM), that considers the number of changes that must be made to change one string into the other and weighs the number of these changes against the length of the shortest string of these two. Other common metrics can be found in [23] and [7].
The semantic level considers the semantic relations between concepts to measure the similarity between them, usually on the basis of semantic oriented linguistic resources. The well-known WordNet1 database, a large repository of English semantically related items, has been used to provide these relations. This kind of mapping is complementary to the pure string similarity metrics. Cases where string metrics fail to identify high similarity between strings that represent completely different concepts are common. For example the words "score" and "store", represent different concepts, but the Levenshtein metric returns 0.68. It is not uncommon works exploring the semantic-structural levels [4] [11]. At the structural level, positions of the terms in the ontology hierarchy are considered, i.e, terms more generals and terms more specifics are considered as input to the mapping process. For instance, in WordNet database there is not direct relation between "blue" and "pink" terms, but they can be connected by an ancestor term, such as "color".
On the other hand, the mapping can be grouped into data layer, ontology structure, and context layer. In the data layer, the instances of the ontology are used as input to the mapping approach (for instance, the attributes data type of the instances are compared). In the ontology layer, the terms of the ontology structure and the hierarchy are taking into account (as example, the class name is take into account). The recent approach involves to consider the ontology's application context, i.e, how the ontology entities are used in some external context. This is especially interesting, for instance, to identify WordNet senses that must be considered to specific terms.
Using only one approach is not satisfactory to the problem. We understand that the approaches are complementary to each other and their combination produces better results than the individual ones. However, they produce different and probably conflicting results, which must be resolved. For instance, when mapping the terms "Music/History" (where "Music" is the super-class of "History") and "Architecture/History", an agent based on lexical approaches indicates that the terms are equivalent, while an agent based on structural approaches indicates that the terms can not be mapped because the super-classes are not the same. We propose a cooperative negotiation model, where agents apply individual mapping algorithms and negotiate on a final mapping result.
In our model, the agents use lexical, semantic and structural approaches to map terms of two different ontologies. The distinct mapping results are shared, compared, chosen and agreed, and a final mapping result is obtained. This approach aims to overcome the drawbacks of the using individual ontology mapping approaches. First, we present the organization of the society of agents and next we detail the negotiation process.
We describe our model according to a society of agents (Figure 1), using the Moise+ model [13]. This model proposes three dimensions for the organizations of society of agents: structural, functional and deontic. The structural dimension defines what agents could do in their environments (their roles). The functional dimension defines how agents execute their goals. The deontic dimension defines the permissions and obligations of a role in a goal. This paper focuses on the first dimension.
According to [13] and [12], structural specification has three main concepts, roles, role relations and groups that are used to build, respectively, the individual, social and collective structural levels of an organization. The individual level is composed by the roles of the organization. A role means a set of constraints that an agent ought to follow when it accepts to play that role in a group. The following roles are identified in the proposed organization:
• Mediator: this role is responsible for mediating the negotiation process, sending and receiving messages to and from the mapping agents.
• Matcher: this role is responsible for giving an output between two ontology mappings (i.e., encapsulates the mapping algorithms). One matcher could assume the lexical, semantic or structural role. On the lexical role, the matcher makes the mapping using algorithms based on string similarity. On the semantic role, the agent searches by corresponding terms in a semantic oriented linguistic database. On the structural role, the agent is based on the intuition that if super-classes are the same, the compared classes are similar to each other. If sub-classes are the same, the compared classes are also similar.
At the social level are defined the kinds of relations among roles that directly constrain the agents. Some of the possible relations are:
• Acquaintance (acq): agents playing a source role are allowed to have a representation of the agents playing the destination role. In Figure 1, this kind of relation is present between the source role mediator and the destination role matcher.
• Communication (com): agents playing a source role are allowed to communicate with agents that play the destination role. In Figure 1, this kind of relation is present between the source role mediator and the destination role matcher (by heritage, lexical, semantic and structural).
• Authority (aut): agents playing a source role has authority upon agent playing destination role. In Figure 1, this kind of relation is present between the source role semantic and the destination roles lexical and structural.
The collective level specifies the group formation inside the organization. A group is composed by the roles that the system could assume, the sub-groups that could be created inside a group, the links (relations) valid for agent and by the cardinality. A group can have intra-groups links and inter-groups links. The intra-group links state that an agent playing the link source role in a group is linked to all agents playing the destination role in the same group or in its sub-groups. The inter-group links state that an agent playing the source role is linked to all agents playing the destination role despite the groups these agents belong to [13]. Links intra-group are represented by a hatched line and links inter-groups are represented by a continue line. This specification defines only a group called negotiation and all links are intra-group.
Based on the structural specification of the proposed organization, our society is composed by one agent that assumes the mediator role and three agents that assume the matcher role. One of the matcher agents is assuming the lexical role, one is assuming the semantic role, and one is assuming the structural role.
Basically, the negotiation process involves two phases. First, the agents work in an independent manner, applying a specific mapping approach and generating a set of negotiation objects. A negotiation object is a triple O = (T1,T2,C), where T1 corresponds to a term in the ontology 1, T2 corresponds to a term in the ontology 2, and C is the mapping category resulting from the mapping for these two terms. Second, the set of negotiation objects, that compose the mapping is negotiated among the agents. The negotiation process involves one mediator and several matcher agents.
In order to facilitate the negotiation process (i.e, reduce the number of negotiation rules), we define four mapping categories according to the output of the matcher agents. Table 1 shows the categories and the corresponding mapping results.
The output of the lexical agents is a value from the interval [0,1], where 1 indicates high similarity between two terms (i.e, the strings are identical). This way, if the output is 1, a "mapping with certainty" is obtained. If the output is 0, the agent has a "not mapping with certainty". A threshold is used to classify the output in uncertain categories. The threshold value is specified by the user.
The semantic agents consider semantic relations between terms according to the WordNet database. Relations such as synonym, antonym, holonym, meronym, hyponym, and hypernym can be returned for a given pair of terms. Synonymous terms are considered as "mapping with certainty"; terms related by holonym, meronym, hyponym, or hypernym are considered "mapping with uncertainty"; when the terms can not be related by the WordNet (the terms are unknown for the WordNet database), the terms are considered as not "mappings with uncertainty".
The structural agent uses the super-classes intuition to verify if the terms can be considered similar. First, it is verified if the super-classes are lexically similar. Otherwise, the semantic similarity is used. If the super-classes are lexically or semantically similar, the terms are similar to each other. The matching category corresponds the output of the lexical or semantic comparison (e.g, if super-classes are not lexically similar, but they are considered synonymous, a "mapping with certainty" is returned). Figure 2 shows an AUML interaction diagram with the messages changed between the agents during a negotiation round. We use an extension of AUML-2 standard to represent agents' actions (the actions are placed centered over the lifeline of the named agent). The interaction diagram refers to negotiation of the mapping between the classes "personal computer " and "pc" (Figures 3 and 4) 2 .
The negotiation process starts with the mediator agent asking to the matcher agents for its number of "mappings with certainty". The first matcher agent to generate a proposal is one that has the greatest number of "mappings with certainty" (lexical agent, in the specific example).
The proposal contains the first negotiation object that still wasn't evaluated by the agent. This proposal is then sent to the mediator agent, which sends it to other agents (in the specific example, the lexical agent proposes a "not mapping with certainty" to the mapping between the classes "personal computer" and "pc"). Each agent then evaluates the proposal, searching for an equivalent negotiation object. One negotiation object is equivalent to another when both refers to equals terms which are being compared in the two ontologies.
If an equivalent negotiation object has the same category, the agent accepts the proposal. Otherwise, if the agent has a different category for the compared terms in the negotiation object, its object negotiation is sent as a counter-proposal to the mediator agent, which evaluates the several counter-proposals received (several agents can send a counter-proposal). In the example, semantic and structural agents have generated counter-proposals, indicating a "mapping with certainty" between the compared terms. The semantic agent identifies that the terms are synonymous in WordNet, and structural agent identifies terms having the same super-class ("electronics").
The mediator selects one counter-proposal that has the greater number of vote. If two categories receive the same number of votes, the category indicated by the semantic agent is considered a consensus. When a proposal is accepted by all agents or a counter-proposal consensus is obtained, the mediator adds the corresponding negotiation object in a consensus negotiation set and the matcher agents mark its equivalent one as evaluated. The negotiation ends when all negotiation At moment we have implemented a negotiation mechanism based on voting and used it to validate our proposal on composite ontology matching approaches. However, we are working on argument-based negotiation, in order to improve this model (see [15] for related work).
We applied the proposed negotiation model to link corresponding class names in two different ontologies. The results produced by our negotiation model were compared with manual matches3 (expert mappings).
The lexical agent was implemented using the edit distance measure (Levenshtein measure). We used the algorithm available in the API for ontology alignment (INRIA) 4 (EditDistNameAlignment). The semantic agent uses the JWordNet API 5 , which is an interface to the WordNet database. For each WordNet synset, we retrieved the synonymous terms and considered the hypernym, hyponym, member-holonym, member-meronym, part-holonym, and part-meronym as related terms. The structural agent is based on super-classes similarity.
The threshold used to classify the matcher agents output was 0.6. This value was defined based on previous analysis of the edit distance values between the terms of the ontologies used in the experiments. The terms with edit distance values greater than 0.6 have presented lexical similarity.
A pre-processing step was made, where special characters (e.g., ) and stop words (e.g., "and", "or", "of") were removed.
We have used four groups of ontologies: parts of Google and Yahoo web directories 6 , product schemas7 , course university catalogs8 , and company profiles 9 . We considered the "mappings with certainty" and the "mappings with uncertainty" as examples of the positive classes. As a mapping quality measure, the well-know measures of precision, recall and F-measure were used.
First, we compared the results obtained from our negotiation model with the results from expert mapping (Table 2 -the column "Others" contains mappings identified as correct by our model, but which were not identified by the experts). We also indicated the number of possible mappings for each group of ontologies (numbers in brackets).
The consensus identified correctly all mappings defined by the expert, for all groups -all mappings defined by the expert were returned as "mappings with certainty" by our model. When considering the other mappings ("Others"), for the "Google and Yahoo", 3 "mappings with certainty" and 5 "mappings with uncertainty" have been returned. For instance, a "mapping with uncertainty" between the terms "Arts/Visual Arts" (where "Arts" is the super-class of "Visual Arts") and "Arts Humanities/Design Art" has seen identified. This mapping was not defined by expert, however it could be considered as correct. This kind of "mapping with uncertainty" has been observed in the other examples. In "Product schemas", only one new mapping has been returned, being a "mapping with certainty", but incorrectly (i.e., "Electronics/Personal Computers/Accessories" and "Electronic/Cameras and Photos/Accessories"). Finally, for the "Course catalogs", 3 new mappings were categorized as "mappings with uncertainty" (e.g., "Courses/College of engineering" and "Courses/College of Arts and Sciences").
Second, we compared the output of all agents (Table 3) (where P = precision; R = recall; and F = F-measure). Using lexical or structural individual agents was not sufficient to obtain all correct mappings. These agents did not classify correctly all positive classes (0.64 and 0.68, respectively, for recall, and 0.67 and 0.71, for F-measure), although having good precision measures. The consensus resulting from negotiation is better than the individual results obtained by these agents, having output correctly all positive classes (recall equals 1 for all groups of ontologies). The semantic agent had better performance than lexical and structural agents (recall equals 1 and F-measure equals 0.78), and it produces similar results when compared with the consensus. For ontologies which are lexically and structurally simple (e.g., "Company profiles"), all agents produce equivalent results.
The similar results between semantic agent and negotiation consensus occurs because all labels mapped by experts have strong semantic correspondence (more than structural), identified as "mappings with certainty" by the semantic agent. In these cases, the structural agent returned "mappings with uncertainty", while the lexical agent returned "not mappings with certainty" (e.g., the correct mapping between "Arts/Arts History" and "Architecture/History" terms). Then, the semantic agent decides the final category. However, for the "Google and Yahoo" ontologies, which have greater number of terms (54) when compared with the other groups of ontologies, the consensus returned better precision (0.33) than semantic agent (0.28). As a concluding result, the consensus had better behavior than lexical, semantic and structural individual agents, with F-measure value equals 0.79 against 0.67, 0.78 and 0.71, respectively.
We also identified cases where conflicts occur, which are not resolved by our model and the semantic agent is not sufficient to identify them. Considering the terms "Music/History" and "Architecture/History" ("Google and Yahoo" ontologies), the semantic and lexical agents returned "mappings with certainty", differently of the structural agent. However, this is not a correct mapping. We are working on argument-based negotiation, in order to solve this kind of conflict. An argument for accepting the mapping may be that the terms are synonymous and an argument against may be that some of their super-concepts are not mapped.
Finally, we compared our negotiation model with three state of the art matching systems: Cupid [14], COMA [6], and S-Match [9]. The comparative results among these three systems are available in [9]. These results consider the mappings between attributes of the ontologies in order to compute the precision and recall measures. Then, we have added to our ontologies such attributes, which are viewed as specific sub-classes by our agents. Table 4 shows the comparative results. Considering the attributes of the ontologies, the number of terms to be compared is 160 (i.e., 10 terms in the first ontology and 16 terms in the second ontology).
As shown in Table 4, our model returned better precision than Cupid and COMA, and similar precision when compared to the S-Match, having returned as "mapping with certainty" only the correct expert mappings (precision equals to 1). When comparing the F-measure values, our model had similar result than COMA and S-Match and better result than Cupid.
In the field of ontology negotiation we find distinct proposals. [25] presents an ontology to serve as the basis for agent negotiation, the ontology itself is not the object being negotiated. A similar approach is proposed by [5], where ontologies are integrated to support the communication among heterogeneous agents. [1] presents an ontology negotiation model which aims to arrive at a common ontology which the agents can use in their particular interaction. We, on the other hand, are concerned with delivering alignment pairs found by a group of agents through a negotiation process. The links between related concepts are the result of the negotiation, instead of an integrated ontology upon which the agents will be able to communicate for a specific purpose. We do not consider negotiation steps such as the ones presented in [1], namely clarification and explanation. But we consider different alignment methods negotiating through voting on the best solution for the alignment problem. [22] describes an approach for ontology mapping negotiation, where the mapping is composed by a set of semantic bridges and their inter-relations, as proposed in [18]. The agents are able to achieve a consensus about the mapping through the evaluation of a confidence value that is obtained by utility functions. According to the confidence value the mapping rule is accepted, rejected or negotiated. Differently from [22], we do not use utility functions. Our negotiation mechanism is based on voting, where the semantic agent is responsible for making a decision when a conflict arises between the matchers (i.e., there exist an equal number of votes to distinct mapping categories).
This paper presented an approach on ontology mapping negotiation, in which agents are able to achieve consensus about their individual mapping results. These agents encapsulate different mapping approaches (lexical, semantic and structural) and consensus results from cooperative negotiation of these agents. We compared our results with expert mappings, for four ontologies in different domains. We also compared our negotiation model with three state of the art matching systems.
Our proposal of a negotiation model is due to the belief that using single matching approaches is not sufficient to obtain a satisfactory mapping. Several approaches must be combined, as exemplified by our initial experiments. The negotiation result was better than lexical and structural agents and it returned better F-measure value than then semantic agent. When comparing our model with the three state of the art matching systems, our model obtained better F-measure than Cupid and COMA and similar results if compared with the S-Match system. The results, although preliminary, are promising especially for what concerns F-measure values.
In the future, we intend to use argumentation-based negotiation; compare the initial results with that obtained from larger ontologies; add to our model structural agents based on sub-classes similarity; consider agents using constraint-based approaches; and use the ontology's application context in our matching approach. Next, we also plan to use the mapping result as input to an ontology merge process in the question answering domain.
The first author is supported by the Programme Alban, the European Union Programme of High Level Scholarships for Latin America, scholarship number E05D059374BR.