A First Taste of Algorithms · Lab 8: Downhill

6. The parrot exam

Nearest neighbor, four lines as promised, on points with two features:

def nearest_label(examples, p):
    best = None
    for q, label in examples:
        d = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2
        if best is None or d < best[0]:
            best = [d, label]
    return best[1]

(Chapter 1’s linear search, distance for equality — and squared distance suffices, since comparing squares compares distances.) Build a little world. Each song is [loudness, tempo]; in this user’s library, morning and night songs come at every loudness — the signal lives entirely in the tempo, slow mornings and fast nights, with honest scatter at the border:

def make_song(kind):
    if kind == "morning":
        return [[random.uniform(1, 9), random.uniform(60, 110)], "morning"]
    else:
        return [[random.uniform(1, 9), random.uniform(105, 160)], "night"]

random.seed(88)
training = [make_song("morning") for _ in range(20)] + [make_song("night") for _ in range(20)]
testing  = [make_song("morning") for _ in range(50)] + [make_song("night") for _ in range(50)]

Now the two exams — the one it memorized, and the one it never saw:

def score(examples, exam):
    right = 0
    for p, truth in exam:
        if nearest_label(examples, p) == truth:
            right = right + 1
    return right / len(exam)

print("training score:", score(training, training))
print("test score:    ", score(training, testing))

Predict both before running. The first is 1.0 — necessarily, eternally, by construction (each exam point finds itself at distance zero); write one sentence on why that score is therefore worth nothing. The second is the honest number — high here, because the world really is learnable and the features really do carry the signal — and the gap between the two numbers is the chapter’s last section in miniature. You have administered the parrot exam, and this learner passed it. Keep the grader; Chapter 9’s learner takes the same exam.

Break it

Predict first. Run second. Explain any gap third.

1. The walker on the hilltop. The two-valley landscape’s hill crests where the slope is exactly zero — solve nothing, just start a walker at 0.16993844331159128 (the lab hands you the cursed coordinate) and descend. Predict its journey. Then nudge it: start at 0.1699384 (seven digits). Predict again, run, and explain the difference in fates using §1’s confession about floats. A zero-slope point is a trap of measure zero — but what does “measure zero” feel like in a world of seventeen decimal places, and which of the two runs is the one real training jobs experience?

2. Convergence vs. arrival. On the bowl with η = 0.25, descend from 2.0 and test path[k] == 0.0 for k = 20, 50, 200. Predict the three answers. Then test abs(path[k]) < 1e-6 instead. State the rule you’ll follow for the rest of your life about asking whether an iterative method has “finished” — and connect it to why §1 banned == before you’d written a single algorithm that needed the ban.

3. The poisoned example. In §6, flip exactly one training label (pick a morning song, call it “night”). Predict both scores’ movements before running: which is guaranteed not to drop, and why? Then measure the test score’s change, and — using nearest_label as a probe — map the poisoned point’s island: classify a small grid of points around it and find the territory one lie governs. The chapter’s Figure 8.1 island, grown in your own lab; finish with one sentence on what a learner that cannot doubt its examples does with a lie.

4. Features are destiny. Rebuild §6’s world with the tempo feature corrupted: multiply every tempo by 0.001 (a units botch — somebody filed kilo-beats-per-minute). The labels are untouched, the algorithm is untouched, and the information is all still present — every tempo is exactly recoverable. Predict the test score anyway. Then run it and explain the collapse to a coin flip: in nearest_label’s distance sum, who is doing all the talking now, who has been whispered into silence, and why does the only feature that knows anything no longer get a vote? Try 0.01 too and watch the score land between coin-flip and honest — silencing comes in degrees. Then repair it without touching the data: rescale inside the distance until both features speak at comparable volume. The lesson — a learner’s competence lives as much in the representation as in the algorithm — is Problem 2.3’s, now measured; it is also, one chapter early, the reason Chapter 9 will spend real care on how text becomes numbers before any learning begins.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses