ICS 582Lecture 03Reference

Reference sheet

N-gram language models compressed onto one page: the definitions, formulas and numbers to have in your head before a quiz or exam.

What a language model is

A language model gives a probability distribution over the next word given a history, which by the chain rule is also a probability for every whole sentence. In applications another component proposes candidates and the LM ranks them by fluency. Part 01: Why predict words

\begin{gathered} P(w_t \mid w_{<t}) \ \text{for every } w_t \in V, \\ \sum_{w \in V} P(w \mid h) = 1 \end{gathered}

One history, one distribution over the whole vocabulary

\hat{S} = \arg\max_{S}\ \Pr(S)\, \Pr(T \mid S)

Noisy channel for MT (Brown et al. 1990): language model times translation model

Application	Candidates from	LM decides	Example
Spelling correction	Variants of the typed words	Which variant gives the more probable sentence	Their are two midterms
Speech recognition	The acoustic model	Which sound-alike transcription is fluent	back soonish / bassoon dish
Machine translation	The translation model	Which faithful candidate is well formed	Pr(S) Pr(T\|S)
AAC and keyboards	The vocabulary or the partial word	The top-k menu, ranked by probability	The quick bro → brown

Candidates from elsewhere, ranking from the LM

Aspect	Count-based (n-gram)	Neural
How P(w \| h) is estimated	Relative frequency of the exact n-gram, then smoothed	A learned function of continuous word vectors
Parameters	One per observed n-gram; the table grows as \|V\|^n	Fixed by network size, shared across contexts
Generalization	Only across identical word sequences	Across similar words: cat transfers to dog
Context	1 to 4 previous words in practice	Hundreds to many thousands of tokens
Gboard 2018	5-gram FST, 13.0% top-1 recall	CIFG RNN, 16.4% top-1 recall

Count-based against neural language models

Chain rule and the Markov assumption

Counting P(w | h) directly fails because histories grow as V^k. The chain rule is exact; the Markov assumption keeps only the last N - 1 words. Part 02: Chain rule and Markov

P(w_{1:n}) = \prod_{k=1}^{n} P(w_k \mid w_{1:k-1})

Chain rule (SLP3 Eq. 3.4), exact

P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-N+1:n-1})

Markov assumption for an N-gram model (SLP3 Eq. 3.8)

\begin{gathered} P(w_{1:n}) \approx \prod_{k=1}^{n} P(w_k \mid w_{k-1}), \\ w_0 = \langle s\rangle,\ \text{plus } P(\langle /s\rangle \mid w_n) \end{gathered}

Bigram sentence probability (SLP3 Eq. 3.9)

Order	Context words	Factor	Possible contexts	Captures
Unigram	0	P(w_k)	1	Frequency only, a bag of words
Bigram	1	P(w_k \| w_(k-1))	10^4	Local syntax between neighbours
Trigram	2	P(w_k \| w_(k-2), w_(k-1))	10^8	Short phrases read fluently

Model order against context and possible contexts (V = 10^4)

A sentence of L tokens has L - n + 1 n-grams of order n.
A trigram pads with <s> <s>; order N pads with N - 1 start tokens.
</s> turns one distribution per sentence length into one distribution over all sentences.
Markov's 1913 Onegin study (20,000 letters) was the first bigram model.

Maximum likelihood estimation

Count, then normalize by the history count so each conditional row sums to 1. Dividing by the total number of bigrams would give a joint probability instead. Part 03: MLE estimation

P(w_n \mid w_{n-1}) = \frac{C(w_{n-1}\, w_n)}{C(w_{n-1})}

Bigram MLE (SLP3 Eq. 3.11)

\begin{aligned} &P(w_n \mid w_{n-N+1:n-1}) \\ &\quad = \frac{C(w_{n-N+1:n-1}\; w_n)}{C(w_{n-N+1:n-1})} \end{aligned}

General N-gram MLE (SLP3 Eq. 3.12): the n-gram over its N - 1 word prefix

p_1 \times p_2 \times \cdots \times p_k = \exp\Big(\sum_i \log p_i\Big)

