Language Evolution and Computation Bibliography

An evolutionary model for emergence of diversity in language is developed. We investigated the effects of two real life observations, namely, people prefer people that they communicate with well, and people interact with people that are physically close to each other. Clearly these groups are relatively small compared to the entire population. We restrict selection of the teachers from such small groups, called imitation sets, around parents. Then the child learns language from a teacher selected within the imitation set of her parent. As a result, there are subcommunities with their own languages developed. Within subcommunity comprehension is found to be high. The number of languages is related to the relative size of imitation set by a power law.

In biological evolution traits may rise and fall in frequency due to genetic drift, where variant frequencies change by chance, or by selection where advantageous variants will rise in frequency. The neutral model of evolution, first developed by Kimura in the 1960s, has become the standard against which selection is detected. While the balance between these two important forces - drift and selection - has been well established in biology there are other domains where the contribution of these processes is still coming together. Although the idea of natural selection has been applied to the cultural domain since the time of Darwin, it has proven more challenging to positively identify cultural traits under selection both because of a lack of established tests for selection and a lack of large cultural data sets. However, in recent years with the accumulation of large cultural data sets many cultural features from pre-history pottery to modern baby names have been shown to evolve according to the neutral theory. But there is accumulating empirical evidence from cultural processes suggesting that the neutral theory alone cannot account for all features of the data. As such, there has been a renewed interest in determining whether there is selection amidst drift. Here we analyze a subset English word frequencies, and determine whether frequency change reveals processes of selection. Inspired by the Moran and Wright-Fisher models in population genetics, we developed a neutral model of word frequency variation to assess when linguistic data appears to depart from neutral evolution. As such, our model represents a possible "test for selection" in the linguistic domain. We explore how the distribution of word use has changed for sets of words in English for more than 100 years (1901-2008) as expressed in vocabulary usage in published books, made available by Google Ngram. When comparing empirical word frequency changes to our neutral model we find pervasive and systematic departures from neutrality.

We study an atomic signaling game under stochastic evolutionary dynamics. There are a finite number of players who repeatedly update from a finite number of available languages/signaling strategies. Players imitate the most fit agents with high probability or mutate with low probability. We analyze the long-run distribution of states and show that, for sufficiently small mutation probability, its support is limited to efficient communication systems. We find that this behavior is insensitive to the particular choice of evolutionary dynamic, a property that is due to the game having a potential structure with a potential function corresponding to average fitness. Consequently, the model supports conclusions similar to those found in the literature on language competition. That is, we show that efficient languages eventually predominate the society while reproducing the empirical phenomenon of linguistic drift. The emergence of efficiency in the atomic case can be contrasted with results for non-atomic signaling games that establish the non-negligible possibility of convergence, under replicator dynamics, to states of unbounded efficiency loss.

We consider a simple computational model of the evolution of a quantitative trait and its phenotypic plasticity based on directional and positive frequency-dependent selection in order to explore whether and how leaning might facilitate evolution under the dynamics that arise from communicative interactions among individuals. In the model, each individual expresses, at many different times in its lifetime, its real-valued trait depending on the probability distribution determined by its own genotypes. In communicative interactions between two individuals, the contribution of an interaction to the fitness is high when their trait values are close to each other as well as large, which represents the positive frequency-dependent and directional components of selection, respectively. The iterative interactions allow individuals to acquire a more adaptive trait pair through trial and error. Under the stochastic evolution process with the limited number of individuals, we show that learning allows the population to avoid getting stuck in the global but low optimum of the innate and individual-level fitness landscape via both aspects of the components of selection, and brings about the successful evolution by increasing the genetic variation of the population. We also analyze how such an effect of learning can be realized by measuring the degree of the two different contributions for increasing the adaptivity and similarity of communicative traits, respectively. We show that this effect of learning arises from these different types of contributions depending on the biological and environmental conditions such as the mutation rate and the duration of communicative interactions. We further show the condition for the complete genetic assimilation to occur.

We used individual-based stochastic models to examine how social structure influences the diversity of socially learned behaviour within a non-human population. For continuous behavioural variables we modelled three forms of dyadic social learning, averaging the behavioural value of the two individuals, random transfer of information from one individual to the other, and directional transfer from the individual with highest behavioural value to the other. Learning had potential error. We also examined the transfer of categorical behaviour between individuals with random directionality and two forms of error, the adoption of a randomly chosen existing behavioural category or the innovation of a new type of behaviour. In populations without social structuring the diversity of culturally transmitted behaviour increased with learning error and population size. When the populations were structured socially either by making individuals members of permanent social units or by giving them overlapping ranges, behavioural diversity increased with network modularity under all scenarios, although the proportional increase varied considerably between continuous and categorical behaviour, with transmission mechanism, and population size. Although functions of the form e(c)¹(m)?(c)² + (c)³(Log(N)) predicted the mean increase in diversity with modularity (m) and population size (N), behavioural diversity could be highly unpredictable both between simulations with the same set of parameters, and within runs. Errors in social learning and social structuring generally promote behavioural diversity. Consequently, social learning may be considered to produce culture in populations whose social structure is sufficiently modular.

