Deep NLP

5 episodes · follows chapter 3 of the textbook

N-gram Language Models

A language model assigns a probability to every possible sentence. This module builds the oldest working one, the n-gram model, from nothing: the chain rule of probability turns a sentence into a product of next-word predictions, the Markov assumption bounds the context, and counting (which we prove is maximum likelihood) fills the table. We then measure models with cross-entropy and perplexity (the same number every LLM training log prints), sample from them, watch them overfit, and repair their zeros with smoothing, ending in interpolated Kneser-Ney.

Progress — loading…

Objectives

Language

  • Explain what a language model is as a probability distribution over sentences, and why next-word prediction is equivalent
  • Explain why sparsity (most n-grams are never seen) is the central problem of count-based language modeling
  • Evaluate a language model on held-out text honestly: train/dev/test discipline, <s> and </s>, <UNK>, and leakage
  • Describe how n-gram models were used in speech recognition and machine translation, and where n-gram statistics are used in LLM work today (data filtering, contamination checks, infini-gram)

Math & data structures

  • Chain rule of probability, conditional probability as a filtered count, the Markov assumption
  • Maximum likelihood estimation, with an argument for why relative frequency maximizes likelihood
  • Logarithms for probabilities: products become sums, underflow avoided
  • Entropy, cross-entropy, and perplexity = 2^H as a weighted branching factor; the link to compression
  • Count tables as nested hash maps and tries; memory and lookup cost; sparsity
  • Smoothing as moving probability mass: add-k, interpolation (EM for the weights), backoff, absolute discounting, Kneser-Ney continuation counts

Code

  • nlpcore.lm.ngram: counts, trie, vocabulary with <UNK>, MLE model with a shared LanguageModel interface
  • nlpcore.eval.perplexity: the course-wide perplexity / bits-per-byte module
  • nlpcore.lm.sampling_np: temperature, top-k/top-p preview, inverse-CDF sampling, Shannon's game
  • nlpcore.lm.smoothing: add-k, interpolation with EM, stupid backoff, absolute discounting, (modified) Kneser-Ney
  • A bigram model trained by gradient descent that converges to the counts (bridge to Logistic Regression and Text Classification and Transformers and Pretraining)

Episodes

  1. The Chain Rule of Probability and the Markov Bet34 min · 31 cues

    Joint probability of a sentence, chain rule, Markov assumption as a cache with bounded context; Markov 1913 Eugene Onegin.

  2. Counting Is Learning: Maximum Likelihood30 min · 31 cues

    MLE from counts, why relative frequency maximizes likelihood (derivation with Lagrange intuition or simple argument), n-gram tables as nested dicts/tries, train/dev/test.

  3. Perplexity, Entropy, and Cross-Entropy26 min · 31 cues

    Perplexity as weighted branching factor; entropy as average bits (Huffman); cross-entropy; perplexity = 2^H; connection to LLM loss.

  4. Sampling, Shannon's Game, and Overfitting24 min · 31 cues

    Sampling from an LM, Shannon's guessing game, temperature, overfitting and generalization, zero counts.

  5. Smoothing, Backoff, and Kneser-Ney (Appendix C)26 min · 32 cues

    Add-one, add-k, interpolation, backoff, stupid backoff, absolute discounting, Kneser–Ney continuation counts; Jelinek, Kneser & Ney history.

Exercises

ExerciseTierLadderTime
The chain rule of probability and the cost of the Markov bet browserPredict · Scratch45 min
Count tables (nested dict and trie) and the MLE n-gram model browserScratch · Harden · Compose75 min
Counting is learning: gradient descent on a bigram logit table converges to the counts browserPredict · Scratch · Probe a claim60 min
Port the bigram learner to PyTorch and match NumPy to 1e-9 gpuPort40 min
The shared perplexity module: cross-entropy, bases, zeros, bits per byte, and compressors browserScratch · Harden · Compose · Probe a claim60 min
Temperature sampling and Shannon's guessing game with character n-grams browserPredict · Scratch · Probe a claim60 min
Interpolated Kneser-Ney from scratch: continuation counts and absolute discounting browserScratch · Compose90 min
Break it: six ways to get a wrong perplexity (add-one, discounts, EM split, <s>/</s>, leakage, vocabulary) browserBreak it · Probe a claim90 min

