Lecture 7: Models — Language Models

Definition

What is a language model?

• An LM assigns a probability \(P(w_1, w_2, \dots, w_N)\) to any string of tokens.
• From a joint, we can predict the next word: \(\arg\max_t P(w_1\dots w_N, t)\) — pick the continuation with the highest score.
• Example: \(P(\text{“We are at The University of Sydney”}) > P(\text{“We are at The University of chocolate”})\).
• The same probability supports completion, scoring candidates in translation/ASR, and generation by sampling.

RecallWhat is the single object an LM defines, and what task does it directly enable?

Approximation

N-gram language models & the Markov assumption

• Chain rule: \(P(w_{1..N}) = \prod_i P(w_i \mid w_{1..i-1})\) — exact but exponentially many contexts.
• Markov assumption: future is independent of the past given the present few tokens. With order \(n\), \(P(w_i \mid w_{1..i-1}) \approx P(w_i \mid w_{i-n+1..i-1})\).
• Unigram (\(n=1\)): \(P(w_i)\) — ignores context entirely.
• Bigram (\(n=2\)): \(P(w_i \mid w_{i-1})\) — only previous token matters.
• Trigram (\(n=3\)): \(P(w_i \mid w_{i-2}, w_{i-1})\); 4-gram extends further.
• Why not push \(n\) very high? Sparsity — long contexts rarely repeat; storage — table grows like \(|V|^n\).
• Strong: a bigram model assigns equal probability to permutations that share the same bigrams (cannot capture long-distance dependencies like coreference or agreement).

RecallWhy is increasing \(n\) not always better? Name the two failure modes.

Estimator

Count-based maximum likelihood

• Estimate each conditional by ratios of corpus counts: \(P(w_i \mid w_{i-1}) = \dfrac{\text{Count}(w_{i-1}, w_i)}{\sum_{w} \text{Count}(w_{i-1}, w)} = \dfrac{\text{Count}(w_{i-1}, w_i)}{\text{Count}(w_{i-1})}\).
• This is the MLE under a multinomial model — proportions match observed frequencies.
• Cheap to compute (one pass for counts), interpretable, no gradient descent needed.
• Fails brittlely on unseen events: if Count(bird opened) = 0 then \(P(\text{opened}\mid\text{bird}) = 0\), zeroing the whole joint. Worse, if Count(history) = 0 we get \(0/0\).

RecallWrite the bigram MLE in words and identify the two ways it can produce a problematic 0.

Boundaries

Sequence start, end, and log-probabilities

• The first token has no history — pad the left with <start> tokens (one for bigram, two for trigram, etc.) so the same conditional template applies.
• Add an explicit <end> token at the right so the model assigns probability mass to stopping; otherwise a model can prefer arbitrarily long strings.
• Multiplying many small probabilities underflows: with vocab 10⁵, mean next-word probability \(10^{-5}\), 100 tokens give \(10^{-500}\) — below smallest positive float (\(\approx 10^{-307}\)).
• Work in log-space: \(\log P(w_{1..N}) = \sum_i \log P(w_i \mid \text{history})\). Sums add cleanly; numbers stay bounded.

RecallTwo structural fixes for the ends of sequences, and one numerical fix during scoring.

Zero counts

Smoothing: Laplace, add-k, Kneser-Ney

• Laplace (add-1): \(P(w_i\mid w_{i-1}) = \dfrac{\text{Count}(w_{i-1}, w_i) + 1}{\text{Count}(w_{i-1}) + |V|}\). Pretend every bigram was seen once. Eliminates zeros; over-smooths frequent events.
• Add-k: same idea with a smaller pseudocount \(k < 1\) — tune on a validation set.
• Kneser-Ney (intuition): instead of "how often did w appear", ask "in how many different contexts did w appear?" — a word like "Francisco" appears often but in few contexts, so it should be a poor unigram fallback. KN combines absolute discounting with this continuation probability.
• All smoothing methods steal mass from observed events and redistribute it to unobserved ones; they differ in how.

RecallWrite add-1 smoothing for a bigram and explain in one sentence what Kneser-Ney measures that add-1 ignores.

Intrinsic metric

Perplexity

• Perplexity rescales the joint probability by sequence length so models can be compared on different test sets: \(\text{PP}(W) = P(w_1\dots w_N)^{-1/N} = \sqrt[N]{1/P(w_1\dots w_N)}\).
• Equivalently, \(\text{PP}(W) = \exp\bigl(-\tfrac{1}{N}\sum_i \log P(w_i\mid\text{history})\bigr) = \exp(\text{cross-entropy})\) — perplexity is the exponentiated per-token cross-entropy.
• Lower is better; minimum is \(1\) (perfect prediction); no upper limit.
• Intuition: "effective branching factor" — the LM behaves as if choosing uniformly among PP options at each step.
• Depends on tokenisation: \(N\) counts your tokens, so a model with smaller pieces is not directly comparable to one with larger pieces.
• Sanity check: uniform over a 10-symbol alphabet ⇒ PP = 10. A model that puts 50% on the true symbol and splits the rest does better.

RecallState perplexity two ways (probability and cross-entropy). Which direction is better — lower or higher?

From counts to vectors

Neural language models

• Replace the count table with a network that maps a context window into a distribution over the vocabulary.
• Pipeline: embedding lookup for each context token → concatenate or pool → one or more hidden layers → linear projection to \(|V|\) logits → softmax.
• Train by maximum likelihood: minimise cross-entropy of the next token (gradient descent, backpropagation).
• Generalises across unseen contexts because similar contexts share embeddings — no zero-count problem (smoothing built in by the smooth function class).
• Recurrent (RNN) and self-attention (Transformer) variants extend the context arbitrarily; large pretrained Transformers are today's dominant LMs.

RecallWalk a single token through a neural LM: which layer produces the distribution and via what nonlinearity?

Applications

Tasks framed as language modelling

• Completion / next-word: directly \(\arg\max_t P(t \mid \text{context})\) — keyboard suggest, search query completion.
• Translation: noisy-channel or seq2seq view — score \(P(\text{target} \mid \text{source})\); generation = beam search over target LM conditioned on source.
• Speech recognition / OCR: combine acoustic/visual model with LM to favour fluent transcripts.
• Spelling / grammar correction: rank candidates by their LM probability.
• Classification & QA via prompting: insert the input into a template ("Review: ... Sentiment: ____") and let an LM fill in the answer.
• Common thread: anywhere we need to score, rank, or generate text, an LM provides a prior over strings.

RecallGive the conditional probability that translation, speech recognition, and completion each maximise.

Lab

Workshop & materials

• chapters/chapter7/materials/lecture-7.pdf — full slide handout.
• Workshop note from the lecture: "Pre-work: none this week. In-class: spaCy." Bring a Python environment with spacy installed.

Quick practice

Tutorial

Worked problems