Introduction

"What are the mechanisms that can explain the emergence of semantic meaning?" Philosophers have long been concerned with this question. Russell once said: "[w]e can hardly suppose a parliament of hitherto speechless elders meeting together and agreeing to call a cow a cow and a wolf a wolf." [24]. With this sentence Russell wanted to point to a particular paradox of the evolution of human language: language (as a tool to make verbal agreements) is needed for language (in form of semantic meaning) to emerge.

Lewis found a very elegant solution for this paradox: he showed that semantic meaning can arise without previous agreements, but just by regularities in communicative behavior. He showed it with a game-theoretical model: the signaling game [16]. This game basically models a communicative situation between a speaker and a hearer, and just by playing this game repeatedly and using simple update mechanisms to adjust subsequent behavior, both participants might finally agree on semantic conventions without making an overt verbal agreement in advance [25]. In other words: semantic meaning can arise automatically and "unconsciously" just by repeated communication and simple adaption mechanisms; 1 a signaling game is an elegant way to formalize these dynamics.

Apparently, quite similar mechanism can be assumed for language change, or to be more precise: for semantic innovation, semantic shift and semantic loss. Like we cannot assume that speechless elders made agreements to call a wolf a "wolf", we furthermore cannot assume that the people in the 1970s made a public announcement to use the word "groovy" when they wanted to express that something is really nice, and another announcement in the 1980s, that people should not use this word anymore. Just as semantic meaning can emerge in an unconscious and automatic way, in the same way, expressions arise, change their meaning, or get lost. It seems to be plausible that a signaling game might also be an appropriate model to explain general mechanisms of semantic change.

A number of studies came up to analyze how semantic meaning arises in realistic population structures, by conducting multi-agent simulations: applying repeated signaling games between connected agents placed in social network structures, c.f. lattice structures [31,18] and small-work networks [28,20]. Next to the signaling game, another line of research uses the so-called naming game [26] to analyze the emergence of semantic conventions in realistic population structures [27,5]. It can be shown that both accounts imply similar mechanisms and reveal similar resulting dynamics. However, as mentioned before, all these studies analyze how semantic meaning 'arises', not how it 'changes'.

Another line of research uses multi-agent simulations to analyze language change in social network structures, but without applying signaling games or similar models of communication [22,14,9]. In these studies agents i) do not communicate, but just choose among (linguistic) variants they are aware of and ii) make explicit decisions of what variant to use. Because of the first point these studies somehow lack the quintessence of language change, namely that it happens through repeated communication. Because of the second point these studies let agents behave in a much too "conscious" way. Language change might usually be the result of much more unconscious decisions and hidden dynamics.

In this study I use repeated signaling games in combination with an update mechanism that depicts unconscious behavior of decision making. This mechanism is called reinforcement learning [23]. Applying reinforcement learning on repeated signaling games is not new, but in fact one of the most popular dynamics in this field [3,4,25]. What is new in this study is the fact that the account is applied to analyze the change rather than the emergence of semantic conventions. For that purpose signaling games and reinforcement learning will be employed to conduct simulation experiments of communicating agents in social network structures with the goal to evaluate the environmental factors that might or might not support semantic change or stability.

This article is divided in the following way: in Section 2 some basic notions of repeated signaling games, reinforcement learning dynamics and network theory will be introduced. Furthermore, I will discuss a noteworthy extension for reinforcement learning, called innovation [25,1]. It can be shown that this additional feature realizes an interesting interplay between stabilizing and renewing effects [21]; and I will adopt it for my experiments, which are described and analyzed in Section 3. A final conclusion will be presented in Section 4.

Signaling Games, Learning and Networks

This section will give a coarse technical and theoretical background to understand the important concepts of this article: the signaling game, reinforcement learning with innovation, and some basic notions of network theory.

Signaling Games

