So now that we've reduced problem to one where we are taking the max over

summation, we're going to now go back to our simple example of a chain.

And we're going to think about how we can do max sum variable elimination in chain.

And this is going to look. It almost identical to the max, to the

sum product algorithm that we had before, so let's, understand what we're trying to

do here. So we're trying, assuming that what we're

trying to do now is forget the argmax. Let's assume that we just want to find

the max of this, of this expression, theta of A, B,

B, D, and E. And so just like in the sum product case

we can break up the maxes in to a max over A and then a max over B and a max

over C and a max over D. And what we might not be quite as used to

doing this kind of operation that I'm just, that I'm about to show it's equally

valid to point out that because none of these guys say the two, say the three or

say the four depend on A, we can, add them up, the max over, this guy over

theta one and AB, after computing the max.

And so that's going to give me, a, factor here which which looks like max over A,

theta 1 of AB, and I'm going to call that lambda 1 of B, because notice that this

is not a constant, it's a function that depends on B, for different values of B,

your going to have different, different A's of maximize and different values of

the max expression. And so, this lambda 1 of B is simply the

max over A of theta 1 AB. And that process has effectively now

eliminated A, from this expression, and given me A maximization problem over one

fewer variable. only B, C, D, and E.

Just like in the context of sum product algorithms we can view all of these

operations as operations over factors rather than just thinking about them in

terms of expression. So whereas before we defined things like

factor product and factor marginalization, we can now define

analogous operations that correspond to factor summation and factor maximization.

So factor summation, a very obvious operation does exactly what we did here,

so who want in, in, in case of factor product, if we want to define.

And the row for a1b1c1 we're going to add up.

The entry three from A1B1 and the entry four from B1C1 and that's going to give

me 7. And I can similarly define all of the

other entries in the factor summation which we're showing here on the right.

Factor maximization, is the same way that we could sum marginalize a factor.

This is something that, max marginalizes. It's called the max marginalization and

what it does is it looks, if I, so I'm trying to get rid of B I have these two

rows here, say, for example, A1, B1, C1 and A1 B2 C1 that only differ from B,

And my new entry here A1 C1 is going to be the max of these two entries over here

which, in this case, is going to be seven.

And similarly for say, A1 C2, I'm going to end up with a max of 4.5 and

two, which is 4.5. So this is another form of

marginalization where I remove the variable b but using an operation other

than summation. So, now that we've defined these two

operations, we can go back and define the max sum variable elimination in chains as

a set of factor operations where I eliminate A, then B and so on and so

forth. So, for example, having eliminated A as

in the previous step I can now do the exact same operation by noticing that

factors that depend on B are theta 2B and 1B so these other two.

I can move outside of the maximization. And that's going to give me a max over b

of a factor that is the sum of the two factors, feta 2bc.

And lambda one of b that I got from the previous elimination step.

And that's going to give me a new factor lambda two of c and the process continues

in exactly the same way as variable elimination did for the case of some

product. And that's basically the algorithm.

So now let's think about what we get at the end of this execution for the final

factor. What is lambda four, having gone through

lambda two and lambda three, now we get lambda four of e.

What is lambda four for a given value little e?