Home > Uncategorized > loopy belief propagation

## loopy belief propagation

Yo Hojin,

This morning I ran across an interesting issue which might interest
you. It’s about the loopy belief propagation which I think can fit
with your current research. I’m afraid I will forget it soon so I sent
it to you before I would completely forget it. However, I’m not sure
if my opinion will be useful for you or not, I also Cc. to Dr. Slatton
and Sweung to consider it too.

I found that a lot of researchers play with this loopy configuration,
and sometimes they use junction tree algorithm, or some even apply the
belief propagation to the loopy configuration as if it’s a singly
connected graph!!! (at first I thought that was so bold and crazy, but
they said it works well in practical!!!)

The interesting thing is the latter case, i.e. using the belief prop
as if the graph is singly connected. I just found out that they call
it “approximate inference” (not exact inference), just because the
message passing procedure may not converge to a fixed solution.

In DAG, the belief propagation will converge to a fixed solution after
running the algorithm for a while. But in the loopy graph, it won’t
get to a fixed solution because of loops, which make the messages
circulate like crazy. However, what we can hope is the solution given
for each iteration will get closer to the “true” solution.

In coding research scheme they use loopy propagation to solve their
loopy problems and it works quite well in practical. So you may
consider to use it.

Actually junction tree algorithm can be implemented to your work too,
but it seems like your structure will make the algorithm trivial
because your graph contains a lot of cliques. I’m studying the
junction tree and interested that it may fit your research somehow.
The only concern is that for your graph, the junction tree alg may be
trivial.

Some good things for using the belief prop. in the loopy graphs are
1. local computation –> not expensive
2. if you are lucky, it may converge
3. if not, then you can worry about it ^-^, but a lot of coding
researchers use it, then it may be applicable for you too. I just wish
that.
4. There are some analysis on this and I believe you know the papers
already. I found good slides containing the references at the end:
http://vision.ucsd.edu/~kbranson/research/bp_pres.pdf
I found some papers under the key words “loopy belief propagation” and
some famous analysis were done by Yedidia and Weiss.

Hopefully I understand it right ^_^
Bot