Hi, in this module, I'm going to talk about the general strategy
for performing probabilistic inference in Bayesian networks.
So recall that a Bayesian network consists
of a set of random variables, for example cold, allergies,
cough, and itchy eyes.
And then the Bayesian network defines
a directed acyclic graph over these random variables
that capture the qualitative dependencies
between the variables.
For example, cough is caused by cold or allergies.
Itchy eyes is caused by allergies alone.
Quantitatively, the Bayesian network
specifies a set of local conditional distributions
of each variable xi given the parents of i.
And so in this example, I would have probability
of c times probability of a times
probability of h given c and a times probability of i given a.
And then when I multiply all of these probabilities together,
then I get by definition the joint probability distribution
over all the rest.
In this case, I have a joint distribution over C,
A, H, and I. So you can think about the Bayesian network
as defining this joint distribution, which
is a probabilistic database where you can answer questions
about this data.
For example, what is the probability of C
given H equals 1 and I equals 1?
Generally, you have a Bayesian network.
Some of the variables you observe as evidence,
for example H and I in this case.
And another set of variables you are
interested in which are the query variables,
so that way Q would be C here.
And what we want to produce is the probability
of the query variables conditioned on evidence.
Normally this is a probability of Q equals q for each
of the values of little q.
So the overarching strategy that we're
going to take for performing inference in Bayesian networks
is to convert them into Markov networks, which
we discussed inference for.
So recall-- we're going to walk through this example.
So recall that the joint distribution over the variables
here is equal to simply the product
of the local conditional distributions by definition
of the Bayesian network, OK?
But these local conditional distributions a
are non-negative quantity.
So they can be interpreted as factors in the factor graph.
So let's draw the factor graph.
So here we have the same set of variables.
For every variable, we have a factor corresponding
to this local conditional distribution.
We have probability of c, probability of a, probability
of h given c and a, which connects C, A, and H
and then probability of i given A.
So in the factor graph representation,
these are simply functions.
This is a function that depends on c and h.
And the factor graph doesn't really
care that it's a local distribution.
So now remember in a Markov network, we take a factor graph
and we multiply all the factors together.
And we divide by the normalization
constant to get this product to sum to 1.
But notice that in this case that the normalization constant
is exactly 1.
Because we had this equality from the definition
of the Bayesian network.
So Z has to be 1 in this case.
So the Bayesian network is just a Markov network
with the normalization constant 1.
And that means we can take any Bayesian network
and reinterpret it as a Markov network
and answer all sorts of marginal queries.
For example, you can ask for the probability of A.
We can ask for the probability of H, and so on.
But I'll just remind you that a single factor connects
all the parents.
So notice that there are two edges, C to H, A to H here.
But in the factor graph representation,
you should connect the parents and the child into one.
So there's only one thing missing
from this picture, which is that often in Bayesian networks
you want to condition on evidence.
So let's condition on H and I. To do this,
we're going to define a Markov network
over the non-conditioned variables.
So in this case, that's going to be C equals c, A equals a,
condition on H equals 1 and I equals 1.
And what I'm going to do is we're just
going to substitute the values of the evidence
into the factors themselves.
So here is a factor graph.
I have only C and A left.
And p of c and p of a is the same.
And now we have this factor that depends on C and A,
but h is equal to 1.
So I don't need to represent h as a variable.
And here the same.
I equals 1.
So I don't need to represent i as a variable.
But now I take these four factors.
And I multiply them all together.
And I get that as this factor graph.
And now I need to normalize by 1 over Z. It's a different Z now.
In this case, Z is not 1, because I'm
conditioning on evidence.
And in particular, Z is going to be the probability
of the evidence.
And you can see this, because this is a joint--
this is a conditional distribution.
And conditional distribution is equal to the joint distribution
divided by the marginal of the thing
that you're conditioning on.
So Z has to be equal to the marginal of the evidence.
But, nonetheless, this is a Markov network.
And now, again, we can run any inference algorithm
we'd like over this Markov network,
for example, Gibbs sampling.
Well, let me actually do that in this little form here.
So here is the medical diagnosis.
We define variables C, A, H, and I.
We're going to condition on H equals 1.
I equals 1.
And we're interested in the marginal probability of C.
And we're going to run Gibbs sampling.
So Gibbs sampling, remember, is going
to take an arbitrary factor graph or Markov network.
And it's going to go through an assignment
and reassign each variable one at a time.
And it's going to accumulate these counts.
But let me speed this up a little bit
and say I do 1,000 steps at a time.
And now you can see that these counts
should converge to the right.
It's about 0.13.
Should converge to the right, of probability of C
conditioned on H and I.
So then we're kind of done.
We have a Bayesian network.
We condition on evidence.
We formed this reduced factor graph or Markov network.
And then we just run Gibbs sampling.
So in some sense, we are done.
But I want to push this a little bit further and show
how we can leverage the structure of Bayesian networks
to optimize things.
So let's take another example where we're now conditioning
on H. OK, so we're conditioning on H.
So let's go through the motions here.
We're going to define a Markov network on the variables
that we didn't condition on, conditioned on H equals 1.
And that's going to be equal to just the product of all
the local conditional distributions
where we've substituted now H equals 1.
And now, the normalization constant
is the probability of the evidence.
And now, I can ask the question, what
is the probability of C equals 1 given H equals 1?
This is something that I can just go and compute
using Gibbs sampling.
But the question is, can we reduce the Markov network
before running inference?
Because if we can get the Markov network to be
a little bit smaller, then hopefully inference
can be a bit faster.
So the answer is yes.
And we're going to show this by doing a little bit of algebra
here.
So here is this Bayesian network again where
I've conditioned on H. So now, let
me compute the marginal distribution
where I marginalize out I. So here, I don't have I anymore.
But I can express this in terms of this probability of C, A,
and I given H where I simply sum out
all possible values of [AUDIO OUT] so this is just
the definition of marginal probability inference.
So now, using the definition of the Bayesian network,
I can rewrite the joint distribution
in terms of local conditional distribution.
OK, so and now, I make an observation,
which is that summing over i.
But none of this actually depends on I
except for this last factor.
So what I can do is push all of this stuff
out or equivalently push the summation inside.
So now, it's wrapped tightly around this p of i given a.
Now, what is this?
By definition of local conditional distributions,
this is exactly 1, so it gets dropped.
So now, I have this nicer form.
But not only is it smaller, let's
try to understand what it is.
This is the probability of c, probability of a,
probability of h equals 1 given c and a.
So it's as if this variable I didn't exist at all.
So this is a general idea behind Bayesian networks, which
is that you can throw away any unobserved leaves
before running inference.
So this is very powerful because it connects marginalization
over variables, which is generally
an algebraic operation.
It involves a lot of hard work with removal,
which is a graph operation, which
is more intuitive and trivial in this case.
So in general, marginalization is hard.
But when they are unobserved leaves of a Bayesian network,
it is trivial or just remove it.
So here is another type of structure we can exploit,
which is actually not specific to Bayesian networks.
It shows up more generally in Markov networks.
Well, let's take another example here.
We're going to condition on I at this time.
So here, we're going to define this Markov network, where
let's just write down this query that we're interested in.
We're interested in C equals c given I equals 1 here.
And expanding it out based on the definition
of marginal probability, I can put
in probability of C, A, and H where I sum over
all possible values of A and H. So I'm
marginalizing out A and H here.
And by definition of the Bayesian network,
I can replace this with the local conditional
distributions.
And now, using the same trick as before,
I notice that H is an unobserved leaf, so I can actually
marginalize out H. And this factor disappears graphically.
This H disappears.
And now, I am left with this Bayesian network,
where notice that the only thing that depends on c
is this p of c.
We're going to try to pull it out and rewrite it as follows.
And now, I have p of c times some mess.
And the nice thing in this case is
that this mess is just the constant
because it doesn't depend on c.
And moreover, because p of c is a distribution
and this left-hand side is a distribution,
this constant is actually 1.
So because C graphically, C and this AI sub-graph,
is actually disconnected, which means that I can simply
remove this part.
So generally, I can throw away any disconnected components
before running inference, OK?
So in general, let's summarize here.
We've tackled the problem of how to perform
probabilistic inference in Bayesian networks
by reducing the problem to inference in a Markov network.
So to prepare the Markov network,
we're going to first condition on the evidence.
So this is tantamount to substituting
the values of the evidence into the factors.
Then we throw away any unobserved leaves,
in this case, H. We throw away any disconnected components.
But these two are just optimizations,
which are totally optional, but it will often
save you some work.
Now, we define a Markov network over the remaining factors.
Now, we just have a factor graph,
where we can now run your favorite inference algorithm.
So in the case, it's very simple.
As it is the case here, you can just do it manually.
Or if what's remaining is more complicated,
then you can do something like Gibbs sampling.
And that's the end.