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

Question

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?

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.