=Paper=
{{Paper
|id=Vol-66/paper-16
|storemode=property
|title=Mutual Online Ontology Alignment
|pdfUrl=https://ceur-ws.org/Vol-66/oas02-22.pdf
|volume=Vol-66
|authors=Jun Wang and Les Gasser
}}
==Mutual Online Ontology Alignment==
https://ceur-ws.org/Vol-66/oas02-22.pdf
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.