9. Classifying by the Closest Examples

Nearest neighbors on handwritten digits

The logistic-regression model from the last few chapters did a lot of work before it predicted anything. It spent up to a few minutes adjusting weights until its scores fit the training images. After that, predicting was cheap: one multiplication per image and the answer came out.

This chapter's model does the reverse. It learns nothing when you fit it. It keeps every training image it was given. All of its work happens later, when a new image arrives and it has to decide what that image is. The method is called k-nearest neighbors, usually shortened to kNN. It is the next first model on the path toward the first portfolio project, and it is worth studying because it is so different from what came before. Because it moves the work to prediction time, it changes what the model costs to run. And because it has no weights, all of its behavior comes from one choice: what you mean when you say two images are close.

The idea

Say someone hands you a scanned digit you have never seen. You have fifty thousand labeled digits in a drawer. One fair way to decide is to pull out the few that look most like the new one and see what they are. If four of the five closest are sevens and one is a one, you call it a seven.

That is the whole method. Store the labeled examples. When a new example comes in, measure how far it is from every stored one. Take the k closest, where k is a number you choose. Let them vote, and predict the label that wins.

Two things in that description need pinning down. The first is "how far," which needs an actual formula. The second is k, and the next example shows why it matters.

Working it by hand

Take a flat page with two classes of points on it. Each point has two coordinates, an x and a y, the way a point on a map has an east-west position and a north-south one. Say yours look like this. Class A has three points: one at one and one, one at one and two, and one at two and one. They sit together near the bottom left. Class B has three points near the top right: four and four, five and four, and four and five. Class B also has one stray point at two and a half, two and a half. It sits close to the A cluster. Maybe it was mislabeled, or maybe it is an unusual real case. Either way, the data contains it.

The new point you want to classify is at two and two, right next to the A cluster.

To measure distance, use the ordinary straight-line distance you would get with a ruler. It is called Euclidean distance. For two points, take the difference in their x values and the difference in their y values. Square each difference, add the two squares, and take the square root. Squaring makes every difference positive. The square root brings the result back to the same units as the coordinates. This is Pythagoras: the two differences are the short sides of a right triangle, and the distance is the long side.

Now measure from the new point at two and two to each stored point.

To the A point at one and two, the x difference is one and the y difference is zero. One squared plus zero is one, and the square root of one is one. To the A point at two and one, the same reasoning gives a distance of one. To the A point at one and one, both differences are one, so you get the square root of two, about one point four one.

To the stray B point at two and a half, two and a half, both differences are a half. A half squared is a quarter. Two quarters make a half. The square root of a half is about point seven one. That is the shortest distance on the page.

The three B points in the far cluster are much farther away. Four and four is about two point eight three away. Five and four and four and five are each about three point six one away.

Now vote.

With k equal to one, you look only at the single closest point. That is the stray B at point seven one, so the prediction is B. One odd point has claimed the new point, even though the new point sits in the middle of A territory.

With k equal to three, you take the three closest: the stray B at point seven one, and the two A points at distance one. A wins two votes to one. The stray point is still counted, but it is outvoted.

With k equal to seven, you take every point on the page. That gives three A votes and four B votes, so the prediction is B again. This time the cause is different. B just has more points in total, and with k this large, the vote no longer cares which points are near. The big class wins everywhere.

The same new point got three answers, B, then A, then B, and only the middle one makes sense. This is the trade that k controls. A small k follows individual points closely, including mistakes and oddities. That is overfitting in a pure form: with k equal to one, every training point is classified perfectly, because each one is its own nearest neighbor at distance zero, and that perfect training score says nothing about new data. A large k smooths over oddities but also smooths over real detail. The border between classes blurs until the larger class takes ground it shouldn't. Good values sit in between, and you find them by measuring on held-out data, not by reasoning.

Two small practical points come out of this. With two classes, an even k can give a tied vote, so odd values are a common habit. And ties in distance also happen. Here two A points were both exactly one away. When they fall right at the edge of the k closest, the library has to break the tie somehow, and that choice can depend on the order of the stored data. With real pixel data, exact ties are rare, but they are the reason two runs on reordered data can differ by an image or two.

Distance is the assumption

