The machine learns

The bot tournament of the last chapter ended with an awkward admission. Search and alpha-beta pruning are mechanics, but the feel for a position, the evaluation function, was tuned into Deep Blue by people over many years. For Go nobody managed to write one at all. What do you do when a person can’t write down the rule? Here is a problem easier than Go: handwritten digits, each one put on paper by someone filling in a form.

Each digit is a picture of 16 by 16 pixels, that is, 256 numbers from 0 (paper) to 1 (ink). X is a numpy table of 3823 such rows, and y holds the right answers, which digit is in each row. The digits were written by some thirty people. This open dataset was collected at Boğaziçi University in Istanbul by Ethem Alpaydın and Cenk Kaynak, and since 1998 it has been in the UCI Machine Learning Repository under the CC BY 4.0 license.

Your assignment: write a function that tells a four from a nine. In your head will do. “A nine has a closed loop at the top,” but in half the fours in the picture the top has closed up too. “A four has a crossbar,” but this nine’s tail is bent, and it looks like a crossbar. Every rule breaks on somebody’s handwriting, and every patch turns up new exceptions. You tell these digits apart instantly and can’t explain how. It is the same wall we hit with the evaluation function for Go: the knowledge is there, the recipe isn’t.

The way out turns everything we have done for sixty chapters upside down. The rule isn’t written; it is fitted. You take a function with adjustable numbers and turn those numbers until the function starts giving the right answers on the examples. This is machine learning. The function with knobs is called a model, the knobs themselves are its weights, and the examples with right answers make up the training set. In the language of Chapter 10, training is a function that takes examples and returns another function: the one that answers.

This chapter is a training camp, and you are the coach. A sports coach often can’t do the thing they teach, but sees the result and knows how far the athlete missed. You will need three things: a trainee with knobs, exercises with answers, and a measure of the miss. There will be four trainees, from simple to complex: a straight line, a perceptron, a small network, and a bigger network that will read your own handwriting at the end. You also need a rule for which way to turn the knobs; you’ll get it in the first workout.

Workout 1. A straight line

We’ll start with a trainee that has only two knobs. In Chapter 8 we checked Zipf’s law: on a plot with logarithmic scales the word frequencies of War and Peace fell almost on a straight line, and we drew it by eye: $65{,}000 / r$. This time the machine will find the line. Plot the points: $x$ is the base-10 logarithm of a word’s rank, $y$ the logarithm of its frequency. The model is the line $y = w x + b$: the weight $w$ sets the slope, and $b$ the height.

Measuring the miss

To train anything, you have to be able to say how bad a line is. For each point the miss is $w x_i + b - y_i$: how far the line passes above or below the point. Misses come with either sign, so they are squared and averaged:

$$L(w, b) = \frac1n \sum_{i=1}^{n} \bigl(w x_i + b - y_i\bigr)^2.$$

Such a number is called a loss function: the smaller it is, the better the model. The square was chosen for good reasons. It is never negative, it punishes one big miss harder than several small ones, and it is smooth: it has a derivative, and we are about to need that. Legendre and Gauss were already minimizing sums of squared misses in the early nineteenth century. For a line there is even a ready-made formula for the best $w$ and $b$, derived in “Mathematics, the Queen of the Sciences,” in the chapter on the best line. But the network we’ll finish with has no such formulas, and we need a method that does without them.

Going downhill

Picture the loss function as terrain: the two horizontal axes are the weights $w$ and $b$, and the height is the loss. We stand at some point and want to go down. We can’t see the whole map, but we can feel the slope underfoot. The derivative $\partial L/\partial w$ says how fast the loss grows if $w$ is increased a little, and $\partial L/\partial b$ says the same about $b$. Together these two derivatives make the gradient, an arrow pointing in the direction of steepest ascent. So the step should go against it:

$$w \leftarrow w - \eta\,\frac{\partial L}{\partial w}, \qquad b \leftarrow b - \eta\,\frac{\partial L}{\partial b}.$$

This is gradient descent, the walker in the fog from the math course. The number $\eta$ (the Greek letter eta) is the learning rate. The derivatives of our loss function follow from the rules you learned in school: the derivative of a square is twice the expression inside, times the derivative of the inside:

$$\frac{\partial L}{\partial w} = \frac2n \sum_{i} \bigl(w x_i + b - y_i\bigr)\,x_i, \qquad \frac{\partial L}{\partial b} = \frac2n \sum_{i} \bigl(w x_i + b - y_i\bigr).$$

Take 38 points of the Zipf plot, at ranks 1, 2, 3, 4, 5, 6, 8, 10, 13 and so on up to 10,000, about the same number for every order of magnitude, and start with the horizontal line $w = b = 0$.

The first step is clumsy: the line tips upward, because all the points lie above zero and the descent starts by pulling the line toward them. After a hundred steps it is nearly in place, and after a thousand it no longer changes in the third decimal place: $w \approx -1.06$, $b \approx 4.87$. The last line of the output turns them back into a law: the word at rank $r$ occurs about $74{,}000 / r^{1.06}$ times. Our eyeballed line from Chapter 8 wasn’t bad, but the machine’s line has a loss about a third lower: 0.0154 against 0.0240. Nobody told it the slope or the height; it had only the points and the measure of the miss.

Now set rate = 0.16 and run it again. After a hundred steps the weights are in the tens of thousands, and after a thousand they are numbers fifty digits long. The step has become longer than the pit: the descent jumps over the bottom, lands on the opposite slope higher than it was before, and with every jump flies off farther. The math course says where the boundary lies: for a quadratic pit the step has to be smaller than $2/\lambda$, where $\lambda$ is the curvature of the pit in its steepest direction. Our pit has $\lambda \approx 13.3$, so the boundary is about $0.15$. Here is the terrain seen from above.

The map explains why even a good step crawls: the pit is long and narrow, like a ravine. The weight $w$ is multiplied by $x$, which runs from 0 to 4, while $b$ is multiplied by one, so a shift in $w$ moves the line more than the same shift in $b$, and the slopes across the ravine are much steeper than along it. A step that is safe on the steep slopes is too short for the gently sloping floor. The cure is to subtract the mean from $x$. Then the slope and the height stop getting in each other’s way, the pit becomes nearly round, and the descent reaches the bottom in a couple of dozen steps. This grew into a rule that everyone who trains models follows: before training, bring the inputs to comparable scales. You’ll need it in the first task of the chapter.

Workout 2. The perceptron

The line predicted a number. The next trainee has to choose: a four or a nine, yes or no. This trainee is the oldest in the camp.

The perceptron never did learn to walk or talk. But what it could do, it can still do today. A perceptron is a weighted sum of its inputs plus a bias: $s = w_1 x_1 + w_2 x_2 + \ldots + w_n x_n + b$. If $s > 0$, the answer is “yes” (+1); otherwise it is “no” (−1). On a plane with two inputs this is the line $w_1 x_1 + w_2 x_2 + b = 0$: “yes” on one side of it, “no” on the other. A 16-by-16 digit has 256 inputs, and instead of a line we get a flat boundary in 256-dimensional space, but the idea is the same.

Rosenblatt’s learning rule fits on one line. Take an example $x$ with the right answer $t = \pm 1$. If the perceptron answered correctly, do nothing. If it was wrong, add the example to the weights with the sign of the right answer: $w \leftarrow w + t\,x$, $b \leftarrow b + t$. After such a correction the sum on this example changes by $t\,(|x|^2 + 1)$, which moves it toward the right answer. The perceptron learns only from its mistakes, and on the plane you can see each mistake turn the line.

Now for the challenge from the start of the chapter, fours against nines. One full pass through the training set is called an epoch. We’ll count how many mistakes the perceptron makes per epoch, and at the end test it on digits it has never seen, written by 13 other people.

The expression w @ x is the sum of the products of weights and pixels, our $s$ without the bias; numpy computes it in a single operation. In the first epoch the perceptron makes 38 mistakes, in the second 13, and from the fifth on, only a handful. It never gets down to zero by the tenth epoch: a few digits in the set are written so that no simple boundary separates them. Yet on the exam, on the handwriting of thirteen strangers, it is right more than 99 times out of 100. The rule we failed to state is written down in 257 numbers.