Work in log space to avoid underflow (SLP3 Eq. 3.13)

History	C(history)	MLE estimates
<s>	3	P(I \| <s>) = 2/3, P(Sam \| <s>) = 1/3
I	3	P(am \| I) = 2/3, P(do \| I) = 1/3
am	2	P(Sam \| am) = 1/2, P(</s> \| am) = 1/2
Sam	2	P(</s> \| Sam) = 1/2, P(I \| Sam) = 1/2

I am Sam toy corpus, one row per history

Estimate	Bigram count	Row word count	Probability
P(want \| i)	827	2533	0.33
P(to \| want)	608	927	0.66
P(eat \| to)	686	2417	0.28
P(food \| chinese)	82	158	0.52
P(lunch \| eat)	42	746	0.056
P(i \| want)	2	927	0.0022

BeRP (9332 sentences, V = 1446): count over row count

Worked results

I am Sam: P(<s> I am Sam </s>) = 2/3 × 2/3 × 1/2 × 1/2 = 1/9
Trigram: P(Sam | I am) = 1/2, P(do | <s> I) = 1/2
BeRP sentence: P(<s> i want english food </s>) = 0.25 × 0.33 × 0.0011 × 0.5 × 0.68 ≈ 0.000031
In logs: ln P = -10.386, log10 P = -4.511, log2 P = -14.984
Sparsity: 32 of 64 cells in the hand-picked BeRP slice are zero
Underflow: 0.1^400 prints 0.0; the smallest normal double is 2.2 x 10^-308

Evaluation and perplexity

Training set counts, dev set tunes, test set is run once. Perplexity is the inverse test probability normalized by length: lower is better. Part 04: Perplexity

\begin{aligned} \mathrm{PP}(W) &= P(w_1 \ldots w_N)^{-\frac{1}{N}} \\ &= \sqrt[N]{\prod_{i=1}^{N} \frac{1}{P(w_i \mid w_1 \ldots w_{i-1})}} \end{aligned}

Perplexity: geometric mean of inverse next-word probabilities

\mathrm{PP}(W) = 2^{-\frac{1}{N}\sum_{i=1}^{N} \log_2 P(w_i \mid w_1 \ldots w_{i-1})}

The same in log space; one zero makes PP infinite

	Extrinsic	Intrinsic
What is measured	The whole application with the LM plugged in	The LM alone, on held-out text
Metric	WER for ASR, BLEU or COMET for MT	Perplexity
Cost	A full end-to-end run per candidate	One pass over the test set
Use	Final decisions and claimed gains	Fast iteration over many variants

Extrinsic against intrinsic evaluation

Model	Previous words	Test perplexity
Unigram	0	962
Bigram	1	170
Trigram	2	109

WSJ, 38M training and 1.5M test words

Model	Test set	P(T)	Perplexity
A: uniform, 1/3 each	any 5 words	(1/3)^5 ≈ 0.0041	3
B: red 0.8, blue 0.1, green 0.1	red red red red blue	0.8^4 × 0.1 = 0.04096	≈ 1.89
B: red 0.8, blue 0.1, green 0.1	blue blue blue blue blue	0.1^5 = 0.00001	10

Perplexity as weighted branching factor: the 3-color language

Sampling

Sampling draws sentences in proportion to their probability: a window into what the model learned, not a metric. Part 05: Sampling

\begin{gathered} w = w_k \ \text{such that } \\ F(w_{k-1}) \le u < F(w_k), \\ F(w_k) = \sum_{j \le k} P(w_j),\ u \sim \mathcal{U}[0,1) \end{gathered}

Unigram sampling by cumulative intervals

\begin{gathered} w_i \sim P(w_i \mid w_{i-N+1:i-1}), \\ \text{start at } \langle s\rangle,\ \text{stop when } w_i = \langle /s\rangle \end{gathered}

The n-gram sampling loop; the sentence probability is the product of the drawn conditionals

	Greedy	Sampling
Choice rule	argmax P(w \| context)	w ~ P(w \| context)
Deterministic	Yes: same context, same word	No: each run draws a fresh u
Failure mode	Bland, loops and repetition	Occasional nonsense from the tail
Use	Closed tasks with one right answer	Open generation and diagnosing a model

