Emergence of order in random languages

  • 2019-06-28 08:38:11
  • E. DeGiuli
  • 0


We consider languages generated by weighted context-free grammars. It isshown that the behaviour of large texts is controlled by saddle-point equationsfor an appropriate generating function. We then consider ensembles of grammars,in particular the Random Language Model of E. DeGiuli, Phys. Rev. Lett., 122,128301, 2019. This model is solved in the replica-symmetric ansatz, which isvalid in the high-temperature, disordered phase. It is shown that in the phasein which languages carry information, the replica symmetry must be broken.


Quick Read (beta)

Emergence of order in random languages

Eric De Giuli Institut de Physique Théorique Philippe Meyer, École Normale Supérieure,
PSL University, Sorbonne Universités, CNRS, 75005 Paris, France
[email protected]

We consider languages generated by weighted context-free grammars. It is shown that the behavior of large texts is controlled by saddle-point equations for an appropriate generating function. We then consider ensembles of grammars, in particular the Random Language Model of [1]. This model is solved in the replica-symmetric ansatz, which is valid in the high-temperature, disordered phase. It is shown that in the phase in which languages carry information, the replica symmetry must be broken.

: \jpa

Keywords: context-free grammar, language, replicas

Many complex systems have a generative, or linguistic, aspect. For example, protein structure is written in sequences of amino acids, a language of 20 different symbols. A large body of previous work has investigated the social aspect of linguistic systems, namely that different agents must find consensus regarding the meaning of symbols [2, 3, 4]. A complementary but necessary aspect of any linguistic system concerns the hidden structure within the sequences themselves, independent of communication. The most basic structural property is syntax: the rules that govern how symbols can be combined to create richer structures and thus carry information. In computer science and linguistics, generative grammar has proved to be a valuable formalism to describe syntax, in a generalized sense [5, 6, 7]. A generative grammar consists of an alphabet of hidden symbols, an alphabet of observable symbols, and a set of rules, which allow certain combinations of symbols to be replaced by others. From an initial start symbol S, one progressively applies the rules until only observable symbols remain; any sentence produced this way is said to be grammatical, and the set of all such sentences is called the language of the grammar. The sequence of rule applications is called a derivation. The Chomsky hierarchy distinguishes grammars based on the complexity of the grammatical rules. In this work, we restrict our attention to context-free grammars (CFGs), for which derivations are trees (Figure 1).

There are many theoretical results on the capabilities of CFGs [7]. However, little is known about the statistical properties of large, typical grammars. Recently, there has been increasing interest in approaching the properties of syntax from the point of view of statistical [8, 1] and quantum [9, 10, 11] physics. In [1], a simple model of random languages was proposed, using weighted context-free grammars. (We refer the reader to this work for all necessary details about generative grammars). With numerical simulations it was shown that as a ‘temperature’ ϵd is lowered, the model has a transition from a ‘disordered’ phase in which the grammar just produces noise, to an ‘ordered’ phase in which the grammar produces sequences with a nontrivial structure. This transition is characterized by emergence of order in the hidden structure, as measured by an order parameter Q2, defined below. As the temperature is lowered through ϵ*, Q2 rapidly increases. With a simple scaling argument, the location of this transition was understood as the place where energetic fluctuations begin to be comparable to entropy. However, detailed information on the transition was not obtained in [1]. In this work we use the replica method, as well as diagrammatic methods, to study random languages. We will solve the Random Language Model of [1] in the replica-symmetric phase, and show that it quantitatively captures the behavior of Q2, as shown in Figure 2. We will see that the replica symmetry must be broken in the ordered phase.

Figure 1: Illustrative derivation trees for (a) simple English sentence, and (b) RNA secondary structure (after [12]). The latter is a derivation of the sequence ‘gacuaagcugaguc’ and shows its folded structure. Terminal symbols are encircled.
Figure 2: Order parameter Q2 on logarithmic axes. Solid lines show numerical data from random grammars with N as indicated and 105. The plateau at large ϵ~d is a finite- effect; empirically it scales as Q2N4/. The function q(ϵ~d)=(e1/(2ϵ~d)-1)(N2-1)/N4 is the theoretical prediction, Eq.45.

1 Partition functions

A CFG in Chomsky Normal form is defined by two types of rules: abc, where one hidden symbol becomes two hidden symbols, and aB, where a hidden symbol becomes an observable symbol. In a weighted CFG (WCFG), we assign weights Mabc and OaB, respectively, to these rules. With these weights we build a weight for an entire derivation tree, 𝒯, as follows. We write σ for the hidden variables, and o for the observables. These are indexed by their positions on the tree. We write Ω𝒯 for the set of internal factors, i.e. factors of the form abc, and Ω𝒯 for the boundary factors, i.e. those associated to aB rules. The number of boundary factors is written 𝒯, which is also the number of leaves. Since derivations are trees, the number of internal factors is 𝒯-1. Write 𝒢 for the objects M and O, which specify the grammar. A table of commonly appearing symbols is shown in Table 1.

Symbol Definition Linguistic Interpretation

alphabet of hidden symbols

(non-terminal symbols)

abstract categories: noun,

verb, noun phrase, …

S start symbol ‘sentence’
A,B, alphabet of observable symbols words: ‘the’, ‘bear’, ‘walked’,
(terminal symbols)
Mabc weight for rule abc grammatical weight
OaB weight for rule aB part-of-speech weight
σi hidden symbol on site i
oi observable symbol on site i
πabc # of occurrences of rule abc
ρaB # of occurrences of rule aB
N # of hidden symbols # of abstract categories
T # of observable symbols # of words in lexicon
m # of sentences
# number of leaves total number of words
0 -m
La downward msg of left-child
La upward msg of left-child
Ra downward msg of right-child
Ra upward msg of right-child
Ha La+Ra head message
η,ζ,ξ Lagrange multipliers to control
# of branches, roots, leaves
ϵd deep temperature inverse variance of M
ϵs surface temperature inverse variance of O
ϵ~d ϵd/N3
ϵ~s ϵs/(NT)
Table 1: Table of symbols. ‘msg’ = message. First block: basic symbols; second block: variables in diagrammatic representation; third block: variables in grammar ensemble.

Consider a derivation tree, such as that depicted in Figure 1a. In a weighted context-free grammar, a tree 𝒯 with hidden variables σi and observables ot has a weight

W({σi,ot}|𝒯,𝒢)=αΩ𝒯Mσα1σα2σα3αΩ𝒯Oσα1oα2, (1)

where each α=(α1,α2,α3) is a factor in the order σα1σα2σα3. This defines a conditional probability measure on configurations

({σi,ot}|𝒯,𝒢)=W({σi,ot}|𝒯,𝒢)Z(𝒯,𝒢) (2)


Z(𝒯,𝒢)={σi,ot}W({σi,ot}|𝒯,𝒢) (3)

Eq.(2) specifies the probability of a derivation, given the tree. However, the topology of the tree is itself dynamical. We will consider that trees are chosen as a Bernoulli process: beginning from the root, each hidden variable either becomes an observable, with probability p, or branches into two hidden variables, with probability 1-p. This implies that (𝒯|𝒢)=Wtree(𝒯)/Ztree with Wtree(𝒯)=p|Ω𝒯|(1-p)|Ω𝒯|. The ‘emission probability’ p controls the size of trees 11 1 Ztree=2p/(1+|2p-1|)=1 for p>1/2.. The tree-averaged partition function is then

(𝒢;)=𝒯,(𝒯)=(𝒯|𝒢)Z(𝒯,𝒢) (4)

as a function of the number of leaves , and the partition function for m sentences of total length is

(𝒢;m,)={i},i=1mi=i(𝒢;i) (5)

We have i|Ω𝒯i|=i=, and i|Ω𝒯i|=(2i-1)=2-m, so that treei(𝒯i|𝒢)=p(1-p)2-mZtree-m just gives a trivial factor. For now we suppress dependence on m and . Note that (𝒢;m,) is the weight for the grand canonical partition function m,0(𝒢;m,); we will, however, work at fixed m and .

2 Energy, Entropy, and Order Parameters

It is convenient to add some auxiliary parameters in order to extract additional observables. First, we note that (1) can be written as

W({σi,ot}|𝒯,𝒢)=a,b,cMabcπabca,BOaBρaB (6)

where πabc(σ) is the usage frequency of rule abc and ρaB(σ,o) is the usage frequency of aB. Adding external fields habc and kaB let us define the energy of a configuration as

E=-a,b,cπabc[habc+logMabc]-a,BρaB[kaB+logOaB] (7)

Then we can generalize (3) to

Zh,k(𝒯,𝒢)={σi,ot}e-βE (8)

where we added a bias β. The original ensemble is recovered for β=1 and h=k=0. We see that the average energy is

E=-logZβ (9)

and it is natural to define the entropy of the grammar as S=βE+logZ.

In [1] it was argued that a natural order parameter for WCFGs is one that measures the extent to which rules are applied uniformly: if all rules abc and aB have the same weight, the grammar carries no information, and sentences will be indistinguishable from noise. To measure order in the deep grammar, define first

Qabc(𝒢)=δσα1,a(N2δσα2,bδσα3,c-1)=N20πabc-10b,cπabc, (10)

averaged over all interior vertices α, and averaged over derivations. The normalization 0=-m for . A spin-glass order parameter specific to deep structure is

Q2a,b,cQabc2¯=N5(N2-1)02(q0-q1) (11)


q0=πabc2¯,q1=πabcπabc¯, (12)

with bb,cc. Here we used the fact that when h=0,k=0, the permutation symmetry is restored upon disorder averaging. We see that

πabc=1βlogZhabc (13)

so q0 and q1 can be obtained from derivatives of logZ¯ with respect to the field.

3 Diagrammatic formulation

We expect that universal properties of weighted context-free languages are contained in the behavior of log¯ when becomes large, where ¯ is an average over grammars. In order to compute this object, we find it convenient to move to an alternative, particle, representation. In particular, we seek a model whose diagrammatic expansion gives the derivation trees we seek to count, with the appropriate weights. This technique has been widely used in the study of 2D gravity [13], and facilitated Kazakov’s solution of the Ising model on random surfaces [14, 15]. Later, it was shown in a simpler setting that this technique could be used to easily obtain results for spin models on random graphs [16, 17].

Figure 3: Feynman rules for weighted context-free grammars. Elements of Feynman diagram expansion (top row) with weights (middle row). (a-b) M-interaction, (c-d) Root source, (e-f) O source, (g-h): Nonzero propagators. Labels a,a,b,c are colour indices, {1,,N}. All propagators are diagonal in colour.

We begin with a simplified model. Consider the formal integral

W=|G|-N/2DUe-12i,jUiGij-1UjeξiUi+ηi,j,kUiUjUkMijk, (14)

where the measure is normalized such that |G|-N/2DUexp(-12i,jUiGij-1Uj)=1. Strictly speaking, the integral is only defined by its perturbative expansion in η; convergence requires that the real part of G-1 be positive-definite. This expansion generates Feynman diagrams with cubic vertices. Each vertex gets a factor ηMijk, and the expansion with respect to ξ generates sources. By Wick’s theorem, each edge gets a factor Gij, the propagator. The coefficient in this expansion of ξmηk thus counts all such diagrams, possibly disconnected, with k vertices and m sources, times an inverse symmetry factor [18] 22 2 Such factors appear when diagrams, including all their colour indices, have nontrivial symmetries, like reflections. In the disordered case where Mabc depends on all indices, these symmetry factors will not play a role since typical connected graphs will have no symmetries..

This is a skeleton of what we need to count derivation trees, but there are several elements missing: first, W includes all graphs with cubic vertices, not only trees. Second, even if we could restrict the sum to trees, there is nothing in W to distinguish leaves from roots, or to distinguish the left and right branches from a given hidden node.

Figure 4: Feynman diagram corresponding to derivation tree in Figure 1a. Alphabet of hidden symbols is χd=(S,NP,VP,Det,N,V,P,PP) and alphabet of surface symbols is χs=(the,bear,walked,into,cave). Vertices are represented by with heads at the tip. The diagram has a weight 2hζξ6η5g11M123M2452M368M872O412O52O63O74O55.

One solution to these problems is to use matrices as the integration variables, because their diagrammatic expansion can be arranged to give planar diagrams in an appropriate large N limit [19, 20]. However, for our problem this is overkill. Instead, we will consider a theory of complex scalar fields with colour indices, equivalent to a complex matrix model with matrices of size 1x1. We will have two scalar fields La and Ra, with colour indices a=1N. Consider

𝔽(𝒢)=DLDRe-1ga[LaLa+RaRa]eI (15)

where denotes complex conjugate and

I=ζh(L1+R1)+ξaOa(La+Ra)+ηa,b,cMabc(La+Ra)LbRc. (16)

with Oa=BOaB. The measure DL=adRe[La]dIm[La]/(πg) is normalized such that DLe-1gaLaLa=1, and similarly for R.

The propagator is diagonal in the colour indices a=1N and for each a is such that LaLa=g; that is, the Feynman rules are as shown in Figure 3. The diagram corresponding to Figure 1a is shown in Figure 4. We claim that, apart from accidental symmetry factors,

(𝒢;m,)=m!dζζ1+mdξξ1+dηη1+-m𝔽(𝒢), (17)

where =/(2πi). The proof is as follows.

The perturbative expansion with respect to η generates cubic vertices with distinguished heads and L and R ends; the vertices can be placed on the plane such that that their heads point up. The expansion and contour integral for ξ generate sources of L and R, which are the leaves. The expansion and contour integral for ζ generate m sources of L1 and R1, which are the roots. An La can only be connected to a La, and a Ra can only be connected to a Ra. We can orient all edges from LaLa and RaRa, and similarly for the half-edges in the cubic vertices, flowing from head to L and R branches. Then, from each root, we can define paths by following arrows; any path we take will go through some number of cubic vertices and end in a leaf. Therefore there are m connected components, one for each root. Considered as a graph, we can count the number of edges as follows: each source generates half an edge, and each cubic vertex generates 3/2 edges. The total number of edges is 12(m+3(-m)+)=2-m. The difference between the number of vertices and the number of edges is (m++-m)-(2-m)=m, which is the number of connected components. Therefore the graph is a forest.

