Language Evolution and Computation Bibliography

Linguistic meaning is a convention. This article investigates how such conventions can arise for color categories in populations of simulated 'agents'. The method uses concepts from evolutionary game theory: A language game where agents assign names to color patches and is played repeatedly by members of a population. The evolutionary dynamics employed make minimal assumptions about agents' perceptions and learning processes. Through various simulations it is shown that under different kinds of reasonable conditions involving outcomes of individual games, the evolutionary dynamics push populations to stationary equilibria, which can be interpreted as achieving shared population meaning systems. Optimal population agreement for meaning is characterized through a mathematical formula, and the simulations presented reveal that for a wide variety of situations, optimality is achieved.

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.

The evolution of color categorization is investigated using artificial agent population categorization games, by modeling observer types using Farnsworth-Munsell 100 Hue Test performance to capture human processing constraints on color categorization. Homogeneous populations of both normal and dichromat agents are separately examined. Both types of populations produce near-optimal categorization solutions. While normal observers produce categorization solutions that show rotational invariance, dichromats' solutions show symmetry-breaking features. In particular, it is found that dichromats' local confusion regions tend to repel color category boundaries and that global confusion pairs attract category boundaries. The trade-off between these two mechanisms gives rise to population categorization solutions where color boundaries are anchored to a subset of locations in the stimulus space. A companion paper extends these studies to more realistic, heterogeneous agent populations [J. Opt. Soc. Am. A 26, 1424-1436 (2009)].

The evolution of color categorization is investigated using computer simulations of agent population categorization games. Various realistic observer types are implemented based on Farnsworth-Munsell 100 Hue Test human performance data from normal and anomalous trichromats, dichromats, and humans with four retinal photopigments. Results show that (i) a small percentage of realistically modeled deficient agents greatly affects the shared categorization solutions of the entire population in terms of color category boundary locations; (ii) for realistically modeled populations, dichromats have the strongest influence on the color categorization; their characteristic forms of color confusion affect (i.e., attract or repel) color boundary locations and accord with our findings for homogeneous dichromat populations [J. Opt. Soc. Am. A26, 1414-1423 (2009)]; (iii) adding anomalous trichromats or trichromat aexpertsa does not destabilize the solutions or substantially alter solution structure. The results provide insights regarding the mechanisms that may constrain universal tendencies in human color categorization systems.

Specifying the factors that contribute to the universality of color categorization across individuals and cultures is a longstanding and still controversial issue in psychology, linguistics, and anthropology. The present article approaches this issue through the simulated evolution of color lexicons. It is shown that the combination of a minimal perceptual psychology of discrimination, simple pragmatic constraints involving communication, and simple learning rules are enough to evolve color naming systems. Implications of this result for psychological theories of color categorization and the evolution of color naming systems in human societies are discussed.

In the course of natural history, Evolution has come up with several great innovations, such as nucleic acids, proteins, cells, chromosomes, multi-cellular organisms, the nervous system.... The last ``invention'' which truly revolutionized the very rules of evolution is language. It gives us an unprecedented possibility to transmit information from generation to generation not by the ``traditional'' means of a genetic code, but by talking. This new mode of cross-generational information transfer has given rise to the so-called ``cultural evolution''. It is responsible for a big part of being ``human''. It is shaping the history and changing the rules of biology. Without exaggeration, it is one of the most fascinating traits of Homo Sapiens.

