The problem of aligning vocabularies has been identified as particularly relevant in the context of dynamic and open environments such as multi-agent systems [5]. Participants in this kind of systems have different backgrounds and may therefore not share the same vocabulary, making alignments necessary to interact meaningfully with each other. This problem has been considered in the past decades from two perspectives. Some approaches [9,4] assume the existence of external elements, such as physical objects, that all agents perceive in common, and explore how those can be used to explain the meaning of words. A second group of techniques [7,8] provide explicit ways of learning or agreeing on an alignment, such as argumentation techniques, explanations, or definitions. These techniques always require agents to share a meta-language. The question of how to communicate with heterogeneous interlocutors when neither a physical context nor a meta-language are available remains practically unexplored.
In recent work [1,2,3] we proposed a novel approach to the problem of multi-agent vocabulary heterogeneity. In our techniques, that we call interaction-based, the alignment is performed considering only the context given by the interactions in which agents engage. In this work we assume the interacting agents share the knowledge of how to perform a task, or, more concretely, the specification of an interaction. As an example, consider an ordering drinks interaction between an English speaking customer and an Italian waiter. Since the agents share the dynamics of the conversation they will, for example, both know that the waiter will ask for the colour if wine is ordered. However, the words used by each agent can be different (vino and colore instead of wine and colour).
In previous work, we developed techniques that agents can use to learn progressively, from the experience of interacting, which mappings lead to successful interactions. After several dialogues, agents learn an alignment that they can use to order and deliver drinks with that particular interlocutor.
An important restriction that we (until now) imposed on agents is that they have to share the entire structure of the interactions they perform. This means that they need to agree on exactly how each interaction should be performed, modulo an alignment. This is a reasonable decision considering that our goal was to study how agents can learn alignments from shared interaction specifications. However, it is in practice a strong restriction, and it always raises the question of what agents can learn if the protocol is not completely shared. Our answer was that if the differences are small, they will be ignored by the learning methods, which work statistically. If, instead, there are significant differences, agents have nothing to learn, since there is no alignment that is useful to perform the tasks together. However, we have never performed a systematic analysis of how these differences affect the learning process.
In this paper we present an extension to the problem we studied in previous work, that considers the case when agents do not share the complete alignment. To this aim, we present a new kind of interaction specifications, based on the LTL constraint protocols that we used in [3]. These new protocols include a weight for each interaction rule, introducing a meaningful way to include differences between specifications. We provide an adaptation of our learning techniques to these protocols, and a way of measuring the quality of an alignment. These ideas can be seen from two points of views. One is to consider agents that use unrelated protocols, and to analyse how the techniques can find the alignment that minimize the punishment. Alternatively, we can suppose agents use protocols that have a shared portion and then diverge in some local rules, and use the method to find the alignment for the common part. In section 4 we present preliminary experiments for these two applications.
In this section we summarize the approach that we proposed in [3] to let agents infer alignments from the experience of interacting. We consider two agents a 1 and a 2 that have different vocabularies V 1 and V 2 respectively. Agents interact repeatedly using, for each interaction, the specification defined in a protocol. In this work we used open specifications consisting of rules that constrain what can be said without specifying completely the flow of the interaction. We chose to use a reduced version of the ConDec protocols [6], which define the constraints in linear temporal logic (LTL).
To define the protocols formally, let a vocabulary V be a set of words and consider a pair of agent IDs A = {a 1 , a 2 }. The set of messages M V,A is the set of all tuples a i , v where v ∈ V and i ∈ {1, 2}. An interaction protocol over V and A is a tuple M V,A ,C , where C is a set of constraints on how messages can be uttered. Constraints are LTL sen-tences renamed conveniently, that are shown in Table 2 1 . In this table, n ∈ N, a, b ∈ M V,A , and ♦, , d are the LTL operators that mean eventually, globally and next respectively. These constraints are generally divided into two classes. Existential constraints (absence) predicate over how many times a message can be uttered, while relational constraints describe binary relations between two utterances. In a protocol M V,A ,C , the constraints C needs to be a subset of the possible constraints over M V,A .
During an interaction, a 1 and a 2 have protocols
respectively, and each agents send messages to its interlocutor respecting the constraints in its protocol. As an example, consider again the ordering drinks scenario where the waiter w speaks Italian and the customer c speaks English. In this situation, agents could be using the following the following two protocols P w and P c , where w is the waiter and c is the customer. P w = {premise( w, da bere , c, birra ), premise( w, da bere , c, vino ), !response( c, birra , w, colore ), imm a f ter( c, vino , w, colore )} P c = {premise( w,to drink , c, beer ), premise( w,to drink , c, wine ), !response( c, beer , w, color ), imm a f ter( c, wine , w, color )}
A sequence of messages is called an interaction. We say an interaction is possible for a protocol if it does not violate any of its constraints, or, more formally, if it is an LTL-model of each of its constraints.
As we mentioned, until now we required agents to share the complete structure of the protocols they use for an interaction. To formalize this restriction, we defined the notion of compatibility between protocols. Intuitively, two protocols are compatible if the interactions that are possible for each protocol are equivalent under an alignment. Given two vocabularies V 1 and V 2 , an alignment from
An interaction in vocabulary V 2 can be translated to an interaction in V 1 using α if all its messages are in the domain of the alignment, by translating each word.
and let Int(P i ) be the set of possible interactions in V i . P 1 and P 2 are compatible if there exists a partial function α :
If we know the alignment α for which the condition holds, we can say they are compatible under α.
Since agents send messages composed of their own words, when they receive a foreign message they need to interpret it in their local vocabulary to continue the interaction. The objective of the learning techniques we propose in [3] is to infer the alignment α under which the protocols are compatible, something that would allow agents to interpret correctly the messages they receive.
The approach we present for learning alignments from interactions is simple. From now on we will use the point of view of a 1 , but everything is analogous for its interlocutor. The agent maintains a confidence distribution ω :
that assigns a value to each mapping between a known foreign word (V 2 ⊆ V 2 ) and a word in their vocabulary. These values are updated according to what agents observe in interactions. We present here only the simplest one of the methods we proposed in [3]. Briefly, when an agent receives a word, it punishes all interpretations that are not possible because they violate some constraint. Suppose a 1 receives v 2 after observing interaction i, and let r be a punishment parameter and i . m the operation of appending a message m to i. The update is described in Eq. (1).
For example, if the customer receives colore right after saying wine, it infers that it cannot mean to drink. By interacting repeatedly with different protocols, agents gradually learn an alignment between their vocabularies.
We now propose an approach that considers more carefully the question of to what extent agents can align their vocabularies when their protocols are different. To this aim, we introduce flexible protocols, in which each constraint has a weight that represents a punishment received when that constraint is violated. This punishment can be interpreted, for example, as a way of expressing preferences (heavier constraints are those that agents prefer not to violate), or degrees of confidence on a constraint, when there is uncertainty about the interaction context. Definition 2 A flexible protocol P f over a vocabulary V and a set of agents A is a tuple M V,A ,C f . The set C f is composed of pairs c, ρ , where c is one of the constraints in Table 2 over M V,A , and ρ ∈ [0, 1].
As an example, consider again the ordering drinks scenario. Assume they have the same constraints as before with high weight, but now the waiter also believes that the customer should not order two different alcoholic beverages in one interaction. This constraint, however, is less strict than the others, since the waiter is willing to accept that behaviour some times. The protocols would look as follows.
P w = { premise( w, da bere , c, birra ), 1 , premise( w, da bere , c, vino ), 1 , !response( c, birra , w, colore ), 1 , imm a f ter( c, vino , w, colore ), 1 , !correlation( c, vino , c, birra ), 0.5 } P c = { premise( w,to drink , c, beer ), 1 , premise( w,to drink , c, wine ), 1 , !response( c, beer , w, color ), 1 , imm a f ter( c, wine , w, color ), 1 }
The core contribution of our previous work consists in the learning techniques that we proposed to update the agent's mapping confidence distribution. In rigid protocols the objective of the learning is to find a correct alignment α under which the protocols were compatible. In [3] we show how, to that aim, it is enough to consider whether a word is a possible interpretation for a received message. The notion of compatibility cannot be applied to a flexible protocol, since the question of whether an interaction is possible is not meaningful anymore. When interacting with a flexible protocol, any sequence of messages can be accepted, but at some cost. This implies that there is no reference alignment α that agents can use to understand each other completely. Instead, each alignment will have an expected punishment that will make it better or worse. The goal now is to find an alignment that optimizes the punishment that is received while interacting.
To do so, agents need to take into account the weight of the rules that would be violated for each interpretation. We propose only one simple approach, that combines the punishment that would be received in a particular moment as well as the information that the agent already had.
As in the rigid cae, agents that use flexible protocols have a confidence distribution ω that assigns a value to each possible mapping. Consider again agents a 1 , a 2 with flexible protocols P f j = M V i ,A ,C f j for j ∈ {1, 2}. Suppose a 1 receives a word v 2 from a 2 after interaction i. For a word v ∈ V 1 , let B(v, P f 1 ) be the set of all constraints c included in a tuple in C f 1 such that the interaction obtained by appending a 1 , v to i violates c, but i does not. Let ρ(P f , c) be the weight of constraint c in P f . Then, for each v ∈ V 1 , and for each br ∈ B(v, P f 1 ), agent a 1 iteratively updates:
After all updates are done, the values are normalized to make ∑ v∈V 1 (ω(v 2 , v)) = 1.
An important question to address before adapting our techniques to the flexible case is the one of when an alignment is good for these new protocols. In the rigid case we measured the quality of an alignment by computing its distance to the reference alignment α, using the standard precision and recall measures. In flexible protocols, where the objective is to minimize the received punishment, a quality measure should reflect how much agents would pay when using them.
We propose a method that evaluates a pair of alignments for a given pair of protocols. Alignments are evaluated in pairs, and not by themselves, because the punishment that an agent receives depends on how its interlocutor interprets the words it utters. The objective is, therefore, to measure how well they would interact together if using the obtained alignments.
Our objective will be to measure the quality of the alignments that agents learn during with our techniques. Since agents have only confidence distributions, we first need to explain how to obtain an alignemnt from them. For simplicity, in this explanation we will assume that these alignments are, for agent a 1 , a partial function α 1 : V 2 → V 1 . This alignment maps each foreign word known by the agent with the local word for which the mapping value ω is maximal. In practice, agents frequently do not have enough information to distinguish between possible mappings, so there are many of them with maximal value. Therefore the alignment is actually a function α 1 : V 2 → P V 1 , where P S is the set of all subsets of a set S. To adapt the measure we present now to this kind of alignments it is only necessary to consider α 1 and its analogue for a 2 , α 2 , as a set of possible alignments, and compute the measure for each combination.
The straightforward way to compute the expected punishment for a pair of protocols and a pair of alignments consists in obtaining all interactions, filtering the ones that could actually occur in an interaction, and computing the average of the received punishment for them. Even if the interactions have bounded length, this method is computationally very expensive, since the amount of interaction grows exponentially with the length. Fortunately, for our particular set of constraints, it is enough to consider only the punishment received by interactions of length 2 to have a measure of the alignment's quality. This is because the constraints are unary or binary, so any violation that could happen would also occur in an interaction of length 2. In future work we plan to investigate in more depth the relation between the measure computed in this way and the actual expected punishment for longer interactions.
We consider only interactions that could be uttered, and discard all sequences of messages that would never occur in a real exchange. These impossible interactions are the ones in which an agent sends an utterance that causes an unnecessary punishment. The notion of utterable interactions is defined over abstract interactions. These are sequences that are actually said before any interpretation, where the messages uttered by a 1 have words in V 1 and the ones by a 2 have words in V 2 .
Definition 3 A two-message abstract interaction i = [ a j , w , a j , w ], for j ∈ {1, 2} is utterable for alignments α 1 , α 2 and protocols P 1 and P 2 if:
• [ a j , w ] does not violate any constraint in P j and • α j (i) does not violate more constraints for P j than α j ([ a j , w ]) does.
We will call U P 1 ,P 2 ,α 1 ,α 2 to the set of all utterable sentences for those protocols and alignments. Next we need to define the punishment for an interaction with a given alignment and protocol.
The punishment for an interaction i and a protocol P (noted ρ(P, i)) is the added weight of all constraints that are violated by i in P.
The quality of alignments α 1 , α 2 for P 1 , P 2 is:
This quality measure is bilateral and measures the amount paid by two agents. It can also be made unilateral by only considering the punishment for one protocol, but it will still depend on both alignments. Note also that we defined the measure for a case in which all words have the same likelihood of being uttered, but it can be easily adapted for other cases. If we know the probability of uttering a given word, to take it into account in the measure it is enough to multiply the punishment for an interaction i ∈ U P 1 ,P 2 ,α 1 ,α 2 by the likelihood of i. The extension is not so simple when agents have more complicated distributions to choose an utterance, such as one in which the likelihood of sending a message depends on the previous interaction.
Flexible protocols, along with the updating technique that we proposed, can be analysed from two points of view. First, we can consider agents that have structurally different protocols for the same task, without requiring any a priori relation between them. In this case, the technique can be used as a tool to find an alignment that minimizes the punishment received by agents for that specific protocol. This can also be used for small sets of protocols.
A second point of view considers flexible protocols as local variations of a common compatible part. In this case we study how the technique lets agents find the correct alignment (the one that is useful for the common par) in spite of the differences. In the following sections we explain the experiments that we performed to study these two cases.
In this set of experiments we analysed how our method can be used by agents that have different protocols, without any similarity assumption. The objective of the interacting agents is to find the alignment that would make them pay as little as possible. For each experiment we created a pair of flexible protocols, gave one to each agent, and let them interact for some time, observing the alignment that they obtained in the end. To decide the quality of the alignments, we used two different measures:
1. The real punishment received by agents when they used the alignment 2. The quality of the alignments with respect to the protocols measured as explained in Section 3.2
Since we proposed the alignment quality measure as an expected value of the punishment received by agents, our hypothesis is that the curves obtained with it are similar to the ones that show the average received punishment. However, the distance measure only considers the expected punishment for interactions of length 2. Since agents use longer interactions, the value of the real punishment will be larger.
An experiment consists of two agents, each of them with a vocabulary and a protocol over it. In this preliminary experimentation the size of the vocabularies is of 4 words. We performed experiments with different protocol sizes and total weight (obtained by adding up the weight for each constraint). Concretely, we used protocols with 6 and 8 rules, and total weight 3.0 and 5.0. In each experiment, both protocols have the same number of constraints and the same added weight. In an experiment, we let agents go through a learning phase in which they interacted n times, performing the experiment for n = [0, 2,5,10,15,20,30]. During these alignments they updated their confidence distributions on mappings. All interactions were of length 6. After this training phase, we ran a test phase of 20 interactions, during which agents did not learn new information. Instead, they interpreted foreign words using the alignments obtained in the previous phase. For the second measure, we added the total punishment that agents received during the test phase. We repeated the experimentation 10 times, for 10 different protocols. Figure 1 shows the results obtained for each experiment. We can see that with more training, agents find alignments that are better according to the measure, and that let them interact receiving lower punishment. The distance measure seems to change in the same way as the actual received punishment, which indicates it is a good estimate. We would need a larger set of experiments to answer some interesting questions that are not reflected in this data, such as the relative importance of the amount of constraints and the total weight.
The objective of the second type of experiments is to analuze the learning techniques when applied by agents with protocols that diverge in some degree from a shared compatible part. To build these kind of protocols, we used four parameters:
r s : the number of shared constraints r d : the number of different constraints w s : the total weight for shared constraints w d : the total weight for different constraints We started from two vocabularies V 1 and V 2 and an alignment α between them, and created two protocols with r s constraints that were compatible under α. This was the shared part. We distributed the weight w s over those constraints (to simplify the experimentation, we did this uniformly). Then, we added r d different constraints to each protocol, and distributed the weight w d between them (not necessarily uniformly).
In each experiment, we let agents interact 100 times with different pairs of protocols, and measured when (and if) they converged to α. It is important to make one comment here. In our previous work, it was enough to consider that agents had found α when their learned alignments were equivalent to it. This is because in rigid protocols, using α would always lead to correct interactions. This is not the case any more, since agents could receive punishments even using α, that could made them change the alignment. For this reason, we considered an agent had converged when after they had spent 15 interactions without changing the alignment (but we recorded the number where they first got to α, before those 15 interactions). The results can be seen in Figure 2. We performed the experiment 10 times, with different protocols. The figure shows the number of experiments after each amount of interactions. We used r d = {0, 1, 2} and w d = {0.0, 0.5, 1.0, 1.5, 2.0}. Some combinations were not performed, because the weight was impossible to distribute in the amount of rules. We see how more and more heavy different constraints imply more difficulty to find α. We also observe an unexpected effect. Even with the same weight, more constraints slow down the convergence. We think this is because of how agents choose which word to utter. Now, they only utter words that do not violate any rule, so they are more restricted, which could make interactions finish in failure earlier, or could make all interactions very similar between them. Another thing to comment is that the difference between small weights cannot be seen correctly in these experiments (for example, see the case od rd = 2, wd = 0.0 vs rd = 2, wd = 0.5). We plan to study this effect more exhaustively in the future, with a larger set of experiments.
To have a deeper comprehension of how these techniques work, they should be compared to the performance of the original learning methods for rigid protocols, when used for protocols that have some diverging constraints. In this way, we would be able to detect if taking into account explicitly the weight of different constraints is better than considering them as noise.
We introduced a new kind of protocols that allow us to investigate the problem of vocabulary alignment for agents that do not share exactly the same procedural knowledge of the tasks they perform together. This can mean either that they have unrelated specifications, or that they share a common part that has a significant number of constraints and another portion differs. The technique that we propose to learn alignments in this case is a simple adaptation of the one we had introduced in previous work, and is useful for both situations.
This work is still in a preliminary state, but we see it as a basis to many extensions. First of all, the experimental part needs to be improved, considering larger protocols and making a more accurate analysis. The current experiments should only be seen as preliminary tests that give an idea of how the method works and provide input for future experimentation. For example, in the first experiment it is possible to consider the optimality of the solution the agents find, something that would be useful to understand how the technique works. In addition to this, there are different questions to consider regarding the technique. We think it would be particularly interesting to consider interactions between agents with different kinds of preferences. For example, what kind of alignment would a pair of agents reach if one of them has very high preference values and the other one very low?