Greedy decoding against random sampling

Order	What it shows
Unigram	Real words, no order at all
Bigram	Each adjacent pair plausible, the sentence goes nowhere
Trigram	Phrases hold for three or four words
4-gram	Fluent because copied: It cannot be but so is from King John

What Shakespeare samples show by order (SLP3 Fig. 3.4)

Slide 44: 0.66 and 0.99 are cumulative positions, not probabilities.
Interval width is the probability: with ticks 0.06, 0.09, 0.11, u = 0.10 emits "a" (width 0.02).
After deep learning the walkthrough draws "," (0.05) over models (0.06): sampling is not argmax.
The context is a sliding window: the oldest word leaves the context but stays in the output.

Generalization, zeros and add-k

Higher order fits training data better and copies it on small corpora; models encode their genre. One unseen n-gram makes the test probability zero and perplexity undefined. Part 06: Generalization and zeros

P_{\text{Laplace}}(w_i) = \frac{c_i + 1}{N + V}

Add-one unigram

P_{\text{Laplace}}(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n) + 1}{C(w_{n-1}) + V}

Add-one bigram

\begin{aligned} &C^*(w_{n-1} w_n) \\ &\quad = \frac{\left[C(w_{n-1} w_n) + 1\right] C(w_{n-1})}{C(w_{n-1}) + V}, \\ &d_c = \frac{C^*}{C} \end{aligned}

Reconstituted count and discount ratio d_c (not the subtracted d of absolute discounting)

P_{\text{Add-}k}(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n) + k}{C(w_{n-1}) + kV}

Add-k: k = 1 is Laplace, k → 0 is the MLE; tune k on dev data

Bigram	C	C(prefix)	MLE	Add-one P	C*	d_c = C*/C
i want	827	2533	0.33	828 / 3979 ≈ 0.21	527	0.64
want to	608	927	0.66	609 / 2373 ≈ 0.26	238	0.39
chinese food	82	158	0.52	83 / 1604 ≈ 0.052	8.2	0.10
i to (unseen)	0	2533	0	1 / 3979 ≈ 0.00025	0.64	n/a

Add-one on BeRP (V = 1446)

k	P(food \| chinese)	P(to \| want)
1	0.0517	0.2566
0.5	0.0936	0.3688
0.1	0.2713	0.5675
0.01	0.4755	0.6458
0 (MLE)	0.519	0.656

Add-k on BeRP

Interpolation, backoff and absolute discounting

Interpolation always mixes every order; backoff uses the highest order with a nonzero count. All weights are hyperparameters tuned on held-out data. Part 07: Interpolation, backoff and discounting

\begin{aligned} &\hat{P}(w_n \mid w_{n-2} w_{n-1}) \\ &\quad = \lambda_1 P(w_n) + \lambda_2 P(w_n \mid w_{n-1}) \\ &\quad + \lambda_3 P(w_n \mid w_{n-2} w_{n-1}), \\ &\sum_i \lambda_i = 1 \end{aligned}

Linear interpolation; λ may depend on the context

\begin{gathered} S(w_i \mid w_{i-k+1}^{i-1}) = \begin{cases} \dfrac{f(w_{i-k+1}^{i})}{f(w_{i-k+1}^{i-1})} & \text{if } f(w_{i-k+1}^{i}) > 0 \\[2mm] 0.4\, S(w_i \mid w_{i-k+2}^{i-1}) & \text{otherwise} \end{cases} \\ S(w_i) = \frac{f(w_i)}{N} \end{gathered}

Stupid backoff (Brants et al. 2007): scores, not probabilities

\begin{aligned} &P_{\text{AD}}(w_i \mid w_{i-1}) \\ &\quad = \frac{\max\big(C(w_{i-1} w_i) - d,\ 0\big)}{C(w_{i-1})} \\ &\quad + \lambda(w_{i-1})\, P(w_i), \\ &\lambda(w_{i-1}) = \frac{d\, \big|\{w : C(w_{i-1} w) > 0\}\big|}{C(w_{i-1})} \end{aligned}

