Math Foundations — Lecture 7

Joint probability of a string, chain rule, Markov approximations, count-based MLE, Laplace smoothing, perplexity, neural LM softmax.

Joint probability of a string

A language model is a probability distribution over finite strings:

\[P(w_1, w_2, \dots, w_N) \in [0, 1], \qquad \sum_{w_{1..N}} P(w_{1..N}) = 1\]

From the joint we can compute conditionals, sample continuations, and rank candidate sentences.

Chain rule (exact factorisation)

\[P(w_1, w_2, \dots, w_N) = \prod_{i=1}^{N} P\bigl(w_i \mid w_1, \dots, w_{i-1}\bigr)\]

Exact for any joint distribution. The number of distinct histories \(w_1\dots w_{i-1}\) grows exponentially in length, so we cannot store all of them explicitly.

Markov approximation & n-gram models

Truncate the history to the last \(n-1\) tokens:

\[P\bigl(w_i \mid w_1, \dots, w_{i-1}\bigr) \;\approx\; P\bigl(w_i \mid w_{i-n+1}, \dots, w_{i-1}\bigr)\]

Special cases:

Unigram\(P(w_i)\) — no context.

Bigram\(P(w_i \mid w_{i-1})\) — last token only.

Trigram\(P(w_i \mid w_{i-2}, w_{i-1})\) — last two tokens.

Bigram approximation in full:

\[P(w_1, \dots, w_N) \;\approx\; \prod_{i=1}^{N} P(w_i \mid w_{i-1})\]

with \(w_0 = \langle s \rangle\) by convention.

Count-based maximum likelihood

For an n-gram model the MLE is the empirical conditional frequency:

\[\widehat{P}_\text{MLE}\!\left(w_i \mid w_{i-n+1}, \dots, w_{i-1}\right) \;=\; \frac{\text{Count}(w_{i-n+1}, \dots, w_i)}{\text{Count}(w_{i-n+1}, \dots, w_{i-1})}\]

For bigrams:

\[\widehat{P}(w_i \mid w_{i-1}) \;=\; \frac{\text{Count}(w_{i-1}, w_i)}{\sum_{w} \text{Count}(w_{i-1}, w)} \;=\; \frac{\text{Count}(w_{i-1}, w_i)}{\text{Count}(w_{i-1})}\]

Properties: unbiased on the training corpus, but assigns zero probability to any bigram unseen during training.

Laplace (add-1) and add-k smoothing

Laplace pretends each bigram was seen once before counting:

\[\widehat{P}_\text{Lap}(w_i \mid w_{i-1}) \;=\; \frac{\text{Count}(w_{i-1}, w_i) + 1}{\text{Count}(w_{i-1}) + |V|}\]

The \(+|V|\) in the denominator keeps the distribution normalised (one pseudocount for each of the \(|V|\) vocabulary items).

Add-k generalises with a smaller pseudocount \(k \in (0, 1]\) tuned on a validation set:

\[\widehat{P}_{k}(w_i \mid w_{i-1}) \;=\; \frac{\text{Count}(w_{i-1}, w_i) + k}{\text{Count}(w_{i-1}) + k\,|V|}\]

Kneser-Ney (intuition)

Two ideas: absolute discounting subtracts a constant \(d\) from each observed count, freeing mass for unseen events; continuation probability backs off using the number of distinct contexts a word appears in, not its raw frequency. Words appearing in many contexts (e.g. "York" in many bigrams) are better fallbacks than common but context-narrow words (e.g. "Francisco" mostly follows "San").

\[P_\text{cont}(w) \;\propto\; \bigl|\{ v : \text{Count}(v, w) > 0 \}\bigr|\]

Perplexity

Length-normalised inverse joint probability of a test sequence \(W = w_1\dots w_N\):

\[\text{PP}(W) \;=\; P(w_1, \dots, w_N)^{-1/N} \;=\; \sqrt[N]{\frac{1}{P(w_1, \dots, w_N)}}\]

Equivalently, the exponentiated per-token cross-entropy:

\[\text{PP}(W) \;=\; \exp\!\Bigl(-\tfrac{1}{N}\sum_{i=1}^{N} \log P\bigl(w_i \mid \text{history}\bigr)\Bigr) \;=\; \exp(H(W))\]

Lower bound\(\text{PP}(W) \geq 1\); equality only when the LM assigns probability 1 to the test sequence.

Intuition"effective branching factor" — uniform over \(K\) symbols gives \(\text{PP} = K\).

Caveat\(N\) is in the chosen tokenisation, so PP across different tokenisers is not directly comparable.

Quick Check: A bigram LM assigns probability \(\tfrac{1}{10}\) to each of two test tokens. The perplexity is:

\(10\)

\(100\)

\(0.01\)

\(2\)

Neural language model (feed-forward sketch)

Given a context window of \(n-1\) tokens, the neural LM computes a distribution over the vocabulary as follows.

Embedding lookup

\[\mathbf{e}_j \;=\; E\,\mathbf{1}_{w_j}, \qquad E \in \mathbb{R}^{d \times |V|}\]

Each context token is replaced by its column of the embedding matrix \(E\).

Hidden layer

\[\mathbf{h} \;=\; \tanh\!\bigl(W_h\,[\mathbf{e}_{i-n+1};\,\dots;\,\mathbf{e}_{i-1}] + \mathbf{b}_h\bigr)\]

Output (softmax over vocabulary)

\[P(w_i = v \mid \text{context}) \;=\; \frac{\exp\!\bigl(\mathbf{u}_v^\top \mathbf{h} + b_v\bigr)}{\sum_{v' \in V} \exp\!\bigl(\mathbf{u}_{v'}^\top \mathbf{h} + b_{v'}\bigr)}\]

Training objective

Maximise log-likelihood (equivalently, minimise cross-entropy per token):

\[\mathcal{L} \;=\; -\frac{1}{N}\sum_{i=1}^{N} \log P\bigl(w_i \mid w_{i-n+1}, \dots, w_{i-1}\bigr)\]

By construction the softmax output is positive and sums to 1, so the model never produces a zero — smoothing is built into the function class. RNN and Transformer LMs replace the hidden-layer construction but keep the same softmax-over-vocab output and cross-entropy objective.