strong potentials, and conflicting directions is probably the single worst
example for the single worst scenario for belief propagation.
This is the case where it's going to do the worst in terms of both convergence
and in terms of the accuracy of the results that are obtained.
Now in this example, ultimately you actually do get convergence.
You can see it, takes about 300 iterations but ultimately you get
convergence, 300 is a lot for graph this size.
Here is one that up to 500 you didn't get convergence at all, maybe if you ran it
for 10,000 it might converge, but it's hard to say.
And, so how do we improve the convergence as well as the accuracy property of the
network? So first let's look at what not to do.
Here is the most important thing not to do.
Which is a variance of belief propagation called synchronous belief propagation.
In synchronous belief propagation, which was actually one of the most commonly
used variants at the very beginning of of the use of, of the BP algorithm.
All messages are updated in parallel. So all of the processors wake up.
So, all of the cle, all the clusters wake up.
They look at all of their incoming messages.
And they compute all of the outgoing messages, all at once.
Now, this is a great algorithm, from the perspective of simplicity of
implementation, and also from the ability to parallelize, because you could assign
a processor to each of the cluster, and they're all working in parallel and
there's no dependencies between them. Unfortunately, synchronous belief
propagation is actually not a very good algorithm.
And so what you see here is the number of messages that are have converged as a
function of the amount of time spent. This is an icing grid with certain
parameters, it doesn't matter. And you can see that you know, there is a
certain improvement over time and then it kind of asymptotes, at the certain number
of messages that have converged. By contrast, let's compare that behavior
to asynchronous belief propagation, where messages are updated one at a time.
So, this one and that one. Now notice that this algorithm is poorly
specified because I didn't tell you what order we should do the updates in and
we'll come back to that in a minute. But by, even by the simple virtue of
passing messages in an asynchronous way, the behavior improves both in terms of
how quickly we get messages to converge, and in terms of the number of messages
that are converged. Now, this is not a particularly good
message passing order. Here's a much better message passing
order. It takes a little bit longer to get
certain messages to converge. It's trying to make sure that everything
is converging. But notice that eventually and in, in not
that long of a time it actually converges to 100% convergence rate,
okay? So, here's some important observation
regarding this. First of all, convergence is a local
property and belief propagation. Some messages converge quite quickly,
others might never converge. And when you have some messages that
after you run the algorithm for certain amount of time, don't converge, one often
simply just stop the algorithm and says you know, this is what we have and we're
done. Synchronous belief propagation has
considerably worse convergence properties than asynchronous belief propagation.
Which is why pretty much, at this point very few people actually ever use
synchronous belief propagation. And, if we're using asynchronous belief
propagation, the order in which messages are passed makes a difference both to the
rate of convergence, but even more surprisingly perhaps, to the actual
extent to which messages are converged ever converged.
And so how do we pick the message passing order?
There's two there's several different scheduling algorithms.
I'm going to present two of the more popular ones.
The first called, tree reparametrization or TRP, for short.
And what it does is, it picks a tree, and then passes messages in that tree in the
same way that you would do in a creek tree algorithm.
To sort of calibrate that tree keeping all other messages fixed.
So for example, we might start by calibrating the red tree,
which means I pass messages this way and then back in the other direction,