# Implementing sum product belief propagation

While implementing a stereo belief propagation algorithm, it is required to transform the unary and pairwise energy terms (that one comes across in graph cuts) as negative exponent of e. It is done as follows: exp(-B/C), where B is the unary/pairwise term and C is some constant required for numerical stability. It looks like the algorithm's performance very much changes according to the constant C. Is there any rule of thumb for deciding this constant C?

Edit: Refer section 3 (page 3) of Comparison of Graph Cuts with Belief Propagation for Stereo, using Identical MRF Parameters, where this transformation of unary and pairwise energies to suit BP is given.

$C$ in your formulation is generally called the temperature parameter and by changing it your are basically solving a different problem. In the case of Markov nets, Sum-product Belief Propagation is solving the marginalization problem for a distribution $P$ over $x = \{x_1,\ldots,x_N\}$ defined as:

$P(x) = \exp(\sum_{i,j} f(x_i,x_j) )$

Here the marginal over $x_i$ is defined as:

$P(x_i) = \sum_{x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_N} P(x)$

and belief propagation is an efficient method for finding this marginal without performing this exponentially expensive summation.

Now when you add the temperature parameter $T$ you have:

$P(x)^{\frac{1}{T}} = \exp(\frac{1}{T}\sum_{i,j} f(x_i,x_j) )$

you are marginalizing a different distribution i.e. $P(x)^{\frac{1}{T}}$. Here I assume your objective is to find a single assignment with high probability

$x = \arg_x\max P(x)$

If so, it is generally better to use max-product (a.k.a. min-sum) Belief Propagation. In that case the temperature parameter does not have any effect on the optimal assignment.

• Thanks for your inputs. I think I am still solving the marginalization problem after introducing C. It looks like C has an effect on how soon the iterations converge. – haripkannan Feb 22 '14 at 14:34
• Yes, higher temperatures usually correspond to easier inference problems and marginals are closer to uniform. In fact in order to evaluate inference methods using Ising model temperature is used to control the difficulty of the problem. – SKV Feb 23 '14 at 2:13