Interpolated absolute discounting

d = \frac{n_1}{n_1 + 2\, n_2} \quad (\text{or } d \approx 0.75)

Discount from counts of counts

	Interpolation	Katz backoff	Stupid backoff
Lower orders used	Always, for every word	Only when the full n-gram count is 0	Only when the full n-gram count is 0
Discount on seen n-grams	Implicit, through the λ weights	Yes, P* frees mass	None
True distribution	Yes, because Σλ = 1	Yes, with the normalizing α	No, it returns scores
Weight	Tuned λ, can depend on context	α(context) from freed mass	Fixed 0.4 per step

Three ways to use lower orders

λ = (λ1, λ2, λ3)	Token probabilities	Perplexity
(0.1, 0.3, 0.6)	0.157, 0.392, 0.2705	3.92
(0.6, 0.3, 0.1)	0.162, 0.152, 0.073	8.22
(0, 0, 1)	0, 0.50, 0.40	∞

Choosing λ on dev tokens: the first setting wins

Training count c	Held-out average	c minus held-out
1	0.448	0.552
2	1.25	0.75
3	2.24	0.76
4	3.23	0.77
5	4.21	0.79
9	8.26	0.74

Church and Gale: 22M AP training words, 22M held-out

Worked results

Interpolation: P(food | want chinese) = 0.1 × 0.01 + 0.3 × 0.52 + 0.6 × 0 = 0.157
Stupid backoff: S(floor | quietly on the) = 0.4 × 0.4 × 3/60 = 0.008
To the base case: 0.4³ × 5 / 10,000 = 0.000032
P_AD seen: P_AD(food | chinese) = 0.525 + 0.225 × 0.02 = 0.5295
P_AD unseen: P_AD(tea | chinese) = 0.225 × 0.001 = 0.000225
Lambda check: λ(chinese) = 0.75 × 3 / 10 = 0.225 = 1 − 0.775

Kneser-Ney for bigrams

Backing off to raw frequency asks how often a word occurs; Kneser-Ney asks how many different words it follows. Part 08: Kneser-Ney bigrams

\begin{aligned} P_{\text{cont}}(w) &= \frac{\big|\{ v : C(v\,w) > 0 \}\big|}{\big|\{ (u, w') : C(u\,w') > 0 \}\big|} \\ &= \frac{N_{1+}(\bullet\, w)}{\sum_{w'} N_{1+}(\bullet\, w')} \end{aligned}

Continuation probability: distinct left contexts over bigram types

\begin{aligned} &P_{\text{KN}}(w_i \mid w_{i-1}) \\ &\quad = \frac{\max\big(C(w_{i-1} w_i) - d,\ 0\big)}{C(w_{i-1})} \\ &\quad + \lambda(w_{i-1})\, P_{\text{cont}}(w_i) \end{aligned}

Interpolated Kneser-Ney bigram

\lambda(w_{i-1}) = \frac{d}{C(w_{i-1})}\, N_{1+}(w_{i-1}\, \bullet)

Exactly the mass removed by discounting, so each row sums to 1

Word	Tokens	Left contexts	Raw P(w)	P_cont(w)
Kong	30	Hong	30 / 34 ≈ 0.882	1 / 5 = 0.2
glasses	4	reading, sun, safety, my	4 / 34 ≈ 0.118	4 / 5 = 0.8

Toy corpus: Hong Kong 30, and reading, sun, safety, my glasses 1 each

History	Word	Frequency backoff	Kneser-Ney
reading	Kong	0.662	0.15
reading	glasses	0.338	0.85
Hong	Kong	0.997	0.98
Hong	glasses	0.003	0.02

Frequency backoff against Kneser-Ney, d = 0.75

Continuation: P_cont(Kong) = 1/5, P_cont(glasses) = 4/5.
Weight: λ(reading) = 0.75 / 1 × 1 = 0.75; λ(Hong) = 0.75 / 30 = 0.025.
Seen: P_KN(glasses | reading) = (1 − 0.75)/1 + 0.75 × 0.8 = 0.85.
Unseen: P_KN(Kong | reading) = 0 + 0.75 × 0.2 = 0.15; check 0.85 + 0.15 = 1.

