To depict the mechanisms that have enabled the emergence of semantic meaning, philosophers and researchers particularly access a game-theoretic model: the signaling game. In this article I will argue that this model is also quite appropriate to analyze not only the emergence of semantic meaning, but also semantic change. In other words, signaling games might help to depict mechanisms of language change. For that purpose the signaling game will be i) combined with innovative reinforcement learning and ii) conducted repeatedly as simulation runs in a multi-agent account, where agents are arranged in social network structures: scale-free networks with small-world properties. The results will give a deeper understanding of the role of environmental variables that might promote semantic change or support solidity of semantic conventions.
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."[
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 [
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 [
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 [
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 [
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 [
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. 2.1
A signaling game SG = hfS; Rg; T; M; A; P r; U i 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) 2 (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 = ft1; t2g, M = fm1; m2g, A = fa1; a2g, a at probability distribution of P r(t) = 1=jT j 8t 2 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 (ti; aj ) = 1 i 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 i 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 de ned in De nition 1.
jT j = jAj = n, jM j = k, 8t 2 T : P r(t) = 1=jT j and U (ti; aj ) = k-game is a signaling game SG with: 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 de ned 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 pro le. A message has a meaning between a sender and a receiver, if both use pure strategies that constitute a speci c isomorphic strategy pro le. For the 2 2-game there are exactly 2 such strategy pro les, as depicted in Figure 1. Here in pro le L1 the message m1 has the meaning of state t1=a1 and message m2 has the meaning of state t2=a2. For pro le L2 it is exactly the other way around. 2 (X) : X ! R denotes a probability distribution over random variable X. 3 Informally, the information state came to the sender's mind. In game theory we say that the state is chosen by an invisible participant, called nature N .
L1: t1 t2 m1 m2 a1 a2
L2: t1 t2 m1 m2 a1 a2
Lewis called such strategy pro les 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 rst 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 [
(mjt) = m(ft) jftj (1) (ajm) = a(fm) jfmj (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 ft is increased by 2 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 intensi ed by lateral inhibition: if communication
via t, m and a is successful, not only will the number of ball type m in urn ft
be increased, but also will the number of all other ball types m0 2 M n fmg be
decreased by 2 N. Similarly, for the receiver. Franke and Jager [
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 ft is decreased by 2 N balls of type m; and the number of balls in the receiver's urn fm is decreased by balls of type a.
Note that reinforcement learning might have the property to slow down the
learning e ect: if the total number of balls in an urn increases over time, but
the rewarding value is a xed value, then the learning e ect mitigates. A way
to prevent learning from slowing down is to keep the overall number of balls jfj
on a xed value by scaling the urn content appropriately after each round of
play. Such a setup is a variant of so-called Bush-Mosteller reinforcement [
All in all, a reinforcement learning setup for a signaling game can be captured by RL = h( ; ); ; ; ; ; i, 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 de nes 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 [
The second study [
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 [
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 [
P T S(n) = m2N(n)
N(n)[N(m)
N(n)\N(m)
jN (n)j
(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.
5 For the de nition of these network properties I refer to Jackson's Social and
Economic Networks [
Finally, as the experiments will show, agents in a social network agree on signaling systems as groups, which constitute connected components6. Such a group-wide signaling system is called a signaling convention (De nition 3). De nition 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. 3
A fascinating puzzle in the theory of language change is the threshold-problem[
Some sociolinguists expect particular environmental patterns of the social
network structure to be source and engine for language change [
In my experiments agents in a social network communicate via signaling
games and update by innovative reinforcement learning. This leads to the e ect
that i) multiple local conventions emerge (see c.f.[
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:
6 A connected component of a network is a subgraph in which any two nodes are
connected to each other by at least one path.
{ network structure: a scale-free network with 500 agents (Holme-Kim
algorithm [
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. 3.2
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 rst 10,000 simulation steps for
the number of learners for 6 di erent signaling conventions: here regions of new
conventions emerge, grow to a speci c 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 speci c 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 speci c structural patterns support
such a behavior.
7 Since generally agents do not learn a totally pure strategy, an agent is attributed
to have learned a signaling convention, when her behavioral strategy pro le and a
signaling system reveal a so-called Hellinger similarity of > :7. For a formal de nition
see [
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 de ned and measured the dynamic
features innovation skill and impact. To compare these values to a number of
further dynamic features, I also de ned and measured loyalty, interiority and
mutual intelligibility. For an agent n these features are de ned 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 I8 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 di erent
strategy pairs. For the de nition see [
S T
C D
C C
C B
L C
V N I 0.8 0.6
In my analysis I measured the correlation of all 5000 data points9 and for each possible combination of feature. The resulting plot is shown in Figure 3: here correlations are depicted as circles, where the size represents the strength of the correlation, and the brightness represents the direction of the relationship (positive: light, negative, dark).
The results show rst of all: the data support the weak-tie theory, since i) IN V has a high negative correlation with T S, and ii) IM P reveals a high positive correlation with all three centrality properties DC, CC and BC. Thus, innovation mostly starts at weak ties and spreads via central nodes.
But there are further interesting correlations. IN V has a high negative
correlation with LOY , M I and IN T . This shows that innovative agents i) do hardly
stay with their favorite convention, ii) are not very intelligible to neighbors, and
iii) are rather positioned at the border of a convention region. Note: the point
that innovation is expected to emerge at the periphery of societies was also
supported by eld studies and computational work [
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 rst 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 { innovation {
that supports the changing nature of the population's dynamics. In my analysis
I compared di erent features of agents { static network properties and dynamic
behavioral properties of agents { to extract the characteristics of di erent roles
that might be involved in language change. The results support the weak
tiestheory: innovation start at weak ties and spreads via central nodes [
Since this study gives only a rst 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 nd 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 ow measures [