Learn
Language 🤖 AI-on 💻 On your computer ⏱ ~10h Difficulty 3/5 v1

Build autocomplete by counting

Suggest the next word of a message, like a phone keyboard. Count which words follow which in thousands of normal messages, turn the counts into probabilities, handle word pairs you have never seen, generate messages, and measure how surprised the model is by new text. Then train a tiny neural network that learns the same probabilities by gradient descent.

Join free to start → Read the brief and materials. Join AI from Scratch to start, submit and ask the tutor. Log in

The problem: guess the next word

You type "Can we meet" on your phone, and the keyboard offers three words: you, up, him. How does it know? It has seen many messages. After "meet", some words come often and most words never do.

In this quest you build that keyboard for the normal messages of our dataset (the "ham" messages: about 3,400 for training). First by counting, then by training a tiny neural network that learns the same thing. The second model is the one the next quests will grow.

Here is what the training messages say about a few words (real counts):

After... seen most common next tokens
"meet" 55 times you (12), them (4), up (4), him (4), in (3)
"call" 171 times me (42), later (32), you (18), "." (8)
"sorry" 117 times "," (43), "." (11), i (11), da (6)
the start of a message 3,372 times i (289), <unk> (127), ok (93), no (80), sorry (73)

So after "call", the chance that the next token is "me" is about 42 / 171 = 0.25. That one division is the whole idea of a bigram model: the next token depends only on the one token before it. A unigram model is even simpler: it ignores the previous token and just uses how common each token is.

A model like this, which gives a probability to every possible next token, is a language model. The big chat assistants are language models too, just with much longer memory.

What you build

  1. ngram.py: a UnigramModel and a BigramModel built from counts (stored in a PyTorch tensor), with smoothing for word pairs they have never seen. They suggest the next word, generate messages, and measure their perplexity on messages they never saw.
  2. neural_bigram.py: the same bigram predictor as a one-layer neural network, trained with gradient descent in PyTorch. You check that its probabilities approach the counts.
  3. A comparison of the three models on the same validation messages.

