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.
PGM Course Summary
Loading...
Do curso por Stanford University
Probabilistic Graphical Models 3: Learning
167 classificações
Na lição
PGM Wrapup
This module contains an overview of PGM methods as a whole, discussing some of the real-world tradeoffs when using this framework in practice. It refers to topics from all three of the PGM courses.
Conheça os instrutores
Daphne KollerProfessor
School of Engineering
We've spent the entire course talking about probabilistic graphical models,
we've talked about variants of probabilistic graphical models on the
presentation site, different inference algorithms that can be used to answer
various types of questions about probabilistic graphical models, and
algorithms that can be used to learn probabilistic graphical models from data.
Now let's take a step back and think about probabilistic models and look at
what they might do for us. So, first,
why probabilistic graphical models? So probabilistic graphical models are in
some sense the synthesis or the marriage of foundational ideas from statistics and
important techniques from computer science.
On the statistics side, we get sound probabilistic foundations that tell us
about probability distributions and how they can be used to think about
uncertainty and various manipulations on the probability distribution such as
conditioning and techniques such as value of information or decision making that
can be used to build on top of probability distributions to make
decisions. From the computer science side, we get
the idea of taking this probability distribution over very high dimensional
space and using ideas such as graphs, as a data structure for exploiting
algorithms that, that. That, allow us to manipulate these high
dimensional objects very efficiently. And it is these ideas that we got from
computer science. That allowed us to take, these sound
probabilistic foundations and make them applicable to the kinds of complex real
world problems that we're now facing, in many scenarios.
Now, a key component of the ability to take a high dimensional probability
distribution and considering, consider it as an object, is the fact that we have
now obtained a declarative representation of our knowledge about the world.
So that declarative representation, which is a model, a probabilistic graphical
model, is a stand alone unit that we can consider separately of any algorithm that
we then use to manipulate it. Now that's important because it allows us
to refine the model, separately from refining the algorithm, that that we're
using. So we can develop the model, and consider
whether it's the appropriate one for application.
And then we can apply one or multiple different algorithms to try and answer
questions regarding that model. It also allows us to separate out the
model construction phase from the inference phase, and the model
construction can involve one or both of elicitation from a domain expert, or
learning from Dana, and we talked extensively about learning methods and
also to some extent about elicitation methods.
Now, when would we apply probabilistic graphical models?
So we would apply probabilistic graphical models when we have noisy data and
uncertainty. That's pretty much true in any
application. So that, that's pretty much a given.
they're also particularly useful when we have lots of prior knowledge that we want
to embed into our model it's often easier to do this in the context of probilistic
graphical models then in a variety of other approaches for example in many
traditional machine learning settings its actually quite difficult to incorporate
prior knowledge in as natural a way as one can do here.
probabilistic graphical models are particularly useful when we have, when we
wish to reason about multiple interrelated variables.
So, if you're trying to predict just a single variable probabilistic graphical
models might not be the most ideal solution and there might be.
A range of other methods that are equally or more competitive from, say,
traditional machine learning. But when you're trying to reason about
multiple variables simultaneously, then the ability to incorporate the
interrelationships between them is often very powerful, and, and here,
probabilistic graphical models can really shine.
Another useful place for probabilistic graphical models brings significant value
is when we want to construct richly structured models that are constructed
from modular building blocks. So when we're trying, for example, to do
fault diagnosis or medical diagnosis, we often have this little building blocks of
models that can recur across different models, for different diagnostic problems
and this architecture allows us to take these building blocks and construct very
rich models from those very quickly by reusing components.
So, we've talked about probabilistic graphical models in terms of the set of
design choices. There is design choices on the
representation side. the inference algorithm that we choose to
use, and on the learning algorithm that we might adopt should learning be
required. It turns out that these design choices,
although the declarative representation allows us to separate them and consider
each them in isolation, and develop each of them separately, they're not actually
totally separate. And it's important to consider the
interactions between them. So on the representation side it's clear
that which representation we choose affects the cost of both inference and
learning. We've talked about differences in the
cost of inference for different types of, of graphical models and also we saw that
in the learning setting there is very different learnability and complexity
issues when you're learning say directed or undirected models.
The inference algorithm is also interrelated with everything else.
So the inference algorithm for example is used as subroutine in many of the
learning algorithms that we showed, for example in MRF or CRF learning even in
the complete data case and in any setting when we're learning with incomplete data.
And so, thinking about the complexity and properties of our inference algorithm is
critical in designing good learning algorithms.
And we also know that some inference algorithms are only usable in certain
types of models and so we're aiming for a particular inference algorithm that
affects our choice of representation. And finally the learning algorithm also
imposes significant constraints on the modelling.
Because our ability to well identify the, the correct patterns from the data impose
significant constraints on the expressive power, for example, our model.
And only certain types of patterns might be identifiable given the amount of data
we have, and the type of data we have, complete or incomplete, for example.
So lets look at one example of some of these trade-offs in the context of image
segmentation. So here one of the first design decisions
that we need to make is whether we're going to try and model this as a Bayes
net, so it's a directed graphical model.
And MRF or a CRF, where we're trying to predict the segment labels or the, the
pic, the super pixel labels S sub I, given features.
X. So we're trying to do P of S, given X,
rather, than a join distribution. What are some of the tradeoffs that we
might want to consider for this kind of decision?
Well one is the naturalness of the model. So initially just thinking about this.
It seems fairly clear that a directed model where we have directed edges from
one super pixel to the other doesn't seem like a particular natural, a particularly
natural choice in this context because which direction would we pick.
And what implications would this have if we went, for example, using directed
edges from the top right corner of the image to the bottom right corner of the
image, it just doesn't seem to make sense.
And so a more natural modeling paradigm here seems to be the MRF or the CRF.
But that still leaves us the question of which of those should we use.
And here for example, one possible design criterion that we ought to consider is
that we might want to use a very rich feature representation.
That is that these features X should be richly structured and count different
gradients and different gradients of texture and color across the image for
example, different histograms. These rich features are often highly
correlated with each other and we know that the correlated features are hard to
model in the sense of capturing correctly their correlation structure and so in
this case. A CRF seems like it might be a better
choice. Because it avoids the issue of how do we
model the correlation between these, the correlation structure between all these
rich features. And so it allows us to use rich features.
Without falling into traps of incorrectly modeling the correlations, which might
diminish our performance. Now another related question is that we
need to consider is the cost of inference in this kind of model, and that comes
back and influences the modeling. So for example for certain types of
models as we've discussed for example when the when the connectivity when the
structure in the potentials in the MRF or the CRF is associative or regular.
Then, we know that we can apply very efficient inference algorithms that
utilize, min cuts and other combinatorial graph algorithms that are much, much
faster than applying say, message passing schemes.
So that's all very but then it imposes on us the constraint of making sure that
our, that our potentials in fact are assocative, and that does have
implications about the baility of our model to correctly capture the structure
and the distribution, so for example it is very easy to capture using
associatives potentials the fact that we espect adjacent.
Pixels to have the same class, to have the same label.
That's very easy to capture using this type of potentials, but not quite so easy
to capture is for example the, the constraint, not the constraint but the
tendency that cows are on top of grass. As opposed to on top of water or on top
of road or on top of sky. That's a potential that goes between one
class and the other, and it's very difficult to come up with with a with an
associate to function that actually captures these kinds of targets.
Another thing to consider is training costs when you think about this.
So, here in fact, MRF or CRF are more expensive than Bayesian networks.
Now we might still in this case want to take the hit because of the, because of
the benefits on the modeling side, but we've already seen that in the case of
complete data tr, training a Bayesian network is considerable more
computational effective than training an MRF or a CRF and so, it's a place where
we're taking a pay, we're taking a hit for a design decision we made on the
representational side. And then finally.
if we have to learn with missing data that sets up yet another constraint that
we want to think about and might not be obvious going in.
So say that we have a scenario where the segment labels are not observed.
That is we're trying to learn, to segment.
In an unsupervised way. So from unsupervised data.
Well, in this case, the S's are unobserved,
they are latent. Which means that optimizing P of S given
X doesn't even make sense because s is never observed.
And so in this case we simply cannot learn a CRF.
In this context because there is no the objective of optimizing the labels S
given the features just is completely undefined in the setting and so at this
point we have to resign ourselves to learning using a different
representational scheme. And so this is another case where we see
the intertwining between different choices that we make and different
constraints that we have in that in this case learning with missing data interacts
with the choice of representation in potentially unexpected ways.
Now, one important component,
one important benefit of probabilistic graphical modules and their modularity,
is that they allow us to mix and match different ideas within the modeling
framework. And the reason why that's important is
because it gives us a much greater richness of options than by considering
individual topics that we, that we learned as a solution in and of itself.
We can often combine those in interesting ways.
So to see one example of that let's go back to our image segmentation that we
just talked about and think about models that actually misdirected and undirected
edges. So here, we might, for example if we're
trying to learn image segmentation for unsupervised data. We might have
undirected edges over the labels S, as an MRF, just as we see in this diagram,
which is the natural directionality or rather the lack of directionality that we
discussed before. But we have directed edges from the S's
to the features XI. And this is a model that is half undirected, it's undirected
at this level and it's directed going from the S's to the X's.
Now why is that good? It's good because, first, it gives us a
meaningful optimization objective, that is we're trying to optimize using our
model parameters and our model structure, the ability to explain the images that
we've seen using a using the segment characteristics or the class label
characteristics. But why is it,
so in that respect it's a generative model that by forcing us to in some sense
generate the observed data can allow us to learn something about the statistics
or the patterns in, in the distribution. But by allowing, by making this model
directed as opposed to undirected which we could have done by doing an MRF over
the entire set which would also have been a generative model, it actually greatly
facilitates the learning because each of these potentials, P of XI given SI can be
learned separately without trying to optomize over the model as a whole and so
is considerably more efficient. So this is the case where mix and match
is, a, a better strategy than a unified model that is entirely directed or
entirely undirected. Another type of mix and match can occur
on the inference side. We learned about a variety of different
inference algorithms, and we might be tempted to just take a model and just
throw it into a black box of one of those inference algorithms or another.
But it turns out to be much more beneficial in certain cases, to consider
applying different inference algorithms to different pieces of the model.
So for example we might use something like belief propagation or Markhoff chain
Monte Carlo on some subset of variables, but on certain sets of variables we can
do exact inference which gives rise to much more accurate results over those
subsets and perhaps makes the convergence properties of our algorithms considerably
better as well as the accuracy that we get.
So, let's take an example, this is an bipartite gr-, MRF that we have seen
before where we have a set of variable of A on the one side and B on the other as
we have seen before and let's assume that there's
fairly dense connectivity between the variables and maybe even full
connectivity between the a's and the b's. Now, let's think which algorithm we might
want to use for this kind of a model. If there is a very small set of As or a
very small set of Bs, then we can use exact inference, but that's not usually
the case, and so we might have to resort to a proximate inference.
One possibility is to apply belief propagation, but if you look at this
graph, you can see that it has a very large number of fairly tight loops.
And we know the tight loops are a problem for belief propagation and so we might be
worried about the quality of the convergence and the quality of the
answers that we get. Another approach is to use something like
the Markov chain Monte Carlos such as Gibb sampling.
but in this case if we have a lot of A's and a lot of B's then we're sampling over
a large very high dimensional space. And we know that sampling methods in high
dimensional methods have, again, limitations in terms of the rate of
convergence and the quality of the answers.
So one possibility that we might consider here is a variant of of Markov chain
Monte Carlo where we only sample for example only, over the A's, say there's
fewer A's than B's. So we sample over the A's and then for
each assignment over the A's, so for each little assignment, A1.
of M up to AK then, which is one of our particles, we maintain.
A distribution. Over the Bs, in closed form.
So we're effectively doing exact inference over the B's and sampling only
over the A's which is going to considerably improve the rate of
convergence as well as the statistical properties of our estimator.
And this is just one example that we in that we can talk about other examples of
current belief propagation that we can construct larger clusters in where in
each we run exact inference there's many, many such examples where mixing different
inference algorithms can be tremendously beneficial.
Mix and match on the learning side is equally useful.
So again, we can apply different learning algorithms to different parts of the
model. So, going back to our image segmentation
example, and now we're assuming we're back in the case where we're doing
learning from fully observed data. So we're, going to consider CRF.
it's very commonly used to to train, a high quality.
easily trainable models such as a support vector machine or some kind of logistic
regression for P of S given X. And we can train that very efficiently.
We can use sophisticated machine learning tricks like kernel methods or various
other ideas to get really high accuracy node potentials.
And then fix those and use CRF learning for the higher order say the pair Y's or
even high order potentials and it turns out that when you do that it's actually
less susceptible in many cases to over fitting and its much, much faster to
train. So by putting together different pieces
of functionality different ideas it turns out that we can build some very nice
integrated applications and I just want to end this discussion with one example
of a cool application that puts together a whole range of different of different
ideas into a single framework. So this is a
a work from Microsoft Research, which has a longstanding tradition in the use of
probabilistic graphical models, and it puts together ideas from, from speech
recognition, from diagnosis, and from decision making under uncertainty.
So let's watch the video and then talk about it briefly.
Hi, thanks for coming to the triage kiosk I am in touch with the best doctors in
the world. Are you here for your child or yourself?
No, for my child. So, how can I help you?
She's been having diarrhea. Oh, no.
Sorry to hear that. Hi there.
What's your name? Manu /g And how old are you?
Five. So, five years old, right?
Yeah. Almost six.
Okay. Six years old.
Have you felt nauseous? I don't know.
So what we can see here is the use of value of information to figure out which
questions ought to be asked, that are going to be the most useful for improving
the quality of the diagnosis and the ability to make decisions in this,
Bayesian network that we see over here on the right.
I'm sorry. Has your child been vomiting at all?
No. Okay.
So lets see, has there been a fever? Slight.
Have you been feeling tired lately? Yes.
Lets see, how about abdominal pains? He's not been complaining about it.
Has your tummy been hurting? Yes.
Oh, I'm really sorry. I hope it will heal better soon. Another
component here is the use of the current model, the current scenarial situation to
guide the speech recognition system so as to get better quality of results from
speech recognition system. So instead of doing totally unguided
speech recognition system, one uses the current scenario as the model, as, as the
system is understanding it to guide the priors on what the person is probably
saying. Okay. Do you happen to know if your child
has been losing weight? No.
That's okay. Have you noticed whether your child's
stool looks funny? Is it black or darker then usual?
It is darker then usual. Okay, let's see.
Considering everything you've told me, I'd like to schedule an appointment with
the doctor just to be sure. However, not to worry.
I am not that concerned at this point. So to summarize.
Probabilistic graphical models provide us with an interpreted coherent framework
for reasoning and learning in complex uncertain domains.
And people over the years have developed an enormous suite of tools that can be
used for accomplishing different tasks within this framework.
And we can put them together within the single unified framework to solve much
harder problems than any single tool can do alone.
We've seen, over the course of different examples in this course that this
framework is used in a huge range of applications and there's many more in
which this can be used. And so overall, we can see that, there's
a lot of places where one can continue to work in this paradigm,
both in utilizing it, for applications that might be of interest and new ideas
that come up and also, improving the foundational methods for representation
inference and learning, that could allow us to address yet new problems.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
