Probabilistic graphical models (PGMs) are a rich framework for encoding probability distributions over complex domains: joint (multivariate) distributions over large numbers of random variables that interact with each other. These representations sit at the intersection of statistics and computer science, relying on concepts from probability theory, graph algorithms, machine learning, and more. They are the basis for the state-of-the-art methods in a wide variety of applications, such as medical diagnosis, image understanding, speech recognition, natural language processing, and many, many more. They are also a foundational tool in formulating many machine learning problems. This course is the third in a sequence of three. Following the first course, which focused on representation, and the second, which focused on inference, this course addresses the question of learning: how a PGM can be learned from a data set of examples. The course discusses the key problems of parameter estimation in both directed and undirected models, as well as the structure learning task for directed models. The (highly recommended) honors track contains two hands-on programming assignments, in which key routines of two commonly used learning algorithms are implemented and applied to a real-world problem.
EM in Practice
Loading...
來自 Stanford University 的課程
Probabilistic Graphical Models 3: Learning
201 個評分
從本節課中
Learning BNs with Incomplete Data
In this module, we discuss the problem of learning models in cases where some of the variables in some of the data cases are not fully observed. We discuss why this situation is considerably more complex than the fully observable case. We then present the Expectation Maximization (EM) algorithm, which is used in a wide variety of problems.
與講師見面
Daphne KollerProfessor
School of Engineering
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 asymptote 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 necessarily 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 expectation 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.
