* Sony CSL, 6, Rue Amyot, 75005, Paris, France
jelle@csl.sony.fr
www-binf.bio.uu.nl/~jelle

** Theoretical Biology, Utrecht University
Padualaan 8, 3584 CH Utrecht, The Netherlands
p.hogeweg@bio.uu.nl

We study the evolution of syntax in a simple multi-agent model. The fitness of agents in the model is not a fixed function of the individual languages, but depends on their communicative success in the group and thus on the composition of the population. This fact significantly alters the evolutionary dynamics, and can both facilitate and hinder the development of syntactic language. The results challenge the traditional picture of the transition towards syntactical language.

The transition from short, finite communication systems found in many animal species, to the open ended language system of humans, is considered to be one of the major transitions in evolution (Maynard-Smith & Szathmáry 1995). There is large agreement that the main qualitative difference is the syntax of human language: the syntactic nature allows for a systematic production and interpretation of an unbounded amount of different messages. Syntax therefore reconciles the need for a large expressiveness with the limitations in human learning and memory. This aspect is, in the traditional view, what makes syntax selectively advantageous, and caused the transition from an extensive non-syntactical "protolanguage" to a more efficient, syntactical language system (Pinker & Bloom 1990; Nowak & Krakauer 1999).

We study this transition in a computational model of an evolving population of communicating agents. The main advantages of computational and mathematical models such as (Hurford 1989; Steels 1997; Hashimoto & Ikegami 1996; Nowak & Krakauer 1999), are that they are relatively precise and productive, in the sense that they generate new concepts and hypotheses. The main contribution so far is that they have shown the plausibility of cultural evolution as a mechanism in the development of more complex languages (De Jong 1998; De Boer & Vogt 1999; Batali 1997; Kirby 2000).

Fewer studies exist that model genetic transmission of language capabilities. Following (Hashimoto & Ikegami 1996), the model reported in this paper studies the dynamics of genetic transmission of language. Our model takes an extreme position, as it ignores learning mechanisms and semantics, and models genetic adaptation of particular grammars. Language capabilities are described with "context free grammars", that make compositional and recursive structures very easy to obtain. However, unlike some other studies of genetic transmission (e.g. Batali 1994), no static fitness function is defined; the grammars of all individuals in a group determine the environment in which an agent must survive.

Under these simplified conditions, the interaction between evolutionary dynamics and group dynamics can be studied. We will show that even without learning and cultural transmission, "social patterns" can influence the evolutionary dynamics. We observe that the multi-agent set-up can yield powerful, recursive grammars, but it can also prevent a population from obtaining them. Interestingly, because of these group effects, rules in one agent’s grammar can influence the persistence of rules in other grammars, even though the mechanism of cultural evolution is excluded. We will show, that the results in some sense challenge the traditional picture of the transition towards syntactical language.

The model consists of a small set of agents that play a language game. They communicate in a language of short sequences (maxl = 6) of 0’s and 1’s. Agents speak ("derive") and understand ("parse") these strings using a Chomskyan rewriting grammar, which they inherited – with some random mutations – from their parent. In each language game, all agents can speak once and try to understand each of the spoken strings. Agents receive scores depending on their success in speaking, understanding and (not) being understood. After a number of language games, scores are evaluated and offspring is produced. Successful agents have a higher chance of survival and reproduction.

The grammars of the agents are context free grammars, with a small terminal (Vte = {0, 1}) and non-terminal alphabet (Vnt = {S, A, B}). As an extra restriction, the start symbol is not allowed on the right-hand side of rules. At the start of most simulations, grammars are randomly initialized with either S ® 1 or S ® 0.

Derivation always starts with the start symbol, and applies iteratively random fitting rules for some maximum number of steps (maxd = 60; failure), until no fitting rule exists (failure), or until a string of only terminal symbols is reached (success). In parsing rules are tried in the order they are stored, and fitting rules are applied recursively until the maximum number of steps (maxp = 500) is reached (failure), no other fitting rules exist to any intermediate string (failure), or the start symbol is reached (success).

The model architecture is similar to the model introduced by (Hashimoto & Ikegami 1996). They discuss their results in terms of the Chomsky hierarchy of grammars and languages. In a domain of changing grammars and finite languages, we believe it is much more convenient to use a classification in terms of "routes". A route is a sequence of rewriting steps that connects the start symbol S to a string of terminal symbols. Routes can be categorized as lexical (directly from S to a terminal string), compositional (via non-terminal symbols from S to a terminal string) or recursive (leading from a non-terminal symbol via one or more rewriting steps to the same non-terminal symbol). The number of routes, can be divided in three components RI, RC, RR, that depend on each of these categories of routes. Similarly, expressiveness (the number of distinct strings a grammar can parse) can be divided in EI, EC, ER routes. Grammars can be characterized by these values, and classified according to the largest component (Zuidema 2000).

To evaluate some general properties of the model, we studied the behavior with the parameter settings of (Hashimoto & Ikegami 1996), and a number of variations. Similar to their results, we find that evolution can quickly lead to grammars that can parse a large fraction of the 126 possible strings. However, under slightly different parameter settings we also find quite different results. We observe three types of behavior:

1. The most frequent behavior is a quick growth of expressiveness, from 1 at initialization, to over 100 after about a 1000 generations. In the first stage the expressiveness depends only on lexical routes. Soon, however, compositional routes and recursive routes become more important. Eventually, recursive routes dominate the grammar's expressiveness.
2. Sometimes, it takes much longer to reach the high level of expressiveness, ranging from 2000 to many thousands of generations. In these type of runs, compositional routes quickly become important, but recursive routes are infrequent.
3. Least frequent are runs that show very little growth in expressiveness. After 3000 generations, only around 20 words can be parsed. In these runs, expressiveness depends almost exclusively on lexical routes.

Figure 1: Three runs, typical for the lexical, compositional and recursive regimes, and some example grammars.

These types of behavior also differ in their robustness against mutations and generalization abilities. With some particular parameter settings, each of the three types of behavior can occur, solely depending on the "seed" for the random generator. At different generations we restarted runs with original grammars but a different random seed. In early generations, a change of type of behavior occurs frequently. However, in restarts from later generations, the type of behavior seems fixed and a change of type becomes increasingly improbable. The types of behavior thus form self-enforcing, dynamical regimes.

These results crucially depend on the fact that the fitness of an agent is evaluated with respect to its performance in the group, rather than with respect to some static fitness function. In a random population, agents with more expressive grammars speak more novel strings, understand more strings and are less likely to be understood, and thus should receive higher scores. The existence of the dynamical regimes, in a non-random population, can be explained by three mechanisms: a mutation bias (mutation tend to produce similar grammars), a context effect (rules are generally most successful in a context of similar rules) and a group effect (agents are most successful in a group of similar agents).

The derive-languages of individuals, jointly constitute a group language, that in turn determines the success of agents in parsing. This indirect feedback can best be described as a social pattern that emerges from individual behaviors, and in turn restricts individual success. Initial similarities (in terms of our classification) are enforced by these social patterns.

Apparently, the larger an lexical grammar is, the less likely it is that evolution can lead to compositional and recursive grammars. This in some sense contradicts the traditional picture of the evolution of syntax, that states that only when lexical grammars became too large, syntax emerged.

A simple analysis can lead to some qualitative predictions on how, given the existence of these regimes, different variables in the model should relate. One can show, that the number of routes grows linearly with grammar size in the lexical regime. In a compositional regime it grows faster, and in a recursive regime extremely fast. A rough estimate of how expressiveness depends on R, gives a qualitative explanation for the trajectories in the phase space in figure 2. If a linear growth of grammar size over time is assumed, the shape of the curves in figure 1 can also be explained.

Figure 2: Trajectories of the same three runs in a phase space of functional grammar size (the number of rules that are actually used in communication) vs. expressiveness

With the scope of possible behaviors sketched, we can now turn to the question under what selection pressures the different dynamical behaviors are likely to arise. To study this, we designed several simple scoring schemes. These include: (i) communication, where both speaker and receiver benefit from exchanging information; and (ii) perception, where only the recognizing agent benefits from the information it receives.

Although recursive structures are always only a few mutations away, the development of recursive and expressive grammars is not trivial at all. With the default initial grammar (randomly S ® 1 or S ® 0), the communication scheme shows no increase in expressiveness, unless an explicit pressure is put on innovation. In that case sometimes recursive structures develop, but slowly and to a limited extent. If grammars are initialized with a longer lexical grammar, even this explicit innovation pressure can not force the simulation out of the lexical regime.

In contrast, the perception scheme leads to recursive grammars under all circumstances considered. However, when the population has been at a high level of expressiveness for some time, agents start to develop grammars that are just as expressive, but have a high probability of failing in derivation. The asymmetry in parsing and derivation makes this possible.

These results yield an interesting paradox. Under the parameter settings that lead to expressive grammars, the willingness to speak is absent, while in cases where communication is mutually beneficial, no increase in expressiveness occurs.

This study concerns the interaction between group dynamics and evolutionary dynamics. We have seen that social patterns influence the course of evolution. Under some conditions powerful, recursive grammars develop (Hashimoto & Ikegami 1996). This appears to be due to the social embedding that yields a dynamical fitness landscape, because simulations with a fixed fitness evaluation fail to give similar good results.

However, in other circumstances social patterns hinder the development of such grammars. These results are particularly interesting, as these specific circumstances in some sense resemble the situation that is thought to precede the emergence of syntax: large lexical grammars and mutually beneficial communication. In the model we arrive at a paradox, where those selection pressures that lead to syntactical languages, also lead to unwillingness to speak. Preliminary results indicate, that this paradox can be solved if a spatial distribution of agents and local communication is assumed\citep (Zuidema & Hogeweg 2000).

Relaxing the idea of explicit selection pressures for syntax, the analysis of the shapes of the curves in figure 2 points at an alternative mechanism for the development of recursion. The fact that recursive expressiveness (ER) grows very fast with the number of rules (N), shows that the larger N (i.e. the "storage capacity"), the larger the expected relative fraction of recursive expressiveness. Whereas the traditional view emphasizes that cognitive limitations create the need for syntax, this observation indicates that larger cognitive abilities in fact make recursive expressiveness more likely to dominate. This might explain the apparent paradox, that the species with the most extended cognitive abilities, is the only species that developed "efficient", recursive communication.

.

 Conference site: http://www.infres.enst.fr/confs/evolang/