The origins of Zipf's meaning-frequency law

The Origins of Zipf’s Meaning-Frequency Law Ramon Ferrer-i-Cancho Complexity and Quantitative Linguistics Lab. LARCA Research Group, Departament de Cie `ncies de la Computaci o, Universitat Polite `cnica de Catalunya, Campus Nord, Edifici Omega, Jordi Girona Salgado 1-3, 08034 Barcelona, Catalonia, Spain. E-mail: [email protected] Michael S. Vitevitch Spoken Language Laboratory, Department of Psychology, University of Kansas, 1415 Jayhawk Blvd., Lawrence, KS 66045, USA. E-mail: [email protected] In his pioneering research, G.K. Zipf observed that more frequent words tend to have more meanings, and showed that the number of meanings of a word grows as the square root of its frequency. He derived this relationship from two assumptions: that words follow Zipf’s law for word frequencies (a power law dependency between frequency and rank) and Zipf’s law of meaning distribution (a power law dependency between number of meanings and rank). Here we show that a single assumption on the joint probability of a word and a meaning suffices to infer Zipf’s meaning-frequency law or relaxed versions. Interestingly, this assumption can be justified as the outcome of a biased random walk in the process of mental exploration. Introduction G.K. Zipf (1949) investigated many statistical regularities of language. Some of them have been investigated intensively, such as Zipf’s law for word frequencies (Fedorowicz, 1982; Ferrer-i-Cancho, & Gavald a, 2009; Font-Clos, Boleda, & Corral, 2013; Ferrer-i-Cancho, 2016a) or Zipf’s law of abbreviation (Strauss, Grzybek, & Altmann, 2006; Ferrer-i-Cancho et al., 2013). Some others, such as Zipf’s law of meaning distribution, have received less attention. In his pioneering research, Zipf (1945) found that more frequent words tend to have more meanings. The functional dependency between l, the number of meanings of a word, and f, the frequency of a word, has been approximated with (Ilgen & Karaoglan, 2007; Baayen & Moscoso del Prado Mart ın, 2005; Zipf, 1945) l/fd;(1) where dis a constant such that d1=2. Equation 1 defines Zipf’s meaning-frequency law. Equivalently, the meaningfrequency law can be defined as f/l1=d:(2) Zipf derived the meaning-frequency law assuming two laws, the popular Zipf’s law for word frequencies and the law of meaning distribution. On the one hand, Zipf’s law for word frequencies states that the relationship between the frequency of a word and its rank (the most frequent word has rank i51, the second most frequent word has rank i52 and so on) as f/i2a;(3) where a1 is a constant (Zipf, 1945, 1949). On the other hand, the law of meaning distribution (Zipf, 1945, 1949) states that l/i2c;(4) where c1=2. Notice that iis still the rank of a word according to its frequency. The constants a,c,anddcan be estimated applying some regression method as in Zipf’s pioneering research (Zipf, 1945, 1949). Sometimes, power-laws such as those described in Equations (1–4) are defined using asymptotic notation. For instance, random typing yields f5Hði2aÞ, that is, for sufficiently large i, one has (Conrad & Mitzenmacher, 2004) a1i2afa2i2a;(5) where a 1 and a 2 are constants such that a1a2. Equation 5 can be seen as a relaxation of Equation 3. Similarly, Heaps’ Received March 2, 2017; revised January 2, 2018; accepted February 8, 2018 V C2018 The Authors. Journal of the Association for Information Science and Technology published by Wiley Periodicals, Inc. on behalf of Association for Information Science and Technology Published online Month 0, 2018 in Wiley Online Library (wileyonlinelibrary.com). DOI: 10.1002/asi.24057 JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY, 00(00):00–00, 2018 This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited. law on the relationship between V, the number of types, as a function of T, the number of tokens, is defined as V5HðTbÞ with 0 <b<1 (Baeza-Yates & Navarro, 2000), a relaxed version of V/Tb(see Font-Clos & Corral, 2015, for a critical revision of the power law model for Heaps’ law). The meaning-frequency law (Equation 1) and the law of meaning distribution (Equation 4) predict the number of meanings of a word using different variables as predictors. The meaning-frequency law has been confirmed empirically in various languages: directly through Equation 1 in Dutch and English (Baayen & Moscoso del Prado Mart ın, 2005) or indirectly through Equation 4 and the assumption of Zipf’s law (Zipf, 1945; Ilgen & Karaoglan, 2007) in Turkish and English. Qualitatively, the meaning-frequency law defines a positive correlation between frequency and the number of meanings. Using a proxy of word meaning, the qualitative version of the law has been found in dolphin whistles (Ferrer-i-Cancho & McCowan, 2009) and in chimpanzee gestures (Hobaiter & Byrne, 2014). Thus, the law is a candidate for a universal property of communication. Zipf (1945) argued that Equation 1 with d51=2 follows from Equation 3 with a51 and Equation 4 with c51=2. Indeed, it has been proven that Equation 1 with d5c=afollows from Equations 1 and 4 (Ferrer-i-Cancho, 2016b). Here we consider alternative derivations of Equation 1 or relaxed versions of Equation 1 from the assumption of a biased random walk (Sinatra, G omez-Garde~ nes, Lambiotte, Nocosia, & Latora, 2011; G omez-Garde~ nes & Latora, 2008) over word-meaning associations. The remainder of the article is organized as follows. First, we will present the mathematical framework. Second, we will present a minimalist derivation of the meaning-frequency law (Equation 1) with d51=2 law that is based on just one assumption on the joint probability of a word and a meaning. Suppose a word sthat is connected to lmeanings and a meaning rthat is connected to xwords. Assuming that the joint probability of sand ris proportional to lif sand rare connected and zero otherwise, it suffices to obtain Equation 1 with d51=2. A problem of the argument is that the definition is somewhat arbitrary and theoretically superficial. Third, we will replace this simplistic assumption by a more fundamental assumption, namely, that the joint probability of sand ris proportional to lx if sand rare connected and zero otherwise. This assumption is a more elegant solution for two reasons: it corrects the arbitrariness of the assumption of the minimalist derivation, fits into standard network theory, and it can be embedded into a general theory of communication. From this deeper assumption we derive the meaning-frequency law following three major paths. The first path consists of assuming the principle of contrast (Clark, 1987) or the principle of no synonymy (Goldberg, 1995, p. 67), namely, x1 for all words, which leads exactly to Equation 1. The second path consists of assuming that meaning degrees are mean independent of word degrees, which leads to a mirror of the meaningfrequency law (Equation 2) E½pjl/l1=d;(6) where E½pjlis the expectation of p, the probability of a word, knowing that its degree is l.Noticethatpis linked with fas pf=L,whereLis the length of a text in tokens, that is, total number of tokens (the sum of all type frequencies; Moreno-S anchez, Font-Clos, & Corral, 2016). The third path makes no assumption to obtain a relaxed version of the meaning-frequency law, namely, the number of meanings is bounded above and below by two power-laws over f, that is b1fdlb2fd; where b 1 and b 2 are constants such that b1b2. The result can be summarized as l5HðfdÞ:(7) Put together, these three paths strongly suggest that languages are channeled to reproduce Zipf’s meaningfrequency law. Fourth, we will review a family of optimization models of communication that was put forward to investigate the origins of Zipf’s law for word frequencies (Ferrer-i-Cancho &D  ıaz-Guilera, 2007) but that has recently been used to shed light on patterns of vocabulary learning and the mapping of words into meanings (Ferrer-i-Cancho, 2016c). Interestingly, models from that family give Equation 1 with d51 (Ferrer-i-Cancho, 2016b). Crucially, however, the true exponent is d1=2 (Zipf, 1945; Ilgen & Karaoglan, 2007). The mismatch should not be surprising. Imagine that a speaker has to choose a word for a certain meaning. Those models assume that given a meaning, all the words with that meaning are equally likely (Ferrer-i-Cancho & D ıaz- Guilera, 2007). However, this simple assumption is not supported by psycholinguistic research (Snodgrass & Vanderwart, 1980). We will show how to modify their definition so that the words that are used for a certain meaning do not need to be equally likely and one can obtain Equation 1 with d51=2 or relaxed versions. Finally, we will discuss the results, highlighting the connection with biased random walks, and indicate directions for future research. A Mathematical Framework As in the family of models of communication above, we assume a repertoire of nwords, s 1 ,...,s i ,...s n and a repertoire of mmeanings, r 1 ,...,r i ,...,r m . Words and meanings are associated through an n3madjacency matrix A5faijg: a ij 51ifs i and r j are associated (a ij 50 otherwise). A defines the edges of an undirected bipartite network of word-meaning associations. The degree of the i-th word is li5X m j51 aij (8) 2 JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi while the degree of the j-th meaning is xj5X n i51 aij:(9) In human language, the relationship between sound and meaning has been argued to be arbitrary to a large extent (Saussure, 1916; Hockett, 1966; Pinker, 1999). That is, there is no intrinsic relationship between the word form and its meaning. For example the word “car” is nothing like an actual automobile. An obvious exception are onomatopoeias, which are relatively rare in language. However, despite the immense flexibility of the world’s languages, some soundmeaning associations are preferred by culturally, historically, and geographically diverse human groups (Blasi, Wichmann, Hammarstr€ om, Stadler, & Christiansen, 2016). The framework above is agnostic concerning the type of association between sound and meaning. By doing that, we are borrowing the abstract perspective of network theory, that is a priori neutral concerning the nature or the origins of the edges (Newman, 2010; Barth elemy, 2011). Our framework could be generalized to accommodate Peirce’s classic types of reference, that is, iconic, indexical, and symbolic (Deacon, 1997), or the state-of-the-art on the iconicity/systematicity distinction (Dingemanse, Blasi, Lupyan, Christiansen, & Monaghan, 2015). A crucial reason to remain neutral is that the distinctions above were not made when defining the laws of meaning that are the target of this article. The framework allows one to model lexical ambiguity: a lexically ambiguous word is a word such that its degree is greater than one. Although the model starts from a flat hierarchy of concepts (by default all concepts have the same degree of generality), a word with an abstract meaning could be approximated either as a word linked to a single abstract concept or as a word linked to the multiple specific meanings it covers (Ferrer-i-Cancho, 2016c). As for the latter approach, the word for vehicle would be linked to the meanings for car, bike, ship, airplane, etc. Suppose that pðsi;rjÞis the joint probability of the unordered pair formed by s i and r j .Bydefinition, X n i51X m j51 pðsi;rjÞ51:(10) The probability of s i is pðsiÞ5X m j51 pðsi;rjÞ(11) and the probability of r i is pðrjÞ5X n i51 pðsi;rjÞ:(12) Our model shares the assumptions of distributional semantics that the meaning of a word is represented as a vector of the weights of different concepts for that word (Lund & Burgess, 1996). In our framework, the meaning of the word s i is represented by the m-dimensional vector fpðsi;r1Þ;...;pðsi;rjÞ;...;pðsi;rmÞg The joint probabilities pðsi;rjÞfor all words and meanings defines a weighted matrix of the same size of A.Inthecoming sections, we will derive the meaning frequency-law defining pðsi;rjÞas a function of A. Put differently, we will derive the law from a weighted undirected bipartite graph that is built from the unweighted undirected graph defined by A. This organization in two graphs (one unweighted and the other weighted) instead of a single weighted graph is borrowed from successful models of communication (Ferrer-i-Cancho, 2016c) and allows one to apply the theory of random walks (Sinatra, G omez-Garde~ nes, Lambiotte, Nocosia, & Latora, 2011; G omez-Garde~ nes & Latora, 2008), as we will see later on. A Minimalist Derivation of the Law The law of meaning distribution can be derived by making just one rather simple assumption, that is pðsi;rjÞ/aijli;(13) Applying Equation 10, one obtains pðsi;rjÞ5caijli;(14) where cis a normalization constant defined as c5 1 X n i51X m j51 aijli 5 1 X n i51 liX m j51 aij 5 1 X n i51 l2 i : Notice that cis not a parameter and its value is determined by the definition of probability in Equation 10. Applying Equation 11 to Equation 14 gives pðsiÞ5cl2 i; Namely, Equation 1 with d51=2. Our derivation of the strong and relaxed version of the meaning-frequency law is simpler than that of Zipf’s in the sense that it requires assuming a smaller number of equations (we are assuming only Equation 13, while Zipf assumed Equations 3 and 4). However, the challenge of our approach is the justification of Equation 13. A Theoretical Derivation of the Law The definition of pðsi;rjÞin Equation 13 suffices as a model but not for the construction of a real theory of language. Equation 13 is simple but somewhat arbitrary: the degree of the word, l i , contributes raised to 1 but the degree of the meaning x j has no direct contribution, or one may say JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi 3 that it contributes raised to 0. Therefore, a less arbitrary equation would be pðsi;rjÞ/aijðlixjÞ/;(15) where /is a positive parameter (/0). Applying Equation 10 to Equation 15, one obtains pðsi;rjÞ5caijðlixjÞ/(16) with c51=M and M5X n i51X m j51 aijðlixjÞ/5X n i51 l/ iX m j51 aijx/ j:(17) Notice that /is the only parameter of the model given nand m. Applying Equation 11 to Equation 16, one obtains pðsiÞ5cl/ iX m j51 aijx/ j:(18) Equation 15 is theoretically appealing for various reasons. If pðsi;rjÞis regarded as the weight of the association between s i and r j , it defines the general form of the relationship between the weight of an edge and the product of the degrees of vertices at both ends that is found in real networks (Barrat, Barth elemy, Pastor-Satorras, & Vespignani, 2004). For this reason, a unipartite version of Equation 15 is assumed to study dynamics on networks (Baronchelli, Castellano, & Pastor-Satorras, 2011). When /50, it matches the definition of models about the origins of Zipf’s law for word frequencies (Ferrer-i-Cancho, 2005b), the variation of the exponent of the law (Ferrer-i-Cancho, 2005a, 2006) and vocabulary learning (Ferrer-i-Cancho, 2016c). When /51, it defines an approximation to the stationary probability of observing a transition involving s i and r j in a random walk on a network that is biased to maximize the entropy rate of the walks (Appendix A1), thus suggesting that the meaningfrequency law could be a manifestation of a particular random walk process on semantic memory. Two equivalent linguistic principles, the principle of contrast (Clark, 1987) and the principle of no synonymy (Goldberg, 1995, p. 67) can be implemented in our model as xj2f0;1g. From an algebraic standpoint, the condition xj 2f0;1gis equivalent to orthogonality of the word vectors of the matrix A.IfAiindicates the row vector of Afor the ith word, Aiand Akare orthogonal if and only if AiAk50, where the dot indicates the scalar product of two vectors. To simplify matters, we assume that there is no row vector of Athat equals ~ 0, a vector that has 0 in all components. So far, we have used l i and x j to refer, respectively, to the degree of the i-th word and the j-th meaning. We define le iand xe ias the degree of the word and the degree of the meaning of the i-th edge. le iand xe iare components of the vectors ~ le iand ~ xe i, respectively. We have ~ le i~ xe i>0becausele i;xe i1 by definition. A deeper insight can be obtained with the concept of remaining degree, the degree at one end of the edge after subtracting the unit contribution of the edge (Newman, 2002). The vectors of remaining degrees are then ~ li0e5~ le i2 ~ 1 ~ xi0e5~ xe i2 ~ 1: The condition xj2f0;1gis equivalent to ~ xi0e5 ~ 0. xj2f0; 1gleads to ~ li0e~ xi0e50 but trivially for being ~ xi0enull. The assumption /51andxj2f0;1g(orthogonality of row vectors of A), transforms Equation 18 into Equation 13 because a ij 50andxj50 are equivalent when x j does not exceed 1. In general, Equation 18 combined with the principle of contrast gives pðsiÞ5cl/ iX m j51 aij 5cl/11 i and finally Equation 1 with d5 1 /11: When /51, we get d51=2 again. Interestingly, the principle of contrast follows from the principle of mutual information maximization, a more fundamental principle that allows one to predict vocabulary learning in children and that can be combined with the principle of entropy minimization to predict Zipf’s law for word frequencies (Ferrer-i-Cancho, 2016c). With Equation 15, we follow Bunge (2013, pp. 32–33) preventing scientific knowledge from becoming “an aggregation of disconnected information” and aspiring to build a “system of ideas that are logically connected among themselves.” It is possible to obtain a relaxed meaning frequency-law under more general conditions. In particular, we would like to get rid of the heavy constraint that meaning degrees cannot exceed 1. Suppose that dis a constant such that 0 <dn. Some obvious but not very general conditions are xj2f0;dg for all jor xj5dfor all j. It is easy to see that they lead again to Equation 13 when /51. A more general condition can be defined as follows. First, we define E½x/jlas the conditional expectation of x/given lfor an edge. Here land xare the degrees at both ends of an edge. Then suppose that Ais given and that x/is mean independent of l, namely, E½x/jl 5E½x/for each value of l(Kolmogorov, 1956; Poirier, 1995), then the expectation of pðsiÞ(as defined in Equation 18) knowing l i is E½pðsiÞjli5Ecl/ iX m j51 aijx/ j li "# 4 JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi 5cl/ iEX m j51 aijx/ j li "# 5cl/ iX m j51 aijEx/ j li  5cl/ iX m j51 aijEx/ j hi 5cE½xjl/11 i; which can be seen as a regression model (Ritz & Streibig, 2008) for the meaning-frequency law (Equation 1) with word degree as predictor. Notice that mean independence is a more general condition than mutual or statistical independence but a particular case of uncorrelation (Ferrer-i-Can- cho, Hern andez-Fern andez, Baixeries, Debowski, & Mac ˇutek, 2014). So far, we have seen ways of obtaining the meaningfrequency law from Equation 15 making further assumptions. It is possible to obtain a relaxed version of the meaning-frequency law making no additional assumption (except Equation 15 or the biased random walk that justifies it). Equation 18 can be expressed as pðsiÞ5l/ iX m j51 aijTj(19) with Tj5cx/ j: Assuming that Tmin TjTmax; Equation 19 leads to Tminl/11 ipðsiÞTmaxl/11 i(20) or equivalently 1 Tmin pðsiÞ1 /11li1 Tmax pðsiÞ1 /11: Recalling pf=L, these results can be summarized using asymptotic notation as f5Hðl/11Þor l5Hðf1=ð/11ÞÞ.The power of the bounds above depends on the gap between T min and T max . The gap can be measured with the ratio Tmax Tmin 5x/ max x/ min ; where x min and x max are the minimum and the maximum meaning degree, respectively. The principle of mutual information maximization between words and meanings, a general principle of communication (Ferrer-i-Cancho, 2016c), puts pressure for concordance with the meaningfrequency law. To see it, we consider two cases: nmand mn.Whennm, its maximization predicts xj1 (Appendix A2). As unlinked meanings are irrelevant (they do not belong to the support set), we have xmin51. As pressure for mutual information maximization increases, x max tends to 1 and thus Tmax=Tmin tends to 1. Put differently, the gap between the upper and the lower bound in Equation 20 reduces as pressure for mutual information maximization increases. When nm, mutual information maximization predicts that xj5d,wheredis an integer such that d2½1;bn=mc (Appendix A2). We have seen above that one obtains the meaning-frequency law (Equation 1) immediatelyfromEquation15whenx j is constant. We conclude that the chance of observing the meaning-frequency law increases as pressure for mutual information maximization increases. A Family of Optimization Models of Communication Here we revisit a family of optimization models of communication (Ferrer-i-Cancho & D ıaz-Guilera, 2007) in the light of the results of the previous sections. These models share the assumption that the probability that a word s i is employed to refer to meaning r j is proportional to a ij ,thatis pðsijrjÞ/aij;(21) Applying X n i51 pðsijrjÞ51 to Equation 21, we obtain pðsijrjÞ5aij xj :(22) We adopt the convention pðsijrjÞ50whenxj50. Equation 22 defines the probability of transition of a standard (unbiased) random walk to a word (Noh & Rieger, 2004), that is, given a meaning, all related words are equally likely. This is unrealistic in light of picture-naming norms (Snodgrass & Vanderwart, 1980; Du~ nabeitia et al., 2017). Consider the picture-naming norms compiled by Snodgrass and Vanderwart (1980), who simply asked participants to name 260 black-and-white line drawings of common objects. For some objects (for example, balloon, banana, sock, star) there was 100% agreement among the participants for the word used to name the pictured object. However, for other objects there was considerable variability in the word used to name the pictured object. Important for the present argument, the other words that were used in such cases were not selected with equal likelihood. For example, the picture of a wineglass had 50% agreement, with the JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi 5 word glass (36% of the responses) and the word goblet (14% of the responses) also being used to name the object, showing that all the words that could be used for a given meaning are not equally likely. Although subjects tend to provide more specific responses when the concept is presented in textual form with respect to a visual form presentation (Tversky & Hemenway, 1983), we used the visual case simply to challenge the assumption of an unbiased random walk in general and justify a more realistic approach. In contrast to Equation 22, the fundamental assumption in Equation 15 leads to pðsijrjÞ5aijl/ i X k akjl/ k ;(23) Namely, the transition probabilities of a biased random walk when />0 (Sinatra, G omez-Garde~ nes, Lambiotte, Nocosia, & Latora, 2011; G omez-Garde~ nes & Latora, 2008). To see it, notice that the combination of Equation 12 and 16 produces pðrjÞ5X n i51 pðsi;rjÞ5cx/ jX n i51 aijl/ i:(24) Recalling the definition of conditional probability pðsijrjÞ5pðsi;rjÞ pðrjÞ and applying Equation 16 again, one obtains Equation 23. Recalling the definition of x j in Equation 9, it is easy to realize that Equation 22 is a particular case of Equation 23 with /50. While the family of models above stems from a concrete definition of a conditional probability, that is, pðsijrjÞin Equation 22, the general model that we have presented in this article is specified by a definition of the joint probability, that is, pðsi;rjÞin Equation 15. Models within that family are generated through pðsi;rjÞ5pðsijrjÞpðrjÞ;(25) assuming an unbiased random walk from a meaning to a word (Equation 22) and making different assumptions on pðrjÞ. If one assumes that all meanings are equally likely (pðrjÞ51=mwith xj1) one obtains the first model (Ferrer-i-Cancho & Sol e, 2003). If one assumes that the probability of a meaning is proportional to its degree (pðrjÞ/xj) one obtains the second model (Ferrer-i-Cancho, 2005b). While in the second model pðrjjsiÞdefines an unbiased random walk from s i to r j (all r j ’s connected to s i are equally likely), this is not necessarily the case for the first model (Ferrer-i-Cancho & D ıaz-Guilera, 2007). Therefore, the second model defines a pure unbiased random walk while the first model is unbiased from meaning to words but biased from words to meanings. Now we will introduce a generalized version of the family of models above consisting of replacing Equation 22 by Equation 23 and generating the corresponding variants of the first and the second model applying the same procedure as in the original family, namely, via Equation 25. Notice that Equation 23 defines the probability of reaching sifrom r j in a biased random walk when />0. Concerning the first model, suppose that the probabilities of the meanings are given a priori (they are independent from the Amatrix), for example, all meanings are equally likely. Then it is easy to show that the model yields a relaxed version of the meaning-frequency law, namely, li5HðpðsiÞdÞ, the number of meanings is bounded above and below by two power-laws (Appendix A3) b1pðsiÞdlib2pðsiÞd;(26) where b 1 and b 2 are constants (b1b2)andd51=ð/11Þ. Equation 26 defines nontrivial bounds when d6¼ 1 (Appendix A3). The case d51 matches an optimization model of Zipf’s law for word frequencies (Ferrer-i-Cancho, 2005b, 2016b). To generate a variant of the second model, recall that Equation 23 comes from Equation 15. Equations 12 and 16 produce Equation 24. This variant of the second model derives all probability definitions from Equation 15. We have shown above that this variant is able to generate the meaning-frequency law. Discussion We have seen that it is possible to obtain the meaningfrequency law (Equations 1 and 2) from Equation 15 making certain assumptions. We have also seen that a relaxed version of the law (Equation 7) can be obtained from Equation 15 without making any further assumption. Our findings suggest that word probabilities are channeled somehow to manifest the meaning-frequency law. We have seen that the principle of mutual information maximization contributes to the emergence of the law. Our derivation is theoretically appealing for various reasons. First, it is more parsimonious than Zipf’s concerning the number of equations that are assumed (we only need Equation 15 while Zipf involved Equations 3 and 4). Second, it can help a family of optimization models of language to reproduce the meaningfrequency law. Therefore, a crucial assumption is Equation 16, that we have justified as the outcome of a random walk that is biased to maximize the entropy rate of the paths (Appendix A1). A random walk is the correlate in network theory of the concept of mental exploration (navigation without a target or nonstrategic search) in cognitive science and related fields (Baronchelli, Ferrer-i-Cancho, Pastor-Satorras, Chatter, & Christiansen, 2013). Semantic memory processes can be usefully theorized as searches over a network (Thompson & Kello, 2014; Abbott, Austerweil, & Griffiths, 2015) or some semantic space (Smith, Huber, & Vul, 2013). These 6 JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi approaches support the hypothesis of a Markov chain process for memory search (Bourgin, Abbott, Griffiths, & Vul, 2014), provide a deeper understanding of creativity (Kenett & Austerweil, 2016), and help to develop efficient navigation strategies (Capit an et al., 2012). A random walk in a unipartite word network of word– word associations has been argued to underlie Zipf’s law for word frequencies (Allegrini, Gricolini, & Palatella, 2004). Here we contribute with a new hypothesis linking random walks with a linguistic law: that the meaning-frequency law would be an epiphenomenon of a biased random walk over a bipartite network of word-meaning associations in the process of mental exploration. The bias consists of exploiting local information, namely, the degrees of first neighbors (Sinatra et al., 2011). Transitions to nodes with a higher degree are preferred. Our model shows that it is possible to approximate the optimal solution to a problem (maximizing the entropy rate of the paths) following an apparently nonstrategic search (Hills, Jones, & Todd, 2012; Abbott et al., 2015). The probability of a word in Equation 18 defines the probability that a random walker visits the word in the long run. This probability is what the PageRank algorithm estimates in the context of a standard (nonbiased) random walk (Page, Brin, Motwani, & Winograd, 1998). The assumption of a random walk with the particular bias above could help to improve random walk/PageRank methods to predict the prominence in memory of a word (Griffiths, Steyvers, & Firl, 2007) or the importance of a tag (J€ aschke, Marinho, Hotho, Schmidt-Thieme, & Stumme, 2007). A virtue of our biased random walk is that it predicts an uneven conditional probability of a word given a meaning (Equation 23) as happens in real language (Snodgrass & Vanderwart, 1980). A standard (uniform) random walk cannot explain this fact and for that reason the family of optimization models of language revisited above fails to reproduce the meaningfrequency law with d51=2. Although biased random walks have already been used to solve information retrieval problems (see Duarte Torres, Hiemstra, Weber, & Pavel, 2014, and references therein), a bias based on the degree of neighbors has not been considered as far as we know. We hope that our results stimulate further research on linguistics laws and biased random walks in the information sciences. Specifically, we hope that our article becomes the fuel of future empirical research. Acknowledgments We thank R. Pastor-Satorras and Massimo Stella for helpful comments and insights. We also thank S. Semple, M. Gentili, and E. Bastrakova for helpful discussions. This research was supported by the grant APCOM (TIN2014– 57226-P) from MINECO (Ministerio de Econom ıa y Competitividad), the grant 2014SGR 890 (MACDA) from AGAUR (Generalitat de Catalunya) and partially by funds from the University of Kansas. Appendix A1: Random Walks We will show that Equation 15 defines the probability of observing a transition between s i and r j in any direction in a biased random walk. We will proceed in two steps. First, we will summarize some general results on biased random walks on unipartite networks and then we will adapt them to bipartite networks. Suppose a unipartite network of nnodes that is defined by an n3nadjacency matrix B5fbijgsuch that b ij 51 if the i-th and the j-th node are connected and b ij 50 otherwise. Let k i be the degree of the i-th node, namely, ki5X n j51 bij: Suppose a random walk over the vertices of a network where pðjjiÞis the probability of jumping from ito j.A first order approximation to the pðjjiÞthat maximizes the entropy rate is (Sinatra et al., 2011) pðjjiÞ5bijkj X n l51 bilkl :(27) We choose a generalization (G omez-Garde~ nes & Latora, 2008) pðjjiÞ5bijk/ j X n l51 bilk/ l ;(28) that gives Equation 27 with /51. The stationary probability of visiting the i-th vertex in the biased random walk defined by Equation 28 is (G omez-Garde~ nes & Latora, 2008) pðiÞ5k/ ici T;(29) where ci5X n j51 bijk/ j(30) and T5X n i51 cik/ i:(31) Now we adapt the results above to a bipartite graph of word-meaning associations. As the graph is bipartite, the random walker will be alternating between words and meanings. The probability that the vertex visited is a JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi 7 word is 1/2 (the same probability for a meaning). Suppose that there are nwords and mmeanings. Recall that the bipartite network of word-meaning associations is defined by an n3madjacency matrix A5faijgsuch that a ij 51 if the i-th word and the j-th meaning are connected and a ij 51 otherwise. l i is the degree of the i-th word is (Equation 8) whereas x j is the degree of the j-th meaning (Equation 9). The probability of jumping from r j to s i becomes (recall Equation 28) pvðsijrjÞ5aijl/ i X n l51 aljl/ l : The probability of jumping from s i to r j is pvðrjjsiÞ5aijx/ j X m l51 ailx/ l :(32) The stationary probability of visiting the word s i becomes (recall Equations 29 and 30) pvðsiÞ5 l/ iX m j51 aijx/ j Mv ;(33) where M v corresponds to Tin Equation 29. Adapting Equations 31 and 30, one obtains Mv5X n i51 l/ iX m j51 aijx/ j1X m j51 x/ jX n i51 aijl/ i 52M; where Mis defined as in Equation 17. Applying Equation 33, it is easy to see that X n i51 pvðsiÞ5 1 2MX n i51 l/ iX m j51 aijx/ j 5 1 2: as expected. The combination of Equations 32 and 33 allows one to derive the probability of observing the transition from s i to r j as pvðsi!rjÞ5pvðrjjsiÞpvðsiÞ 5cvaijðlixjÞ/; where cv51=ð2MÞ. Similarly, the probability of observing the transition from r j to s i is pvðsi rjÞ5pvðsijrjÞpvðrjÞ 5cvaijðlixjÞ/: Therefore, the stationary probability of observing a transition between s i and r j in any direction (from s i to r j or from r j to s i )is pðsi;rjÞ5pvðsi!rjÞ1pvðsi rjÞ 52cvaijðlixjÞ/: 5caijðlixjÞ/: with c51=M, as we wanted to show. Finally, we will link pðsiÞ, the probability of a word that is used in the main text to derive the meaning-frequency law, with pvðsiÞ. Notice that pðsiÞ5pvðsijSÞ, the latter being the probability of visiting vertex s i knowing that it belongs to the partition S, the partition of words. Since the graph is bipartite, pvðSÞ, the probability that the random walk is visiting a vertex of partition S, is 1/2. The joint probability of visiting vertex s i and that the vertex belongs to Sis pvðsi;SÞ5pvðSjsiÞpvðsiÞ 5pvðsiÞ: Therefore, pðsiÞ5pvðsijSÞ 5pvðsi;SÞ pvðSÞ 52pvðsiÞ: Then pðsiÞis the stationary probability of visiting s i in a biased random walk knowing that the vertex is in S. Appendix A2: Mutual Information Maximization Suppose that I(S,R) is the mutual information between words (S) and meanings (R), that can be defined as IðS;RÞ5HðSÞ2HðSjRÞ;(34) where H(S) is the entropy of words and HðSjRÞis the conditional entropy of words given meanings. For the case /50, the configurations that maximize I(S,R) when nmare defined by two conditions (Ferrer-i-Cancho, 2016c) 1. li5dwith d2½1;bm=nc for i51;2;...;n. 2. xj2f0;1gfor j51;2;...;m. When nm, those configurations are the symmetric, that is (Ferrer-i-Cancho, 2016c) 1. xj5dwith d2½1;bn=mc for j51;2;...;m. 2. li2f0;1gfor i51;2;...;n. 8 JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi Here we will show that the configurations that maximize I(S,R) are the same as in the case /50when/is a positive and finite real number (/0). By symmetry, it suffices to show it for the case nm. We will proceed in three steps. First, deriving the configurations minimizing HðSjRÞ.Second, showing that the configurations above yield maximum I(S,R). Third, showing that they are the only configurations. Step 1: Recall that HðSjRÞ5E½HðSjrjÞ 5X m j51 pðrjÞHðSjrjÞ where HðSjrjÞis the conditional entropy of words given the meaning r j . Equation 24 implies that pðrjÞ 6¼ 0is equivalent to wj>0 and then HðSjRÞ5X m j51 pðrjÞ6¼0 pðrjÞHðSjrjÞ 5X m j51 wj>0 pðrjÞHðSjrjÞ: Knowing that HðSjrjÞ52X n i51 pðsijrjÞlog pðsijrjÞ it is easy to see that HðSjrjÞ50 when pðsijrjÞ2f0;1gfor i51;2;...;n: 0log 050 by continuity since xlog x!0as x!0 (Cover & Thomas, 2006, p. 14) and obviously 1log 150. Equation 23 implies that pðsijrjÞ51 is equivalent to s i being the only neighbor of r j , that is, xj51. Therefore, HðSjRÞ50 implies xj1 for j51;2;...;m. Step 2: Notice that the second condition of the case n mabove implies HðSjRÞ50 (recall Step 1). The second condition transforms Equation 17 into M5X n i51 l/ iX m j51 aij5X n i51 l/11 i and Equation 18 into pðsiÞ5cl/ iX m j51 aij5cl/11 i:(35) Adding the first condition, one obtains M5X n i51 d/115nd/11 pðsiÞ5cl/11 i5 1 Md/115 1 n: and then HðSÞ5log n(as all words are equally likely). Thus, H(S) is taking its maximum possible value, whereas HðSjRÞ is taking its minimum value. As IðS;RÞ5HðSÞ2HðSjRÞ,it follows that I(S,R) is maximum. Step 3: Notice that •If the second condition fails, then HðSjRÞ>0 and thus IðS;RÞ<log neven if H(S) is maximum because of Equation 34. Thus, the second condition is required to maximize I(S,R). •If the first condition fails (while the second condition holds), then words are not equally likely as the probability of a word is proportional to a power of its degree (Equation 35). Then one has that HðSÞ<log nand it follows that I(S,R) is not maximum because IðS;RÞHðSÞ. Appendix A3: New Models Combining Equations 11 and 23, one obtains pðsiÞ5X m j51 pðsi;rjÞ5X m j51 pðsijrjÞpðrjÞ5l/ iX m j51 aijTj(36) with Tj5pðrjÞ X n i51 aijl/ i : Suppose that Tmin TjTmax when xj>0. Equation 36 leads to l/ iX m j51 aijTmin pðsiÞl/ iX m j51 aijTmax and finally Tminl/11 ipðsiÞTmaxl/11 i(37) recalling the definition of l i in Equation 8. Equivalently, T2d maxpðsiÞdliT2d minpðsiÞd;(38) with d5 1 /11; Namely, a relaxed version of the meaning-frequency law when /51. Notice that Equations 37 and 38 define nontrivial bounds in the sense that they are not expected from bounds on join-probability alone. If the range of variation of pðsi;rjÞsatisfies pmin pðsi;rjÞpmax JOURNAL OF THE ASSOCIATION FOR INFORMATION SCIENCE AND TECHNOLOGY—Month 2018 DOI: 10.1002/asi 9