The most prominent way to assess the quality of an ontology alignment is to compute its precision and recall with respect to another alignment taken as reference. These measures determine, respectively, the proportion of found mappings that belong to the reference alignment and the proportion of the reference alignment that was found. The use of these values has been criticised arguing that they fail to re ect important semantic aspects. In addition, they rely on the existence of a reference alignment. In this work we discuss the evaluation of alignments when they are used to facilitate communication between heterogeneous agents. We introduce the notion of pragmatic alignment to refer to the mappings that let agents understand each other, and we propose new versions of precision and recall that measure how useful mappings are for a particular interaction. We then discuss practical applications of these new measures and how they can be estimated dynamically by interacting agents.
Communication between heterogeneous agents has been identi ed as one
important application for ontology alignments [
In this paper we focus on the problem of using ontology alignments as
translators for agent communication, and particularly on their evaluation for that
application. We are interested in developing measures to decide whether an
alignment is useful for a particular interaction, that is, if using it will help agents
communicate. Traditionally, ontology alignments are evaluated with respect to a
human-crafted reference alignment, and accuracy measures count the elements
in the intersection between the evaluated alignment and the reference. In this
way, the precision of an alignment is de ned as the proportion of found
mappings that belong to the reference alignment, while the recall is the proportion
of the reference alignment that was found. We propose an application-dependent
evaluation technique that does not require the (possibly arbitrary) construction
of a gold standard. In this way, we make a step towards considering the problem
of \in situ evaluation", based on the idea that \the relative quality or usefulness
of a generated alignment also depends on its intended use" [
Our approach considers agents taking part in task-oriented interactions, and de nes a mapping as correct if it allows agents to nish the joint task successfully. This leads to the notion of useful and misleading mappings, which are, respectively, those that lead to the success or failure of an interaction. This new classi cation allows us to rede ne the traditional precision and recall measures that are used for alignment evaluation, comparing an alignment against the speci cation of an interaction, thus providing a method for evaluating alignments that does not rely on a human-built alignment. We then show how these newly de ned measures can be used by agents to improve the quality of their understanding, and sketch a method in which agents can estimate them online using their experience from interaction, making evaluation automatic. 2
The use of the standard precision and recall notions from information retrieval
for the evaluation of ontology alignments has been criticised by di erent authors,
all of whom argue that these measures ignore important aspects of the problem
that should also be taken into account to decide how good a solution is. The
main approach to creating measures that are more appropriated for the nature of
semantic mappings is the one of semantic precision and recall [
Also relevant are approaches that consider the use and evolution of
alignments in a multi-agent environment. Both [
We consider the problem of achieving meaningful communication between two agents a1 and a2 that need to interact to perform some task, but use potentially di erent vocabularies V1 and V2 respectively. Each agent can organise its vocabulary in its own way, using structures that go from simple lists of words to fully edged ontologies. We only suppose that they can be matched with one of the existing tools to obtain an alignment between them.
De nition 1. An alignment A between two vocabularies V1 and V2 is a nite set
of mappings between words in V1 and V2. A mapping is de ned as a quadruple
hv1; v2; n; ri, where v1 2 V1, v2 2 V2, n 2 (0; 1] is the degree of con dence on the
mapping, and r is the kind of relation that holds between words. An alignment
must contain at most one tuple for each pair v1 2 V1, v2 2 V2. [
When working with an alignment A, if a mapping hv1; v2; n; ri belongs to A we will write v1 r v2 (for example, v1 v2).
In general, techniques to build alignments between di erent vocabularies
make use of the structure or additional information in the ontologies in which
such vocabularies are organised. Other techniques use external resources, such
as text corpora or the web. Still others have a completely syntactic approach.
Extending the ideas in [
We specify interactions performed jointly by agents by means of interaction protocols that de ne all possible sequences of message exchanges. The multi-agent systems community has extensively discussed possible formalisms to describe these kind of protocols; in this work we stick to a generic approach that uses Finite State Automata. Since we focus on agents that communicate to perform a task together (for example, ordering drinks ), the interaction can end successfully (if the task is completed) or can fail (if it is not). To decide this outcome, we introduce the notion of state properties, which are Boolean predicates assigned to nal states to represent observations. Interactions are successful only if agents reach together nal states with the same properties.
De nition 2. Given two agents a1 and a2, a vocabulary V , and a set of state properties SP , an interaction model IM is de ned as a tuple hQ; q0; ; F; ; speaksi where Q is a nite set of states, q0 2 Q is the initial state, F Q is the set of nal states, : F ! P(SP ) assigns a subset of state properties to each nal state, speaks : Q ! fa1; a2g assigns to each state its sender agent, and : Q V ! Q is a partial function called the transition function.
Note that while we do not specify any particular turn-taking pattern, we do require that, for each state, all messages labelling transitions from this state share the same sender agent, who is determined with the speaks function. For simplicity reasons, we will consider that is unde ned for the nal states F .
In the rest of this paper, including all the de nitions, we consider interactions between two agents a1 and a2 with interaction models IMi = hQi; qi0; Fi; i; i; speaksii; i = 1; 2. While IM1 and IM2 have the same set of agents (fa1; a2g), their vocabularies and state properties can di er; we will call them V1; V2 and SP1; SP2 respectively. 3.2
Alignments between the vocabularies of two interaction models, that we will call pragmatic alignments, capture relations between the ways in which words are used in a conversation. In this way, a word v1 from IM1 matches with a word v2 from IM2 if an agent can interpret v1 as v2 in an interaction and nish the task successfully.
De nition 3. Consider IM1 and IM2 such that speaks(q10) = speaks(q20).
Extending [
With this construction, we can easily obtain all possible interactions between agents with two interaction models.
De nition 4. An interaction between two interaction models IM1, IM2 is an accepted string in the communication product IM between IM1 and IM2. An interaction is successful if it ends in a state q such that (q) = fsuccessg, it is unsuccessful if (q) = ff ailureg.
These interactions can be seen as all possible combinations of uttered messages and their interpretations; our objective is to use them to de ne pragmatic alignments. An immediate approach consists in considering two words as equivalent if they belong to a successful interaction. In an alignment of this kind, one word in V1 could be mapped to many words in V2 if they have di erent interpretations in di erent states. Instead, agents will be interested in knowing which mapping is correct for each state. This information can be obtained from successful interactions if we consider deterministic FSAs in which any accepted string can be assigned to an unique sequence of states. In the following de nition, mappings are parametrised by states in the communication product. De nition 5. A pragmatic alignment between interaction models IM1; IM2 is a set of tuples hq; v1; v2; ri, where q 2 Q; v1 2 V1; v2 2 V2, and r 2 f ; Gg.
The relation between two words ( or G) depends on whether nishing the interaction successfully is always possible after mapping them. To de ne formally their semantics, we will refer to each state in one of these accepted strings as hq; vi, representing the state and the message.
{ IM1; IM2 j= hhq1; q2i; v1; v2; i if there are interactions between IM1 and IM2 that include hhq1; q2i; hv1; v2ii, and all strings accepted by IM1 or IM2 that include hq1; v1i or hq2; v2i are the projection of one of these interactions (the interaction can always end successfully after mapping v1 with v2). { IM1; IM2 j= hhq1; q2i; v1; v2; Gi if there exists at least one successful interaction between IM1 and IM2 that includes hhq1; q2i; hv1; v2ii (the interaction can end successfully at least for some cases after mapping v1 with v2).
As an example, consider the interaction models in Figure 1, which represent fragments of interactions between a waiter (w) and a customer (c) to order drinks in English and Italian (state transitions should be read as (sender; receiver) : message.). Let IM1 have SP : fsize beer; kind beer; kind wineg, and IM2 have SP : fkind beer; kind wineg, and 1(3) = size beer, 1(4) = 2(3) = kind beer, 1(5) = 2(4) = kind wine. The mapping Wine Vino in h0; 0i is satis ed by IM1; IM2, because the interaction (a1 : hWine; Vinoi; a2 : hColor; Tipoi) is successful in the communication product, and all accepted strings in IM1 and IM2 that include mathsf W ine and mathsf V ino respectively are projections of it. The mapping Beer Birra in h0; 0i is not, because there is no interaction that projects (Beer; Size). However, Beer G Birra is satis ed, because (hBeer; Birrai; hVariety; Tipoi) is successful.
Pragmatic alignments are everything agents need to communicate successfully, but they are only useful in a particular context. Notice, for example, that mapping Tipo with Color is not correct in a general English-Italian translation; however in the context of ordering drinks it yields to common understanding. 4
The quality of a vocabulary alignment is typically measured in comparison with a reference alignment, for which values of precision and recall are computed. As 1 (w, c): Variety
4 (c, w): Wine 2 it is commonly done, we do not take into account the con dence degrees in these measures.
De nition 6. Given an alignment A, let A0 denote the set of mappings of A for which we have removed the con dence degree, i.e., A0 = fhv1; v2; ri j hv1; v2; n; ri 2 A for some ng. The precision of an alignment A with respect to a reference alignment B is the fraction of the mappings in A0 that are also in B0: precision(A; B) = j A0 \ B0 j
j A0 j recall (A; B) = j A0 \ B0 j j B0 j while its recall is the fraction of the mappings in B that were found by A:
Two problems arise when using these measures to assess the quality of an
alignment A used for agent interaction. First, a reference alignment between the
vocabularies may not be available. Second, even if it is, the measures do not
take into account the way in which terms are used in an interaction. To show
this, we performed a small experiment, based on the ones in [
In this section we propose adaptations of the traditional precision and recall measures that evaluate an alignment taking as reference, not a human-crafted standard, but a pragmatic alignment obtained from two interaction models. We introduce the notions of useful and misleading mappings for those that belong to successful and unsuccessful interactions respectively. In this rst approach we will only consider alignments with relations, the problem of analysing other relations is left for future work.
De nition 7. Consider an alignment A between vocabularies V1 and V2 and the already de ned interaction models IM1 and IM2. A mapping hv1; v2; n; i 2 A is useful with respect to IM1; IM2 if hv1; v2i appears in a successful interaction between IM1 and IM2. It is misleading if the same pair appears in an unsuccessful interaction between IM1 and IM2.
Notice that there can be mappings in A that are neither useful or misleading. We will call relevant to the mappings that can be classi ed in useful or misleading, or equivalently, those between pairs that belong to an interaction between the models. More surprisingly, a mapping can be both useful and misleading at the same time, if the relation in the pragmatic alignment is G. This allows for di erent possibilities when computing precision and recall. In this paper we consider as correct all useful alignments.
To de ne precision and recall for A with respect to IM1; IM2, let usef ul and relevant be, respectively, the sets of useful and relevant mappings of A with respect to the interaction models. Let Ap be the pragmatic alignment between IM1 and IM2, and let us de ne pragmatic = fhv1; v2; ri if hq; v1; v2; ri 2 Ap for some q 2 Qg. Pragmatic precision and recall are de ned as follows: recall =
j usef ul j j pragmatic j precision = j usef ul j
j relevant j
As argued in [
It is worth noting that, with these de nitions, possible values for pragmatic precision and recall are determined by the structure of interaction models. For example, consider a linear interaction model in which each state has only one outgoing arrow. There are no possible misleading matches with this protocol; therefore the minimum level of precision for alignments is necessarily 1. Consider the alignments presented in Table 1 applied to the ordering drinks scenario represented by the protocols in Figure 3. According to an English-Italian dictionary, they would both have precision 0:5 (Wine Vino and Red Rosso are correct). Depending on the way of using the dictionary, Media Half Pint could also be considered correct, giving the second alignment a precision of 0.75. However, they are clearly not equally useful when used by agents interacting, because the second alignment has a misleading mapping Media Half Pint. Using our values, both alignments have a recall of 0:2 (Wine Vino, Red Rosso are the useful alignments found), but the rst one has a precision of 1 and the second one of 0.66.
Alignment 1 v1 2 V1 Bibita Vino
Rosso Quantita v2 2 V2 Water Wine Red Pint
Alignment 2 v1 2 V1 Bibita Vino Rosso Media v2 2 V2 Water Wine
Red
Half Pint
In their pragmatic version, precision and recall are not only indicators of how
useful an alignment is for a particular interaction, but can also be actively used
by semantically heterogeneous agents to improve their mutual understanding.
Methods to learn pragmatic alignments and to transform traditional alignments
into pragmatic ones can be obtained by adapting the techniques developed in [
Consider an agent a1 with interaction model IM1 and an alignment A. When receiving v2 in state q1 2 Q1, a1 needs to decide how to interpret it, or which outgoing arrow from q1 to follow. Let U (q1) be the set of all these possible interpretations. For each v1 2 U (q1), a1 computes the value of the mapping as: V(v1; v2) = n if hv1; v2; n; i 2 A 0 otherwise let V^(v1; v2) be the normalized values for v1 2 U (q1), and consider an exploration parameter 2 [0; 1]. The criterion consists in choosing v1 2 U (q) with probability: p(v1) =
V^(v1; v2) + (1 )
A reasonable question is how to choose a good value of . It is easy to see that the values that give better results in terms of rate of successful interactions depend on the pragmatic precision of A with respect to IM1 and the protocol IM2 of the agent a1 interacts with. If precision is high, agents should trust more on the alignment, if it is low they should rely more on the random exploration.
To show this, we performed a short experiment, in which we analyse the rate of success of interactions between agents that use di erent values of and have alignments of di erent qualities. We used the customer and waiter agents from the example in Section 4.1 and let them interact for 150 times, measuring in how many cases they succeeded. As a simpli cation, we used only alignments that had the same values of precision and recall; this should be extended in future work to consider more realistic values. We de ned three alignment quality levels: low (precision and recall 0.2), medium (precision and recall 0.5) and a high (precision and recall 0.8) quality. Figure 4 shows the results. As expected, when the alignment is good with respect to the interaction, best results are obtained with a high , while for bad alignments it is better to make random choices. For medium quality, there is almost no di erence, since the probability of a mapping being correct is similar to the one of choosing randomly the right option. Although pragmatic precision and recall can be useful in practice, in most applications it is not realistic to expect agents to know them beforehand. In what follows we discuss how agents can use the experience of interaction to automatically estimate the values of precision and recall of an alignment. This would be useful not only to improve their behaviour as explained before, but also to evaluate alignments in a dynamic, distributed way.
Let us rst focus on estimating recall. In this case, agents can simply use the proportion of the mappings they made in successful interactions that were already in A.
recallest = j mappings in successful interactions \ A j
j mappings in successful interactions j
precisionest = j mappings in successful interactions \ A j
j relevant mappings seen j
However, this considers as incorrect all the relevant mappings that were not part of successful interactions. This can sub-estimate the precision, particularly in the rst steps, when an estimation is needed most.
Alternatively, we propose to use a learning strategy that estimates gradually
the precision of A by analysing which of the mappings that were made are likely
to be correct and which ones are not. A possibility is to use a technique proposed
in [
To estimate precision, let increased be the set of all the mappings made that are in A and for which the calculated con dence is greater or equal to the one in A. Precision can then be estimated as: precisionest =
j increased \ A j j relevant mappings seen j
This can improve the precision estimation in early stages, since mappings that are likely to be correct (because many good mappings were found after them) would still increase their value. These are preliminary ideas, that we plan to further develop and evaluate experimentally in future work. 6
We consider the ideas presented in this paper to be a rst step towards the development of ontology alignment tools that are particularly designed for agent interaction. These tools would require novel reasoning techniques that take into account contextual information about the tasks that are being performed to build mappings of high pragmatic precision and recall. To this aim, a rst technical requirement is the formalisation of a language that allows to express properties of the domain together with information about the interaction. To apply the ideas we propose here, it may be necessary to adapt them to more complex descriptions of interactions, or to incomplete ones.