You can see them: the pictures under the cell are the weights, laid out back into a 16-by-16 square. On the left are the pixels with positive weights: ink in them pushes the answer toward “four.” On the right are those with negative weights, which vote for “nine.” The strongest votes for nine are in the top rows, where a nine has its closed arc. The middle and the left side vote for four, where it has its crossbar and its left stroke. These are the rules we tried to put into words at the start of the chapter, only written in numbers and adjusted for hundreds of different hands.

If a boundary can be drawn, the perceptron will find it. That is a theorem, and it has one of the shortest proofs in the course.

The theorem was proved in the early 1960s; the best-known proof, this one, was published by Albert Novikoff in 1962. The theorem says nothing about what happens when no separating boundary exists.

A gate it can never learn

In Chapter 29 you built “exclusive or” out of gates: one when the inputs differ. Here are the four rows of the XOR truth table, for the perceptron to learn.

Four mistakes out of four, and after every epoch the weights come back to where they started: the perceptron walks in a circle and will go on walking forever. Press “Steps” to see the whole circle. Neither the order of the examples nor the learning rate is to blame; the problem itself is.

Geometrically it is obvious at a glance: the points (0, 1) and (1, 0) lie on one diagonal of the square, (0, 0) and (1, 1) on the other, and no line can leave one diagonal on one side and the other diagonal on the other. And XOR is everywhere in a computer: it computes the low bit of the adder, the circuit on which all of the processor’s arithmetic stands.

Workout 3. A network

A hint on how to get around the wall comes from Chapter 29 again. XOR can be written in disjunctive normal form: $a \oplus c = (\lnot a \land c) \lor (a \land \lnot c)$. Each of the three parts, “not $a$ and $c$,” “$a$ and not $c$,” and “or,” can be separated by a line, which means a perceptron can compute it. Put two perceptrons on the inputs and a third on their outputs. The result is a neural network with a hidden layer, “hidden” because the examples contain no answers for its neurons: what they should compute, the network has to invent by itself.

But Rosenblatt’s rule doesn’t work here. It knows how to correct a neuron that got its own answer wrong. But what did a hidden neuron get wrong, if the right answer is known only for the output? We need gradient descent, as in the first workout: a loss function of all nine weights of the network, and a step against the gradient. The obstacle is the step function. A perceptron answers +1 or −1, and if you turn a weight slightly, the answer doesn’t change at all: the derivative is zero almost everywhere, and there is no slope to follow. So the step is smoothed out: instead of the sign of the sum, the neuron outputs $\sigma(s) = 1/(1 + e^{-s})$, a smooth passage from 0 to 1. A function like this is called an activation function. Now the loss is a smooth function of all the weights.

What is left is to compute the gradient. The network’s output depends on the hidden layer’s weights through a chain: weight → the hidden neuron’s sum → its output → the output neuron’s sum → the answer → the loss. The derivative along such a chain is given by the chain rule: it is the product of the derivatives of the links. It is most convenient to compute from the end: first the derivative of the loss with respect to the answer, then with respect to the output neuron’s sum, then, multiplying by the weight of each connection, with respect to the outputs of the hidden neurons, and so on, layer by layer, back to the input. The error flows backward through the network, hence the name: backpropagation. All it costs is one more pass through the network, the same size as the forward one, so the gradient with respect to thousands or billions of weights costs only a few times more than the answer itself.

The derivative of the sigmoid is written in terms of the sigmoid itself, $\sigma'(s) = \sigma(s)\,(1 - \sigma(s))$, which is where the factors y * (1 - y) and h * (1 - h) come from. After three thousand steps the output is close to 0, 1, 1, 0. The middle columns are more interesting. The first hidden neuron lights up only on the input (0, 1): it has become the gate “not $a$ and $c$.” The second lights up only on (1, 0): “$a$ and not $c$.” The output switches on when either of them is lit, and that is “or.” The network has put together the disjunctive normal form of Chapter 29 by itself. Nobody told it which gates it needed; it found them by descent.

Change default_rng(1) to default_rng(5). The loss gets stuck around 0.17, and the output on three of the four inputs sits around a third. The descent has come down into a pit that isn’t the deepest one, and it can’t climb out: the slope underfoot goes up in every direction. A network’s smooth loss surface can have many such pits. In practice what helps is a random start, another run, and spare neurons: oddly enough, a network with neurons to spare runs into bad pits less often. This will come in handy in the XOR task at the end of the chapter.

Workout 4. Ten digits

Now in earnest: all ten digits at once. The input is 256 pixels, the hidden layer has 64 neurons, and the output has ten, one per digit. To get an answer out of ten outputs, their sums $z_0, \ldots, z_9$ are turned into probabilities by the softmax function:

$$p_k = \frac{e^{z_k}}{e^{z_0} + e^{z_1} + \ldots + e^{z_9}}.$$

All the $p_k$ are positive, they add up to one, and a larger sum gets a larger probability. The network’s answer is the digit with the highest probability. The loss on an example is $-\ln p$ of the right digit: if the network gave the right answer a probability of 0.9, the loss is 0.1; if 0.01, the loss is 4.6. It is a measure of surprise: how surprised the network was by the right answer. People like it for another reason too. The derivative of this loss with respect to the sums of the output neurons is as simple as can be: $p_k - 1$ for the right digit and $p_k$ for the others. “What it gave minus what was needed” is where the backward pass begins.

Two more changes. In the hidden layer the sigmoid is replaced by the function $\max(0, s)$, called ReLU: negative values become zero, positive ones pass through unchanged. Its derivative is 0 or 1, it is cheap to compute, and the signal doesn’t fade as it passes through many layers; today it is the most common activation function. And the gradient is computed on a batch of 32 random examples rather than on all 3823 at once: the estimate is noisy but cheap. This is called stochastic gradient descent; it takes 120 steps per epoch.

The line dz[np.arange(len(batch)), labels] -= 1 subtracts one in each example’s column for its right digit, and what comes out is “what it gave minus what was needed.” Then comes the backward pass: the gradient with respect to W2 is the product of the hidden layer’s outputs and the output errors, and the hidden layer’s error is the output errors passed back through W2 and through the derivative of ReLU (h > 0).

In a fraction of a second the network of 17,098 weights reaches 98–99% on the training digits and about 95% on the exam. Its mistakes are under the cell. Some of them are forgivable: a person, too, might not read a few of these digits at first glance. But half the mistakes under the cell are clear sevens that the network took for nines and fives. They are written very much alike, with the same hook on the left of the top stroke, probably by one hand. And not one of them is crossed in the middle, while in the training set nine sevens out of ten are crossed: the network has hardly ever seen a seven without the bar. We’ll come back to this.

Nearly all of the network’s time goes into matrix multiplications, five for every step: two in the forward pass and three in the backward one. That is why networks are trained on graphics cards, which, as we saw in Chapter 35, can do the same operation on thousands of numbers at once.

The exam

We hold the exam on other people’s digits for the same reason a test in school doesn’t use problems from the textbook: a student who has done them all may have memorized the answers. With a model it is the same. Here is an experiment: train the same network on 20, 50, 200 and 1000 examples and on all 3823, and each time test it both on the training examples and on the exam.

On twenty examples, two per digit on average, the network knows every one of them: 100% in training. On the exam it gets about 60%. This is overfitting: seventeen thousand weights are plenty to memorize twenty pictures with all their accidental features (the slant, the thickness, a blot), and the model memorizes them instead of looking for what they have in common. The more examples, the harder it is to cram and the smaller the gap: on a thousand it is about six percentage points, on the whole set three and a half. (Sixty percent from twenty examples isn’t bad either, by the way: random guessing would give ten.)

The camp’s main rule is this: some of the examples are set aside until the end and never shown to the model. They form the test set. Only accuracy on it tells you how the model will work on new data. Accuracy on the training examples tells you only how well the model has memorized them. A test set is easy to spoil, and it is hard to tell when it has been spoiled. If you try twenty versions of a network and keep the one that did best on the exam, the exam has become part of training: you have fitted the model to these 1797 digits. That is why settings are chosen on a third, validation part, and the exam is taken once. The authors of our dataset had such a part: of the 3823 digits by thirty people, they trained models on half, kept 946 digits for validation, and used the 1797 digits of thirteen other people as the exam. To keep things simple we train on all 3823, so this chapter has no validation part.

Even this rule has its limits. A model learns what is in the data, not what we meant: it confuses the sevens in an unfamiliar hand from the last section with nines. It can be worse. In 2018 Reuters reported that starting in 2014, Amazon had tried rating job applicants’ résumés with a model trained on the résumés sent to the company over ten years. Most of them had come from men, and by 2015 it turned out that the model marked down résumés that contained the word “women’s.” People tried to fix the model, but it could never be relied on, and the project was dropped. A test set won’t catch a problem like this: it comes from the same data, with the same skew, and on it the model looks accurate.

Your handwriting

The last exam is the strictest. The dataset doesn’t contain a single digit written by you. Train the network on the server and draw a digit with your finger or the mouse.

Most likely the network recognizes your digits, although it has never seen any of them. With boxy digits like those on a calculator display, its confidence drops. Our networks took a boxy six for a five on one run and for a four on another, and sometimes gave a square zero a one-in-four chance of being a five: the dataset has no digits like these. The network learns anew from a random start each time, so your answers may differ. It is the same story as with the résumés, in miniature: the model knows the handwriting it learned from.

It can. Nobody wrote the rule that tells a four from a nine: descent fitted it on 3823 examples, and the network reads the handwriting of people it has never seen. The network invented the gates for XOR by itself, and nobody told it which ones it needed. In this sense the machine has learned what it wasn’t taught: a rule that was neither in the program nor in the programmer’s head.

But this “by itself” has strict limits. The machine learns only what is in the examples and what the loss function measures. It generalizes to things that are new but resemble what it has seen, such as other people’s handwriting, and it easily goes wrong on what doesn’t: a boxy digit from a calculator display, a résumé not written the way past ones were. So the machine does have a teacher: the data. This teacher explains no rules, but it decides what the machine gets to see.

A model of language

One thing remains to explain: how programs that write text work. In Chapter 8 we already built one: a dictionary of which word came after which, and a random choice of the next. That was a language model, a function that takes the beginning of a text and gives the probabilities of the next piece. We’ll make it a little sharper: it will guess the next character from the four before it. We’ll train it on the first 90% of the novel and hold out the last 10%.

Counter is a counting dictionary: a missing key has the value 0, and most_common(3) returns the three most frequent. defaultdict(Counter) creates an empty counter for each new context by itself. After “ndre” the model has seen a “w” 1123 times (Andrew), a “d” 145 times (hundred) and an “s” 29 times (undress). What it writes isn’t Tolstoy, but it already contains whole words, “sonya” and “dolokhov” among them, and near-words such as “thouted” and “attalions.” The model knows only what followed four characters, and its output still looks like English at a glance.

We’ll compare such models with an exam on the held-out 10% of the novel. The measure of surprise is the same as for the network with the digits, only in bits rather than natural logarithms: $-\log_2 p$ of the character that stands in the text. Averaged over a text, it gives the same entropy as in the chapter on compression: with a model that is surprised by 2 bits per character, the text can be compressed to 2 bits per character. Below, models with contexts of zero to six characters sit the exam.

With no context, the model knows only the frequencies of letters: 4.24 bits. Each character of context helps: 3.39, 2.72, 2.14, 1.87 bits. Five characters gain nothing over four (1.87 again, a hair worse in the third decimal), and six are clearly worse: 2.06. This is overfitting again, now in a language model: the novel has hundreds of thousands of six-character contexts, most of them seen once or twice, and the model memorizes chance continuations instead of patterns. The small addition of 0.01 in the formula is there for the same reason: without it, a combination that never occurred in the training text would get probability zero and infinite surprise.

