Step 1 — A Bigram Model from Counts

Released with Lecture 1 · Prerequisites: Setup complete · Solution: notebook · read online

In what follows, there are blocks of code provided for you. Please read these with the help of Gemini in colab.

Goal

Build the simplest possible language model, namely a bigram model $p(x_{t+1} \mid x_t)$ estimated by counting character pairs in the corpus. Sample text from it, and measure its quality with average log loss (cross-entropy) in nats per character, in bits per character, and with perplexity. These are three reports of the same underlying score. You will measure it twice: first on the text the model was fit on, then on a held-out 10% the counts never saw.

Concept Review

1. Let $V$ be a finite alphabet and suppose we model a text $x_1,\dots,x_T$ by a Markov chain: $p(x_1,\dots,x_T) = p(x_1)\prod_{t=1}^{T-1} p(x_{t+1}\mid x_t)$, with parameters $\theta_{ab} = p(b \mid a)$. Show that the maximum likelihood estimator for a given text is the count ratio $\hat\theta_{ab} = N_{ab} / \sum_{c} N_{ac}$, where $N_{ab}$ is the number of times character $b$ follows character $a$ in the text.
2. The model’s average log loss on the text is $\mathcal L = -\frac{1}{T-1}\sum_{t=1}^{T-1} \log p(x_{t+1}\mid x_t)$. This is the empirical cross-entropy, measured in nats. Divide by $\ln 2$ for bits per character; perplexity is $e^{\mathcal L}$. Show that perplexity is $|V|$ exactly when the model is uniform (Lecture 1’s Proposition 4.2).

Tasks

1.1 Load the data

If on Colab, download the data file first by entering the following into a cell: !wget -q https://raw.githubusercontent.com/karpathy/char-rnn/master/data/tinyshakespeare/input.txt

with open('input.txt', 'r') as f:   # open the downloaded file for reading, temporarily named f
    text = f.read()                 # read the whole file into one big string
print(len(text))        # how many characters long the text is: 1,115,394
print(text[:250])       # show the first 250 characters, as a sanity check

Here’s a preview of text[1106534:1114665]:

ALONSO:
Prithee, peace.

SEBASTIAN:
He receives comfort like cold porridge.

ANTONIO:
The visitor will not give him o'er so.

SEBASTIAN:
Look he's winding up the watch of his wit;
by and by it will strike.

GONZALO:
Sir,--

SEBASTIAN:
One: tell.

GONZALO:
When every grief is entertain'd that's offer'd,
Comes to the entertainer--

SEBASTIAN:
A dollar.

GONZALO:
Dolour comes to him, indeed: you
have spoken truer than you purposed.

SEBASTIAN:
You have taken it wiselier than I meant you should.

GONZALO:
Therefore, my lord,--

ANTONIO:
Fie, what a spendthrift is he of his tongue!

ALONSO:
I prithee, spare.

GONZALO:
Well, I have done: but yet,--

SEBASTIAN:
He will be talking.

ANTONIO:
Which, of he or Adrian, for a good
wager, first begins to crow?

SEBASTIAN:
The old cock.

ANTONIO:
The cockerel.

SEBASTIAN:
Done. The wager?

ANTONIO:
A laughter.

SEBASTIAN:
A match!

ADRIAN:
Though this island seem to be desert,--

SEBASTIAN:
Ha, ha, ha! So, you're paid.

ADRIAN:
Uninhabitable and almost inaccessible,--

SEBASTIAN:
Yet,--

ADRIAN:
Yet,--

ANTONIO:
He could not miss't.

ADRIAN:
It must needs be of subtle, tender and delicate
temperance.

ANTONIO:
Temperance was a delicate wench.

SEBASTIAN:
Ay, and a subtle; as he most learnedly delivered.

ADRIAN:
The air breathes upon us here most sweetly.

SEBASTIAN:
As if it had lungs and rotten ones.

ANTONIO:
Or as 'twere perfumed by a fen.

