Mutual Online Ontology Alignment Jun Wang Les Gasser Graduate School of Library and Information Science University of Illinois at Urbana-Champaign 501 E. Daniel St., Champaign, IL 61820, USA {junwang4, gasser}@uiuc.edu ABSTRACT In short, we need distributed methods that manage both One critical foundation for reliable collective coordinated control uncertainty and semantic uncertainty in dynamic action in multi-agent systems is the ability to exchange rep- settings, and that reduce—or at least stabilize—both uncer- resentational objects that can be locally interpreted in ways tainties over time. Two points of interactional and temporal that make collective sense. Coherent local interpretation of space interest us: the long-term, large-scale dynamics of col- shared representations is needed to create global semantic lective concepts and their overall structure, and the short coherence for the distributed actions of individual agents. term adjustment, adaptation, and innovation processes in The process of autonomously establishing a collective se- which situation-specific concepts and interpretations emerge mantics and organization of the concepts in an open domain quickly within a context of the more stable and long-term is not well understood. This paper discusses our motivations conceptual architecture. We are led to viewing collective and approach to this problem. It presents a specific formal- concept management as a multi-tiered dynamic system built ization and algorithm that we call mutual online ontology from constrained, regionalized (i.e., not globally random) in- alignment with its rationale, and illustrates the performance teractions, that may have local dynamism while exhibiting a of the approach with some simulation experiments. degree of global stability. In our research work as a whole, we approach these two levels with two different methodologies: Keywords: ontology evolution, ontology alignment, co- algorithms for rapid multi-agent mutual concept design and learning alignment for the local, short term adaptation, and a “popu- lation dynamics of concepts” for understanding, predicting, 1. INTRODUCTION and stabilizing the longer-term structural properties of con- ceptual spaces. In this paper we treat only the design of “We must be systematic, but we should keep our specific algorithms for the short-term, context-sensitive mu- systems open.” (Alfred North Whitehead, Modes tual adaptation of ontologies by a collection of autonomous of Thought). agents. Our work on the issues of stability and long-term structure of collective ontologies is treated elsewhere. In multi-agent systems research and practice, reliable collec- Agents cooperating in a multi-agent setting need a shared tive coordinated action rests on two foundations: ontology[8]. But the fact is that there is often more than one ontology established in a given domain. Since these F1. Distributed reasoning algorithms whose critical prop- existing ontologies are designed by different people or orga- erty is their ability to manage the control uncertainty inher- nizations, ontology alignment1 is needed for agents to coop- ent in distributed settings. erate in multi-agent systems. Recently there has been an increasing interest in ontology alignment [6, 4, 1, 5, 2]. F2. Representational objects that can be exchanged and still be locally interpreted in ways that make collective sense, However, existing work on ontology alignment does not fully yielding semantic coherence to the actions of distributed al- accommodate requirements for open multi-agent systems. gorithms. Open multi-agent systems must adapt rapidly to new cate- gories, conceptualizations, and specifications of domains — This presents a kind of chicken-and-egg problem: distributed they cannot be defined or aligned once and for all. Moreover, reasoning algorithms depend on collectively-sensible objects autonomous multi-agent systems must refine and align their for coherent behavior, yet the collective sensibility of ob- own ontologies collectively, not through the external human jects arises through distributed reasoning algorithms. So, intervention of standards committees and designers. To cre- our central questions are these: ate multi-agent systems that are both adaptive and open, agents must collectively design common ontologies actively Q1. How can we break into this cycle and create algorithms in an online fashion. to bootstrap and adapt new collective object semantics over time? To this end, we propose a mutual ontology adaptation frame- Q2. How can we stabilize collective semantics in dynamic 1 By ontology alignment we mean a process that is often ap- settings so that collective behavior is possible? proached through ontology mapping and/or merging. work. The framework assumes that each agent has its own agents will eventually converge to a shared ontology. ontology which is not open to other agents or outside. An agent learns about the ontology of other agents through the 3. MUTUAL ONTOLOGY ADAPTATION exchange of information. In this paper, we define an ontol- ogy as an extensional categorization of the domain of inter- FRAMEWORK est, and we define the information that agents exchange as an instance or object of an ontological category. We will de- scribe this approach formally in next section. The intuition adaptation adaptation behind this assumption is that each person in human society has its own ontology or conceptualization about the world, ontology ontology interpretation and one way that we know about the ontologies of others is interpretation production production through the exchange (or reference to) of instances such as concrete examples rather than the exchange of an abstract concept. Based on the above framework, we design an ontology align- instance agent k instance ment game in which agents with different ontologies mutu- ally adapt to each other’s ontology through interaction. We agent i agent j also conduct an experimental simulation of the game which shows how agents can converge to a shared ontology, using a mutual ontology update algorithm proposed in this paper. communication 2. ONTOLOGY ALIGNMENT PROBLEM channel FORMAL DESCRIPTION An ontology is a system of categories for a domain [7]. Let there be n agents {A1 , · · · , An }, and a domain O which has Figure 1: Framework of mutual ontology adaptation m instances or objects O = {o1 , · · · , om }. Each agent Ai has a categorization Ci on the domain O. A categorization C is To approach the online ontology alignment problem, we in- a partition of the domain O: C = c1 ∪ c2 ∪ · · · ∪ ck , where troduce a mutual online ontology adaptation framework (see ci = {o1 , · · · , cli } is called a category. For example, let a figure 1). A mutual online ontology adaptation system con- domain O have 10 instances: O = {0, 1, ..., 9}. A catego- sists of a set of agents and a communication channel used by rization can be: C = {0, 1, 2, 3} ∪ {4, 5, 6, 7} ∪ {8, 9}, where agents to exchange information. In this paper we suppose c1 = {0, 1, 2, 3}, c2 = {4, 5, 6, 7}, and c3 = {8, 9} are three the communication channel is perfect without noise. For categories. one agent, the framework includes five elements: ontology, instance, instance production, instance interpretation, and A single category is a concept of an agent’s ontology. Note ontology adaptation ( or online ontology alignment). that in this definition, a category is an extensional repre- sentation of a concept. Most of existing work on ontology Ontology assumes that the representation of a concept is intensional A partition of the domain O (see the previous section). description. Instance Given the above definition, we can identify two different An element o in the domain O: o ∈ O. ontology alignment problems: off-line ontology alignment and online ontology alignment. Most existing work belongs Production to off-line alignment, in which the entire specification for the When an agent plans to express some concept or category problem exists before the alignment is done. to other agents, it can use an instance belonging to that category to represent this concept2 . There might exist many nbe defined∗ as follows. Find The task of off-line alignment can instances that can be used to represent the concept. It is a categorization C ∗ such that i=1 M(C , Ci ) is minimal. possible that different instances have different priorities to The mis-alignment function M can be defined according to represent a same concept. the needs of application. Off-line alignment requires that an agent knows the ontology of other agents. Interpretation Given an instance, find the category of this instance. In this paper, we are concerned about online ontology align- ment problem, which is defined as follows. Design a mecha- n (t+1) (t+1) Adaptation nism or find a solution such that i,j=1 M(Ci , Cj )< When an agent receives an instance from another agent, it n (t) (t) M(Ci , Cj ) , where t means the time step. In i,j=1 may adapt its ontology such that its ontology would be more online mode, we don’t care about finding a global optimal compatible with the ontology of the sender. We will give a categorization such as C ∗ in off-line mode. Since the align- specification of some adaptation rules in the next section. ment process in this setting is dynamical, and thus the result 2 In fact, unless a set of agents already has a compatible and is adaptable as the situation changes. If we can work out verified shared ontology, it is difficult to see how they could a mechanism to satisfy the above inequality, it means all specify categories to each other in another way. 4. ONTOLOGY ALIGNMENT GAME on the learner’s side. If the learner’s response matches the We model the multi-agent mutual ontology alignment as an teacher’s, the update will be: ontology alignment game. The game is played repeatedly in  a (finite or infinite) sequence of rounds. On each round, the sT(o,o ) ← sT(o,o ) + α (1) following events happen: sL (o,o ) ← sL (o,o ) + α where α (0 ≤ α < 1) is called match update rate. When 1. Two agents are randomly chosen from the agent pop- α = 0, it means doing nothing. Teacher and learner can ulation. One is called the learner AL and the other take different α values. For simplicity, we assume that they is called the teacher AT . In fact, this terminology is take the same value. not completely accurate, since both agents will adapt their ontology in the same round, learning from each If the learner’s response doesn’t match the teacher’s, the other. However, there is a slight asymmetry because update will be: the teacher will initiate the process. Denote by CT  the teacher’s categorization or ontology, and by CL sT(o,o ) ← sT(o,o ) + β the learner’s one. (2) sL (o,o ) ← sL (o,o ) − β 2. The teacher randomly chooses a category c from its ontology CT , and then chooses an instance o ∈ c. where β (0 ≤ β < 1) is mismatch update rate. Similarly, when β = 0, it means doing nothing. Teacher and learner 3. The learner receives the instance o, and performs an can take different β values. For simplicity, we assume that interpretation, locating a category c ∈ CL such that they take the same value. o ∈ c . From c , the learner chooses a new object o from c which is different from the received one, and Note that both learner and teacher will update their matri- sends o back to the teacher to indicate that to the ces. The intuition behind the joint update is that neither learner’s knowledge c , o and o all belong to the same agent’s existing ontology is treated as the ideal reference. In concept or category. a sense, the learner has made a mistake because the teacher, too, has made a mistake: if the teacher’s ontology had been 4. The teacher tells the learner whether the instance o corrected with respect to the learner (i.e. identical to the actually does match the category c of the teacher or learner’s ontology), then the learner would not have made a not. If it matches, we say that the learner has made a mistake. The collection of agents is collaboratively design- correct interpretation on this round. ing an ontology that fits their mutual circumstances, rather than moving toward a pre-ordained one. 5. The learner takes certain actions (e.g., updating its ontology or doing nothing), after getting the feedback Ontology update from the teacher. The teacher also takes certain ac- Let an agent have a set of categories as its ontology: C = tions (e.g., updating its ontology or doing nothing) af- c1 ∪ · · · ∪ cn . The agent also has an association matrix S = ter sending the feedback to the learner. Below we de- (sij ). Initially, sij is set to: tail these actions and the decisions that lead to them.  1 if object oi and oj belong to the same category sij = 0 otherwise The goal of an agent in a learner’s role is to make as few mistakes as possible during the game. If possible, we would like all agents to converge to a shared ontology so that no The update of categorization C is done by using a variant interpretation mistakes will be made in the population. One of K-means clustering. The basic idea is as follows. For an good measure of success is the probability that any agent object o, compute the association strength between o and makes no mistakes of interpretation. each category ci , which can be defined as: 1  4.1 Ontology update AS(o, ci ) = s(o,o ) | ci |  In our model, we assume that each agent keeps an associ- o ∈ci ation matrix, which is used to capture relationships among For each object, assign it to a category which has the maxi- objects in the domain of interest. After each round of the mal association strength with this object. The (re)assignment alignment game, the association matrix might be updated to of object to a category may be repeated until some criterium reflect the new relationships among objects. Given a current is satisfied. In this paper, we only conduct once for object version of an agent’s ontology and a newly updated associ- assignment. ation matrix, a new version of ontology can be computed using a variant of K-means — a classical partition-based clustering method[3]. 5. SIMULATION We have constructed a simple simulation that represents Association matrix update this collective ontology alignment. To make things simple, Denote by sij or s(oi ,oj ) the association strength of the in- in this experiment, we consider only the categorization of stances pair (oi , oj ). Let sT(o,o ) be the association strength fixed number of categories3 . between the two objects o and o on the teacher’s side, 3 In fact, K-means clustering requires the number of clusters and sL(o,o ) be the association strength between o and o  be fixed in advance. 1 7. ACKNOWLEDGMENTS 0.8 This work was partially supported under NSF grant 9981- Average accuracy 0.6 797, and by the Information Systems Research Lab (ISRL) of the Graduate School of Library and Information Science. 0.4 We thank the reviewers for helpful comments. 0.2 0 5 10 15 20 25 30 35 40 45 50 8. REFERENCES Generation [1] R. Agrawal and R. Srikant. On integrating catalogs. In WWW2001, Hong Kong, May 2001. Figure 2: Simulation of ontology alignment game. [2] A. Doan, J. Madhavan, P. Domingos, and A. Halevy. Learning to map between ontologies on the semantic Figure 2 shows such a simulation of 2 agents in a domain con- web. In WWW2002, Honolulu, Hawaii, May 2002. taining 10 instances {0, 1, 2, · · · , 9} with 2 fixed categories. We set the two update rates as: α = β = 0.1. Each gener- [3] A. K. Jain and R. C. Dubes. Algorithms for Clustering ation contains 10 rounds of the ontology alignment game— Data. Prentice Hall, 1988. one for each agent as teacher with a random learner (though [4] M. S. Lacher and G. Groh. Facilitating the exchange of the selection of agents doesn’t make a large difference). The explicit knowledge through ontology mappings. In The average accuracy is the ratio of the total number of correct 14th International FLAIRS Conference, Key West, FL, interpretations over all rounds in the single generation to the 2001. AAAI Press. number of rounds in that generation (i.e., 10 in this case). As the figure shows, the collection of agents in this simula- [5] A. Maedche and S. Staab. Ontology learning for the tion converges to a perfect collective interpretation at about semantic web. IEEE Intelligent Systems, 16(2):72–79, 31 generations. March/April 2001. [6] N. F. Noy and M. A. Musen. Prompt: Algorithm and Table 1: The evolution of agents’ ontologies. tool for automated ontology merging and alignment. In AAAI/IAAI 2000, pages 450–455, Austin, TX, 2000. Initial ontologies of agents [7] J. Sowa. Knowledge Representation: Logical, agent 1 {0, 1, 2, 3, 4} {5, 6, 7, 8, 9} Philosophical, and Computational Foundations. agent 2 {0, 2, 4, 6, 8} {1, 3, 5, 7, 9} Brooks/Cole, Pacific Grove, CA, 2000. Shared ontologies after evolution agent 1 {0, 2, 4} {1, 3, 5, 6, 7, 8, 9} [8] L. Steels. The origins of ontologies and communication agent 2 {0, 2, 4} {1, 3, 5, 6, 7, 8, 9} conventions in multi-agent systems. Autonomous Agents and Multi-Agent Systems, 1(2):169–194, October 1998. Table 1 illustrates what the evolution result looks like. Af- ter the convergence, they share the same ontology. Ac- cording to the initial ontologies of two agents, we are able to figure out that there exist two optimal shared ontolo- gies4 : C = {0, 2, 4} ∪ {1, 3, 5, 6, 7, 8, 9} and C = {5, 7, 9} ∪ {0, 1, 2, 3, 4, 6, 8}. This simulation shows the first solution. In fact, with different random seed setting, another solution was also obtained in our experiment. 6. DISCUSSION AND CONCLUSION We have given the sketch of a formalized approach to a dy- namic process for mutual continuous co-alignment (actually a kind of collective design) of a group-wide ontology. At present we have no formal characterization of the specific conditions for collective convergence of this procedure, or proof of convergence in all cases. However, our simulation work indicates that there is a wide range of conditions un- der which convergence does occur, and we believe a more rigorous result can be built. Further development of this idea will include improving our understanding of these con- vergence conditions, as well as expanding our treatment to cover more forms of ontological representation with greater structural complexity. 4 Here, we define optimal shared ontology as the ontology which has the minimal mismatch with the initial ontologies of all agents.