We thus generate a forest of m planar, rooted, trees, with leaves in total. The weight of each diagram is

hmg2-ma,b,cMabcπabcaBOaBρaB (18)

where πabc is the usage frequency of rule abc and ρaB is the usage frequency of aB. This expansion counts diagrams with a degeneracy of 2m since each tree root can be either an L or an R. In the expansion, the different connected components are not ordered. We would like to distinguish forests by the order of the trees, so we multiply the result by m!. Choosing g and h such that

(2h)mg2-m=p(1-p)2-mZtree-m (19)

for all and m we have our result.

The virtue of working with (17) is that when ,m/=α= constant, the leading behavior can be extracted by a saddle-point analysis [21] 33 3 This can be seen explicitly by considering the rescaling L=1/2L,R=1/2R,η=-1/2η,ξ=1/2ξ,ζ=1/2ζ. . There is one subtlety. The integration variables are the real and imaginary parts of L and R, and the saddle-point equations should be taken with respect to these parts. The solutions to Re[La] and Im[La], which may be complex, are then added to produce La=Re[La]+iIm[La], and similarly for R. By linearity, this is equivalent to taking saddle-point equations with respect to La and La, and treating La and La as independent. It is convenient to write Ha=La+Ra for a head. The saddle-point equations are

La =gξOa+gηb,cMabcLbRc (20)
La =ghζδa1+gηa,b,cMabcHaδabRc (21)
Ra =gξOa+gηb,cMabcLbRc (22)
Ra =ghζδa1+gηa,b,cMabcHaLbδac (23)
-m =ηa,b,cMabcHaLbRc (24)
=ξaOaHa (25)
m =ζh(L1+R1) (26)

for all a.

(20),(21) and their pairs (22),(23) have an interpretation as recursion equations, which are equivalent to the saddle-point limit of Tutte recursion relations or loop equations in related contexts [22, 23]. They are also related to self-consistent equations derived for spin glasses on trees 44 4 For example, La is analagous to what is called ϕ({σa}) in [16] and gn({σa}) in [24]. In these works, ϕ and gn are functions of n Ising variables, so that they can take 2n different values. Below, we will replicate the La so that they take nN different values; N=2 is the Ising case.. Indeed, any La node can either propagate into La and become a leaf, with weight gξOa, or propagate into La and become another branch, with weight gηb,cMabcLbRc, including all possibilities. This gives (20). Similarly, any La node is either the child of a root, with weight gζhδb1, or the child of a branch, with weight gηa,a,cMaac(La+Ra)Rc, including all possibilities. This gives (21).

For specific grammars, (20)-(26) can be explicitly analyzed. Indeed, after writing these equations in terms of real variables, these take the form of ‘context-free schema’ as defined in section VII.6.1 in [25]. This class of equations, mainly defined by the fact that coefficients in the right-hand side of (20)-(26) are positive, generically have square root singularities at their radius of convergence [25]. Moreover, they can be solved by iteration.

These equations are also related to cavity equations, or belief propagation equations, in the literature of disordered systems [26]. For any probabilistic model living on a tree, the cavity equations are a closed, self-consistent set of equations that can be used to compute the partition function. The variables of these equations, known as messages, are probability measures on the symbols of the graph. Here the symbols are the hidden symbols, hence each message can be considered a variable with a colour index a=1N. In general, there are two messages per site: one going into the interaction, which here is a branch, and one outgoing. For a WCFG, the interaction at a branch depends only on the values of the hidden symbols there; there is no intrinsic site-to-site disorder. Therefore for large trees, one can seek a solution to the cavity equations that is independent of site, only depending on whether sites are the left or right children of their parent. In this case, the cavity equations become (20)-(26), up to some normalization factors. Therefore the variables L and R, which above were introduced as dummy variables to generate the diagrammatic expansion, in fact have their proper interpretation as messages: L is a downward message, while L is an upward message. In an iterative scheme to solve the cavity equations, these variables have additional time indices, hence the dynamical aspect of their name; (20)-(26) are the fixed-point equations.

In what follows, our interest, however, is in extracting the behavior of typical grammars in the case when N is large. For this we need to choose an ensemble.

4 Grammar ensembles

Figure 5: Distribution of individual grammar weights in (a) Random Language model (RLM) and (b) Gaussian model for ϵ~d as indicated. The regime of unphysical negative weights is shaded in the Gaussian model.

We will consider two models. In [1] it was argued that a generic model will have lognormally distributed weights, viz.,

G(M,O) ZG-1Je-ϵdsde-ϵsss (27)

where the deep and surface sparsities sd and ss are defined by

sd=1N3a,b,clog2[MabcM¯],ss=1NTa,Blog2[OaBO¯] (28)

