0:00

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.

4:06

It's an edge that I have to introduce. Because of the elimination ordering.

So one way to think about this is is using the following example.

Imagine that every variable that's eliminated is going off on a trip around

the world. And when it's doing that it's throwing a

big goodbye bash, and inviting all of its friends to come an join it.

And when it does that all of its friends get to meet each other and say, oh.

You, you guys are nice. I'm going to be your friends to.

And so all, of the, friends of the variable that's eliminated become

friends, as a consequence of the elimination step.

Okay? So let me write that down, all variables.

Connected. Two.

In this case I, become connected, after it's eliminated.

So become connected directly. And that's a general, consequence of the

elimination step process. It's just that the previous ones didn't

happen to introduce filedges. 'Kay?

Let's continue. so now we're going to eliminate H.

H also doesn't introduce any fill edges and so we're going to end up with that.

And basically the remaining steps are pretty mundane.

We're going to eliminate G, L and S and we're going to end up with the following

graph. So this particular variable elimination

process only introduced one fill edge which is a fairy conservative thing.

It shows that we, that we selected a pretty good elimination ordering in this

case. So we can now take and put all of these

edges that we that we ended up using, together in a single graph.

And that graph is called, the induced graph.

And the induced graph which is denoted I for induced.

Phi comma alpha over a set of factors phi.

And induced by a particular ordering, alpha, because you remember that we were

getting different complexities. And we're going to have different fill

edges. depending on the order in which variable

are eliminated. So this variable, this induced graph has

the following properties. It's an undirected graph, where we

connect every pair of variables xi and xj, if they ever appeared in the same

factor, when we ran variable elimination using alpha as the ordering.

And so, in this case, all of the original, all of the black edges were

there to begin with, and we ended up introducing just one of those additional,

new, or fill edges. So now, let's, there's some interesting

properties of the induced graph that are worth noting.

First of all, there's some, there's properties that relate factors produced

during variable elimination. And cliques in the induced graph, so

first of all let's define what a clique is.

A clique is a maximal. Fully connected sub-graph.

7:23

So lets parse that to. So for example,

DIG here, is a fully connected subgraph, because all of its three nodes are

connected to each other. And it's maximal, because I can't add any

other variable to this and still have that property whole.

So if I try and add S, for example, then S is not connected to D.

If I try and add C, C is not connected to I or G.

So I can't add any other variable to this particular clique.

So it's a clique. here's a clique that's not maximal.

So, here is, so it's not a clique, so GLA is a connect, fully connected subgraph.

But it's not maximal, because I can add S, and still have that hold.

So here is another clique in this graph. So we have GID being one clique,

GSL and J being another clique. we're going to have a third one, which is

G, S, and I. Another one which is CD.

And let's see if I have enough colors to do this.

And a final one, which is g, h and j. And, if we now look at the factors that

we produced in the in the course of variable elimination, we see that there

is an exact correspondence between the factors and those cliques.

So here, for example, the yellow one is CD,

which is this one over here. this one over here, which is GID, is the

red one. This one.

9:19

So that's the red one. This one has sig, so that's the green

one, this one. This one is a to d j, which is the brown

one. Tau 5 induces the big factor, the one

that involves four variables, and that's the blue factor over G, S, L and J.

And this one doesn't actually introduce any new kleeks which is why it doesn't

have any kleeks, associated with it. So every factor produced during variable

elimination is a kleek in the induced graph.

Hm. We can equally well check, and we saw

that in the previous slide already, that every maximal clique in the induced graph

is a factor that's produced during variable elimination.

So we've demonstrated this to ourselves by inspection.

But let's actually do a proof of this. So let's consider a maximal clique in

this induced graph. So let's consider, for example, G, S, L,

and J. That's a maximal clique, and now it's

considered the run of variable elimination and one of those variables

has to be, oops. One of those variables has to be the one

to be eliminated first. So, some variable in this clique.

14:04

The minimal induced width of the graph, is the minimum over all possible

elimination orderings, alpha, of the width of the induced graph.

So this is the best achievable complexity that one can aspire to with any

elimination ordering. You can think of the minimal induced

width of the graph as a lower bound on the best performance of variable

elimination for any model that factorizes over the graph k.

In summary we've seen that the variable elimination algorithm can be viewed quite

intuitively as taking a set of steps, each which transforms the graph.

Specifically a variable elimination step for a variable X takes all of X's

neighbors that may or may not have been connected before and connects them to

each other. The result of all this is something

called the induced graph and we've seen that the induced graph is possibly quite

connected as a result of this variable elimination process and that the cliques

in this induced graph, that is the maximally connected subsets, maximally

fully connected subsets, correspond directly to the complexity of the

variable elimination algorithm and as we'll see can therefor help us analyze

its computational properties.