Random Language Model

Many complex generative systems use languages to create structured objects. We consider a model of random languages, defined by weighted context-free grammars. As the distribution of grammar weights broadens, a transition is found from a random phase, in which sentences are indistinguishable from noise, to an organized phase in which nontrivial information is carried. This marks the emergence of deep structure in the language, and can be understood by a competition between energy and entropy.

Figure 1

Illustrative derivation trees for (a) simple English sentence, and (b) the RNA secondary structure (after [6]). The latter is a derivation of the sequence “gacuaagcugaguc” and shows its folded structure. Terminal symbols are encircled.

Figure 2

Shannon entropy of random CFGs as functions of ${\tilde{\epsilon }}_d={\epsilon }_d/N^3$. (a) Block entropy of hidden configurations for indicated $k$ and $N$. (b) Block entropy of observed strings; symbols as in (a). The constant value for ${\epsilon }_d>{\epsilon }_{*}$ depends on the surface temperature ${\epsilon }_s$. Bars indicate 20th and 80th percentiles.

Figure 3

(a) Zipf plot of hidden symbols for $N=40$. Here ${\tilde{\epsilon }}_d={\epsilon }_d/N^3$. (b) Order parameter $Q_2$, with bars indicating 20th and 80th percentile ranges over grammars at each parameter value. Inset: same plot in log-log axes.