Train a character bigram language model
Lesson: Text Generation Before Transformers — N-gram Language ModelsCheat sheetTrack: LLM inferenceTrack: Train tiny models
Problem
A bigram language model predicts the next character from the current character only. It is the smallest model that uses context, and its loss is the same next-token cross-entropy that trains a GPT. In this task you train a table of next-character logits with gradient descent. The checks then measure it on a held-out text that your code never sees.
Task
Write two functions.
train(ids, vocab_size, rng)trains the model on one long sequence of character ids and returns the model.next_log_probs(model, prev_ids)returns \log P(\text{next} \mid \text{prev}) for each context inprev_ids.
The model is a matrix W of shape (V, V). Row a holds the logits of the character that follows character a, so P(\cdot \mid a) = \mathrm{softmax}(W_a). The training pairs are (x_t, x_{t+1}) for t = 0, \dots, T - 2. Train W with gradient descent on the mean negative log-likelihood
The training text is TEXT in support.py. It holds the "What it actually means" lines of the first 26 entries of the course glossary, glossary/terms.md, from "Activation Checkpointing" to "Benchmark Contamination". The text is lower case. Every character outside VOCAB is a space. VOCAB has 29 characters: the space, the letters a to z, the full stop and the comma. encode(text) gives the ids and decode(ids) gives the text back.
During training, call report(step, loss) from practice_check once for each update step. The first step is 0. The page draws these values as a live loss curve, and the checks count them.
Input and output
| Name | Type | Shape | Meaning |
|---|---|---|---|
ids | int array | (T,) | the character ids of the training text, from 0 to vocab_size - 1 |
vocab_size | int | the number of characters, 29 | |
rng | np.random.Generator | the only source of random numbers | |
model | any | the value that train returns | |
prev_ids | int array | (M,) | the context characters |
trainreturns the model. The model can be any Python value, for example the matrix W.next_log_probsreturns a float array of shape(M, 29). Row i holds the log probabilities of the 29 characters afterprev_ids[i].
Constraints
- Budget: at most 300 update steps, so at most 300 calls to
report. - Target: a mean negative log-likelihood of at most 2.55 nats per character on a held-out text from other glossary entries. This page does not show that text. A uniform model gets \log 29 = 3.367. A unigram model that ignores the context gets about 2.9.
- Train with gradient descent. Pairs that never occur in the training text must keep a finite log probability.
- Take every random number from
rng. The same seed must give the same model. - Do not change
ids. - Use numpy only. One full submit has a limit of 15 seconds.
Examples
pythonids = encode(TEXT)
model = train(ids, len(VOCAB), np.random.default_rng(1))
np.exp(next_log_probs(model, encode("q"))[:, encode("u")])text[[0.9663]]The output is rounded to 4 decimals. After q, the model gives the letter u a probability of 0.9663. The reference starts with logits near 0, so its first reported loss is 3.3666, close to \log 29. After 300 steps its loss on the training text is 2.3148. A unigram model gets 2.9110 on the same text.
Provided code: support.py
Your code and the checks import this module with from support import .... You do not change it.
import numpy as np
VOCAB = " abcdefghijklmnopqrstuvwxyz.,"
TEXT = (
'a training memory technique that saves only selected forward pass activations and '
'recomputes the omitted ones during backpropagation. a function applied after a '
'linear or affine layer that introduces nonlinearity. without it, composing layers '
'with weights and biases collapses to one affine transformation. relu, gelu, and silu'
' are common choices. the choice directly affects whether gradients flow during '
'training. adaptive moment estimation. it combines an exponential average of '
'gradients with an exponential average of squared gradients, applies bias correction,'
' and adapts the update scale per parameter. it is a useful baseline, but it still '
'needs a suitable learning rate and schedule. an adam variant that decouples weight '
'decay from the gradient based parameter update. that makes the shrinkage behavior '
'easier to reason about than adding an l penalty inside adam s adaptively scaled '
'gradient. a pre acceptance gate that decides whether a request may enter a bounded '
'queue or service under the system s current capacity, priority, and policy. a '
'software system that lets a model select actions toward a goal, observe tool or '
'environment results, and continue under an orchestration policy. an agent may use a '
'loop, a state machine, a workflow engine, or human approvals. the model is one '
'component, not the entire system. the runtime around a model that assembles context,'
' exposes tools, manages state, enforces limits, records traces, and decides when the'
' agent should continue, retry, ask, or stop. information stored outside the model '
'and selected for use in later agent steps, such as prior decisions, user '
'preferences, task episodes, or verified facts. the explicit data an agent carries '
'across steps, such as the current objective, completed actions, tool results, open '
'questions, budgets, approvals, and artifact references. a discoverable directory of '
'procedural instructions whose entry point is skill.md , with optional references, '
'scripts, and assets that a compatible runtime can load in stages. a documented '
'analysis of how an ai system can affect people, organizations, and environments, '
'including context, hazards, likelihood, impact, controls, residual risk, and '
'monitoring responsibilities. the effort to make a model or ai system behave in ways '
'that match intended goals, constraints, and human preferences across both expected '
'and adversarial situations. a control point that blocks a consequential action until'
' an authorized person or policy grants permission. a search method that returns '
'vectors likely to be among the nearest to a query without exhaustively comparing the'
' query with every stored vector. a mechanism that forms contextual representations '
'by comparing query vectors with key vectors, normalizing the resulting scores, and '
'using them to combine value vectors. masks, position rules, or sparse patterns can '
'restrict which positions participate. a discrete identifier produced by an audio '
'codec or tokenizer for a short segment or feature of an audio signal, sometimes '
'across several codebooks. a durable, access controlled record of security or '
'accountability relevant events, including who or what acted, what changed, when it '
'happened, and the resulting status. a system that records or transforms tensor '
'operations so it can compute derivatives, usually with reverse mode automatic '
'differentiation. you write the forward computation and the framework derives the '
'gradients needed for backpropagation. the task and system pipeline that maps a '
'speech signal to a transcription, often with optional token or segment timing and '
'confidence information. a factorization in which each output token is predicted from'
' the tokens that precede it. during generation, the selected token is appended to '
'the sequence and becomes part of the next prediction s context. a control loop that '
'changes the number or capacity of serving workers from observed demand, resource '
'use, or application metrics within configured bounds. the proportion of eligible '
'service interactions or time windows in which users can obtain the defined '
'acceptable service under a stated measurement boundary. a flow control mechanism '
'that slows or rejects upstream work when a downstream component cannot process it '
'safely at the current rate. an efficient application of the chain rule that '
'propagates derivatives from a scalar loss backward through a computation graph. it '
'computes gradients an optimizer uses those gradients to update parameters. the '
'number of examples whose losses contribute to one gradient estimate before an '
'optimizer update. larger batches can improve hardware utilization and reduce '
'gradient noise, but they require more memory and may need different learning rate or'
' scheduling choices. overlap or information leakage between evaluation examples and '
'data used to pretrain, tune, prompt, select, or otherwise improve the evaluated '
'system.'
)
def encode(text):
return np.array([VOCAB.index(ch) for ch in text], dtype=int)
def decode(ids):
return "".join(VOCAB[int(i)] for i in ids)
Hints
4 hintsSolution and notes
LockedPass every check with Submit to open the reference solution and the notes.
Run it on your computer
Clone the repository, install numpy and run the same checks in a terminal:
python3 scripts/practice/run.py train-char-bigram my_answer.py
python3 scripts/practice/run.py train-char-bigram my_answer.py --examplesStart my_answer.py from starter.py.
Your code is saved in this browser as you type. On a phone you can read and edit the code, but the checks are easier to use on a desktop.
Keyboard shortcuts
- Ctrl Enter
- Run the examples
- Ctrl Shift Enter
- Submit
- Tab / Shift Tab
- Indent or outdent the lines
- Esc then Tab
- Move the focus out of the editor
- Alt H
- Show the next hint
On a Mac, use Cmd in place of Ctrl.
Select Run to check the examples, or Submit to run every check.