Language Evolution and Computation Bibliography

The topics dealt with in this thesis are all part of the general problem of social consensus, namely how a convention flourish and decay and what motivates people to conform to it. Examples range from driving on the right side of the street, to language, rules of courtesy or moral judgments. Some conventions arise directly from the need to coordinate or conform, such as fashion or speaking the same language, others, instead, apply to situations where there is a tension between individual and collective interest, such as cooperation, reciprocity, etc. This thesis is developed around three main questions still open in the research field of collective human behavior: how coexistence of concurrent conventions is possible, why cooperation in real systems is more common than predicted and how a population undergoes collective behavioral change, namely how an initially minority norm can supplant a majority ones. In the first work, we study the impact of concurrent social pressures in consensus processes. We propose a model of opinion competition where individuals participate in different social networks and receive conflicting social influences. The dynamics take place in two distinct domains, which we model as layers of a multiplex network. The novelty of our study lies to the fact that individuals can have different options in the different layers. This naturally reflects a common situation where an individual can possess some different opinions in different social contexts as a result of consensus with other individuals in the one context but not in the other. Our analysis shows that the latter property enriches the system’s dynamics and allows not only for consensus into a single state for both layers, but also for active dynamical states of coexistence of both options. In the second model, we analyze the influence of opinion dynamic in competitive strategical games. Cooperation between humans is quite common and stable behavior even in situations where both game theory and experiments predict defection prevalence. One of the reasons could be just the fact that individuals engaging in strategic interactions are also exposed to social influence and, consequently, to the spread of opinions. We present a new evolutionary game model where game and opinions dynamics take place in different layers of a multiplex network. We show that the coupling between the two dynamical processes can lead to cooperation in scenarios where the pure game dynamics predicts defection and, in some particular setting, gives rise to a metastable state in which nodes that adopt the same strategy self-organize into local groups. In the last work, we present the first extensive quantitative analysis of the phenomenon of norm change by looking at 2,365 orthographic and lexical norms shifts occurred in English and Spanish over the last two centuries as recorded by millions of digitized books. We are able to identify three distinct patterns in the data depending on the nature of the norm shift. Furthermore, we propose a simple evolutionary model that captures all the identified mechanisms and reproduces quantitatively the transitions between norms. This work advances the current understanding of norm shifts in language change, most often limited to qualitative illustrations (e.g., the observation that adoption curve of the new norm follows an ‘S-shaped’ behavior.

This dissertation advances our understanding of the roles played by pragmatic and grammatical competence in theories of language change by using mathematical and statistical methods to analyze the cross-linguistic change in the expression of negation known as Jespersen's cycle. In the history of Middle English this change is characterized by two transitions: from pre-verbal ne to an initially emphatic embracing ne...not; from embracing ne...not to post-verbal not. This description conflates two often related process: the formal cycle describes changes in the forms of negation available and consists of the transitions from pre-verbal to embracing to post-verbal negation; the functional cycle describes changes in how forms are used to signal meaning and consists of the transition from pre-verbal to embracing negation. Using tools from evolutionary game theory, we show that the functional cycle can be explained by limits on our pragmatic competence. The incoming embracing form is initially restricted to negating propositions that are common information between interlocutors. But, experimental evidence shows that speakers have difficulty in distinguishing common and privileged information. Speakers use the initially restricted form in more and more contexts that are less and less closely tied to the discourse, and it undergoes a kind of informational bleaching. Applying statistical methods developed in population genetics, we show that grammatical competence, and the process of acquisition through which it is formed, predict stability rather than change in both transitions of the formal cycle unless the observed transitions are the result of the accumulation of small random changes akin to genetic drift in finite populations. We show that we can reject this possibility in the first transition of the formal cycle, but not in the second. The possibility of random change in the second transition of the formal cycle offers some insight into the varying amount of time it takes across languages. The main contribution of this dissertation is demonstrating the need for articulated models of both pragmatic and grammatical competence in explanatory theories of language change, while also offering a set of tools and methods for analyzing different factors in historical corpora. https://repository.upenn.edu/edissertations/1578

“The meaning of a word is its use in the language”. In the first half of the 20th century Ludwig Wittgenstein introduced this idea into philosophy and especially in the last few decades, related disciplines such as psychology and linguistics started embracing the view that that natural language is a dynamic system of arbitrary and culturally learnt conventions. From the end of the nineties on, researchers around Luc Steels transferred this notion of communication to the field of artificial intelligence by letting software agents and later robots play so-called language games in order to self-organize communication systems without requiring prior linguistic or conceptual knowledge. Continuing and advancing that research, the work presented in this thesis investigates lexicon formation in humanoid robots, i.e. the emergence of shared lexical knowledge in populations of robotic agents. Central to this is the concept of referential uncertainty, which is the difficulty of guessing a previously unknown word from the context. First in a simulated environments and later with physical robots, this work starts from very simple lexicon formation models and then systematically analyzes how an increasing complexity in communicative interactions leads to an increasing complexity of representations and learning mechanisms. We evaluate lexicon formation models with respect to their robustness, scaling and their applicability to robotic interaction scenarios and one result of this work is that the predominating approaches in the literature do not scale well and are not able to cope with the challenges stemming from grounding words in the real-world perceptions of physical robots. In order to overcome these limitations, we present an alternative lexicon formation model and evaluate its performance.

In the present thesis, first, the principle of center-embedded (CE) recursion is explained. Next, we briefly discuss animal studies on recursion learning, followed by a section with theories and experimental evidence about human learning. Here, the complexity of the principle is contrasted with pragmatic learning strategies. Then, we discuss the features of the input that might help recursion learning. Finally, we discuss the methodological issues regarding the use of artificial language to study aspects of natural language learning.

Language is one of the most prominent examples of complex systems. It is one of the basic tools of humanity, and yet many of its aspects still puzzle a broad range of scientists. The phenomena underlying the emergence and evolution of language, as well as cultural change, have been subject to increased interest from the physics community over the past two decades. We begin this work by discussing a number of mathematical and computational models of language dynamics.

Many of the world's languages display a preferred ordering of subject, object and verb, known as that language's basic word order. There are six logically possible basic word orders, and while each occurs in at least one known language, not all are found equally frequently. Some are extremely rare, while others are used by almost half the world's languages. This highly non-uniform cross-linguistic distribution of basic orders is a fundamental explanatory target for linguistics. This thesis tackles this problem from a psychological perspective. It constitutes an advance over previously proposed explanations in that it is compatible not only with the distributions observed today, but with what is known of broad trends in the word order change which happen over hundreds of years. There are two largely independent components of the explanation given in this thesis, which is necessary to be compatible with both synchronic and diachronic evidence. The first component is focused on the structures which the human mind uses to represent the meanings of sentences. While mental representations of meaning are not inherently serial (hence ordered) like spoken language, we can think of the different components in these representations as being ordered in a different sense, based on some components being more accessible to cognitive processing than others. This thesis develops the idea that the word order used most often in the earliest human languages, which are taken to rely on a direct interface between mental representations and motor control systems, were determined by a "word order of the language of thought". The second component is focused on the functional adequacy of different word orders for high speed, reliable communication. The driving idea here is that human language represents a rational solution to the problem of communication. The mathematical formalism of information theory is used to determine the gold standard for solutions to this problem, and this is used to derive a ranking of word orders by functionality. This thesis develops a novel perspective on word order functionality in which cross-linguistic preferences are ultimately a reflection of statistical properties of the events which languages describe.

Storytelling, both factual and fictional, is a universal, cross-cultural phenomenon, largely characterised by one or more intentional agents interacting with unexpected events. Frequently, the protagonist achieves his or her goal, resolving the tension created by the unexpected event. The form of the story—both in conversational event reporting and fictional literature—has undergone cultural evolution to attract attention from others, and as such reflects human cognitive biases. It has been hypothesised that language evolved in part to advertise biological relevance through narrative style event reporting. Thus, it is conceivable that human language and intelligence evolved out of a need to advertise and recognise resourceful individuals. Evolutionary theories of Machiavellian intelligence in early humans support this position. The present study partially replicates Mesoudi et al.’s (2006) transmission chain study, which showed that participants more accurately remember stories about social interactions than stories about individual agents. It was concluded that humans have an evolved bias for social information, but not specifically gossip-like information. The present study hypothesised that the individual information did poorly because its protagonist failed to achieve her goal, while she was unexpectedly successful in the social narratives. While there was no significant difference discovered between successful and unsuccessful individual stories, there was also no clear distinction in recall accuracy between social and non-social stories, and gossip was recalled with far greater accuracy than the social story. These results suggest that while humans most likely do have a social bias, other narrative factors such as unexpectedness and high-stakes vs. low stakes scenarios also come into play.

[Masters Thesis] Compositionality, a unique and fundamental property of human language, emerges from the pressures placed on language as it is learnt and used by consecutive generations – the pressure for learnability, arising from the transmission process, and a pressure for expressivity imposed by the use of language to convey meaning. This study uses human diffusion chains to explore the contribution that learning and communication make to the cultural evolution of linguistic structure. Languages are exposed to either a learning pressure, a communication pressure, or both. The language in the communication chain became expressive and showed varying degrees of structure, in some cases deliberately introduced as an aid to comprehension. This puts the focus back on the cognitive processes of language users, and emphasises the role of recipient design in the emergence of structure in language. The languages in the learning conditions struggled to maintain a significant degree of structure, contrary to expectations. However, the development of the languages provides clues about the way that language adapts in response to the particular communicative and learning environment.

[Masters Thesis] This dissertation presents the results of a series of simulations intended to expand the findings of Burkett and Griffiths (2009, 2010), whose model is shown to make a number of assumptions that may be unrealistic with regard to human language learners. These assumptions are modified to create a number of more realistic scenarios. A series of simulations shows that the concentration parameter if continues to affect the outcome of iterated learning with Bayesian learners in these new scenarios. To overcome the need for the concentration parameter to be specified by the modeller, a model is presented where agents learn a complex hypothesis composed of both a distribution of languages within a population and the appropriate value for. The outcome of the simulations based on this model are inconclusive but do hint at the possibility of _ being affected by iterated learning, potentially enabling learners to acquire a complex hypothesis.

The sound inventories of the world's languages show a considerable extent of symmetry. It has been postulated that this symmetry is a reflection of the human physiological, cognitive and societal factors. There have been a large number of linguistically motivated studies in order to explain the self-organization of these inventories that arguably leads to the emergence of this symmetry. A few computational models in order to explain especially the structure of the smaller vowel inventories have also been proposed in the literature. However, there is a need for a single unified computational framework for studying the self-organization of the vowel as well as other inventories of complex utterances like consonants and syllables.

In this thesis, we reformulate this problem in the light of statistical mechanics and present complex network representations of these inventories. The central objective of the thesis is to study and explain the self-organization and emergence of the consonant inventories. Nevertheless, in order to demonstrate the versatility of our modeling methodology, we further apply it to investigate and detect certain interesting properties of the vowel inventories.

Two types of networks are considered - a language-consonant bipartite network and a consonant-consonant co-occurrence network. The networks are constructed from the UCLA Phonological Segment Inventory Database (UPSID). From the systematic analysis of these networks we find that the occurrence and co-occurrence of the consonants over languages follow a well-behaved probability distribution. The co-occurrence network also exhibits a high clustering coefficient. We propose different synthetic models of network growth based on preferential attachment so as to successively match with higher accuracy the different statistical properties of the networks. Furthermore, in order to have a deeper understanding of the growth dynamics we analytically solve the models to derive expressions for the emergent degree distribution and clustering coefficient. The co-occurrence network also exhibits strong community structures and a careful inspection indicates that the driving force behind the community formation is grounded in the human articulatory and perceptual factors. In order to quantitatively validate the above principle, we introduce an information theoretic definition of this factor feature entropy and show that the natural language inventories are significantly different in terms of this quantity from the randomly generated ones. We further construct similar networks for the vowel inventories and study various interesting similarities as well as differences between them and the consonant inventories.

To summarize, this thesis shows that complex networks can be suitably used to study the self-organization of the human speech sound inventories. In this light, we deem this computational framework as a highly powerful tool in future for modeling and explaining the emergence of many other complex linguistic phenomena.

For a long time, human language has been assumed to be genetically determined and therefore the product of biological evolution. It is only within the last decade that researchers have begun to investigate more closely the domain-general cognitive mechanisms of cultural evolution as an alternative explanation for the origins of language. Most of this more recent work focuses on the role of imperfect cultural transmission and abstracts away from the mechanisms of communication. Specifically, models developed to study the cultural evolution of language ''both theoretical and computational ''often tacitly assume that linguistic signals fully specify the meaning they communicate. They imply that ignoring the fact that this is not the case in actual language use is a justified idealisation which can be made without significant consequences. In this thesis, I show that by making this idealisation, we miss out on the extensive explanatory potential of an empirically attested property of language: its pragmatic plasticity. The meaning that a signal comes to communicate in a specific context usually differs to a certain degree from its conventional meaning. This thesis (i) introduces a model of the cultural evolution of language that acknowledges and incorporates the fact that communication exhibits pragmatic plasticity and (ii) explores the explanatory potential of this fact with regard to language evolution.

The thesis falls into two parts. In the first part, I develop the model conceptually. I begin by analysing the components of extant models of general cultural evolution and discuss how models of language change and linguistic evolution map onto them. Innovative use is identified as the motor of cultural evolution. I then conceptualise the cognitive mechanisms underlying innovative language use and argue that they originate in pre-linguistic forms of ostensive-inferential communication. In a next step, the identified mechanisms are employed to provide a unified account of the two main explananda of evolutionary linguistics, the emergence of symbolism and the emergence of grammar. Finally, I discuss the implications of the presented analysis for the so-called proto-language debate. In the second part of the thesis, I propose a computational implementation of the developed conceptual model. This computational implementation allows for the simulation of the cultural emergence and evolution of symbolic communication and provides a laboratory-like environment to study individual aspects of this process. I employ such computer simulations to explore the role that pragmatic plasticity plays in the development of the expressivity, signal economy and ambiguity of emerging and evolving symbolic communication systems.

As its main contribution to the study of language evolution, this thesis shows that a model of linguistic cultural evolution that incorporates the notion of pragmatic plasticity has the potential to explain two crucial evolutionary puzzles, namely (i) how language can emerge from no language, and (ii) how language can come to exhibit the appearance of design for communication. The proposed usage-based model of language evolution bridges the evolutionary gap between no language and language by identifying ostensive-inferential communication as the continual aspect present in both stages, and by demonstrating that the cognitive mechanisms involved in ostensive-inferential communication are sufficient for the transition from one stage to the other.

Pragmatics is the branch of linguistics that addresses the relationship between language and its external environment `` in particular the communicative context. Social evolution (or sociobiology) is the branch of the biological sciences that studies the social behaviour of organisms, particularly with respect to the ecological and evolutionary forces with which it must interact. These two disciplines thus share a natural epistemic link, one that is concerned with the relationship between behaviour and the environment. There has, however, historically been no dialogue between them. This thesis attempts to fill that void: it examines pragmatics from the perspective of social evolution theory. Chapter 1 gives a brief introduction to the two fields and their key ideas, and also discusses why an evolutionary understanding of pragmatics is crucial to the study of language origins.

In chapter 2 the vexed question of the biological function of language is discussed. Responses are given to the claims, common in the evolutionary linguistics literature, that the processes of exaptation, self organisation and cultural transmission provide alternatives to natural selection as a source of design in nature. The intuitive conclusion that the function of language is communication is provisionally supported, subject to a proper definition of communication.

Chapter 3 reviews previous definitions and consequently argues for an account predicated on the designedness of signals and responses. This definition is then used to argue that an evolutionarily coherent model of language should recognise the pragmatic realities of ostension and inference and reject the code like idealisation that is often used in its place.

Chapter 4 observes that this fits the argument that the biological function of language is communication and then addresses the key question faced by all evolved communication systems `` that of evolutionary stability. The human capacity to record and remember the past behaviour of others is seen to be critical.

Chapter 5 uses the definition of communication from chapter 3 to describe a very general model of evolved communication, and then uses the constraints of that model to argue that Relevance Theory, or at least some theory of pragmatics with a very similar logical structure, must be correct.

Chapter 6 then applies the theoretical apparatus constructed in chapters 2 to 5 to a crucial and topical issue in evolutionary linguistics: the emergence of learnt, symbolic communication. It introduces the Embodied Communication Game, an experimental tool whose basic structure is significantly informed by both social evolutionary and, in particular, pragmatic theory. The novelty of the game is that participants must find a way to communicate not just the content that they wish to convey, but also the very fact that a given behaviour is communicative in nature, and this constraint is found to fundamentally influence the type of system that emerges.

Chapter 7, which concludes the thesis, recounts and clarifies what it tells us about the origins and evolution of language, and suggests a number of possible avenues for future research.

Case languages use an inflectional category system for marking event structure. The research in this thesis investigates how such a grammatical system can be developed as the consequence of distributed processes whereby language users continuously shape and reshape their language in locally situated communicative interactions. Since these processes are notoriously difficult to grasp in natural languages, this thesis offers additional evidence from computational simulations in which autonomous artificial agents self-organise a case-like grammar with similar properties as found in case languages such as German, Latin and Turkish.

This thesis hypothesises that language users gradually build their grammar in order to optimise their communicative success and expressiveness while at the same time reducing the cognitive effort needed for semantic interpretation. In the experiments, artificial agents engage in a series of `language games' in which the speaker has to describe a dynamic event to the hearer. The agents are equipped with diagnostics for autonomously detecting communicative problems, repair strategies for solving these problems, and alignment strategies for coordinating their linguistic inventories with each other. Through comparative simulations, this thesis aims at demonstrating which communicative and external pressures and which cognitive mechanisms are minimally required for the formation of a case grammar.

Two innovating experiments are reported. The first experiment offers the first multi-agent simulations ever that involve polysemous categories. The agents are capable of inventing grammatical markers for indicating event structure and of generalising these markers to semantic roles by performing analogical reasoning over events. Extension by analogy occurs as a side-effect of the need to optimise communicative success and is accompanied by careful abstraction, which yields an increased productivity of the categories. In the second experiment, the agents are capable of combining markers into larger argument structure constructions through pattern formation. The results show that languages become unsystematic if the linguistic inventory is unstructured and contains multiple levels of organisation. This thesis demonstrates that this problem of systematicity can be solved using multi-level selection.

All the experiments are implemented in Fluid Construction Grammar. This thesis presents the first computational formalisation of argument structure in a construction-based approach that works for both production and parsing. It implements the `fusion' of the participant roles of events with the semantic roles of argument structure constructions. This representation aims at maximal fluidity and introduces some novel concepts in linguistics. Instead of containing a fixed predicate frame, verbs list their `potential valents' from which the `actual valency' is selected by argument structure constructions.

Even though the experiments involve the formation of artificial languages, the results are highly relevant for natural language research as well. This thesis therefore engages in an interdisciplinary dialogue with linguistics and contributes to some currently ongoing debates such as the formalisation of argument structure in construction grammar, the organisation of the linguistic inventory, the status of semantic maps and thematic hierarchies and the mechanisms for explaining grammaticalization.

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.

This thesis inquires into how human language relates to morality -- and shows the ways language enables, extends, and maintains human value systems. Though we ultimately need to view the relation between language and morality from many different perspectives -- biological, psychological, sociological, and philosophical -- the approach here is primarily a linguistic one informed by evolutionary theory.

At first, this study shows how natural selection relates to the problem of altruism and how language serves human moral ontogeny. Subsequently, the argument demonstrates how language helps enable cultural group selection. Moreover, as language helps influence human behavior in an altruistic direction beyond in-group non-kin (helping facilitate cultural group selection), we also consider how language can help facilitate altruistic behavior towards out-group non-kin. This therefore raises the prospect of a limited moral realism in a world of evolutionary processes.

With these issues and possibilities in mind, we consider and analyze the properties of language that help extend human morality. Specifically, discussion covers how recursion, linguistic creativity, naming ability, displacement, stimulus freedom, compositionality, cultural transmission, and categorization extend moral systems. Moreover, because language so broadly influences morality, the inquiry extends into how linguistic differences (specifically between English and Japanese) might also cause subtle differences in moral perception between Japanese and English speakers.

Lastly, we consider how moral ideas might take on a life of their own, catalytically propagating in degrees dependent and independent of human intention. That is, we consider how ideas might become memetic. After considering the serious problems of memetics, this approach employs a linguistic version of memetic theory and considers how psychological, social, and linguistic constraints may cause moral memes to attain a memetic state and spread by an independent or semi-independent replicator dynamic. Thus, some moral ideas that we possess through language may actually possess us.

This thesis investigates the evolutionary plausibility of the Minimalist Program. Is such a theory of language reasonable given the assumption that the human linguistic capacity has been subject to the usual forces and processes of evolution? More generally, this thesis is a comment on the manner in which theories of language can and should be constrained. What are the constraints that must be taken into account when constructing a theory of language? These questions are addressed by applying evidence gathered in evolutionary biology to data from linguistics.

The development of generative syntactic theorising in the late 20th century has led to a much redesigned conception of the human language faculty. The driving question - `why is language the way it is' - has prompted assumptions of simplicity, perfection, optimality, and economy for language; a minimal system operating in an economic fashion to fit into the larger cognitive architecture in a perfect manner. Studies in evolutionary linguistics, on the other hand, have been keen to demonstrate that language is complex, redundant, and adaptive, Pinker & Bloom's (1990) seminal paper being perhaps the prime example of this. The question is whether these opposing views can be married in any way.

Interdisciplinary evidence is brought to bear on this problem, demonstrating that any reconciliation is impossible. Evolutionary biology shows that perfection, simplicity, and economy do not arise in typically evolving systems, yet the Minimalist Program attaches these characteristics to language. It shows that evolvable systems exhibit degeneracy, modularity, and robustness, yet the Minimalist Programmust rule these features out for language. It shows that evolution exhibits a trend towards complexity, yet the Minimalist Program excludes such a depiction of language.

By determining where language falls in each of these three cases, the choice between the opposing positions of gradual adaptive evolution and the Minimalist Program is resolved. Language is shown to be imperfect, uneconomic, and non-optimal, and hence a typical biological system. Language is shown to exhibit the key features of evolvability, and hence accords with the usual pressures and constraints of evolution. Language is shown to be both complex and adaptive, and hence amenable to a gradual adaptive evolutionary account.

In addition, the uniqueness of the pivotal property of language according to one minimalist evolutionary account - recursion - is examined, its place as just one of a collection of properties which make language special illustrating that language is significantly more complex and sophisticated than the Minimalist Program allows. Finally, significant flaws in the details of minimalist theories themselves - including extraneous operations, and unmotivated and stipulative features - are uncovered, further signalling that the perfection, simplicity, and economy that minimalism advocates is not a valid characterisation of language.

The mental lexicon is a complex structure organised in terms of phonology, semantics and syntax, among other levels. In this thesis I propose that this structure can be explained in terms of the pressures acting on it: every aspect of the organisation of the lexicon is an adaptation ultimately related to the function of language as a tool for human communication, or to the fact that language has to be learned by subsequent generations of people. A collection of methods, most of which are applied to a Spanish speech corpus, reveal structure at different levels of the lexicon. ...

The origins of human language, with its extraordinarily complex structure and multitude of functions, remains among the most challenging problems for evolutionary biology and the cognitive sciences. Although many will agree progress on this issue would have important consequences for linguistic theory, many remain sceptical about whether the topic is amenable to rigorous, scientific research at all. Complementing recent developments toward better empirical validation, this thesis explores how formal models from both linguistics and evolutionary biology can help to constrain the many theories and scenarios in this field.

I first review a number of foundational mathematical models from three branches of evolutionary biology -- population genetics, evolutionary game theory and social evolution theory -- and discuss the relation between them. This discussion yields a list of ten requirements on evolutionary scenarios for language, and highlights the assumptions implicit in the various formalisms. I then look in more details at one specific step-by-step scenario, proposed by Ray Jackendoff, and consider the linguistic formalisms that could be used to characterise the evolutionary transitions from one stage to the next. I conclude from this review that the main challenges in evolutionary linguistics are to explain how three major linguistic innovations -- combinatorial phonology, compositional semantics and hierarchical phrase-structure -- could have spread through a population where they are initially rare.

In the second part of the thesis, I critically evaluate some existing formal models of each of these major transitions and present three novel alternatives. In an abstract model of the evolution of speech sounds (viewed as trajectories through an acoustic space), I show that combinatorial phonology is a solution for robustness against noise and the only evolutionary stable strategy (ESS). In a model of the evolution of simple lexicons in a noisy environment, I show that the optimal lexicon uses a structured mapping from meanings to sounds, providing a rudimentary compositional semantics. Lexicons with this property are also ESS's. Finally, in a model of the evolution and acquisition of context-free grammars, I evaluate the conditions under which hierarchical phrase-structure will be favoured by natural selection, or will be the outcome of a process of cultural evolution.

In the last chapter of the thesis, I discuss the implications of these models for the debates in linguistics on innateness and learnability, and on the nature of language universals. A mainly negative point to make is that formal learnability results cannot be used as evidence for an innate, language-specific specialisation for language. A positive point is that with the evolutionary models of language, we can begin to under- stand how universal properties and tendencies in natural languages can result from the intricate interaction between innate learning biases and a process of cultural evolution over many generations.

The origins of language have become a hotly debated topic in the last decade. Researchers from many fields have been trying to explain them using the tools that their specialisations provide. Also in Artificial Intelligence their has been interest in the topic, and computer science provides a very powerful tool for studying language as a complex dynamical system: multi-agent systems. In the thesis, we present four models based on the ``Language Game'' paradigm developed by Luc Steels for studying language. We support a gradualist view of the evolution of language, and we provide partial answers to three issues that need to be clarified in order to strengthen this position: (1) each stadium of the developing communication system must be viable and successful in its own right; (2) their must be a path from each intermediate communication system to the next; and (3) the users of the communication systems must be able to transition from one system to the next using only local data. Three models describe intermediate communication systems: a system in which the agents can exchange single words referencing one referent; a system in which the agents can exchange several words referencing one referent; and a system in which the agents can exchange complex, structured utterances referencing several referents. Experiments with these systems show that each system is a successful communication system in its own right. The fourth model attempts to show that the agents can make the transition from one communication system to the next successfully and on their own. Agents in this system have the cognitive capacities for two systems: (1) and (2), and have internal pressures that can push either of the communication systems as the one to use, based on different criteria. Two criteria push the agents from system (1) to system (2), yielding interesting results. The models and experiments in the thesis give positive results for each of the issues to be clarified, thereby supporting the gradual evolution hypothesis.

This thesis proposes a framework adopting the self-organization theory for the study of language evolution. Self-organization explains collective behaviors and evolution with the observation that the patterns at the global level in a complex system are often properties spontaneously emergent from the numerous local interactions among the individual components, and they cannot be understood by only examining the individual components.

Language can be viewed as such emergent properties instead of products from some innate blueprint in humans. We highlight the importance of recognizing language at two distinctive but inter-dependent levels of existence, i.e. in the idiolect and in the communal language, and a self-organizing process existing at each of the two levels. It is necessary to clarify what phenomena are properties of the idiolects, and what properties are the collective behaviors at the population level.

In linguistics, however, very often an abstract language system is taken as the object of analysis. This level of analysis disregards the distinction between idiolect and communal language, and neglects the heterogeneous nature of language at both levels. As a consequence, explanations for observed patterns based on this abstract level of analysis are often inadequate. However, this is a necessary step for linguists to identify interesting phenomena in the first place. At this abstract level of analysis, the self-organization framework can also be applied. It is assumed that the abstract language system self-organizes. A study on homophony in languages is taken as an example to illustrate the analysis at this level. It is shown that the existence of homophony reflects several self-organization characteristics in a dynamic process of language evolution, such as the predictable degree of homophony, the disyllabification in Chinese dialects, the differentiation of homophone pairs in grammatical class.

We are further interested in how the self-organization is implemented. To answer this question, we need to look into the idiolects in this self-organizing process, to know how the idiolects are formed and affect each other. Language change provides an informative window in addressing these issues. Language change is the result of the collective behaviors of idiolects, even as it affects the idiolects. The heterogeneity among idiolects is exposed to the greatest extent in on-going changes.

An on-going sound change in Cantonese is taken as a case study to scrutinize the heterogeneity in the self-organizing processes. The fieldwork data reveal a large degree of variation both in the population (VT-I) and in the set of words (VT-II). Another type of variation (VT-III) is highlighted, that is, a word may also show variation within one single speaker. But this VT-III within speakers only exists in a proportion, but not all, of the words subject to the change. Also we find that if a speaker has some words consistently in the unchanged state and some words in the changed state, then this speaker must have some other words in the variation state. Most speakers show the existence of VT-III, but they vary in degree. The observed individual differences in the degree of VT-III suggest that the large heterogeneity may be not only accounted for by the variability of linguistic input, but also by individuals' different learning styles. We hypothesize two types of lexical learning styles, i.e. probabilistic and categorical learning. These differences in learning styles suggest that when we examine the agent's internal properties in the self-organization framework, it is not only necessary to examine the commonalities among agents, but also the differences among them.

In addition to empirical studies, this thesis employs computational modeling as a major tool for investigation, as modeling provides effective ways to test hypotheses beyond empirical studies, and suggests new questions. After a brief review of the modeling studies in the field, some models developed in this thesis for language origin and language change are reported.

The first model is to simulate the emergence of a consistent vocabulary from a set of random mappings between meanings and forms. It emphasizes the importance of implementing the actual process of interaction among agents, and the cumulative effect on agents' linguistic behaviors. The model suggests that the Saussurean sign with identical speaking and listening mappings may not be a biological predisposition from natural selection, but rather a result from the process of language learning and use. The process exhibits a phase transition from a long period of small oscillation to an abrupt convergence. Such phase transition is often observed in self-organizing systems.

The second model simulates language change as innovation diffusion, and examines the effects of various factors, including some concerning properties of agents and some affecting agents' interactions. By comparing the outcome under different conditions, the model illustrates the importance of incorporating realistic assumptions, such as finite population size, age-dependent propensity to change, different learning environment in a social network, etc. The model compares the dynamics of language change in different types of network structures and shows that in non-regular networks, the rate of innovation diffusion increases little as population size increases. The model also tests the effect of the two types of hypothesized learning styles, and shows that in a population with the presence of probabilistic learners, an innovation with a small advantage will easily spread into the population and lead to a change. This may explain why language changes are so frequent.

This thesis demonstrates that both empirical and modeling studies on language evolution can greatly benefit from adopting a self-organization framework. The convergence and interplay of the two lines of exploration, i.e. biological bases in agents and the long term effect of interactions among them, should bring us a deeper understanding of how language has evolved and is evolving.

This thesis investigates language acquisition and evolution, using the methodologies of Bayesian inference and expression-induction modelling, making specific reference to colour term typology, and syntactic acquisition. In order to test Berlin and Kay's (1969) hypothesis that the typological patterns observed in basic colour term systems are produced by a process of cultural evolution under the influence of universal aspects of human neurophysiology, an expression-induction model was created. Ten artificial people were simulated, each of which was a computational agent. These people could learn colour term denotations by generalizing from examples using Bayesian inference, and the resulting denotations had the prototype properties characteristic of basic colour terms. Conversations between these people, in which they learned from one-another, were simulated over several generations, and the languages emerging at the end of each simulation were investigated. The proportion of colour terms of each type correlated closely with the equivalent frequencies found in the World Colour Survey, and most of the emergent languages could be placed on one of the evolutionary trajectories proposed by Kay and Maffi (1999). The simulation therefore demonstrates how typological patterns can emerge as a result of learning biases acting over a period of time.

Further work applied the minimum description length form of Bayesian inference to modelling syntactic acquisition. The particular problem investigated was the acquisition of the dative alternation in English. This alternation presents a learnability paradox, because only some verbs alternate, but children typically do not receive reliable evidence indicating which verbs do not participate in the alternation (Pinker, 1989). The model presented in this thesis took note of the frequency with which each verb occurred in each subcategorization, and so was able to infer which subcategorizations were conspicuously absent, and so presumably ungrammatical. Crucially, it also incorporated a measure of grammar complexity, and a preference for simpler grammars, so that more general grammars would be learned unless there was sufficient evidence to support the incorporation of some restriction. The model was able to learn the correct subcategorizations for both alternating and non-alternating verbs, and could generalise to allow novel verbs to appear in both constructions. When less data was observed, it also overgeneralized the alternation, which is a behaviour characteristic of children when they are learning verb subcategorizations. These results demonstrate that the dative alternation is learnable, and therefore that universal grammar may not be necessary to account for syntactic acquisition. Overall, these results suggest that the forms of languages may be determined to a much greater extent by learning, and by cumulative historical changes, than would be expected if the universal grammar hypothesis were correct.

Since Hinton & Nowlan published their seminal paper (Hinton & Nowlan 1987), the neglected evolutionary process of the Baldwin effect has been widely acknowledged. Especially in the field of language evolution, the Baldwin effect (Baldwin 1896d, Simpson 1953) has been expected to salvage the long-lasting deadlocked situation of modern linguistics: i.e., it may shed light on the relationship between environment and innateness in the formation of language.

However, as intense research of this evolutionary theory goes on, certain robust difficulties have become apparent. One example is genotype-phenotype correlation. By computer simulations, both Yamauchi (1999, 2001) and Mayley (1996b) show that for the Baldwin effect to work legitimately, correlation between genotypes and phenotypes is the most essential underpinning. This is due to the fact that this type of the Baldwin effect adopts as its core mechanism Waddington's (1975) `genetic assimilation'. In this mechanism, phenocopies have to be genetically closer to the innately predisposed genotype. Unfortunately this is an overly na{umlaut}yssumption for the theory of language evolution. As a highly complex cognitive ability, the possibility that this type of genotype-phenotype correlation exists in the domain of linguistic ability is vanishingly small.

In this thesis, we develop a new type of mechanism, called `Baldwinian Niche Construction (BNC), that has a rich explanatory power and can potentially overcome this bewildering problem of the Baldwin effect. BNC is based on the theory of niche construction that has been developed by Odling-Smee et al. (2003). The incorporation of the theory into the Baldwin effect was first suggested by Deacon (1997) and briefly introduced by Godfrey-Smith (2003). However, its formulation is yet incomplete.

In the thesis, first, we review the studies of the Baldwin effect in both biology and the study of language evolution. Then the theory of BNC is more rigorously developed. Linguistic communication has an intrinsic property that is fundamentally described in the theory of niche construction. This naturally leads us to the theoretical necessity of BNC in language evolution. By creating a new linguistic niche, learning discloses a previously hidden genetic variance on which the Baldwin `canalizing' effect can take place. It requires no genetic modification in a given genepool. There is even no need that genes responsible for learning occupy the same loci as genes for the innate linguistic knowledge. These and other aspects of BNC are presented with some results from computer simulations.

Generative models of phonology account for output patterns through a complex grammar applied over a minimal lexicon. In contrast, many natural complex patterns result from the gradual accumulation of structure through repeated local interactions. In this dissertation I present results of simulations supporting the proposal that some phonological patterns can be accounted for through self-organization within an analogically structured lexicon, in response to forcing from external biases. In Chapter 1, I show that patterns accounted for by the Optimality-Theoretic principles of constraint dominance and strict constraint dominance can be shown to spontaneously arise in analogically-structured systems, driven by competition between leveling pressures within the lexicon and differentiating pressures from lexicon- external performance biases.

Phonological systems exhibit `constrained contrast' in two distinct ways: first, phonologies exhibit only a subset of cross-linguistically attested contrasts, formed from a subset of possible features in combination. Second, crosslinguistically infrequent elements also tend to occur less frequently in a language that does have them. In Chapter 2, I present evidence that both of these patterns can be accounted for diachronically through indirect selection over phonetic variants, given the assumptions that, 1) lexical categories are richly specified, 2) a perceived utterance updates the content of a lexical category only if it is identified as an example of that lexical category, and 3) lexical categories can influence each others' production in proportion to phonological similarity.

When a simulated speaker/hearer pair alternately communicate their lexicons to each other under these conditions their lexicons converge. Further, when an output is too close to multiple categories, it is less likely be consistently categorized, with the result that it has less influence on the evolution of the pairs' lexicons, resulting in pressure on lexical categories to remain contrastive. W hen biases against certain features or feature combinations are introduced, the pairs' lexicons evolve to avoid as many of these `less-fit' elements as possible. However, when avoidance of all marked elements would result in insufficient contrast, the lexicons evolve to utilize a subset of less-fit elements, but at a lower frequency than fitter elements.

Human language is a remarkable communication system, apparently unique among an- imals. All humans have a built-in learning mechanism known as universal grammar or UG. Languages change in regular yet unpredictable ways due to many factors, including properties of UG and contact with other languages. This dissertation extends the standard replicator equation used in evolutionary biology to include a learning process. The resulting language dynamical equation models language change at the population level. In a further extension, members of the population may have di#erent UGs. It models evolution of the language faculty itself.

We begin by examining the language dynamical equation in the case where the param- eters are fully symmetric. When learning is very error prone, the population always settles at an equilibrium where all grammars are present. For more accurate learning, coherent equilibria appear, where one grammar dominates the population. We identify all bifurca- tions that take place as learning accuracy increases. This alternation between incoherence and coherence provides a mechanism for understanding how language contact can trigger change.

We then relax the symmetry assumptions, and demonstrate that the language dynami- cal equation can exhibit oscillations and chaos. Such behavior is consistent with the regular, spontaneous, and unpredictable changes observed in actual languages, and with the sensi- tivity exhibited by changes triggered by language contact. From there, we move to the extended model with multiple UGs. The first stage of analysis focuses on UGs that admit only a single grammar. These are stable, immune to invasion by other UGs with imperfect learning. They can invade a population that uses a similar grammar with a multi-grammar UG. This analysis suggests that in the distant past, human UG may have admitted more languages than it currently does, and that over time variants with more built-in information have taken over. Finally, we address a low-dimensional case of competition between two UGs, and find conditions where they are stable against one another, and where they can coexist. These results imply that evolution of UG must have been incremental, and that similar variants may coexist.

This research was conducted under the supervision of Dr. Martin A. Nowak (Program in Theoretical Biology at the Institute for Advanced Study, and Program in Applied and Computational Mathematics at Princeton University).

Theories of language evolution typically attribute its unique structure to pressures acting on the genetic transmission of a language faculty and on the cultural transmission of language itself. In strongly biological accounts, natural selection acting on the genetic transmission of the language faculty is seen as the key determinant of linguistic structure, with culture relegated to a relatively minor role. Strongly cultural accounts place greater emphasis on the role of learning in shaping language, with little or no biological adaptation.

Formal modelling of the transmission of language, using mathematical or computational techniques, allows rigorous study of the impact of these two modes of transmission on the structure of language. In this thesis, computational models are used to investigate the evolution of symbolic vocabulary and compositional structure. To what extent can these aspects of language be explained in terms of purely biological or cultural evolution? Should we expect to see a fruitful interaction between these two adaptive processes in a dual transmission model?

As a first step towards addressing these questions, models which focus on the cultural transmission of language are developed. These models suggest that the conventionalised symbolic vocabulary and compositional structure of language can emerge through the adaptation of language itself in response to pressure to be learnable. This pressure arises during cultural transmission as a result of 1) the inductive bias of learners and 2) the poverty of the stimulus available to learners. Language-like systems emerge only when learners acquire their linguistic competence on the basis of sparse input and do so using learning procedures which are biased in favour of one-to-one mappings between meanings and signals. Children acquire language under precisely such circumstances.

