Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive Belief Propagation

  1. Sep 3, 2012 #1
    Dear all,

    Let me introduce the topic first, so this thread can be put in the most appropriate subforum. Belief propagation, also called message passing, is a method that communicates messages between nodes on graphical model (for example a Markov random field) and where the messages correspond to specific types of operations (like summation and products) that leave certain global properties in tact. In different disciplines related forms of this algorithms are called the Viterbi algorithm, Turbo (de)coding, Kalman filter, the transfer-matrix approach (physics). If belief propagation converges (which it won't necessarily do in case of loops), it converges towards a stationary point of the Bethe free energy. Belief propagation can be used for indoor localisation, stereo matching, background subtraction, region filling, super-resolution, etc.

    Generalized belief propagation introduces clusters. For example when considering an image it is easy to conceive that we do not need only to communicate messages between pixels. It would be cool to communicate messages between regions (clusters or cliques) and only communicate the differences on an individual pixel level if required.

    a.) These methods look very much like renormalization group methods in statistical physics. Is there any physicist interested in looking into generalized belief propagation to see if we are not missing some recent results? For example, see [1].

    b.) How would coarse-graining methods look like in the context of optimal control? Would it correspond to setting multiple temporal horizons? Or would it try to satisfy the Bellman equation for multiple resolutions of the state variable x? See [2].

    I hope we'll have some nice discussions here. Thanks in advance!

    [1] Acceleration Strategies in Generalized Belief Propagation (2012) Chen, Wang.
    [2] Optimal Control as a Graphical Model Inference Problem (2012) Kappen, Gómez, Opper.
  2. jcsd
  3. Sep 4, 2012 #2


    User Avatar
    Science Advisor

    Hey saviourmachine.

    When you mention coarse-grained methods, the first question I have is how are you actually doing the resolution structurally?

    A few examples would include a completely hierarchical approach to something more in line with say a fourier approach where you have a signal in some region and each coeffecient gives more information as to give more "finer" details of that particular region.

    If you have a fourier type situation, it means that you can condition things on global characteristics with particular resolution as opposed to those that are completely local like a hierarchical clustering or even a non-hierarchical scheme where all clusters are mutually exclusive.

    This has obvious implications for the belief propagation because it means that the message passing doesn't take into account one completely local part of the node/cluster/whatever.

    In fact you might want to consider treating the whole thing as one node and consider all the individual bases (i.e. the trig basis vectors in the right space) as the individual message passing nodes instead of only trying to looking at a completely mutually exclusive set of nodes.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook