Language Evolution and Computation Bibliography

The availability of large diachronic corpora has provided the impetus for a growing body of quantitative research on language evolution and meaning change. The central quantities in this research are token frequencies of linguistic elements in the texts, with changes in frequency taken to reflect the popularity or selective fitness of an element. However, corpus frequencies may change for a wide variety of reasons, including purely random sampling effects, or because corpora are composed of contemporary media and fiction texts within which the underlying topics ebb and flow with cultural and socio-political trends. In this work, we introduce a computationally simple model for controlling for topical fluctuations in corpora—the topical-cultural advection model—and demonstrate how it provides a robust baseline of variability in word frequency changes over time. We validate the model on a diachronic corpus spanning two centuries, and a carefully-controlled artificial language change scenario, and then use it to correct for topical fluctuations in historical time series. Finally, we show that the model can be used to show that emergence of new words typically corresponds with the rise of a trending topic. This suggests that some lexical innovations occur due to growing communicative need in a subspace of the lexicon, and that the topical-cultural advection model can be used to quantify this.

We set out an account of how self-domestication plays a crucial role in the evolution of language. In doing so, we focus on the growing body of work that treats language structure as emerging from the process of cultural transmission. We argue that a full recognition of the importance of cultural transmission fundamentally changes the kind of questions we should be asking regarding the biological basis of language structure. If we think of language structure as reflecting an accumulated set of changes in our genome, then we might ask something like, "What are the genetic bases of language structure and why were they selected?" However, if cultural evolution can account for language structure, then this question no longer applies. Instead, we face the task of accounting for the origin of the traits that enabled that process of structure-creating cultural evolution to get started in the first place. In light of work on cultural evolution, then, the new question for biological evolution becomes, "How did those precursor traits evolve?" We identify two key precursor traits: (1) the transmission of the communication system through learning; and (2) the ability to infer the communicative intent associated with a signal or action. We then describe two comparative case studies-the Bengalese finch and the domestic dog-in which parallel traits can be seen emerging following domestication. Finally, we turn to the role of domestication in human evolution. We argue that the cultural evolution of language structure has its origin in an earlier process of self-domestication.

Human language is composed of sequences of reusable elements. The origins of the sequential structure of language is a hotly debated topic in evolutionary linguistics. In this paper, we show that sets of sequences with language-like statistical properties can emerge from a process of cultural evolution under pressure from chunk-based memory constraints. We employ a novel experimental task that is non-linguistic and non-communicative in nature, in which participants are trained on and later asked to recall a set of sequences one-by-one. Recalled sequences from one participant become training data for the next participant. In this way, we simulate cultural evolution in the laboratory. Our results show a cumulative increase in structure, and by comparing this structure to data from existing linguistic corpora, we demonstrate a close parallel between the sets of sequences that emerge in our experiment and those seen in natural language.

Language is systematically structured at all levels of description, arguably setting it apart from all other instances of communication in nature. In this article, I survey work over the last 20 years that emphasises the contributions of individual learning, cultural transmission, and biological evolution to explaining the structural design features of language. These 3 complex adaptive systems exist in a network of interactions: individual learning biases shape the dynamics of cultural evolution; universal features of linguistic structure arise from this cultural process and form the ultimate linguistic phenotype; the nature of this phenotype affects the fitness landscape for the biological evolution of the language faculty; and in turn this determines individuals' learning bias. Using a combination of computational simulation, laboratory experiments, and comparison with real-world cases of language emergence, I show that linguistic structure emerges as a natural outcome of cultural evolution once certain minimal biological requirements are in place.

The emergence of signaling systems has been observed in numerous experimental and real-world contexts, but there is no consensus on which (if any) shared mechanisms underlie such phenomena. A number of explanatory mechanisms have been proposed within several disciplines, all of which have been instantiated as credible working models. However, they are usually framed as being mutually incompatible. Using an exemplar-based framework, we replicate these models in a minimal configuration which allows us to directly compare them. This reveals that the development of optimal signaling is driven by similar mechanisms in each model, which leads us to propose three requirements for the emergence of conventional signaling. These are the creation and transmission of referential information, a systemic bias against ambiguity, and finally some form of information loss. Considering this, we then discuss some implications for theoretical and experimental approaches to the emergence of learned communication.

Human language has unusual structural properties that enable open-ended communication. In recent years, researchers have begun to appeal to cultural evolution to explain the emergence of these structural properties. A particularly fruitful approach to this kind of explanation has been the use of laboratory experiments. These typically involve participants learning and interacting using artificially constructed communication systems. By observing the evolution of these systems in the lab, researchers have been able to build a bridge between individual cognition and population-wide emergent structure. We review these advances, and show how cultural evolution has been used to explain the origins of structure in linguistic signals, and in the mapping between signals and meanings.