tokenizer.py is provided (it is the last quest's reference solution; you may swap in your own). autocomplete.py is a small given demo: python autocomplete.py "Can we meet" prints your model's three suggestions.

Fixed vocabulary. Everyone uses the same one, so that numbers can be compared: Vocab.build(training ham messages, min_count=2): 2,710 tokens, and about 9% of validation tokens become <unk>. The grader builds it the same way.

Set up PyTorch

Same as the last quest: pip install -r requirements.txt (torch 2.14.1, Python 3.10 or newer). On an Intel Mac, pip install torch==2.2.2 instead (Python 3.12 or older; a NumPy warning on import is harmless). On Linux without a graphics card, pip install torch==2.14.1 --index-url https://download.pytorch.org/whl/cpu saves a large download.

Part 1: count pairs, with boundaries

Boundary tokens. Put <s> before every message and </s> after it, then count each pair of neighbours:

"ok see you"   ->   <s> ok see you </s>   ->   pairs (<s>, ok) (ok, see) (see, you) (you, </s>)

<s> lets the model learn how messages start, and </s> how they end (and when to stop generating). They also keep messages apart: the last word of one message is never counted before the first word of the next one, because the two messages have nothing to do with each other. Unknown words are counted as <unk>.

Counts in a tensor. With V tokens in the vocabulary, the bigram counts fit in a tensor of shape (V, V): row = previous token, column = next token, so counts[i, j] is how often token j followed token i. Store it in model.counts (raw counts, before smoothing). Dividing each row by its total turns counts into probabilities: every row sums to 1. (A unigram model needs only one row: how often each token is predicted, </s> included.)

Ranked suggestions. next_token_probs(prev) returns a probability for every token that can come next, and suggest(text, k=3) the k most likely words after the text's last token, most likely first. Don't suggest <unk>, <s> or </s>: nobody wants to type those.

Generate by sampling. Start at <s>. Draw the next token at random with the model's probabilities (after "call", "me" a quarter of the time), then draw the one after that, and so on until </s>. Use a seeded random generator (torch.Generator().manual_seed(seed) and torch.multinomial), so the same seed gives the same message. Read some samples: they look like messages for two or three words, then wander off. Why?

Part 2: pairs you have never seen

"meet tonight" never appears in the training messages, so its count is 0, and with plain division its probability is 0. But "Can we meet tonight?" is a perfectly normal message! A model that says "impossible" about normal text is broken, and you will see it in the numbers below (an infinite perplexity).

Smoothing moves a little probability to the pairs you have never seen. Two simple policies from the reading:

  • Add-k: pretend every pair was seen k extra times: P(next | prev) = (count + k) / (total + k V). With k = 1 ("add-one") this takes far too much from the real counts here: with 2,710 possible next tokens, most of the probability goes to pairs that never happen. Try smaller k.
  • Interpolation: mix the bigram with the unigram model: P(next | prev) = λ · count(prev, next) / count(prev) + (1 − λ) · P_unigram(next).

Choose k or λ using the validation messages, never the test messages. Also decide what an unseen context gives: a previous token with no counts at all (for example </s>, or a word the model has never seen, which becomes <unk>). Every next token except <s> must get a probability above 0, and every distribution must sum to 1. Write your policy at the top of ngram.py.

Part 3: how surprised is the model?

To compare models, measure how well they predict messages they have never seen. For each token of a held-out message (and its final </s>), take the probability the model gave it, then:

message   <s> ok see you </s>      probabilities of ok, see, you, </s>:  0.05, 0.1, 0.5, 0.2
negative log-likelihood (NLL) per token:   -ln 0.05 = 3.00, -ln 0.1 = 2.30, -ln 0.5 = 0.69, -ln 0.2 = 1.61
average NLL = (3.00 + 2.30 + 0.69 + 1.61) / 4 = 1.90
perplexity  = e^1.90 = 6.7

Perplexity is "as unsure as choosing among about 6.7 equally likely tokens at each step". Lower is better. A probability of 0 gives an infinite NLL, which is why smoothing matters. Average over all the tokens of all the held-out messages (not per message). Compare models only with the same tokenizer, the same vocabulary and the same text: with more <unk> tokens, for example, the numbers look better while the model got worse.

Expect roughly: unigram about 240, a well-smoothed bigram well under 200, add-one smoothing much worse than the unigram model.

Part 4: the same model, trained instead of counted

Now build the bigram model as a neural network: a table W of shape (V, V) with one row of scores (also called logits) per previous token. That's the entire model: one layer. softmax turns a row of scores into probabilities:

scores after "call":   me 2.0   later 1.0   you 0.0       (a tiny vocabulary of 3)
softmax:  e^2.0, e^1.0, e^0.0  =  7.39, 2.72, 1.00   ->  divide by their sum 11.11
          ->  me 0.67   later 0.24   you 0.09            (always positive, always sums to 1)

Training makes the true next token likely. For each (previous, next) pair from the messages, the cross-entropy loss is −ln(probability of the true next token). That's exactly the NLL from Part 3, so training lowers the same number you measured. Use bigram_pairs (with <s> and </s>, as before) to get all the pairs, then the four-line training step from the last quest, with random mini-batches of pairs (say 1,024 at a time: all 63,000 pairs at once would need gigabytes of memory for 2,710 scores each). F.cross_entropy computes softmax and cross-entropy together; check it once against your own computation on a tiny example.

The check you can trust. With no smoothing, the best possible table W gives exactly the count fractions count(prev, next) / count(prev). So a well-trained network should agree with your counts, most clearly for frequent contexts like <s>, "i" or "call". Measure it: for each frequent context, compare the two rows (for example the largest probability difference, or the KL divergence: Σ p · ln(p / q) over next tokens with count p > 0). Start W at zeros (all next tokens equally likely) and train for a minute or two on all the training messages. Then measure its validation perplexity too, and explain what you see: what does the network do with pairs it never saw, compared with your smoothed counts? (Karpathy's video shows one fix: regularization works like smoothing.)

Why bother, if counting gives the same answer? Because counting stops here: with two or three previous words, most combinations are never seen. A network can grow, and the next quest makes it bigger.

What to submit

  • ngram.py, neural_bigram.py (and your tokenizer.py if you changed it), plus the code you used to compare the models. No model files: the grader fits the counting models itself (it takes a second), and trains your neural bigram only on tiny corpora. (A full-size table has 2,710 × 2,710 = 7.3 million weights, too big to submit.)
  • SUBMISSION.md with these sections (the starter has a template): 1. Counting and smoothing: your boundary handling, your smoothing policy and how you chose it on validation, some suggestions and samples. 2. Comparing unigram, bigram and neural bigram: one table, same tokenizer, vocabulary and validation text; how close the neural model gets to the counts on frequent contexts. 3. An unseen-context failure: a real example where the model has never seen the context or the pair, what it does, and why. 4. How I used AI and checked it.
  • Your AI transcripts in .neugen/logs/ (neugen log <file>).

How you're graded

  1. Hidden tests (neugen test runs the public ones): - Counts, probabilities, sampling, perplexity (all must pass), mostly on tiny corpora where the right answer is known: raw counts with boundaries and nothing across messages, distributions that sum to 1 with no zeros, unseen contexts, suggestions, reproducible sampling that follows your probabilities, and a perplexity() that agrees with your own probabilities (starting at <s>, including </s>). - Held-out perplexity on normal messages you have never seen: unigram at most 260, bigram at most 200. - Neural bigram: bigram_pairs, the shapes, and train_neural_bigram(tokens, vocab, seed=0) with your default settings on tiny corpora must reach the counts (average KL at most 0.1 on contexts seen at least 4 times) within a minute. So the defaults must train plainly: put any regularization behind an argument that is 0 by default.
  2. Rubric review by an AI grader: your comparison, the unseen-context failure, and how you used and checked AI.
  3. Defense: a short conversation about your code.

What you must be able to explain and change

This is an AI-on quest: use AI for anything, including writing code. In the defense you will be asked about these, in your own code:

  • the bigram counts of a tiny corpus with <s> and </s>, by hand, and why the boundaries matter;
  • your smoothing policy: the probability of an unseen pair, and of anything after an unseen context;
  • the perplexity of a tiny example, by hand, and why a single zero makes it infinite;
  • how sample() draws a token, and why the seed makes it reproducible;
  • softmax and cross-entropy on a tiny row of scores, and why the trained network approaches the counts;
  • a small change, for example a different smoothing setting, a trigram, or suggestions that skip punctuation, and what it would do to your numbers.

Suggested path (about 10 hours)

  1. Read the chapter, and watch the video segments if you like (2.5 hours).
  2. Counting models with boundaries, suggestions, sampling (2 hours).
  3. Smoothing and perplexity; tune on validation (2 hours).
  4. The neural bigram; compare it with the counts (2 hours).
  5. neugen test, the comparison and SUBMISSION.md (1.5 hours).

Optional extension: a trigram model (two previous tokens) that backs off to your bigram when it has not seen a context. Does it beat the bigram on validation? It is not graded.

Tips

  • Check on a tiny corpus first. Three short messages, counts by hand, then your code. The grader does exactly this.
  • Print a row. next_token_probs("call") sorted by probability tells you a lot. Does it sum to 1? Is anything 0?
  • Mind <s> and </s>. <s> is never predicted; </s> is predicted once per message and counts in perplexity.
  • Use the tensor. Dividing all rows at once (counts / counts.sum(dim=1, keepdim=True)) is one line; a Python loop over 2,710 × 2,710 cells is slow.
  • Shapes again: the network maps (N,) IDs to (N, V) scores. F.cross_entropy wants scores (N, V) and target IDs (N,).

Interface

# tokenizer.py is provided (from the last quest); IDs 0 <unk>, 1 <s>, 2 </s>.
# The grader builds the vocabulary as Vocab.build(train_ham_token_lists, min_count=2).
# Token lists are messages WITHOUT boundaries; the models add <s> and </s> themselves.

# ngram.py
class UnigramModel:
    def __init__(self, vocab)
    def fit(self, token_lists) -> "UnigramModel"
    def next_token_probs(self, prev=None) -> dict[str, float]   # ignores prev
    def perplexity(self, token_lists) -> float
class BigramModel:
    def __init__(self, vocab)                       # smoothing settings: your defaults
    counts: torch.Tensor                            # after fit: (V, V) RAW counts, row = previous token
    def fit(self, token_lists) -> "BigramModel"
    def next_token_probs(self, prev: str) -> dict[str, float]
        # every token except <s> (which may be left out) with probability > 0; sums to 1;
        # works for "<s>", "<unk>" and words never seen
    def perplexity(self, token_lists) -> float      # exp(mean -log P), </s> included
    def sample(self, seed=0, max_tokens=30) -> list[str]   # without <s> / </s>
    def suggest(self, text: str, k=3) -> list[tuple[str, float]]   # no special tokens

# neural_bigram.py
def bigram_pairs(token_lists, vocab) -> tuple[torch.LongTensor, torch.LongTensor]  # (prev, next)
class NeuralBigram(nn.Module):
    def __init__(self, vocab_size)                  # a (V, V) table of parameters
    def forward(self, prev_ids) -> torch.Tensor     # (N,) -> (N, V) logits
def train_neural_bigram(token_lists, vocab, seed=0) -> NeuralBigram   # plain training by default