As the second stage of inquiry, dual transmission models are developed to ascertain whether this cultural evolution of language interacts with the biological evolution of the language faculty. In these models an individual's learning bias is assumed to be genetically determined. Surprisingly, natural selection during the genetic transmission of this innate endowment does not reliably result in the development of learning biases which lead, through cultural processes, to language-like communication -- there is no synergistic interaction between biological and cultural evolution. The evolution of language may therefore best be explained in terms of cultural evolution on a domain-general or exapted innate substrate.

In this thesis, I address the problem of how successful communication systems can emerge between agents who do not have innate or explicitly transferable meanings, cannot read the minds of their interlocutors, and are not provided with any feedback about the communication process. I develop a solution by focusing on the role of meanings within the framework of language evolution, and on communication through the repeated inference of meaning.

Much recent work on the evolution of language has concentrated on the emergence of compositional syntax as the crucial event which marked the genesis of language; all the experimental models which purport to demonstrate the emergence of syntax, however, rely on models of communication in which the signals are redundant and which contain pre-defined, structured meaning systems which provide an explicit blueprint against which the syntactic structure is built. Moreover, the vast majority of such meaning systems are truly semantic in name only, lacking even the basic semantic characteristics of sense and reference, and the agents must rely on mind-reading or feedback (or both) in order to learn how to communicate.