Large language models follow the same plan. Given a context, the model gives the probabilities of the next token, a character, a word or a piece of a word; the loss is the average surprise on texts; training is gradient descent with backpropagation. There are three differences. Their context is thousands of tokens instead of four characters. Instead of a table of counts there is a network: a table knows nothing about a context it hasn’t seen, while a network generalizes, the way it generalized handwriting. To a network, “prince andrew said” and “princess mary said” are alike, and what it learned about one helps with the other. And the scale: billions of weights and as much text as can be collected. Training such models is only possible on powerful graphics cards. And the model predicts a plausible continuation; nobody taught it to check whether that continuation is true. Coherent text doesn’t yet mean understanding: remember the ELIZA effect.

You can walk this road yourself in the Sprout course on this site. It starts where we stop, with counting letters, and chapter by chapter, by way of the measure of surprise, descent, backpropagation, tokens and attention, it arrives at a transformer with 17 million weights that writes stories right in your browser.

Tasks

Four tasks, four trainees. Each has a trap that people usually walk into the first time they train models: a ravine, a boundary with no margin, slow distances, and a pit the descent can’t climb out of.

Write fit_line(xs, ys): use gradient descent to find the weights $w$ and $b$ of the line $y = w x + b$ with the smallest mean squared miss, and return the pair (w, b). The tests compare your loss with the loss of the best line: you may fall short of it by at most 1%. The data can be awkward: years from 1900 to 2020, apartment prices in the millions, all the $x$ equal, a hundred thousand points that must be handled in under two seconds. Ready-made formulas, np.polyfit, np.linalg.lstsq and matrix inversion, are not allowed, and the tests check for them.

Run the tests: on the years the weights fly apart. With $x \approx 2000$ the curvature of the pit along $w$ is about $2x^2 = 8$ million, and a safe step is smaller than $2/(8 \cdot 10^6)$. With a step like that, $b$ won’t budge even in a million steps. It is the ravine from the widget, only very narrow.

Bring $x$ to scale: $u = (x - m)/s$, where $m$ is the mean and $s$ is the standard deviation. Look for the line $y = w' u + b'$: its pit is round, and with a step of 0.5 the descent converges in a handful of steps. Then convert it back to the original $x$: $w = w'/s$, $b = b' - w' m / s$.

If all the $x$ are equal, $s = 0$ and you can’t divide. A horizontal line at the height of the mean $y$ will do. And for a hundred thousand points, replace the sums in the loop with numpy operations: np.mean(miss * u).

Once $x$ is replaced by $u$, both curvatures of the loss function equal 2: $\partial^2 L/\partial w^2 = 2\,\overline{u^2} = 2$ and $\partial^2 L/\partial b^2 = 2$, and the mixed derivative is $2\,\bar u = 0$. The pit has become round, and the step $\eta = 0.5 = 1/2$ lands on the bottom in a single step, after which the descent stays put. Without normalization the same problem needs a step millions of times smaller. Normalizing the inputs is the first thing done before training any model, from a line to a network with billions of weights.

Write train_perceptron(points, labels, epochs). points is a list of points (lists of numbers of the same length), and labels holds the answers, +1 and −1. The function trains a perceptron by Rosenblatt’s rule, starting from zero weights, and returns the pair (w, b), a list of weights and a bias, with which every point lies strictly on its own side: $t\,(w \cdot x + b) > 0$. If no such boundary turns up within epochs epochs, return None. The tests include XOR, the digits from the chapter, and points with a very narrow margin.

The starter has two problems. The first is the comparison sign: for the starter, a point right on the boundary ($s = 0$) isn’t a mistake, so the zero weights at the start count as right for every point at once. The second: it never stops and never says that there is no boundary.

Count the mistakes in each epoch. An epoch without a single mistake means the boundary is found: return the weights. If the epochs run out and there are still mistakes, return None: by the convergence theorem, if a boundary with a reasonable margin existed, the perceptron would have found it.

The comparison <= 0 instead of < 0 is no small matter: without it a perceptron with zero weights considers itself right about everything and learns nothing. The narrow margin shows what the theorem is saying: the number of mistakes grows like $(R/\gamma)^2$, and with a margin of 0.01 the perceptron needs dozens of epochs (64 in the test), even though a boundary exists. The theorem doesn’t promise the converse, though: “not found in 1000 epochs” doesn’t yet prove that there is no boundary; perhaps the margin is very small. So an empty answer from the function means “not found,” and nothing more.

