Follow the gradient
Random search found good weights for your message filter, but only by luck and many tries. Measure which way is downhill instead: estimate slopes by nudging one weight, work out the exact gradient of the loss, check one against the other, and train the filter with gradient descent. Then compare it with random search on the same budget, and see what a learning rate that is too large does.
The problem: search learns by luck
In the last quest, random search trained your filter. It works, but look at what one run of random local search learned (50 tries, step size 0.3, seed 2):
| Clue | has_link | prize_words | caps_fraction | length |
|---|---|---|---|---|
| Weight | -0.03 | 3.27 | -3.18 | 0.60 |
A link makes a message less suspicious, and so do capital letters? Nobody would choose that. The search found these numbers by chance, and kept them because nothing better turned up. Here is what they do to two real messages from the validation split:
| Message | Really | Search filter | Filter from this quest |
|---|---|---|---|
| "Monthly password for wap. mobsi.com is 391784. Use your wap phone not PC." | spam | 7% spam | 72% spam |
| "Congratulations ore mo owo re wa. Enjoy it and i wish you many happy moments to and fro wherever you go" | normal | 75% spam | 41% spam |
Random search tries a change and only then finds out if it helped. But the loss can tell you which way to move each weight before you try anything. That is the gradient, and following it is how almost every AI model learns. In this quest you train the same filter by following the gradient, check your maths in two independent ways, and measure whether it beats search.
What you'll build
| File | What it does |
|---|---|
gradients.py |
numerical_gradient, analytic_gradient and gradient_descent (the grader tests these) |
compare.py |
your experiments: anyone can rerun them and get your numbers |
gd_filter.json |
your trained filter: {"weights": [...], "bias": ..., "threshold": ...} |
SUBMISSION.md |
your write-up (the starter kit has a template) |
Your starter kit has the clues (features.py), the filter (filter.py: score, predict,
evaluate) and the loss and search (learn.py: sigmoid, cross_entropy, average_loss,
local_search). They are provided, marked "Provided", from the earlier quests. You may replace
them with your own. Note that average_loss, evaluate and local_search there take
(text, label) pairs.
The ideas, with small numbers
1. A slope, by nudging one weight
Take one spam message, "WINNER!! Claim your prize at www.example.com". Its clues are
[1, 3, 0.2, 0.44]. Start with every weight and the bias at 0. The score is 0, the filter says
"50% spam", and the loss is 0.693.
Now nudge one weight, prize_words, up by a tiny amount h = 0.001, and then down by 0.001:
| prize_words weight | score | loss |
|---|---|---|
| 0.001 | 0.003 | 0.691648 |
| -0.001 | -0.003 | 0.694648 |
The loss changed by -0.003 over a change of 0.002 in the weight:
slope = (0.691648 - 0.694648) / (2 * 0.001) = -1.5
This number is the derivative of the loss with respect to that weight: how fast the loss changes when the weight changes a little. It is negative, so a bigger prize-words weight gives a smaller loss. Nudging in both directions and dividing by 2h is called a centered difference; it is much more accurate than nudging in one direction only.
2. The gradient: one slope per parameter
The filter has five parameters: four weights and a bias. Do the nudge for each one, and you have
five slopes. Together they are the gradient. numerical_gradient does exactly this for any
function and any number of parameters.
3. Downhill steps
The gradient points uphill (towards a bigger loss). So move every parameter a small step the other way:
new value = old value - learning_rate * slope
With learning rate 0.5 and slope -1.5, the prize-words weight goes from 0 to 0.75. Repeat: compute the gradient again at the new point, take another step. That is gradient descent. The learning rate decides how big each step is.
For the whole training split, use the average loss over all messages, so every step uses all the messages ("full batch"). The slope of an average is the average of the slopes.
4. The exact gradient, with calculus
Nudging costs two passes over the data for every parameter. For a network with a million parameters, that is two million passes for one step: far too slow. Instead, work the slopes out once with calculus. You need one rule, the chain rule: if the loss depends on the score, and the score depends on a weight, then
(slope of loss with respect to the weight) = (slope of loss w.r.t. the score) * (slope of score w.r.t. the weight)
The second part is easy: the score is w1*c1 + w2*c2 + w3*c3 + w4*c4 + b, so a small change in w2
changes the score by c2 times as much (for the bias: 1 times). The first part is yours to work
out from the cross-entropy and the sigmoid. The answer is surprisingly short. Check it on the
example above: it must give -1.5.
Then check your formula against numerical_gradient at a few points, on real messages. The
two methods have nothing in common except the loss, so if they agree to about 6 decimal places,
both are almost surely right. This habit, called gradient checking, catches most bugs in
gradient code.
Your tasks
- Slopes. Write
numerical_gradient. Try it on a function where you know the answer (for examplef(p) = p[0] ** 2at 3: the slope is 6). - One slope by hand. For one real message of your choice, work out one slope with pencil and
paper (or a calculator) using your formula, and compare it with
numerical_gradient. - The exact gradient. Write
analytic_gradientand check it againstnumerical_gradientat several points, including one where some scores are large (for example 50 or -50). - Gradient descent. Write
gradient_descent. Watch the loss go down. - Search versus gradient descent. Compare with random search (yours from the last quest, or
local_search(messages, "loss", budget, step_size, seed)inlearn.py) on the same budget. Count the budget in passes over the training data: one search try costs one pass (one loss), and one gradient step costs one pass (one gradient). Try a small budget and a larger one (for example 10, 50 and 200 passes), and several search seeds. Report training and validation loss. - Learning rates. Train with several learning rates, from very small to too large. Find one where the loss goes up. Describe what the loss curve looks like in each case.
- A broken run. Flip the sign of the update (
+instead of-) and run a few steps. How does that loss curve differ from a learning rate that is too large? You will be asked to recognise both in the defense. - Your filter. Train your final filter on the training split, choose a threshold using the
validation split, and save
gd_filter.json.
Rules the grader checks
- In
gradients.py,messagesis a list of(clues, label)pairs, whereclues = features.extract(text). Working out the clues once makes training fast. numerical_gradient(loss_fn, params, h=1e-5)uses centered differences with thehit is given, works for any number of parameters, and does not changeparams.analytic_gradient(messages, weights, bias)returns(grad_w, grad_b)for the average cross-entropy. It must work for any scores, even 1000 or -1000 (math.exp(1000)overflows; the providedsigmoidandcross_entropydon't).gradient_descent(messages, learning_rate, steps, weights=None, bias=None)uses all messages in every step, starts from zeros by default, and returns(weights, bias, history), wherehistoryholdssteps + 1average losses: the start, then one after each step.
The exact interface is in the "Interface" section at the end of this brief.
The core pieces you must be able to explain
You may use AI for anything in this quest. The defense then checks that you understand your own submission. Be ready to:
- compute a centered difference by hand and say why it is centered;
- derive the slope of one message's loss with respect to one weight, with the chain rule;
- predict the result of one gradient-descent step on a tiny example;
- explain why the average loss is used, and what a learning rate that is too large does;
- tell a wrong-sign update from a learning rate that is too large, from the loss curve alone;
- change your code: for example, add a fixed penalty on large weights to the loss and its gradient.
How you're graded
- Automated checks, on a public suite (you have it;
neugen testruns it) and a hidden one: - Numerical gradient, Analytic gradient, Gradient descent: all checks must pass. The hidden suite adds other functions, other values of h, edge-case messages (empty, all capitals, extreme scores) and 100 steps on the whole training split. - Your filter:gd_filter.jsonis scored on the validation split (public) and on hidden test messages: loss at most 0.20, recall at least 0.6, precision at least 0.7. - Write-up review of
SUBMISSION.mdwith the rubric on this page. - Defense: a short conversation with the AI examiner about your code and results.
Suggested path (about 7 hours)
- Read the CS231n sections listed in the materials (1 hour).
- Work through "The ideas, with small numbers" above with a calculator, then write
numerical_gradient(1 hour). - Derive the gradient on paper, write
analytic_gradient, check it (1.5 hours). gradient_descentand your final filter (1 hour).- Experiments: search versus gradient descent, learning rates, the broken run (1.5 hours).
- Write-up,
neugen test, submit (1 hour).
Tips
- Derivatives refresher. The slope of
x * xat x is2 * x; ofc * xit isc; oflog(x)it is1 / x; ofexp(x)it isexp(x). For the sigmoids(z) = 1 / (1 + exp(-z)), the slope iss(z) * (1 - s(z)). Check any of these withnumerical_gradient. - If the gradients disagree, test one parameter at a time, on one message, with all weights at 0. Then on two messages. A factor of exactly 2, or exactly the number of messages, is a clue.
- Speed. Pure Python handles one full-batch step on 3,900 messages in a few milliseconds if the clues are worked out once. A few thousand steps take about a minute.
- Fair comparisons. Same training data, same starting point, same budget, several seeds for search. Report validation loss too, not only training loss.
- Accuracy hides things. Report recall and precision for your final filter, as in the earlier quests: always answering "normal" already scores 86% accuracy.
Interface
# gradients.py. Here `messages` is a list of (clues, label) pairs:
# clues = features.extract(text) (4 numbers), label is 1 for spam and 0 for normal.
def numerical_gradient(loss_fn, params, h=1e-5) -> list[float]: ...
# params is a flat list, for the filter [w1, w2, w3, w4, b]; loss_fn(params) -> float.
# Centered differences, one parameter at a time. Do not change the params list.
def analytic_gradient(messages, weights, bias) -> tuple[list[float], float]: ...
# (d average_loss / d weights, d average_loss / d bias), worked out with calculus.
def gradient_descent(messages, learning_rate, steps, weights=None, bias=None):
# -> (weights, bias, history). Full batch: every step uses all the messages.
# Starts from zeros by default. history holds steps + 1 average losses:
# the starting loss, then the loss after each step.
# gd_filter.json, your trained filter:
{"weights": [w1, w2, w3, w4], "bias": b, "threshold": t} # flags spam when score > t
Read now
Read 'Strategy #3: Following the gradient', 'Computing the gradient' (both 'Numerically with finite differences' and 'Analytically with calculus') and 'Gradient Descent'. Skim strategies #1 and #2: they are your S2 search. The notes use an image classifier; apply each idea to your four-clue filter. Mini-batches are optional here (your data is small enough for the full batch).
Three stages. You only move on when the one before passes.
Automated gates
| Metric | Gate | What it checks |
|---|---|---|
| Numerical gradient | ≥ 1.0 | Share of numerical_gradient checks that match the true slopes. The hidden set uses other functions, other values of h and more parameters. All must pass. |
| Analytic gradient | ≥ 1.0 | Share of analytic_gradient checks that match the exact gradient of the average cross-entropy. The hidden set has edge cases (an empty message, all capitals, extreme scores). All must pass. |
| Gradient descent | ≥ 1.0 | Share of gradient_descent checks that pass: exact updates, the default start, the history, a falling loss with a sensible learning rate, and (hidden) 100 steps on the whole training split. All must pass. |
| Your filter: loss | ≤ 0.2 | Average cross-entropy of gd_filter.json on validation (public) or the hidden test messages. A well-trained filter gets about 0.19 on validation. |
| Your filter: spam caught (recall) | ≥ 0.6 | Share of spam messages your filter flags, with your threshold. |
| Your filter: precision | ≥ 0.7 | Share of flagged messages that really are spam, with your threshold. |
Gates run on the public set (which you have) and a hidden set with inputs you haven't seen.
Rubric review need ≥ 60%
"One slope by hand" works one slope for one real message step by step (clues, score, probability, the slope from their formula) and compares it with numerical_gradient. "My gradient, checked" states the formula in the student's own words with the chain rule (slope of the loss w.r.t. the score times the slope of the score w.r.t. the weight), and reports numerical-versus-analytic differences at several points, including large scores.
The comparison uses the same data, start and budget (passes over the training data) for both methods, several search seeds and at least two budgets, with training and validation loss in a table produced by compare.py (or a script like it). Conclusions stay within the evidence (for example: gradient descent is better at small budgets and has no luck in it; with only five parameters, search catches up given enough tries). The learning-rate section shows a rate that is too small, a good one and one that is too large, with what the loss curve did. The broken run shows the wrong-sign curve and says how to tell it from a rate that is too large.
The logs and "How I used and checked AI" show the student used AI to learn (for example asked for the chain rule on a tiny example, or why a centered difference is better) and checked what it produced: a formula verified with numerical_gradient or by hand, a claim tested with a small experiment, or a mistake in AI-written code found and fixed. Using AI to write code is fine; judge the checking, not the amount of AI use.
Defense need ≥ 50%
A 4-question conversation with the AI examiner about your code. It isn't a trick: if you did it and understood it, it's the easy part. A weak defense on strong work gets you a new variant to redo.