On the page, straight-line distance matched what your eye sees. On MNIST it's less obvious what it measures.

Each MNIST image is twenty-eight by twenty-eight pixels, which makes seven hundred and eighty-four numbers between zero and two hundred fifty-five. You can treat those numbers as the coordinates of one point. That point lives in a space with seven hundred and eighty-four directions instead of two. The distance formula carries over unchanged: subtract the two images pixel by pixel, square each of the seven hundred and eighty-four differences, add them up, and take the square root.

So two images are close when the same pixels are dark in both. That works well enough when two people write a seven in roughly the same spot. Now take one seven and slide it one pixel to the right. To you it is the same seven. To this formula, many of the dark stroke pixels now land on pixels that were blank, and the blank ones land on ink. The shifted copy can end up farther from the original than a different digit drawn in the same place. The model has no idea that "shifted" is a thing. Its only notion of similarity is pixel overlap. That is the assumption you take on when you choose this distance, and later models in the course get much of their improvement by learning a better notion of similarity.

Scaling the pixels interacts with that assumption, and here kNN behaves differently from logistic regression.

Start with dividing every pixel by two hundred fifty-five, so values run from zero to one. Every difference shrinks by the same factor. So every squared difference shrinks by that factor squared, the sum shrinks by the same amount, and after the square root every distance is exactly one two-hundred-fifty-fifth of what it was. All distances shrink together, so their order doesn't change. The nearest neighbor is still the nearest neighbor, every vote comes out the same, and accuracy is identical to raw pixels.

StandardScaler is different, because it scales each pixel separately. For each pixel position, it subtracts that pixel's average over the training images and divides by that pixel's spread, the standard deviation. Recall from the MNIST inspection that border and corner pixels are zero in nearly all training images. A pixel that is almost always zero has a tiny spread. Dividing by a tiny number makes a big number. So in the rare image where a stray mark touches that border pixel, its value after scaling can come out enormous. A pixel that carries almost no information about the digit now dominates the sum. Meanwhile the center pixels, where strokes actually differ between a three and an eight, have large spreads and get scaled down to ordinary size. The distance now pays the most attention to the least useful pixels. Reported results show this can cost kNN anywhere from a couple of points of accuracy to much more.

That raises a fair question. The logistic-regression pipeline used StandardScaler, and it helped. Why does the same step help one model and hurt another?

The answer is that the two models use the numbers differently. Logistic regression learns a weight for every pixel. If a border pixel is blown up by scaling, the model can learn a small weight for it and make it harmless. Scaling helped there because it changed how easy the optimization was. The lbfgs solver converged faster and more reliably when all features had similar ranges. That was the point of the max-iteration warnings in the earlier exercise. kNN has no weights to learn. It adds up squared pixel differences with every pixel counted equally. Whatever scale you hand it is the importance it uses. So for kNN, scaling isn't a numerical convenience. It changes what the model thinks similar means.

Running it on MNIST

This uses the arrays you already have. The data is loaded through fetch_openml as mnist_784, the first sixty thousand images are training data, and the last ten thousand stay sealed as the test set. Inside the training data, use the same validation split as before: fit on the first fifty thousand, evaluate on the next ten thousand. Every number in this chapter comes from those ten thousand validation images. The test set stays untouched, so the comparisons you are about to make can't shape the final score.

The model is scikit-learn's KNeighborsClassifier, from the neighbors module. You create one, call fit with the fifty thousand training images and their labels, then call score, or predict and compare, on the ten thousand validation images. The defaults are a reasonable start, but you should know what each one means.

The setting n neighbors is k, and it defaults to five.

The setting weights decides how the vote is counted. Its default is uniform, which gives every one of the k neighbors one equal vote, as in the hand example. The other choice is distance. Then each neighbor's vote is weighted by one over its distance, so a very close neighbor counts more than one at the edge of the group. With k equal to one, the two settings give the same answer, since there's only one voter.

The metric defaults to Minkowski, together with a setting called p that defaults to two. Minkowski distance is a family of distances, and p picks the member. With p equal to two, it is exactly the Euclidean distance you computed by hand. With p equal to one, it is Manhattan distance, which adds the absolute differences instead of squaring them, like walking city blocks instead of cutting diagonally.