By contrast, at the heart of this thesis is a solution to the signal redundancy paradox based on the inference of meaning and the disambiguation of potential referents through exposure in multiple contexts. I describe computational models of meaning creation in which agents independently develop individual conceptual structures based on their own experiences of the environment, and show through experimental simulations that the agents can use their own individual meanings to communicate with each other about items in their environment. I demonstrate that the development of successful communication depends to a large extent on the synchronisation of the agents' conceptual structures, and that such synchronisation is significantly more likely to occur when the agents use an intelligent meaning creation strategy which can exploit the structure in the information in the environment.

Motivated by research into the acquisition of language by children, I go on to explore how the introduction of specific cognitive and lexical biases affects the level of communicative success. I show that if the agents are guided by an assumption of mutual exclusivity in word meanings, they do not need to have such high levels of meaning similarity, and can instead communicate successfully despite having very divergent conceptual structures.

How did language come to have its characteristic structure? Many argue that by understanding those parts of our biological machinery relevant to language, we can explain why language is the way it is. If the hallmarks of language are simply properties of our biological machinery, elicited through the process of language acquisition, then such an explanatory route is adequate.

As soon as we admit the possibility that knowledge of language is learned, in the sense that language acquisition is a process involving inductive generalisations, then an explanatory inadequacy arises. Any thorough explanation of the characteristic structure of language must now explain why the input to the language acquisition process has certain properties and not others. This thesis builds on recent work that proposes that the linguistic stimulus has certain structural properties that arise as a result of linguistic evolution. Here, languages themselves adapt to fit the task of learning: they reflect an accumulated structural residue laid down by previous generations of language users.

Using computational models of linguistic evolution I explore the relationship be- tween language induction and generalisation based on a simplicity principle, and the linguistic evolution of compositional structures. The two main contributions of this thesis are as follows. Firstly, using a model of induction based on the minimum description length principle, I address the question of linguistic evolution resulting from a bias towards compression. Secondly, I carry out a thorough examination of the parameter space affecting the cultural transmission of language, and note that the conditions for linguistic evolution towards compositional structure correspond to (1) specific levels of semantic complexity, and (2), induction based on sparse language exposure.

Ultimately, the story of the evolution of language in humans must depend on an account of the genetic evolution of the biological machinery underlying language. Rather than explicitly encoding the observed constraints on language, I argue that any explanation based on biological evolution should instead aim to explain how the conditions for linguistic evolution, outlined above, came about.

The emergence and evolution of human language has been the focus of increasing amounts of research activity in recent years. This increasing interest has been coincident with the increased use of computer simulation, particularly using one or more of the methods and techniques of `Artificial Life', to investigate a wide range of evolutionary problems and questions. There is now a significant body of work that uses such computer simulations to investigate the evolution of language.

In this thesis a broad review of work on the evolution of language is presented, showing that language evolution occurs as two distinct evolutionary processes. The ability to use language is clearly the result of biological evolution. But the changes that occur over time to all spoken languages can also be viewed as being part of a process of cultural evolution. In this thesis, work using artificial life models to investigate each of these processes is reviewed. A review of the methods and techniques used in artificial life is also presented early in the work.

A novel model is developed which is used to explore the conditions necessary for the evolution of language. Interesting results from initial tests of the model highlight the role of redundancy in language. From these initial tests, the model is further developed to explore the biological evolution of the human capacity for language. One significant outcome of this work is to highlight the limitations of the model for developing, and especially for `proving', particular theories on how or why Homo sapiens alone evolved language. This is tied to a brief review showing that this weakness is not one specific to this particular model, but may be one that is possessed by all artificial life models that try to explain the origins of language.

