So let's understand how this complexity manifests in the context of a real

example. So this is the run of variable

elimination that we did, that we did before just written out all in one in one

slide. And so now let's see what the complexity

of this is. When we see that we have produced several

factors here and let's write down how many variables are in the scope of each

of these factors, this one has two. This one has three, G, I, and V.

This one has, three, S, G, and I. This one has three, H, G, and J.

This one has four, L, G, S, and J. And this one has three, J, L, and S.

And so the size of the largest factor is, is this one that has four variables in

it. And that is what's going to, in general,

drive the complexity of the algorithm. not an example as simple as this, but in

more realistic examples. So, now let's understand how elimination

ordering plays into this. We previously said that variables can be

eliminated in any order, so long as we're careful about multiplying things in at

the appropriate time. But now let's see how elimination order

might affect the complexity. So assume that in this example I'm going

to make a not very judicious decision and I'm going to start by eliminating G.

So which factors do I need to multiply in, in order to eliminate G?

Well, psi L of L and G. Psi G of GI and D, and, phi H of H, G,

and J. And so if I multiply all these together,

it turn out that I now end up with a variant with a factor whose scope is,

let's see, L. D, I, D, H, and J, so a total of six

variables, whereas before the largest factor that we ever generated had four

variables. So that's, maybe you might say, six

versus four, not a big deal, I mean it's, you know, how much does, how much

difference does it make? So let's convince ourselves that in other

graphs it might make a bigger difference. So here is a graph that has, it's a

simple, pairwise Markov network with A and C and then a bunch of variables in

the middle, B1 up to BK. And then imagine that I start by

eliminating A first. Well, what are the factors that involve

A? Well, we have a factor, ab1, ab2, ab3, up

to abk. And the total scope of the factors are,

Is, of this factor that we generate is going to a, b1, up to bk.

So it's going to be exponential in k. So the size of the factor Is exponential.

Nk. Maybe this is inevitable.

Well, no. So let's imagine that, instead, we're

going to eliminate the bi's first. So, let's think, for example, that we're

going to start by eliminating b1. Well, b1 is in a factor with a, and in a

factor with c. So we're going to end up with a product

of, say, phi one, phi a1 of a, b1 * phi c1 of c, b1.

And that's going to give me a factor whose scope.

Is a. B1 and C.

And the result of summing out B1 is going to be a factor, tau one of A and C.

We're going to get the exact same behavior when we now eliminate B2.

And that's going to give me a factor, tau two of A and C.

And so on and so forth. Until, at the very end, I'm going to have

a bunch of factors. Tau I of A and C that are all multiplied

together. And I've done this without ever

generating a factor whose size is bigger than three.