1 0BIntroduction
A language game is a process of finding agreement on the meaning of words by agents in a system. It was introduced by Wittgenstein [1] as a concept for mapping an object reality to a language, where a speaker utters a word and associates it with an object that he or she points at so the hearer is able to infer the object. This game is a communication function. If the inferred object matches the intended object of the speaker, the game is considered successful, otherwise, the game fails. The game is repeated until agreement is reached. The goal is to create effective communication, reduce word ambiguity and word variability, and increase the number of successful games.
To deal with two major concerns, i.e. ambiguity and variability [2], we propose a new model of how agents share knowledge in a society of multiple hearers and employ norms or cultural knowledge mutually shared by all agents. With this new approach, the knowledge obtained from a joint agreement between direct agents (multiple hearers) and indirect agents (cultural knowledge extracted from social intentions) form the base for an agent's decision. At the initial state, each agent has its own prototype language, i.e. an innate conceptual structure with no belief about word-object pairings. Individual conceptual structures are modeled using self-organizing maps (SOMs) [3]. While the agents play the game, they learn from each other using joint attention to enable associative Hebbian-based learning on topical data. They must determine to which degree they believe their own beliefs compared to the set of standard beliefs, consisting of the other agents' and the culture's beliefs.
Steels [4] has explored the language game as a tool for finding agreement on word-object pairs in a repertoire of meaning structures and later-formed syntactic structures. However, the tool's syntactic structures are not as complex as those found in human languages. The Chomskyan approach was used in [5] to achieve language complexity in the form of innate static abstractions since everyone having a similar innate structure will make communication easier in a community than everyone having different types of structures. The nativist paradigm argues that cognitive skill is unique to humans and that it is encoded in our genome. For these reasons, we created an innate conceptual structure. The initial prototype constructs a similar conceptual space in every agent and uses it for language acquisition.
Recent studies have investigated the use of multiple hearers [6] and multiple parties [7-9] where one party may eavesdrop on the conversation of other parties. This approach simulates agents simultaneously playing two roles, both speaker and hearer. In real life, however, knowledge-sharing for speaking with meaning and listening with understanding also comes from social gatherings [10,11], i.e. cultural knowledge, so individuals are able to adjust their beliefs like a form of social introspection. Moreover, a specific knowledge domain was used to promote desirable knowledge or to reduce searching in undesirable knowledge. This can give the game system a better capability to reach desirable words more quickly. For this reason, we included a cultural algorithm [12] for simulating the social process of maintaining the norms of a community and thus reducing ambiguity and variability.
This article is divided into five sections. In the following section, we present our proposed observational language game model, which is composed of three belief levels: individual belief, social belief, and cultural belief. These beliefs have mutual interactions among each other. In the third section, we discuss our evaluation of the game using four measurements: coherence, specificity, word size, and success rate. In the fourth section, we simulate a number of language games and present results under various conditions. In the final section, we summarize the study and discuss further research.
2 Proposed Method
2.1 Language Game
There are three types of language games: observational, guessing and selfish language games. In an observational game, both the speaker and the hearer know the topics in advance with some degree of belief in the pairings between lexicon and objects. After the game ends, they both know the success of communication and adjust their beliefs accordingly. In a guessing game, the speaker utters a word along with some context of the topic, which is shown indirectly to the hearer. The hearer must guess what topic the word uttered by the speaker refers to. At the end of game the speaker gives corrective feedback. A selfish game is similar to the guessing game, but at the end of the game the speaker doesn't give any feedback about whether the hearer guessed correct or not. Vogt and Coumans [13] concluded that observational games and guessing games are faster than selfish games. In this research, we propose an observational game with multiple hearers.
The proposed language game algorithm can be described as follows:
- 1. The speaker is chosen randomly from a group of agents and assigned the role as speaker. A number of agents (60% of the remaining agents for example) are randomly chosen as hearers.
- 2. The topics are initially generated and chosen randomly in the game.
- 3. The speaker searches for a word in his or her belief space (SOM), i.e. the node that best matches the topic. This node is called the best-matching unit or BMU.
- 4. If no word is found, the speaker looks at the cultural memory; the searching process selects the best match in the cultural memory. If it cannot be found, the speaker searches in its neighborhood nodes; this situation may produce a polysemy lexicon, which is natural in human languages. If there is still no word found, the speaker will generate a new word and keeps this word, mapping it as the BMU for the topic. Finally, the speaker utters this word to the hearers.
- 5. The hearers search this topic in their memory in the same fashion as the speaker. However, they integrate three levels of belief: individual belief, social belief, and cultural belief.
- 6. When the hearers receive a word from the speaker, they search their individual memories. If the number of hearers who find the same word is higher than a pre-specified percentage, for example 50% of the hearers, the game accepts the uttered word of the speaker and the game is considered successful. The unknown hearers update their beliefs, adding that word to their own BMUs.
- 7. If the sixth step fails, the hearers keep searching in the neighboring nodes in their memories. Doing this also creates polysemy. If the number of hearers finding the word is more than the pre-specified number, the game is considered successful and the unknown hearers update their beliefs. Otherwise, the game is unsuccessful.
- 8. If the seventh step fails, the hearers keep searching in all the nodes. If the number of hearers who find the word reaches the pre-set number of hearers, the unknowing hearers update their knowledge following the knowing hearers, in which case the game is considered successful. Otherwise the game is unsuccessful. In a successful game, both speaker and hearers increase their belief counters by one. In a failed game only the speaker decreases his belief counter by one. The maximum belief is set at 20 and the minimum belief is set at zero.
2.2 Conceptual Space Structure
The structure of the conceptual space is based on Gardenfors [14], who models a conceptual space as a geometrical structure instead of creating a symbolic or associationism model. With a self-organizing map (SOM), the space can be formed by a set of quality dimensions. In addition, in this research the space can be generated from knowledge sharing among multiple hearers and social knowledge. According to Gardenfors, knowledge representation in cognitive science has three levels: symbolic, conceptual, and sub-conceptual. On the symbolic level, a language is a simple kind of representation through which humans understand each other. For mapping the geometrical structure at the conceptual level, a self-organizing map is applied. The SOM keeps input data in a space at nodes containing vectors of a red/green/blue color or a set of quality dimensions. Each node includes an array of concepts and each concept holds a single word associated with a degree of belief. The nodes are connected in a map that represents the sub-conceptual level. Thus, using the SOM represents knowledge at all three levels.
To create a conceptual structure, each agent needs to formulate an innate conceptual structure. The prototypes of 10 colors (grey, blue, green, aquamarine, red, pink, yellow, white, azure, and brown) are defined to create the innate conceptual structure. The larger the number of prototypes, the more complex the knowledge will be. The innate concept is trained with the prototypes only at the initial state, before game playing. The SOM forms a conceptual space that is a repository of the physical world for internal cognition of the agent. A conceptual space using an SOM with two-dimensional nodes is shown in Figure 1.
The agent maintains a degree of belief in the association between the lexicon (symbolic level) and the conceptual space. The conceptual space has three quality dimensions (red, green and blue). It holds the physical world (the colors) associated with the conceptual space.
Figure 1 Conceptual space structure.
Within the concept, a concept class consists of a pair of a lexicon and a belief. The concept's belief property is an integer between 1 and 20. In a successful game, the belief will be increased by one, with a maximum of 20. In an unsuccessful game, the belief is decreased by one, with a minimum of zero.
2.3 Lexicon in Nodes
The word generation process uses all English characters (a-z). A word has a length of two to six characters, interleaving consonants and vowels, i.e. "CABAKI". Word generation is performed by the speaker. Figure 2 shows examples of words generated by a speaker on an SOM.
Figure 2 Possible words on an SOM.
The SOM consists of 14 x 14 nodes in order to reduce computational resources while still being sufficient to generate suitable words in simulated communication.
2.4 Proposed Searching Strategy for Words in Conceptual Spaces and Cultural Repository
After the SOM is trained 1,000 times with random prototypes, a random topic, i.e. a color vector, is shown to the speaker and the hearers. The process of searching for the best words is performed at four levels: searching in the best node, the cultural repository, the neighboring nodes, and all the nodes. The speaker searches first in the best mapping unit (BMU) in his or her SOM. This node may contain many concepts. Each concept stores a word associated with the word's beliefs (see Figure 1). Only the best belief is selected. Remember that the degree of belief is defined by a counter; each time the game succeeds, the counter is increased by one.
Initially, there are no BMUs, so the speaker searches in the cultural repository, which is maintained as a hash collection. If the speaker finds the mapping node in this collection, he or she keeps this word and associates it with the node. However, the word may not be found in the cultural repository; the speaker will then search for a word in its neighboring nodes within radius R. For effective communication, the radius is set at one or two neighbors [15]. If the speaker cannot find any word in the neighboring nodes, he or she will search all nodes in the map. If it then still cannot find an exisiting word, a new word is generated and mapped as the BMU and finally uttered to the hearers.
The topic that was shown to the speaker is also shown to the hearers. The hearers perform searching in a similar way as the speaker does, except that they do not look at the cultural memory. Therefore, the hearers' searching process has only three stages: search among its BMUs, search in neighboring nodes, and search in all nodes. Moreover, at each state, the number of agents who find the word is pre-specified. If the number of hearers is greater than this value, the game is considered successful and the word is spread to all hearers who did not find a word. If the hearers cannot find a word in any state, the game is unsuccessful, but the hearers must add the speaker's word to their BMUs and the speaker decreases his or her belief counter by one for this word. In case of a successful game, the speaker and hearers increase their belief counters for that word by one.
2.5 Cultural Knowledge Construction and Maintenance
Evolutionary computation (EC) [12] is the origin of the cultural algorithm (CA). EC has been successfully used for searching and optimization to solve many diverse problems. However, EC uses one level of evolution to gather knowledge from a population, while CA, as shown in Figure 3, includes a higher level of evolution, which is the cultural level. CA promotes desirable knowledge by allowing individuals to vote for acceptable knowledge to be stored in the belief space through an acceptance function and the voted knowledge is used to update the cultural belief space by an adjust function. This belief space is used as a guideline or a norm that everyone agrees with for individual actions. This guideline is defined as an influence function. There is an influence or a feedback to control the individual. At each step, the belief space will be more specific. The population space evolves via selection for reproduction and by mutation for self-adaptation.
Figure 3 The general framework of a cultural algorithm.
To apply CA to language games, the agents are the population, which is the primary source of knowledge (or normative knowledge), holding the population spaces, while the secondary knowledge (or cultural space) holds the cultural
beliefs. The cultural algorithms in language games can be defined as following in Eq. (1):
CA = \{P, V, B, f, Accept, Adjust, Influence\} (1)
where P is the population of players (agents), V is a variate function, B is the cultural (belief) space, f is the performance function representing the problem-solving experience of individuals, Accept is the acceptance function, Adjust is the adjust function that adjusts or updates the belief space, and Influence is the influence function that is used to influence the variation function. In our proposed language game, the population in the games is not maintained, thus the selection operation is not applied. The proposed pseudo code of CA for language games is shown in Figure 4.
Begin Game<sup>t</sup>=0; Initialize P<sup>t</sup> Initialize B<sup>t</sup> while (condition is true) Evaluate(P(COH<sup>t</sup>, SPE<sup>t</sup>)); Adjust(B<sup>t</sup>, Accept(P<sup>t</sup>)); Variate(P<sup>t</sup>, Influence (B<sup>t</sup>)); Game<sup>t</sup> = Game<sup>t</sup> + 1; \nend End
Figure 4 Cultural algorithm for language games.
The language games start at game 0 (\(Game^t\)). The agents are generated (\(P^t\)) with empty belief and the cultural space \((B^i)\) is also empty. When a game begins, the agents' knowledge is evaluated with a performance function that computes two fitness measures: coherence \((COH^{i})\) and specificity \((SPE^{i})\). The results of these evaluations are determined by the acceptance function \((Accept(P^t))\). The agents' knowledge with the best fitness is considered acceptable and is promoted to the cultural space with the adjust function \((Adjust(B^t, Accept(P^t)))\). The adjust function uses the acceptable knowledge to update the cultural space, which is shared by the population. The new belief space has an influence on agents' beliefs via the influence function (\(Influence(B^t)\)). As described earlier, the speaker selects a word from the cultural belief only if no word is found among its BMUs. Thus, the selected word from the cultural space that is mapped to the topic has an influence on the population. A hearer will accept the knowledge or adjust his or her belief with the variate function, i.e. a guided variation [16]. At each step of the game play, the two sources of knowledge are updated. The cultural space and the individual's normative knowledge are recalculated.
Consequently, the language games promote the specific knowledge in the cultural space and create agreements among agents.
3 Experimental Evaluation
To evaluate the proposed language game, four measurements were utilized: coherence, specificity, word size, and success rate. The first two measurements were adopted from De Jong [17]. Word size is calculated at the end of each game and the success rate is calculated every 10 games through sliding windows.
3.1 Coherence
A concept can occasionally be conveyed by more than one word, i.e. synonymy, as shown in Figure 5. This is typical in human languages.
Figure 5 A concept is represented by more than one word.
Table 1 shows concepts in each agent and their coherence. The black circles indicate words agreed upon with other agents. Concept 1 is represented by two different words (WI and W2). To calculate the coherence of an agent \(coh(A_i)\), we sum the number of agreed words and divide it by the total number of concepts, as shown in the following Eq. (2):
\[coh(A_i) = \frac{W_c}{\sum_{i=0}^n A} \tag{2}\] where \(W_c\) is the number of agreed upon words (black circle), and A is the total number of concepts in the games.
| Agent | Concept 1 | Concept 2 | Concept 3 | Concept 4 | Coherence |
|---|---|---|---|---|---|
| Agent1 | W1 ● | W3 ● | W4 ● | W6 ● | 1 |
| Agent2 | W1 ● | W3 ● | W5 | W7 | 0.5 |
| Agent3 | W2 | W3 ● | W4 ● | W6 ● | 0.75 |
| Agent4 | W1 ● | W3 ● | W4 ● | W7 | 0.75 |
| Frequency | 3 | 4 | 3 | 2 | |
| Coherence | 0.75 | 1 | 0.75 | 0.5 |
Table 1 Coherence calculation.
3.2 Specificity
In some cases, one word may convey more than one meaning or concept. This can cause ambiguity. Figure 6 shows that concepts 1 and 2 (C1, C2) are associated with word 1 (W1) causing a polysemy, but a polysemy doesn't occur when concept 3 (C3) refers to word 2 (W2) and concept 4 (C4) refers to word 3 (W3).
Figure 6 One word may represent more than one concept.
To measure ambiguity, the specificity of an agent \(spec(A_i)\) can be calculated as follows in Eq. (3):
\[spec(A_i) = \frac{n_s^2 - \sum_{k=1}^{n_s} f_k}{n_s^2 - n_s}\] (3)
where \(n_s\) is the number of concepts and \(f_k\) is the frequency of words related to concept k. This formula specifies the degree of polysemy. Specificity decreases if two meanings refer to the same word. The higher the specificity, the less polysemy there is. Table 2 discusses how to calculate the specificity. When Agent 1 has two concepts (Concept 1 and 2) referring to the same word (W1), Concepts 3 and 4 have a single reference since they each refer to different words, W2 and W3, respectively.
Table 2 Specificity calculation.
| Agent | Concept 1 | Concept 2 | Concept 3 | Concept 4 | \(\sum\)f | Specificity |
|---|---|---|---|---|---|---|
| Agent1 | 2 | 2 | 1 | 1 | 6 | 0.833 |
| Agent2 | 1 | 3 | 3 | 3 | 10 | 0.5 |
| Agent3 | 1 | 1 | 1 | 1 | 4 | 1 |
To select a word for a concept while an agent has more than one word associated with it, the selected word is the one with the highest values of coherence and specificity. Word ambiguity is seen as coherence in some papers [6,18].
3.3 Word Size
Word size considers all words from both successful and unsuccessful games in the agents' conceptual memories. It can be calculated as follows in Eq. (4):
\[word_{size} = \sum_{i=0}^{n} node \left( \sum_{j=0}^{m} concept_{j} \right)_{i}\] (4)
where m is the number of concepts in a node and n is the number of nodes on the map. A smaller value for word size can indicate that communication is more effective than when word size is larger.
3.4 Success Rate
The success rate is calculated after the hearers finish searching for words after every 10 games, calculated as a moving average. The success rate is calculated as follows:
\[succ_{rate} = \frac{1}{m} \sum_{i=0}^{m} \left( \frac{1}{n} \sum_{j=t-n+1}^{t} x_j \right)_i\] (5)
where \(x_j\) is the number of successful communications evaluated after every 10 games, n is the number of sliding windows, m is the total number of agents, and t is the number of games. The success rate indicates the effectiveness of the communication.
4 Results
In this section we analyze the comparative performance between a single and multiple hearers, the effects of the number of agents in the games, the effects of the number of hearers, and finally the effectiveness of including cultural knowledge in the game.
4.1 Performance of Using One Single Hearer and Multiple Hearers
We first compared the system's performance of using one single hearer and multiple hearers on four measures: coherence, specificity, success rate, and word size. Figure 7 shows the coherence and specificity of one single hearer and multiple hearers. The results are averaged across 10 simulations, each with 50 agents, where 60% of them were randomly selected as hearers. We can see that the graphs of multiple hearers rise sharply from the beginning and become stable as the games develop. This indicates that using multiple hearers is much better than one single hearer, since knowledge is spread and exchanged well among agents. The success rate and word size are shown in Figure 8. We can see that the success rate of using multiple hearers (left graph) increases sharply from the beginning while that of using a single hearer increases gradually and reaches only around 25%. The graph on the right shows that using multiple hearers creates a much smaller number of words, which indicates its capacity to communicate successfully using a small set of words. In addition, the small word size reduces word ambiguity and variability. Thus, it is clear that using multiple hearers is more effective than using a single hearer. Hence, in further experiments, only multiple hearers are examined.
Figure 7 Coherence (left) and specificity (right) with 50 agents.
Figure 8 Success rate (left) and word size (right) with 50 agents.
4.2 15BEffects of the Number of Agents in Games
When more agents are involved in the games, the ambiguity and variability are expected to increase. Figure 9 shows the coherence and specificity rates for different numbers of agents as the games proceed. In general, as shown in the previous section, coherence and specificity rise steeply early on and slowly
converge to a certain level as the games go on. Three communities of agents were studied: 5 agents, 10 agents and 20 agents for playing the language games (60% of them selected as hearers).
We can see that a small group of agents communicates much more efficiently than a larger group, since the smaller group has less variability in the generated words, which makes it easier to communicate. To improve word variability and ambiguity, an additional component is needed, which will be discussed in Section 4.4.
Figure 9 Effects of the number of agents.
4.3 Effects of the Number of Hearers
In this section we study the effects of the number of hearers by varying the percentage of agents selected as hearers.
Figure 10 Effects of the number of hearers.
From the total of 50 agents, the results in Figure 10 show that using more hearers yields better coherence and specificity and at the same time climbs to a steady state more quickly than using less hearers, because more hearers generate more knowledge sharing. This means that the interpretation of a word's meaning depends more on others' interpretations than on that of the agent itself.
4.4 Effectiveness of Cultural Knowledge
So far, we examined language games with only individual and social knowledge. In this section, cultural knowledge as described in the proposed method is included and its effectiveness is analyzed. We can see from the results in Figure 11 that using cultural knowledge gives a higher coherence and slightly more specificity, which shows that cultural knowledge allows agents to reach agreements more efficiently, as proposed.
Figure 11 Effectiveness of cultural knowledge on coherence and specificity.
The results for word size, in Figure 12, show that the games with CA generate a lower value for word size than those without CA. The results indicate that agents who live in a society holding a strong belief that is extracted from the society are more confident in communication because the speaker chooses standard beliefs about word-object pairing from the cultural memory when it encounters an obscure situation.
Figure 12 Effect of cultural knowledge on word size.
5 Conclusions
Autonomous agreement in agents is important for their communication. Language games attempt to find the meanings of words by using shared agreement among agents. In this article a language game was proposed for sharing agreement in a population using three levels of belief: individual belief formed by a conceptual space implemented with a self-organizing map, social belief created by communications among multiple hearers, and cultural belief created by a cultural algorithm. The evaluation results showed that using multiple hearers yields fast convergence to mutual agreement in a society of agents, a small lexicon size and a higher success rate, especially with a large number of agents. In addition, using cultural knowledge helps the speaker select words from the cultural repository when he or she needs help, which has a positive impact on word-belief in the hearers. In future research, belief sharing, either social or cultural belief, should be investigated in more detail to help the autonomous learning process more effectively.