So now, we're going to look more closely into the belief propagation algorithm and

understands some of the important properties that it has.

So here's our example, cluster graph with the four clusters over the loop.

And now, let's remind ourselves that the cluster beliefs are defined to be the

product of the clust, of the factors assigned to the to the clusters of psi

one up to psi four times the product of the messages that were incoming into the

clusters. So for example, the beliefs over cluster

one is psi one of a b times the message coming in from cluster four, whose scope

is a, and the message coming in from cluster two, whose scope is b.

Now a cluster graph is said to be calibrated.

If the clusters agree with each other, so specifically if in terms of their beliefs

beta I, if we were to ask cluster one what it thinks about say variable B, and

we were to ask cluster two what it thinks about the variable B, they would agree

with each other. Formally, this says that if we

marginalize out the belief that say cluster I and, marginalize out the

beliefs in cluster J and we ask them what they agree about their joint subset.

S I J, they would agree with each other in terms of the marginal beliefs.

Now, an important property of cluster graph belief propagation is that

convergence of the belief propagation algorithm implies calibration.

So, to understand why that's the case, let's go through a simple derivation.

So the convergence of belief propagation occurs when the message at the next time

step equals the message at the previous time step.

So now, let's see what the implications of that are.

So if this is the, message it's the next time step.

It's computed. As the product of the.

psi Is, which are the factors assigned to the cluster I times all of the messages

other, except for.

cluster J. And those are all multiplied together,

and marginalized out over the subset. So now let's remind ourselves of what the

beliefs would be at this point in the process if we were to compute them.

And that's derived from this expression over here.

So this is the same psi I that we had over here.

And this is the product of all messages. So if this is, if, if here we have the

product of psi I, and all messages except one and here we have psi I and all

messages we can equally well, rewrite it, in this form over here where we multiply

in all the messages, and the divide out, the one that wasn't included, delta JI.

So now, because of convergence we have the this is equal to this is equal to

delta IJ because of this equality over here.

And so if we rewrite that, we can see that we have that delta IJ times delta JI

is equal to this summation over here. Because we can multiply delta JI on the

right-hand side by delta IJ on the left-hand side.

So we have shown that delta JI times Delta IJ is,

is effectively the marginal over the beliefs at that point in the process.

But we can equally well, using the identical argument, show that Delta JI

times Delta IJ is also the marginal over the beliefs for cluster J.

So if is the beliefs for cluster I, this is the beliefs for cluster j, and so and

that we've shown that in both cases. The marginals are equal to the same

expression, which is the product of the messages on both sides of the link.

And so, because both expressions are equal to the same thing, they must be

equal to each other. And this is exactly the calibration

property that we were trying to prove. So we've shown the convergence of the

belief propagation algorithm implies calibration.

This expression, which corresponds to the, subset beliefs.