A signaling game SG = {S, R}, T, M, A, P r, U is a game played between a sender S and a receiver R. T is a set of information states, M is a set of messages and A is a set of interpretation states (or actions). Pr(t) ∈ ∆(T )2 is a probability distribution over T and describes the probability that an information state is topic of communication. U : T × A → R is a utility function that basically determines how well an interpretation state matches an information state.

Let us take a look at the simplest variant of the game where we have two states, two messages and two actions:

T = {t 1 , t 2 }, M = {m 1 , m 2 }, A = {a 1 , a 2 }, a flat probability distribution of P r(t) = 1 /|T | ∀t ∈ T ,

and a simple utility function that gives a positive value if the interpretation state a matches the information state t, marked by the same index: U (t i , a j ) = 1 iff i = j, else 0. Such a game is played as follows: an information state t is chosen with prior probability P r3 , which the sender wants to communicate to the receiver by choosing a message m. The receiver wants to decode this message by choosing an interpretation state a.

Communication is successful iff the information state matches the interpretation state. In this study only a subset of all possible signaling games is considered, which I call n × k-games, as defined in Definition 1.

Definition 1 (n × k-game).

A n × k-game is a signaling game SG with:

|T | = |A| = n, |M | = k, ∀t ∈ T : P r(t) = 1 /|T | and U (t i , a j ) = 1 if i = j 0 else

Note that messages are initially meaningless in this game, but meaningfulness can arise from regularities in behavior. Behavior is here defined in terms of strategies. A behavioral sender strategy is a function σ : T → ∆(M ), and a behavioral receiver strategy is a function ρ : M → ∆(A). A behavioral strategy can be interpreted as a single agent's probabilistic choice. Now, what circumstances can tell us that a message is attributed with a meaning? The answer is: this can be indicated by the combination of sender and receiver strategy, called strategy profile. A message has a meaning between a sender and a receiver, if both use pure strategies that constitute a specific isomorphic strategy profile. For the 2 × 2-game there are exactly 2 such strategy profiles, as depicted in Figure 1. Here in profile L 1 the message m 1 has the meaning of state t 1 /a 1 and message m 2 has the meaning of state t 2 /a 2 . For profile L 2 it is exactly the other way around. Lewis called such strategy profiles signaling systems [16], which have interesting properties. It can be shown that signaling systems i) ensure perfect communication and maximal utility, ii) are Nash equilibria over expected utilities [7], and iii) are evolutionary stable states [29] [12]. Furthermore, note that the number of signaling systems increases strongly with the number of states and/or messages: an n × k-game has k! /(k−n)! possible signaling systems.

At this point it is explained how semantic meaning can be expressed by participants' communicative behavior: a message has a meaning, if sender and receiver communicate according to a signaling system. However, this does not explain at all, how participants come to such a signaling system in the first place, by expecting that messages are initially meaningless. To explore the paths that might lead from a meaningless to a meaningful message, it is necessary to explore the process that leads from participants' arbitrary communicative behavior to a behavior that constitutes a signaling system. Such a process can be simulated by repeated signaling games, where the participants' behavior is guided by update dynamics. One popular dynamics is called reinforcement learning [3,4,25].

Reinforcement Learning and Innovation

Reinforcement learning can be captured by a simple model based on urns, also known as Pólya urns [23]. An urn models a behavioral strategy, in the sense that the probability of making a particular decision is proportional to the number of balls in the urn that correspond to that choice. By adding or removing balls from an urn after each access, an agent's behavior is gradually adjusted. For signaling games, the sender has an urn t for each state t ∈ T , which contains balls for different messages m ∈ M . The number of balls of type m in urn t designated with m( t ), the overall number of balls in urn t with | t |. If the sender is faced with a state t she draws a ball from urn t and sends message m, if the ball is of type m. The same holds in the same way for the receiver. The resulting sender response rule σ and receiver response rule ρ is given in Equation 1 and 2, respectively.

σ(m|t) = m( t ) | t | (1) ρ(a|m) = a( m ) | m |(2)