In language, recombination of a discrete set of meaningless building blocks forms an unlimited set of possible utterances. How such combinatorial structure emerged in the evolution of human language is increasingly being studied. It has been shown that it can emerge when languages culturally evolve and adapt to human cognitive biases. How the emergence of combinatorial structure interacts with the existence of holistic iconic form‐meaning mappings in a language is still unknown. The experiment presented in this paper studies the role of iconicity and human cognitive learning biases in the emergence of combinatorial structure in artificial whistled languages. Participants learned and reproduced whistled words for novel objects with the use of a slide whistle. Their reproductions were used as input for the next participant, to create transmission chains and simulate cultural transmission. Two conditions were studied: one in which the persistence of iconic form‐meaning mappings was possible and one in which this was experimentally made impossible. In both conditions, cultural transmission caused the whistled languages to become more learnable and more structured, but this process was slightly delayed in the first condition. Our findings help to gain insight into when and how words may lose their iconic origins when they become part of an organized linguistic system.

Language exhibits striking systematic structure. Words are composed of combinations of reusable sounds, and those words in turn are combined to form complex sentences. These properties make language unique among natural communication systems and enable our species to convey an open-ended set of messages. We provide a cultural evolutionary account of the origins of this structure. We show, using simulations of rational learners and laboratory experiments, that structure arises from a trade-off between pressures for compressibility (imposed during learning) and expressivity (imposed during communication). We further demonstrate that the relative strength of these two pressures can be varied in different social contexts, leading to novel predictions about the emergence of structured behaviour in the wild.

It is well established that context plays a fundamental role in how we learn and use language. Here we explore how context links short-term language use with the long-term emergence of different types of language system. Using an iterated learning model of cultural transmission, the current study experimentally investigates the role of the communicative situation in which an utterance is produced (situational context) and how it influences the emergence of three types of linguistic systems: underspecified languages (where only some dimensions of meaning are encoded linguistically), holistic systems (lacking systematic structure), and systematic languages (consisting of compound signals encoding both category-level and individuating dimensions of meaning). To do this, we set up a discrimination task in a communication game and manipulated whether the feature dimension shape was relevant or not in discriminating between two referents. The experimental languages gradually evolved to encode information relevant to the task of achieving communicative success, given the situational context in which they are learned and used, resulting in the emergence of different linguistic systems. These results suggest language systems adapt to their contextual niche over iterated learning.

Iterated learning describes the process whereby an individual learns their behaviour by exposure to another individual's behaviour, who themselves learnt it in the same way. It can be seen as a key mechanism of cultural evolution. We review various methods for understanding how behaviour is shaped by the iterated learning process: computational agent-based simulations; mathematical modelling; and laboratory experiments in humans and non-human animals. We show how this framework has been used to explain the origins of structure in language, and argue that cultural evolution must be considered alongside biological evolution in explanations of language origins.

Maynard Smith and Szathmáry (1995) propose a series of major transitions in the evolutionary history of life. Their work provides a rich framework for thinking about replication. They identified the importance of language in this light, but language is a new system of replication in more than one sense: it is both an enabler of cultural replicators with unlimited heredity, and also a new kind of evolutionary system itself. Iterated learning is the process of linguistic transmission, and it drives both language change and the transitions to qualitatively new kinds of linguistic system. By seeing language as an evolutionary system, the biggest payoff we get may be the ability to take biologists’ insights into the evolution of life and apply them to the evolution of language.

This article investigates approaches adopted to explain the role of cultural transmission in linguistic structure. One of the approaches is to build working models of populations made up of individuals that interact and acquire language from each other, which uncovers the general relationship between learning biases/constraints and emergent language universals. There are three broad approaches to this kind of modeling that include computational/robotic, mathematical, and experimental approaches. There are a number of ways these models could be configured, but the iterated learning model (ILM) provides a framework, which characterizes many of them. The guiding principles for the ILM include that individuals are explicitly modeled, individuals learn by observing instances of behavior, and individuals also produce behavior as a result of learning that then goes on to be input to other individuals' learning. Researchers used a mathematical model of learning placed within the iterated learning framework to try and answer precisely how the nature of the learner impacts on the structure of language. A recent emerging trend is the use of experimental techniques with human participants to build close analogues to the computational and mathematical models of iterated learning in the laboratory. The technique offers several advantages such as it can be used to test the generality of conclusions from models in a situation where the prior bias is provided by real human biology. It can be used to analyze whether results such as the emergence of compositionality from a holistic protolanguage can really occur in a feasible timescale.