With further minor modifications to the model, the focus is shifted to the evolution of languages and language diversity. In comparison with some of the earlier conclusions, this work emphasises the positive contribution to ongoing scientific debate that is possible using computer simulations. In this case, experiments using the model focus on whether social and/or linguistic benefits are required in explanations of language change. A review and debate is then presented on work that contradicts our findings. Further corroboration of our conclusions is then gained by conducting a similar experiment using a different computer model.

The key contributions of this interdisciplinary work are: first, in detailing some of the unique problems and issues inherent in using computer models specifically for modelling the evolution of language; second, in emphasising the importance of redundancy in language evolution; and finally, in adding to the current debate on whether the evolution of languages can be viewed as a form of adaptively neutral evolution.

The PhD thesis titled ``An Agent-Based Evolutionary Computing Approach to Memory-Based Syntactic Parsing of Natural Language'' introduces the grael system (grammar evolution) as one of the first research efforts that investigates an agent-based evolutionary computing approach as a possible machine learning method for data-driven grammar optimization and induction. Using the same architecture, but different information sources, grael can be shown to handle a diverse range of grammar engineering tasks, which can help resolve common issues in corpus-based parsing systems, such as insufficient grammar coverage and the suboptimal distribution of probability mass.

Since the PhD thesis covers a considerable array of research issues, which may not be relevant to all researchers alike, this web page is further subdivided into thematic units. If you want to read the entire thesis, please go to the full download page...

