Vol. XXXI · History and Projects Plate 1 of 14history, Shannon, entropy of English, n-grams, smoothing, speech recognition, statistical machine translationDL

From Shannon to n-grams.

Predict the next letter from the last few. It worked better than anyone expected, for fifty years.

Shannon’s 1948 paper defined information and, in passing, generated text from letter and word n-gram statistics of English — the first language models. In 1951 he asked people to guess the next letter of a passage and estimated that English carries between 0.6 and 1.3 bits per letter: most of the 4.7 bits a letter could carry is redundancy a good model can predict.

The engineering came decades later. Jelinek’s group at IBM recast speech recognition as finding the most probable word sequence under an acoustic model times a language model, and n-gram language models with smoothing — Good–Turing, Katz back-off, Kneser–Ney — became the workhorse of speech and translation systems through the 2000s, trained on ever larger corpora. The workshop builds character n-gram models of course text, measures their bits per character on held-out text, and compares them with Shannon’s range.

Left: milestones. Right: bits per character of character n-gram models of English course text, by order, against Shannon’s estimate for English.

What you will learn
Workshop
Character n-grams of order 1–8 trained on 140 000 characters of English course text with add-0.01 smoothing, evaluated on the next 20 000 characters; Shannon’s 1951 range for printed English shown as a band. Course text is technical English, so the comparison is indicative.

Counting goes a long way, then stops

Character frequencies alone give 4.51 bits per character; the best n-gram here reaches 3.15 at order 4, and longer contexts get worse because most of their counts are zero — the sparsity that plate I.6 showed. Shannon’s human subjects did far better, 0.6 to 1.3 bits, because they brought knowledge of words, grammar and the world: the gap between counting and understanding that the rest of the field’s history closes.

n-gram models were not a dead end. They established the framing of this whole course — a probability over sequences, scored by cross-entropy on held-out text — and the lesson that more data beats cleverer models, which Brants and colleagues summarised in 2007 with a two-trillion-token n-gram model whose crude “stupid back-off” smoothing beat careful methods at scale. The next plate replaces the counts with learned vectors.

Shannon’s 1948 paper already contains machine-generated “English” from word bigrams — “THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER…” — the first sampled text from a language model.

Terms

Entropy of English
The average information per letter, estimated from prediction.
n-gram model
A model predicting from the previous n − 1 units by counting.
Smoothing
Assigning probability to unseen n-grams.
Noisy-channel model
Recognition as the most probable source given the signal.
Language modelling began with Shannon’s measurements and counted n-grams, which carried speech and translation for decades and fixed the framing still in use.

Sources

  1. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal, 1948.
  2. Shannon, “Prediction and Entropy of Printed English”, Bell System Technical Journal, 1951.
  3. Jelinek, “Continuous speech recognition by statistical methods”, Proceedings of the IEEE, 1976.
  4. Kneser and Ney, “Improved backing-off for M-gram language modeling”, ICASSP 1995.
  5. Brants et al., “Large Language Models in Machine Translation”, EMNLP 2007.