Learn
Learning 🤖 AI-on 💻 On your computer ⏱ ~6h Difficulty 2/5 v1

Make the filter learn

Choosing weights by hand is slow, and you can't do it for a thousand clues. Let the computer choose: try random filters, then improve one with small random changes, and keep what works. On the way, find out why accuracy is a poor guide for search, turn scores into probabilities, and build a loss that tells the search how wrong each message is.

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

Why this quest

In the last quest you chose six numbers by hand: four weights, a bias and a threshold. It took patience, and it only worked because there were four clues. Later in this course your filter reads every word of a message: thousands of clues, thousands of weights. Nobody can tune those by hand.

So let the computer choose. Training means: try parameters, measure them on labelled examples, keep the better ones. In this quest you build the simplest training methods there are, random search and random local search, and you find out that what you measure matters as much as how you search.

Start with three real messages that a hand-tuned filter (weights [3, 2, 2, 1], bias -3.5) gets wrong:

Message Really Score
"You have 1 new voicemail. Please call 08719181513." spam -2.86
"Ringtone Club: Get the UK singles chart on your mobile each week and choose any top quality ringtone! ..." spam -0.06
"Hi, Mobile no. <#> has added you in their contact list on www.fullonsms.com It s a great place to send free sms ..." normal 3.07

Accuracy counts each of these as one mistake. But they are not equally wrong. "Ringtone Club" is a near miss: a tiny change to the weights would flag it. The voicemail message is far from the threshold. The filter is very sure about the third message, and wrong. A search that only looks at accuracy can't see any of this. By the end of this quest, your filter will.

1. Training is search

To train, you need three things:

  1. Something to change: the parameters (weights and bias).
  2. Examples: labelled messages (data/sms_train.tsv).
  3. An objective: one number that says how good a filter is on the examples.

Random search: try budget random filters (for example each weight and the bias between -5 and 5) and keep the best. Simple, and surprisingly hard to beat on a tiny problem.

Random local search: start somewhere (here: all zeros), add a small random change to every parameter, and keep the new filter if it is better. Repeat budget times. Each step only looks near the current filter, like walking downhill in fog by testing one step at a time.

Seeds. Random numbers in a program come from a generator. rng = random.Random(42) makes a generator that always produces the same numbers, in the same order:

import random
rng = random.Random(42)
rng.uniform(-5, 5), rng.uniform(-5, 5)   # (1.394..., -4.749...) every time you run it

Use random.Random(seed) in your searches, and the same seed and budget always give the same filter. That makes your experiments reproducible: you, a friend and the grader get the same result.

2. The first objective: accuracy

Start with accuracy (threshold 0) as the objective. Run local search with it. Watch how often a change is accepted, and how often accuracy changes at all.

You will see that accuracy is flat in many places. A small change to a weight moves every score a little, but a prediction only changes when a score crosses the threshold. Most small changes flip no prediction, so accuracy stays the same, and the search learns nothing about which direction is better. Accuracy also ignores confidence: the voicemail message and "Ringtone Club" count the same.

And there is a trap. About 86% of these messages are normal. The filter "never flag anything" has 86% accuracy and catches no spam: recall 0. If your search reports 87% accuracy, check its recall before you celebrate.

3. A better objective: probabilities and loss

From scores to probabilities. The sigmoid function squeezes any score into a number between 0 and 1:

sigmoid(z) = 1 / (1 + e^(-z))

sigmoid(-2.86) = 0.054    sigmoid(0) = 0.5    sigmoid(3.07) = 0.956

Read it as "the filter's probability that this message is spam". A score of 0 means 50/50. (This is why a score is not a probability, but can be turned into one.)

Loss: how wrong is the filter about one message? If a message is spam, the filter should give it a high probability p. The cross-entropy loss is:

spam (label 1):    loss = -log(p)          natural log
normal (label 0):  loss = -log(1 - p)

Some values for a spam message:

p (filter's probability of spam) 0.99 0.9 0.5 0.1 0.01
loss = -log(p) 0.010 0.105 0.693 2.303 4.605

Confident and right costs almost nothing. Unsure costs 0.693. Confident and wrong costs a lot, and the cost keeps growing. For the three messages above: "Ringtone Club" (p = 0.486) costs 0.72, the voicemail (p = 0.054) costs 2.92, and the false alarm (p = 0.956, label normal) costs -log(1 - 0.956), about 3.1.

The average loss over many messages is the new objective: lower is better. Unlike accuracy, it changes with every small change to the weights, because every probability changes. So the search can tell "a bit better" from "a bit worse".

Two useful numbers: the all-zero filter gives every message p = 0.5, so its average loss is log(2) = 0.693. The best filter that ignores the clues (the same probability, 0.135, for every message) gets about 0.39. A filter that uses the clues well gets below 0.2.

Note: lower loss does not guarantee higher accuracy. Loss rewards honest probabilities; accuracy only counts which side of the threshold a score lands on. You will see both in your experiments.

4. Big numbers: make it stable

Computers store numbers with limited range. In Python, math.exp(1000) raises OverflowError, and math.exp(-1000) is 0.0. So:

  • 1 / (1 + math.exp(-z)) crashes for z = -1000.
  • A spam message with score -800 has p = sigmoid(-800), which is 0.0 in floating point, and -log(0.0) is an error.

What should the loss be? The filter is extremely sure and wrong, so the loss must be large: about 800. A common shortcut "clips" p to at least 1e-15. That gives 34.5 instead of 800: the search would think a terrible mistake is only a bit bad. Don't clip.

The way out is maths, not bigger numbers. For spam, -log(sigmoid(s)) = log(1 + e^(-s)). For normal, -log(1 - sigmoid(s)) = log(1 + e^(s)). (Check one of these by hand.) So compute the loss from the raw score, never from p. When z is large, log(1 + e^z) is almost exactly z. Can you rewrite log(1 + e^z) so that e is only ever raised to a zero or negative power? Do the same kind of thinking for sigmoid.

5. What to build

Your starter kit has features.py and filter.py (provided: the reference solution of the last quest; you may replace it with your own). Write learn.py with five functions (the docstrings explain each one):

def sigmoid(z) -> float                        # no overflow for any finite z
def cross_entropy(score, label) -> float       # from the raw score; (-800, 1) gives about 800
def average_loss(messages, weights, bias) -> float
def random_search(messages, objective, budget, seed) -> (weights, bias)
def local_search(messages, objective, budget, step_size, seed) -> (weights, bias)
  • messages is a list of (text, label) pairs, as features.load_messages returns them.
  • objective is "accuracy" (higher is better, threshold 0) or "loss" (average loss, lower is better). Write in your code which direction each one goes.
  • budget is how many candidate filters a search tries. seed: use random.Random(seed).
  • local_search starts from weights [0, 0, 0, 0] and bias 0. What to do with a tie (a change that is exactly as good) is your choice; explain it.

Keep these names exactly: the next quest uses them.

Then experiment (in a script of your own, for example experiment.py):

  1. Search on the training messages; measure the result on the validation messages.
  2. Compare random search and local search, and accuracy and loss as objectives, with the same budget and seed. Look at real misclassified messages and their probabilities and losses.
  3. Save your best filter, the one with the lowest validation loss, in learned_filter.json (same shape as last time):
{"weights": [1.0, 1.0, 1.0, 1.0], "bias": -2.0, "threshold": 0}

Never choose parameters by looking at the test set: you don't have it, and that is the point. The grader measures learned_filter.json on hidden test messages.

Keep short experiment notes as you go. Before each run, write what you expect; after it, what happened. For example: "Prediction: random search with 1,000 tries beats local search with 200, because it tries five times more filters. Change: random, budget 1000 versus local, budget 200, seed 0, loss. Result: validation loss 0.201 (random) versus 0.189 (local). Learned: most random filters are far from good ones; local search spends its tries near a good filter." Two or three entries are enough; a wrong prediction is the most useful kind.

6. What you must be able to explain

You may use AI for anything in this quest. In the defense, the examiner asks about your code. Be ready to:

  • work out a sigmoid and a cross-entropy value by hand for a small score (for example 0 or 2);
  • explain how your sigmoid and cross_entropy avoid overflow, and why clipping is wrong;
  • explain why the same seed gives the same filter, and what your local search does with a tie;
  • explain, with your own runs, why accuracy is flat and loss is not;
  • explain why 86% accuracy can mean a useless filter;
  • change your code, for example to add a new stopping rule or a third objective.

What to submit

With neugen submit, from your quest folder:

  • learn.py, learned_filter.json, your experiment script, and your filter.py if you changed it;
  • your AI transcripts or notes in .neugen/logs/ (neugen log <file>), if you used AI;
  • SUBMISSION.md (the starter kit has a template), short: 1. Accuracy versus loss: the two objectives compared on the same budget and seed, with numbers and real misclassified messages. 2. Why high accuracy can hide a useless filter: with the never-flag baseline and your filter's recall and precision. 3. Experiment notes: two or three entries of prediction, change, result, what you learned. 4. How I used and checked AI: what you asked, and how you checked the answers.

How you're graded

  1. Automated checks (neugen test runs the public ones): - sigmoid, cross_entropy and average_loss (all must pass), including huge scores. The hidden checks use more extreme values than the public ones. - random_search and local_search (all must pass), on a few hundred training messages with a small budget: the same seed gives the same result, different seeds give different results, and the result is better than the all-zero filter (loss) or at least as good as never flagging (accuracy). - Your learned filter, on the hidden test messages: average loss at most 0.23, catches at least 50% of the spam, flags at most 10% of the normal messages.
  2. Rubric review by an AI grader: your comparison of the objectives, the baseline and your experiment notes, and how you checked your work (and the AI's).
  3. Defense: a short conversation about your code and your experiments.

Suggested path (about 6 hours)

  1. Read this brief, Jurafsky and Martin 4.1 to 4.5 and the CS231n search sections (2 hours).
  2. Write random_search and local_search with accuracy; watch how they behave (1 hour).
  3. Write sigmoid, cross_entropy and average_loss; check values by hand and with huge scores (1 hour).
  4. Search with loss, compare, look at mistakes, save learned_filter.json (1 hour).
  5. Write SUBMISSION.md, run neugen test, submit (1 hour).

Tips

  • Compute the clues once. features.extract is the slow part. A search that tries 2,000 filters on 3,900 messages should extract each message's clues once, not 2,000 times.
  • Check by hand first: cross_entropy(0, 1) = 0.6931 and cross_entropy(2, 1) = 0.1269.
  • Test the extremes: try sigmoid(±1000) and cross_entropy(±800, 0 or 1) before you search.
  • Same budget, same seed when you compare two methods. Otherwise you compare luck.
  • Step size matters in local search. Try a few, and write down what you expect first.

Interface

# learn.py   (filter.py and features.py are provided; you may use your own filter.py)
def sigmoid(z: float) -> float: ...            # 1 / (1 + e^-z), no overflow for any finite z
def cross_entropy(score: float, label: int) -> float: ...
    # -log(sigmoid(score)) for spam (1), -log(1 - sigmoid(score)) for normal (0); natural log.
    # Computed from the raw score: cross_entropy(-800, 1) is about 800 (not inf, nan or capped).
def average_loss(messages, weights, bias) -> float: ...   # mean cross_entropy, features.extract
def random_search(messages, objective, budget, seed) -> (weights, bias): ...
def local_search(messages, objective, budget, step_size, seed) -> (weights, bias): ...
    # objective: "accuracy" (higher is better, threshold 0) or "loss" (lower is better)
    # budget: how many candidate filters to try; seed: use random.Random(seed)
    # local_search starts from weights [0, 0, 0, 0], bias 0

# learned_filter.json: the best filter your search found (chosen on validation loss)
{"weights": [4 numbers], "bias": number, "threshold": number}