Humans perceive a continuous colour spectrum, but divide the spectrum into colour categories in order to reason and communicate about colour. There is an ongoing debate on whether these colour categories necessary for language communication are universal or culture-specific, whether these categories are genetically determined or learned, and whether there is a causal influence of language on colour category acquisition or not. The dissertation presents a number of models, each examining one of these outstanding issues. The models draw on techniques from multi-agent systems, machine learning and evolutionary programming. After considering the behaviour of each model, we conclude in favour of a cultural specificity of language categories and argue that learning under the influence of language is the most plausible explanation for their acquisition.

This thesis explores a perspective for explaining the origins of linguistic structure that is based on considerations beyond the constraints of the language acquisition device. In contrast to the theory of Universal Grammar proposed by Chomsky, this perspective considers how the processes of language acquisition and use create a dynamical system that is capable of adapting linguistic structure to the inductive biases of learners. In this view it is possible to conceive of language adapting to aid its own survival: those languages that are more reliably and easily acquired will tend to persist for longer than their less easily learned counterparts. Thus, linguistic structures are seen as emergent, adaptive phenomena rather than preordained features of language.

The particular issue that this thesis investigates is the extent to which language adaptation can facilitate acquisition by general-purpose learners. In the Generative Grammar tradition much is made of the necessity for domain-specific constraints on the language acquisition device. (Indeed, that there must be a distinct mental com- ponent dedicated to language tasks.) This outlook is in contrast to the connectionist viewpoint, which posits far more moderately constrained, domain-general mecha- nisms. This thesis examines how language adaptation can give general-purpose, connectionist learners the appearance of being language-savvy learners.

A simulation framework is proposed in which agents attempt to communicate simple concepts to one another using sequential utterances. In earlier simulations we aim to maximise the learnability of a language for the communication task. Later simulations show how the processes of language production and acquisition, when iterated, are capable of producing such languages. In total, three series of simulations are performed.

The first series of simulations addresses the question of how linguistic structure adapts when sender and receiver disagree on the form of language that is easiest to learn. Analysis reveals that, if necessary, the structural properties of language can take on forms that compromise between the competing constraints on sender and receiver.

The second series of simulations considers the bottleneck of linguistic transmis- sion: the requirement that learners generalise from a limited set of observed utter- ances to the entire language. Results show that generalisability can be boosted in a naive, domain-general learner by allowing language to adapt to the inductive biases present in the learner.

The third and final series of simulations investigates how the dynamical charac- teristics of linguistic change depend on the properties that drive the dynamics. That is, we explore the range of conditions under which the iterated learning dynamic is suAecient to establish a learnable language throughout the population. The results of these simulations show that the iterated learning dynamic is indeed able to act as a generator of languages that general-purpose learners are capable of acquiring.

The results from these studies suggest that through the dynamics of linguistic transmission, language can adapt to the capabilities and biases of its users. Fur- thermore, that language can exploit the inductive biases of general-purpose learning mechanisms to facilitate their own acquisition, contrary to Universal Grammar's hypothesised need for an innate, domain-specific acquisition mechanism.

This dissertation provides an Optimality-Theoretic (OT: Prince & Smolensky 1993, McCarthy & Prince 1993) account of the evolution of the English obstruent inventory over an extended period of time, starting with Proto-Indo-European and ending with Early New English. By modeling the mechanism through which the PIE [voice] distinction in stops emerged as a Germanic [spread glottis] distinction, the analysis lends support to a recently established claim that [spread glottis], rather than [voice], is distinctive in stops in the majority of the Germanic languages (Iverson & Salmons 1995, Jessen 1998) OT, a non-derivational framework which provides a model of Universal Grammar (UG) significantly different from the earlier rule-based approaches, views language change as the reranking of hierarchically organized UG constraints on the well-formedness of output representations (Cho 1995, Berm dez-Otero 1995). The non-serial essence of OT makes it possible to describe parallel sound shifts, whereby a number of sound changes occur in parallel, rather than sequentially. For example, in Grimm's Law, p-b shifts to psg-p, whereby the contrast is preserved, yet it is has a different segmental composition. Specifically, it is demonstrated that a comprehensive analysis of language change, and, especially, parallel sound shifts, calls for the integration of two complementary approaches within OT: faithfulness (McCarthy & Prince 1995, and others) and dispersion (Flemming 1996, Padgett 1997). In the faithfulness framework, language change is viewed as a resolution of the conflict between the tendency to save articulatory effort and the preference for the faithful mapping of input representations to their output correspondents. In the dispersion framework, language change results from the conflict between articulatory effort minimization and the preference for a maximal perceptual contrast among output forms, with no reference to inputs. In more general terms, the dispersion interaction reflects the tendency to maintain a balanced inventory, whereas a faithfulness interaction implements the preference for a transparent (i.e., non-structure changing) inventory. The integration of the two approaches amounts to claiming that each individual output form experiences two competing pressures: to be different from or similar to other output forms, and to be identical to a corresponding input form. Unlike the proponents of the dispersion-based approach (e.g., Flemming 1998), who contend that the two approaches are incompatible, I demonstrate that dispersion and faithfulness are not only compatible, but complementary in accounting for language change. Dispersion constraints exercise a stabilizing effect on the inventory. By enforcing a fixed number of contrasts, the dispersion interaction thereby delimits the range of (or censors) possible faithfulness violations. The faithfulness constraints complement the dispersion interaction, by referring to an input as the reference point relative to which the output contrast is evaluated, so that the contrast which is minimally unfaithful to the input is selected as optimal. In other words, whereas dispersion is responsible for enforcing contrast itself, faithfulness is in charge of determining the adequate segmental composition of the contrast. The analysis reveals that the integrated dispersion/faithfulness framework has advantages over earlier linguistic approaches in accounting for the sound changes which have a perceptual origin, such as Grimm's Law and Verner's Law.

A new microevolutionary theory of complex design within language is pro- posed. Experiments were carried out that support the theory that complex functional design --- adaptive complexity --- accumulates due to the evolu- tionary algorithm at the simplest levels within human natural language. A large software system was developed which identifies and tracks evolution- ary dynamics within text discourse. With this system hundreds of examples of activity suggesting evolutionary significance were distilled from a text collection of many millions of words.

