Given is a chain factor graph as presented in the image below with the following properties:
- Each node can take values 0 or 1
- All unary potentials are equal (e.g. $U(a) = 0$ for every node)
- All pairwise potentials are defined as $P(a,b) = \lvert a - b\rvert$
I want to use the Min-Sum Belief Propagation algorithm to find MAP solution to the problem.
The obvious answer is that there exist two correct solutions:
- All variables have value 0
- All variables have value 1
However, the Min-Sum Belief Propagation algorithm, as the final output, gives equal beliefs for 0 and 1 at each label. As the messages are initialized to 0, they remain unchanged after the message passing and updating iterations. That and the equal unary potentials imply equal beliefs. I cannot see how that information can be used to obtain correct results.
Viterbi algorithm solves the problem easily and correctly. AFAIK, Min-Sum Belief Propagation should always find optimal solution when applied on acyclic graphs. But in this concrete example, it doesn't.
This is minimal repro example.
Does the Min-Sum Belief Propagation algorithm has a mode of failure or am I misunderstanding something?