Take this graph:

$$ \overset{S}{\fbox{$+$}} \underset{\textstyle \nwarrow \!\underset{\overset{\scriptstyle X_2}{\textstyle\bigcirc}} {}} {\overset{\textstyle \swarrow \!\overset{\overset{\scriptstyle X_1}{\textstyle \bigcirc}} {\mathstrut}} {\mathstrut}} \qquad \begin{align} X_i \text{ iid }\sim B(0.5), \\ S = X_1 + X_2 \mod 2 \end{align} $$

Say you observe $S$ to be, say, $0$, and want to use belief propagation to find the most probable values for the rest of the variables. By inspection, the right answer is to say $(S,X_1,X_2)$ is uniform on $\{(0,1,1),(0,0,0)\}.$

If I understand belief propagation properly, it's never going to do better than saying $(S,X_1,X_2)$ is uniform on all of $\{(0,\cdot,\cdot)\}$. This happens because the product of S's "message" distributions is a poor approximation of the whole joint distribution, i.e. P(X1\mid S)P(X2\mid S) $\not\approx$ P(X1,X2\mid S).

How do you amend belief propagation to fix this sort of situation?

If there is no easy way (I can't think of any), what other likelihood maximization algorithms can you use if this is a dominating phenomenon in your graph?

  • 1
    $\begingroup$ I'm a bit rusty on the particulars, but I believe you can only coherently represent a hierarchical Bayesian model with a directed acyclic graphical model (DAG) if that DAG is an I-map for the Bayesian model. Your graphical model is not an I-map since it encodes independencies which don't exist in your Bayesian model. Your graphical model is, in effect, a relaxation of your Bayesian model, which means you should sometimes expect it to result in the type of degeneracy which you've just observed. Is there a reason you didn't set both your arrows to point in the opposite direction? $\endgroup$
    – Set
    Commented Jun 24, 2017 at 14:07
  • $\begingroup$ Oops, yes the arrows were the wrong direction. Also you're right, since posting I've learned that I've been using the wrong graphical model for my formulation of belief propagation. This tutorial from Mitsubishi has been useful for clearing up errors in my understanding: merl.com/publications/docs/TR2001-22.pdf $\endgroup$ Commented Jun 24, 2017 at 17:38

1 Answer 1


The figure in the question post is a directed acyclic graph (DAG), which is just one type of graphical representation of the dependecies between the random variables.

The operation of belief propagation described in the question is an algorithm for Markov random fields which are not the same as DAGs. The corresponding Markov random field looks like:

$$ \overset{S}{\fbox{$+$}} \text{ —} \overset{\scriptstyle \!\!\!(X_1,X_2)}{\bigcirc} \!\underset{\textstyle\diagdown \underset{\overset{\scriptstyle X_2}{\textstyle\bigcirc}} {}} {\overset{\textstyle \diagup \overset{\overset{\scriptstyle X_1}{\textstyle \bigcirc}} {\mathstrut}} {\mathstrut}} \qquad \begin{align} X_i \text{ iid }\sim B(0.5), \\ S = X_1 + X_2 \mod 2 \end{align} $$

where the described algorithm produces the correct answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.