and J=e-a,b,clogMabc-a,BlogOaB. Here M¯=1/N2 and O¯=1/T. A plot of the weights for a range of ϵ~d=ϵd/N3 is shown in Fig.5a. It is straightforward to show that ϵd and ϵs satisfy

sd¯=(2ϵ~d)-1,ss¯=(2ϵ~s)-1. (29)

where ¯ denotes a grammar average and ϵ~s=ϵs/(NT). A small ‘deep temperature’ ϵd corresponds to a large deep sparsity. The model (27) was called in [1] the Random Language Model (RLM).

It was shown in [1] that the RLM shows two phases, depending on the value of ϵ~d, plus logarithmic corrections. More precisely, Shannon entropies appear to collapse with respect to ϵ~dlogkN, where k=1 or k=2 depending on the quantity considered. For ϵ~dlogkN1, Shannon entropies are independent of the deep temperature ϵd, and take maximal values, indicating that the grammar does not carry information: despite strictly following the rules of a WCFG, sentences are indistinguishable from random noise. For smaller ϵd, entropies drop, and the grammar carries nontrivial information. It is our goal to extract this transition from (17).

It will turn out to be much simpler to consider an alternative model, where the weights Mabc and OaB are Gaussian, rather than lognormal; matching the mean and variance to those of the RLM we can again use the quantities M¯ and ϵ~d, and similarly for OaB. The distribution is plotted in Fig.5b. This model has the unphysical feature that weights have a negative tail; naively, we could imagine that this would be unimportant, since the largest weights are most important, but we will have to revise this statement later. We call this the Gaussian model (GM).

We wish to compute

log(𝒢)¯=(𝒢)nn|n=0¯=n|n=0(𝒢)n¯, (30)

where we used the replica method [27]. The fields ζ,ξ,η,L, and R are all replicated, adding an index i=1n. To compute 𝔽(𝒢)n¯ we need the grammar average

A(ξ,η,L,R) =eξi,aOaHai+ηi,a,b,cMabcHaiLbiRci¯
=a,BeξOaBiHai¯a,b,ceηMabciHaiLbiRci¯ (31)

Write xabc=iηiHaiLbiRci. In the RLM the grammar averages over M are of the form (m=logMabc/M¯)

ϵ~d/π𝑑me-ϵ~dm2eemM¯x =ϵ~d/π𝑑me-ϵ~dm2q0M¯qxqq!eqm (32)
=q0M¯qxqq!eq2/(4ϵ~d) (33)

A term of order q corresponds to the rule appearing q times. We are interested in a transition due to patterns of repeated rule application between sentences, rather than inside them (this would correspond to a transition deeper in the ordered phase). Therefore a priori we expect that we only need connected terms up to a small finite order q*. Note that at order q*, terms involving q* different replicas will be present. Resumming gives

q0M¯qxqq!eq2/(4ϵ~d)=exp(q1aqM¯qxq) (34)

with a1=e1/(4ϵ~d),a2=12(e4/(4ϵ~d)-e2/(4ϵ~d)), etc. From this divergent sum we only need to retain terms up to order q=n(-m), since the integration over η will retain only -m vertices for each replica.

For practical reasons exact calculations are limited to q*=2. In this case, we consider all derivations in which a rule can appear at most twice in one derivation tree. Note that rules can still appear arbitrarily many times in the set of n replicas and m sentences. Keeping terms to q*=2 is equivalent to letting the M be drawn from a Gaussian distribution. For appropriate choice of mean and variance, we can thus fix the GM to be equal to the RLM to this order. In the remainder of this work, we will first find the exact solution of the GM, and then discuss its extension to the RLM.

4.1 Gaussian model

Applying the same arguments to the integral over O, we have for the GM

A(ξ,η,L,R) =a,Beb1O¯iξiHai+b2O¯2(iξiHai)2a,b,cea1M¯iηiHaiLbiRci+a2M¯2(iηiHaiLbiRci)2
=eb1NTO¯iξiH*i+b2TO¯2i,jξiξjQHij+a1N3M¯iηiH*iL*iR*i+a2M¯2i,jηiηjQHijQLijQRij (35)

where we introduced ‘magnetization’ vectors and overlap matrices

H*i=1NaHai,L*i=1NaLai,R*i=1NaRai, (36)
QHij=aHaiHaj,QLij=aLaiLaj,QRij=aRaiRaj, (37)

and b1=e1/(4ϵ~s),b2=12(e4/(4ϵ~s)-e2/(4ϵ~s)). (Recall that Ha=La+Ra.). Assembling the above results we find that for the GM,

(𝒢)n¯ =i[m!dζiζi1+mdξiξi1+dηiηi1+-mDLiDRie-1ga[LaiLai+RaiRai]]

