Chapter 5: Birds of a Feather

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Okay, let's dive in.

We're pulling back the cover on a single chapter from the book, Why Machines Learn, and using it as our map, really, to navigate one of the simplest yet

surprisingly powerful algorithms in machine learning.

Now we're going to start with connections you absolutely will not see coming.

Yeah, what's fascinating here is how the core idea of the algorithm seems to echo through history.

It pops up in fields as different as 19th century public health and ancient theories of vision.

It's a concept that feels almost intuitively human.

That's the mission for this deep dive then, to trace that idea, see how it got formalized into a potent ML algorithm, understand it's, well, it's elegant math, it's surprising power, and also the significant challenges it faces.

We're letting the source material guide us every step of the way here.

So let's go back to London, 1855.

The source opens with this really vivid report detailing a devastating cholera outbreak in the Soho area.

And there's this chilling line, no street in the cholera area was

the death rates were just terrifying, rather more than 10 % just on Broad Street alone.

And this report, it included observations from Dr.

John Snow.

Now he was a physician already making waves, particularly in anesthesiology.

He famously gave chloroform to Queen Victoria.

Right, I've heard of him in that context.

But his work on this cholera outbreak, that was groundbreaking for epidemiology.

He had this hypothesis that cholera was waterborne, which was, well, pretty controversial at the time.

And his key piece of evidence,

an annotated map of Soho.

This map is like legendary in epidemiology circles.

But the source highlights how more recently it's really intrigued computer scientists, too.

Exactly, because it visualizes a concept that's fundamental to a specific ML algorithm.

How did it work?

So Snow marked deaths on the map with little black rectangles and water pumps with black dots.

Simple enough.

But his real insight was drawing this inner dotted line around the main pump, the Broad Street pump.

And this line, it didn't just show distance as the crow flies.

It showed points that were, and this is the key, at an equal distance by the nearest road from the Broad Street pump and any other nearby pump.

So walking distance.

Inside that line, you were closer walking to the Broad Street pump.

Outside, you were closer to a different pump.

Precisely.

And his conclusion was just so powerful.

Deaths very much diminish or cease altogether at every point where it becomes decidedly nearer to send to another pump than to the one in Broad Street.

So people closer to other pumps weren't getting sick nearly as much.

The Broad Street pump was clearly the source.

Bingo.

The Broad Street pump was the source.

And what Snow did there,

dividing up the space based on which seed point, which pump is nearest.

That's a striking illustration of a mathematical concept, right?

A Voronoi cell, yes.

Named after Georgi Voronoi, who formalized the math later on.

A Voronoi diagram basically tiles or tessellates space into these regions.

Each region belongs to a seed point, like Snow's pumps, and any point within that region is closer to its seed than to any other seed.

Snow was essentially drawing Voronoi cells based on street distance.

Which, as the source points out, is often crucial.

As the crow flies, or Euclidean distance, that's one way to measure.

But in a city grid, walking distance, what they call Manhattan distance, right?

The sum of the absolute differences in coordinates, it's often much more relevant.

Right.

The source uses this neat example.

Imagine assigning buildings in Midtown Manhattan to their nearest post office branch.

You treat the post offices as the seeds.

A building goes to the branch whose seed is nearest, probably using Manhattan distance because you walk on streets.

Snow's map is just this beautiful early example of partitioning space by proximity.

And this idea, finding the nearest neighbor, it wasn't just about maps and pumps.

It kind of popped up in theories of how we see things, how we recognize things, centuries earlier.

Indeed.

Centuries.

We jump now way back to al -Hasan, Abu Ali ibn al -Haytham, during the Islamic Golden Age.

A computer scientist named Marcello Pelleo actually discovered this connection in a book about theories of vision.

Al -Hasan, he revolutionized optics, right?

Proposed light enters the eye instead of the eye shooting out rays.

Exactly.

He challenged those older theories.

But Pelleo was really interested in al -Hasan's ideas about recognition.

What happens after light hits the eye?

Okay.

What did al -Hasan think?

Well, al -Hasan proposed that after light enters the eye, our faculty of discrimination, basically, our brain, our cognitive process, it seeks a counterpart among the forms persisting in the imagination.

