Language Evolution and Computation Bibliography

Coding plays a universal and pervasive role in biological organization, in forms such as genetic coding (DNA to protein translation), RNA processing, gene regulation, protein modification, cell signalling, immune responses, epigenetic development and natural language. Nevertheless, the ways and means by which organic codes are formed and used are still poorly understood. A formal model is presented in this paper to investigate the emergence of conventional codes among code users. The relationship between the formation and the usage of codes is discussed, and a biological mechanism involving coding is identified in the context of the immune system.

A computational language game model is presented that shows how a population of language users can evolve from a brightness-based to a brightness+hue-based color term system. The shift is triggered by a change in the communication challenges posed by the environment, comparable to what happened in English during the Middle English period in response to the rise of dyeing and textile manufacturing c. 1150--1500. In a previous model that is able to explain such a shift, these two color categorization strategies were explicitly represented. This is not needed in our model. Instead, whether a population evolves a brightness-or a hue-based system is an emergent phenomenon that depends only on environmental factors. In this way, the model provides an explanation of how such a shift may come about without introducing additional mechanisms that would require further explanation.

According to recent developments in (computational) Construction Grammar, language processing occurs through the incremental buildup of meaning and form according to constructional specifications. If the number of available constructions becomes large however, this results in a search process that quickly becomes cognitively unfeasible without the aid of additional guiding principles. One of the main mechanisms the brain recruits (in all sorts of tasks) to optimize processing efficiency is priming. Priming in turn requires a specific organisation of the constructions. Processing efficiency thus must have been one of the main evolutionary pressures driving the organisation of linguistic constructions. In this paper we show how constructions can be organized in a constructional dependency network in which constructions are linked through semantic and syntactic categories. Using Fluid Construction Grammar, we show how such a network can be learned incrementally in a usage-based fashion, and how it can be used to guide processing by priming the suitable constructions.

A key feature of many biological distributed systems is that they have the capacity to behave in highly coordinated ways. In the domain of language, such coordination dynamics have been studied within the framework of language games. As yet however, a fundamental understanding that goes beyond the simplest cases is still missing. In this paper, a novel approach is proposed for investigating coordination problems. I illustrate the approach for a simple but well studied case called the naming game. I will therefore bring together a number of ideas from Artificial Chemistry and Chemical Reaction Network Theory, Semiotic Dynamics and Immunology, and conclude by arguing why the proposed approach provides a good starting point for tackling more complex coordination problems as well.

It is argued that compositionality, hierarchy and recursion, generally acknowledged to be universal features of human languages, can be explained as being emergent properties of the complex dynamics governing the establishment and evolution of a language in a population of language users, mainly on an intra-generational time scale, rather than being the result of a genetic selection process leading to a specialized language faculty that imposes those features upon language or than being mainly a cross-generational cultural phenomenon. This claim is supported with results from a computational language game experiment in which a number of autonomous software agents bootstrap a common compositional and recursive language.

In this paper we motivate and report on the implementation of a computer experiment to investigate the syntax and semantics of linguistic constructions about time. It is argued that the way in which a domain like time is conceptualized is not universal and evolves over time. To investigate this we want to simulate a population of agents evolving their proper language and ontology of time in order to succeed in communicating temporal information. Such simulations can be done using a formalism proposed by Steels (2004). Some advances in applying the formalism to the domain of time are reported and examples of actual simulations are presented.