This is now in the form amenable to standard treatment by replicas: the overlap matrices can be introduced as new parameters, and the original variables can be integrated out. We notice that the colour indices play the role usually played by spatial indices in spin glasses [27]. The surprising result is that the model can be exactly integrated, without even making an ansatz on the replica structure, and without taking the large limit. This integrability can be traced to the fact that the overlap matrices depend only on the real and imaginary parts of L in the canonical way, i.e. through Lai=Re[Lai]+iIm[Lai]. This gives rise to a symplectic structure that simplifies the integration over these variables. The derivation is sketched in Appendix A. The final result is

log¯ =mlogh+(2-m)logg+S,m+log(TO¯b1)+0log(N2M¯a1) (38)

with 0=-m,

f(x)=dt2πe-12t2log[1+xt], (39)


S,m=log0!-log!+log(1++0)!-log(1+20)! (40)

Here xd=N-3/2e1/(2ϵ~d)-1 and xs=(NT)-1/2e1/(2ϵ~s)-1.

The elements of log¯ are as follows. Those involving h and g give logtree, the contribution to log that weights configurations by the number of sentences and leaves; these are precisely those required from 18. S,m is entropic, and apparently counts the number of ways to partition a total string of length into m sentences. Terms with bj and aj are energetic, since they depend on the grammar weight distribution. Those involving b1 and a1 capture the change in the mean occupancy as temperature is varied. The function f(x) captures the non-trivial effects of correlation between different symbols. This function, which can written in terms of hypergeometric functions, is plotted in Fig.6. It develops an imaginary part for x𝒪(1), indicating that the unphysical negative probability states are becoming important. For large N the condition xd𝒪(1) is equivalent to

ϵ~dlogN1/6, (41)

and similarly the condition xs𝒪(1) is equivalent to ϵ~slogNT1/2. These inequalities fix the regime in which the GM is physical.

Figure 6: Function f(x) from 39.

4.2 RLM

We now return to the full model. As discussed above, we cannot obtain the exact solution; however, since a saddle-point method is justified for large , we can consider different ansatze on the form of the solution. Two are natural: (i) the colour-symmetric ansatz Lai=Li,Rai=Ri a, and the (ii) replica-symmetric ansatz Lai=La,Rai=Ra i. After some calculations similar to those for the GM, we eventually find for either (i) or (ii) the same form (38), except that f0. Besides the ansatze on the form of L and R, we assume that is large and that the replica limit n0 can be taken perturbatively, i.e. keeping terms 𝒪(n) in the action, as in the usual approach [27] 55 5 Consistency with the GM suggests that we should be able to recover (38) with f0 for that model, without necessarily taking the limit ϵ~d,ϵ~s, in which case the f terms are trivially unimportant. Indeed, if instead of taking n0 in (49), we look for a saddle-point with large , the saddle-point perturbative in n gives exactly (38) with f0. This indicates that the function f is nonperturbative in the replica limit.. We now analyze (38) with f0, with the understanding that this holds in the replica-symmetric regime, whose range of validity is to be determined.

It is convenient to separate F=-log¯ into its entropic and energetic contributions. This can be done exactly because the RLM has a scaling symmetry when the bias β is included. Indeed, it is not hard to show that the partition function satisfies the scaling property n¯(β,ϵ~d,M¯,ϵ~s,O¯)=n¯(1,ϵ~d/β2,M¯β,ϵ~s/β2,O¯β) (in abuse of earlier notation). The β-dependent part of F is

Fβ=-βlogO¯-β0logM¯-β24ϵ~s-β204ϵ~d (42)

so that at β=1, E=-logO¯-0logM¯-2ϵ~s-02ϵ~d and the replica-symmetric entropy is

SRS=0log(gN2/h)+log(gTh)-4ϵ~s-04ϵ~d+S,m (43)

The entropy cannot be negative; this gives necessary, though perhaps not sufficient, conditions on the regime where the replica-symmetric ansatz is applicable. For simplicity, consider the case ,m/=α1 (/m is the typical length of a tree; we let it be large). Then one can determine that S,m=𝒪(α) and, for the simulated case where the emission probability is close to p=1/2, g=h1/8. The condition SRS>0 is approximately equivalent to

14ϵ~d+14ϵ~slog(N2T/8) (44)

Our main concern is the emergence of deep structure, which does not depend on what happens at the surface of the tree. In the limit ϵ~s, this becomes ϵ~dlog(N2T/8)1/4, very similar to the regime in which the GM is physical, 41.

4.3 Order parameter

