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 second in a sequence of three. Following the first course, which focused on representation, this course addresses the question of probabilistic inference: how a PGM can be used to answer questions. Even though a PGM generally describes a very high dimensional distribution, its structure is designed so as to allow questions to be answered efficiently. The course presents both exact and approximate algorithms for different types of inference tasks, and discusses where each could best be applied. The (highly recommended) honors track contains two hands-on programming assignments, in which key routines of the most commonly used exact and approximate algorithms are implemented and applied to a real-world problem.
Gibbs Sampling
Loading...
Del curso dictado por Stanford University
Probabilistic Graphical Models 2: Inference
286 calificaciones
De la lección
Sampling Methods
In this module, we discuss a class of algorithms that uses random sampling to provide approximate answers to conditional probability queries. Most commonly used among these is the class of Markov Chain Monte Carlo (MCMC) algorithms, which includes the simple Gibbs sampling algorithm, as well as a family of methods known as Metropolis-Hastings.
Conoce a los instructores
Daphne KollerProfessor
School of Engineering
We define the notion of the general Markov chain.
We talked about how certain conditions guaranteed that if we sampled from the
chain we achieve conversion sistationary distribution.
We then described how if we then generate samples from the Markov Chain we can then
use that to estimate properties of that stationary distribution like varying
statistics that we might care about. But the question of where the Markov
Chain might come from was left very vague.
It turns out that four graphical models people have constructed a general purpose
sampler that can be used to sample from any graphical model, and that class of
chains is called the Gibbs chain. So now we're going to talk about the
Gibbs chain and how to use in the context of graphical models.
So, here are target distribution, the one from which we would like to sample is
the, good ole, Gibbs distribution, P of Pi, of X1, up to XN.
And just as a reminder that P of Pi can equally well represent a, a Gibbs
distribution that we got from just the product of undirected factors.
A Markov net style distribution. Or it could, as well, represent a set of
factors that [INAUDIBLE] Bayesian network, reduced by evidence.
And so, that is the factor set Pi. And everything that I'm going to say from
now on is agnostic to where those, factors Pi came from.
If they came from a directed or an undirected model.
So, now our Markov chain state space. Is a set of complete assignments, little
x, to the set of variables big X. So we're sampling over, note, an
exponentially large state space. The space of all possible assignments of
the random variables in a graphical model.
So those little circles that we saw when we were talking about mark off chains,
and we were g, going from one state to the other.
Each of these now is now a complete assignment.
[INAUDIBLE]. So it turns out that the Gibbs chain is
actually a very simple and easy to understand, Markov chain.
And here's what it does. Assuming that I have a starting state,
little x. What I'm going to do is, I'm going to
take each variable in its turn, using some arbitrary ordering.
And I'm going to sample. A new value for that variable given
values for all of the rest. So let me introduce this notation, this
is an assignment. All.
x1 of the xn except xi. So for example if we had three random
variables: x1, x2, and x3. We would sample x1 given x2 and x3.
X2 given x1 and x3. And x3 given x1 and x2.
Right, so one at a time. Okay so let me, let me draw that out
because in order to make that clear. So here we would have, here's my current
assignment, let's say here's X1, X2, X3, and let's say that we have zero, zero,
zero as my initial assignment. So I'm going to start by.
Sampling X one from the probability of X one given X two equals zero.
And x3 equal zero, and let's say I end up with one, that other two haven't changed
yet. I now sample from p of x two, given x1
equaled the new value one, and x3 equals zero.
And say that's thay zero. Could.
And then I sample x three from x, the probability of x three given x one equals
one and x two equals zero and save our changes to the value one and so now this
is my new assignment 101 which gets substantiated into x five.
That is a single step of the Gibbs chain. It goes and potentially modifies, it
doesn't have to modify because you might end up staying in the same assignment.
Resampled every single variable, in its turn.
And when all of them are done, that's my new state.
So let's do this example in the context of a real graphical model.
So here is the good old student Bayesian network.
And I'm assuming that I have observed two of the values, two, values for two of the
variables. So I've observed l equals l zero and s
equals s one. And so now I have a product of, reduced
factors that represent the evidence that I received and only three variables are
now getting sampled because the other two are fixed so they observe values so now I
am sampling from P of P tilta of Phi, I mean, I like the sample from P tilta Phi
of DIG, given little S1 and L0. And so what I'm going to do in this
sampling process is I'm going to start out with some arbitrary assignment to
these three variables, D, I and G. So, for example, since it's arbitrary,
D0, I0, E0. And now I'm going to go ahead and sample
each of these in turn. And so I'm going to initially sample D
from. Of the, given.
I've. Zero.
G zero. SL0 and S1.
Okay? And we'll talk about how that's done in
just a moment. And that might give me D one by zero D
zero. And now I'll continue and I might sample
I. So I'm going to sample I from probability
of I given D one. E zero, L zero, S, one, they end up with
I one. Finally I sample G and it couldn't be G0,
I apologize because G only goes one, two, three.
So let's say it was G1 and now I sample G, from the probability of G.
Okay, so this was G1 here too, and this is the propability of, of mouse sampling
G, from the propability of G, given, D1, I1 that's where I am right now, L0 and
S1. And double G3, for the new finer.
Use this one. D1, i1, g3.
So how do I do this in a tractable way? So here is the trick that.
I mean, you might say, well. You're dealing with this intractable
distribution. I mean, you just moved the problem from
the original problem that we had to computing these conditional
probabilities. Why is that any easier?
Well, turns out it is. So let's look at the sampling stuff over
here where I sample'xi' from this conditional distribution and let's break
that down into these into its constituent definitions.
So this distribution, this conditional distribution is a ratio.
Between the join distribution of the value XI and the stuff on the right hand
side of the conditioning bar, divided by the stuff on the right hand side of the
conditioning bar. Now importantly, because each of these
is, is, an unnormalized measure divided by the partition function, the partition
function cancels and so I end up so if I had a one over z here.
The one over z cancels then I end up with the ratio to unnormalized measures, so,
the point being now, that this. Is a complete assignment.
And therefore the product of factors. So let's look at that in the context of a
concrete example, and see how that might help us.
So now we're doing an example that's a Markov network in order to demonstrate
that this is equally applicable to both. So this is our good old misconception
network where we have these four factors Pi one, Pi two, Pi three, and Pi four.
And let's imagine that we're trying to do P Pi of A given B, C, and D.
And we can see that what we have here is P tilde Pi of A, B, C, D divided by the
sum over A prime. And I'm using A prime to distinguish it
from this A over here, just to avoid ambiguity.
P tildify of sum over A prime, P tildify of A prime BCD.
And now I'm going to. Since each of these [INAUDIBLE] is a
product of the factors, I'm going to inject product of factors into each of
the numerator and denominators separately.
And so over here I end up with five one of ab times five two bc five three cd
five four ad. And similarly end up with exactly the
same expression in the denominator. Except I sum out, over A prime.
And, what, do we? Determined by looking at this expression.
Well, some things are immediately jump to ones eye which is the sine two bc appears
in the numerator and in the denominator and therefore I can cancel it and
similarly with 5-3 of cd. And so what I end up with here is a
product of these two factors. Five, one of ab and five, four of ad.
Which are the two factors. That involve A.
Well that's for the numerator, what about the denominator?
Well the denominator is just our good old.
Normalizing constant. So really what we have here is that this
is proportional to, Pi one, of A, little B times pi four of A, little D.
So this is a factor over A that I can compute, by multiplying two, singleton
factors in this case over A. Multiply them together and renormalize
and I get a distribution over a, from which I can sample, and we already talked
about how to sample from a discrete distribution.
So what is the computational cost, now, of this algorithm?
The sampling step for xi, given all of the others is simply this expression,
over here. Which is proportional to a product of
factors. And not just any old product of factors,
but just the factors that involves XI involve.
Just the factors that have XI in its scope.
Which means that I only care about XI and its neighbors in the graph.
Which, for a large graph, with tens of thousands of nodes, can be a considerable
savings, okay?
So only XI and its neighbors. So, do we like the Gibbs chain?
We've certainly defined it. Does it have the properties that we,
would. Like it to have?
Well, the answer is unfortunately, not always.
So, let's look at and specifically is a, is a regular change and we have
guaranteed convergence for unique station redistribution.
So the answer is unfortunately not and to that we're going to return to our old
enemy the exclusive-or network which as I said in other examples is the counter
example to pretty much anything is exclusive-or.
So let's look at the exclusive-or network.
So here we have Y which is the exclusive or of X1, X2.
And let's imagine that I observe. Y equals one.
And so these two disappear. And now I'm going to try and sample.
X one and X two, which I should be able, you know, if, if, if I were so lucky, I
would get the, each of the two possible states for X one and X two occurs with
probability a half. So let's imagine that I start out with
this one. And I'm going to now sample X one given X
two and Y. So I have my initial state is zero one
for X one and X two. And of course Y equals one is my
evidence. And now I'm going to sample.
what I'm going to sample, X one given X two and Y.
And that is a deterministic dependence, and the only possible value that I get is
zero for X one. Well, am I going to have any better luck
with X two? Nope.
I'm going to end up with exactly the same zero one that I started out with.
And I can do the exact same thing again, and you know what?
It'll work the same way every single time, and I will always end up with zero
one. Conversely, if I start out with one zero,
I will never leave one zero. This is a classical example of a non
mixing chain. On the other hand, if all factors are
positive, that is, if there are no zero entries in any of the factors, then you
can show that the Gibbs chain is regular. Now, however, it's important to realize
that regular doesn't mean good. So, I can make this chain regular by
adding a tiny probability epsilon of having y not be the exact exclusive orb X
one and X two. Now the chain is regular, because all
possibilities have probability non zero. And it's still going to mix extremely
slowly for values of epsilon that are small.
So regularity remember, is a very weak condition.
It says if you sample long enough, we will eventually converge.
But it doesn't mean it'll happen in a reasonable time frame.
And one such example of a very slow to mix chain actually occurs in practical
applications. So, here's one example.
Here, it's an example in our image segmentation domain.
And imagine that we're trying to resample, say, the class of.
let me use a different color. Of this super pixel here, and that we
have some fairly strong potentials that tell me that the class of this super
pixel, should be very highly correlated with the class of its adjacent super
pixels, because of the appearance being, very similar to each other.
Because I have some set of peer wise Markov network with some very strong
potentials that try and enforce consistency between adjacent super
pixels. So if it turns out that for whatever
reason, my initial assignment was actually wrong, so for example what is
often an error mode for set segmentation models is that is that road is often
labeled water or sky because the appearance is actually kind of a similar
and grayish kind of appearance so say that for, for example if I happen to
label all of these superpixels as say water, and now I'm going to use Gibbs
sampling. None of them are likely to move away from
their current assignment because each of the superpixels is really constrained by
strong pairwise potentials with its neighbors.
And so this notion of slow to mix Markov chains is not just a theoretical
construct that occurs with exclusive or it actually happens in practice a fair
amount. Now to summarize what Gibbs sampling does
is it takes the very challenging problem of inference in a Gibbs distribution.
And converts it to a sequence of easy sampling steps, where each sampling step
samples one variable, given all of the others.
This method has the advantage that it's probably the simplest Markov Chain for
probabilistic graphical model and it's very efficient to compute each of the
different stuff. The cause is that they are very slow to
mix, when the probabilities are peaked and the variables are very highly
correlated. And, it's only applicable in cases where
we can sample from a product of factors. Now, we can always do that in a discreet
graphical model, if our factors aren't too large.
But, if our samples are, but if we have, for example, either a very densely
connected Say Markov network or we have one with
continuous distributions where the product the factors isn't something has a
nice parametric form that we can sample, [INAUDIBLE] sampling might not be
actually applicable. And so there is non-trivial limitations
to the applicability of gift sampling and even when it applies, it is actually a
very slowed mix. And we often want to do something more
clever, and we'll talk about more clever algorithm later on.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
