0:00

We describe the expectation maximization algorithm and gave the formulas for how

to use it but we didn't talk about how it might perform in practice so let's talk

about that a little bit. So first let's look at how EM behaves as

a function of the number of iterations. So over here on the x axis we see the

number of iterations going from zero to 50 and on the y axis we have the log

likelihood of the average training instances so averaged over all the

training instances. Which is the objective that the algorithm

is trying to optimize. Remember, EM is the maximum likelihood

optimization algorithm. So what we're showing here is effectively

how the objective improves and so the first observation that we have is that as

we effectively stated as a theorem. So this shows that the theorem is true.

the EM, the log likelihood increases

consistently, monotonically, over iterations, t.

So that's good. So that shows our theorem is correct.

But let's understand what happens now as the algorithm continues to evolve.

We see that in the earlier iterations, so up to about, I don't know, iteration

eight or ten in this context, the algorithm, the log like exhibits a very

sharp improvement. But then it aymptote and so we might

think that when we get to the ration tenerso right around here maybe there's

no point continuing to run because there's no more increase and we've

achieved convergence and we might as well stop.

Turns out that's not quite right. What we see here is for the same model

with the same graph, the x axis iterations and the y axis is the value of

different parameters in the model. And over here we see the same iteration

10 and we see that although the log likelihood no longer continues to improve

after duration 10 as we can see on the left hand graph, various parameter values

actually exhibit extremely sharp changes after duration ten.

specifically the blue parameter goes down significantly, the black parameter goes

up significantly.

And so and so we see that the convergence in the likelihood space which is what we

have on the left is not the same as convergence in parameter space which

means that if we're trying to gauge convergence, we probably ought to look at

convergence on parameter space. However, it's also important, to realize

that carry EM through the convergence is not necassarily the best ideal.

So what we see here, is the same graph of the training log likelihood per instance,

but on the right hand side, we look, we can the, log likelihood per instance, on

test instances, that is instances that the algorithm was not trained on, and

what we see, is that, while the log likelihood of testt instances also

increases sharply. Up to about iteration ten.

After that, it starts to decrease gradually and so, in fact, as the

algorithm is continuing to modify its parameters and slightly improve the

training log likelihood, the test log likelihood in this particular case

actually goes down. So this is an example of over fitting.

In this case it's numerical over fitting to the specific data instances that we

have, or the noise in those data instances.

And in order to avoid that there's two main strategies that people adopt.

The first is to use a validation set, or cross-validation, to determine the time T

at which we should stop doing iterations and so we basically measure m-log

likelihood on the test set and say okay, at this point we can see that it's

starting to go down and so we should just stop doing iterations.

This is potentially a computationally costly procedure however because

evaluating the test log likelihood needs that we need to run inference.

On the test sentences and that can be expensive.

So a cheaper strategy is to use some kind of map assignment rather than maximum

likelihood destination. With the same benefits that we saw when

doing estimation for the complete data case.

Basically a prior smooths out the estimates and makes them less susceptible

to noise in the training data. So that's one aspect of the behavior of

the expectation maximization algorithm. And by the way, the same phenomena will

also happen if we use gradient ascent, so this is really orthogonal in many ways to

the specifics of the optimization algorithm.

Except the very sharp increase at the beginning which is very characteristic of

the m. A very different problem that we already

mentioned before is the fact that both EM and gradient ascent effectively achieve

only a local optimum of the log likelihood function.

So what we see over here is on the x axis the number of samples m that we're

training on. So this is not iterations anymore this is

the number of samples. and the y axis is the number of the

distinct local optima that the algorithm found over 25 iterations.

So sorry 25 applications of the m algorithm initialized at different random

starting points. So what we see here is we have three

lines. The blue line represents 25% of missing

data. The red line is 50% missing data, so 50%

of the entries at randomly, were, were omitted.

And the black line is when you have a hidden variable.

So in this case, the fraction of missing data is actually not perhaps as large,

but there is one variable that we never get to observe in any of the instances.

And what we see, in both the blue line, for the 25%, and the red line, for the

50%. Is that, initially, we have a very large

number of local optima. In fact, initially, the pretty much every

iteration of the m finds a distinct local optima.

But then as we have more and more training instances.

The algorithm, begins to be able to better identify, a global

a, a smaller number of optima come to the forefront.

The other ones kind of, become less dominant or disappear.

Now the more missing data we have so in the red line.

The slower this process to reduce the number of local optima.

And when we have hidden variables, which is this black line over here, the local

optima never go away. Now, you might say that fine, we have

local optima, but maybe, we don't care. Maybe these local optima are all about

the same and it doesn't really matter which one we land at.

Unfortunately that doesn't, turn out to be the case so here we have on the x

axis, sorry on the y axis, rather. The, log, particular log likelihood

value, that, might be achieved, on, the training set, by

By a run of expatiation maximization. And then the Y axis, we have the percent

of runs that achieve a particular log likelihood value.

And we can see that there are That there are, huge variation, in the

log likelihood values that are achieved by different runs of the expectation

maximization algorithm. Which brings us to the point that

initialization is absolutely critical to the performance of an algorithm such as

expectation maximization. And there's different strategies that

people adopt in order to try and get to a better local optimum.

So first and perhaps. easiest implement in some sense is the

use of multiple random research. So we randomly sample parameters for

example and we initialize 'em at these different points and we run 'em to

convergence and then we pick the run of 'em that has the highest training log

like we'd have to all of the objective that we're trying to optimize.

In some cases, we might have some amount of prior knowledge, that we might use to

initialize the algorithm, for example, we can have some prior knowledge about the

parameter, or if we're initializing on the E step, we might have some prior

knowledge about the assignment say of, of variables to cluster, of, of instances to

clusters for example, from some other source.

Making them in graphic data for people or something like that.

And finally a common and quite effective initialization strategy is to use a

simpler algorithm rather than full scaling because it turns out that while

EM very powerful that also makes it more susceptible to getting stop in certain

local optimal where some simpler algorithms for example in the context of

missing over the hidden variables who might use a simpler clustering algorithm.

That you might have heard about in, in a different context.

K means or, how to work with [INAUDIBLE] clustering.

Which is a simpler algorithm. Not as powerful.

But. But is also somewhat less susceptible to.

Local optimum, and so we might initialize from that and, then run the M to get a

better, output then these simple algorithms might give rise to.

So to summarize we've seen that convergence of the likelihood function is

not the same as convergence of the parameters and so we have to decide which

one we actually care about. We've also seen that running the

algorithm to convergence, all the way to convergence, can lead to numerical

over-fitting. We talked about strategies to get, to

avoid this problem. we talked about local optima, and the

fact that they're unavoidable. And, furthermore, they increase with the

amount of missing data. So the more missing data we have, the

more local optima we have. And, furthermore, they decrease with the

total amount of data, but not if we have missing, not if we hidden variables, at

which point you're stuck with them no matter how much data you have.

We also show that local optimum are not a fake problem.

That is, which local optimum you land in can actually be a significant factor in

terms of the performance, that the algorithm achieves in terms of log

likelihood and, therefore, smart initialization turns out to be often

critical for the performance of algorithms you'll learn with latent

variables with and with missing data.