An alternative class of algorithms to the variable elimination algorithms is the

class of Message Passing algorithms. And, as we'll see, this is, a class that

is in some ways closely related to variable elimination.

It also offers us additional flexibility in how we do a summation and, factor

product steps so as to potentially come up with a lower complexity than would be

required by even the minimal elimination ordering.

So lets consider simple mark of network of the following type and lets assume

that I don't want to go to the cost of eliminating variables although in this

network its not going to be to expensive. And instead what were going to do is

we're going to construct what we call a cluster graph.

A cluster graph is something where is what, is a data structure in which we're

going to take little bits of knowledge from this graphical model and we're going

to place them in things called clusters. So here, we have four clusters in this

example. Cluster one is a cluster who's

jurisdiction of influence is the, the pair of variables AB.

Cluster two has jurisdiction over B and C.

Three is over C and D. And four is over A and B.

And these clusters are going to sit there, and they're going to talk to each

other, and they're going to try and convince each other that what they think

about a variable that they both consider to be under their jurisdiction is, is

correct. So for example cluster one is going to

talk to cluster two about the variable B, and it's going to tell cluster two what

it thinks about B, so that cluster two might become more informed about the

distribution over B. And so what we're going to do is

initially each cluster is going to have it's own little piece of information so

phi one is going to go here, phi two is going to go there, phi three goes there

and phi four goes there. And now the variables are going to

communicate by via these things called messages.

So we're going to call, we're going to slightly rename things.

We're going to call the variable, the initial set of beliefs, if you will or

evidence that a factor, that a cluster has over the variables in this

jurisdiction. We're going to call those psis.

In the example, we just had psis where just the psi in the original model, but

as we'll see sometimes it can becomes a little bit more complicated than that.

So now factor, the cluster one has the factor Phi one.

And if cluster two has psi two and so on, and now let's imagine that Si one wants

to send a message, oh sorry, this psi two, the cluster two wants to send a

message to cluster one. So it has to figure out, what it believes

and our, our priority we're going to assume that it's just going to, we're

going to start out by initialising with a totally uninformed message.

So, because initially they haven't even started talking to each other.

So all messages are initialized to be one.

But now cluster two can come back and say, okay I'm going to ping the

information, uninformative as it was that I got from cluster two, and notice that I

call this message delta two one. Delta two being the from and one being the two

and so if taken delta two, one and now factor one eh cluster one is going to say

well I'm going to take that I'm going to multiply it with my current thoughts

about the variables AB and that's going to give me a more informed factor.

And now, I'm going to communicate that information to factor four, to cluster

four. But cluster four doesn't care about a,

sorry cluster four doesn't care about b, and so what I'm going to communicate to

cluster four which is this message delta one four from one two four is the sum

over B, which is the variable that four doesn't want to hear about.

The incoming message. Times my initial beliefs, of my initial

factors. Now, this general process is what keeps

the message-passing algorithm going. So each variable.

Each cluster is going to send messages to its adjacent clusters that reflect this

exact same process. So for example, just take a different

different example here is delta three four.

So this is the message that goes from three to four.

And that message takes into consideration the evidence that two sent to three,

which is this guy over here, times whatever three thought about c d to begin

with. notice, and this is important, that the

message that three sends to four doesn't take into consideration the information

that it got from four. So there isn't in this expression over

here the contribution of delta four, three.

Because you want to have, you want to avoid this case of I repeat back to you a

rumor that you just told me and we all become more convinced about the truth of

this rumor, because oh, you, I, I thought about this first, but now you're

reinforcing me by telling it to me again and the beliefs are just going to go up

and up and up. And so what happens here is that we

deliberately only, restrict attention to evidence that.

Comes in from other sources. So three only uses evidence from two when

reporting to four, and it only uses conversely evidence from four.

One reporting to two. And so now this is, 'em, this defines a

set, a communication protocol by which one factor or one cluster rather in the

graph can communicate information, to its neighbors.

What do we do with this so how do we generalize this message

passing process? Let's construct a more general version of

this. so, this uses a data structure called a

cluster graph. A cluster graph is an un-directed graph,

whose modes are not variables anymore. Not as, not in, this is not a you know,

graphical model of the type that we've seen.

The modes in this un-directed graph are clusters that correspond to subsets, of

variables. Just like we had before.