"What ya going to have, Mac? Something to eat?" "Yeah. What kind of sandwiches ya got besides hamburgers and hot dogs?" "How about a ham'n cheese sandwich?" "Nah ...I guess I'll take a hamburger again." *** "Hey, that's no hamburger; that's a cheeseburger!" Charles O. Frakes, 1962 [7] The first requirement for a communication can be seen as the ability for two systems to send and receive signals. If two systems want to communicate, we assume that they will need more than sending and receiving random noises. This is where the key notion of meaning appears. Our two systems will need of course to exchange symbols, but also to agree that these symbols have -if not equal, at least compatible -meanings. A global agreement on the symbol-meaning associations from both systems leads to mutual intelligibility, while disagreements might cause you to eat something different than what you thought you ordered. How to reach such an agreement is the object of various fields of research that we can refer to by the term concept convergence.
Before addressing any issue in communicating systems, there should be a clear definition for each of the three key elements listed above: the symbol, the meaning and the nature of their relation.
A definition for the term symbol is given relatively to the notion of sign by Pierce: there are three kinds of sign -icons, indexes and symbols. A symbol is a sign that "denotes its object solely by virtue of the fact that it will be interpreted to do so": it possesses an abstract relation with its associated meanings, (for instance the words "poule", "pollo" and "chicken" do not share any physical connection with the animal that they represent). Symbols are the category of sign that we use in computer science.
Conversely, the term meaning is more tricky to define. There is a long story of debate within the field of philosophy of language over the meaning of meaning. However, Goldstone [8] simplifies them into two major branches: the conceptual web approach and the externally grounded concepts approach. The former approach considers that the meaning of a concept is given by its connections to other concepts [3] [6] [11] in a similar way as the early semiotic theories of Ferdinand De Saussure. In contrast, the last approach considers that a meaning has to be grounded. The term has been coined by Steven Harnard and its thought experiment of the Chinese room [9]. The conceptual web approach finds its foundation in the British empiricist movement and continues to influence science today, through the embodied cognition theory in cognitive sciences for instance.
With the diversity of approaches to give a definition of meaning, and often in contradiction with each other, it can be challenging for researchers to address formally an issue in communicating systems, especially if the research takes place in an interdisciplinary context that combine the two approaches. We do not intend to list the advantages and drawbacks of each approach, we rather intend to create a formalism that can be used in both.
While this formalism does not define the notion of meaning, it defines a set of other related notions that can help anyone to create a formalization of its custom notion of meaning -regardless to where this notion falls in the spectrum of possible approaches, between the conceptual web and the externally grounded concepts. Moreover, even if a scientific community decides to use a huge set of definitions for the notion of meaning, as long as they notions are defined in the same formalism it will be possible to compare them, and their related work.
Researchers from many fields including (but not limited to) Machine Learning, Ontology Matching or Multi-Agent Systems need to address a broad range of situations where two communicating systems, that we will refer to as agents from now on, do not agree on the meaning of their symbols. In order to clarify their problem and solution, they need a robust and domain independent formalism that provides clear definitions for notions including meaning, agreement on the meaning, concept etc.
We provide a formalism that defines these notions in a compatible way with respect to each other. While this formalism has been initially created in the context of symbolic inductive learning [2], it incorporates elements from semiotics and can be used with a large set of approaches. The formalism's inherent flexibility comes from three main points:
The formalism is designed for an interactive approach In most of ontological approaches, a third system -the oracle -will solve the disagreements on the meaning between two other agents by accessing the combined knowledge of both agents [5]. We designed a formalism that is able to work in an interactive way, where the two disagreeing agents are able to solve their disagreements by interacting with each other, without any help from a third part. While this allows the formalism to remain compatible with classical approaches of ontology matching, the growing interest from the research community in interactive approaches [4] allows this point to be a main feature of our formalism.
The formalism is designed for a lazy approach This formalism is designed to allow a lazy approach of resolving disagreements on the meaning: a disagreement can be solved on demand when it arises, without requiring an exhaustive analysis of both agent's symbols and meanings. For this reason, the formalism can represent a concept as itself, not only through all its relations with other concepts (external concepts approach). The exhaustive approach usually found in ontology matching (conceptual web) can also be formalized, due to the notion of contrast set which defines a set of concepts by their respective relations.
The formalism differentiates symbols and meanings The formalism establishes a strict distinction between the symbol and what it stands for, allowing the agents to clarify the notions of symbol, meaning, and these two notions' relations. This allows researchers to formalize models where the agents can dynamically modify the symbol of a concept without modifying the relations that the concept has with other concepts, in the case of a conceptual web approach.
The formalism uses the three basic components of semiotics from the semiotic triangle of Odgen and Richards [10], and draw a correspondence between the triangle's symbol, thought of reference and referent with respectively the sign, the generalizations and the examples more commonly used in machine learning (see Figure 1).
These three components are assembled into a concept, and concepts are assembled among containers. There are two kinds of containers: the contrast sets, that are used for communication by agents, and the hypotheses, that are not suitable for communication but useful during the process of building new contrast sets.
The semiotic element are the components of concepts and containers. The different elements that an agent has perceived in its environment are called examples -real world observations of objects. For example, a specific chair from an office is an example. They are noted e
The agents are using ψ-terms as their representation language. An agent represents an example e i using a feature-term. A generalization g j of a set of examples E i is an other feature-term that verifies ∀e i ∈ E i , g j e i . An intensional definition
A sign s i is an abstract entity that exists only in the communication between two agents. A concept C i = (s i , I i , E i ) is the triadic relation between a sign1 , an intensional definition and an extentional definition. The relation should verify: ∀e i ∈ E i , ∃g i ∈ I i as g i e i . If the concept C i belongs to an Agent A k , we note it C k i .
Containers are a dyadic relation between a context E and a set of concepts {C 1 , ...,C n }.
A hypothesis H = (E, {C 1 , ...,C n }) is a container such that the set of examples E 1 ∪ ... ∪ E n ⊆ E and where the signs of the concepts are different: ∀C i ,C j ∈ {C 1 , ...,C n }, i = j → s i = s j . We will note the context of the hypothesis E H .
A contrast set
0 and the signs of the concepts are different. K is a partition of E. We will note the context of the contrast set E K .
In multi-agent systems, agents are using their contrast sets to encode a meaning into a sign and decode signs into meanings. Understanding the conditions to mutual intelligibility between two agents requires to study the relations between the contrast sets they are using, A 1 .K for agent 1 and A −1 .K for agent 2. Since we aim to grant the agents with the ability to modify their contrast sets into A 1 .K and A −1 .K , the relation between an initial version A k .K of a contrast set and its latest version A k .K needs to be studied as well.
Agents always aim to set the contrast set they are using as intelligible for both of them: we refer at this aim as mutual intelligibility. Each agent is in charge of evaluating if a contrast set is intelligible for himself. The different criteria that an agent uses to evaluate whether or not a contrast set is intelligible from its point of view, are called the agreements.
The first criterion to the intelligibility, is to share the same signs for concepts with same extensional definitions, and different signs for concepts with different extensional definitions. In order to avoid ambiguity, the contrast sets still need to have the extensional definitions of its concepts disjoint. This criterion is the synchronic agreement, referring to the sub-field of linguistics that describes language at a specific point of time, by opposition to diachronic. The synchronic agreement can be formalized as
A second criteria reflects the expected trade-off between generalization and specialization among a contrast set. We want the agents to have concepts general enough to remain as far as possible from the extreme scenario of having one different concept by example. However at the same time, we want the agents to have concepts specific enough to remain as far as possible from the extreme scenario of having only one concept for all examples.
We consider here that agents initially start with contrast sets that were intelligible from their point-of-view. Therefore, we use there level of trade-off as the baseline for the expected generality and specialization of any new contrast set's concepts. However, if agents need to change their concepts in order to reach mutual intelligibility, they will have to make concessions either on the generality or the specialization of their concepts. Therefore, we have to make a choice between having more general or more specific concepts as the result of the changes.
Since the number of concepts among the contrast set is from far inferior to the number of examples in its context, the risk of having an over-generalized contrast set is more constraining than the risk of an over-specialized. For this reason, an agent can only give its agreement to a contrast set that is more specific than its initial one. It will be the role of the argumentation to limit the concepts' specialization. We call this criterion the diachronic agreement, in reference to linguistics where diachronic refers to the development and evolution of language through time. The diachronic agreement can be formalized as
Within a mutli-agent system, the success of a communication lies on multiple criteria that we present as agreements. Every contradiction to these criteria are seen as disagree- ments over these criteria. Since the criteria over one agent's agreement are now clear, it is possible to express which relations between concepts can contradict them. Since we have synchronic and diachronic agreements, we refer to their respective contradictions synchronic and diachronic disagreements. First, the synchronic agreement can be contradicted by two kinds of relations: relations between two concepts' signs, or relations between two concepts' extensional definitions.
The first kind of synchronic disagreement is related to the signs. If two concepts C k i ∈ A k .K and C −k j ∈ A −k .K have different signs but their extensional definitions are the same, situation that is formalized as (s i = s j ) ∧ (E i = E j ), the two concepts are in a relation of homonymy. However, if the two concepts have different sign but the same extensional definition, formalized as (s i = s j ) ∧ (E i = E j ), the concepts are in a relation of synonymy.
The second kind of synchronic disagreement is independent from the signs, and lies only on extensional definitions. If one of the two concepts' extensional definition is a proper subset of the other concept's extensional definition such that E i ⊂ E j , then the two concepts are in a hypo/hypernymy relation. The other possibility is that the two extensional definitions are overlapping onto each others such that
). This relation is referred by as an overlapping relation. The diacronic agreement can be contradicted in two ways. The first one is by having at least one concept from a contrast set that does not have its extensional definition included in the extensional definition of a concept from an anterior contrast set. The relation causing the disagreement is referred to as a confusion, and adopting the same notation as in section 3.1.2 about K and K , we formalize it as
The last contradiction arises when some examples from one contrast set's context is not present in a posterior contrast set's context. This particular case is not caused by a relation between concepts, but by a relation between contexts. It is noted E K ⊂ E K , and is referred by as the incompleteness relation.
The relations behind the diachronic disagreement are easily identifiable by one agent, since it possesses the two contrast sets with the incriminated relations. However, the case of the synchronic disagreement is more complicated. Since the relations causing this disagreement are between examples from different agent, and that agents are not necessary having the same examples in their contexts, the agents might not individually identify a disagreement that occurs when you consider the total set of examples present in both agents. This kind of disagreements is referred to as second order disagreements.
To detect and solve the second order disagreements with the elements of our protocol listed so far, the agents would need to transfer all their example to each other. Fortunately, by granting the agents the ability to communicate with each other about their point-of-view on the relation between two concepts, it is possible to overcome the requirement of an extensive example transfer. To do so, an agent has to receive all the pairs of signs and intensional definitions from the other agent's contrast set. When the agent A k received all the pairs from A −k .K, it can build a hypothesis H with the context E K of its contrast set and a concept C k j = (s j , I j , E j = {e ∈ E|∃g ∈ I j ∧ g e}) for each received pair (s j , I j ).
After building the hypothesis, A k can examine the relations between the concepts from its contrast set and the concepts from its hypothesis. These relations are referred to as the local relations. If A k has m concepts and A −k has n concepts, each agent has a set of m * n local relations. In order to standardize the communication, we allow the agents to express their relations through four different symbols. A relation r between the concepts C i and C j takes its value from the set {≡, , , ⊗} depending on the relation between the concepts' extensional definitions E i and E j as follow:
Set of all cats Set of all dogs
Set of all dogs
Set of all Reptilias (Birds) • r = if E i and E j are disjoint.
A k knows the local relation between each pair of concepts
By getting the local relation between C −k i and C −k j , A k can infer the overall relation between C k i and C −k j according to the following rule:
• case 0: if the two local relations are the same, the overall relation is also the same.
• case 1: if the local relations are
Since these relations are symmetrical, this set of rules covers any possible combination of relations. The overall relation is the relation that the two concepts C k i and
Case 1 Case 2
Case 4
The overall relation does not provide enough information yet to decide an agreement in all cases. The relation does not specify which concept includes the other in the overall relation. In order to resolve this ambiguity, the agents have to decide on a hierarchy between the concepts.
If we look at the vocabulary from section 3.2, we see that the case of a concept's extensional definition having the extensional definition of another concept as a subset is referred to as a hypo/hypernymy. This name comes from the field of linguistic: a hyponym shares a type-of relation with its hypernym, where the most general concept is the hypernym and the most specific is the hyponym. An example is the color navy-blue, that is a hyponym of blue. Deciding a hierarchy, in our case, means deciding which of the two concepts of the overall relation is the hyponym, and which one is the hypernym.
The hierarchy among the overall relation is deciding according to the following rules. There are five possibilities that leads to the relation as the overall relation between two concepts C k i and C −k j . In three of these possibilities, both local relations were already a relation:
i is the hyponym and C −k j the hypernym. In the last two possibilities, one of the local relation was not but ≡, as in case 2 of section 3.3:
• if E i ⊂ E j and E i ≡ E j , or E i ≡ E j and E i ⊂ E j , C k i is the hyponym and C −k j the hypernym.
• if E j ⊂ E i and E j ≡ E i , or E j ≡ E i and E j ⊂ E i , C −k j is the hyponym and C k i the hypernym.
These additions are not part of the core formalism, but can be still useful for researchers that face particular situations. Ambiguity of the Sign: Since sometimes the concepts C k i from A k .K and C −k j from A −k .K will be in a situation where i = j. In this situation, the concept C i from A K and the concept C j from A k .H can be both noted C k i or C k j . In order to remove this ambiguity, we will note C k j the concept that belongs to A k .H. This way, the apostrophe marks the belonging to a hypothesis. In the situation where i = j, the absence of ambiguity allows us to not put the apostrophe.
Co-hyponymy: In this Section, four notions from semiotics have been introduced to describe the semantic relation 3 between two concepts. These notions are: hyponymy, hypernymy, synonymy and homonymy. We add now a fifth notion, the co-hyponymy. A set of concepts C h 1 , ...,C h n are co-hyponyms of a common hypernym C H if the co-hyponyms' extensional definitions E h 1 , ..., E h n are a partition of the extensional definition of the hypernym's extensional definition E H .
The formalism is versatile and can be used in many of the fields cited in the introduction (Ontology Matching, Symbolic Inductive Learning, Semiotic ...). However, the real interest of the formalism lies in its compatibility with works that belong to a combination of these fields. The main feature of the formalism is its ability to formalize concepts of our language that we use to talk about language itself. This function of language, the reflexive function, can be confusing sometimes. Expressions like meaning of the meaning, or concept of concept are often useful to use in a research paper from one of the previously cited field, but confuses the reader. This problem is exacerbated in the case of interdisciplinary texts, where making a reference to which instance of a notion like concept is used may degrade the clarity of the text even more. By formalizing each of these terms together with their relations, we aim to improve the clarity of interdisciplinary research reports: for instance C refers to the formal notion of a concept while concept refers to the notion of concept in its broad meaning. The concept of concept is now noted C concept .
We do not provide a definition for the meaning. Since this notion is subjective and defined in different ways among different approaches, we prefer to let each user of the formalism choose the way that he/she considers the most appropriate to define the notion of meaning. Different ways to formalize the meaning of a concept C i include (but are not limited to):
• its intensional definition I i (dualism) • its extensional definition E i (materialism) • the concept C i itself, as the tuple {s i , I i , E i } (externally grounded concepts)
• the relation r of the concept C i with another concept C j (conceptual web)
The formalism has been used in an experiment where a pair of agents resolves simple scenarios of disagreements by arguing over the meaning of their concepts [1].
We presented an original formalism that can fit, but is not limited to, interdisciplinary approaches of communication. This formalism presents the basic elements sign, extensional definition and intensional definition, how their interaction forms a concept, how concepts are organized to partition a linguistic context, and finally how these organizations can cause disagreements on the meaning, what is the typology of these disagreements and how we can evaluate a good organization that results in an agreement, even from the point of view of an agent that has only partial information on the linguistic context of its interlocutor. We are looking forward to see how the research community will use this formalism to disambiguate abstract notions of our language.
Acknowledgements This paper has been partially supported by projects ESSENCE: Evolution of Shared Semantics in Computational Environments (ITN 607062).