Using Cooperative Agent Negotiation for Ontology Mapping

Abstract

Well-known approaches for the ontology mapping can be grouped into lexical, semantic, and structural ones. We assume that the approaches are complementary to each other and their combination produces better results than the individual ones. However, they produce di®erent and probably con°icting results, which must be shared, compared, chosen and agreed. This paper proposes a cooperative negotiation model, where agents apply individual mapping algorithms and negotiate on a ¯nal mapping result. We compare our model with three state of the art matching systems. The results, although preliminary, are promising especially for what concerns precision and recall.

Introduction

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 ¯rst 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 con°icts posed by having only partial views [ 8 ].

This kind of negotiation has been currently adopted in resource and task allocation ¯elds [ 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 di®erent ontology mapping approaches. 3

Ontology Mapping

The ontology mapping process aims to de¯ne 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 di®erent concepts are common. For example the words \score" and \store", represent di®erent 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 speci¯cs 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 speci¯c 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 di®erent and probably con°icting 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 ¯nal mapping result. In our model, the agents use lexical, semantic and structural approaches to map terms of two di®erent ontologies. The distinct mapping results are shared, compared, chosen and agreed, and a ¯nal 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. 4.1

Organization of the Society of Agents

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 de¯nes what agents could do in their environments (their roles). The functional dimension de¯nes how agents execute their goals. The deontic dimension de¯nes the permissions and obligations of a role in a goal. This paper focuses on the ¯rst dimension.

According to [ 13 ] and [ 12 ], structural speci¯cation 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 identi¯ed 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 de¯ned 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 speci¯es 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 speci¯cation de¯nes only a group called negotiation and all links are intra-group.

Based on the structural speci¯cation 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. 4.2

Negotiation Process

Basically, the negotiation process involves two phases. First, the agents work in an independent manner, applying a speci¯c 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 de¯ne 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 speci¯ed 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 veri¯ed 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).

Category Mapping (certainty) Mapping (uncertainty) Not mapping (uncertainty) Not mapping (certainty) 2Ontologies available in http://dit.unitn.it/»accord/Experimentaldesign.html(Test 4) objects are evaluated.

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). 5

Experiments

We applied the proposed negotiation model to link corresponding class names in two di®erent 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 API5, 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 de¯ned 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 directories6, product schemas7, course university catalogs8, and company pro¯les9. 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 identi¯ed as correct by our model, but which were not identi¯ed by the experts). We also indicated the number of possible mappings for each group of ontologies (numbers in brackets).

The consensus identi¯ed correctly all mappings de¯ned by the expert, for all groups { all mappings de¯ned 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" 3Obtained from http://dit.unitn.it/»accord/Experimentaldesign.html 4http://alignapi.gforce.inria.fr 5http://jwn.sourceforge.net (using WordNet 2.1) 6http://dit.unitn.it/»accord/Experimentaldesign.html (Test 3) 7http://dit.unitn.it/»accord/Experimentaldesign.html (Test 4) 8http://dit.unitn.it/»accord/Experimentaldesign.html (Test 7) 9http://dit.unitn.it/»accord/Experimentaldesign.html (Test 8)

Ontology Google and Yahoo directories (54) Product schemas (30) Course catalogs (48) Company pro¯les (9) 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 identi¯ed. This mapping was not de¯ned 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 su±cient 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 pro¯les"), 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), identi¯ed 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 ¯nal 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 identi¯ed cases where con°icts occur, which are not resolved by our model and the semantic agent is not su±cient to identify them. Considering the terms \Music/History" and \Architecture/History" (\Google and Yahoo" ontologies), the semantic and lexical agents returned \mappings with certainty", di®erently 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 con°ict. 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 speci¯c 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 ¯rst 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. 6

Related Work

In the ¯eld of ontology negotiation we ¯nd 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 speci¯c purpose. We do not consider negotiation steps such as the ones presented in [ 1 ], namely clari¯cation and explanation. But we consider di®erent 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 con¯dence value that is obtained by utility functions. According to the con¯dence value the mapping rule is accepted, rejected or negotiated. Di®erently 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 con°ict arises between the matchers (i.e., there exist an equal number of votes to distinct mapping categories). 7

Final Remarks

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 di®erent 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 di®erent 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 su±cient to obtain a satisfactory mapping. Several approaches must be combined, as exempli¯ed 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.

Acknowledgments

The ¯rst author is supported by the Programme Alban, the European Union Programme of High Level Scholarships for Latin America, scholarship number E05D059374BR.

References

