|
Referring capter 8 of PRML, I implemented loopy belief propagation(max-sum) for factor graph. However, probabilities of all variable nodes creating loops on loopy factor graph are always 0, as follows.
I doubt whether I misunderstand the algorithm. Please help me. |
|
Yes, messages will tend to 0 on loopy graphs. You have to normalize your messages, e.g., so that they sum/max to 1. You'd want to do this on tree networks anyways, to help prevent underflow. |
You do misunderstand the algorithm. There's a bug in your implementation. How are you incorporating the factor scores into your messages?
Another possibility is for you to check out one of the many implementations of loopy bp available on the web to see what you missed.
I considered the factor scores as mentioned on PRML. My implementation correctly works on markov-chain, tree or graphs which have no loops. However, errors occur if I apply my implementation to loopy factor graph.
What I want to implement is max-sum on loopy factor graph. I searched it on the web, but I couldn't find any codes.
Max-product loopy BP can use almost the same code as sum-product loopy BP, the only difference being that when sending a factor message you maximize over the values of the other variables rather than sum over them. With this in mind you can easily grab any implementation of loopy sum-product BP and adapt it to suit your tastes.
I am reading source code of loopy sum-product, but I still feel confused. According to message update equations described in PRML, It is clear that messages diverge to -∞ for all loopy factor graph, I think.