Finally, we return to the order parameter Q2 that measures deep structure. Let us first give a heuristic derivation of its value in the RLM. We need to compute q0=πabc2¯ and q1=πabcπabc¯, where πabc is the occupancy of the rule abc. Using (7) and (13) in the diagrammatic representation, one can see that πabc=ehabcηMabcHaLbRc. The πabc satisfy the sum rule abcπabc=0 and so have a mean value π¯=0/N3. The occupancies are positively correlated with the grammar weights, since rules with higher weights are sampled more frequently. A crude estimate is then πabc/π¯Mabc/(M¯a1) (the mean value of a weight is M¯a1). This leads to the estimate

Q2 N5(N2-1)0202N6M¯2a12Mabc2-MabcMabc¯
=N2-1N(e1/(2ϵ~d)-1), (45)

which indicates that order increases as ϵd is lowered simply because the weight variance increases. Q2 can be computed more precisely using replicas. After a long computation, assuming the replica symmetric ansatz and taking large , one eventually finds exactly the same result, (45). Thus this simple expression is in fact the genuine replica symmetric result; it is plotted in Fig.2, where it is compared with numerical data 66 6 These data have been obtained by the same methods as described in [1]. Here we have simulated many more samples (105 compared to 103 in that work) in order to resolve the large ϵd part of the curve.. In the large limit, it matches quantitatively, without fitting parameters, above ϵ~dlogN1. For smaller ϵ~d, the data asymptote, as they must, while the replica-symmetric prediction diverges.

5 Conclusion

We showed that the partition function for weighted context-free grammars has a convenient diagrammatic representation. For individual grammars, the behavior of a large text 1 is governed by saddle-point equations, which resemble belief-propagation equations [26].

We then considered two ensembles of grammars, which are equivalent in a large temperature limit. The Gaussian model (GM) was solved exactly, and shown to become unphysical for ϵ~dlogN1/6. For the random language model (RLM), previously simulated in [1], the partition function was computed in the replica-symmetric ansatz; the entropy becomes negative at low temperature, again depending essentially on the quantity ϵ~dlogN. Finally, the order parameter Q2 was computed in the replica-symmetric ansatz. The prediction quantitatively agrees with simulations above ϵ~dlogN1. These results indicate that replica-symmetry must be broken in the nontrivial low-temperature phase.

The RLM bears some similarity to a spin-glass on the Bethe lattice, a difficult problem that is still not fully understood [28, 29]. Indeed, both problems can be generated by a diagrammatic method [17], and in both problems one finds that overlaps of all orders are needed to compute the partition function [30, 28, 24, 29]. However, for the spin-glass, one can perform an expansion around the mean-field limit [30, 28, 24], which is the Sherrington-Kirkpatrick model solved by Parisi [27]. Naïvely, the analogue to the SK model would be the Gaussian model, which we solved above. However, we showed that this model does not break the replica symmetry. This is related to a gauge symmetry in the diagrammatic formulation. It is therefore an open question whether there is a more primitive model that captures the essence of random languages in the low-temperature phase, and remains solvable.

Finally, we have focussed here on context-free grammars, for which derivations are trees. The next level up in the Chomsky hierarchy are context-sensitive grammars. A theorem of Kuroda [31] says that it is sufficient to add rules of the form abcd to those above to model all context-sensitive grammars. Clearly this will add a quartic vertex to our (16), which is not in itself a difficulty. However, well-formed derivations must be represented by planar diagrams, so that the order of symbols is preserved in the derivation. Generating random planar graphs that are not trees requires matrices as integration variables; this strongly suggests that general grammars require the full machinery of complex matrix models.