General and modified Kneser-Ney

The recursion interpolates every order down to a uniform floor, using raw counts only at the top order and continuation counts below. Part 09: General Kneser-Ney

\begin{aligned} &P_{KN}(w_i \mid w_{i-n+1:i-1}) \\ &\quad = \frac{\max\big(c_{KN}(w_{i-n+1:i}) - d,\ 0\big)}{\sum_v c_{KN}(w_{i-n+1:i-1}\, v)} \\ &\quad + \lambda(w_{i-n+1:i-1})\, P_{KN}(w_i \mid w_{i-n+2:i-1}) \end{aligned}

Recursive interpolated Kneser-Ney

c_{KN}(\cdot) = \begin{cases} \text{count}(\cdot) & \text{highest order} \\ \text{continuationcount}(\cdot) & \text{lower orders} \end{cases}

N-grams that start with <s> keep raw counts

\begin{aligned} P_{KN}(w) &= \frac{\max\big(c_{KN}(w) - d,\ 0\big)}{\sum_{w'} c_{KN}(w')} \\ &\quad + \lambda(\epsilon)\, \frac{1}{V} \end{aligned}

Base case: unigram interpolated with uniform; <UNK> gets λ(ε)/V

\begin{gathered} Y = \frac{n_1}{n_1 + 2 n_2} \qquad D_1 = 1 - 2Y\frac{n_2}{n_1} \\ D_2 = 2 - 3Y\frac{n_3}{n_2} \qquad D_{3+} = 3 - 4Y\frac{n_4}{n_3} \end{gathered}

Modified Kneser-Ney discounts, per order (D1 always equals Y)

\gamma(h) = \frac{\begin{gathered} D_1 N_1(h\bullet) + D_2 N_2(h\bullet) \\ + D_{3+} N_{3+}(h\bullet) \end{gathered}}{\sum_w c(h\, w)}

Reserved mass for history h under modified KN

N-gram	Level	Raw	c_KN	Left neighbours
reading glasses	bigram	3	2	her, his
glasses	unigram	4	2	reading, sun
hong	unigram	3	2	visited, loves
kong	unigram	3	1	hong
she	unigram	4	0	none, always first

Raw count against c_KN (toy corpus, V = 13)

Level	Weight	P(glasses)	P(kong)
Unigram	λ(ε) = 0.75 × 11 / 15 = 0.55	1.25 / 15 + 0.55 / 13 = 0.1256	0.0590
Bigram, reading	λ = 0.75 × 1 / 2 = 0.375	0.625 + 0.375 × 0.1256 = 0.6721	0.0221
Trigram, her reading	λ = 0.375	0.625 + 0.375 × 0.6721 = 0.8770	0.0083

P_KN(glasses | her reading), d = 0.75 at every level

Aspect	Kneser-Ney	Modified KN
Discounts per order	1 (d)	3 (D1, D2, D3+)
Estimate	d = n1 / (n1 + 2 n2)	Dk = k − (k+1) Y n(k+1) / n(k)
Reserved mass for h	d · N1+(h•) / Σ c(hw)	(D1 N1 + D2 N2 + D3+ N3+) / Σ c(hw)
SRILM	-ukndiscount	-kndiscount
KenLM	Not offered	lmplz (default)

Kneser-Ney against modified Kneser-Ney

Worked discounts and toolkits

Counts of counts: n1 = 1000, n2 = 300, n3 = 150, n4 = 90
Discounts: Y = 0.625, D1 = 0.625, D2 = 1.0625, D3+ = 1.5
Reserved mass: Counts 1, 1, 2, 5: γ = 3.8125 / 9 = 0.4236, against 0.333 with one d = 0.75
KenLM: lmplz -o 5 <text >model.arpa
SRILM: ngram-count -order 5 -kndiscount -interpolate
Neural gain: Bengio et al. 2003: about 24% lower perplexity on Brown, 8% on AP News

Entropy, cross-entropy and the chapter

