L3.3 · LESSON 3 OF 6

Smoothing

Build a smoothed bigram model and connect next-token probabilities to log loss and perplexity.

THE IDEA

Never say never

A pair that did not occur in the training text gets a count of zero, and so a probability of zero, even though it might be perfectly normal English. Additive smoothing fixes that by pretending every pair was seen α extra times:

P(next) = (count + α) / (total + α · V)

V is the vocabulary size, the number of possible next tokens. The same V must appear in the numerator's addition (one α per token) and in the denominator, otherwise the probabilities no longer add up to 1.

count of token 00count of token 12alpha1

use a vocabulary size of 3 in the denominator (a bug)

token	count	(count + α) / (total + α·V)	probability
0	0	(0 + 1) / (2 + 1·2)	0.25
1	2	(2 + 1) / (2 + 1·2)	0.75

probabilities add up to 1

Counts [0, 2] with add-one smoothing. Tick the box to see what a mismatched vocabulary size does.

Predict first. With counts [0, 2], add-one smoothing gives which probabilities?

Chapter context

A causal language model predicts the next token from the allowed prefix. A bigram model is a transparent starting point: it uses only the immediately preceding token, making counts, uncertainty and sampling easy to inspect.

TRY IT YOURSELF

Part 1. Do it hands-on

Compute smoothed probabilities and expose the vocabulary-size bug, then implement smoothing in Python.

count of token 00count of token 12alpha1

use a vocabulary size of 3 in the denominator (a bug)

token	count	(count + α) / (total + α·V)	probability
0	0	(0 + 1) / (2 + 1·2)	0.25
1	2	(2 + 1) / (2 + 1·2)	0.75

probabilities add up to 1

P(first token), α = 1 P(first token), α = 0.5 (3 decimals) sum with the buggy denominator

To do: Counts [0, 2] over a vocabulary of 2. Add-one smoothing: (count + 1) / (total + 2). Type the probability of the first (never seen) token
To do: Same counts but add 0.5 instead of 1: (count + 0.5) / (total + 0.5·2). Type the probability of the first token (3 decimals)
To do: A bug: the numerators add 1 for 2 tokens but the denominator was computed for a vocabulary of 3 (total + 3). Counts [0, 2]: what do the two probabilities add up to?

Part 2. Do it in code

smooth_row(counts, alpha=1.0): additive smoothing of one row of counts: (c + alpha) / (sum(counts) + alpha * len(counts)). alpha must be >= 0 (ValueError). If alpha is 0 and the row is all zeros raise ValueError.
smooth_matrix(C, alpha=1.0): smooth every row of a count matrix.
rows_sum_to_one(P, tol=1e-9): True if every row of P sums to 1 within tol.
buggy_smooth_row(counts, alpha, vocab_size): the same formula but with a given vocabulary size in the denominator (alpha * vocab_size). It is correct only if vocab_size equals len(counts).

import numpy as np

def smooth_row(counts, alpha=1.0):
    pass

def smooth_matrix(C, alpha=1.0):
    pass

def rows_sum_to_one(P, tol=1e-9):
    pass

def buggy_smooth_row(counts, alpha, vocab_size):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

With counts [0,2], add-one smoothing gives which probabilities?

A[0, 1], because unseen tokens stay impossible.B[1/3, 2/3], because only one count is added in total.C[1/4, 3/4], because (0+1)/(2+2) and (2+1)/(2+2) share one denominator that includes an extra count for each token.

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

P(y\mid x)=\frac{C(x,y)+\alpha}{\sum_j C(x,j)+\alpha V},\quad \operatorname{NLL}=-\frac1N\sum_t\log P(x_{t+1}\mid x_t).

V is the output vocabulary size and alpha is a nonnegative smoothing amount. Perplexity is exp(NLL) for natural-log loss.

Worked example

For ababa, a→b occurs twice and b→a occurs twice. With vocabulary {a,b} and alpha=1, P(b|a)=(2+1)/(2+2)=0.75. An alternating transition then incurs −ln(0.75)≈0.287682 nats, whose perplexity is 4/3.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import log,exp,isclose
seq='ababa'
count=sum(a=='a' and b=='b' for a,b in zip(seq,seq[1:]))
assert count == 2
prob=(count+1)/(2+2)
assert prob == .75
assert isclose(-log(prob),.2876820724517809)
assert isclose(exp(-log(prob)),4/3)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Predicting the input token itself can create target leakage. Bigram counts depend on token boundaries. Perplexities across incompatible tokenizers are not directly comparable.