# How do you do belief propagation on nodes with conditional dependence?

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?

• 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?
– Set
Commented Jun 24, 2017 at 14:07
• 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 Commented Jun 24, 2017 at 17:38

\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}