The learning dynamics is realized by changing the urn content dependent on the communicative success. The standard account works as follows: if communication via t, m and a is successful, the number of balls in urn t is increased by α ∈ N balls of type m. Similarly, for the receiver. In this way successful communicative behavior is more probable to reappear in subsequent rounds.

This mechanism can be intensified by lateral inhibition: if communication via t, m and a is successful, not only will the number of ball type m in urn t be increased, but also will the number of all other ball types m ∈ M \ {m} be decreased by γ ∈ N. Similarly, for the receiver. Franke and Jäger [10] introduced the concept of lateral inhibition for reinforcement learning in signaling games and showed that it leads the system more speedily towards pure strategies.

Furthermore, negative reinforcement can be used to punish unsuccessful behavior. It changes urn contents in the case of unsuccessful communication in the following way: if communication via t, m and a is unsuccessful, the number of balls in the sender's urn t is decreased by β ∈ N balls of type m; and the number of balls in the receiver's urn m is decreased by β balls of type a.

Note that reinforcement learning might have the property to slow down the learning effect: if the total number of balls in an urn increases over time, but the rewarding value α is a fixed value, then the learning effect mitigates. A way to prevent learning from slowing down is to keep the overall number of balls | | on a fixed value Ω by scaling the urn content appropriately after each round of play. Such a setup is a variant of so-called Bush-Mosteller reinforcement [6].

All in all, a reinforcement learning setup for a signaling game can be captured by RL = (σ, ρ), α, β, γ, Ω, φ , where σ and ρ are the participants' response rules, α is the reward value, β the punishment value, γ the lateral inhibition value and Ω the urn size. Finally, φ is a function that defines the initial urn settings.

With the goal to analyze issues of language change, a really interesting additional feature for reinforcement learning is called innovation. The basic idea stems from Skyrms [25] and works as follows: each sender urn contains, next to the balls for each message, an additional ball type, which Skyrms calls black ball. Whenever the sender draws a black ball from an urn, he sends a completely new message that was never sent before. In other words, the sender invents a new message. Further experiments with this setup were made for 2-players games [1] as well as for multi-agent accounts [21].

The second study [21] used a reinforcement learning setup with negative reinforcement and lateral inhibition. In such a setup the black balls of the agents' sender urns can increase and decrease in dependence of communicative success. By naming the total number of an agent's black balls her force of innovation, the study revealed an interesting relationship between society-wide force of innovation and communicative success: increasing communicative success leads to decreasing force of innovation, and vice versa. 4 Note that this relationship between both values implies two things: i) once a population has learned one unique signaling convention and reaches perfect communication, the force of innovation has dropped to zero: the society has reached a stable state without any spirit of innovation; ii) if the society contains multiple conventions and communication is therefore not perfectly successful society-wide, the force of innovation has a positive level and produces new strategies that might finally manifest as new conventions; in other words: language change is possible to be realized.

Basic Notions of Network Theory

To ensure that a network structure resembles a realistic interaction structure of human populations, it should have small-world properties; c.f. Jackson found out that these properties show in the analysis of human friendship networks [13]. According to this line of studies, the essential two properties of small-world networks are i) a short characteristic path length, and ii) a high clustering coefficient [30]. 5 Additionally, most often human networks display a third property, namely to be scale-free: the frequency of agents with ever larger numbers of connections roughly follows a power-law distribution. In this sense I consider a special kind of a scale-free network, which is both scale-free and has small-world properties [2]. This network type is constructed by a preferential attachment algorithm that takes two parameters m that controls the network density, and p that controls the clustering coefficient [11]. In my experiment I used a scale-free network with 500 nodes, m = 2 and p = .8, which ensures small-world properties.