We consider the problem of linguistic agents that communicate with each other about a shared world. We develop a formal notion of a language as a set of probabilistic associations between form (lexical or syntactic) and meaning (semantic) that has general applicability. Using this notion, we define a natural measure of the mutual intelligibility, F(L,L'), between two agents, one using the language L and the other using L'. We then proceed to investigate three important questions within this framework: (1) Given a language L, what language L' maximizes mutual intelligibility with L? We find surprisingly that L' need not be the same as L and we present algorithms for approximating L' arbitrarily well. (2) How can one learn to optimally communicate with a user of language L when L is unknown at the outset and the learner is allowed a finite number of linguistic interactions with the user of L? We describe possible algorithms and calculate explicit bounds on the number of interactions needed. (3) Consider a population of linguistic agents that learn from each other and evolve over time. Will the community converge to a shared language and what is the nature of such a language? We characterize the evolutionarily stable states of a population of linguistic agents in a game-theoretic setting. Our analysis has significance for a number of areas in natural and artificial communication where one studies the design, learning, and evolution of linguistic communication systems.

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.

Language is our legacy. It is the main evolutionary contribution of humans, and perhaps the most interesting trait that has emerged in the past 500 million years. Understanding how darwinian evolution gives rise to human language requires the integration of formal language theory, learning theory and evolutionary dynamics. Formal language theory provides a mathematical description of language and grammar. Learning theory formalizes the task of language acquisition--it can be shown that no procedure can learn an unrestricted set of languages. Universal grammar specifies the restricted set of languages learnable by the human brain. Evolutionary dynamics can be formulated to describe the cultural evolution of language and the biological evolution of universal grammar.

Language is an apparent miracle. Children master it with exceptional ease, while simultaneously struggling to walk, hold a fork, and recognize that others have thoughts and emotions that differ from their own. They perform, with near perfection, mental computation and generalizations about language which are virtually impossible for state of the art computers. They grasp the tree-like phrase structure of language even though their parents have never taught them, and most probably couldn't even if they wanted to (such properties of language are not the stuff of school education). And children babble on about the present, past, and future, creating imaginary worlds that no one but they can see.

The language acquisition period in humans lasts about 13 years. After puberty it becomes increasingly difficult to learn a language. We explain this phenomenon by using an evolutionary framework. We present a dynamical system describing competition between language acquisition devices, which differ in the length of the learning period. There are two selective forces that play a role in determining the critical learning period: (i) having a longer learning period increases the accuracy of language acquisition; (ii) learning is associated with certain costs that affect fitness. As a result, there exists a limited learning period which is evolutionarily stable. This result is obtained analytically by means of a Nash equilibrium analysis of language acquisition devices. Interestingly, the evolutionarily stable learning period does not maximize the average fitness of the population.

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.

The lexical matrix is an integral part of the human language system. It provides the link between word form and word meaning. A simple lexical matrix is also at the center of any animal communication system, where it defines the associations between form and meaning of animal signals. We study the evolution and population dynamics of the lexical matrix. We assume that children learn the lexical matrix of their parents. This learning process is subject to mistakes: (i) children may not acquire all lexical items of their parents (incomplete learning); and (ii) children might acquire associations between word forms and word meanings that differ from their parents' lexical items (incorrect learning). We derive an analytic framework that deals with incomplete learning. We calculate the maximum error rate that is compatible with a population maintaining a coherent lexical matrix of a given size. We calculate the equilibrium distribution of the number of lexical items known to individuals. Our analytic investigations are supplemented by numerical simulations that describe both incomplete and incorrect learning, and other extensions.

Universal grammar specifies the mechanism of language acquisition. It determines the range of grammatical hypothesis that children entertain during language learning and the procedure they use for evaluating input sentences. How universal grammar arose is a major challenge for evolutionary biology. We present a mathematical framework for the evolutionary dynamics of grammar learning. The central result is a coherence threshold, which specifies the condition for a universal grammar to induce coherent communication within a population. We study selection of grammars within the same universal grammar and competition between different universal grammars. We calculate the condition under which natural selection favors the emergence of rule-based, generative grammars that underlie complex language.

Language is a biological trait that radically changed the performance of one species and the appearance of the planet. Understanding how human language came about is one of the most interesting tasks for evolutionary biology. Here we discuss how natural selection can guide the emergence of some basic features of human language, including arbitrary signs, words, syntactic communication and grammar. We show how natural selection can lead to the duality of patterning of human language: sequences of phonemes form words; sequences of words form sentences. Finally, we present a framework for the population dynamics of grammar acquisition, which allows us to study the cultural evolution of grammar and the biological evolution of universal grammar.