It is supposed that humans are genetically predisposed to be able to recognize sequences of context-free grammars with centre-embedded recursion while other primates are restricted to the recognition of finite state grammars with tail-recursion. Our aim was to construct a minimalist neural network that is able to parse artificial sentences of both grammars in an efficient way without using the biologically unrealistic backpropagation algorithm. The core of this network is a neural stack-like memory where the push and pop operations are regulated by synaptic gating on the connections between the layers of the stack. The network correctly categorizes novel sentences of both grammars after training. We suggest that the introduction of the neural stack memory will turn out to be substantial for any biological 'hierarchical processor' and the minimalist design of the model suggests a quest for similar, realistic neural architectures.

Communication in nature is not restricted to the transmitter-receiver pair. Unintended listeners, or eavesdroppers, can intercept the signal and possibly utilize the received information to their benefit, which may confer a certain cost to the communicating pair. In this paper we explore (computationally and mathematically) such situations with the goal of uncovering their effect on language evolution. We find that in the presence of eavesdropping, languages exhibit a tendency to become more complex. On the other hand, if eavesdroppers belong to a different (competing) population, the languages used by the two populations tend to converge, if the cost of eavesdropping is sufficiently high; otherwise the languages synchronize. These findings are discussed in the context of animal communication and human language. In particular, the emergence of synonyms is predicted. We demonstrate that a small associated cost can suppress synonyms in the absence of eavesdropping, but that their likelihood increases strongly with the probability of eavesdropping.

Cultural evolution is a complex process that can happen at several levels. At the level of individuals in a population, each human bears a set of cultural traits that he or she can transmit to its offspring (vertical transmission) or to other members of his or her society (horizontal transmission). The relative frequency of a cultural trait in a population or society can thus increase or decrease with the relative reproductive success of its bearers (individual's level) or the relative success of transmission (called the idea's level). This article presents a mathematical model on the interplay between these two levels. The first aim of this article is to explore when cultural evolution is driven by the idea's level, when it is driven by the individual's level and when it is driven by both.

The recent Bayesian approaches to language evolution and change seem to suggest that genetic biases can impact on the characteristics of language, but, at the same time, that its cultural transmission can partially free it from these same genetic constraints. One of the current debates centres on the striking differences between sampling and a posteriori maximising Bayesian learners, with the first converging on the prior bias while the latter allows a certain freedom to language evolution. The present paper shows that this difference disappears if populations more complex than a single teacher and a single learner are considered, with the resulting behaviours more similar to the sampler. This suggests that generalisations based on the language produced by Bayesian agents in such homogeneous single agent chains are not warranted. It is not clear which of the assumptions in such models are responsible, but these findings seem to support the rising concerns on the validity of the 'acquisitionist' assumption, whereby the locus of language change and evolution is taken to be the first language acquirers (children) as opposed to the competent language users (the adults).

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

The handicap principle has been applied to a number of different traits in the last three decades, but it is difficult to characterize its record, or even its perceived relevance, when it comes to an important human attribute ''spoken language. In some cases, assumptions regarding the energetic cost of speech, and the veracity of linguistically encoded messages, have failed to recognize critical aspects of human development, cognition, and social ecology. In other cases, the fact that speech contains honest (physiological) information, and tends to be used honestly with family and friends, has been overlooked. Speech and language are functionally related but they involve different resources. Individuals can increase the attractiveness of their speech, and of more stylized vocal and verbal performances, without enhancing linguistic structure or content; and they can modify their use of language without significant changes in the physical form of speech. That its production costs are normally low enables speech to be produced extravagantly in bids for status and mating relationships, and in evolution, may have allowed its content ''linguistic knowledge and structure ''to become complex.

The paper investigates the class of signaling games with the following properties: (a) the interests of sender and receiver coincide, (b) different signals incur differential costs, and (c) different events (meanings/types) have different probabilities. Necessary and sufficient conditions are presented for a profile to be evolutionarily stable and neutrally stable, and for a set of profiles to be an evolutionarily stable set.