A main goal of this work is to investigate the relationship between the change of meaning and the structural properties of the network and its members. As the experiments will show, there seems to be an explanatory value of network properties that express an agent's connectivity and embeddedness. In order to capture these properties more adequately, suitable notions from social network theory will be considered: degree centrality (DC) describes the local connectivity of an agent, closeness centrality (CC) and betweenness centrality (BC) her global centrality, and individual clustering (CL) her local embeddedness. 5 As I will argue later, also the strength of ties between agents might play an important role in language change. Easley and Kleinberg [8] showed that the strength of a tie between two agents has basically a strong linear correlation with the overlap of both agents' neighborhoods. To keep things easy I will define the strength of a tie by this neighborhood overlap. Furthermore, since my analysis deals with agents rather than with ties between them, I calculate an agent's ties strength T S as the average strength value of all ties of this agent: Definition 2 (Ties Strength). For a given network the ties strength of agent n is defined as follows (where N (i) is the set of neighbors of agent i):

T S(n) = m∈N (n) N (n)∪N (m) N (n)∩N (m) |N (n)|(3)

Note: the notions of DC, CC, BC, CL and T S describe static network properties of an agent, since they do not change during a simulation run and are determined by the network structure and the agent's position inside it.

Finally, as the experiments will show, agents in a social network agree on signaling systems as groups, which constitute connected components 6 . Such a group-wide signaling system is called a signaling convention (Definition 3). Definition 3 (Signaling Convention). For a given network structure of agents that play the repeated signaling game with their connected neighbors, a signaling convention is a signaling system that is used by a group of agents that constitutes a connected component of the network structure.

Simulating Language Change

A fascinating puzzle in the theory of language change is the threshold-problem [22]: how can a new linguistic variant spread and reach a particular threshold of speakers that enables to replace a concurrent old variant? To reach such a threshold is rather improbable considering the facts that i) the new variant is expected to be initially used by a minority and ii) the old variant is expected to be a societywide linguistic conventions that serves for perfect communication. Therefore, sociolinguists expect that new variants mostly do not disseminate but remain in small social groups, often with short durability [17]. Now, what enables new variants in rare cases to spread and establish a new linguistic convention? Some sociolinguists expect particular environmental patterns of the social network structure to be source and engine for language change [17]. Their weakties theory purports that new (innovative) variants i) emerge most often among edges that constitute weak ties in the social network, and ii) disseminate via central nodes. According to the theory, exactly the combination of weak ties and central nodes supports new variants to overcome the threshold problem [17].

In my experiments agents in a social network communicate via signaling games and update by innovative reinforcement learning. This leads to the effect that i) multiple local conventions emerge (see c.f. [31,18,28,20]), and ii) agents invent new messages from time to time, since communication is not perfectly successful in a society with multiple conventions and therefore the force of innovation stays on a positive level. As my experiments will show, while mostly invented messages disappear as fast as they appear, from time to time new variants can spread and realize new regional conventions. Therefore, I want to analyze if particular structural features support emergence and spread of innovation. Do the results support the weak-tie theory? Is it possible to detect other network properties that support language change?

Experimental Settings

I conducted simulation runs of agents that are placed in a social network structure. Per simulation step the agents communicate by playing a signaling game with each of their direct neighbors. They update their behavior by innovative reinforcement learning. The concrete settings of the experiments were as follows:

network structure: a scale-free network with 500 agents (Holme-Kim algorithm [11] with m = 2 and p = .8) signaling game: a 3 × 9-game reinforcement learning: Bush-Mosteller reinforcement with negative reinforcement and lateral inhibition (α = 1, β = 1, γ = 1, Ω = 20) stop condition: reaching 100,000 simulation steps initiation condition: the network is initially divided in 8 connected components, and agents communicate only with neighbors of the same component with a given signaling system for the first 100 simulation steps number of simulation runs: 10 Since I am interested in the mechanisms that show how and why semantic conventions change, not how they evolve from the scratch, the simulation runs were started with the given initiation condition, which ensures that already established local signaling conventions are given from the beginning. In the following the results of the simulation runs will be presented.

Global Values

To get a good impression of how the population behaves during a simulation run, two global values were measured: i) the average communicative success: the utility value of a played game averaged over all plays during a simulation step, and ii) the global number of signaling conventions: the total number of signaling conventions agents have learned7 at the given simulation step.

