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%20Bulatov's gravatar image

Yaroslav Bulatov
2303214164

edited Nov 15 '10 at 00:00


One Answer:

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 max-sum semi-ring 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 tree-like. I could be wrong, however.

answered Nov 13 '10 at 14:59

Gabriel%20Goh's gravatar image

Gabriel Goh
163

edited Nov 13 '10 at 15:32

Thanks for the example! I was actually looking for more applications of "Generalized Distributive Law". So far I have sum-product, maxn-product (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 max-product 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 semi-rings, "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, Tree-Reweighted 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
Your answer
toggle preview

powered by OSQA

User submitted content is under Creative Commons: Attribution - Share Alike; Other things copyright (C) 2010, MetaOptimize LLC.