Project 40: Markov Chain Text Generator

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 1-2 weeks
  • Language: Python
  • Prerequisites: Projects 6, 12, and 20
  • Source: ML-Math P16

What You Will Build

Build a character- or word-level n-gram text generator as a finite Markov chain. Tokenize a corpus, count transitions from states of order n to next tokens, normalize counts into probability distributions, and sample seeded continuations. Provide order-1 through higher-order models, start/end tokens, unknown-state fallback, and optional additive smoothing. Visualize a small transition matrix or graph and inspect the highest-probability successors of any state. Measure held-out negative log-likelihood/perplexity where possible, and compare diversity, coherence, memory, and sparsity as order changes. Add a synthetic transition-matrix mode that simulates arbitrary chains and estimates occupancy/stationary behavior, connecting text generation to general Markov processes.

Real World Outcome

After training on a text file, the CLI reports vocabulary, state count, transition sparsity, and held-out score, then emits reproducible samples from a prompt. An inspector displays successor probabilities and observed counts. A comparison report shows that low order is repetitive but robust, while high order copies longer fragments and suffers unseen states.

Core Question

How much sequence structure can be captured by assuming the next token depends only on a finite recent state, and what breaks as that memory grows?

Concepts You Must Understand First

  1. Markov property: the modeled future depends on the current state, not the full history.
  2. Conditional probability: transition rows are normalized distributions over next states.
  3. Transition matrices: repeated multiplication evolves state distributions and may approach stationary behavior.
  4. N-gram state design: increasing order stores more context but causes sparse, unseen states. See Jurafsky and Martin, Speech and Language Processing, n-gram chapters.
  5. Sampling and likelihood: seeded categorical draws generate sequences; log probabilities avoid underflow when scoring them.

Build Milestones

  1. Build deterministic tokenization, start/end markers, and transition counts for a tiny hand corpus.
  2. Normalize transitions and implement seeded categorical sampling with probability checks.
  3. Generalize to configurable n-gram order and prompt-conditioned generation.
  4. Add smoothing/fallback, held-out log-likelihood, and order-comparison experiments.
  5. Visualize small chains and estimate occupancy/stationary distributions through simulation.

Hints in Layers

  1. Preserve raw counts; derive probabilities on demand so smoothing and diagnostics remain possible.
  2. Sample by cumulative probability with one seeded random generator, and test boundary draws.
  3. Split the corpus before building counts; otherwise held-out likelihood measures memorization on training data.

Common Pitfalls and Debugging

  • Symptom: generated text stops immediately or crashes. Cause: prompt state was unseen or has no outgoing transition. Fix: implement backoff, restart, or explicit end-state handling.
  • Symptom: probabilities do not sum to one. Cause: wrong denominator or mixed state orders. Fix: assert each nonterminal row independently.
  • Symptom: high-order evaluation looks excellent. Cause: train/test leakage or copied spans. Fix: split first and inspect overlap and unseen-state rate.

Definition of Done

  • Counts and probabilities match a hand-worked corpus.
  • Every nonterminal state’s transition probabilities normalize within tolerance.
  • Seeded generation is reproducible for multiple n-gram orders.
  • Unknown states and sequence endings have explicit behavior.
  • Held-out scoring and sparsity/unseen-state statistics compare model orders.
  • A small transition graph and simulation demonstrate general Markov-chain behavior.

Previous: Project 39 · Complete learning path · Next: Project 41