In all simulation runs similar results were observed: after around 1,000 simulation steps the average communicative success increased to a value of around .85, and the number of signaling conventions to a value of around 25. Furthermore, while both values show no tendency to increase or decrease in the long-run, they oscillate quite strongly: the communicative success oscillates between .8 and .9 and the number of signaling conventions oscillates between 20 and 30. This result reveals a global interaction dynamics that shows long-term stability and short-term reactivity at the same time.

Especially the oscillation of the number of signaling conventions is an indicator for local reactivity. To get a better understanding of what is actually happening, Figure 2 shows a sequence of the first 10,000 simulation steps for the number of learners for 6 different signaling conventions: here regions of new conventions emerge, grow to a specific amount and possibly get extinct. This pattern shows quite nicely how language change is realized: an innovation is made at one point in time and place, and then it spreads and its number of speakers increases to a specific amount and constitutes a region of a new signaling convention. The next step is now to detect agents that tend to contribute to innovation and spread, and to investigate if specific structural patterns support such a behavior.

Agent Features

Considering the dynamic picture of language change in the simulation runs, I was interested if it is possible to detect specific roles of agents that might support language change or strengthen local conventions. Following the study of Mühlenbernd and Franke [20], I was particularly interested in the way an agent's static structural features and dynamic behavioral features might correlate. Static features are given by an agent's network properties ties strength T S, degree centrality DC, closeness centrality CC, betweenness centrality BC and clustering coefficient CL, as introduced in Section 2.3.

Dynamic features of an agent can be measured through her behavior or position during a simulation run. Since I was interested in the way agents were involved in the spread of a new variant, I defined and measured the dynamic features innovation skill and impact. To compare these values to a number of further dynamic features, I also defined and measured loyalty, interiority and mutual intelligibility. For an agent n these features are defined as follows:

innovation skill IN V (n): the proportion of simulation steps at which agent n switched to a new convention, which no neighbor has actually learned impact IM P (n): the proportion of simulation steps at which a neighbor of agent n switched to agent n's convention loyalty LOY (n): the proportion of simulation steps agent n played her favorite strategy (most often played strategy) interiority IN T (n): the proportion of simulation steps for which agent n has exclusively neighbors with the same convention mutual intelligibility M I(n): the average M I 8 value of agent n to her neighborhood at a given simulation step, averaged over all simulation steps 8 The mutual intelligibility value M I reproduces the expected utility for two different strategy pairs. For the definition see [21], Definition 3.

Conclusion

In this study I used the signaling game -a model that is generally used to deal with issues of language evolution -to analyze the dynamics of language change. At first this is an ambitious challenge by considering that signaling games are designed in a way that players are generally attracted to convention and stability. For all that, I was particularly interested in the way environmental variables in terms of network structure might describe characteristics that promote or mitigate semantic change. For that purpose I made experiments on social network structures of agents that play the signaling game repeatedly with connected neighbors and update their behavior by a simple dynamics: reinforcement learning. I extended this learning account by an additional feature -innovationthat supports the changing nature of the population's dynamics. In my analysis I compared different features of agents -static network properties and dynamic behavioral properties of agents -to extract the characteristics of different roles that might be involved in language change. The results support the weak tiestheory: innovation start at weak ties and via central nodes [17]. Since this study gives only a first impression of where to look for forces of language change, there are at least two steps necessary to reveal more insightful results. First of all, the current data should be further analyzed by using regression models to find out, if there are non-trivial interactions -e.g. non-linear dependencies -between static network properties and the role of agents in language change dynamics. Second, my current results indicate to analyze further i) static properties, like information flow measures [13] or closeness vitality [15]; and ii) dynamic features like the individual force of innovation, the number of known messages or the growth magnitudes of an agent's newly innovated signaling system. These two additional steps are currently investigated and can hopefully enrich subsequent work by delivering deeper insights into the role of innovation in dynamics of semantic change.