GONZALO:
Here is everything advantageous to life.

ANTONIO:
True; save means to live.

SEBASTIAN:
Of that there's none, or little.

GONZALO:
How lush and lusty the grass looks! how green!

ANTONIO:
The ground indeed is tawny.

SEBASTIAN:
With an eye of green in't.

ANTONIO:
He misses not much.

SEBASTIAN:
No; he doth but mistake the truth totally.

GONZALO:
But the rarity of it is,--which is indeed almost
beyond credit,--

SEBASTIAN:
As many vouched rarities are.

GONZALO:
That our garments, being, as they were, drenched in
the sea, hold notwithstanding their freshness and
glosses, being rather new-dyed than stained with
salt water.

ANTONIO:
If but one of his pockets could speak, would it not
say he lies?

SEBASTIAN:
Ay, or very falsely pocket up his report

GONZALO:
Methinks our garments are now as fresh as when we
put them on first in Afric, at the marriage of
the king's fair daughter Claribel to the King of Tunis.

SEBASTIAN:
'Twas a sweet marriage, and we prosper well in our return.

ADRIAN:
Tunis was never graced before with such a paragon to
their queen.

GONZALO:
Not since widow Dido's time.

ANTONIO:
Widow! a pox o' that! How came that widow in?
widow Dido!

SEBASTIAN:
What if he had said 'widower AEneas' too? Good Lord,
how you take it!

ADRIAN:
'Widow Dido' said you? you make me study of that:
she was of Carthage, not of Tunis.

GONZALO:
This Tunis, sir, was Carthage.

ADRIAN:
Carthage?

GONZALO:
I assure you, Carthage.

SEBASTIAN:
His word is more than the miraculous harp; he hath
raised the wall and houses too.

ANTONIO:
What impossible matter will he make easy next?

SEBASTIAN:
I think he will carry this island home in his pocket
and give it his son for an apple.

ANTONIO:
And, sowing the kernels of it in the sea, bring
forth more islands.

GONZALO:
Ay.

ANTONIO:
Why, in good time.

GONZALO:
Sir, we were talking that our garments seem now
as fresh as when we were at Tunis at the marriage
of your daughter, who is now queen.

ANTONIO:
And the rarest that e'er came there.

SEBASTIAN:
Bate, I beseech you, widow Dido.

ANTONIO:
O, widow Dido! ay, widow Dido.

GONZALO:
Is not, sir, my doublet as fresh as the first day I
wore it? I mean, in a sort.

ANTONIO:
That sort was well fished for.

GONZALO:
When I wore it at your daughter's marriage?

ALONSO:
You cram these words into mine ears against
The stomach of my sense. Would I had never
Married my daughter there! for, coming thence,
My son is lost and, in my rate, she too,
Who is so far from Italy removed
I ne'er again shall see her. O thou mine heir
Of Naples and of Milan, what strange fish
Hath made his meal on thee?

FRANCISCO:
Sir, he may live:
I saw him beat the surges under him,
And ride upon their backs; he trod the water,
Whose enmity he flung aside, and breasted
The surge most swoln that met him; his bold head
'Bove the contentious waves he kept, and oar'd
Himself with his good arms in lusty stroke
To the shore, that o'er his wave-worn basis bow'd,
As stooping to relieve him: I not doubt
He came alive to land.

ALONSO:
No, no, he's gone.

SEBASTIAN:
Sir, you may thank yourself for this great loss,
That would not bless our Europe with your daughter,
But rather lose her to an African;
Where she at least is banish'd from your eye,
Who hath cause to wet the grief on't.

ALONSO:
Prithee, peace.

SEBASTIAN:
You were kneel'd to and importuned otherwise
By all of us, and the fair soul herself
Weigh'd between loathness and obedience, at
Which end o' the beam should bow. We have lost your
son,
I fear, for ever: Milan and Naples have
More widows in them of this business' making
Than we bring men to comfort them:
The fault's your own.

