Language Evolution and Computation Bibliography

A lot of conventions emerge in gradual stages without being centrally imposed. The most significant and complex example in our human society is undoubtedly human language which evolved according to our need for communication. Also in artificial multi-agent systems, e.g. mobile robots or software agents, it is often desirable that agents can reach a convention in a distributed way. To make this possible, it is important to have a sound grasp of the mechanism by which conventions arise.

In this thesis we define a theoretical framework that enables us to examine this process carefully. We make a strict distinction between the description of the convention problem on the one hand and the solution to this problem in terms of an agent design on the other. A convention problem specifies the preconditions any type of agent must comply with. This includes (i) the space of alternatives from which the convention is to be chosen, (ii) the interaction model between the agents, which determines which agents interact at what time and (iii) the amount, nature and direction of information transmitted between the agents during an interaction. A particular agent design solves a convention problem if a population of such agents will reach an agreement in a reasonable time, under the given restrictions.

We focus on the class of convention problems with a global interaction model: every agent is equally likely to interact with any other agent. We argue that for these convention problems the performance of an agent can be predicted by inspecting the properties of the agent's response function. This response function captures the average behavior of an agent when interacting with agents from a non-changing population.

We apply this analytical technique to different sorts of convention problems. For the more simple convention problems we define general, sufficient properties which guarantee that a convention will arise after a certain amount of time when an agent possesses these. For the more difficult convention problems we confine ourselves to the construction of agents who, we can show, will solve the problem. Finally, our framework is applied to the problem of language evolution in artificial agents. This is a complicated domain for which precise mathematical results are very difficult to obtain. We will focus on the naming game, a relatively simple instance in the paradigm of languages games. In certain instances our analysis will surface problems of convergence that have not been noticed before. This shows on the one hand that it is important to theoretically substantiate computer experiments in language evolution and on the other that the framework introduced in this thesis is very suitable to this extent.

There is a growing body of research on multi-agent systems bootstrapping a communication system. Most studies are based on simulation, but recently there has been an increased interest in the properties and formal analysis of these systems. Although very interesting and promising results have been obtained in these studies, they always rely on major simplifications. For example, although much larger populations are considered than was the case in most earlier work, previous work assumes the possibility of meaning transfer. With meaning transfer, two agents always exactly know what they are talking about. This is hardly ever the case in actual communication systems, as noise corrupts the agents' perception and transfer of meaning. In this paper we first consider what happens when relaxing the meaning-transfer assumption, and propose a cross-situational learning scheme that allows a population of agents to still bootstrap a common lexicon under this condition. We empirically show the validity of the scheme and thereby improve on the results reported in (Smith, 2003) and (Vogt and Coumans, 2003) in which no satisfactory solution was found. It is not our aim to reduce the importance of previous work, instead we are excited by recent results and hope to stimulate further research by pointing towards some new challenges.

In this paper we introduce a mathematical model of naming games. Naming games have been widely used within research on the origins and evolution of language. Despite the many interesting empirical results these studies have produced, most of this research lacks a formal elucidating theory. In this paper we show how a population of agents can reach linguistic consensus, i.e. learn to use one common language to communicate with one another. Our approach differs from existing formal work in two important ways: one, we relax the too strong assumption that an agent samples infinitely often during each time interval. This assumption is usually made to guarantee convergence of an empirical learning process to a deterministic dynamical system. Two, we provide a proof that under these new realistic conditions, our model converges to a common language for the entire population of agents. Finally the model is experimentally validated.

In this paper it is argued that the way the world is conceptualized for language is language dependent and the result of negotiation between language users. This is investigated in a computer experiment in which a population of artificial agents constructs a shared language to talk about a world that can be conceptualized in multiple and possibly conflicting ways. It is argued that the establishment of a successful communication system requires that feedback about the communicative success is propagated to the ontological level, and thus that language shapes the way we conceptualize the world for communication.

Evolutionary game dynamics have been proposed as a mathematical framework for the cultural evolution of language and more specifically the evolution of vocabulary. This article discusses a model that is mutually exclusive in its underlying principals with some previously suggested models. The model describes how individuals in a population culturally acquire a vocabulary by actively participating in the acquisition process instead of passively observing and communicate through peer-to-peer interactions instead of vertical parent-offspring relations. Concretely, a notion of social/cultural learning called the naming game is first abstracted using learning theory. This abstraction defines the required cultural transmission mechanism for an evolutionary process. Second, the derived transmission system is expressed in terms of the well-known selection-mutation model defined in the context of evolutionary dynamics. In this way, the analogy between social learning and evolution at the level of meaning-word associations is made explicit. Although only horizontal and oblique transmission structures will be considered, extensions to vertical structures over different genetic generations can easily be incorporated. We provide a number of simplified experiments to clarify our reasoning.

In this paper we present our work on developing a shared repertoire of action categories through imitation. A population of robotic agents invents and shares a repertoire of actions by engaging in imitative interactions. We present an experimental set-up which enables us to investigate what properties agents should have in order to achieve this. Among these properties are: being able to determine the other's actions from visual observation and doing incremental unsupervised categorisation of actions.