The historical origins of natural language cannot be observed directly. We can, however, study systems that support language and we can also develop models that explore the plausibility of different hypotheses about how language emerged. More recently, evolutionary linguists have begun to conduct language evolution experiments in the laboratory, where the emergence of new languages used by human participants can be observed directly. This enables researchers to study both the cognitive capacities necessary for language and the ways in which languages themselves emerge. One theme that runs through this work is how individual-level behaviours result in population-level linguistic phenomena. A central challenge for the future will be to explore how different forms of information transmission affect this process.

Arbitrariness and systematicity are two of languageas most fascinating properties. Although both are characterizations of the mappings between signals and meanings, their emergence and evolution in communication systems has generally been explored independently. We present an experiment in which both arbitrariness and systematicity are probed. Participants invent signs from scratch to refer to a set of items that share salient semantic features. Through interaction, the systematic re-use of arbitrary signal elements emerges.

The past couple of decades have seen an explosion of research on language evolution, initially fueled by Pinker and Bloomas (1990) groundbreaking article arguing for the natural selection of biological structures dedicated to language. The new millennium has seen a shift toward explaining language evolution in terms of cultural evolution rather than biological adaptation. Crucially, this research has many important implications for cognitive science, not only in terms of the nature of the biases to consider in language acquisition but also for cognition, more generally. In this symposium, we therefore take stock of current work on the cultural evolution of language, highlighting key implications of this work for cognitive scientists from different perspectives, ranging from philosophical considerations (Chater) and Bayesian analyses (Griffiths) to evolutionary psycholinguistics (Kirby) and molecular genetics (Christiansen).

This article discusses human language in the context of the major evolutionary transitions in the history of life. Because of its unique structure, language enables the transmission of unlimited cultural information in our species. Understanding its evolution is therefore an important topic for both cognitive science and evolutionary theory more widely. This article highlights points of consensus on what is crucial for progress in this area: understanding preadaptations; the necessity for interdisciplinarity; and the importance of modeling, comparative approaches, and genetics. It also discusses current controversies: biological versus cultural evolution, vocal versus manual origins, and the nature of protolanguage.

Language is a product of both biological and cultural evolution. Clues to the origins of key structural properties of language can be found in the process of cultural transmission between learners. Recent experiments have shown that iterated learning by human participants in the laboratory transforms an initially unstructured artificial language into one containing regularities that make the system more learnable and stable over time. Here, we explore the process of iterated learning in more detail by demonstrating exactly how one type of structureacompositionalityaemerges over the course of these experiments. We introduce a method to precisely quantify the increasing ability of a language to systematically encode associations between individual components of meanings and signals over time and we examine how the system as a whole evolves to avoid ambiguity in these associations and generate adaptive structure.

A unique hallmark of human language is that it uses signals that are both learnt and symbolic. The emergence of such signals was therefore a defining event in human cognitive evolution, yet very little is known about how such a process occurs. Previous work provides some insights on how meaning can become attached to form, but a more foundational issue is presently unaddressed. How does a signal signal its own signalhood? That is, how do humans even know that communicative behaviour is indeed communicative in nature? We introduce an experimental game that has been designed to tackle this problem. We find that it is commonly resolved with a bootstrapping process, and that this process influences the final form of the communication system. Furthermore, sufficient common ground is observed to be integral to the recognition of signalhood, and the emergence of dialogue is observed to be the key step in the development of a system that can be employed to achieve shared goals.

Human languages include vast numbers of learned, arbitrary signal-meaning mappings but also many complex signal-meaning mappings that are systematically related to each other (i.e. not arbitrary). Although arbitrariness and systematicity are clearly related, the development of the two in communication systems has been explored independently. We present an experiment in which participants invent signs from scratch to refer to a set of real concepts that share semantic features. Through interaction, the systematic re-use of arbitrary elements emerges.

We introduce an experimental paradigm for studying the cumulative cultural evolution of language. In doing so we provide the first experimental validation for the idea that cultural transmission can lead to the appearance of design without a designer. Our experiments involve the iterated learning of artificial languages by human participants. We show that languages transmitted culturally evolve in such a way as to maximize their own transmissibility: over time, the languages in our experiments become easier to learn and increasingly structured. Furthermore, this structure emerges purely as a consequence of the transmission of language over generations, without any intentional design on the part of individual language learners. Previous computational and mathematical models suggest that iterated learning provides an explanation for the structure of human language and link particular aspects of linguistic structure with particular constraints acting on language during its transmission. The experimental work presented here shows that the predictions of these models, and models of cultural evolution more generally, can be tested in the laboratory.

There are two possible sources of structure in language: biological evolution of the language faculty, or cultural evolution of language itself. Two recent models (Griffiths & Kalish, 2005; Kirby, Dowman, & Griffiths, 2007) make alternative claims about the relationship between innate bias and linguistic structure: either linguistic structure is largely determined by cultural factors (Kirby et al., 2007), with strength of innate bias being relatively unimportant, or the nature and strength of innate machinery is key (Griffiths & Kalish, 2005). These two competing possibilities rest on different assumptions about the learning process. We extend these models here to include a treatment of biological evolution, and show that natural selection for communication favours those conditions where the structure of language is primarily determined by cultural transmission.

The 'developmental stress hypothesis' attempts to provide a functional explanation of the evolutionary maintenance of song learning in songbirds. It argues that song learning can be viewed as an indicator mechanism that allows females to use learned features of song as a window on a male's early development, a potentially stressful period that may have long-term phenotypic effects. In this paper we formally model this hypothesis for the first time, presenting a population genetic model that takes into account both the evolution of genetic learning preferences and cultural transmission of song. The models demonstrate that a preference for song types that reveal developmental stress can evolve in a population, and that cultural transmission of these song types can be stable, lending more support to the hypothesis.

We agree that language adapts to the brain, but we note that language also has to adapt to brain-external constraints, such as those arising from properties of the cultural transmission medium. The hypothesis that Christiansen & Chater (C&C) raise in the target article not only has profound consequences for our understanding of language, but also for our understanding of the biological evolution of the language faculty.

Human language is unique among the communication systems of the natural world: it is socially learned and, as a consequence of its recursively compositional structure, offers open-ended communicative potential. The structure of this communication system can be explained as a consequence of the evolution of the human biological capacity for language or the cultural evolution of language itself. We argue, supported by a formal model, that an explanatory account that involves some role for cultural evolution has profound implications for our understanding of the biological evolution of the language faculty: under a number of reasonable scenarios, cultural evolution can shield the language faculty from selection, such that strongly constraining language-specific learning biases are unlikely to evolve. We therefore argue that language is best seen as a consequence of cultural evolution in populations with a weak and/or domain-general language faculty.

Human language arises from biological evolution, individual learning, and cultural transmission, but the interaction of these three processes has not been widely studied. We set out a formal framework for analyzing cultural transmission, which allows us to investigate how innate learning biases are related to universal properties of language. We show that cultural transmission can magnify weak biases into strong linguistic universals, undermining one of the arguments for strong innate constraints on language learning. As a consequence, the strength of innate biases can be shielded from natural selection, allowing these genes to drift. Furthermore, even when there is no natural selection, cultural transmission can produce apparent adaptations. Cultural transmission thus provides an alternative to traditional nativist and adaptationist explanations for the properties of human languages.

In order to persist, language must be transmitted from generation to generation through a repeated cycle of use and learning. This process of iterated learning has been explored extensively in recent years using computational and mathematical models. These models have shown how compositional syntax provides language with a stability advantage and that iterated learning can induce linguistic adaptation. This paper presents an extension to previous idealised models to allow linguistic agents flexibility and choice in how they construct the semantics of linguistic expressions. This extension allows us to examine the complete dynamics of mixed compositional and holistic languages, look at how semantics can evolve culturally, and how communicative contexts impact on the evolution of meaning structure.

We show how cultural selection for learnability during the process of linguistic evolution can be visualized using a simple iterated learning model. Computational models of linguistic evolution typically focus on the nature of, and conditions for, stable states. We take a novel approach and focus on understanding the process of linguistic evolution itself. What kind of evolutionary system is this process? Using visualization techniques, we explore the nature of replicators in linguistic evolution, and argue that replicators correspond to local regions of regularity in the mapping between meaning and signals. Based on this argument, we draw parallels between phenomena observed in the model and linguistic phenomena observed across languages. We then go on to identify issues of replication and selection as key points of divergence in the parallels between the processes of linguistic evolution and biological evolution.

Is the range of languages we observe today explainable in terms of which languages can be learned easily and which cannot? If so, the key to understanding language is to understand innate learning biases, and the process of biological evolution through which they have evolved. Using mathematical and computer modelling, we show how a very small bias towards regularity can be accentuated by the process of cultural transmission in which language is passed from generation to generation, resulting in languages that are overwhelmingly regular. Cultural evolution therefore plays as big a role as prior bias in determining the form of emergent languages, showing that language can only be explained in terms of the interaction of biological evolution, individual development, and cultural transmission.

We present a neural-competitive learning model of language evolution in which several symbol sequences compete to signify a given propositional meaning. Both symbol sequences and propositional meanings are represented by high-dimensional vectors of real numbers. A neural network learns to map between the distributed representations of the symbol sequences and the distributed representations of the propositions. Unlike previous neural network models of language evolution, our model uses a Kohonen Self-Organizing Map with unsupervised learning, thereby avoiding the computational slowdown and biological implausibility of back-propagation networks and the lack of scalability associated with Hebbian-learning networks. After several evolutionary generations, the network develops systematically regular mappings between meanings and sequences, of the sort traditionally associated with symbolic grammars. Because of the potential of neural-like representations for addressing the symbol-grounding problem, this sort of model holds a good deal of promise as a new explanatory mechanism for both language evolution and acquisition.

