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.
MAP Estimation for MRFs and CRFs
Loading...
Compétences que vous apprendrez
Algorithms, Expectation–Maximization (EM) Algorithm, Graphical Model, Markov Random Field
Avis
4.6 (212 notes)
- 5 stars151 ratings
- 4 stars45 ratings
- 3 stars11 ratings
- 2 stars3 ratings
- 1 star2 ratings
JR
Jan 29, 2018
Great course! It is pretty difficult - be prepared to study. Leave plenty of time before the final exam.
AK
Nov 09, 2017
Awesome course... builds intuitive thinking for developing intelligent algorithms...
À partir de la leçon
Learning Undirected Models
In this module, we discuss the parameter estimation problem for Markov networks - undirected graphical models. This task is considerably more complex, both conceptually and computationally, than parameter estimation for Bayesian networks, due to the issues presented by the global partition function.
Enseigné par
Daphne Koller
Professor
So far we've talked about MRF and CRF learning purely in the context of maximum
likely destination where our goal is to optimize value likelihood function or the
conditional likelihood function. But as for Bayesian networks maximum
likely destination is not a particularly good regiment and it's very susceptible
to over-fitting of the parameters to the specifics of the training data.
So what we'd like to do is we'd like to utilize some ideas that we, exploited
also in the context of Bayesian network. Which are, ideas such as parameter priors
to soothe out our estimates of the parameters, at least in initial phases.
Before we have a lot of data to really drive us into the right region of the
space. So in the context of Bayesian networks
that was all great, because we could have a conjugate prior, on, on the parameters,
such as the derscht laid prior that we could then, integrate in with a
likelihood to obtain a close form conjugate posterior and it was all
computationally elegant. But in the context of MRF's and CRF's,
even the likelihood itself is not computationally elegant and can't be
maintained in closed form. And so, therefore the posterior is also
not something that's going to be computationally elegant.
And so the question is, how do we then incorporate ideas such as priors into MRF
and CRF learning, so as to get some of the benefits of regularization?
So the ideal here in this context, is to use what's called map estimation, where
we have a prior, but we're instead of maintaining a postiariary is close form,
we're computing what's called the maximum, postierory estimates of the
parameters. And, this in fact is the same notion of map, that we saw when we did
map inferencing graphical models, where we were computing a single map
assignment. Here continue in this thread of Bayesian learning as of form inference
we're computing a map, inference estimate of the parameters.
So concretely how is map inference implemented in the context of an MRF or
CRF learning. A very typical solution, is to define a,
Gaussian distribution over each parameter theta i separately, And that is usually a
zero mean, uni-variant Gaussian.
[SOUND] with some variance. sigma^2.
And, the variance of sigma squared dictates how firmly we believe that the
parameter is close to zero. So for, small variances we are, very
confident that the parameter is close to zero and are going to be unlikely to be
swayed by a limited amount as data, whereas sigma gets larger we're going to
be more inclined to believe, believe the data early on and move the parameter away
from zero. So we have such a parameter prior over
each data i separately, and they're multiplied together to give us a joint
parameter prior. So the parameter prior over each is going
to, over each parameter is going to look like this.
This sigma^22. is called a hyperparameter.
And it's exactly the same kind of beast as we had for the Dirichlet
hyperparameters in the context of learning these in the works.
The alternative prior that's also in common use, is what's called the
Laplacian Parameter Prior. And the Laplacian Parameter Prior looks
kind of similar to the Gaussian, in that, it has an exponential that, increases as
the parameter moves away from zero. But, in this case, the increase in the
parameter depends on the absolute value of theta i and not on theta i^22, which
is what, the behavior that we would have with the Gaussian.
And so this function looks, looks as we see over here, with a much sharper peak,
around zero, that effectively corresponds to a discontinuity, at theta i equals,
equals zero. And, we have again such a prior, a
Laplacian prior to theta i over each of the parameters, of theta i which are
multiplied together. Just like the Gaussian, this distribution
has a hyperparameter. Which in this case is often called beta.
And the hyperparameter just like the variance, of, in the Gaussian
distribution Sigma squared, dictates how tight this distribution is around zero.
Where tighter distributions correspond to cases where the model is going to be less
inclined to move away from zero, based on limited amount of data.
So now, let's consider what map estimation would look like in the context
of these two distributions. So here we'd have these two parameters
priors rewritten, the Gaussian and the Laplacian.
And, now map estimation corresponds to the arg max over theta of the joint
distribution, P of D comma theta, so we're trying to maximize, oh, we're
trying to find the, theta that maximizes this joint distribution.
And by the simple rules of, probability theory, this joint distribution is the
product of P of D of given theta which is our likelihood.
Multiplied by, the prior p theta. And, because of the linearity of the, not
linearity, sorry, the lognicity of the logarithm function, we have the, this is
the same as doing arc max of theta, of our log likelihood function.
Which is just the log of the likelihood. And the log of, the parameter prior.
So now looks at what these logarithms look like in the context of these two
priors. And so this is, I'm actually drawing the
negative log of p of theta and the negative log of p of theta for a Gaussian
Distribution is simply a quadratic. And so we have a quadratic penalty that
pushes the parameters towards zero. And this is the same for those of you
who've seen this in the machine learning class, for example as doing one
regularization. Over the parameter theta i.
The distribution that, if you now do the same for the Laplacian distribution,
we're going to get. the penalty that pushes the parameter
towards zero in a way that depends on the absolute value of the parameter.
And, this is equivalent to L1 regularization which again, some of you
might have seen in a machine learning class.
So this is a linear penalty. Now these penalties although they both
push the parameters towards zero. Are actually quite different in terms of
the behavior. So if we look at what l two does.
In, when the parameters far away from zero, sort of towards the edges.
The quadratic penalty's actually quite severe and it pushes the parameter down
dramatically. But as the parameter gets small, so
closer to the case of theta I equals zero, the pressure to move down
decreases. So, effectively you're, it's quite
legitimate for the model to have a lot of parameters that are close to zero but not
quite zero and there isn't a lot of push at the point to get the parameters to hit
to zero exactly. And, so that means that models that use
L2 regularization are going to be dense. That is, a lot of the theta I's are going
to be non-zero. Conversely when you look at the L1
regularization you see that there's a consistent push, towards zero regardless
of where in the parameter space we are. And so it's in the interest of the model
to continue pushing parameters that don't impact significantly, the log likelihood
component and push them towards zero. And so for L1 regularization we're going
to get models that are sparse, and sparsity has it's own value.
Because the sparser the model the easier. It is to the inferences in general,
because sparsity corresponds to, in principle removing edges or removing
features from the graphical model. Which in turn can remove edges, and make
inference more efficient. And so L1 regularization or the
corresponding Laplacian penalty is often used to make the model both more
comprehensible as well as computationally more efficient.
So to summarize, when we're doing learning in undirected models.
The parameter coupling that we have in the likelihood function prevents us from
doing Bayesian destination efficiency. That is maintaining a posterior
distribution over parameters. However, we can still use the parameter
as a notion of parameter priors to avoid the over fitting that we would get with
maximum likelihood destination. And specifically, we're going to use map,
as a substitute for MLE. The most typical priors used in this
context are L1 and L2, or Gaussian and Laplacian And both of these drive the
parameters towards zero which has the effect of preventing the model from going
wild and using very drastic parameter values that allow us to over fit the
specific training data that we've seen. Now while this behavior is shared among
these two models there's also a significant difference between them in
that the L1 or Laplacian distribution can be shown both empirically and provably to
induce sparse solutions and therefore it performs for us a form of feature
selection or equivalently structured learning in the context of MRFs and CRFs.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