So in our memory.

In our memory.

Exactly.

You see something and your brain compares it to stored memories.

So recognition is finding a match in memory.

Finding something similar, that was his word.

You recognize a dog because you find a similar dog form stored in your memory.

And if you see something totally new with no similar form in memory,

well, you can't recognize it.

That word similar.

That's so key in computer science, isn't it?

It often comes back to distance.

Points close together in some, you know, abstract space are considered similar.

Precisely why Pelleo saw al -Hasan's description as so remarkable.

Comparing a new observation to memory and finding the most similar match.

I mean, that sounds almost algorithmic.

A clear precursor to the modern nearest neighbor rule.

Even though that rule was formally developed much, much later.

Oh, yeah, much later.

In the 1950s and 60s, notably by folks like Thomas Cover and Peter Hart, Hart himself, though, felt the intuition was even more primal.

He called it the caveman intuition.

The caveman intuition.

Yeah, basically.

If they look alike, they probably are alike.

You see a new berry.

Does it look like the poisonous one or the edible one you already know?

You classify it like the one it most resembles.

Find the nearest neighbor.

Okay, so we have this really powerful intuitive idea.

Classify something new based on the most similar things you've already seen and labeled.

How do we actually turn that into a machine learning algorithm?

Right, the mechanics.

We represent patterns or objects or images mathematically as vectors.

Like coordinates.

Exactly, like coordinates.

Think of an image, say a handwritten digit, drawn on a simple seven by nine grid that's 63 pixels.

If it's just black and white, each pixel is maybe a zero or one.

Okay.

We can just string those 63 numbers together into a list, a vector.

It's a 63 dimensional vector.

Every unique image becomes a single point in this, well, this very high dimensional 63D space.

Different drawings of the number two would become different points in this 63D space, but they'd kind of cluster together.

Exactly.

They'd form a sort of two cloud,

and drawings of eight would form another separate cluster, another cloud, hopefully far away from the two cloud.

Right.

If you have a data set where you've already labeled a bunch of these vectors, these are twos, these are eights, the task is given a new unlabeled image vector.

What is it, a two or an eight?

And this is where the 1NN algorithm, the simplest version, comes in.

1NN, meaning one nearest neighbor.

Just one.

It's beautifully simple.

You take that new vector, that new point in 63D space, you calculate its distance to every single labeled vector you already have stored in your data set.

Okay.

Find the distances to everything.

Then you find the one point in your data set that is geometrically nearest to your new unlabeled point.

And you just assign the new point the same label as that single nearest neighbor.

That's it.

If the closest labeled point in your whole data set is an eight, you confidently, well, maybe confidently, classify the new one as an eight.

It's the direct application of that caveman intuition again.

If this new image vector looks most like a known eight vector, meaning they are closest in this 63D space, it probably is an eight.

That nailed it.

That's the core logic.

The intuition feels ancient, almost obvious, but the formal math treatment that came much later, you said?

Yeah.

The first sort of rigorous mathematical mention of the NN rule seems to be in a 1951 technical report by Evelyn Fix and Joseph L.

Hodges Jr.

working for the U .S.

Air Force, actually, at the School of Aviation Medicine.

Huh.

Interesting place for it to pop up.

Isn't it?

The source mentions a bit about Fix's background, her statistical expertise, develops doing heavy calculations during the war years at Berkeley.

And then Peter Hart, who you mentioned earlier, working with Thomas Cover at Stanford,

he was determined to understand the why, right?

The theory behind this simple rule.

Exactly.

He was a big believer in theory.

His quote was something like, the most practical thing in the world is a good theory.

He really wanted to know, okay, how large can this simple algorithm actually perform?

What are its limits?

And his work established these theoretical bounds on its error rate.

Yeah, it did.

And the finding was actually surprisingly good, wasn't it?

Very good.

He showed that, okay, assuming you have infinite data, which you never do, but theoretically - Right, the ideal case.

The error rate of the simple 1NN rule is no worse than twice the error rate of the absolute best possible classifier you could ever imagine for that problem.

Something called the Bayes optimal classifier.

