Alright so let's see if we can figure out what
happens to this E function as in one step we update
the partitions and in the other step we update the centers.
So let's look at the partition one first. The way that
this partition is being defined is we, for each point
loop over all the clusters and find the cluster whose center
is closest to x in terms of squared distance. What happens
to E when we do that? Well we move a point.
>From one cluster to a different cluster only if it causes the
square distance to the center to go down. So that means that
the error, either stays the same if the point stays in the
same cluster or it goes down if it goes to a better cluster.
>> That makes sense.
>> So, can only go down.
>> Well, it can never go up. It's different than saying it can only go down.
>> Agreed, because it could stay the same. What happens
if it stays the same? I guess, not necessarily anything interesting.
>> Right.
>> But, certainly, when we converged, it stays the same.
>> Right.
>> Alright. Now let's look at the other side here. So that's
what happens when we move things into partitions. And in some sense
that seems easy. Because we only move things if it causes the
error to go down so it really is a lot like hill climbing
>> Mm-hm
>> On this side though what happens when we move the centers so could it be
the case that when we move the center
to some other place that the error goes up?
>> No.
>> And why do you say that?
>> Because the average is going to be the best way to represent
a set of points. On average, we should be able to demonstrate that.
>> I think we already have. We did this earlier in,
in the course when we were talking about minimizing the squares.
>> You are right. So, basically, you could take
that equation and you could just take the derivative of
it. Set it equal to zero and it will
turn out to be exactly the average. You're right that's
exactly right.
>> The error equation E that's right, yeah
so this is like really kind of neat.
When we moved points around we move it
to reduce error and we move centers around we
always move it to the center even though
this is a continuous space we always jump
to the center that actually has minimum error
under the assumption that we're holding the partition steady.
>> Right.
>> So this is just great.
>> So put them together, you're guaranteed to be,
let's see, what's the math term? Monotonically non-increasing in error.
>> Monotonically
non-increasing in error, very nice. And does that imply that thing
has to converge? Could we be monotonically non-increasing in error forever?
>> You could, in some worlds, but not in
this world. I, I think I could argue that.
>> Alright.
>> So a monotonically non-increasing function, is a function that
never gets bigger. So you could end up in a case
where you hit some point, like say zero error, and you
keep going. So, why wouldn't that happen here? Here's the argument.
You ready?
>> Sure.
>> There are a finite number of configurations.
>> Hm.
>> There have to be a finite number of configurations 'cause there's a
finite number of objects, and there's a finite number of labels they can have.
>> Mm-hm.
>> And once you've chosen a label for a bunch
of the objects, the centers are defined deterministically from that.
>> Right, so even though it is an infinite space as
we're tick-tocking back and forth, if we don't move the partitions
then the centers are going to be where they were.
So, the centers are quite constrained even though it's continuous.
>> Right, so, the only tricky part to
that is that you could have a point that
can go to either of, let's say, two
partitions, because the distance is the same. So you
have to have some way of breaking ties,
such that you always get the same answer. For
example, I will just say that if I, as a point, can go to any of two partitions,
I will pick whichever one has the lowest number.
>> Good idea. So breaking ties consistently
and you gave a particular role for
that is going to guarantee that we at
least don't kind of spin around not improving.
>> Right so let's see if what I just said makes sense. So
tell me if you buy this, they have a finite number of configurations.
If I always break ties consistently and I never go into a configuration with a
higher error, then at some point. Basically, I will never repeat configurations.
I'll never go back to a configuration that I was at before. And at some
point, I'll have to run out of configurations
because there are a finite number of them.
>> Yeah, nicely done.
>> So it converges, in finite time no less.
>> Finite time. Could it be exponential time?
because there is a lot of possible partitions.
>> So how many different configurations are there, there K to
the N because you can assign K to the first object, K
to the second object. K to the third object, so k
times, k times, k times, k times, k all the way up
to n, so that's k to the n. So, that's
a lot of possible configurations, but regardless, there's a finite
number of them and I suppose in practice, it's not
like you would look at every single one of them.
Because you're going to jump around very quickly because, of the
way distance metrics works. They point close together, they're always
going to be close together. So you're never going to try, assigning
each one to all possible configurations if they're close together.
>> Yeah, it tends to converge pretty fast.
So let's summarize some of these properties.
>> Okay.