Compositionality is a hallmark of human language - words and morphemes can be factorially combined to produce a seemingly limitless number of viable strings. This contrasts with nonhuman communication systems, which for the most part are holistic - encoding a whole message through a single, gestalt form. Why does every human language adopt a compositional strategy? In this paper, we show that compositional language can arise automatically through grounded communication among populations of communicators. The proposed mechanism is the following: if a holistic and a compositional approach are in competition and if both structured (compositional) and atomic meanings need to be communicated, the holistic strategy becomes less successful as it does not recruit already acquired bits of language. We demonstrate the viability of this explanation through computer simulations in which populations of artificial agents perform a communicative task - describing scenes that they have observed. Successful language strategies (that is, those yielding successful transmission of information about a scene) are reinforced while unsuccessful ones are demoted. The simulations show that this reinforcement on the basis of communicative success indeed leads to the dominance of compositional language as long as the fraction of unstructured meaning to be communicated is sufficiently high. Moreover, following Elman (1993), we then show that the same effect can be achieved by, instead of manipulating the world (the fraction of unstructured meaning presented to the agents), letting the agents themselves go through developmental stages. These simulations confirm that simple reinforcement mechanisms applied during communicative interactions can account for the emergence of linguistic compositionality.

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.

Fluid Construction Grammar (FCG) is a new linguistic formalism designed to explore in how far a construction grammar approach can be used for handling open-ended grounded dialogue, i.e. dialogue between or with autonomous embodied agents about the world as experienced through their sensory-motor apparatus. We seek scalable, open-ended language systems by giving agents both the ability to use existing conventions or ontologies, and to invent or learn new ones as the needs arise. This paper contains a brief introduction to the key ideas behind FCG and its current status.

Research into the evolution of grammar requires that we employ formalisms and processing mechanisms that are powerful enough to handle features found in human natural languages. But the formalism needs to have some additional properties compared to those used in other linguistics research that are specifically relevant for handling the emergence and progressive co-ordination of grammars in a population of agents. This document introduces Fluid Construction Grammar, a formalism with associated parsing, production, and learning processes designed for language evolution research. The present paper focuses on a formal definition of the unification and merging algorithms used in Fluid Construction Grammar. The complexity and soundness of the algorithms and their relation to unification in logic programming and other unification-based grammar formalisms are discussed.

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.

This paper reports further progress into a computational implementation of a new formalism for construction grammar, known as Fluid Construction Grammar (FCG). We focus in particular on how hierarchy can be implemented. The paper analyses the requirements for a proper treatment of hierarchy in emergent grammar and then proposes a particular solution based on a new operator, called the J-operator. The J-operator constructs a new unit as a side effect of the matching process.

One of the key problems in any language processing system is to establish an adequate syntax/semantics interface, and one of the major requirements of such an interface is that partial meanings contributed by individual words are properly linked with each other based on grammatical constructions. This paper reports how we deal with this problem within the context of Fluid Construction Grammars ({\sc fcg}). {\sc Fcg} is a general unification-based inference engine which has been designed to support experiments in the self-organisation of language in a population of interacting situated embodied agents. The paper focuses on technical details pertaining to the linking problem.

A mechanism is described that enables a robotic agent to create temporal categories for conceptualizing the world. The creation of a new category is triggered when the agent is unable to temporally distinguish an event from the other events in the context using already adopted categories. This is different from most other approaches where ontological categories are defined by humans and the ontologies are fixed in advance.

Human, syntactic language is one of the most intriguing behaviors and receives increasing attention from researchers in numerous fields. Here we present a model that goes an important step further than previous work because it explicitly connects low-level perception and categorization, hierarchical meaning construction and syntactic language. The model thus shows a solution to the `symbol grounding problem' (Harnad, 1990): the meaning of the symbolic system - logical symbols and syntactic rules - is grounded in its relation with a simplified but realistic world. We discuss the different components of this collaborative effort: (i) a realistic simulation of Newtonian dynamics of objects in a 2D plane; (ii) schemabased event-perception and categorization; (iii) a semantics based on predicate logic; and (iv) a categorial grammar for the production and interpretation of language. The integration of the different components poses on the one hand novel and important constraints; on the other hand, it allows for experiments that help to identify the relations between the different levels. We note some important similarities and differences with SHRDLU (Winograd, 1976) and the Talking Heads experiment (Steels et al., 2002), and give an agenda for future experiments.