L3.6 · LESSON 6 OF 6

Beyond bigrams

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

THE IDEA

Longer contexts

A bigram looks one token back, so two different histories that end in the same token look identical to it. Conditioning on more of the prefix (a trigram uses two tokens, an n-gram n − 1) separates them. The cost is that the number of possible contexts grows exponentially with the length, so most never appear in the training data. Neural language models condition on long prefixes without a table, which is the road the rest of this track takes.

Training text: c a x d a y. After the token "a" the model must predict x or y. Choose the text before it:

text so far:

model	looks at	P(x)	P(y)
bigram	only "a"	0.5	0.5
trigram	"c a"	1	0

The bigram cannot tell "c a" from "d a": both prefixes end in the same token. A longer context separates them, at a price:

vocabulary size V10

table entries: bigram V² = 100, trigram V³ = 1000, 4-gram V⁴ = 10000 most long contexts never appear in the training text, so those entries are never seen

After the token "a", which comes next, x or y? It depends on what came before.

Predict first. Does a bigram model distinguish two prefixes that end in the same token?

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

Compare a bigram and a trigram on a text where context matters, and count how fast the tables grow. Then build n-gram counts and perplexity in Python.

Training text: c a x d a y. After the token "a" the model must predict x or y. Choose the text before it:

text so far:

model	looks at	P(x)	P(y)
bigram	only "a"	0.5	0.5
trigram	"c a"	1	0

The bigram cannot tell "c a" from "d a": both prefixes end in the same token. A longer context separates them, at a price:

vocabulary size V10

table entries: bigram V² = 100, trigram V³ = 1000, 4-gram V⁴ = 10000 most long contexts never appear in the training text, so those entries are never seen

bigram P(x | a) trigram P(x | c a) trigram table entries for V = 10

To do: Training text: c a x d a y. After "a" the next token was x once and y once. Bigram P(x | a), unsmoothed
To do: A trigram model uses the two previous tokens. In the same text, after "c a" the next token was x. Trigram P(x | c a)
To do: With a vocabulary of 10 tokens, how many probability entries does a full trigram table need (10 × 10 contexts, each with 10 next-token entries)?

Part 2. Do it in code

count_ngrams(tokens, n): a dict mapping a context (tuple of the n−1 previous tokens) to a dict {next_token: count}. n must be at least 2 (ValueError).
ngram_prob(table, context, token, alpha, V): (count + alpha) / (total for that context + alpha*V). An unseen context has total 0.
perplexity_ngram(train, test, n, alpha, V): build the table from train and return the perplexity of the test text (exp of the average −ln probability over every position that has n−1 tokens of context).
table_size(V, n): the number of probabilities a full n-gram table needs: V ** n.

def count_ngrams(tokens, n):
    pass

def ngram_prob(table, context, token, alpha, V):
    pass

def perplexity_ngram(train, test, n, alpha, V):
    pass

def table_size(V, n):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Does a bigram model distinguish two prefixes ending in the same token?

AYesBNo

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.