A First Taste of Algorithms · Lab 8: Downhill

4. The two valleys

The chapter’s tilted world, f(x) = x⁴ − 3x² + x, slope 4x³ − 6x + 1:

def hills_slope(x):
    return 4 * x**3 - 6 * x + 1

def hills(x):
    return x**4 - 3 * x**2 + x

for start in [-2.0, -0.5, 0.5, 2.0]:
    path = descend(hills_slope, start, 0.02, 500)
    end = path[500]
    print("start", start, " ->  settles at", round(end, 4),
          "  floor value", round(hills(end), 4))

Predict the four destinies first (Fluency 1.5 did the two middle ones by sign alone). Then read the results: two walkers in the deep valley at −1.3008 (floor −3.514, the 7+7 valley), two in the shallow one at 1.1309 (floor −1.070, the grab-the-10 valley) — and the border between fates runs along the hilltop near 0.17, not at zero. Each walker, asked, would report complete success: slope zero, every direction uphill, work done. Print hills_slope(path[500]) for a shallow-valley walker and see its honest, useless certificate.

Now the chapter’s managed retreat, dice against valleys — many random birthplaces, keep the best:

import random
random.seed(8)

best_end = None
for _ in range(10):
    start = random.uniform(-2, 2)
    end = descend(hills_slope, start, 0.02, 500)[500]
    if best_end is None or hills(end) < hills(best_end):
        best_end = end
print("best of 10 random starts:", round(best_end, 4), " floor:", round(hills(best_end), 4))

Ten dice throws against a landscape the walker cannot see. Compute (Problem 2.4) what each throw’s chance of the deep valley is, and how rarely all ten can miss.

5. Learning a line

Now the real thing: descent applied to a loss. Hours studied and test scores, six students:

hours  = [1, 2, 3, 4, 5, 6]
scores = [16, 31, 47, 60, 78, 89]

def loss(w):
    total = 0
    for x, y in zip(hours, scores):        # zip: walk two lists in step
        total = total + (w * x - y) ** 2
    return total / len(hours)

def loss_slope(w):                         # the gradient from Problem 1.3
    total = 0
    for x, y in zip(hours, scores):
        total = total + 2 * (w * x - y) * x
    return total / len(hours)

path = descend(loss_slope, 0.0, 0.01, 60)
print("learned slope:", round(path[60], 3))

plt.plot([loss(w) for w in path])
plt.xlabel("step")
plt.ylabel("loss")
plt.show()

The loss curve — the signature picture of this entire field; every training run you will ever see reported is this plot, grown up — falls steeply, then levels as the strides self-brake near the floor. The learned slope says each hour of study buys about 15 points; check it crudely against the data by eye. Then two experiments of your own: re-run with η = 0.05 and watch the curve ring (you know its name now), and add one student who studied 2 hours and scored 95 — a prodigy or a typo — and report what one outlier does to the learned line (Problem 3.4 predicted this; here is the measurement).

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