Are there examples of applying generalized BP to domains that don't involve real numbers? For instance, BP can be used for Fourier Transform over finite groups (it's an example in the Generalized Distributive Law paper), can GBP be similarly used on finite domains? Closely related questions is  for which problems is GBP exact? (in analogy to BP which is exact for trees) asked Nov 11 '10 at 14:35 Yaroslav Bulatov 
Interesting question. I've seen BP has been used over polytopes in Algebraic Statistics to do MAP inference on a HMM. This is not the vanilla maxsum semiring inference which is really dynamic programming, however. The gist of it is  instead of propagating over a max/sums with on a parametric model, (tropical arithmetic), you propagate over the convex hull/minkowski sums of all possible sequences generated by all possible parameters (the details are a bit more complicated). Amazingly, the (convex hull, Minkowski sum) form a semiring which you can use the BP algorithm on. If this is slightly opaque to you, I recommend reading Parametric inference for biological sequence analysis. I'm pretty sure there's a use for BP in Boolean Formulas too, I would guess it's for solving SAT type problems, but I don't know what it is. I cannot see why convergence in BP should be different for any other semiring i.e it converges in a finite number of steps iff the graph is treelike. I could be wrong, however. answered Nov 13 '10 at 14:59 Gabriel Goh Thanks for the example! I was actually looking for more applications of "Generalized Distributive Law". So far I have sumproduct, maxnproduct (find n top scoring sequences), fast fourier transform on abelian groups, solving sparse linear equation systems (Gaussian BP), constraint propagation, and now  polytope propagation. By the way, "Generalized Belief Propagation" is something different. Regular BP can be formulated as message passing between two types of regions  clusters and separators. Generalized BP extends this to more than 2 types.
(Nov 14 '10 at 20:16)
Yaroslav Bulatov
Note that the maxproduct version of "Generalized BP" is simply Dynamic Programming. I think this has to be both Generalized both in the algebraic sense and the the second way you describe (I'm not sure about this though), to encompass all dynamic programming algorithms. I found this quite startling when I discovered this for the first time. Semirings rule.
(Nov 15 '10 at 00:54)
Gabriel Goh
I think there's some terminology confusion here  there's "Generalized Distributive Law" and "Generalized Belief Propagation", described in papers named "Generalized Distributive Law" and "Generalized Belief Propagation", respectively. "Generalized Distributive Law" shows how to extend BP to distributive semirings, "Generalized Belief Propagation" shows how to extend BP to general message structures. It would be neat if you could combine the two into "Generalized Generalized Distributive Law." ATM I'm not sure it's possible, hence the question
(Nov 15 '10 at 03:49)
Yaroslav Bulatov
actually, I understand you perfectly, (but only after your first comment) though I have articulated myself poorly. I am talking about a "Generalized Generalized Distributive Law", in the context of Dynamic Programming Algorithms. These are intuitions I have had for some time, actually. A more concrete example: The Viterbi Algorithm can be seen as a version of "Generalized Distributive BP"  it can be written as a graphical model, in fact it's structure is identical to that of a HMM. Sequence Alignment needs a "Generalized Generalized Distributive BP", as it cannot be written down as a graphical model. You can try this out as an exercise if you wish. This would be an example of a "Generalized Generalized Distributive BP" algorithm, I think. These are just my personal intuitions and I could be totally wrong.
(Nov 15 '10 at 18:24)
Gabriel Goh
Still not sure if that relates to "Generalized Belief Propagation" of Yedidia. To summarize GBP you define a hierarchy of regions and a set of counting numbers. Different counting numbers recover different algorithms The messages propagate up and down the region hierarchy. Different counting numbers recover different algorithms, Convex Belief Propagation, TreeReweighted Belief Propagation, Fractional Belief Propagation (and of course, standard BP) are special cases. From a brief scan of Sturmfels paper, it seems like their generalization goes in a different direction, ie, I don't see how it might cover Fractional/TRW/Convex BP. We might need a Generalized Generalized Generalized Distributive law to cover all inference related message passing
(Nov 15 '10 at 21:08)
Yaroslav Bulatov