ALONSO:
So is the dear'st o' the loss.

GONZALO:
My lord Sebastian,
The truth you speak doth lack some gentleness
And time to speak it in: you rub the sore,
When you should bring the plaster.

SEBASTIAN:
Very well.

ANTONIO:
And most chirurgeonly.

GONZALO:
It is foul weather in us all, good sir,
When you are cloudy.

SEBASTIAN:
Foul weather?

ANTONIO:
Very foul.

GONZALO:
Had I plantation of this isle, my lord,--

ANTONIO:
He'ld sow't with nettle-seed.

SEBASTIAN:
Or docks, or mallows.

GONZALO:
And were the king on't, what would I do?

SEBASTIAN:
'Scape being drunk for want of wine.

GONZALO:
I' the commonwealth I would by contraries
Execute all things; for no kind of traffic
Would I admit; no name of magistrate;
Letters should not be known; riches, poverty,
And use of service, none; contract, succession,
Bourn, bound of land, tilth, vineyard, none;
No use of metal, corn, or wine, or oil;
No occupation; all men idle, all;
And women too, but innocent and pure;
No sovereignty;--

SEBASTIAN:
Yet he would be king on't.

ANTONIO:
The latter end of his commonwealth forgets the
beginning.

GONZALO:
All things in common nature should produce
Without sweat or endeavour: treason, felony,
Sword, pike, knife, gun, or need of any engine,
Would I not have; but nature should bring forth,
Of its own kind, all foison, all abundance,
To feed my innocent people.

SEBASTIAN:
No marrying 'mong his subjects?

ANTONIO:
None, man; all idle: whores and knaves.

GONZALO:
I would with such perfection govern, sir,
To excel the golden age.

SEBASTIAN:
God save his majesty!

ANTONIO:
Long live Gonzalo!

GONZALO:
And,--do you mark me, sir?

ALONSO:
Prithee, no more: thou dost talk nothing to me.

GONZALO:
I do well believe your highness; and
did it to minister occasion to these gentlemen,
who are of such sensible and nimble lungs that
they always use to laugh at nothing.

ANTONIO:
'Twas you we laughed at.

GONZALO:
Who in this kind of merry fooling am nothing
to you: so you may continue and laugh at
nothing still.

ANTONIO:
What a blow was there given!

SEBASTIAN:
An it had not fallen flat-long.

GONZALO:
You are gentlemen of brave metal; you would lift
the moon out of her sphere, if she would continue
in it five weeks without changing.

SEBASTIAN:
We would so, and then go a bat-fowling.

ANTONIO:
Nay, good my lord, be not angry.

GONZALO:
No, I warrant you; I will not adventure
my discretion so weakly. Will you laugh
me asleep, for I am very heavy?

ANTONIO:
Go sleep, and hear us.

ALONSO:
What, all so soon asleep! I wish mine eyes
Would, with themselves, shut up my thoughts: I find
They are inclined to do so.

SEBASTIAN:
Please you, sir,
Do not omit the heavy offer of it:
It seldom visits sorrow; when it doth,
It is a comforter.

ANTONIO:
We two, my lord,
Will guard your person while you take your rest,
And watch your safety.

ALONSO:
Thank you. Wondrous heavy.

SEBASTIAN:
What a strange drowsiness possesses them!

ANTONIO:
It is the quality o' the climate.

SEBASTIAN:
Why
Doth it not then our eyelids sink? I find not
Myself disposed to sleep.

1.2 Tokenize

Our tokens, for the next five steps, are single characters.

vocab = sorted(set(text))                     # the 65 distinct characters that occur in text, in order
V = len(vocab)                                # how many distinct characters there are: 65
stoi = {ch: i for i, ch in enumerate(vocab)}  # table: character -> its integer id
itos = {i: ch for i, ch in enumerate(vocab)}  # table: integer id -> character (the reverse)
encode = lambda s: [stoi[c] for c in s]       # turn a string into a list of integer ids
decode = lambda ids: ''.join(itos[i] for i in ids)  # turn a list of integer ids back into a string
assert decode(encode("Fear no more")) == "Fear no more"  # check: decoding an encoded string gives back the original