Twice the error of the best possible.

Yeah.

That's actually a really strong guarantee for such a simple method.

It really is.

And crucially, another big advantage is that the NN rule doesn't need to make complicated assumptions about how the data is distributed, unlike some other algorithms.

It just uses the data points themselves.

The source has that great anecdote about

Hart consulting the mathematician, Chi -Li Chung.

Oh, yes.

Hart apparently went to Chung, explained his problem, the bounds he was trying to prove.

Chung asked if he knew a couple of specific advanced math concepts, like measure theory.

Which Hart did.

Which Hart did.

And Chung just looked at him and said, well, you know enough, now you just have to be smarter.

Wow.

And apparently that was the end of the meeting.

Talk about tough love, pushing him to figure it out himself.

Totally.

Hart really had to wrestle with some serious math, including measure theory, which his advisor cover encouraged him to tackle head on.

Though the story goes he did take the summer off to learn sailing first.

Ah,

a well -deserved break before cracking the code.

Seems like it.

But he did crack it.

His eventual dissertation, apparently only 65 pages long, really laid the foundation for understanding NN's theoretical power.

So intuitively, just trying to grasp why it gets so close to the best possible classifier.

Right.

How does looking at just one neighbor do so well?

Think of the penguin example the source uses maybe classifying Adélie and Gentoo penguins based on their buildup.

The Bayes optimal classifier, the theoretical best, it knows the true underlying probability distribution.

It knows maybe at a specific buildup, there's a 75 % chance it's in Adélie and 25 % Gentoo.

It always picks Adélie for that depth.

But 1 and N doesn't know those probabilities, it just looks at its single closest neighbor in the data it has seen.

Exactly.

But here's the key.

If you have a very large data set, that single closest neighbor is highly likely to come from the class that is locally most probable.

So if 75 % of penguins around that buildup are Adélies, your nearest neighbor is very likely to be in Adélie too.

The 1 and N rule, in a sense, it implicitly estimates the local probability density just based on the nearby sample points.

It acts like a bias coin reflecting the local density.

Okay, the simplicity is appealing,

the theoretical guarantees are impressive,

but the source definitely points out a significant potential issue with strictly using just one nearest neighbor.

Oh yeah, overfitting.

Big time potential for overfitting.

Overfitting, meaning it learns the training data too well, including the noise.

Exactly.

Let's go back to that mock data set example the source uses, the one with gray circles and black triangles.

We saw 1 and N can create a really squiggly complex boundary, which is good because it lets it separate data that isn't linearly separable, a simple line wouldn't work.

But imagine there's a mistake in the data, a single black triangle data point that got mislabeled or is just an outlier sitting right smack in the middle of a dense cluster of gray circles.

What happens then?

The 1 and N rule, being hyperlocal, will draw a tiny little boundary like an island around that single misplaced black triangle.

So any new data point that happens to fall into that tiny island will be classified as a black triangle, even though it's completely surrounded by gray circles in the broader neighborhood.

Ah, so it's paying way too much attention to that one noisy point.

Precisely.

The algorithm is too sensitive to noise or errors in the training data.

It's fitting the noise, not just the underlying pattern that's overfitting.

The boundary becomes too specific to the exact training points it saw, and it probably won't generalize well to new unseen data.

So how do you fix that?

The fix is actually wonderfully simple and intuitive.

Instead of using just 1 and N, you use K nearest neighbors, K and N.

So look at more than one neighbor, like the 3 nearest or 5 nearest.

Exactly.

You choose a number K.

You find the K points in your training data that are nearest to your new point.

Then you look at the labels of those K neighbors, and you classify the new point based on the majority vote.

Ah, a democratic decision among the neighbors.

Pretty much.

If K5 and 3 of the 5 nearest neighbors are gray circles and 2 are black triangles, the majority vote says gray circle, so you classify the new point as a gray circle.

And for a two -class problem like circles versus triangles, K should probably be odd, right?

To avoid ties.

Good point.

Yes, using an odd K like 357 avoids those 50 -50 splits.

How does this help with the overfitting island?

Well, the source shows this clearly.

Using 3 and N on that same data set with the outlier,

