Statistical mechanics of letters in words

We consider words as a network of interacting letters, and approximate the probability distribution of states taken on by this network. Despite the intuition that the rules of English spelling are highly combinatorial and arbitrary, we find that maximum entropy models consistent with pairwise correlations among letters provide a surprisingly good approximation to the full statistics of words, capturing $\sim 92\mathrm{\%}$ of the multi-information in four-letter words and even “discovering” words that were not represented in the data. These maximum entropy models incorporate letter interactions through a set of pairwise potentials and thus define an energy landscape on the space of possible words. Guided by the large letter redundancy we seek a lower-dimensional encoding of the letter distribution and show that distinctions between local minima in the landscape account for $\sim 68\mathrm{\%}$ of the four-letter entropy. We suggest that these states provide an effective vocabulary which is matched to the frequency of word use and much smaller than the full lexicon.

Figure 1

(Color online) (a) The six pairwise marginal distributions of four-letter words sampled from the Jane Austen corpus. Common letter pairs such as “th” in ${\rho }_{12}$ are apparent in their large marginal probability. (b) The iterative scaling algorithm solves the constrained maximization problem to high precision. All pairwise marginal components of the full distribution are compared to the marginals constructed from the computed maximum entropy distribution.

Figure 2

(Color online) (left) The pairwise maximum entropy model provides an excellent approximation to the full distribution of four-letter words, capturing 92% of the multi-information. (right, dots) Scatter plot of the four-letter word probabilities in the full distribution $P_{\text{full}}$ vs the corresponding probabilities in the maximum entropy distribution $P_2$. (right, red crosses) To facilitate the comparison we divided the full probability into 20 equally logarithmic-spaced bins and computed the mean maximum entropy probability conditioned on the states in the full distribution within each bin. The dashed line marks the identity. (right, blue circles) We singled out two words, edge and itch, whose small probability is well captured by the pairwise model yet whose sounds, “dge” and “tch,” could have resulted from a triplet interaction.

Figure 3

(Color online) The Zipf plot for all words in the corpus (solid black line), four-letter words in the corpus (blue asterisks), and four-letter words in the maximum entropy model (red crosses). Green circles denote non-words, states in the maximum entropy model that did not appear in the corpus. The 25 most likely non-words are shown in the text inset (ordered in decreasing probability from left to right and top to bottom). Some of these are recognizable as real words that did not appear in the corpus, and even the others have plausible spelling.

Figure 4

(Color online) The energy landscape of the maximum entropy model estimated from the ANC corpus. To find the local minima we take each word in the corpus, compute the change in energy for all single-letter replacements, substitute the letter replacement which is lowest in energy, and repeat until letter replacements only increase the energy. This dynamics assigns each word to unique local minima (black filled circle with the lowest energy in each basin) and distinctions between these local minima account for $\sim 68\mathrm{\%}$ of the full entropy. We order the basins by decreasing probability of their ground states and show only the lower-energy excitations in each basin and the first ten ground states. The energy landscape suggests that an effective vocabulary is built by first populating distinct basin states (which are error correcting by construction). Finer distinctions are then contained in the low-lying excitations. The arbitrary energy offset is chosen so the most likely stable word has zero energy.