# normalization in max-sum algorithm (loopy belief propagation)

I was implementing the max sum algorithm for a general graph (i.e., the ones with a cycle). I updated the messages as indicated in http://www.cedar.buffalo.edu/~srihari/CSE574/Chap8/Ch8-GraphicalModelInference/Ch8.3.3-Max-SumAlg.pdf.

What I found is that, however, in the case of a factor graph with a cycle, if the factor value is between 0 and 1, the messages will keep decreasing as the iteration goes. It is because the log of the factor value is negative and the looping in the cycle will keep adding the (negative) factor value. This can be easily verified with a factor graph with two random variable nodes and two factor nodes connecting the two random variable nodes.

It seems to me that there should be a kind of normalization after each message update but the slides I am refering to do not mention it. Does anybody know the solution for this phenomenon?

Yes. You need to normalize the messages between each iteration in order to avoid underflow.

You can normalize them so that $\log \sum_i \exp (m(i))$ = 0.

I was thinking through @user7814's answer and decided to figure out where his answer came from -- I had a hard time finding information about normalizing in log space so I decided to figure it out myself:

# Probability Space vs Log Space Normalization

We can normalize a message $\mathbf{u} = [u_1,\ u_2\, \ldots,\ u_n]$ in probability space by dividing each entry by the sum $N = \sum u_i$ resulting in the normalized message $\mathbf{\hat{u}} = \frac{1}{N}[u_1,\ u_2\, \ldots,\ u_n].$

Let the corresponding message in log probability space be $\mathbf{v} = [v_1,\ v_2\, \ldots,\ v_n]$ where $v_i = \log{u_i}$ or $u_i = e^{v_i}.$ The corresponding normalized message would be $$\mathbf{\hat{v}} = [\log{\frac{u_1}{N}},\ \log{\frac{u_2}{N}},\ \ldots,\ \log{\frac{u_n}{N}}] \\ \mathbf{\hat{v}} = [\log{u_1} - \log{N},\ \log{u_2} - \log{N},\ \ldots,\ \log{u_n} - \log{N}] \\ \mathbf{\hat{v}} = [v_1 - \log{N},\ v_2 - \log{N},\ \ldots,\ v_n - \log{N}]$$ where $$\log{N} = \log \left( \sum u_i \right) = \log \left( \sum e^{v_i} \right)$$

So letting $M = \log \sum e^{v_i}$ we get the corresponding normalized message $$\mathbf{\hat{v}} = [v_1 - M,\ v_2 - M,\ \ldots,\ v_n - M].$$

## Practical Considerations

In probability space if you are getting small $u$'s where $\sum u = N < 1$ (because you are multiplying lots of floating point numbers less than 1) then scaling by $1/N > 1$ will scale up the $u$'s (i.e., thus avoiding underflow). In log space you will have $M = \log N < \log 1 = 0$ so you will adding a small positive quantity $-M > 0$ to each $v$ we preventing the values from becoming too negative (and keeping the mean at zero).

Keep in mind that as $u \rightarrow 0$ then $v \rightarrow -\infty$ so messages should avoid these conditions.

Note that normalizing in log space is expensive! It might be worth approximating $e^x$ and $\ln{x}$ to avoid the cost.