[1] Sidney Bailin and Walt Truszkowski . Ontology negotiation between intelligent information agents . The Knowledge Engineering Review , 17 ( 1 ):7{ 19 , 2002 .

[2] M. Beer , M. d'Inverno, M. Luck , N. Jennings , C. Preist , and M. Schroeder . Negotiation in multi-agent systems . In Workshop of the UK Special Interest Group on Multi-Agent Systems , 1998 .

[3] J. Bigham and L. Du . Cooperative negotiation in a multi-agent system for real-time load balancing of a mobile cellular network . In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems , pages 568 { 575 . ACM Press, 2003 .

[4] Marcirio Chaves . Mapeamento e comparacao de similaridade entre estruturas ontologicas . Master's thesis , Ponti¯cia Universidade Catolica do Rio Grande do Sul , 2002 .

[5] J. van Diggelen , R.J. Beun , F. Dignum , van R.M. Eijk , and J. Ch . Meyer. Anemone: An e®ective minimal ontology negotiation environment . In Proceedings of the V International Conference on Autonomous Agents and Multi-Agent Systems , pages 899 { 906 , 2006 .

[6] Hong Hai Do and Erhard Rahm . Coma - a system for °exible combination of schema matching approaches . In Proceedings of the 28th Conference on Very Large Databases (VLDB) , 2002 .

[7] J. Euzenat , T. Le Bach , J. Barrasa , P. Bouquet , J. De Bo , R. Dieng-Kuntz , M. Ehrig , M. Hauswirth , M. Jarrar , R. Lara , D. Maynard , A. Napoli , G. Stamou, H. Stuckenschmidt , P. Shvaiko , S. Tessaris , S. Van Acker , and I. Zaihrayeu. State of the art on ontology alignment . Technical report , 2004 .

[8] N. Gatti and F. Amigoni . A cooperative negotiation protocol for physiological model combination . In Proceedings of the Third Internation Joint Conference on Automomous Agents and Multi-Agent Systems , pages 655 { 662 , 2004 .

[9] F. Giunchiglia , P. Shvaiko , and M. Yatskevich . S-match: An algorithm and an implementation of semantic matching . In First European Semantic Web Symposium , pages 61 { 75 , 2004 .

[10] S. Green , L. Hurst , B. Nangle , P. Cunningham , F. Somers , and R. Evans . Software agents: A review . Technical report , Trinity College, 1997 .

[11] Farshad Hakimpour and Andreas Geppert . Resolving semantic heterogeneity in schema integration: an ontology approach . In Proceedings of the International Conference on Formal Ontology in Informational Systems , pages 297 { 308 , 2001 .

[12] Jomi Hubner . Um Modelo de Reorganizac»~ao de Sistemas Multiagentes. PhD thesis , Escola Polit¶ecnica da Universidades de S~ao Paulo, Departamento de Engenharia da Computa»ca~o e Sistemas Digitais, 2003 .

[13] Jomi Hubner , Jaime Sichman, and Olivier Boisser . A model for structural, functional, and deontic speci¯cation of organizations in multiagent systems . In Advances in Arti¯cial Intelligence , 2002 .

[14] P. Bernstein J. Madhavan and E. Rahm . Generic schema matching with cupid . In Proceedings of the Very Large Data Bases Conference (VLDB) , pages 49 { 58 , 2001 .

[15] L. Laera , V. Tamma , J. Euzenat , T. Bench-Capon , and T. R. Payne . Reaching agreement over ontology alignments . In Proceedings of 5th International Semantic Web Conference (ISWC 2006 ).

[16] S. Lander and V. Lesser . Understanding the role of negotiation in distributed search among heterogeneous agents . In Proceedings of the International Joint Conference on Arti¯cial Intelligence , January 1993 .

[17] I. Levenshtein . Binary codes capable of correcting deletions, insertions an reversals . In Cybernetics and Control Theory , 1966 .

[18] A. Maedche , B. Motik , N. Silva , and R. Volz . Mafra - a mapping framework for distributed ontologies . In 13th International Conference on Knowledge Engineering and Knowledge Management , pages 235 { 250 , 2002 .

[19] A. Maedche and Ste®en Staab. Measuring similarity between ontologies . In Proceedings of the European Conference on Knowledge Acquisition and Management , pages 251 { 263 , 2002 .

[20] M. Mailler , V. Lesser , and B. Horling . Cooperative negotiation for soft real-time distributed resource allocation . In Proceedings of the second international joint conference on Autonomous agents and multiagent systems , pages 576 { 583 . ACM Press, 2003 .

[21] Andrea Rodriguez and Max Egenhofer . Determining semantic similarity among entity classes from di®erent ontologies . IEEE Transactions on Knowledge and Data Engineering , 15 ( 2 ): 442 { 456 , 2003 .

[22] Nuno Silva , Paulo Maio, and Joao Rocha . An approach to ontology mapping negotiation . In Proceedings of the K-CAP Workshop on Integrating Ontologies.

[23] T.F. Smith and M.S. Waterman . Identi¯cation of common molecular subsequences . Journal of Molecular Biology , 147 : 195 { 197 , 1981 .

[24] G. Stoilos , G. Stamou, and S. Kollias . A string metric for ontology alignment . In ISWC , pages 624 { 637 . 4th International Semantic Web Conference (ISWC 2005 ), Galway, 2005 , 2005 .

[25] Valentina Tamma , Michael Wooldridge, Ian Blacoe, and Ian Dickinson . An ontology based approach to automated negotiation . In Proceedings of the IV Workshop on Agent Mediated Electronic Commerce , pages 219 { 237 , 2002 .

[26] M. Wooldridge . An Introduction to Multiagent Systems . John Wiley and Sons, 2002 .

[27] X. Zhang , V. Lesser , and R. Podorozhny . Multi-dimensional, multistep negoriation for task allocation in a cooperative system . Autonomous Agents and Multi-Agent Systems , 10 :5{ 40 , 2005 .