The simplest learner generalizes nothing: it memorizes all the examples, and when asked a question, it answers the way similar examples answered. Write knn_predict(train_x, train_y, test_x, k): for each row of test_x, find the $k$ nearest rows of train_x (the distance is the ordinary one, the square root of the sum of squared differences) and return the label that occurs most often among them. If several labels are tied, the one whose representative is nearest wins. The arguments are numpy arrays, and the answer is a list or array of labels. The main test: all 1797 exam digits against the 3823 training ones, with an accuracy of at least 97% and in no more than three seconds.

The starter has the right idea but is slow: 1797 × 3823 distances over 256 pixels each is almost two billion operations in a Python loop. It does break ties correctly, by the way: neighbors go into the dictionary from nearest to farthest, and max picks the first of equal ones. Keep that property.

All the distances at once come from a single matrix multiplication: $|a - b|^2 = |a|^2 - 2\,a \cdot b + |b|^2$. A column of $|a|^2$ over the exam rows, a row of $|b|^2$ over the training rows, and the matrix test_x @ train_x.T add up to a 1797 × 3823 table. You don’t need the square root: it doesn’t change the order of the neighbors.

np.argsort(d, axis=1)[:, :k] gives the indices of the $k$ nearest in each row, already ordered from nearest. The vote count can stay in an ordinary loop: there are only 1797 × $k$ votes.

About 98%, more than our network gets. On small data simple methods are strong, and it always pays to compare against them: a complicated model has to beat the neighbors, or what is it for? But the neighbors have a price of their own. To answer, they need the whole training set and a comparison with every example; the network keeps 17,000 numbers and answers with two matrix multiplications. On a million photographs the neighbors can no longer cope, either in memory or in accuracy: a pixel-by-pixel distance doesn’t notice that the cat has moved half a frame over.

Write train_gate(table, seed): train a network with a hidden layer to act as a gate with two inputs. table holds the four required answers for the inputs (0, 0), (0, 1), (1, 0), (1, 1), for example [0, 1, 1, 0] for XOR; seed is the seed for the random start. Return the parts of the network, (W1, b1, w2, b2): W1 of size 2 × $k$, b1 and w2 of $k$ numbers each, and b2 a single number. The tests compute the output $\sigma(\sigma(x W_1 + b_1)\,w_2 + b_2)$ themselves and require it to be on the right side of 0.5 for all four inputs. All sixteen gates are checked, and XOR and equality are checked from twenty different starts.

The starter is the network from the XOR section, and from most starts it learns. Find the seeds on which it fails and print the outputs: on some inputs they are stuck around a third or around a half. That is the pit the chapter talked about.

The training examples themselves tell you whether the descent got stuck: if after training the network answers wrongly on even one of the four inputs, it hasn’t finished learning. Then start again from another random start: the same rng gives different numbers on the next call to normal.

Restarting is the simplest cure, and people use it in earnest: big networks, too, are sometimes trained several times from different starts. Another cure is spare neurons: with four hidden neurons instead of two, XOR gets stuck noticeably less often, because the descent has more directions in which to leave a bad pit. The tests don’t need a training function, only the weights, and for each of the sixteen gates they could have been picked by hand. Descent finds them by itself, from nothing but a table of answers.

What next

When a person can’t write a rule down, the machine finds it from examples, given a model with knobs, a measure of the miss, and descent. But all of this is computed by the same machine as in Part IV: bits, gates, multiplying numbers. The network that learns XOR is itself built out of XOR.

There is a problem, though, that defeats this machine outright. To describe the quantum state of fifty tiny magnets, the spins of electrons, takes $2^{50}$, about $10^{15}$, complex numbers: petabytes of memory. For three hundred spins there are more numbers than atoms in the observable universe. Yet nature somehow manages it in every molecule, every fraction of a second. In 1981 Richard Feynman drew a conclusion from this: if nature isn’t classical, then a machine for simulating it shouldn’t be built on bits either. All our machines so far have been built on bits. Another way of computing, one that physics allows, is in the next chapter.