Ok, Michael, so I'm going to talk a little bit
about bias. In particular, the preference bias for K
[INAUDIBLE]. So, let me remind you what preference bias
is. Preference bias is kind of our notion of
why we would prefer one hypothesis over another. And
they say all things, other things being equal. And
what that really means is, it's the thing that
encompasses our belief. About what makes a good hypothesis.
So in some of the previous examples that
we used it was things like shorter trees,
smoother functions, simpler functions, Occam's Razor, those sorts of
things were the ways that we expressed our preferences
over various hypothesis. And kNN is no exception.
It also has preference by its built in
as does every algorithm of any note. So I just wanted to go through three that I
thought of is as being indicitive of this bias. And they're,
kind of all related to one another. So the first one
is a notion of locality. Right? There's this idea that near
points are similiar to one another. Does that make sense to you?
>> Yeah. Yeah. That was really important. It came out
nicely in the the real estate example. Right. So the
whole idea. The whole thing we are using to generalize
from one thing to another is this notion of nearness.
>> Right. And exactly
how this notion of nearness works out.
Is embedded in whatever distance function we happen
to be given. And so, there's further
bias that might come out, based upon exactly
the way we implement distances. So, in
the example we just did, euclidian distance is
making a different assumption about what nearness or
similarity is, compared to Manhattan distance, for example.
>> So is there like, a perfect distance function for a given problem?
>> There's certainly a perfect distance function for any particular problem.
>> Yeah, that's what I mean. Not one that works for the
universe, but one, like, you know, if I give you a problem and
you can work on it all day long. Can you find, is
there a notion that there''s a
distance function that would capture things perfectly?
>> Well, it has to be the case for any given fixed problem. That there
is some distance function that minimizes, say,
sum of squared errors or something like that.
First is some other distance function. Right?
>> Okay.
>> That has to be the case. So there, there always to
be at least one best distance function given everything else is fixed.
>> That makes sense.
>> Right. Now, what that is, who
knows. Maybe you finding it might be. Arbitrarily
difficult. Because there's at least an infinite, there's
at least an infinite number of distance functions.
>> Well yeah, I was thinking that, that for latter to find distance functions
to be anything we want. What about a distance function that said
the distance between all the things that have the same answer, is zero.
>> Mm-hm.
>> And the distance between them and the ones that
have different answers is you know, infinity or something big.
>> Yeah.
>> And then, then the distance function,
like, somehow already has built in the solution
to the problem because it's already put
the things that have the same answers together.
>> Right, you could do that, and of course, doing
that would require again solving the original problem. But yeah, so.
So, such a function has to exist, or, well, you
know, there's always noise. What if there's noise in your data,
you know? But some such function like that has to
exist, the question is finding it. But I think the real
point to take there is, there are some good distance
functions for our problem and there are some bad distance functions
for our problem. And how you pick those is really fundamental
assumption your making about the domain. That's why it's domain knowledge.
>> Yeah, that sounds right.
>> Mm 'Kay. So, locality however it's expressed
to the distance function, that is similarity. It's built
in to kNN that we believe that near points
are similar. Kind of by definition. That leads actually
to the second preference bias which is this notion of
smoothness. Alright. That we are by choosing to average.
And by choosing to look at points that are similar
to one another. We are expecting functions to behave,
smoothly. Alright, so, you know, in the 2D case.
It's, it's kind of easy to see, right? You, you, you, you have these,
these sort of points and you're basically
saying, look, these two points should somehow be
related to one another more than this point and this point. And that sort
of assumes kind of smoothly changing behavior
as you move from one neighborhood to another.
Does that make sense?
>> I mean, it seems like we're defining to be pretty similar to locality.
>> In this case. So I'm, I'm drawing an example, such that, you know,
whatever we meant by locality has already been kind of expressed in the graph.
>> Okay.
>> And you know, by picking, you know, this is really for pedagogical
reasons. You know can imagine, this you know, these are points that live in
77,000 dimensions, and it's impossible to actually
visualize them much less draw them. And
I could try. [LAUGH] But here's, here's
three dimensions and here's the fourth dimension.
I think I'm going to get tired before I hit seven and seven thousand
but, you know, you kind of, you kind of get the idea, right? That, if. In,
you know, if you can imagine in your head points that are really
near one another in some space, you
kind of hope that they behave similarly. Right.
>> Right. Okay, so locality and smoothness. And I think these make sense. I
mean, these, this is hardly the only
algorithm that makes these kind of assumptions.
But there is another assumption which is a bit more subtle I think. Which
is worth spending a second talking about, which is, for at least the distance
functions we've looked at before. The Euclidian distance and
the Manhattan distance. They all kind of looked at each
of the dimensions, sort of, and subtracted them, and
squared them, or didn't, or took their absolute value and
added them all together. What that means is, we
were treating, at least in those cases, that all the
features mattered. And not only did they matter, they
mattered equally. Right. So think about the the last quiz
I gave you. Right. It said y equals x 1 squared plus x 2. And you noticed we
got answers that were wildly off from what the
actual answer was. Well if I know that the
first dimension. The first feature is going to be squared
and the second one is not going to be
squared. Do you think either one of these features
is more important or more important to get right?
>> Okay. Right. Trying to think about what that might mean. So,
if, yea its definitely the case that when you look
for similar examples in the database you want to care
more about X1 because a little bit of a difference
in X1 gets squared out. Right? It can lead to a
very large difference in the corresponding Y value. Whereas in
the x2's, it's not quite as crucial. Th, th, the,
if you're off a little bit more, then you're off
a little bit more, it's just a linear relationship. So yeah,
it does seems like that first dimension needs to be a lot
more important, I guess, when you're doing the matching. Then the second one.
>> Right so, we probably would have gotten
different, I'm not going to go through this but,
we probably would have gotten different answers if, in
the Euclidian or Manhattan case we had instead of
just taking the difference between the first two The
first dimensions, we had taken that difference and squared
it. And then in the case, including this and
squaring it again, and then some of those things
that were closer in the first dimension instead
of the second dimension would've looked more similar and
we might've gotten better answer. That's probably a good
exercise to go back and do for someone else.
>> [LAUGH] Yeah, I was thinking of doing it right
now, but yeah, probably should leave it for other people.
>> Well you can do it if you want to. So did you do it Michael?
>> I did.
>> And?
>> So it's a kind of now a mix between the Manhattan distance
and the Euclidian distance. So, I'm taking
the first component, take the difference, square
it.
>> Mm-hm.
>> Take the second component, take the difference,
absolute value it. And add those two things together.
>> Sure.
>> All right. So if I do that, with one nearest neighbor,
I still get that tie, but the output answer ends up being 12.
>> Hm. Which
is better than 24.7.
>> And that's better than eight, which is what
it was before. So the eight has gone up to
12, which is better than the other one, which I
think was 35.5, comes down to 29.5 Close here again
to the correct answer which is eighteen. So in
both cases it kind of pushed in the right direction,
it was using more, of the, the answers that were
relevant and fewer of the answers that were not relevant.
>> Right. There you go. So the notion of relevance by the way,
turns out to be very, very important. And highlights a weakness of
kNN. So this brings me to a kind of theorem or fundamental
results of a machine learning that is particularly relevant to kNN but
its actually relevant everywhere. Do you think its worth while to mention it?
>> Sure it sounds very relevant.
>> Alright let's do it.