Vocal learning is a key component of the human language faculty, and is a behaviour we share with only a few other species in nature. Perhaps the most studied example of this phenomenon is bird song which displays a number of striking parallels with human language, particularly in its development. In this paper we present a simple computational model of bird song development and then use this in a model of evolution to investigate some of the ecological conditions under which vocal behaviour can become more or less reliant on cultural transmission.

John Maynard Smith and EoSzathma argued that human language signified the eighth major transition in evolution: human language marked a new form of information transmission from one generation to another [Maynard Smith J, Szathma E. The major transitions in evolution. Oxford: Oxford Univ. Press; 1995]. According to this view language codes cultural information and as such forms the basis for the evolution of complexity in human culture. In this article we develop the theory that language also codes information in another sense: languages code information on their own structure. As a result, languages themselves provide information that influences their own survival. To understand the consequences of this theory we discuss recent computational models of linguistic evolution. Linguistic evolution is the process by which languages themselves evolve. This article draws together this recent work on linguistic evolution and highlights the significance of this process in understanding the evolution of linguistic complexity. Our conclusions are that: (1) the process of linguistic transmission constitutes the basis for an evolutionary system, and (2), that this evolutionary system is only superficially comparable to the process of biological evolution.

One of the most distinctive characteristics of human language is the extent to which it relies on learned vocal signals. Communication systems are ubiquitous in the natural world but vocal learning is a comparatively rare evolutionary development (Jarvis, 2004). In this paper we take one example of this phenomena, bird song, which displays some remarkable parallels with human language (Doupe \& Kuhl, 1999), and we focus on one particular case study, that of the Bengalese finch (Lonchura striata var. domestica), a domesticated species whose song behaviour differs strikingly from its feral ancestor in that it has complex syntax and is heavily influenced by early learning (Okanoya, 2002). We present a computational model of the evolutionary history of the Bengalese finch which demonstrates how an increase in song complexity and increased influence from early learning could evolve spontaneously as a result of domestication. We argue that this may provide an insight into how increased reliance on vocal learning could evolve in other communication systems, including human language.

What constitutes linguistic evidence for Universal Grammar (UG)? The principal approach to this question equates UG on the one hand with language universals on the other. Parsimonious and general characterizations of linguistic variation are assumed to uncover features of UG. This paper reviews a recently developed evolutionary approach to language that casts doubt on this assumption: the Iterated Learning Model (ILM). We treat UG as a model of our prior learning bias, and consider how languages may adapt in response to this bias. By dealing directly with populations of linguistic agents, the ILM allows us to study the adaptive landscape that particular learning biases result in. The key result from this work is that the relationship between UG and language structure is non-trivial.

Why is language the way it is? How did language come to be this way? And why is our species alone in having complex language? These are old unsolved questions that have seen a renaissance in the dramatic recent growth in research being published on the origins and evolution of human language. This review provides a broad overview of some of the important current work in this area. We highlight new methodologies (such as computational modeling), emerging points of consensus (such as the importance of pre-adaptation), and the major remaining controversies (such as gestural origins of language). We also discuss why language evolution is such a difficult problem, and suggest probable directions research may take in the near future.

There are an enormous number of communication systems in the natural world (Hauser, 1996). When a male Tungara frog produces `whines' and `chucks' to attract a female, when a mantis shrimp strikes the ground to warn o a competitor for territory, even when a bee is attracted to a particular flower, communication is taking place. Humans as prodigious communicators are not unusual in this respect. What makes human language stand out as unique (or at least very rare indeed, Oliphant, 2002) is the degree to which it is learned.

The frog's response to mating calls is determined by its genes, which have been tuned by natural selection. There is an inevitability to the use of this signal. Barring some kind of disaster in the development of the frog, we can predict its response from birth. If we had some machine for reading and translating its DNA, we could read-off its communication system from the frog genome. We cannot say the same of a human infant. The language, or languages, that an adult human will come to speak are not predestined in the same way. The particular sounds that a child will use to form words, the words themselves, the ways in which words will be modi ed and strung together to form utterances - none of this is written in the human genome.

Whereas frogs store their communication system in their genome, much of the details of human communication are stored in the environment. The information telling us the set of vowels we should use, the inventory of verb stems, the way to form the past tense, how to construct a relative-clause, and all the other facts that make up a human language must be acquired by observing the way in which others around us communicate. Of course this does not mean that human genes have no role to play in determining the structure of human communication. If we could read the genome of a human like we did with the frog, we would find that, rather than storing details of a communication system, our genes provide us with mechanisms to retrieve these details from the behaviour of others.

From a design point of view, it is easy to see the advantages of providing instructions for building mechanisms for language acquisition rather than the language itself. Human language cannot be completely innate because it would not t in the genome. Worden (1995) has derived a speed-limit on evolution that allows us to estimate the maximum amount of information in the human genome that codes for the cognitive di erences between us and chimpanzees. He gives a paltry gure of approximately 5 kilobytes. This is equivalent to the text of just the introduction to this chapter.

The implications of this aspect of human uniqueness are the subject of this chapter. In the next section we will look at the way in which language learning leads naturally to language variation, and what the constraints on this variation tell us about language acquisition. In section three, we introduce a computational model of sequential learning and show that the natural biases of this model mirror many of the human learner's biases, and help to explain the universal properties of all human languages.

If learning biases such as those arising from sequential learning are to explain the structure of language, we need to explore the mechanism that links properties of learning to properties of what is being learned. In section four we look in more detail at this issue, and see how learning biases can lead to language universals by introducing a model of linguistic transmission called the Iterated Learning Model. We go on to show how this model can be used to understand some of the fundamental properties of human language syntax.

Finally, we look at the implications of our work for linguistic and evolutionary theory. Ultimately, we argue that linguistic structure arises from the interactions between learning, culture and evolution. If we are to understand the origins of human language, we must understand what happens when these three complex adaptive systems are brought together.

Evolutionary computing is a powerful tool for studying the origins and evolution of music. In this case, music is studied as an adaptive complex dynamic system and its origins and evolution are studied in the context of the cultural conventions that may emerge under a number of constraints (e.g. psychological, physiological and ecological). This paper introduces three case studies of evolutionary modelling of music. It begins with a model for studying the role of mating-selective pressure in the evolution of musical taste. Here the agents evolve ``courting tunes'' in a society of ``male'' composers and ``female'' critics. Next, a mimetic model is introduced to study the evolution of musical expectation in a community of autonomous agents furnished with a vocal synthesizer, a hearing system and memory. Finally, an iterated learning model is proposed for studying the evolution of compositional grammars. In this case, the agents evolve grammars for composing music to express a set of emotions.

Language is culturally transmitted. Iterated Learning, the process by which the output of one individual's learning becomes the input to other individuals' learning, provides a framework for investigating the cultural evolution of linguistic structure. We present two models, based upon the Iterated Learning framework, which show that the poverty of the stimulus available to language learners leads to the emergence of linguistic structure. Compositionality is language's adaptation to stimulus poverty.

Language arises from the interaction of three complex adaptive systems -- biological evolution, learning, and culture. We focus here on cultural evolution, and present an Iterated Learning Model of the emergence of compositionality, a fundamental structural property of language. Our main result is to show that the poverty of the stimulus available to language learners leads to a pressure for linguistic structure. When there is a bottleneck on cultural transmission, only a language which is generalizable from sparse input data is stable. Language itself evolves on a cultural time-scale, and compositionality is language's adaptation to stimulus poverty.

How and where are the universal features of language specified? We consider language users as situated agents acting as conduits for the cultural transmission of language. Using multi-agent computational models we show that certain hallmarks of language are adaptive in the context of cultural transmission. This observation requires us to reconsider the role of innateness in explaining the characteristic structure of language. The relationship between innate bias and the universal features of language becomes opaque when we consider that significant linguistic evolution can occur as a result of cultural transmission.

As language users humans possess a culturally transmitted system of unparalleled complexity in the natural world. Linguistics has revealed over the past 40 years the degree to which the syntactic structure of language in particular is strikingly complex. Furthermore, as Pinker and Bloom point out in their agenda-setting paper Natural Language and Natural Selection ``grammar is a complex mechanism tailored to the transmission of propositional structures through a serial interface'' (Pinker and Bloom, 1990, 707). These sorts of observations, along with influential arguments from linguistics and psychology about the innateness of language (see, e.g. Chomsky, 1986; Pinker, 1994), have led many authors to the conclusion that an explanation for the origin of syntax must invoke neo-Darwinian natural selection.

``Evolutionary theory offers clear criteria for when a trait should be attributed to natural selection: complex design for some function, and the absence of alternative processes capable of explaining such complexity. Human language meets these criteria.'' (Pinker and Bloom, 1990, 707)

Since Pinker and Bloom made these arguments there have been many attempts to put forward a coherent evolutionary story that would allow us to derive known features of syntax from communicative selection pressures (e.g. Nowak, Plotkin, and Jansen, 2000; Newmeyer, 1991 and discussion in Kirby, 1999a). One problem with this approach to evolutionary lin- guistics is that it often fails to take into account that biological natural selection is only one of the complex adaptive systems at work.

