Language Evolution and Computation Bibliography

Sociolinguistic studies have demonstrated that centrally-connected and peripheral members of social networks can both propel and impede the spread of linguistic innovations. We use agent-based computer simulations to investigate the dynamic properties of these network roles in a large social influence network, in which diffusion is modeled as the probabilistic uptake of one of several competing variants by agents of unequal social standing. We find that highly-connected agents, structural equivalents of leaders in empirical studies, advance on-going change by spreading competing variants. Isolated agents, or loners, holding on to existing variants are safe-keepers of variants considered old or new depending on the current state of the rest of the population. Innovations spread following a variety of S-curves and stabilize as norms in the network only if two conditions are simultaneously satisfied: (1) the network comprises extremely highly connected and very isolated agents, and (2) agents are biased to pay proportionally more attention to better connected, or popular, neighbors. These findings reconcile competing models of individual network roles in the selection and propagation process of language change, and support Bloomfield's hypothesis that the spread of linguistic innovations in heterogeneous social networks depend upon communication density and relative prestige.

It is widely assumed that, over their evolutionary history, languages increased in complexity from simple signals to protolanguages to complex syntactic structures. This papers investigates processes for increasing linguistic complexity while maintaining communicability across a pop- ulation. We assume that linguistic communicability is important for reliably exchanging infor- mation critical for coordination-based tasks. Interaction, needed for learning others languages and converging to communicability, bears a cost. There is a threshold of interaction (learning) effort beyond which convergence either doesn t pay or is practically impossible. Our central findings, established mainly through simulation, are: 1) There is an effort-dependent frontier of tractability for agreement on a language that balances linguistic complexity against linguis- tic diversity in a population. For a given maximum convergence effort either a) languages must be simpler, or b) their initial average communicability must be greater. Thus, if either conver- gence cost or high average communicability over time are important, then even agents who have the capability for using complex languages must not invent them from the start; they must start simple and grow. 2) A staged approach to increasing complexity, in which agents initially con- verge on simple languages and then use these to scaffold greater complexity, can outperform initially-complex languages in terms of overall effort to convergence. This performance gain improves with more complex final languages.

An important problem for societies of natural and artificial animals is to converge upon a similar language in order to communicate. We call this the language convergence problem. In this paper we study the complexity of finding the optimal (in terms of time to convergence) algorithm for language convergence. We map the language convergence problem to instances of a Decentralized Partially Observable Markov Decision Process to show that the complexity can vary from P-complete to NEXP-complete based on the scenario being studied.

We suggest that the primary motivation for an agent to construct a symbol-meaning mapping is to solve a task. The meaning space of an agent should be derived from the tasks that it faces during the course of its lifetime. We outline a process in which agents learn to solve multiple tasks and extract a store of ``cumulative knowledge'' that helps them to solve each new task more quickly and accurately. This cumulative knowledge then forms the ontology or meaning space of the agent. We suggest that by grounding symbols to this extracted cumulative knowledge agents can gain a further performance benefit because they can guide each others' learning process. In this version of the symbol grounding problem meanings cannot be directly communicated because they are internal to the agents, and they will be different for each agent. Also, the meanings may not correspond directly to objects in the environment. The communication process can also allow a symbol meaning mapping that is dynamic. We posit that these properties make this version of the symbol grounding problem realistic and natural. Finally, we discuss how symbols could be grounded to cumulative knowledge via a situation where a teacher selects tasks for a student to perform.