Research contributions include: (1) An active replicator model of micro- evolutionary dynamics within natural language, (2) methods to distill active replicators offering evidence of evolutionary processes in action and at multiple linguistic levels (lexical, lexical co-occurrence, lexico-syntac- tic, and syntactic), (3) a demonstration that language evolution and organic evolution are both examples of a single over-arching evolutionary algo- rithm, (4) a set of tools to comparatively study language over time, and (5) methods to materially improve text retrieval.

The thesis presents research that investigates how two mobile robots can develop a shared lexicon from scratch of which the meaning is grounded in the real world. It is shown how the robots can solve the symbol grounding problem in a particular experimental setup. The model by which the robots do so is explained in detail. The experimental results are presented and discussed.

The research in this thesis addresses the question of how autonomous agents may develop concepts about their environment and develop a system of communication that allows them to exchange information about this environment based on those concepts. An autonomous agent is a system, in software or in hardware, that receives sensor input from the environment, selects actions, and may receive evaluative feedback reflecting the appropriateness of its actions. Communication is viewed as the transfer of information, in the sense that when a sender sends a message to a receiver, the amount of uncertainty in the receiver's knowledge about its environment decreases as a result of receiving the message. When agents have incomplete knowledge about their environment, communication can be valuable as a means to reduce this uncertainty by sharing information, and can be used to coordinate the actions of agents. Communication is learned during the life time of the agents, and the research concerns the question of how agents may cooperate to arrive at a shared system of communication.

Features of the information available to an agent through its sensors can be used to construct concepts, also called meanings. Constructing concepts based on the requirements posed by the environment is a more flexible approach than fixing the concepts of agents at design time, and may be necessary when the agents are to function in unknown or changing environments.

In this thesis, a particular type of concepts is described, called situation concepts. Situation concepts consist of features in the history of interaction between the agent and its environment, which consists of sensor data, actions, and subsequent evaluative feedback. A defining criterion of a situation concept is that it predicts some aspect of the future evolution of the state of the environment, possibly conditioned on the actions the agent may take. Several existing methods, particularly from the field of reinforcement learning, can be viewed as constructing a form of situation concepts. A particular method for constructing a specific type of situation concepts, called the adaptive subspace method, is described. The method uses the current sensor values of an agent as features and develops concepts that specify an interval for each sensor. These concepts predict the value of actions the agent can take when its current sensor values are within the specified intervals. The meanings thus formed represent situations, and are especially appropriate for use in communication, since they convey information about the environment.

