Very important insights about variable elimination and how to best pick the

elimination ordering is provided by thinking about the operations of variable

elimination execute as operations on a graph.

So let's see what that does. So let's consider the initial graph in

our example. And let's, first view this graph in terms

of the factors that it involves. so if this is the set of factors that we

have in in our analysis, viewed as undirected, view, viewed as, simply as

factors. so what is the structure of the graph

that corresponds to the set of factors. Well, first, we're going to make all of

the edges undirected, but that's not enough, because we see, for example, that

we have a factor here, which is a factor over G, I, and D, and so, what we need to

do is we need to add an edge between I and D to represent the fact that they're

together in the factor. Other examples in the other cases where

we need to correspond to the other V structures that we have in the scruff.

So here for example we have a V structure involving J so we're going to need to

connect J's two parents and similarly for H's two parents.

This step, by the way, is called, not by me, a moralization.

Because of the dubious moral value of marrying the parents of a child, no

matter how many of them there are. and so I did not invent that name.

So having moralized the graph, we now have this version of it.

And this is what we previously defined to be the induced Markov network for the

current set of factors. So now let's think about a variable

elimination step and what it does to this graph.

So let's begin by eliminating c. And if you remember that involved this

operation. And so first eliminating c is hey

changing the set of factors. It removes these two factors over here

from the set and introduces a new factor tau 1 of d.

So the induced graph is now going to look like the following.

We've taken C out, and this, the remainder is the induced

graph over the set of tau. Okay?

Now, we're going to continue. We're going to eliminate d.

So, once again, we're going to take the two factors that we've now introduced.

sorry. These two factors that in-, are involved

here, which is tau 1 of d, and phi g of g, I, and d,

going to to multiply them, and going to eliminate d.

And so, the resulting, and then the resulting graph is now going

to look like this. Were again, the the nose, with the, with

the dashes edges are not really there. They're just there to remind us that they

were there before. Continuing on, we're going to eliminate

I. And that involves multiplying in, this

term, this term, and this term. And now, something interesting is going

to happen. The factor that we introduced, which is

tau 3 of S and G is a factor that doesn't have an edge in the current graph.

So, if we're interested in having this graph represent our current set of

factors, we're going to need to introduce this edge between G and S.

Because that edge and, is necessary because S and G are together in the same

factor. So that edge is called a fill edge.