Mutual Exclusivity in the Naming Game

The Categorisation Game or Naming Game looks at how agents in a population converge on a shared system for referring to continuous stimuli (Steels, 2005; Nowak & Krakauer, 1999). Agents play games with each other, one referring to an object with a word and the other trying to guess what object the first agent was referring to. Through experience with the world and feedback from other agents, agents update their words. Eventually, agents are able to communicate effectively.  The model is usually couched in terms of agents trying to agree on labels for colours (a continuous meaning space).  In this post I'll show that the algorithms used have implicit mutual exclusivity biases, which favour monolingual viewpoints.  I'll also show that this bias is not necessary and obscures some interesting insights into evolutionary dynamics of langauge.

A variant of this game called the 'minimal naming game' has been studied recently (Loreto et al., 2009). It works in the following way:

There is a population of N agents, each able to partition the perceptual space into categories. Each category has a list of associated words. Each agent has a minimum perceptual difference threshold dMIN, below which stimuli appear the same. At each time step:

  1. Two individuals are chosen at random to be the speaker and the listener.
    They both have access to a scene containing M stimuli (usually set to 2). The stimuli must be perceptually distinguishable by the agents (perceptual distance > dMIN)
    The speaker selects a topic and discriminates it in the following way:
    • Each stimulus is assigned to a perceptual category
    • If one or more other stimuli are assigned to the same category as the topic, the agent splits its perceptual categories so that each stimulus belongs to only one perceptual category.
    • The new partitions inherit the associated words of the old partition.
    • Heuristic A: Each new partition is given a new, unique name. It's assumed that no two agents will create the same name.
  2. The speaker transmits a word that it associates with the topic to the listener. If it has no words associated with the category, it creates a new one. If it has more than one word associated, it transmits the one that was last used in a successful communication.
  3. The hearer receives the word and finds all categories which have the associated word and which identify one of the stimuli in the scene. Then:
  4. If there are no such categories, the agent does nothing.
    If there is one such category, the agent points to the associated stimulus.
    If there is more than one such category, the agent points randomly at an associated stimulus.
  5. The hearer discriminates the scene, as above.
  6. The speaker reveals the topic to the listener.
    If the hearer did not point to the topic, the communication is a failure. The hearer adds the transmitted word to the category discriminating the topic.
    If the hearer pointed to the topic, the communication is a success.
  7. Heuristic B: If the communication is a success, both agents delete all other words but the transmitted one from the inventory of the category discriminating the topic.

I've labelled some steps above as 'heuristics'.  Heuristic A, above, invents new words for each sub-category when a category is split.  This is an implementation of the assumption that each name only refers to one object, hence when there are two objects with the same name, the agent should discriminate between them linguistically.  This interacts with Heuristic B which removes all competing names associated with a category from the listener's lexicon when communication is successful.  The effect is that the listener conforms to the speaker's labeling, but also `forgets' any previously associated words.  This is an implementation of the assumption that each object only has one name.

That is, these heuristics implement a Mutual Exclusivity Bias.  Although mutual exclusivity is exhibited by monolinguals (Markman_Wachtel_1988,Merriman_Bowman_1989), it is not exhibited by bilinguals (Merriman_Kutlesic_1993,Byers-Heinlein2009,Healey_Skarabela_2009,Houston_Price_2010).  This is presumably because bilinguals have more variation in their input.

However, the minimal naming game assumes that mutual exclusivity is a fundamental part of any agent's learning algorithm.  The other view is that it's a heuristic that emerges - a king of corner-cutting tactic - if the variation in the input is low enough.  That is, it makes sense for monolinguals to apply mutual exclusivity, but perhaps not for bilinguals.

So, what happens if we take away the mutual exclusivity bias?  The graph below shows the communicative success of a population of 4 agents with different heuristics turned on or off.  The solid black line is with both heursitics on.  The red line is Heuristic A only, the green line is heuristic B only and the blue line is with neither heuristic.

Surprisingly, the agents still converge on a functional language without these biases.  In a forthcoming paper, Baronchelli looks at the effect of removing.  Baronchelli finds similar results, but focusses on the role of feedback rather than the individual learning algorithm.

The effect of switching the heuristics on or off can affect the communicative success, but this depends on the number of agents in the model.  Below is the communicative success of four populations.  The two on the right have two agents, the two on the left have four agents.  The black lines are for agents with neither heuristic. The red lines have the heuristics switched 'on' after 1500 rounds (vertical red line).  Performance in the 4-agent condition, but not the 2-agent condition, is affected.

Communicative success at the lexical level can be achieved without mutual exclusivity constraints.  In fact, in some cases, the constraint impedes the process.  The mutual exclusivity bias is, however, an efficient way of integrating the ingredients for evolution.  If we see the heuristics as optional extras, then it is bilingualism - not monolingualism - that is the simplest, default assumption of learners.  That is, monolingualism is a specialised form of bilingualism.

When modelling cultural processes, abstraction is necessary.  However, the cultural phenomena that appear simplest (e.g. monolingualism) may not be caused by the simplest learning mechanisms.  Much of the complexity in cultural phenomena stem from complex interactions between individuals.  That is, the cultural transmission process itself can shape and influence the cultural practices it transmits.

Andrea Baronchelli (2010). Do you agree? Role of feedback and broadcasting in the Naming Game ArXiv e-prints arXiv: 1009.4798v1

Vittorio Loreto, Andrea Baronchelli, & Andrea Puglisi (2009). Mathematical Modeling of Language Games Evolution of Communication and Language in Embodied Agents DOI: 10.1007/978-3-642-01250-1_15