The main finding is that a profile belongs to some evolutionarily stable set if and only if a maximal number of events can be reliably communicated. Furthermore, it is shown that under the replicator dynamics, a set of states with a positive measure is attracted to ``sub-optimal'' equilibria that do not belong to any asymptotically stable set.

It has recently been proposed [Dediu, D., Ladd, D.R., 2007. Linguistic tone is related to the population frequency of the adaptive haplogroups of two brain size genes, ASPM and Microcephalin. Proc. Natl Acad. Sci. USA 104(26), 10944-10949] that genetically coded linguistic biases can influence the trajectory of language change. However, the nature of such biases and the conditions under which they can become manifest have remained vague. The present paper explores computationally two plausible types of linguistic acquisition biases in a population of agents implementing realistic genetic, linguistic and demographic processes. One type of bias represents an innate asymmetric initial state (initial expectation bias) while the other an innate asymmetric facility of acquisition (rate of learning bias). It was found that only the second type of bias produces detectable effects on language through cultural transmission across generations and that such effects are produced even by weak biases present at low frequencies in the population. This suggests that learning preference asymmetries, very small at the individual level and not very frequent at the population level, can bias the trajectory of language change through the process of cultural transmission.

In signaling games the replicator dynamics does not almost always converge to states of perfect communication. A significant portion of the state space converges to components of Nash equilibria that characterize states of partial communication. Since these components consist of non-hyperbolic rest points, the significance of this result will depend on the dynamic behavior of specific perturbations of the replicator equations. In this paper we study selection-mutation dynamics of signaling games, which may be considered as one plausible perturbation of the replicator dynamics. We find that the long term behavior of the dynamics depends on the mutation rates of senders and receivers and on the relevance of communication.

This paper studies the evolution of a proto-language in a finite population under the frequency-dependent Moran process. A proto-language can be seen as a collection of concept-to-sign mappings. An efficient proto-language is a bijective mapping from objects of communication to used signs and vice versa. Based on the comparison of fixation probabilities, a method for deriving conditions of evolutionary stability in a finite population [Nowak et al., 2004. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 246-650], it is shown that efficient proto-languages are the only strategies that are protected by selection, which means that no mutant strategy can have a fixation probability that is greater than the inverse population size. In passing, the paper provides interesting results about the comparison of fixation probabilities as well as Maynard Smith's notion of evolutionary stability for finite populations [Maynard Smith, 1988. Can a mixed strategy be stable in a finite population? J. Theor. Biol. 130, 247-251] that are generally true for games with a symmetric payoff function.

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

