A First Taste of Algorithms

Lab 8: Downhill

✦ ✦ ✦

Accompanies Chapter 8. Gradient descent gets built in ten lines and then systematically mistreated: the stride cranked through every fate the Diamond classifies, the two valleys claiming walkers by their birthplace, a line fitted to real points, and nearest neighbor sitting the parrot exam — scoring perfectly on what it memorized and honestly on what it never saw. One quiet arrival: numbers with decimal points, and their one sharp edge.

1. Floats, and their edge

Until now this book’s numbers were whole. Landscapes need floats — numbers with decimal points — and they mostly behave like numbers. Mostly. Run the classic:

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)

Not a bug — a confession. Floats are approximations: the machine stores numbers in binary, and 0.1 in binary is an infinite repeating fraction the machine must cut short, the way 1/3 = 0.3333… must be cut short in decimal. The error is tiny (look at it: seventeen places out) and almost never matters — except in one habit you must never form: testing floats with ==. Ask instead whether two floats are close: abs(a - b) < 0.000001. Adopt the habit now; today’s algorithms converge toward answers without ever exactly arriving, and == would wait forever for an arrival that isn’t coming.

2. The descent, in ten lines

The bowl f(x) = x², slope 2x, the chapter’s hand-run made executable:

def descend(slope, x, eta, steps):
    path = [x]
    for _ in range(steps):
        x = x - eta * slope(x)
        path.append(x)
    return path

def bowl_slope(x):
    return 2 * x

print(descend(bowl_slope, 2.0, 0.25, 6))

Check the first three steps against the chapter: 2, 1, 0.5, 0.25 — then watch the next three continue the halving. The function takes the slope, not the landscape: the walker never sees the terrain, only the tilt underfoot. That blindness is not an implementation shortcut. It is the algorithm’s entire epistemology, and everything that goes wrong today goes wrong because of it.

3. Every fate of the stride

The Diamond claims one number, 1 − 2η, decides everything on this bowl. Produce the full taxonomy:

for eta in [0.05, 0.25, 0.5, 0.75, 1.0, 1.05]:
    path = descend(bowl_slope, 2.0, eta, 20)
    print("eta =", eta, "  factor =", 1 - 2 * eta,
          "  x after 20 steps =", round(path[20], 6))

Predict each row before running, from the factor alone. Then the pictures — plot |x| against step for a chosen few (a log scale makes geometric behavior into straight lines; plt.semilogy is plt.plot with a logarithmic y-axis):

import matplotlib.pyplot as plt

for eta in [0.05, 0.25, 0.75, 1.05]:
    path = descend(bowl_slope, 2.0, eta, 20)
    sizes = [abs(x) + 1e-12 for x in path]      # +tiny: log of zero is forbidden
    plt.semilogy(sizes, label="eta = " + str(eta))
plt.xlabel("step")
plt.ylabel("|x|  (log scale)")
plt.legend()
plt.show()

Four straight lines, four slopes: crawl, brisk convergence, ringing convergence (print that path and look at the signs — the walker overshoots the bottom every step and lands closer anyway), and explosion. Find η = 0.5’s line by adding it: where did it go, and why does the +1e-12 in the code suddenly matter? One dial, every fate, exactly as the factor foretold.

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