Generating text with a Markov model

Intermediate

Introduction

The letter model of the first lesson knew how common each letter is, but not their order. The next step up is to learn which word tends to follow which. This idea, a Markov model of text, was used to generate text long before neural networks, and it is the direct ancestor of today's language models, which also predict the next piece of text from what came before.

How it works

Training is counting. For every pair of neighbouring words (a bigram) in the training text, count how often the second follows the first. After "the", this corpus has cat twice and mat, fish, dog and log once each. Dividing by the total gives the next-word probabilities:

P(next = cat | current = the) = count(the cat) / count(the followed by anything) = 2 / 6

A model whose next word depends only on the current one is a Markov model (after the mathematician Andrey Markov). Looking at the last two words (trigrams) or more gives an n-gram model; the words used to predict are the context.

Generation starts from a word and repeatedly chooses a next word:

  • Greedy generation always takes the most likely next word. It is repeatable, but it easily falls into loops: the cat ate the cat ate the...
  • Sampling picks the next word at random with its probability (the method of the last lesson), so the text varies and escapes loops, at the risk of odd choices.

A bigram model writes locally sensible phrases but no coherent sentences, because one word of context is not enough. Longer n-grams help, but most long word sequences never appear in any training text, so the counts run out. Large language models solve this by learning a smooth function of a long context instead of counting exact sequences.

Example

corpus = "the cat sat on the mat . the cat ate the fish . the dog sat on the log ."
words = corpus.split()

# Training: count which word follows which
following = {}
for a, b in zip(words, words[1:]):
    following.setdefault(a, {})
    following[a][b] = following[a].get(b, 0) + 1
print("after 'the':", following["the"])
print("after 'sat':", following["sat"])


def most_likely(word):
    options = following[word]
    return min(options, key=lambda w: (-options[w], w))  # highest count, then alphabetical


# Generation: always take the most likely next word
word, text = "the", ["the"]
while word != "." and len(text) < 10:
    word = most_likely(word)
    text.append(word)
print("greedy:", " ".join(text))
Open in compiler

Line by line

  1. The corpus is split into words; "." counts as a word, so the model also learns where sentences end.
  2. zip(words, words[1:]) pairs each word with the next one, and following counts the pairs.
  3. The two printed tables show the learned counts after "the" and after "sat".
  4. most_likely picks the next word with the highest count, breaking ties alphabetically.
  5. Greedy generation runs until it reaches "." or ten words. After "cat", "ate" and "sat" are tied and "ate" wins, which sends it back to "the cat" again: a loop.

Expected result

after 'the': {'cat': 2, 'mat': 1, 'fish': 1, 'dog': 1, 'log': 1}
after 'sat': {'on': 2}
greedy: the cat ate the cat ate the cat ate the

In the real world

Phone keyboards long used n-gram models to suggest the next word, and speech recognizers used them to choose between similar-sounding phrases. Markov chains still generate filler text, game dialogue and test data. The greedy loop in the example is a real problem even for large models, which is why chat assistants sample with settings such as temperature and penalties for repetition (lesson 6).

Common mistakes

  • Using greedy generation and getting the same loop every time.
  • Forgetting sentence ends, so generation never stops.
  • Expecting long-range sense from a model that only sees one word back.
  • Dividing by the number of all words instead of the number of pairs that start with the current word.

Best practices

  • Include an end marker such as "." so the model learns where to stop.
  • Cap the length of generated text.
  • Break ties in a fixed order so results are repeatable, and sample when you want variety.

Summary

A bigram (Markov) model learns next-word probabilities by counting neighbouring word pairs. Generation starts from a word and repeatedly picks a next word, either the most likely one (greedy, repeatable but loop-prone) or a sampled one (varied). One word of context is too little for coherent text; more context helps, and language models learn to use long contexts without exact counts.

Quick check

1. In the corpus, 'the' is followed by cat twice and by four other words once each. What is P(cat | the)?
2. What does a bigram model use to predict the next word?
3. Why does greedy generation often loop?
4. Why include '.' as a word in the training text?

Key takeaways

  • A bigram model predicts the next word from the current word alone, using counts.
  • Greedy generation is repeatable but gets stuck in loops; sampling adds variety.
  • More context gives more sensible text, which is what large language models take to the extreme.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.