{ "cells": [ { "cell_type": "markdown", "id": "297bb8e8", "metadata": {}, "source": [ "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/MeiraDavidson/compute_module1/blob/main/notebooks/lab_08_downhill.ipynb)\n\n", "# Lab 8: Downhill\n", "\n", "*From* **A First Taste of Algorithms — and the Machines That Learn** *(The Curious Family Library). A computational lab: run the cells in order. A few labs end with a deliberately broken “Break it” cell — that one is meant to fail, and seeing how is the point.*" ] }, { "cell_type": "markdown", "id": "e3715594", "metadata": {}, "source": [ "*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.*\n", "\n", "## 1. Floats, and their edge\n", "\n", "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:" ] }, { "cell_type": "code", "execution_count": null, "id": "663155fe", "metadata": {}, "outputs": [], "source": [ "print(0.1 + 0.2)\n", "print(0.1 + 0.2 == 0.3)" ] }, { "cell_type": "markdown", "id": "708e48c6", "metadata": {}, "source": [ "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.\n", "\n", "## 2. The descent, in ten lines\n", "\n", "The bowl f(x) = x², slope 2x, the chapter's hand-run made executable:" ] }, { "cell_type": "code", "execution_count": null, "id": "bd6e6b14", "metadata": {}, "outputs": [], "source": [ "def descend(slope, x, eta, steps):\n", " path = [x]\n", " for _ in range(steps):\n", " x = x - eta * slope(x)\n", " path.append(x)\n", " return path\n", "\n", "def bowl_slope(x):\n", " return 2 * x\n", "\n", "print(descend(bowl_slope, 2.0, 0.25, 6))" ] }, { "cell_type": "markdown", "id": "ece853a5", "metadata": {}, "source": [ "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.\n", "\n", "## 3. Every fate of the stride\n", "\n", "The Diamond claims one number, 1 − 2η, decides everything on this bowl. Produce the full taxonomy:" ] }, { "cell_type": "code", "execution_count": null, "id": "4cd8e912", "metadata": {}, "outputs": [], "source": [ "for eta in [0.05, 0.25, 0.5, 0.75, 1.0, 1.05]:\n", " path = descend(bowl_slope, 2.0, eta, 20)\n", " print(\"eta =\", eta, \" factor =\", 1 - 2 * eta,\n", " \" x after 20 steps =\", round(path[20], 6))" ] }, { "cell_type": "markdown", "id": "58a6cfc9", "metadata": {}, "source": [ "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):" ] }, { "cell_type": "code", "execution_count": null, "id": "1bab8d24", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "for eta in [0.05, 0.25, 0.75, 1.05]:\n", " path = descend(bowl_slope, 2.0, eta, 20)\n", " sizes = [abs(x) + 1e-12 for x in path] # +tiny: log of zero is forbidden\n", " plt.semilogy(sizes, label=\"eta = \" + str(eta))\n", "plt.xlabel(\"step\")\n", "plt.ylabel(\"|x| (log scale)\")\n", "plt.legend()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "e5ed74db", "metadata": {}, "source": [ "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.\n", "\n", "## 4. The two valleys\n", "\n", "The chapter's tilted world, f(x) = x⁴ − 3x² + x, slope 4x³ − 6x + 1:" ] }, { "cell_type": "code", "execution_count": null, "id": "a8997ad8", "metadata": {}, "outputs": [], "source": [ "def hills_slope(x):\n", " return 4 * x**3 - 6 * x + 1\n", "\n", "def hills(x):\n", " return x**4 - 3 * x**2 + x\n", "\n", "for start in [-2.0, -0.5, 0.5, 2.0]:\n", " path = descend(hills_slope, start, 0.02, 500)\n", " end = path[500]\n", " print(\"start\", start, \" -> settles at\", round(end, 4),\n", " \" floor value\", round(hills(end), 4))" ] }, { "cell_type": "markdown", "id": "7cb9fad3", "metadata": {}, "source": [ "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.\n", "\n", "Now the chapter's managed retreat, dice against valleys — many random birthplaces, keep the best:" ] }, { "cell_type": "code", "execution_count": null, "id": "c451af91", "metadata": {}, "outputs": [], "source": [ "import random\n", "random.seed(8)\n", "\n", "best_end = None\n", "for _ in range(10):\n", " start = random.uniform(-2, 2)\n", " end = descend(hills_slope, start, 0.02, 500)[500]\n", " if best_end is None or hills(end) < hills(best_end):\n", " best_end = end\n", "print(\"best of 10 random starts:\", round(best_end, 4), \" floor:\", round(hills(best_end), 4))" ] }, { "cell_type": "markdown", "id": "3707c98f", "metadata": {}, "source": [ "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.\n", "\n", "## 5. Learning a line\n", "\n", "Now the real thing: descent applied to a *loss*. Hours studied and test scores, six students:" ] }, { "cell_type": "code", "execution_count": null, "id": "8a8d3280", "metadata": {}, "outputs": [], "source": [ "hours = [1, 2, 3, 4, 5, 6]\n", "scores = [16, 31, 47, 60, 78, 89]\n", "\n", "def loss(w):\n", " total = 0\n", " for x, y in zip(hours, scores): # zip: walk two lists in step\n", " total = total + (w * x - y) ** 2\n", " return total / len(hours)\n", "\n", "def loss_slope(w): # the gradient from Problem 1.3\n", " total = 0\n", " for x, y in zip(hours, scores):\n", " total = total + 2 * (w * x - y) * x\n", " return total / len(hours)\n", "\n", "path = descend(loss_slope, 0.0, 0.01, 60)\n", "print(\"learned slope:\", round(path[60], 3))\n", "\n", "plt.plot([loss(w) for w in path])\n", "plt.xlabel(\"step\")\n", "plt.ylabel(\"loss\")\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "a725e81d", "metadata": {}, "source": [ "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).\n", "\n", "## 6. The parrot exam\n", "\n", "Nearest neighbor, four lines as promised, on points with two features:" ] }, { "cell_type": "code", "execution_count": null, "id": "bbd83265", "metadata": {}, "outputs": [], "source": [ "def nearest_label(examples, p):\n", " best = None\n", " for q, label in examples:\n", " d = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2\n", " if best is None or d < best[0]:\n", " best = [d, label]\n", " return best[1]" ] }, { "cell_type": "markdown", "id": "aecd9c75", "metadata": {}, "source": [ "(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:" ] }, { "cell_type": "code", "execution_count": null, "id": "67343c6e", "metadata": {}, "outputs": [], "source": [ "def make_song(kind):\n", " if kind == \"morning\":\n", " return [[random.uniform(1, 9), random.uniform(60, 110)], \"morning\"]\n", " else:\n", " return [[random.uniform(1, 9), random.uniform(105, 160)], \"night\"]\n", "\n", "random.seed(88)\n", "training = [make_song(\"morning\") for _ in range(20)] + [make_song(\"night\") for _ in range(20)]\n", "testing = [make_song(\"morning\") for _ in range(50)] + [make_song(\"night\") for _ in range(50)]" ] }, { "cell_type": "markdown", "id": "4bb0533c", "metadata": {}, "source": [ "Now the two exams — the one it memorized, and the one it never saw:" ] }, { "cell_type": "code", "execution_count": null, "id": "a29d10c7", "metadata": {}, "outputs": [], "source": [ "def score(examples, exam):\n", " right = 0\n", " for p, truth in exam:\n", " if nearest_label(examples, p) == truth:\n", " right = right + 1\n", " return right / len(exam)\n", "\n", "print(\"training score:\", score(training, training))\n", "print(\"test score: \", score(training, testing))" ] }, { "cell_type": "markdown", "id": "0ce161e2", "metadata": {}, "source": [ "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.\n", "\n", "## Break it\n", "\n", "Predict first. Run second. Explain any gap third.\n", "\n", "**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?\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "\n", "\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }