The next step in the analysis that we did before, eliminated the variable i and

again used two of the original factors phi i and phi s.

And it also used how to. And so now, we have a factor lambda 3

whose scope is G S and I because those are the variables in this scope over

here. And the message GI is that we see here,

this edge between GID and GSI corresponds to this tau 2 that was produced by lambda

2 and consumed by lambda 3. The next elimination step didn't use any

of the prid factors produced by other, by other cliques, just used one of the

original cliques, so it just used phi h. And so note that it's currently not

connected to anything, it's just sitting there all by its lonesome.

And the next step now gets to use, gets to use factors that were produced in two

separate computations. So notice that this computation for tau,

for tau, for lambda 5 which is this guy, used both, tau 3 and tau 4 which is why

we have both an edge from cluster 3 and an edge from cluster 4.

The next step that we took marginalized out S, it's multiplied in tau 5 and one

of the original factors JLS. And, so now we have a message, here that

is passed between cluster 5 and cluster 6.

And finally there was the marginalization of L and so we have a JL cluster.

Now if you look at this graph, at this clique tree, you'll notice that it's

bigger than the clique tree that we had for this network to begin with.

And one of the, and the reason for that, is that we actually have three adjacent

cliques where one is a subset of the others.

So JL is a subset of JSL which in turn is a subset of GJSL.

Now if you think about it there's really no point to including three cliques when

one is a subset of the other because you might as well do all of the computation

in the first clique to begin with. There is no value to sort of breaking it

out into separate data structures. And so a typical post-processing step is

to go ahead and remove redundant cliques and just basically collapse them, and

their factors into into the one, the biggest clique subsumes them.

So in this case since we had 5JLS which originally utilized in tau 6, we're now

going to move that and put that instead in, sorry it was used in lambda 6 we're

now going to stick that in clique 5. And so we've seen how we can take a

variable eliminator process a run of variable elimination and use that to

produce what looks like a cleek tree. But is it a clique tree?

SO what properties can we prove about this output from a variable elimination

model? Well first is the fact that it is in fact

a tree. If we want it to be a clique tree it

better be a tree. Why is it a tree?

Because in variable elimination, every intermediate factor tau, once you produce

it, it gets consumed exactly once. Once it gets consumed, remember in the

variable elimination algorithm, it gets taken out of the set of factors and then,

it disappears because it gets multiplied in.

And so if you think about this as a directed tree, it starts out and it

produces factors and each factor feeds up only into a single factor parent and, so

as a directed tree it means that every var-, every cluster has exact, has at

most one parent. And in fact every cluster except the last

one has exactly one parent because eventually everything has to be consumed

because everything is multiplied together.

And so this variable elimination process induces a directed tree where we

subsequently forget about the directionality of the edges.