The speech code is a vehicle of language: it defines a set of forms used by a community to carry information. Such a code is necessary to support the linguistic interactions that allow humans to communicate. How then may a speech code be formed prior to the existence of linguistic interactions? Moreover, the human speech code is discrete and compositional, shared by all the individuals of a community but different across communities, and phoneme inventories are characterized by statistical regularities. How can a speech code with these properties form? We try to approach these questions in the paper, using the `methodology of the artificial'. We build a society of artificial agents, and detail a mechanism that shows the formation of a discrete speech code without pre-supposing the existence of linguistic capacities or of coordinated interactions. The mechanism is based on a low-level model of sensory-motor interactions. We show that the integration of certain very simple and non language-specific neural devices leads to the formation of a speech code that has properties similar to the human speech code. This result relies on the self-organizing properties of a generic coupling between perception and production within agents, and on the interactions between agents. The artificial system helps us to develop better intuitions on how speech might have appeared, by showing how self-organization might have helped natural selection to find speech.

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

Human language is unique among the communication systems of the natural world. The vocabulary of human language is unique in being both culturally-transmitted and symbolic. In this paper I present an investigation into the factors involved in the evolution of such vocabulary systems. I investigate both the cultural evolution of vocabulary systems and the biological evolution of learning rules for vocabulary acquisition.

Firstly, vocabularies are shown to evolve on a cultural time-scale so as to fit the expectations of learners -- a population's vocabulary adapts to the biases of the learners in that population. A learning bias in favour of one-to-one mappings between meanings and words leads to the cultural evolution of communicativelyoptimal vocabulary systems, even in the absence of any explicit pressure for communication. Furthermore, the pressure to conform to the biases of learners is shown to outweigh natural selection acting on cultural transmission. Human language learners appear to bring a one-to-one bias to the acquisition of vocabulary systems. The functionality of human vocabulary may therefore be a consequence of the biases of human language learners.

Secondly, the evolutionary stability of genetically-transmitted vocabulary learning biases is investigated using both static and dynamic models. A one-to-one learning bias, which leads to the cultural evolution of optimal communication, is shown to be evolutionarily stable. However, the evolution de novo of this bias is complicated by the cumulative nature of the cultural evolution of vocabulary systems. This suggests that the biases of human language learners may not have evolved specifically and exclusively for the acquisition of communicatively-functional vocabulary.

Replicator-mutator equation is used to describe the dynamics of complex adaptive systems in population genetics, biochemistry and models of language learning. We study 'localized', or 'coherent', solutions, which are especially relevant in the context of learning and correspond to the existence of a predominant language in the population. There is a coherence threshold for learning fidelity, above which coherent communication can be maintained. We prove the following surprising universality property of coherence threshold: for typical realizations of random coefficients in the fitness matrix, the value of the coherence threshold does not depend on the size of the system.

Any mechanism of language acquisition can only learn a restricted set of grammars. The human brain contains a mechanism for language acquisition which can learn a restricted set of grammars. The theory of this restricted set is universal grammar (UG). UG has to be sufficiently specific to induce linguistic coherence in a population. This phenomenon is known as ``coherence threshold''. Previously, we have calculated the coherence threshold for deterministic dynamics and infinitely large populations. Here, we extend the framework to stochastic processes and finite populations. If there is selection for communicative function (selective language dynamics), then the analytic results for infinite populations are excellent approximations for finite populations; as expected, finite populations need a slightly higher accuracy of language acquisition to maintain coherence. If there is no selection for communicative function (neutral language dynamics), then linguistic coherence is only possible for finite populations.

Grammar is the computational system of language. It is a set of rules that specifies how to construct sentences out of words. Grammar is the basis of the unlimited expressibility of human language. Children acquire the grammar of their native language without formal education simply by hearing a number of sample sentences. Children could not solve this learning task if they did not have some pre-formed expectations. In other words, children have to evaluate the sample sentences and choose one grammar out of a limited set of candidate grammars. The restricted search space and the mechanism which allows to evaluate the sample sentences is called universal grammar. Universal grammar cannot be learned; it must be in place when the learning process starts. In this paper, we design a mathematical theory that places the problem of language acquisition into an evolutionary context. We formulate equations for the population dynamics of communication and grammar learning. We ask how accurate children have to learn the grammar of their parents' language for a population of individuals to evolve and maintain a coherent grammatical system. It turns out that there is a maximum error tolerance for which a predominant grammar is stable. We calculate the maximum size of the search space that is compatible with coherent communication in a population. Thus, we specify the conditions for the evolution of universal grammar.

A distinctive feature of all human languages is the diverse and arbitrary nature of the sign (signifier). This can be interpreted as stating that the mapping between signals and referents is established by convention rather than by functional constraints. This property of the sign provides for a great deal of linguistic flexibility and is a key component of symbolic communication. Game theoretic models to describe signal imitation are investigated with a view to understanding how non-arbitrary (indexical) animal-style signals might 'evolve' culturally into diverse, arbitrary signs. I explore the evolutionary hypothesis that private, arbitrary signs emerge as a result of selective imitation within a socially structured population. Once arbitrary signs have emerged, they contribute towards greater assortative interactions among individuals using a shared sign system. In natural populations, the models for imitation will very often be close kin. Hence, kinship provides one mechanism for the creation of true symbols. An imitation-structured population can support many more sign systems than an equivalent non-structured population and is one in which symbols become the dominant force in assortative interactions.

Language is about words and rules. While there is some discussion to what extent rules are learned or innate, it is clear that words have to be learned. Here I construct a mathematical framework for the population dynamics of language evolution with particular emphasis on how words are propagated over generations. I define the basic reproductive ratio of word, R, and show that R>1 is required for words to be maintained in the lexicon of a language. Assuming that the frequency distribution of words follow Zipf's law, an upper limit is obtained for the number of words in a language that relies exclusively on oral transmission.

This paper places models of language evolution within the framework of information theory. We study how signals become associated with meaning. If there is a probability of mistaking signals for each other, then evolution leads to an error limit: increasing the number of signals does not increase the fitness of a language beyond a certain limit. This error limit can be overcome by word formation: a linear increase of the word length leads to an exponential increase of the maximum fitness. We develop a general model of word formation and demonstrate the connection between the error limit and Shannon's noisy coding theorem.

Evolutionary models of communication are used to shed some light on the selective pressures involved in the evolution of simple referential signals, and the constraints hindering the emergence of signs. Error-prone communication results from errors in transmission (in which individuals learn the wrong associations) and communication (in which signs are mistaken for one another). We demonstrate how both classes of errors are required to generate diversity and subsequently impose limits on the sign repertoire within a population. We then explore the influence of geographic structuring of a population on the evolution of a shared sign system and the importance of such structure for the maintenance of sign diversity. Deceit tends to erode conventional signs systems thereby reducing signal diversity, we demonstrate that population structure can act as a hedge against deceit, thereby ensuring the persistence of sign systems.

We explore how evolutionary game dynamics have to be modified to accomodate a mathematical framework for the evolution of language. In particular, we are interested in the evolution of vocabulary, that is associations between signals and objects. We assume that successful communication contributes to biological fitness: individuals who communicate well leave more offspring. Children inherit from their parents a strategy for language learning (a language acquisition device). We consider three mechanisms whereby language is passed from one generation to the next: (i) parental learning: children learn the language of their parents; (ii) role model learning: children learn the language of individuals with a high payoff; and (iii) random learning: children learn the language of randomly chosen individuals. We show that parental and role model learning outperform random learning. Then we introduce mistakes in language learning and study how this process changes language over time. Mistakes increase the overall efficacy of parental and role model learning: in a world with errors evolutionary adaptation is more efficient. Our model also provides a simple explanation why homonomy is common while synonymy is rare.

Using a simple model of signaling of fighting ability, I demonstrate that; (1) conventional, cost-free, signals of fighting ability can be an ESS, (2) signals with significant costs can be used at ESS as long as they are used to indicate weakness rather than strength, (3) that if a set of signals is used to indicate a set of fighting abilities through their costs, they must decrease in cost for stronger signalers. The reason for this is that individuals of higher fighting ability have less to gain by avoiding escalated contests, and are thus more sensitive to signal costs. These results are of particular relevance to badges of status and other simultaneous signals used to settle contests over minor resources

The use of biological models and metaphors in studies of culture has a long and checkered history. While there are many superficial similarities between biological and cultural evolution, attempts to pin down such analogies have not been wholly successful. One limiting factor may be a lack of empirical evidence that the basic assumptions of the evolutionary model are met within a cultural system. We argue that a focus on the detection and description of the units of selection is an essential first step in constructing any evolutionary model. In this paper we outline the necessary connection between units of selection and evolution, describe the properties of a unit of selection, and introduce an empirical method for the detection of putative units of selection in a model cultural system: discourse within NetNews, a discussion system on the Internet.

Animal communication and human language have fundamental differences in their structures and functions. Furthermore, there is no living species demonstrating an intermediate stage of language evolution. Thus, we have difficulty in finding characteristics attributable to a communication system which can already be considered as a starting point for linguistic evolution. However, some findings coming from neurolinguistic research give us the opportunity to suppose that varying and arranging linguistic elements can be detached from other grammatical functions. Further information in this direction comes from apes' language-teaching experiments; namely bonobos (Panpaniscus) are able to understand and produce differences in meaning by varying word arrangements. Based on these results one can suppose that an acoustic signal system, which possesses discrete units for variable use, might be very ancient and might exist independent and prior to a more advanced language state. In the natural setting, acoustic territorial marking behaviour is exposed to selection pressure to elaborate sign systems built up from discrete, variable units. In addition to the well-known territorial bird songs, some monkey species and all species of lesser apes have territorial songs fitting these criteria. The analyses of the so-called long calls in chimpanzees and bonobos make it likely that the group-living great apes preserved the ability to create syntactically different calls, which would be developed by requirements of social life. A call repertoire emerged in these species, which contained a large number of call variants at group level available for each group member via social learning. This type of animal call is different from ordinary animal communication; its how some features of human language. It can represent an intermediate stage between animal communication and language, and communication system similar to this one can be considered as a starting point or first stage of language evolution.

I present a simple game, the Basic Action-Response game, which allows investigation of the claim that signals must be costly to be reliable. The Basic Action-Response game is the simplest communication game possible, by investigating its parameters we are able to define clearly ``conflict'', ``handicap'', ``communication'' and other relevant concepts. I explore the conditions on the magnitude of the stabilizing cost and handicap that must hold in order to maintain the evolutionary stability of signalling. It will be demonstrated that stable communication need not make use of costly signals at ESS, not even ``on average'', and that ``negative handicaps'' can be stable as long as the stabilizing cost is large enough.

The intricate phenomena of biology on one hand, and language and culture on the other, have inspired many writers to draw analogies between these two evolutionary systems. These analogies can be divided into four principal types: species/language, organism/concept, genes/culture, and cell/person. I argue that the last analogy--between cells and persons--is the most profound in several respects, and, more importantly, can be used to generate a number of empirical predictions. In the first half of the paper, the four analogies are each evaluated after briefly describing criteria for a good predictive analogy. In the second half of the paper, the cell/person analogy and predictions deriving from it are explored in detail.