Ontology matching is currently a key technology to achieve the semantic alignment of ontological entities used by knowledge-based applications, and therefore to enable their interoperability in distributed environments such as multi-agent systems. Most ontology matching mechanisms, however, assume matching prior integration and rely on semantics that has been coded a priori in concept hierarchies or external sources. We present a formal model for a semantic alignment procedure that incrementally aligns differing conceptualisations of two or more agents relative to their respective perception of the environment or domain they are acting in. It hence makes the situation in which the alignment occurs explicit in the model. We resort to Channel Theory to carry out the formalisation.
An ontology is commonly defined as a specification of the conceptualisation of a particular domain. It
fixes the vocabulary used by knowledge engineers to denote concepts and their relations, and it constrains
the interpretation of this vocabulary to the meaning originally intended by knowledge engineers. As such,
ontologies have been widely adopted also in multi-agent systems. Ontology matching is commonly defined
as the process that computes the semantic relationships between entities of separate ontologies. With the
proliferation of ontologies used in multi-agent systems caused by different conceptualisations of even the
same domain —and their subsequent specification using varying terminology— ontology matching is now
seen as a necessary technology to achieve semantic alignment and to enable interoperability of separately
engineered knowledge-based agents [
Until recently, most ontology matching mechanisms developed so far have taken a classical functional
approach to the semantic heterogeneity problem, in which ontology matching is seen as a process taking
two or more ontologies as input and producing a semantic alignment of ontological entities as output [
Certainly, there exist efforts to efficiently match ontological entities at run-time, taking only those
ontology fragment that are necessary for the task at hand [
We claim that semantic alignment is ultimately relative to the particular situation in which it is carried out and that this situation should be made explicit and brought into the ontology matching mechanism. Even two systems with identical conceptualisation capabilities and using exactly the same vocabulary to specify their respective conceptualisations may fail to interoperate because of their differing perception of the domain. Imagine a situation in which two agents are facing each other on a checker board. Agent A1 may conceptualise a figure on the board as situated on the “left”, while agent A2 may conceptualise the same figure as situated on the “right”. Although the conceptualisation of “left” and “right” is done in exactly in the same manner by both agents, they still will need to align their respective vocabularies if they want to successfully communicate to each other actions that move figures on the checker board. Their semantic alignment, however, will only be valid in the scope of their communication within this particular situation or environment. The same agents situated differently may lead to a different alignment.
This scenario is reminiscent to those in which a group of distributed agents adapt to form an ontology
and a shared lexicon in an emergent, bottom-up manner, with only local interactions and no central control
authority [
Let us consider two agents A1 and A2 situated in an environment E.2 We associate a numerable set S of
states to E and, at any given instant, we suppose E to be in one of these states. We further assume that each
agent is able to observe the environment and has its own perception of it. This ability is faithfully captured
by a surjective function seei : S → Pi, where i ∈ {1, 2}. According to Channel Theory, information is only
viable where there is a systematic way of classifying some range of things as being this way or that. This
idea is captured in the notion of classification:
Definition 1 ([
For each agent Ai, i ∈ {1, 2}, we consider a classification Ai that models Ai’s viewpoint of E. First, tok(Ai) is composed of Ai’s perceptions of E states, that is, tok(Ai) = Pi. Second, typ(Ai) comprises the syntactic entities by which Ai describes its perceptions, the ones constituting the ontology of Ai. Finally, |=Ai synthesizes how Ai relates its perceptions with these syntactic entities.
Now, in order to associate the environment E with a classification E we choose the power classification of S as E. which is the classification whose set of types is 2S , whose tokens are the elements of S, and for which a is of type α if a ∈ α. The reason for taking the power classification is because, in general, there is no global conceptualisation of the environment and hence there are no sytactic entities that may play the role of types for E. However, the set of types of the power classification includes all possible token configurations potentially described by types. Thus tok(E) = S, typ(E) = 2S and e |=E ε iff e ∈ ε.
1We do not assume any knowledge of Channel Theory; we restate basic definitions and theorems in this paper, but any detailed exposition of the theory is outside the scope of this paper.
2The generalization to any numerable set of agents is straightforward.
In Channel Theory, the information flow between the components of a distributed system is modelled
in terms of a channel. The relationships between the components are expressed via infomorphisms which
provide a way of moving information between them:
Definition 2 ([
fˇ(b) |=A α iff b |=B fˆ(α) for each token b ∈ tok(B) and each type α ∈ typ(A).3 We omit the superscripts of informorphisms if no confusion arises. Types are usually denoted by greek letters and tokens by latin letters so f (α) ≡ fˆ(α) and f (a) ≡ fˇ(a).
Definition 3 ([
typ(C) sssfˆs1sssss9 eKKKKKfKˆ2KKK typ(A1) |=C typ(A2) |=A1
yss tok(A1)
tok(C) |=A2 sssfsˇ1sss KKKfˇK2KKKKK% tok(A2) The information flow of our scenario is accurately described by the channel E = {fi : Ai → E}i∈{1,2} defined as follows: • fˆi(α) = {e ∈ tok(E) | seei(e) |=Ai α} for each α ∈ typ(E), • fˇi(e) = seei(e) for each e ∈ tok(E), where i ∈ {1, 2}. The fundamental property of the infomorphisms is fulfilled indeed: fˇi(e) |=Ai α seei(e) |=Ai α e ∈ fˆi(α) e |=E fˆi(α) {by definition of fˇi} {by definition of fˆi} {by definition of |=E} In this way, E is the core of the channel E and a state e ∈ tok(E) connects the agents’ perceptions fˇ1(e) and fˇ2(e).
A1
E }f}1}}}}}}> `AAAAAAfA2A
A2
Example. This example is taken from [
3Strictly speaking, an infomorphism f comprehends on the one hand a pair of classifications hA, Bi and on the other hand a contravariant pair of functions hfˆ, fˇi defined as above.
4Actually, this is the definition of a binary channel. A channel can be defined with an arbitrary index set as well as a distributed system can have an arbitrary number of components.
The magic box Mr.2's viewpoint With respect to our approach, the magic box will play the role of E and M r.1 and M r.2 will be the agents. The states of E are the possible configurations of the box so a state e can be represented as a 3 × 2 binary matrix (eij ). In this way:
S = ( 1 0 ! Intuitively, the state 1 0 , for instance, means that there are only two balls in the box, 0 0 one in the left up sector and another in the left centered sector. Notice that M r.1 sees a ball on the left if there is a ball in at least one of the sectors of the left column of the box and sees a ball on the right provided that there is ball in at least one of the sectors of the right column. Then M r.1’s perceptions of the states of E can be represented as two-dimensional binary vectors, and the function see1 can be defined formally as follows: see1(e) = (0 0)
(1 0) (0 1) (1 1) if if if if e = where e ∈ S. The function see2 can be defined analogously on three-dimensional binary vectors as representations of M r.2’s perceptions. Note that M r.1 has the notions of a ball being on the left or on the right and so has M r.2, but this last one has also the notion of a ball being in the center. After these considerations, A1 is defined by: • • • tok(A1) = (1 1), (1 0), (0 1), (0 0) • typ(A1) = {left, right} (v1 v2) |=A1 left iff (v1 v2) |=A1 right iff • typ(A2) = {left, center, right} (v1 v2 v3) |=A2 left (v1 v2 v3) |=A2 center (v1 v2 v3) |=A2 right • tok(A2) = (1 1 1), (1 1 0), (1 0 1), (0 1 1), (1 0 0), (0 1 0), (0 0 1), (0 0 0) Finally, a channel E = {fi : Ai → E}i∈{1,2} as defined above explains the information flow of this scenario. In the previous subsection, we have shown how channel E explains the information flow of our scenario. Now, we want to relate the agents’ syntactic entities, i.e., the agents’ types, and obtain meaningful relationships justified by E .
In Channel Theory, the sum operation gives us a way of putting the two components of a channel C = {fi : Ai → C}i∈{1,2} together into a single classification A1 + A2 (see Definition 4), and the infomorphisms together into a single infomorphism f = f1 + f2 (see Proposition 1).
Definition 4 ([
Proposition 1 ([
uuufu1uuuu
uu: CO dIII
f
PROOF: We just give the definition of f (see [
Note that typ(A1 + A2) is the disjoint union of typ(A1) and typ(A2). We attach importance to take the disjoint union because A1 and A2 could use some identical types in order to describe their perceptions of E (for instance, in the Magic Box example, left and right are both M r.1’s types and M r.2’s types). Therefore, A1 + A2 is the place where we should look for relationships between agents’ types. Moreover, as we will see f = f1 + f2 is of use to find meaningful relationships justified by E .
Channel Theory provides a way to make these relationships explicit in a logical fashion by means of
“theories” and “local logics”:
Definition 5 ([
When it comes to writing constraints of a theory T = hΣ, `i, we will use the usual notational conventions. For example, we write α ` β, γ instead of {α} ` {β, γ} and Γ, Γ0 ` Δ, α instead of Γ∪Γ0 ` Δ∪{α}.
A theory is regular if it satisfies the properties Identity, Weakening and Global Cut (see [
The notion of local logic puts a classification and a theory together but with an important added twist. In order to model reasonable but unsound inferences, the notion of‘ “normal token” is introduced.
5That is, fi = f ◦ σi, i.e., fˆi = fˆ◦ σˆi and fˇi = σˇi ◦ fˇ, for i ∈ {1, 2}.
Definition 7 ([
The local logic generated by a classification is sound and complete. Furthermore, given a classification A
and a local logic L on A, L is sound and complete if and only if L = Log(A) (see [
Now, let us return to our scenario modeled by E . Log(E ) explains the relationships between the agents’ viewpoints of the environment. On the one hand, T h(Log(E )) contains the most meaningful relationships between agents’ types according to the channel E . On the other hand, NLog(E) contains those pairs of agents’ perceptions connected together by the environment state of which they come from.
uuufu1uuuu uu: EO dIII
f
A1
Log(E ) is complete since Log(E) is complete but it is not necessarily sound because although Log(E) is
sound, f = f1 + f2 is not token surjective in general (see [
NLog(E) = {hfˇ1(e), fˇ2(e)i | e ∈ tok(E)} ⊆ tok(A1 + A2) If Log(E ) is also sound then Log(E ) = Log(A1 + A2), as we comment above. It means that there is no meaningful compatibility between agents’ viewpoints of the environment according to E . It is just the fact that Log(E ) is unsound what allows a meaningful compatibility between the agents’ viewpoints. This compatibility relation is expressed at the type level in terms of constraints by T h(Log(E )) and at the token level in terms of pairs of tokens by NLog(E).
Example. Following the previous example, Log(E ) includes among its constraints: h1, lefti `Log(E) h2, lefti, h2, centeri, h2, righti h1, righti `Log(E) h2, lefti, h2, centeri, h2, righti Let us check the first constraint (the second one can be verified in a similar way). We have to prove:
fˆ(h1, lefti) `Log(E) fˆ(h2, lefti), fˆ(h2, centeri), fˆ(h2, righti) Let e = (eij ) ∈ tok(E) and assume that e |=E fˆ(h1, lefti). Then e ∈ fˆ(h1, lefti), that is, see1(e) |=A1 left. Therefore e11 + e21 + e31 ≥ 1 and we can assure that there exists i ∈ {1, 2, 3} such that ei1 = 1. Hence ei1 + ei2 ≥ 1. If i = 3 then e |=E fˆ(h2, lefti), if i = 2 then e |=E fˆ(h2, centeri) and if i = 1 then e |=E fˆ(h2, righti).
The necessary and sufficient conditions for a token ha1, a2i of A1 + A2 being normal are the following: if a1 6= (0 0) then a2 6= (0 0 0) if a2 6= (0 0 0) then a1 6= (0 0) 3
We have stated that T h(Log(E )) contains the most meaningful relations between agents’ types. The problem is that neither agent can make use of this theory because they do not know the channel E completely. We present a method by which agents obtain approximations to T h(Log(E )). These approximations gradually become more reliable as the method is applied.
A1 and A2 communicate by exchanging information about their perceptions of the environment states. This information is expressed in terms of their own classification relations. Specifically, if E is in a concrete state e, we assume that agents can convey to each other which types are satisfied by their respective perceptions of e and which are not. This exchange generates a channel C = {fi : Ai → C}i∈{1,2}. Furthermore, T h(C) provides the logical relationships between the agents’ types justified by the fact that agents have observed e. If E turns to another state e0 and agents proceed as before, another channel C0 = {fi0 : Ai → C0}i∈{1,2} gives account of the new situation. The significant point is that C0 refines C (see Definition 11). Theorem 1 ensures that the refined channel involves more reliable information.
The communication ends when agents have observed all the environment states. Again this situation can be modeled by a channel, call it C∗ = {fi∗ : Ai → C∗}i∈{1,2}. Theorem 2 states that T h(C∗) = T h(Log(E )).
Definition 11 ([
Theorem 1 Let C = {fi : Ai → C}i∈{1,2} and C0 = {fi0 : Ai → C0}i∈{1,2} be two channels. If C0 is a refinement of C then: 1. T h(Log(C0)) ⊆ T h(Log(C)) PROOF: Since C0 is a refinement of C then there exists a refinement infomorphism r from C0 to C. Let us write A = A1 + A2, f = f1 + f2 and f 0 = f10 + f20 .
1. Let Γ and Δ be subsets of typ(A) and assume that Γ `Log(C0) Δ, which means fˆ0[Γ] `C0 fˆ0[Δ]. We have to prove Γ `Log(C) Δ, or equivalently, fˆ[Γ] `C fˆ[Δ]. We proceed by reductio ad absurdum. Suppose c ∈ tok(C) does not satisfy the sequent hfˆ[Γ], fˆ[Δ]i. Then c |=C fˆ(γ) for all γ ∈ Γ and c 6|=C fˆ(δ) for all δ ∈ Δ. Let us choose an arbitrary γ ∈ Γ. We have that γ = hi, αi for some α ∈ typ(Ai) and i ∈ {1, 2}. Thus fˆ(γ) = fˆ(hi, αi) = fˆi(α) = rˆ ◦ fˆi0(α) = rˆ(fˆi0(α)). Therefore: c |=C fˆ(γ) c |=C rˆ(fˆi0(α)) rˇ(c) |=D fˆi0(α) rˇ(c) |=D fˆ0(hi, αi) rˇ(c) |=D fˆ0(γ) Consequently, rˇ(c) |=C fˆ0(γ) for all γ ∈ Γ. Since fˆ0[Γ] `C0 fˆ0[Δ] then there exists δ∗ ∈ Δ such that rˇ(c) |=C0 fˆ0(δ∗). A sequence of equivalences similar to the above one justifies c |=C fˆ(δ∗), contradicting that c is a counterexample to hfˆ[Γ], fˆ[Δ]i. Hence Γ `Log(C) Δ as we wanted to prove. 2. Let ha1, a2i ∈ tok(A) and assume ha1, a2i ∈ NLog(C). Therefore, there exists c token in C such that ha1, a2i = fˇ(c). Then we have ai = fˇi(c) = fi0 ◦ rˇ(c) = fˇi0(rˇ(c)), for i ∈ {1, 2}. Hence ˇ ha1, a2i = fˇ0(rˇ(c)) and ha1, a2i ∈ NLog(C0). Consequently, NLog(C0) ⊇ NLog(C) which concludes the proof.
We assume that typ(Ai) is finite for i ∈ {1, 2} and S is infinite numerable, though the finite case can be treated in a similar form. We also choose an infinite numerable set of symbols {cn | n ∈ N}6.
Agent communication starts from the observation of E. Let us suppose that E is in state e1 ∈ S = tok(E). A1’s perception of e1 is f1(e1) and A2’s perception of e1 is f2(e1). We take for granted that A1 can communicate A2 those properties that are and are not satisfied by f1(e1) according to its classification A1. So can A2 do. Since both typ(A1) and typ(A2) are finite, this process eventually finishes. After this communication a channel C1 = {fi1 : Ai → C1}i=1,2 arises.
A1 {f{1{1{{{{{= C1 aCCCCCfC2C1C
A2 On the one hand, C1 is defined by: tok(C1) = {c1}, typ(C1) = typ(A1 + A2) and c1 |=C1 hi, αi if fi(e1) |=Ai α, for α ∈ typ(Ai) and i ∈ {1, 2}. On the other hand, fi1(α) = hi, αi and fi1(c1) = fi(e1), for α ∈ typ(Ai) and i ∈ {1, 2}. Clearly, f11 and f21 are infomorphims.
Note in this case both agents know C1. Hence they can compute separately T h(C1) = htyp(C1), `C1 i. This theory represents the logical relationships between the agents’ types justified by the fact that agents have observed e1.
Now, let us assume that E turns to a new state e2. Agents can proceed as above exchanging this time information about their perceptions of e2. Therefore, another channel C2 = {fi2 : Ai → C2}i∈{1,2} comes up. First of all, C2 is defined by: tok(C2) = {c1, c2}, typ(C2) = typ(A1 + A2) and for 1 ≤ k ≤ 2, ck |=C2 hi, αi if fi(ek) |=Ai α, for all α ∈ typ(Ai) and i ∈ {1, 2}. Second, fi2(α) = hi, αi and fi2(ck) = fi(ek) again for 1 ≤ k ≤ 2, α ∈ typ(Ai) and i ∈ {1, 2}. f12 and f22 are infomorphims by definition. The theory T h(C2) = htyp(C2), `C2 i represents the logical relationships between the agents’ types justified by the fact that agents have observed e1 and e2. The significant point is that C2 is a refinement of C1:
A1
= C2 |f1|2 |||| | | f11 / C1 o
aBB f 1 B f2
BB 2B
B B f21
A2 It is easy to prove that f 1 defined as the identity function on types and the inclusion function on tokens is a refinement infomorphism. By Theorem 1, C2 constraints are more reliable than C1 constraints. 6We write these symbols with superindexes because we limit the use of subindexes for what concerns to agents.
Example. Let us assume that the environment changes to the state e2 = perception of e2 is (1 1) and A2’s perception of e2 is (1 1 0). In this case: h1, lefti `C2 h2, centeri but h1, lefti 0C2 h2, righti
In the general situation, once the states e1, e2, . . . , en have been observed and a new state en+1 appears, the channel Cn+1 = {fin+1 : Ai → Cn+1}i∈{1,2} informs about agents communication up to this moment. First, tok(Cn+1) = {c1, c2, . . . , cn+1}, typ(Cn+1) = typ(A1 + A2) and for each 1 ≤ k ≤ n + 1, ck |=Cn+1 hi, αi if fi(ek) |=Ai α, for all α ∈ typ(Ai) and i ∈ {1, 2}. Second, fin+1(α) = hi, αi and fin+1(ck) = fˇi(ek) for 1 ≤ k ≤ n + 1, α ∈ typ(Ai) and i ∈ {1, 2}. Clearly, f1n+1 and f2n+1 are infomorphims. The theory T h(Cn+1) = htyp(Cn+1), `Cn+1 i represents the logical relationships between the agents’ types justified by the fact that agents have observed e1, . . . , en, en+1. Also Cn+1 is a refinement of Cn. f n defined as the identity function on types and the inclusion function on tokens is a refinement infomorphism. By Theorem 1, Cn+1 constraints are more reliable than Cn constraints.
Remember we have assumed that S is infinite numerable. It is therefore unpractical to let communication finish when all environment states have been observed by A1 and A2. At that point, the family of channels {Cn}n∈N would inform of all the communication stages. It is therefore up to the agents to decide when to stop communicating should a good enough approximation have been reached for the purposes of their respective tasks. But the study of possible termination criteria is outside the scope of this paper and left for future work. From a theoretical point of view, however, we can consider the channel C∗ = {fi : Ai → C∗}i∈{1,2} which informs of the end of the communication after observing all environment states. C∗ is defined as follows: tok(C∗) = {cn | n ∈ N}, typ(C∗) = typ(A1 + A2) and for n ∈ N, cn |=C∗ hi, αi if fi(en) |=Ai α, for all α ∈ typ(Ai) and i ∈ {1, 2}. In addition, fi∗(α) = hi, αi and fi∗(cn) = fi(en) for n ∈ N, α ∈ typ(Ai) and i ∈ {1, 2}. By definition, f1∗ and f2∗ are infomorphims.
Theorem 2 below is the cornerstone of the theory exposed in this paper. In short, it ensures that at each communication stage agents obtain a theory that approximates the most meaningful relationships between their types: Theorem 2 The following statements hold:
2. T h(Log(E )) = T h(C∗).
PROOF: 1. It is easy to prove that for each n ∈ N, gn defined as the identity function on types and the inclusion function on tokens is a refinement infomorphism from C∗ to Cn. 2. It follows directly from: cn |=C∗ hi, αi fˇi(en) |=Ai α en |=E fˆi(α) en |=E fˆ(hi, αi) {by definition of |=C∗ } {because fi is infomorphim} {by definition of fˆ} 4
In this paper we have exposed a formal model of semantic alignment as a sequence of information-channel
refinements that are relative to the particular states of the environment in which two agents communicate and
align their respective conceptualisations of these states. Before us, Kent [
This work is supported under the UPIC project, sponsored by Spain’s Ministry of Education and Science under grant number TIN2004-07461-C02- 02 and under the OpenKnowledge Specific Targeted Research Project (STREP), sponsored by the European Commission under contract number FP6-027253. M. Schorlemmer is also supported by a Ramo´n y Cajal Research Fellowship from Spain’s Ministry of Education and Science, partially funded by the European Social Fund.