Hi.
In this module, I'm going to be talking about Markov networks.
So far, we've introduced constraint satisfaction
problems, the first of our variable-based models.
Now we're going to talk about Markov networks,
the second type of variable-based models, which
will connect factor graphs with probability.
And this will be a stepping stone along the way to
[INAUDIBLE].
So recall that variable-based models are all
based on factor graphs, and Markov networks
are no different.
So remember that a factor graph consists of a set of variables,
x1 through xn, and a set of factors, f1
through fn, where each factor takes a subset of the variables
and returns a non negative number.
If you multiply all of these numbers together,
you can evaluate the weight of a particular assignment.
So let's look at an example of object tracking.
So here, remember the goal is over time, record
the noisy sensor reading of an object's position at 0, 2,
and 2.
And the goal is to figure out what the actual trajectory
of this object is.
We modeled this as a factor graph
as follows where we have a number of factors representing
the affinity for x1 to be close to 0 and x2
to be close to 2 and x3 to be close to 2
and also adjacent positions to be close to each other.
So before, we treated this factor graph
as a constraint satisfaction problem
where the goal is to find the maximum weight assignment.
And in this particular example, we
look at all the possible assignments.
Each assignment has a weight.
And you can find that the maximum weight
assignment is 1, 2, 2.
But just returning a single maximum weight assignment
doesn't really give us the full picture.
In particular, it doesn't represent how certain
we are of this assignment.
And what about all the other possibilities?
The goal of Markov networks is to try
to capture this uncertainty over assignments using
the language of probability.
So we've actually done most of the hard work
already by setting up factor graphs.
The only remaining part is to connect factor graphs
with probability.
So formally, a Markov network, or a Markov random field
as it's sometimes called, is a factor graph
which defines a joint distribution
over a set of random variables x1 through xn.
So before, these were just variables,
and now they're random variables because we're
talking about probabilities.
So remember, the factor graph gives us a weight
for each possible assignment x.
And to convert this weight into a probability,
we just need to normalize it.
So what I mean by that is I'm going
to look at the sum over all possible weights,
all possible assignments and their weights.
And I'm going to define z as the sum of all the weights.
And that's going to be called the normalization constant
or sometimes called the partition function.
And then I'm just going to divide by z.
So this is going to produce something that sums to 1,
and I'm going to define that as a joint distribution over big X
equals the [INAUDIBLE] at little x.
OK, so let's do this example here.
We have x1, x2, x3, and a weight of x.
So for this, we have a bunch of eight possible, or not--
or six possible non-zero weight assignments
with particular weights.
We add all these weights up.
That gives us the partition function z, which is 26 here.
And then we divide each of these weights by 26
to produce the joint probability.
And so now this probability distribution
represents the uncertainty in the problem.
And notice that while 122 was the maximum weight assignment,
and it still is, this probability gives us
a more nuanced picture, which is that we're only 31%
sure that that is actually the true trajectory of that object.
So could be useful information.
There's a big difference between 31% and 90%.
But wait, we can do more than that.
So the language of probability can allow us to ask or answer
or other questions besides just probabilities
of all assignments.
For example, if we wanted to know
where was an object at time step 2,
so that is what is the value of random variable x2?
And I don't care about x1 and x3.
So this query is captured by a quantity
called marginal probability.
And the marginal probability of a particular random variable
equaling a particular value v is given by--
so we write this as p of xi equals v.
And this is given by just summing
over all possible full assignments
such that xi equals v. So all assignments
consistent with this condition of the joint distribution,
which we have defined on the previous slide.
And now let's look at this object tracking example again.
So we have our joint probability table
that we computed on the previous slide.
And now let's compute some probabilities
of marginal probability.
So first, let's consider what is the probability of x2
equals 1 here?
But to do that, we look over here
and look at all the rows where x2 equals 1.
So that's the first four here.
And then we just add up their probabilities.
So that's 0.15, 0.15, 0.15, 0.15.
And that gives us 0.6.
And now we can issue another marginal probability query.
What's the probability of x2 equals 2?
And look at all the rows where x2 is 2,
and these are these last two rows.
And we add up these probabilities,
and that gives us our point.
There are some rounding errors here,
why this doesn't add up exactly.
OK, so that allows us to answer marginal probability.
So one thing you might know is that the answer here
is actually different than if you just look at the max weight
assignment and the value of it.
In particular, if you look at the maximum weight assignment,
it says the most likely thing is that x2 is 122.
And you look at x2 of, and it says 2.
But notice that that is not the most likely
under the marginal probability.
The most likely value for x2 under marginal probability
is 1, and it has 62% chance of being a 1 in that case.
So the intuition here is that while this trajectory has
indeed the largest weight, there is actually
a lot of decentralized evidence for x2 equals 1
with these assignments, which have less weight.
So kind of strength in numbers, if you add up
all these weights, they actually outnumber the evidence for x2
equals 2.
So this is kind of an important lesson
that what answer you're going to get really
depends on the type of question you're asking.
And in this case, if you're really
interested in the object at timestep two,
then marginal probability is--
so let's look at a particular example.
So the Ising model is a very canonical example
that dates back to the 1920s from statistical physics.
And the ideal was that this is a model for ferromagnetism.
So the idea is that you have a Markov network which contains
a bunch of different sites.
And each site is going to be denoted xi,
which can take on two values--
minus 1 and plus 1.
So minus 1 represents a down spin
and plus 1 represents an up spin.
And furthermore, all these variables
are going to be related by a factor.
And we're going to call this fij, which
connects site i and site j.
It's going to depend on the spin of i and the spin of xj.
And that's going to be equal to x of beta times xi xj.
OK, so intuition is that we want neighboring sites
to have the same spin.
OK, so by multiplying these together, if both of them
have the same sign, then this is going to be 1.
If they have opposite signs, they're going to be negative 1.
And beta here is a scaling that says
how strong is the affinity.
If beta is 0, that means this is just x of 0, which is 1.
So that means there's no connection between.
And as beta increases, then the affinity becomes stronger.
The difference between them agreeing and not agreeing
becomes i tended.
So one thing Ising models are useful for is
to study phase transitions in [INAUDIBLE] systems.
So here is an example of what happens when a beta increases.
So if beta is close to 0, then you're
basically going to get unstructured systems where
each side is just behaving independently.
In fact, if beta is 0, then all assignments are equally likely.
And as beta increases, you'll see
that more and more coherence happens
where neighboring sites really like to be close to each other.
But of course, there's going to be some kind of sharp ridges
where two neighbors have to disagree.
So how we're going to sample from this model
is going to be a topic for another module.
So here is another canonical application of Markov networks
from computer vision.
So this used to be very popular before deep learning.
So the idea is that you take a noisy image,
and you want to denoise it into a clean image.
So we're going to present a very stylized, simple example
of this.
So here is our 3 by 5 image.
So each site is a pixel, and we assume that we only--
so xi is either 0 or 1, which is a pixel value, which
is unknown for modeling the clean image.
And we assume that only a subset of the pixels are observed.
Or maybe we observe this one, this one, this one, this one,
this one.
And the goal is to fill in the rest of the pixels.
So we can capture this observation by an observation
potential of oi xi, which is 1 if xi agrees with
the observation and 0 if it doesn't.
So this is a hard constraint that
says where I observed a value, xi must take on that value.
So this one has to be 0, this one has to be 1, and so on.
And finally, we have transition factors
that say neighboring pixels are more likely to be
the same than different.
So again, the same intuition is that Ising model,
and we're going to denote this as tij.
And this equals is 2 if two neighboring pixels agree
and is going to be 1 If they--
so let me summarize.
Markov networks, you can think about it
as simply as taking factor graphs
and marrying them with probability.
So again, factor graphs already have done a lot of the work.
They allow already you to specify non-negative weight
for every assignment.
And all we have to do is normalize
that to get a probability distribution.
And once we have the probability distribution,
we can answer all sorts of queries.
Now we're computing marginal probabilities,
which allows us to pinpoint individual variables
and ask questions about them.
So it is useful comparing Markov networks with CSP.
So CSPs, we talked about variables who are known,
unknown.
And Markov networks, we call them random variables.
They behave like variables, but they're random variables
because we're endowing them with a probabilistic interpretation.
And CSPs, we talked about weights.
Markov networks, we talk about probabilities, which
are the normalized weights.
And the main difference is that in CSPs we
were trying to find the maximum weight assignment.
And in Markov networks, we're looking
at the distribution over assignments holistically
and answering questions about marginal probabilities, which
gives us a more nuanced idea of the set of possible components.
OK, that's it for this module.