The algorithm setting defaults to auto, and the other options are ball tree, kd tree and brute. Brute force means exactly what it sounds like: compare the query to every stored image. The tree options organize the stored points ahead of time so that a search can skip whole regions that can't contain a near neighbor. In two dimensions, that saves a lot. In seven hundred and eighty-four dimensions it saves almost nothing, because points spread out so evenly that every region looks possibly close and few can be skipped. On MNIST, the search ends up exhaustive either way. You can leave algorithm on auto, knowing that what happens is effectively brute force.

One more setting matters for your wall clock: n jobs. Its default uses a single worker. Setting n jobs to minus one uses every processor core you have.

Leave the pixels raw, or divide by two hundred fifty-five if you prefer, since you now know the two give identical neighbors. Don't add StandardScaler here.

Results reported for this setup, fitting on fifty to sixty thousand raw images and scoring ten thousand held-out images, fall between about ninety-six point eight and ninety-seven point two percent. With the defaults, k of five and uniform weights, expect a figure close to ninety-seven percent. Those reported numbers were measured on the standard test set. Your validation images come from the training portion, so your exact figure will differ a little, but it should land in that region. Compare it with logistic regression's roughly ninety-two percent. About eight in every hundred digits were wrong before. Now about three are. The model with no learned weights, which just looks things up, made well under half as many mistakes.

Then look at the timing, which is where you pay for it.

The fit call returns almost instantly, because fitting only stores the arrays. The predict call is slow. Every one of ten thousand validation images is compared with every one of fifty thousand stored images. That is five hundred million image-to-image distances, and each one is a sum over seven hundred and eighty-four pixels. Reported times are several minutes using all cores, and over twenty minutes on a single worker. Logistic regression predicts the same ten thousand images in tens to hundreds of milliseconds, since it does one matrix multiplication for the whole batch. That makes kNN slower at prediction by a factor of somewhere between about a thousand and ten thousand.

Memory follows the same pattern. Logistic regression keeps ten rows of seven hundred and eighty-four weights after training, and the training images can be thrown away. kNN has to keep all fifty thousand images, because they are the model. Stored as sixty-four-bit floats, that is about three hundred megabytes. And it grows with every example you add. More training data makes kNN more accurate and also slower and heavier with every prediction.

That is a systems decision as much as a modeling one. If you're labeling a fixed batch of digits once overnight, a few minutes of prediction is fine and the extra accuracy is worth it. If you're answering requests one at a time while someone waits, every request pays for a scan of the whole training set, and a cheaper model, or a faster neighbor-search system, starts to matter.

Reading the result with the tools you already have

Accuracy alone repeats the mistake from two chapters ago, so build the ten-by-ten confusion matrix from the kNN validation predictions. Use the same confusion matrix function and display as before, and put it next to the one from logistic regression.

Look for the cells that changed most, not just for a smaller overall error. Some confusions that troubled the linear model tend to shrink, because kNN can match a digit to a specific training example drawn the same unusual way, where logistic regression had to separate whole classes with straight boundaries. Others may stay or grow. Pixel-overlap distance is easily fooled by thin, thick, or shifted strokes, so check whether the remaining errors are pairs that share a lot of ink in the same places. Your matrix will show which pairs those are. Writing down the cells that improved and the ones that didn't is the start of an error analysis you can carry into the portfolio project.

The ranking tools from the last chapter need more care. KNeighborsClassifier does have a predict proba method. With uniform weights, its probability for a digit is simply the fraction of the k neighbors that voted for it. With k of five, the only possible values are zero, point two, point four, point six, point eight and one. Every probability is a multiple of one over k.

Think about what that does to a ROC curve. That curve came from sorting images by score and sweeping a cut down the list. Here, thousands of images share the exact score of one, thousands more share zero, and only a few distinct values exist between them. The sorted list is mostly large tied blocks. When the cut passes a tied block, it lets in all of its positives and negatives at once, so the curve moves in a few big diagonal jumps instead of many small steps. The area under it is still calculated correctly, but it describes a coarse ranking, and comparing that area with logistic regression's smooth scores isn't measuring quite the same thing. Distance weights give finer values, since the vote fractions now depend on exact distances. And these vote fractions say nothing reliable about calibration. A score of one means all five neighbors agreed, not that the model is certain.