Entropy is average surprise in bits; cross-entropy of a model is never below the true entropy, and perplexity is two to the per-word cross-entropy. Part 10: Entropy and summary

H(X) = -\sum_x p(x)\log_2 p(x)

Entropy in bits (Shannon 1948)

\begin{aligned} H(p) \le H(p,m) &= -\sum_x p(x)\log_2 m(x) \\ &= H(p) + D_{\mathrm{KL}}(p \,\|\, m) \end{aligned}

Cross-entropy; the gap is the KL divergence

\begin{gathered} H(W) = -\tfrac{1}{N}\log_2 P(w_1\ldots w_N), \\ \mathrm{PP}(W) = 2^{H(W)} = P(w_1\ldots w_N)^{-1/N} \end{gathered}

Per-word cross-entropy and its link to perplexity

Distribution	H (bits)	2^H
Fair coin	1	2
8 uniform horses	3	8
Skewed horses (1/2, 1/4, 1/8, 1/16, 1/64 x4)	2	4
3 uniform colors	1.585	3
0.8/0.1/0.1 colors	0.922	1.89

Entropy and 2^H

Model m	H(p, m) bits	KL gap	Perplexity
Uniform (1/3, 1/3, 1/3)	1.585	0.663	3
(0.6, 0.2, 0.2)	1.054	0.132	2.08
(0.9, 0.05, 0.05)	0.986	0.064	1.98
m = p (0.8, 0.1, 0.1)	0.922	0	1.89

Cross-entropy against true p = (0.8, 0.1, 0.1)

Unit	Log base	Perplexity	Where
Bits	2	PP = 2^H	Textbooks, compression, Shannon
Nats	e	PP = e^H	Training loss in neural LM code
Conversion		1 nat = 1.4427 bits	H bits = H nats / ln 2

Bits against nats

Problem	Fix	Part
Full history is intractable	Markov assumption	Part 02
Probabilities are unknown	MLE from counts	Part 03
Need to judge models	Perplexity on test, tuning on dev	Part 04
Need to see what was learned	Sampling	Part 05
Unseen n-grams get zero	Add-k, interpolation, backoff	Parts 06 and 07
Unigram backoff overrates Kong	Continuation probability	Part 08
One discount misfits counts 1, 2, 3+	Modified KN with D1, D2, D3+	Part 09

The chapter as problems and fixes

Slide errata

Mistakes on the original slides

Slide 13: The Key idea box says the window is the last n - 1 words, but its formula uses n for the position and N for the order. The window is the last N - 1 words. Part 02
Slide 19: Title renders as "extitI am Sam" from a broken \textit; it should read "Toy corpus: I am Sam". Part 03
Slides 46 to 53: Titled "Bigram example", but from slide 48 the model conditions on two words (deep learning, then learning ,), which is trigram sampling. Part 05
Slide 55: Titled "Shakespeare vs WSJ sampling" but shows only Shakespeare; the WSJ samples are on the next slide. Part 06
Slide 73: Titled Stupid backoff, but the substitutions carry no 0.4 factor and no Katz α: it is generic backoff intuition. Backoff fires on a zero n-gram count, not an unseen context. Part 07
Slide 74: The recursion has no base case. Brants et al. end it with S(w_i) = count(w_i) / N, and the slide's λ ≈ 0.4 is their fixed α = 0.4. Part 07
Slide 79: The numerator needs max(C − d, 0) or unseen bigrams go negative, and λ(w_(i-1)) is never defined: it equals d · |{w : C(w_(i-1) w) > 0}| / C(w_(i-1)). Part 07
Slide 83: Lists "sunglasses" as a left context of glasses; the corpus has C(sun glasses) = 1, so the context is sun. Part 08
Slide 84: Title renders as P_extcont from a broken \text; it should read P_cont. The formula itself is correct. Part 08
Slide 95: Says "back off" but the formula interpolates at every level, and the chain ends at uniform 1/V, not the unigram. λ is left undefined. Part 09
Slide 103: Gives PP(W) = 2^H(W) without defining H(W): it is the model's per-word cross-entropy, -(1/N) log2 P(w1...wN), not the true entropy of W. Part 10