Hi, in this module, I'm going to talk
about Gibbs sampling, a simple algorithm for approximately
computing marginal probabilities and [AUDIO OUT]..
You'll recall that a Markov network
is based on a factor graph.
And a factor graph gives a weight
to every possible assignment of variables in that factor graph.
And in a Markov network, we'll convert that weight
into a probability by first computing
the normalization constant.
Which is sum over all the assignments of the weight
of that assignment.
Divide by that normalization constant,
and we get the probability of assignment little x.
So in this object tracking example,
you see how we have a bunch of different assignments.
There are weights.
The partition function in this case is 26.
We divide each of these weights by 26.
And we get these probabilities.
So the cool thing with Markov networks
is that you can compute marginal probability.
And that's going to be our focus.
So marginal probability is going to be focusing
on one particular variable Xi.
And asking what values could it take on?
And to get that, we're going to sum
over all possible assignments where Xi does actually
equal P, the joint probability of that assignment.
And this example, if you look and ask
for the probability of x2 equals 1.
You sum over all the rows where x2
is equal to 1, that gives you 0.62.
And if you ask for x2 equals 2.
Then you're summing over the last two rows
and that gives [AUDIO OUT].
So now let me present Gibbs sampling,
just a simple algorithm for approximately computing
these marginals.
You could iterate over all possible assignments
and compute, but that would take exponential time.
So Gibbs sampling is going to follow
the template of local search.
Where we're going to go through each variable one at a time
and update them.
But unlike iterated conditional modes, which we saw before.
Gibbs sampling is a randomized algorithm
tailored for the purpose of computing a marginal.
So let's present the algorithm.
So, we're going to initialize the assignment
to some completely random assignment.
And then we're going to loop through each of the variables
until convergence, which I'll talk about a little bit later.
We're going to set the assignment Xi equals v
with this probability,
The probability of Xi equals v, given x minus i
equals x minus i.
So this my x minus i notation, just
refers to all the variables except for Xi.
So I'll come back to this in a second.
But let me just highlight kind of the general flow
of the algorithm.
So suppose you have three variables.
Gibbs sampling is going to provide a sample x1,
holding the other ones fixed.
And now it's going to move on to x2, holding the others fixed.
And update x2, and then go to x3,
and then it's going to cycle back to x1, x2, x3 and so on.
So now how do I sample Xi equals v?
So here is one example.
What we're going to do, is we're going
to try assigning Xi equals v, and getting some weight.
So for every possible assignment of x2,
I'm going to get some weight.
And now remember in ICM, I would just
simply take the value that produced the largest weight.
But the main difference with Gibbs sampling
is that I'm going to take these weights,
and I'm going to normalize them to produce a probability.
Again, normalizing is summing these values, so I get 5.
And dividing by 5 to get probability 0.2, 0.4, 0.4.
And now I'm going to sample x2 equals one of these values,
according to this probability distribution.
You can visualize that sampling process
by the interval from 0 to 1.
Where I have a number of segments
representing the different possible values of x2.
And the length is exactly the probability.
So probability of x2 equal to 0, probability of x2 equals 1,
and probability of x2 equal to 2.
And then I'm going to throw a one dimensional
dart at this line.
I'm going to hit it somewhere and I'm
going to take whatever value is specified by that interval.
OK, so now I have a new value for x2 here.
And now I proceed to the next variable
and so on and so forth.
So that produces a sequence of samples of the assignments.
And the remaining thing to do is to aggregate them.
So, I'm going to every time I go through this loop,
I'm going to increment a counter or variable
i of the particular value that I saw.
OK, and at the very end, I'm going to compute an estimate P
hat, of Xi equals little xi.
And this is going to be simply the normalized version
of the count.
So this is going to be the relative frequency of seeing
a particular value little xi, compared
to everything else I've seen.
OK, but there's a lot of counting and normalizing.
But let's look at this demo to give us a kind of a more fuller
sense of what's going on.
So here is the object tracking example,
I have three variables.
And here I'm going--
I can specify the query which is, which variable am I
interested in calculating the marginal of?
And I'm going to run Gibbs sampling here.
And then at the beginning, I sample a variable x1 given
everything else, so consider all the possible values of x1.
I'm going to look at their potentials or factors,
compute a weight, normalize to get a distribution.
And I'm going to sample a value according
to these probabilities.
So in this case, it's just a coin flip.
I choose xy equals 0.
And then I update my counter.
So I'm recording that I saw x2 equals 1 once.
OK, and then I'm going to move on to the next variable X2,
do the same thing.
Move to the next variable x3, kind of do the same thing.
And I'm going to just cycle for this for a moment.
You can see that the assignment, which is depicted up here,
is changing.
And down here, I can see that the count
of the number of times x2 equals 1 has gone up to 25.
And now look, I actually hit a different value.
I went to a configuration where x2 equals 2 now.
And then I might sample a little bit more,
and they'll come back to 1.
And you can just watch this for a little while.
And you can see over here, that these
are the estimates of the marginal probability of x2
based on the counts.
So these numbers are simply these normalized versions
of the counts.
So I'm going to speed this up a little bit.
So let me do just 1,000 steps at a time.
OK, so now if I did 1,000 steps of Gibbs sampling.
Now I have a lot of counts of x2 equals
1, some counts of x2 equals 2.
And now you can see the probabilities
are kind of converging to something like 0.6 and 0.3.
Let me just hit step a few more times.
And you can see that these probabilities are indeed
converging to 0.61.
Which if you remember from here, is
pretty close to the true marginal probability.
OK, so it seems at first glance, kind of a wild thing, right?
So we're running this algorithm, it's just generating samples
left and right.
It's kind of random.
And yet, if I compute the randomness,
it's very carefully orchestrated.
So that when I sum things up properly,
I actually get the right answer out.
So let me now go to the image denoising examples.
So here the goal is given a noisy image, clean it up.
And in our simplified version, I have
Xi which represents the clean pixel value, which
I don't know.
Now, a subset of the pixels are observed.
So for example, these in green here.
And I'm going to clamp those pixel values to the observed
value.
And then I have a factor that says
neighboring pixels are twice as likely to be the same,
than different.
So let's do Gibbs sampling in this image denoising case.
So what Gibbs sampling would do, is
it's going to sweep across the image,
and sample each variable condition on the way.
So suppose I'm landing on this particular pixel value,
and I'm trying to figure out what should its value be.
So again, I look at the possible values that could be 0 or 1.
And for each value, I'm going to compute a weight.
So remember from ICM, that I actually
don't need to compute the weight of the entire assignment.
And I just only need to look at the factors which
are dependent on this value.
OK, so let's consider v equals 0.
So here if I put 0 here, that means this potential
is going to be happy.
Because [INAUDIBLE] and I'm going to get a 2.
And this one is going to disagree.
This one's going to disagree and this one is going to disagree.
So the weight is 2 times 1 times 1 times 1, which is 2.
So now if I try to put a 1 in this position,
now this potential says 1, while the others say 2.
So now that has a weight of 8.
So now to get the probability of Xi equals
v given everything else, I'm simply
going to sum up and normalize.
So I have 2 and 8 here, the normalization constant is 10.
So I get probabilities 0.2 and 0.8.
Now given this distribution, I'm going
to set this value to 1 with probability of 0.8,
and 0 with probability 0.2.
And then I'm going to keep on going.
So here is a fun little demo of Gibbs
sampling for an image denoising that runs in your browser.
OK, so the idea is that here is an image.
And if you hit Control Enter here.
You'll see that this is the input to the system.
So we have black pixels and red pixels,
these are the observed pixels.
And white pixels are unobserved.
And these are the ones that we want to fill in.
So there's a bunch of settings where I'll
talk to you about in a second.
But if you click here, you can see how--
get a feeling for what Gibbs sampling is doing.
Each frame here, each iteration is a full pass
over all the pixels.
And you can see that it's kind of dancing
around, because it's trying to explore different assignments.
So one thing you can do, is you can
set showMarginals equals true.
And what this does, is that instead of visualizing
the assignment at a particular iteration for each pixel here,
I'm actually visualizing the marginal probability estimate.
So this is in general, going to be a number between 0 and 1
which is represented as a shade between black and red here.
So this, in some sense, is the kind of best guess
at what the reconstruction is.
So there are a number of things you can play with.
So for example, the fraction of missing pixels.
If I reduce this to let's say 0.3.
Then the problem becomes easier.
And you can see that the reconstruction
gets pretty reasonable results.
Another fun thing you can play with
is, well actually, let me bring down the--
bring up the missing fraction to 1.
OK, so that means I don't see any pixel.
So here, this is just going to be--
actually let me do that.
showMarginals equals false, oops.
So here you can see kind of just blind samples from the model,
OK?
And if I bump up the coherence, if I bump it down,
then you'll see kind of a more random pattern.
If I bump it up to 10, then you'll see more coherence.
So remember, this is kind of like the phase transitions
that we saw for the [AUDIO OUT].
OK, so I will let you play with this on your own.
So let me just conclude here.
Actually, one thing before we conclude.
So let me try to go back to Iterated Conditional Modes.
And compare that with Gibbs sampling.
Both of them have the same kind of template.
You're working with complete assignments,
and you're going through each variable
and updating the assignment to that variable one at a time.
But there's a few differences here.
One, the first salient one is that Iterated Conditional Modes
was for solving CSPs, where we're trying to find
the maximum weight assignment.
Gibbs sampling is for Markov networks,
where we're trying to compute marginal probabilities.
So as a consequence for ICM, at each step
we're choosing the value to assign to a variable, which
maximizes weight.
Whereas in Gibbs sampling, where using
the weights to form a distribution
and sampling from that distribution.
In ICM, we noticed that the algorithm does converge
but often to a local optimum.
Which is not the best maximum weight assignment.
For Gibbs sampling, as you can see from these samples,
there's no traditional notions of convergence.
The samples are going to keep on changing and keep on changing.
So, the Iterates are not the ones which are converging.
What is actually going to converge
are the marginal estimates.
And under some technical assumptions,
these estimates are actually going
to converge to the correct answer.
We saw that for object tracking.
It did a pretty good job there.
But there were some technical conditions.
One sufficient condition is that all the weights be positive.
But more generally, what we need is
that for the probability of going from one assignment
to another assignment via Gibbs sampling
has positive probability.
As if you have two disconnected regions.
Then if you start a Gibbs sampling
at one particular point, then you
will never reach the other point.
The one important caveat is Gibbs sampling is wonderful.
But in the worst case, it does take exponential time.
So these are really--
computing marginal probabilities is a really hard problem.
And Gibbs sampling is just a heuristic
with some nice asymptotic energy.
So wrapping up, we looked at computing
the marginal probabilities of a Markov network.
And we saw that Gibbs sampling did this
by sampling one variable at a time.
And it counts visitations to each of the values for a given
variable.
And it's one of these kind of astonishing things,
that Gibbs sampling is so carefully constructed,
that it actually kind of works.
And you can prove lots of interesting theorems about it.
Finally, Gibbs sampling is just the first taste
of a much more broad class of techniques of Markov chain
Monte Carlo which are used to produce
much kind of richer ways of estimating probabilities
in Markov.
All right, that's the end of this module.