The development of communication is viewed as the formation of associations between words and the meanings formed by the agents in a population, in such a way that agents tend to use the same word in the same situation. When agents autonomously construct concepts, a consequence is that they may not possess identical concepts. Additional constraints that are respected, such as the commitment that agents have no direct access to the meanings formed by other agents (they can not 'look inside each other's head'), and that no single agent may decide on the system of communication, further complicate the problem of how such a system of associations may come about.

Rather than viewing communication as fixed, it is viewed as a dynamical system. A dynamical system is a mathematical model of a system that changes over time. The variables of this system are the strengths of the associations between words and the meanings of the agents in a population. An algorithm is described in detail that, when used by each individual agent to adapt its associations between words and the situation concepts it has formed, leads to a shared system of communication.

The necessity of different components of the algorithm is shown with statistical significance. Associations are linear combinations of use (the frequency with which a word is observed in a situation) and success (the degree to which the word correctly indicates that its associated situation is the current situation in the environment). Analysis of the success component of the algorithm showed that not the success information itself, but the lateral inhibition between competing associations is crucial for the development of communication. It is experimentally demonstrated how the development of communication can compensate for differences in conceptual systems.

Systematic measures have been introduced to determine the quality of conceptual systems and communication systems. The measures require knowledge of the ideal concepts, called referents; although such knowledge is not available in general, simulation experiments often do provide the opportunity for such referents to be determined.

The specificity measure for communication is based on the principle that knowledge of a word should yield information (i.e. reduce uncertainty) about the referent (the current situation in the environment), and vice versa for the consistency measure. In cases of maximal specificity, the information a word yields is complete, and thus identifies the situation, whereas in the worst case, the word does not yield any information at all. The measure quantifies these and all intermediate cases. The consistency measure is computed as the extent to which a referent identifies a word, and thus expresses whether for each a referent the agent consistently uses the same word. If both specificity and consistency are high, each agent consistently uses a unique word for each referent. A population measure called coherence is used to determine whether different agents use the same words. In combination with the specificity and consistency measures, the experimenter can determine to what degree a perfect system of communication, consistently linking each referent to a unique word, is approximated.

Interestingly, the same principle can be used to evaluate the quality of a conceptual system. Ideally, each concept an agent has formed identifies a single referent in the environment; this is expressed by the distinctiveness measure, calculated as the degree to which the meanings an agent possesses distinguish between the different referents. Conversely, parsimony expresses the degree to which a referent identifies a meaning. It thus reflects whether the agent has not generated more meanings than necessary. Together, high distinctiveness and high parsimony imply that a conceptual system is ideal in the sense that it approximates a one-to-one relation between meanings and referents.

A contribution is made to the viewpoint of communication as a dynamical system by considering the attractors in the communication system that has been described. A deterministic version of the system is proved mathematically and demonstrated experimentally to have point attractors that correspond to perfect communication. An operational definition of pseudo-attractors is used to demonstrate that the stochastic system has points that play a similar role. Stochasticity is found to be a useful ingredient in the development of communication, in that it avoids deadlocks and results in communication more consistently and under a wider variety of parameter settings. This finding is confirmed by a systematic investigation of the effect of different amounts of stochasticity, regulated by the temperature parameter that governs word production. The analysis provides evidence that a dynamical systems perspective on the development of communication is valuable.

An exploration is presented of the interplay between the situated activity of embodied autonomous organisms and the social dynamics they constitute in interaction, with special emphasis on evolutionary, ecological and behavioral aspects. The thesis offers a series of theoretical and methodological criticisms of recent investigations on the biology of social behavior and animal communication. An alternative theoretical framework, based on a systemic theory of biological autonomy, is provided to meet these criticisms and the elaboration of the corresponding theoretical arguments is supported by the construction and analysis of mathematical and computational models.

A game of action coordination is studied by a series of game-theoretic, ecological and computational models which, by means of systematic comparisons, permit the identification of the evolutionary relevance of different factors like finite populations, ecological and genetic constraints, spatial patterns, discreteness and stochasticity. Only in an individual-based model is it found that cooperative action coordination is evolutionarily stable. This is due to the emergence of spatial clusters in the spatial distribution of players which break many of the in-built symmetries of the game and act as invariants of the dynamics constraining the path of viable evolution.

An extension to this model explores other structuring effects by adding the possibility of parental influences on phenotypic development. The result is a further stabilization of cooperative coordination which is explained by the presence of self-promoting networks of developmental relationships which enslave the evolutionary dynamics.

The behavioral aspects involved in the attainment of a coordinated state between autonomous systems are studied in a simulated model of embodied agents coupled through an acoustic medium. Agents must locate and approach each other only by means of continuous acoustic signals. The results show the emergence of synchronized rhythmic signalling patterns that resemble turn-taking which is accompanied by coherent patterns of movement. It is demonstrated that coordination results from the achievement of structural congruence between the agents during interaction.

The research described in this thesis tries to explain the origins and the struc- ture of human sound systems (and more specifically human vowel systems) as the result of self-organisation in a population under functional con- straints. These constraints are: acoustic distinctiveness, articulatory ease and ease of learning. The process is modelled with computer simulations, following the meth- odology of artificial life and artificial intelligence. The research is part of a larger re- search effort into understanding the origins and the nature of language and intelli- gence.

The emergence of sound systems is studied in a setting called the imitation game. In an imitation game, agents from a population interact in order to imitate each other as well as possible. Imitation is a binary process: it is either successful or a failure. Agents are able to produce and perceive speech sounds in a human-like way, and to adapt and extend their repertoires of speech sounds in reaction to the outcome of the imitation games. The agents' vowel repertoires are initially empty and are bootstrapped by random insertion of a speech sound when an agent with an empty repertoire wants to produce a sound. When the agents' repertoires are not empty anymore, random insertion does not happen anymore, except with very low probability. This low-probability random insertion is done in order to keep a pres- sure on the agents to extend their number of vowels. .

As the agents' repertoires are initially empty and their production and percep- tion are not biased towards any language in particular, the systems of speech sounds that emerge are language-independent and can be considered predictions of the kinds of systems of speech sounds that can be found in human languages.

The main focus of the thesis is on the emergence of vowel systems. It is shown that coherent, successful and realistic vowel systems emerge for a wide range of pa- rameter settings in the simulation. When the vowel systems are compared with the types of vowel systems that are found in human languages, remarkable similarities are found. Not only are the most frequently found human vowel systems predicted, (this could already be done with direct optimisation of acoustic distinctiveness) but also less frequently occurring vowel systems are predicted in approximately the right proportions.

Variations on the basic imitation game show that it is remarkably robust. Not only do coherent, successful and realistic vowel systems emerge for a large number of parameter settings, but they also emerge when either the imitation game or the agents are changed qualitatively. Coherent and realistic systems still emerge when the perception and production of the agents are changed. Even if the rules of the imitation game are slightly changed, coherent and realistic systems still emerge. Of course, there are circumstances under which no systems emerge, indicating that the process is non-trivial.

It is also shown that the vowel systems can emerge and be preserved in chang- ing populations. When old agents are removed from the population, and new, empty agents are added, coherent and realistic vowel systems can still emerge, provided that the replacement rate is not too high. It is also shown in the thesis that vowel systems can be preserved in a population, even though all original agents in it have been replaced. Furthermore, it is shown that under certain circumstances it can be advantegeous to have an age-structure in the population, so that older agents learn less quickly than young ones.

Finally, some experiments with more complex utterances are presented in the thesis. An experiment with artificial CV-syllables is presented and it is shown that, although phonemically coded (as opposed to holistically coded) systems can emerge, this simulation is much harder and much more sensitive to parameter changes than the vowel simulation. This probably has to do with the fact that in the case of CV- syllables multiple independent and partly contradictory constraints have to be satis- fied simultaneously, whereas in the vowel simulations, only one constraint (acoustic distinctiveness) is really important. Also, the first attempts at building a system that can produce complex and dynamic utterances without any constraints on their structure are presented, and it is argued that the main obstacle to getting such a system to work is the mapping from acoustic signals back to articulatory com- mands.

The conclusion of the thesis is that universal tendencies of human vowel sys- tems, and probably of human sound systems in general can be explained as the re- sult of self-organisation in a population of agents that try to communicate as well as possible under articulatory and acoustic constraints. The articulatory and acoustic constraints cause the emerging sound systems to tend towards articulatory and acoustic optimality. However, the fact that the agents communicate in a population forces them to conform to the sound system in the population and causes sub- optimal systems to emerge as well.

Simulated evolution is used as a tool for investigating the selective pressures that have influenced the design of animal signalling systems. The biological literature on communication is first reviewed: central concepts such as the handicap principle and the view of signalling as manipulation are discussed. The equation of ``biological function'' with ``adaptive value'' is then defended, along with a workable definition of communication. Evolutionary simulation models are advocated as a way of testing the coherence of a given theory. Contra some ALife enthusiasts, simulations are not alternate worlds worthy of independent study; in fact they fit naturally into a Quinean picture of scientific knowledge as a web of modifiable propositions. Existing simulation work on the evolution of communication is reviewed: much of it consists of simple proofs of concept that fail to make connections with existing theory. A particular model (MacLennan and Burghardt, 1994) of the evolution of referential communication in a co-operative context is replicated and critiqued in detail.

Evolutionary simulations are then presented that cover a range of ecological scenarios; the first is a general model of food- and alarm-calling. In such situations signallers and receivers can have common or conflicting interests; the model allows us to test the idea that a conflict of interests will lead to an arms race of ever more costly signals, whereas common interests will result in signals that are as cheap as possible. The second model is concerned with communication during aggressive interactions. Many animals use signals to settle contests, thus avoiding the costs associated with fighting. Conventional game-theoretic results suggest that the signalling of aggression or of strength will not be evolutionarily stable unless it is physically unfakeable, but some recent models imply that cost-free, arbitrary signals can be reliable indicators of both intent and ability. The simulation, which features continuous-time perception of the opponent's strategy, is an attempt to settle the question. The third model deals with sexual signalling, i.e., elaborate displays that are designed to persuade members of the opposite sex to mate. The results clarify the question of whether such displays are the pointless result of runaway sexual selection, or whether they function as honest and costly indicators of genetic quality.

The models predict the evolution of reliable communication in a surprisingly narrow range of circumstances; a serious gap remains between these predictions and the ethological data. Future directions for simulation work are discussed.

This dissertation identifies the conditions necessary to establish a system of communication in a population of individuals, whether through evolution or learning. A definition of communication is proposed that encompasses the behavior of species ranging from flowers to human beings, and a formal framework for modeling such behavior is presented. Through the use of computational simulations, it is shown that systems of communication evolve in cases where such behavior conveys a selective advantage to both sender and receiver. It is also demonstrated that factors such as kin selection and reciprocal altruism can result in the establishment of communication even when there is no direct pressure on the transmission of signals. In the case of learned communication, it is argued that observational learning is the appropriate learning model. Learning strategies that simply imitate the behavior of others, however, are not suitable. Instead, a learning mechanism must optimize its behavior so as best to communicate with the population it is observing. A Bayesian learning procedure designed to maximize the probability of communicative success is shown to be capable not only of learning an existing communication system, but also constructing such a system from random initial signaling behavior. To examine how animals might actually implement such a procedure, network learning models are considered. It is shown that a simple form of Hebbian learning, well within the grasp of most animals, has the required properties. Given this, it is surprising that learned systems of communication are not more frequent. Evidence from the animal social learning literature suggests that the primary reason for this may be that observational learning is difficult, if not impossible, for non-human animals. Given this, he most basic explanation for why only humans have language may not lie in the ability of learn a complex, syntactic form of communication, but rather in the ability to learn any system of communication at all.

This thesis investigates communication between animals with conflicting interests. Particular attention is paid to conventional signalling, in which signals are not inherently costly and information is inferred by convention. This type of signalling is emphasised for two reasons: firstly it is communication in its purest sense, and secondly it seems to more accurately reflect the properties of many biological signals. The costs which maintain the evolutionary stability of communication are of great interest because of the apparent benefit to be gained through the use of misleading signals, such as bluffs. I argue that these stabilising costs emerge from the manner in which receivers respond to signals, rather than being inherent to the signals themselves.

The theoretical papers in this thesis begin with the most basic signalling game and proceed towards a more general understanding of conventional signalling. I begin by investigating the importance of signal cost in the simplest possible model of communication, the Action-Response game. I demonstrate that the signals used do not have to be costly to be reliable, even when the signaller and receiver are in a state of conflict. I then consider the effect of adding costs to signals in a game in which reliable conventional signalling already exists, and demonstrate that the costly signals will be used by the weaker, not stronger, signallers. This demonstrates a stabilising mechanism fundamentally different from that of the handicap hypothesis, with its stabilisation through signal cost. Finally, I identify the conditions other than cost which are necessary for conventional signalling to be evolutionarily stable. These conditions relate to the information which both signaller and receiver must gain over the course of an interaction. Most models used to investigate signalling cannot account for behaviour seen in more complicated biological interactions because they are too simple to produce results other than that of the handicap prediction.

The other work included in this thesis addresses issues raised by the models. I review the literature on threat display use by birds, and present evidence that these displays are conventional signals. The stability of conventional signalling rests upon the existence of some common interest within a larger conflict between signaller and receiver. I present a clear example of communication attributable to common interest between fighting opponents. Cichlids of the species Nannacara anomala use a distinct colour signal, the Medial Line display, to coordinate another agonistic behaviour, tail-beating. It appears that both individuals benefit from the clearer assessment of relative fighting ability that this coordination affords. These N. anomala colour displays are quite conspicuous. It has been assumed that when common interest exists, signals will be very subtle, whereas when signaller and receiver are in conflict, signals will be exaggerated and conspicuous. Using an evolving neural-network model, I demonstrate that selection for exaggerated signals may exist even when the signaller and receiver have complete common interests.

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.

This thesis presents a connectionist theory of how infinite languages may fit within nite minds. Arguments are presented against the distinction between linguistic competence and observable language performance. It is suggested that certain kinds of finite state automata--i.e., recurrent neural networks|are likely to have sufficient computational power, and the necessary generalization capability, to serve as models for the processing and acquisition of linguistic structure. These arguments are further corroborated by a number of computer simulations, demonstrating that recurrent connectionist models are able to learn complex recursive regularities and have powerful generalization abilities. Importantly, the performance evinced by the networks are comparable with observed human behavior on similar aspects of language. Moreover, an evolutionary account is provided, advocating a learning and processing based explanation of the origin and subsequent phylogenetic development of language. This view construes language as a nonobligate symbiant, arguing that language has evolved to fit human learning and processing mechanisms, rather than vice versa. As such, this perspective promises to explain linguistic universals in functional terms, and motivates an account of language acquisition which incorporates innate, but not language-specific constraints on the learning process. The purported poverty of the stimulus is re-appraised in this light, and it is concluded that linguistic structure may be learnable by bottom-up statistical learning models, such as, connectionist neural networks.