Okay, Michael, so let's, let's look at this little line
segment, okay? And then say I've got ten little points that
I could put down on this line segment, and I want
them all to represent some part of this line, alright? That's
kind of K nearest neighbor-y/-ish. So, I'm going to put a little
X here, I'll put one here, I'll put one here, put
one here, put one here, here, here, here, here, here. Is
that ten? Three... six. Nine, ten. Ten. Okay. And let's pretend
I did the right thing here and I have them
kind of uniformly distributed across the line segment. So that means
each one of these points is sort of owning, an
equal size sub segment of this segment. Does that make sense?
>> Yeah, so, so it's representing it in the sense that, that point. Uh,when
you're trying to estimate values of other places on the line it's going to
default as the nearest neighbor to being
that point so there's a very small little
neighborhood of the red line segment that is covered by each of the green X's.
>> That is exactly right and in fact each one
of these green X's represents. How much of this segment?
>> Each of the green X's covers one tenth?
>> That's exactly right. You cover one tenth. Alright
Michael, so let's say I move from a line
segment now to a two dimensional space. So
a little square segment. If that's the right
technical term. And I've taken my little ten
x's, and I put them down here before. Well,
here's something you'll notice; you'll notice that each
one of these x's is going to still end
up representing one-tenth of all of this space,
but you'll also notice that, that, that it's representing
now you know. Really really really really big.
>> I see.
>> So one way of putting it is, you know if you think
about the farthest point, as opposed to
the furthest point which would be incorrect.
>> [LAUGH]
>> The farthest point that this particular first x
over here is representing, its got some distance here.
Over here, the farthest point from this x, the
distance is very, very far away. So, a question
would be, how can I make it so that each of
the x's I put down represents the same amount of. I
don't know diameter or distance as the xs in this line
segment over here. So what do you think I have to do?
>> I feel like you need to fill up the square with xs.
>> Yeah, that's exactly right so let's do that. So
filling em up Michael as you suggested. You'll notice that
at least if we pretend that I drew this right. Each of
these X's is now going to end up being the nearest neighbor for
a little square like this, and the diameter of these little squares are
going to be the same as the diameter of these little line segments.
>> Yeah, I agree for some definition of the word diameter.
>> Yes, and for some definition of our demonstration. Okay, so how
many of these X's are there, Michael? Can you tell? You want to count?
>> [LAUGH].
I'm going to multiple [CROSSTALK] cause it looks like
you did ten by ten so that'll be 100.
>> That'll be 100. So each one now holds a hundredth of the space, and I went
from needing ten points to, of course, 100 points
in order to cover the same amount of space.
>> Alright, so that definitely seems like the mild rebuke of dimensionality.
>> Yes.
>> But doesn't seem that bad.
>> Okay well, what happens if I now move into three dimensions?
So now, if I want to cover the same amount of, you know,
diameter space for, you know, sufficient
definition of diameter. I'm going to have
to do a bunch of copying and pasting that I'm not willing
to do so, you know, there would be more x's here and
you know, there will be x's there and an x here and
it'll just kind of go and fill up some space and you
know, I'm not going to do this whatever but [SOUND] and you'll get
x's everywhere. And you notice, I need a lot more X's than
I had before. And by the way, I'm just
showing you the outside of this little cube, there are
actually X's on the inside as well, that you
can't see. How many X's do you think I have?
>> I don't think you drew any X's. You're
just like scribbling on the side of the cube.
>> These are X's.
>> You, you were doing so well for awhile, and then just lost it entirely.
>> Well, wouldn't you lose it if you had to write 1000 x's.
>> Hm. No
because I would use computers to help me but yes, yes it is very
frustrating to have to have that many x's. And so but in particular in
this case we're talking about data points in a nearest neighbor method and that,
boy that does seem like a big growth from ten to a 100 to 1000.
>> In fact the growth is, exponential.
>> Exponential
>> >Right. So if we went into four dimensions, which
I'm not going to draw, then we would need not
1,000, but 10,000 points. And if five dimensions we would
need 100,000 points. And in six dimensions, we would need 1,000,000
points. And so on and so forth. So something like.
Ten to the D, where D is the number of dimensions.
>> Wow.
>> Right. So this is really problematic right.
In my little nearest neighbor method, wanted to be
able to say, well, I want to make
sure the neighborhood remains small, as I add dimensions,
I'm going to need to grow the number of points that
I have in my training set exponentially. And that's really bad.
And by the way, this isn't just an issue of
kNN. This is true in general, don't think about this now
as nearest neighbors in the sense of kNN, but think
of it as points that are representing or covering the space.
And if you want to represent the same sort of hyper-volume
of space as you add dimensions, you're going to have to get
exponentially more points in order to do that. And
coverage is necessary to do learning. So the curse
of dimensionality does not just to kNN.
It is a curse of dimensionality for ML period [SOUND].
>> You mean for me?
>> Yes. Because of [INAUDIBLE]
>> [LAUGH] Okay. And that seems really problematic because it's very
natural to just keep throwing dimensions into a machine learning problem.
Like it's, it's having trouble learning. Let me
give it a few more dimensions so, to give
it hints. But really what you're doing is just
giving it a larger and larger volume to fill.
>> Yeah. And it can't fill it unless you give it more and more
data. So you're better off giving more data than you are giving more dimensions.
>> Zoinks.
>> Mm-hm. There's an entire series of lessons that
we will get eventually that, that deals with this issue.
>> The issue of?
>> Dimensionality.
>> Finding the right dimensionality?
>> Yeah.
>> That would be a useful thing.
>> It would. But it's far off in the future. It's like infinitely
far in the future. So we'll worry about that in a few weeks.
>> Okay.
>> Okay. All right. So there you go, Michael.
Curse of Dimensionality is real and it's a real problem.
>> Where did that term come from, it's a cool
term. I think it came from, oh what's his name. Bellman.
>> Oh, Bellman, like the dynamic programming guy.
>> Yeah, the dynamic programming guy,
uh,the Bellman of Bellman equation guy.
>> Which we haven't gotten to yet in the course.
>> Which we haven't gotten to in the course but we will get to in the
course. Because it's central. So it looks like
actually, the element's central to a lot of things.
>> Wow.
>> Sometimes it gives us equations that
helps us but sometimes it gives us curses.
>> [LAUGH] Curses Betterman. Foiled again.
>> [LAUGH]