the boundary smooths out.

That little island around the lone black triangle disappears.

Why?

Because a new point near that outlier might have the outlier as its nearest neighbor, but its second and third nearest neighbors are likely to be the surrounding gray circles.

So the majority vote, two gray, one black,

correctly classifies it as gray.

Makes sense.

It considers the neighborhood context more broadly.

Exactly.

And if you use an even larger K like 7 and N, as shown in the source, the boundary gets even smoother, less jagged.

So using K and N smooths the decision boundary and helps the model generalize better to new data, even if maybe it might now misclassify a few points right on the edge in the training data itself.

That's the trade -off, and it's generally considered a good one.

A slightly higher error on the training data might be acceptable if it means much better performance on unseen data.

A smoother boundary is usually more robust to noisy real -world data.

And does the theory still hold up for K and N?

It does.

Hart actually extended his results to K and N.

The core idea is that as your data set size N grows very large and you let D grow as well, but slowly compared to N, the performance of K and N gets closer and closer to that optimal Bayes classifier.

The majority vote among many neighbors in a large local sample gives you a really good estimate of the true local probabilities.

Right.

If 75 % of penguins in that area are dailies,

a majority vote of, say, 11 neighbors in a big data set is highly likely to reflect that 75%.

Precisely.

It converges to the optimal decision.

Hart apparently found generalizing the proof quite challenging, involving more measure theory.

There's another anecdote about him deciding he'd proven enough for his PhD and taking that summer off to learn sailing instead of tackling the final generalization.

Huh.

Knows when to quit while he's ahead.

Or just needed a break.

His 65 -page dissertation did pretty well for him.

So K and N seems like the way to go in practice.

It's intuitive,

has theoretical backing, fixes the overfitting issue.

What are the practicalities?

How do you actually code this up?

Right.

Implementation.

From a programming perspective, the source outlines the steps and they are honestly very straightforward.

Step one, you just store all your labeled training data, every data point, like a penguin's features, and its known label, a daily or gen two.

Okay.

Just a big database of examples.

Essentially.

Step two,

when you get a new unlabeled data point,

a new penguin arrives, you calculate its distance to every single point in your stored training data.

Every single one.

That sounds like it could take a while for big data sets.

We'll get to that drawback.

But yes, calculate all distances.

Step three, you sort those distances, find the eight points with the smallest distances.

Those are your A near nearest neighbors.

Got it.

Step four, you look at the labels of those state neighbors, take a majority vote, and assign that winning label to your new penguin.

Done.

That does sound pretty simple from a coding logic perspective.

Yeah, and it's used in the real world.

Oh, absolutely.

Recommendation systems are a classic, classic example.

Think Amazon or Netflix.

How does that work?

Well, you can represent user's tastes, maybe based on what books or movies they've rated as vectors.

To recommend something to you, the system finds users whose taste vectors are nearest to yours, your taste neighbors.

Ah, and then it recommends things those neighbors liked, but I haven't seen yet.

Exactly.

It's basically saying, people with similar tastes to you like this, so maybe you will too.

The source even mentions fascinating biological examples, like evidence that fruit flies might use a form of KNN to process and react to odors by comparing new smells to known ones.

Wow.

From Dr.

Snow's map to fruit fly noses.

Via theoretical math, that's quite a journey.

It really is.

The source also points out a really key characteristic here.

KNN is what's called a nonparametric model.

Nonparametric.

What does that mean compared to, say, a perceptron?

Good question.

A parametric model, like the perceptron, learns a fixed set of parameters like the weight vector W.

The size of the model, the number of parameters, stays the same regardless of how much training data you throw at it.

A nonparametric model like KNN is different.

The model essentially is the entire training data set.

Its complexity grows with the data.

To make a prediction, you need to refer back to and use all the original training instances.

Ah, and that directly leads to that big practical drawback you hinted at earlier, especially for really large data sets.

Precisely.

First, you have to store the entire data set, which could require huge amounts of memory if you have millions or billions of examples.

Right.

And second, for every single new prediction, you have to calculate the distance from the new point to every single point in that massive stored data set.

That computational cost can become really prohibitive.