I am grateful to V. Kazakov and G. Semerjian for conversations at an early stage of this work, and to G. Parisi and W. Bialek for encouragement.


  • [1] DeGiuli E 2019 Phys. Rev. Lett. 122 128301
  • [2] Loreto V and Steels L 2007 Nature Physics 3 758
  • [3] Loreto V, Baronchelli A, Mukherjee A, Puglisi A and Tria F 2011 Journal of Statistical Mechanics: Theory and Experiment 2011 P04006 1742–5468
  • [4] Burridge J 2017 Physical Review X 7 031008
  • [5] Carnie A 2013 Syntax: A generative introduction (John Wiley & Sons, Ltd.)
  • [6] Chomsky N 2002 Syntactic structures (Berlin: Walter de Gruyter)
  • [7] Hopcroft J E, Motwani R and Ullman J D 2007 Introduction to automata theory, languages, and computation 3rd ed (Boston, Ma: Pearson)
  • [8] Lin H W and Tegmark M 2017 Entropy 19 299
  • [9] Piattelli-Palmarini M and Vitiello G 2015 arXiv preprint arXiv:1506.08663
  • [10] Gallego A J and Orus R 2017 arXiv preprint arXiv:1708.01525
  • [11] Pestun V and Vlassopoulos Y 2017 arXiv preprint arXiv:1710.10248
  • [12] Searls D B 2002 Nature 420 211
  • [13] Di Francesco P, Ginsparg P and Zinn-Justin J 1995 Physics Reports 254 1–133
  • [14] Kazakov V 1986 Physics Letters A 119 140–144
  • [15] Boulatov D and Kazakov V 1987 Physics Letters B 186 379–384 0370–2693
  • [16] Bachas C, De Calan C and Petropoulos P 1994 Journal of Physics A: Mathematical and General 27 6121
  • [17] Baillie C, Janke W, Johnston D and Plecháč P 1995 Nuclear Physics B 450 730–752
  • [18] Bessis D, Itzykson C and Zuber J B 1980 Advances in Applied Mathematics 1 109–157
  • [19] t’Hooft G 1974 Nuclear Physics. B 72 461–473
  • [20] Brezin E, Itzykson C, Parisi G and Zuber J 1978 Commun. math. Phys 59 35–51
  • [21] Le Guillou J C and Zinn-Justin J 2012 Large-order behaviour of perturbation theory vol 7 (Elsevier)
  • [22] Di Francesco P 2006 2D quantum gravity, matrix models and graph combinatorics (Springer) pp 33–88
  • [23] Eynard B 2016 Counting surfaces (Springer)
  • [24] Parisi G and Tria F 2002 The European Physical Journal B-Condensed Matter and Complex Systems 30 533–541
  • [25] Flajolet P and Sedgewick R 2009 Analytic combinatorics (cambridge University press)
  • [26] Mezard M and Montanari A 2009 Information, physics, and computation (Oxford University Press)
  • [27] Mézard M, Parisi G and Virasoro M 1987 Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications vol 9 (World Scientific Publishing Company)
  • [28] Mézard M and Parisi G 2001 The European Physical Journal B-Condensed Matter and Complex Systems 20 217–233
  • [29] Parisi G 2017 Journal of Statistical Physics 167 515–542 0022–4715
  • [30] De Dominicis C and Goldschmidt Y 1989 Journal of Physics A: Mathematical and General 22 L775
  • [31] Kuroda S Y 1964 Information and Control 7 207–223
  • [32] Mackey D S and Mackey N 2003 On the determinant of symplectic matrices (Manchester Centre for Computational Mathematics)

Appendix A Solution of Gaussian model

We introduce QLij=aLaiLaj as a new variable with a corresponding momentum ΛLij, and similarly for QRij=aRaiRaj and Pij=aLaiRaj, with conjugate momenta ΛR and ΛP, respectively. Let us write xai=Re[Lai],yai=Im[Lai]. The variables {xai,yai} are Gaussian, with a coupling matrix diagonal in colour. For each a, the coupling matrix is a 2n×2n matrix acting on (xa1,xan,ya1,,yan),

Z=[δ^-gΛ^L-giΛ^L-giΛ^Lδ^+gΛ^L], (46)

where δ^ is the n×n identity matrix. It is easily verified that Z is complex symplectic: J=ZtJZ, where

J=[0δ^-δ^0] (47)

This implies that Z-1=J-1ZtJ and, less obviously, |Z|=1 [32]. Hence after integrating out {Lai} there is no nontrivial entropic term from log|Z|, nor does there appear the inverse of ΛL, as would naively be expected. In fact, after integrating out {Lai} and {Rai} the action remains linear in ΛL, ΛR, and ΛP. Hence these can be immediately integrated out and we find that

QLij=NL*iL*j,QRij=NR*iR*j,Pij=NL*iR*j (48)

We find

(𝒢)n¯ =i[m!dζiζi1+mdξiξi1+dηiηi1+-m𝑑L*i𝑑R*ie-Nga[L*iL*i+R*iR*i]]

with b~j=NTO¯jbj,a~j=N3M¯jaj, j=1,2. The quadratic terms can be linearized with a Hubbard-Stratonovich transformation, after which the integrals over ζ,ξ, and η are simple. The result is

(𝒢)n¯ =12π𝑑pe-12p2𝑑qe-12q2[𝑑L𝑑RK(L,R,p,q)]n (49)


K(L,R,p,q) =hm(πg/N)-2!(-m)!(b~1+p2b~2)(a~1+q2a~2)-m
  e-Ng[LL+RR](L+R)2-m(LR)-m (50)

The calculation is thus reduced to an effective single-colour problem. We have

  =hm!(g/N)2-m(-m)!(1+2-m)!(1+2-2m)! (51)

so that the final result is

log¯ =mlogh+(2-m)log(g/N)+S,m+logb~1+(-m)loga~1
+f(2b~2/b~12)+(-m)f(2a~2/a~12) (52)


f(x)=dt2πe-12t2log[1+xt] (53)

and S,m=log(-m)!-log!+log(1+2-m)!-log(1+2-2m)!. Letting xd=2a~2/a~12=N-3/2e1/(2ϵ~d)-1 and xs=(NT)-1/2e1/(2ϵ~s)-1, we have the result shown in the main text.