Language Models by Counting

Phones suggest the next word, and speech recognisers choose between "recognise speech" and "wreck a nice beach". Both rely on a language model: a way of saying how likely a word is given the words before it. The oldest and simplest kind is built from nothing but counting.

What a Language Model Is

Wikipedia's Language model article defines it as a computational model that predicts sequences in natural language, with uses including speech recognition, machine translation and natural language generation. Its history section runs: in the 1950s Noam Chomsky developed formal grammar-based approaches; in the 1970s Frederick Jelinek and colleagues at IBM developed statistical models using probabilistic n-grams; in the 2000s Yoshua Bengio and co-authors introduced a neural probabilistic language model; in 2010 Tomáš Mikolov and colleagues showed recurrent neural network models could substantially outperform n-gram models; and large language models, based mainly on transformers, are the most advanced form as of 2026. This chapter stays with the statistical stage; NLP 6 covers the neural sequence models.

n-grams

The N-gram article defines an n-gram as "a sequence of n adjacent symbols in a particular order"; the symbols can be letters, syllables, words, phonemes or DNA base pairs. Size 1 is a unigram, 2 a bigram, 3 a trigram. It says n-grams let bag-of-words models capture word order, and cites Shannon's 1951 examples and Google's n-gram corpus. The Language model article describes an n-gram model as one that "calculates the probability of the next word in a sequence from a fixed size window of previous words": a bigram model uses one previous word, a trigram two, an n-gram model n − 1.

Estimating by counting is my explanation. Neither page, in the parts I read, explains how the probabilities are computed from counts. The usual idea, which I demonstrate below, is: P(next word | previous word) = (how often the pair occurred) ÷ (how often the previous word occurred).

A bigram model of 66 words

The text is Chapter 3's invented lighthouse paragraph. The code and outputs are mine, run with py -X utf8.

The occurs 14 times. Four of those are followed by keeper, so the model says P(keeper | the) = 4/14 ≈ 0.286; sea follows twice, 0.143; and dog, which never follows the in this text, gets 0.0.

The Zero Problem

A sentence's probability, in this model, is the product of its bigram probabilities. Try a perfectly sensible sentence the model has not seen:

The pair keeper watched never occurs in the text (the keeper drank and made and climbed), so the whole sentence gets probability 0.0, as if it were impossible. That is the data sparsity problem. The Language model article treats it as a core problem: unseen word sequences would otherwise get zero probability, so seen probabilities are slightly lowered to make room for unseen ones; the methods it names are add-one smoothing, Good–Turing discounting and back-off models. It says skip-gram models were an attempt at "overcoming the data sparsity problem" of word n-gram models, and that neural embeddings are said to help alleviate the curse of dimensionality, which causes data sparsity as vocabulary size grows. The N-gram page, in the part I read, does not cover sparsity, smoothing or the limits of n-gram models.

Smoothing

The Additive smoothing article calls it "a technique used to smooth count data, eliminating issues caused by certain values having 0 occurrences", also called Laplace or Lidstone smoothing. For counts x_i out of N trials across d categories the smoothed estimate is (x_i + α) / (N + αd), where α > 0 is the pseudocount; α = 1 is add-one smoothing, and common values are 0, ½ and 1. The estimate lies between the observed frequency and the uniform probability 1/d, so it is a shrinkage estimator. The article says treating an unseen event's observed zero as a probability of zero is "an oversimplification". It reports studies finding it more effective than some other smoothing methods for tasks such as language-model-based pseudo-relevance feedback and recommender systems, and notes it is a common component of naive Bayes classifiers. Its limits, which it implies: the choice of α is partly subjective, and larger pseudocounts pull estimates toward uniform.

Applied to the bigram model, with V = 40 word types as the vocabulary size (my mapping of the article's formula: N = count of the first word, d = V):

The impossible pair now has probability 0.0227, so the sentence has a small but nonzero probability (5.7 × 10^-6). The last line is a check: the smoothed probabilities of every possible next word after the still add up to 1.0. The price is that every seen pair lost some probability: P(keeper | the) fell from 0.286 to 0.0926. With a 40-word vocabulary and only 66 words of text, add-one smoothing takes a large bite.

Perplexity

The Perplexity article defines it as "a measurement of how well a probability distribution or probability model predicts a sample": low perplexity means it predicts the sample well. It is "the exponentiation of the entropy", and a random variable with perplexity k has the same uncertainty as a fair k-sided die. For a language model, a model q is judged on a separate test sample, and better models "will tend to assign higher probabilities" to it, hence lower perplexity; for language the article uses perplexity per word. Its word-level example is a model "as confused on test data as if it had to choose uniformly and independently among 247 possibilities for each word." It cautions that perplexity "is sometimes used as a measure of the difficulty of a prediction problem," but "it's not always an accurate representation". The Language model article's own evaluation section does not cover perplexity; it appears there only in the history section.

Perplexity 20.5: on this sentence the smoothed model is about as unsure as if it were choosing among roughly 20 equally likely words each time (the vocabulary has 40). I normalise by the four predictions, not five words, because a bigram model does not predict the first word; that is my choice, and other conventions exist.

Try It Yourself