Language emerges at the intersection of three complex adaptive systems:

• Learning: During ontogeny children adapt their knowledge of language in response to the environment in such a way that they optimise their ability to comprehend others and to produce comprehensible utterances.
• Cultural evolution: On a historical (or glossogenetic) timescale, languages change. Words enter and leave the language, meanings shift, and phonological and syntactic rules ad- just.
• Biological evolution: The learning (and processing) mechanisms with which our species has been equipped for language, adapt in response to selection pressures from the environ- ment, for survival and reproduction.

There are two problems with this multiplicity of dynamical systems involved in linguistic evolution. Firstly, we understand very little about how learning, culture, and evolution inter- act (though, see Belew, 1990; Kirby and Hurford, 1997; Boyd and Richerson, 1985), partly because language is arguably the only sophisticated example of such a phenomenon. There clearly are interactions: for example, biological evolution provides the platform on which learning takes place, what can be learnt influences the languages that can persist through cultural evolution, and the structure of the language of a community will influence the selec- tion pressures on the evolving language users (see figure 1).

Secondly, it is not clear what methodology we should use to study this problem. Mathe- matical techniques for looking at the interaction of dynamical systems and linguistic behaviour are in their infancy (though, Nowak, Komarova, and Niyogi, 2001, take a potentially valuable approach). We feel that computational modelling is currently the most appropriate method- ology, but although simulations of language learning have a long history, and there are many methods from the A-life field that can be used for modelling evolution, models of the cultural transmission of learned behaviour are relatively sparse (see Steels, 1997 for a review). This is unfortunate, since we will argue in this chapter that it is through this particular mechanism that the most basic features of human language syntactic structure can be explained.

To remedy this situation, we introduce here the Iterated Learning Model (ILM), a gen- eral approach to exploring the transmission over a glossogenetic timescale of observationally learned behaviour. We will illustrate the ILM with a few examples of simulations that lead to two conclusions:

• There is a non-trivial mapping between the set of learnable languages (i.e. the lan- guages allowed by our innate language faculty), and the set of stable languages (i.e., the languages we can actually expect to see in the world).
• Under certain circumstances, cultural evolution leads inevitably to recursively compo- sitional (i.e., syntactic) languages.

Human language is a unique natural communication system for two rea- sons. Firstly, the mapping from meanings to signals in language has structural properties that are not found in any other animal's communi- cation systems. In particular, syntax gives us the ability to produce an in nite range of expressions through the dual tools of compositionality and recursion. Compositionality is defined here as the property whereby an expression's meaning is a function of the meanings of parts of that expression and the way they are put together. Recursion is a property of languages with finite lexica and rule-sets in which some constituent of an expression can contain a constituent of the same category. Together with recursion, compositionality is the reason that this in finite set of expressions can be used to express different meanings.

Secondly, at least some of the content of this mapping is learned by children through observation of others' use of language. This seems not to be true of most, maybe all, of animal communication (see review in Oliphant, this volume). In this chapter I formally investigate the interaction of these two unique properties of human language: the way it is learned and its syntactic structure.

This paper aims to show that linguistics, in particular the study of the lexico-syntactic aspects of language, provides fertile ground for artificial life modelling. A survey of the models that have been developed over the last decade and a half is presented to demonstrate that ALife techniques have a lot to offer an explanatory theory of language. It is argued that this is because much of the structure of language is determined by the interaction of three complex adaptive systems: learning, culture and biological evolution. Computational simulation, informed by theoretical linguistics, is an appropriate response to the challenge of explaining real linguistic data in terms of the processes that underpin human language.

Many artificial life researchers stress the interdisciplinary character of the field. Against such a backdrop, this report reviews and discusses artificial life, as it is depicted in, and as it interfaces with, adjacent disciplines (in particular, philosophy, biology, and linguistics), and in the light of a specific historical example of interdisciplinary research (namely cybernetics) with which artificial life shares many features. This report grew out of a workshop held at the Sixth European Conference on Artificial Life in Prague and features individual contributions from the workshop's eight speakers, plus a section designed to reflect the debates that took place during the workshop's discussion sessions. The major theme that emerged during these sessions was the identity and status of artificial life as a scientific endeavor.

Recent work in the field of computational evolutionary linguistics suggests that the dynamics arising from the cultural evolution of language can explain the emergence of syntactic structure. We build on this work by introducing a model of language acquisition based on the Minimum Description Length Principle. Our experiments show that compositional syntax is most likely to occur under two conditions specific to hominids: (i) A complex meaning space structure, and (ii) the poverty of the stimulus.