Labs

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. Y. Bengio, R. Ducharme, P. Vincent, C. Jauvin, A Neural Probabilistic Language Model, JMLR 2003
  2. T. Brants, A. C. Popat, P. Xu, F. J. Och, J. Dean, Large Language Models in Machine Translation, EMNLP-CoNLL 2007 · link
  3. S. F. Chen & J. Goodman, An Empirical Study of Smoothing Techniques for Language Modeling, ACL 1996 · arXiv:cmp-lg/9606011
  4. S. F. Chen & J. Goodman, An Empirical Study of Smoothing Techniques for Language Modeling, Harvard TR-10-98, 1998 · link
  5. K. W. Church & W. A. Gale, A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams, Computer Speech and Language, 1991
  6. Zhang, Lipton, Li, Smola, Dive into Deep Learning, §9.3 Language Models (n-grams, Laplace smoothing, perplexity) and §22.11 Information Theory · link · §9.3, 22.11
  7. I. J. Good, The population frequencies of species and the estimation of population parameters, Biometrika 40:237-264, 1953
  8. Goodfellow, Bengio, Courville, Deep Learning, §3.13 Information Theory (entropy, KL, cross-entropy), §5.5 Maximum Likelihood Estimation · link · §3.13, 5.5
  9. K. Heafield, KenLM: Faster and Smaller Language Model Queries, WMT 2011 · link
  10. F. Jelinek & R. L. Mercer, Interpolated estimation of Markov source parameters from sparse data, Pattern Recognition in Practice, 1980
  11. 'Every time I fire a linguist, the performance ... goes up', attributed to F. Jelinek
  12. S. M. Katz, Estimation of probabilities from sparse data for the language model component of a speech recognizer, IEEE Trans. ASSP, 1987
  13. R. Kneser & H. Ney, Improved backing-off for M-gram language modeling, ICASSP 1995
  14. J. Kun, A Programmer's Introduction to Mathematics (style exemplar: 'mathematics has a culture' notes; definitions as API design)
  15. L. Lee, 'I'm sorry Dave, I'm afraid I can't do that': Linguistics, Statistics, and Natural Language Processing circa 2001 · arXiv:cs/0304027
  16. J. Liu, S. Min, L. Zettlemoyer, Y. Choi, H. Hajishirzi, Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens, 2024 · arXiv:2401.17377
  17. A. A. Markov (1913), statistical analysis of 20,000 letters of Pushkin's Eugene Onegin as a two-state (vowel/consonant) chain; English translation in Science in Context 19(4), 2006
  18. Experiments on predictability of word in context (ar5iv cs/0612136) · arXiv:cs/0612136
  19. Multimodal Shannon Game with Images · arXiv:2303.11192
  20. Isaac Newton, Opticks, 4th ed. (London, 1730); public domain; PGDP/Project Gutenberg transcription (file as shipped in Go's src/testdata)
  21. A. M. Sabatini, Markov reads Pushkin, again: A statistical journey into the poetic world of Evgenij Onegin · arXiv:2604.20221
  22. C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal 27:379-423, 1948
  23. C. E. Shannon, Prediction and Entropy of Printed English, Bell System Technical Journal 30:50-64, 1951
  24. Jurafsky & Martin, SLP3 draft (Aug 2026), Appendix C: Kneser-Ney Smoothing · link · §C
  25. Jurafsky & Martin, SLP3 draft (Aug 2026), Ch. 1 §1.6.1 (pretraining as a Shannon game), §1.9.2 (perplexity), p. 13 (Jelinek's group coined 'language model') · link · §1.6.1, 1.9.2
  26. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Ch. 3 N-gram Language Models · link · §3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, Historical Notes
  27. LLMs Unplugged: Teaching Resources for a ChatGPT World · arXiv:2609.13183
  28. S. Merity, C. Xiong, J. Bradbury, R. Socher, Pointer Sentinel Mixture Models (WikiText), 2016 · arXiv:1609.07843