An experiment to run

Now turn the open choices into measurements. Keep the run time manageable by predicting on a subset of the validation images, say the first two thousand. Still fit on all fifty thousand training images, because the stored set is the model, and shrinking it would change what you are measuring.

Vary three things. Try k of one, three, five and ten. Try uniform and distance weights. Try raw pixels and pixels passed through StandardScaler, with the scaler fitted on the fifty thousand training images only and then applied to the validation subset. A scikit-learn pipeline does that ordering for you. Four values of k, two weightings, and two scalings make sixteen runs. For each one, record validation accuracy and the time the predict call took. You can measure time with the perf counter function from Python's time module, read just before and just after predicting.

Before running, write down what you expect. Which k do you think wins? Will distance weighting help more at small k or at large k? How much will StandardScaler cost? Committing to a guess first is what turns the results into something you learn from.

When the numbers come back, judge them with three ideas in mind.

First, size the noise. On two thousand images, one image is a twentieth of a percentage point. At an accuracy near ninety-seven percent, ordinary chance from which images happened to be in your subset moves the result by roughly four tenths of a point. Two settings that differ by less than that haven't been shown to differ. Differences of a point or more are worth believing. If two settings look close and the choice matters, rerun them on all ten thousand validation images.

Second, check what must be true. The uniform and distance runs at k of one should give identical predictions. If they don't, something else changed between runs. Raw and divided-by-two-hundred-fifty-five pixels would also tie exactly, which is a check you can add if you want one.

Third, look at the timing pattern. Prediction time should barely change with k or with weighting, because the expensive part, computing all the distances, is the same in every run. Picking the top five instead of the top three adds almost nothing. If StandardScaler runs are slower, it's because the data type or the extra transform step changed, not because the search got harder. The result you should be able to explain is that accuracy moves with your choices, while cost is set by the size of the stored set.

Write the sixteen results into your project notes beside the logistic-regression numbers, with the subset size and the settings, so the comparison can be rerun later.

kNN draws its boundaries from individual stored points and says nothing about why a region belongs to a class. The next model, the decision tree, makes the opposite trade. It learns a short sequence of yes-or-no questions about pixels at fit time, then answers new images by following them, quickly and in a way you can read.

PyTorch reaches Google's TPUs without the old detour

The consequential tooling news this time is in PyTorch, the deep-learning library this course uses once it reaches neural networks.

On the twentieth of October, at the PyTorch Conference, Google and Meta announced TorchTPU, which they built together and have released as open source. TPUs, tensor processing units, are Google's own chips for training and running neural networks. PyTorch could already run on them through a layer called PyTorch/XLA, but that route required changing how your code ran. TorchTPU instead supports PyTorch's normal eager mode on TPUs. Eager mode means each operation runs as soon as the line is reached, the way ordinary Python does, which is how most people write and debug PyTorch. With TorchTPU, moving a tensor to the chip works like moving it to a graphics card: you call the to method with "tpu" as the device. It covers roughly four hundred and fifty of PyTorch's core operations and connects to torch compile and to serving and training projects including vLLM, SGLang and TorchTitan.

Keep the announcement apart from what you can rely on. Released code means you can inspect it and try it. Covering about four hundred and fifty core operations isn't the same as covering every operation a given model uses, and how fast it runs depends on the workload. Treat it as a new deployment option to test against a known result, not as a proven replacement.

The same week brought PyTorch 2.15. Most of it is aimed at large-scale training: upgrades to FSDP2, the library's fully sharded data parallel tool for splitting a big model across many GPUs, plus updated support for newer AMD and Intel hardware. One item reaches ordinary laptops. On an M3 Ultra Mac, models built as a mixture of experts generated tokens about a third faster through Apple's Metal backend. A mixture of experts sends each token through only some parts of the network. That figure was measured for that kind of model, on that chip, in the token-by-token decoding step. It doesn't tell you how other models or other Macs will do.

You have nothing to change today. The project lock file doesn't include PyTorch yet. When it does, the same habit from the pandas and scikit-learn news applies: pin a version, rerun a saved experiment before and after any upgrade, and compare the results.