Look at vocab. What are tokens 0 and 1? Which characters made the cut?

1.3 Count

PyTorch (import torch) is the deep-learning library used throughout this course. At its core it’s a library for computing with tensors — multi-dimensional numerical arrays, generalizing vectors and matrices. It has two capabilities we’ll need later: it can run the same code on a GPU, and it can automatically compute gradients of the computations it performs (autograd — you’ll build a miniature version of it in Step 3, and use it ever after). This week we use neither: it’s purely an array library here, playing the role NumPy plays elsewhere in scientific Python.

Build the $65 \times 65$ count matrix $N$ with $N_{ab}$ = occurrences of character pair $(a, b)$, as a PyTorch integer tensor. Then visualize it:

import torch
import matplotlib.pyplot as plt

N = torch.zeros((V, V), dtype=torch.int64)  # a 65x65 grid of zeros, to hold the counts
ids = encode(text)               # the whole text as a list of integer ids
for a, b in zip(ids, ids[1:]):   # walk every adjacent pair of characters in the text
    N[a, b] += 1                 # add 1 to the count for "b follows a"

plt.figure(figsize=(10, 10))          # start a new 10x10-inch plot, big enough to read
plt.imshow(N.log1p(), cmap='Blues')   # draw N as an image, log-compressed so it isn't a few bright dots

Stare at the heatmap and find three things (each is checkable from N, and the answers are in the checkpoints below):

1. the row for q — what single column dominates, and how completely?
2. the column for space — is every character ever followed by a space?
3. the capital-letter block — is it brighter into lowercase or into itself? Predict before you look, then explain what you actually see.

Here is where each of those three regions sits inside the 65×65 grid (rows and columns are both ordered exactly as in vocab: punctuation first, then A–Z, then a–z):

For reference, here is vocab itself — the full ordered list of all 65 characters, printed by print(vocab):

['\n', ' ', '!', '$', '&', "'", ',', '-', '.', '3', ':', ';', '?', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

q, u, sp = stoi['q'], stoi['u'], stoi[' ']
caps  = torch.tensor([stoi[c] for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'])
lower = torch.tensor([stoi[c] for c in 'abcdefghijklmnopqrstuvwxyz'])

print(N[q].sum().item(), N[q, u].item())        # 609 609
print((N[:, sp] > 0).sum().item(), 'of', V)     # 46 of 65

after_cap = N[caps].sum(dim=0)   # column totals over just the 26 capital rows
total = after_cap.sum()
print(f'{after_cap[caps].sum() / total:.1%} capitals, '
      f'{after_cap[lower].sum() / total:.1%} lowercase, '
      f'{after_cap[stoi[":"]] / total:.1%} colon')
# 51.0% capitals, 32.9% lowercase, 6.9% colon

1.4 Normalize — carefully

Turn the counts $N$ into the MLE (maximum likelihood estimate) transition matrix $P$, with each row summing to 1. Some character pairs never occur in the text, and a single zero probability would make the log-likelihood of any text containing that pair $-\infty$ — so instead of the raw MLE, use add-one (Laplace) smoothing: add 1 to every count before normalizing, so

P = (N + 1).float()                 # add 1 to every count (smoothing), then convert to decimals
P = P / P.sum(dim=1, keepdim=True)  # divide each row by its own total, so rows become probabilities
assert torch.allclose(P.sum(dim=1), torch.ones(V))  # check: every row now sums to (approximately) 1

1.5 Sample

Generate text by running the Markov chain: start from the newline character, repeatedly draw the next character from row $P_{x_t,\cdot}$ (torch.multinomial), for 500 steps. Decode and read your model’s Shakespeare aloud.

cur = stoi['\n']
out = []
for _ in range(500):
    cur = torch.multinomial(P[cur], num_samples=1).item()
    out.append(cur)
print(decode(out))

1.6 Evaluate on the training text

Compute your model’s average log loss on the text (average $-\log P_{x_t, x_{t+1}}$; vectorize it — P[ids[:-1], ids[1:]] indexes all the transitions at once) and report:

• log loss (cross-entropy) in nats and in bits per character,
• perplexity $e^{\mathcal L}$,
• the same reports for the uniform model $P_{ab} = 1/65$ as a baseline.

One caveat to keep in mind throughout: the counts came from this same text, so every number in this task is a training value — the model is being graded on the exam it studied from. Task 1.7 is the honest version.

Guidance. You are implementing Lecture 1 §3’s token-level log loss, specialized to a bigram model with $p_\theta(b\mid a)=P_{ab}$ and $T-1$ predicted tokens. Perplexity is defined in Lecture 1 §4; §6 gives the bits-per-character conversion.

You are computing one number per transition: for each of the $T-1$ adjacent pairs $(x_t, x_{t+1})$ in the text, look up the probability your model assigned to the character that actually came next, take $-\log$, and average. The vectorized lookup works because PyTorch accepts a pair of index tensors:

ids_t = torch.tensor(ids)         # convert the list of ids into a tensor
p_next = P[ids_t[:-1], ids_t[1:]] # for every adjacent pair, look up the probability the model gave it — all at once

p_next has length len(text) - 1, and entry $t$ is the model’s probability for character $t{+}1$ given character $t$ — the likelihood of the corpus, unrolled into a vector. From it: the mean of $-\log$ is $\mathcal L$ in nats; divide by $\ln 2$ for bits per character, and apply $e^{\mathcal L}$ to obtain perplexity.

Checks and common stumbles, in the order people hit them:

• Validate the vectorization against a loop. Compute the same average with an explicit for loop over the first 10,000 pairs and compare the two numbers.
• Run the uniform baseline through the same code, rather than only computing $\ln 65$ on paper. The uniform answer is insensitive to the data, so getting exactly 4.1744 is a test of your code.
• If your model scores above the uniform 4.1744 (this is bad), maybe you swapped the inputs in P[ids_t[1:], ids_t[:-1]]? The probability of the previous character given the next gives 4.6647 nats on this corpus, worse than knowing nothing. A model evaluated backwards underperforms ignorance!
• Keep logarithm bases straight. Work in natural logs until the final conversion: perplexity is $e^{\mathcal L_{\text{nats}}}$, equivalently $2^{\text{bits/char}}$, and mixing them ($e^{3.54} \approx 35$) produces a plausible-looking wrong number.
• Expected values are in the checkpoints below.

import math

ids_t = torch.tensor(ids)

def avg_log_loss(P, ids_t):
    p_next = P[ids_t[:-1], ids_t[1:]]   # entry t is P[ids[t], ids[t+1]]
    return float(-torch.log(p_next).mean())

def report(name, L):
    print(f'{name:<18} {L:.4f} nats   {L / math.log(2):.4f} bits/char   '
          f'perplexity {math.exp(L):.3f}')

P_uniform = torch.full((V, V), 1 / V)   # the baseline, through the same code

report('bigram (add-one)', avg_log_loss(P, ids_t))
report('uniform', avg_log_loss(P_uniform, ids_t))

bigram (add-one)   2.4549 nats   3.5417 bits/char   perplexity 11.646
uniform            4.1744 nats   6.0224 bits/char   perplexity 65.000

# the vectorized loss agrees with an explicit loop, on the first 10,000 pairs
loop = -sum(math.log(P[a, b]) for a, b in zip(ids[:10000], ids[1:10001])) / 10000
print(f'{loop:.4f} vs {avg_log_loss(P, ids_t[:10001]):.4f}')   # 2.4527 vs 2.4527

# swapping the indices scores the model backwards — worse than knowing nothing
report('backwards', float(-torch.log(P[ids_t[1:], ids_t[:-1]]).mean()))
# backwards          4.6647 nats   6.7297 bits/char   perplexity 106.129

1.7 Evaluate on held-out text

Task 1.6 graded the model on the text its counts came from (teaching to the test). It’s better to test it on fresh data.

1. Split chronologically: the first 90% of the text is the training set, the last 10% the validation set.

   n_train = int(0.9 * len(ids))         # the index that's 90% of the way through the text
   ids_tr = torch.tensor(ids[:n_train])  # the first 90% of the ids: the training set
   ids_va = torch.tensor(ids[n_train:])  # the last 10% of the ids: the validation set

   Keep the vocabulary from Task 1.2, built from the full text. (Conveniently, the last 10% contains no characters absent from the first 90%, so nothing else changes.)

2. Refit from training counts only. Rebuild the count matrix N_tr and the add-one matrix P_tr exactly as in Tasks 1.3–1.4, but from ids_tr alone.

3. Evaluate twice through one pipeline. Wrap the Task 1.6 computation in a function avg_log_loss(P, ids) and call it on ids_tr and on ids_va (score the transitions internal to each portion). Report log loss in nats, bits per character, and perplexity for both.

4. Count the transitions training never saw.

   train_count_of_val_pairs = N_tr[ids_va[:-1], ids_va[1:]]  # for every validation-set pair, how many times training saw it
   print((train_count_of_val_pairs == 0).sum())              # how many of those pairs training never saw at all

5. Run the uniform model through the same validation pipeline. It must give exactly 4.1744 nats again: any change from Task 1.6 is a bug.

Guidance. Validation loss is the number that estimates performance on new text (Lecture 1 §6.3); training loss only tells you how well the counts memorized their own corpus. The gap you should see is real but tiny, about 0.03 nats. The bigram matrix has only 4,225 cells sharing a million characters of evidence, so almost every cell is estimated from abundant data. Overfitting is the tendency of a model to do better on the training data than on novel validation data. In general, overfitting is a function of the ratio of parameters to data, and here that ratio is tiny.

# 1. split chronologically
n_train = int(0.9 * len(ids))
ids_tr = torch.tensor(ids[:n_train])
ids_va = torch.tensor(ids[n_train:])

# 2. refit from training counts only, exactly as in Tasks 1.3-1.4
N_tr = torch.zeros((V, V), dtype=torch.int64)
for a, b in zip(ids[:n_train], ids[1:n_train]):
    N_tr[a, b] += 1
P_tr = (N_tr + 1).float()
P_tr = P_tr / P_tr.sum(dim=1, keepdim=True)

# 3. and 5. the same pipeline, three times
report('train', avg_log_loss(P_tr, ids_tr))
report('validation', avg_log_loss(P_tr, ids_va))
report('uniform (val)', avg_log_loss(P_uniform, ids_va))

train              2.4546 nats   3.5412 bits/char   perplexity 11.641
validation         2.4819 nats   3.5806 bits/char   perplexity 11.964
uniform (val)      4.1744 nats   6.0224 bits/char   perplexity 65.000

# 4. which transitions did training never see?
train_count_of_val_pairs = N_tr[ids_va[:-1], ids_va[1:]]
unseen = train_count_of_val_pairs == 0
pairs = torch.stack([ids_va[:-1][unseen], ids_va[1:][unseen]], dim=1)
distinct, counts = torch.unique(pairs, dim=0, return_counts=True)

print(f'{unseen.sum()} transitions, {len(distinct)} distinct pairs')
for k in counts.argsort(descending=True)[:3]:
    a, b = distinct[k].tolist()
    print(f'  {itos[a]!r} -> {itos[b]!r}: {counts[k]}')

187 transitions, 23 distinct pairs
  'S' -> 'P': 63
  'E' -> 'B': 42
  'N' -> 'Z': 37

Checkpoints

• len(text) = 1,115,394; vocabulary size 65; count matrix sums to len(text) - 1 = 1,115,393. 2,822 of the 4,225 cells of $N$ are zero — two thirds of possible character pairs never occur in the complete works of Shakespeare, which is the concrete reason smoothing is not optional.
• Heatmap answers: (1) q occurs 609 times and is followed by u 609 times so probability exactly 1.000. (2) Only 46 of 65 characters are ever followed by a space. (3) The capital block is brightest into itself — 51% of characters following a capital are capitals against 33% lowercase, backwards from ordinary prose, because of the ALL-CAPS SPEAKER: convention of a printed play (a further 6.9% are :).
• Training-corpus values (Task 1.6 — counts and evaluation both use the full text): average log loss 2.4549 nats = 3.5417 bits/char; perplexity 11.646 (uniform baseline: $\ln 65 = 4.1744$ nats, perplexity exactly 65). Unsmoothed MLE gives 2.4526 — the smoothing costs you 0.002 nats and buys finiteness.
• Held-out values (Task 1.7): the split is 1,003,854 training / 111,540 validation characters, and the validation slice opens mid-Taming of the Shrew (GREMIO: Good morrow, neighbour Baptista). The add-one bigram fit on the training portion scores 2.4546 nats on train, 2.4819 nats on validation (3.5412 vs 3.5806 bits/char; perplexity 11.641 vs 11.964) — a gap of 0.027 nats. 187 validation transitions (23 distinct pairs) have zero training count. Look at which: the top three, S→P (63), E→B (42), and N→Z (37), are PROSPERO, SEBASTIAN, and GONZALO — The Tempest and its ALL-CAPS cast enter the corpus only in the final 10%. The unsmoothed MLE scores 2.4519 on train and infinite on validation; any one of the 187 suffices.
• Samples look like: Thas ppomat he s I fone hell, t athe pen. Nonsense — but English-shaped nonsense: mostly pronounceable, word lengths right.

For calibration: Shannon (1951) estimated English at ~1 bit/character, and your Step 6 transformer will reach roughly 1.5 bits/char on this dataset. Watch your bits/char drop as the course proceeds.

Troubleshooting

• KeyError in encode: you’re encoding a character not in Shakespeare’s vocabulary (e.g. curly quotes from copy-pasting).
• Rows of P don’t sum to 1: check dim= and keepdim= in the sum: did you mix rows and columns?
• Samples are all one repeated character: you probably normalized columns instead of rows.

Going further (optional)

• Trigrams: condition on two characters ($65^2$ contexts). With counts fit and evaluated on the full corpus, average log loss drops to 1.9532 nats (2.818 bits/char, perplexity 7.05) — but that is a training-corpus value, and Lecture 1 §6.4 proved that $n$-gram training loss can only improve as context grows, all the way to memorization. So comparing the bigram’s training optimum with the trigram’s training optimum is not evidence that the trigram generalizes better. The comparison that counts: refit the trigram on the same 90% training portion, with the same character tokenizer, and score the same validation portion as Task 1.7. Expected: 1.9526 nats train, 2.0684 nats validation (2.9841 bits/char, perplexity 7.91) against the bigram’s 2.4819 — so the trigram genuinely does generalize better here. But the warning signs are growing: its train/val gap is 0.116 nats to the bigram’s 0.027, and 1,553 validation transitions are unseen in training, up from 187. Now estimate how the number of parameters grows with context length $k$: the matrix has $65^{k+1}$ entries, so $k=4$ already exceeds a billion while the data stays at a million characters. This exponential blow-up against fixed data is precisely why Lecture 2 replaces matrices with functions.

  Solution: trigrams

  Index the context pair $(a,b)$ as the single integer $aV+b$, so the count table is $4{,}225 \times 65$ and every bigram idiom carries over unchanged. torch.bincount tallies all the triples at once — the Task 1.3 for loop would also work, just slower.

  def trigram_P(seq):
      ctx = seq[:-2] * V + seq[1:-1]      # the context pair, flattened to one integer
      N3 = torch.bincount(ctx * V + seq[2:], minlength=V * V * V).view(V * V, V)
      P3 = (N3 + 1).float()
      return P3 / P3.sum(dim=1, keepdim=True), N3
  
  def trigram_loss(P3, seq):
      ctx = seq[:-2] * V + seq[1:-1]
      return float(-torch.log(P3[ctx, seq[2:]]).mean())
  
  P3, _ = trigram_P(ids_t)              # fit and scored on the full text, as in Task 1.6
  report('trigram (full)', trigram_loss(P3, ids_t))
  
  P3_tr, N3_tr = trigram_P(ids_tr)      # fit on the 90%, scored on both, as in Task 1.7
  report('trigram, train', trigram_loss(P3_tr, ids_tr))
  report('trigram, val', trigram_loss(P3_tr, ids_va))
  
  ctx_va = ids_va[:-2] * V + ids_va[1:-1]
  print((N3_tr[ctx_va, ids_va[2:]] == 0).sum(), 'validation transitions unseen (bigram: 187)')

  trigram (full)     1.9532 nats   2.8178 bits/char   perplexity 7.051
  trigram, train     1.9526 nats   2.8171 bits/char   perplexity 7.047
  trigram, val       2.0684 nats   2.9841 bits/char   perplexity 7.912
  1553 validation transitions unseen (bigram: 187)

  The held-out comparison is the one that counts, and the trigram wins it: 2.0684 against the bigram’s 2.4819. But read the warning signs beside the win — the train/validation gap grew from 0.027 nats to 0.116, and unseen validation transitions from 187 to 1,553. The table is starting to memorize.

• Vary smoothing: $P \propto N + \alpha$ for $\alpha \in \{0.01, 1, 100\}$. Explain qualitatively what large $\alpha$ does to samples and to log loss. Then choose $\alpha$ by validation loss on the Task 1.7 split — using validation data to select a hyperparameter is exactly the role Lecture 1 §6.3 assigns it.

  Solution: varying the smoothing α

  def smoothed(N, alpha):
      P_a = N + alpha
      return P_a / P_a.sum(dim=1, keepdim=True)
  
  for alpha in (0.01, 1, 100):
      P_a = smoothed(N_tr, alpha)
      print(f'alpha={alpha:<6} train {avg_log_loss(P_a, ids_tr):.4f}   '
            f'validation {avg_log_loss(P_a, ids_va):.4f}')

  alpha=0.01   train 2.4519   validation 2.4875
  alpha=1      train 2.4546   validation 2.4819
  alpha=100    train 2.6180   validation 2.6307

  • Training loss increases monotonically with α, from 2.4519 to 2.6180: smoothing can only pull the fitted probabilities away from the counts they were fit to. Choosing α by training loss would therefore always answer “as small as possible” — which is exactly why the choice has to be made on validation data.
  • Validation loss is U-shaped, and of the three, α = 1 wins: 2.4819 against 2.4875 at α = 0.01 and 2.6307 at α = 100. Too little smoothing and the 187 unseen transitions get near-zero probability; too much and every real pattern is diluted.
  • Large α flattens the model toward uniform. At α = 100 every cell is dominated by the constant rather than by its count, rows approach $1/65$, and the samples degrade from English-shaped nonsense toward something closer to random characters — capitals in mid-word, no plausible syllables. In the limit α → ∞ the loss would climb to the uniform 4.1744.
  • α = 1 is not automatically the optimum — it just wins this three-point grid. Sweep a finer range and you are doing hyperparameter selection on validation data, exactly the role Lecture 1 §6.3 assigns it.

Catch-up

None — this is the first step. If you’re joining after Lecture 2+, run solutions/step-01.ipynb and read its prose; it’s self-contained.