It can be very slow at prediction time.

So that's one major challenge.

Computation and memory for large end, large number of data points.

Yeah, that's a big one.

And then there's perhaps the biggest challenge, the real Achilles heel, especially for data with lots and lots of features, like our 63 dimensional image vectors, or maybe even thousands of dimensions.

Yes.

The most glaring disadvantage, particularly for distance -based algorithms like KNN, operating in very high dimensional spaces, it's what the researcher Richard Billman famously called the curse of dimensionality.

The curse.

It sounds dramatic because I guess it is.

It really is because our intuition, which we develop living in a 2D or 3D world, completely breaks down in high dimensions.

Things behave very strangely.

Have so.

The source gives a great clear example.

Imagine your sampling points uniformly in some region, say between zero and two on a number line.

Okay, 1D.

In 1D, if you want to sample the sub region zero, one, that's half the total length.

Maybe 10 out of 20 samples fall there.

Feels reasonably dense.

Makes sense.

Now go to 2D.

The space is zero, two by zero, two.

The sub region you care about, zero, one by zero, one, is now only one quarter of the total area.

With the same 20 samples, maybe only four or five fall in your target square.

It's already sparser.

Right, the target area shrunk proportionally.

Now jump to 3D.

The unit cube zero, 13, is only one eighth of the volume of the zero, 23 cube.

With 20 samples, you might only get two or three points in there.

It's getting really sparse.

I see the pattern.

As dimensions increase,

the volume of that local unit hypercube becomes an exponentially smaller fraction of the total volume.

Exactly.

So in very high dimensions, thousands, tens of thousands, even if you have a lot of samples overall, the space becomes incredibly, almost unimaginably sparse.

Any given point is likely to be very far from all other points.

Like that quote in the source from Julie Delon, in high dimensional spaces, nobody can hear you scream in your immediate neighborhood.

Yes, that's a great way to put it.

To have enough data points to reasonably fill or cover a high dimensional space, you'd need an exponentially increasing number of samples, which is usually just impossible to get.

The space is effectively mostly empty.

Okay, so sparsity is one aspect of the curse.

Does it affect distances too?

Oh, dramatically.

The source explains this using the weird geometry of high dimensional spheres and cubes.

Spheres and cubes.

Yeah, counterintuitively, the volume of a unit sphere with radius one into dimensions actually tends towards zero as the dimension goes to infinity.

The volume goes to zero, that seems wrong.

It feels wrong, but it's true.

The formula involves pi and gamma functions, but basically the denominator grows way faster than the numerator.

Meanwhile, the volume of a unit hypercube side length one is always one, no matter the dimension.

Okay, sphere volume vanishes, cube volume stays at one.

Now picture that sphere fitting snugly inside the cube.

As dimensions increase, almost all the volume of the cube gets pushed out towards its corners, its vertices, leaving effectively zero volume near the center where the sphere is.

And the vertices get further away.

Much further away.

In 3D, a corner like 111 is distant squirt three from the origin.

And on 1000 dimensions, a corner is distant squirt 1000, which is over 31 units away.

And there are 21 ,000 corners.

So what this means for K &N is that in very high dimensions, your data points tend to live out in these very sparse, very numerous far -flung corners of the space.

And because everything is so spread out and far away in these corners, a really weird thing happens.

The distance between any two randomly chosen points becomes almost the same, regardless of which points you pick.

Wait, all points become roughly equidistant from each other.

Pretty much.

The concept of nearness starts to break down.

If all points are roughly the same distance away from a new point, how do you pick the nearest neighbors?

The distance measure loses its discriminatory power.

So the core premise of K &N that points nearby, belonging to the same class, just completely falls apart when nearby stops being a meaningful concept.

That's the curse of dimensionality in a nutshell for distance -based methods like K &N.

It works best, much, much best, for lower dimensional data where distances still mean something intuitive.

Okay, that sounds like a huge limitation.

A real showstopper for high dimensional data, potentially.

So if you do have data with thousands of features, how on earth do you use algorithms like K &N effectively?

Or can you?

You often can, but you usually need to do something first.

This is where statisticians and machine learning practitioners rely on, well, really essential tools to try and combat the curse.

