We've already said that there's many different algorithms for inferencing

graphical models, but the simplest and most fundamental is an algorithm

typically known as variable elimination. Let's consider the variable elimination

algorithm in the context of a simple example of a graphical model structured

as a chain. Here we have we're interested maybe in

computing the distribution over variable E.

So we're interested in P(E). And as we've already said that

probability is proportional to the un-normalized measure p tilda over A B C

D and E summing up all of the variables except for E.

So now let's see how we can do this more efficiently than simply constructing the

joint distribution and then summing things out.

So the first thing we do is we write up this unnormalized measure as a product of

the constituent factors. And for the moment we're going to assume

that we only have pairwise factors for the edges in, this graph.

So we have a factor for AB, a factor for BC, CD, and D.

So those are the factors phi one up to phi four.

Now, what is the first observation that we have when we see the summation over A

B C and D of a product of factors? Well, we've already done this exercise

previously when we were doing some proofs related to graphical models.

That if we have a factor that doesn't mention a particular variable in its

scope we can move it out of the scope for the summation.

So specifically, phi two of BC can be moved out of the summation over A, as can

phi three of CD and phi four of DE, which leaves us only with the summation over A

of phi one AB. So that gives us the expression over

here. Now this is.

Now this is a summation over a para-wise factor.

And the result of this is a factor over a single variable B. which we're going to

call tau one of B. And so we end up with an expression that

looks like this. So now let's continue this expression the

developing this expression further. noting that we now have an expression

that doesn't involve A, only the variables B, C, D and E, so that

effectively, we have eliminated E from our graph, A, we've eliminated A from our

graphical model. So let's go back to this expression, we

now have this, this product of four factors and once again we can look at

what factors involve the variable B and which ones don't.

And the ones that don't can be moved out of the summation, just as before, giving

us this where now we have an expression which is a product of these two factors.

Sum that over B. And this is going to give us an

expression. How to, whose scope is C.

And so we now have an expression that does not involve the variable B.

And so now we've eliminated B from this graphical model.

And we can similarly continue to eliminate C and D.

So that, ultimately, we will end up with an expression that involves only the

variable E. And that expression is going to be

proportional to the probability of the, to the marginal probability of E.

Now let's do this algorithm in the context of a somewhat more complicated

example which is our enhanced student network that we've played around with

before. So let's imagine that our goal is to

compute the probability of a variable J as one, and in order to do that we're

going to have to eliminate some of the joint distribution all of the other

variables except for J. So this our, our expression.

And note that we have this product of factors.

I've taken, already, in this expression, the factors that were, the CPDs, and

turned them into factors so that we can have a consistent notation.

And now we need to eliminate every one of the variables except for J.

So we're going to start with eliminating the variable C first.

And and so once again we are going to take the summation over C and, we are

going to push it in, leaving in the summation only the factors that involve

C. And those are phi D and phi C.

Multiplying them together and eliminating C is going to give us a factor which

we're going to call tau one, and whose scope is D.