A computationally implemented model of the transmission of linguistic behavior over time is presented. In this iterated learning model (ILM), there is no biological evolution, natural selection, nor any measurement of the success of the agents at communicating (except for results-gathering purposes). Nevertheless, counter to intuition, significant evolution of linguistic behavior is observed. From an initially unstructured communication system (a protolanguage), a fully compositional syntactic meaning-string mapping emerges. Furthermore, given a nonuniform frequency distribution over a meaning space and a production mechanism that prefers short strings, a realistic distribution of string lengths and patterns of stable irregularity emerges, suggesting that the ILM is a good model for the evolution of some of the fundamental features of human language.

How can we explain the origins of our uniquely human compositional system of communication? Much of the recent work tackling this problem (e.g Bickerton 1990; Pinker & Bloom 1990; Newmeyer 1991; Hurford et al. 1998) explicitly attempts to relate models of our innate linguistic endowment with neo-Darwinian evolutionary theory. These are essentially functional stories, arguing that the central features of human language are genetically encoded and have emerged over evolutionary time in response to natural selection pressures.

In this paper I put forward a new approach to understanding the origins of some of the key ingredients in a syntactic system. I show, using a computational model, that compositional syntax is an inevitable outcome of the dynamics of observationally learned communication systems. In a simulated population of individuals, language develops from a simple idiosyncratic vocabulary with little expressive power, to a compositional system with high expressivity, nouns and verbs, and word order expressing meaning distinctions. This happens without natural selection of learners --- indeed, without any biological change at all --- or any notion of function being built into the system.

This approach does not deny the possibility that much of our linguistic ability may be explained in terms of natural selection, but it does highlight the fact that biological evolution is by no means the only powerful adaptive system at work in the origins of human language.

Function, Selection, and Innateness is a powerful demonstration of the value of looking at language as an adaptive system, which reaches the heart of debates in linguistics and cognitive science on the evolution and nature of language. Why are all languages alike in some ways, different in others? Why do languages change? How did they originate and evolve? Kirby argues these questions must be studied together. He combines functional and formal theories in order to develop a way of treating language as an adaptive system in which its communicative and formal roles have crucial and complimentary roles. He then uses computational models to show what universals emerge given a particular theory of language use or acquisition.

TABLE OF CONTENTS
1 A Puzzle of Fit
2 The Impact of Processing on Word Order
3 Hierarchies and Competing Motivations
4 The Limits of Functional Adaptation
5 Innateness and Function in Linguistics
6 Conclusion

There is evidence for increase, followed by decline, in synaptic numbers during development. Dendrites do not function in isolation. A constructive neuronal process may underpin a selectionist cognitive process. The environment shapes both ontogeny and phylogeny. Phylogenetic natural selection and neural selection are compatible. Natural selection can yield both constructivist and selectionist solution to adaptuive problems.

A central topic for linguistic theory is the degree to which the communicative function of language influences its form. In particular many so-called functional explanations argue that cross-linguistic constraints can be explained with reference to pressures imposed by processing. In apparent opposition to this is the innatist stance which claims that universals are properties imposed by an autonomous language module. This thesis approaches the issues raised by this conflict by examining the nature of the link between processing and universals. The starting point for the work, then, is not the discovery of new universals nor new explanations, but the question ``exactly how do processing theories that have been proposed give rise to the universals that they claim to explain?'' Careful investigation of this problem proves to be fruitful in highlighting the roles of innateness and function in explaining universals.

The methodology chosen involves computational simulations of language as a complex adaptive system, in which language universals appear as emergent properties of the dynamics of the system and the influence of processing on use. This influence is characterised as a differential selection of competing variant forms. The simulation approach is first used to demonstrate the plausibility of a recent parsing explanation for word order universals. An extension of the model to deal with hierarchical universals relating to relative clauses leads to the conclusion that current explanations of hierarchies in general are incomplete. Instead, it is argued that implicational hierarchies are the result of competing processing pressures, in particular between morphological and parsing complexity.

Further examination of relative clause processing and universals leads to an apparent flaw in the approach put forward. It is noted that not all processing pressures appear to show up as universals, challenging the explanatory adequacy of the functional explanations. Instead, it is shown that a complete characterisation of language as an adaptive system requires there to be an innate, autonomous syntactic component to language. This leads to the conclusion that universals arise from the interaction of processing constraints and constraints imposed on the adaptive process by an innate language acquisition device. Moreover, the possibility of processing directly influencing this innate faculty without violating its autonomy is investigated with reference to recent work on the biological evolution of language.

This thesis therefore espouses a perspective on the explanation of language universals in which processing complexity and autonomous syntactic constraints have crucial and complementary roles.