And probably the most common and powerful one is called principal component analysis, or PCA.

PCA, I've heard of that, was the basic idea.

The core idea behind PCA and dimensionality reduction techniques in general is the realization that even if your raw data lives in, say, 10 ,000 dimensions,

the meaningful variation, the actual structure in the data that helps you tell twos apart from eights, or a daily penguins from gen twos, might actually lie in a much, much lower dimensional subspace.

Maybe only 50 dimensions capture most of the important differences.

So the data is high dimensional on the surface, but intrinsically perhaps it's lower dimensional.

Exactly.

It might live on a sort of flat sheet or a curved manifold within that high dimensional space.

PCA is a technique to find that lower dimensional subspace, to project the data down onto it, effectively reducing the number of features, the number of dimensions you need to deal with.

While trying to keep the important information.

While trying to preserve as much of the original variance, the important information as possible, By reducing the data to a more manageable number of dimensions, maybe 50 or 100 instead of 10 ,000, you often bring it back into a realm where distance metrics become meaningful again.

And then algorithms like KNN can work effectively on this reduced data.

Yes.

KNN and many other algorithms that suffer from the curse can often perform much better after dimensionality reduction like PCA.

So the curse is real.

It's a serious challenge.

But there are ways to fight back to mitigate it.

Absolutely.

It's not necessarily game over for high dimensional data.

As Bellman himself said, even after coining the term curse, something like, since this is a curse, which has hung over the head of the physicist and astronomer for many a year, there is no need to feel discouraged about the possibility of obtaining significant results despite it.

That's encouraging.

It is.

Techniques like PCA reveal, as the source puts it, the awesome power of dimensionality reduction.

Which definitely sounds like a crucial topic in its own right, maybe for another deep dive.

It certainly is.

It's often the next essential stop on the journey after understanding algorithms like KNN and the challenges they face.

Okay.

So wrapping up this particular deep dive, we've covered a lot of ground.

We travel all the way from a 19th century cholera outbreak map and ancient theories of vision

to formalizing that core intuition into an algorithm.

Understanding its surprising theoretical strengths, tackling practical problems like overfitting, confronting the really weird effects of the curse of dimensionality, and then finding ways to mitigate that curse.

Yeah.

We've really seen how this elegantly simple idea classifying things based on the nearest -know examples, that if they look alike, they probably are alike.

Principle.

How it has these roots stretching across centuries and across completely different fields of thought.

And it's fascinating how the KNN algorithm itself is, on the surface, so straightforward to describe and even implement.

Right.

The code is simple.

But underneath, it's underpinned by some pretty deep mathematical theory.

And it faces these really significant computational and especially dimensional hurdles in practice.

This deep dive, using the source material, it really highlights how these core machine learning concepts often aren't just invented out of thin air, right?

They frequently formalize intuitions or observations that have been around maybe implicitly for a very, very long time, even if actually applying them effectively and handling the challenges required modern computational tools and mathematical insights.

So reflecting on all this, what's a final thought for us, for you listening, to maybe chew on?

Well, it kind of brings it back to that human intuition, doesn't it?

It raises a fascinating question, I think, for you to ponder.

How much of your own everyday understanding and decision -making actually relies on finding similarities?

When you encounter something new, a person, a situation, a news article, whatever are you, maybe unconsciously, comparing it to stored examples in your own memory, using your own internal nearest neighbors to help you categorize it, understand it, react to it.

Yeah, that comparison to past experience feels very fundamental, almost automatic.

It does.

And then maybe take it a step further.

Think about that curse of dimensionality in the context of your own really complex decisions.

When you're faced with a problem that has tons of interacting factors, maybe dozens or hundreds of features.

Like a big life decision or understanding a complex societal issue.

Exactly.

Does the sheer volume of information, the high dimensionality of the problem, make it harder for you to find truly relevant past experiences or analogies to guide you?

Does our own mental capacity face a kind of cognitive curse that limits our ability to effectively grasp and make decisions about truly complex, multifaceted issues?

Does our intuition based on simple comparisons break down when things get too complex?

That's the question.

It's definitely something worth mulling over.