Markov Random Field Non-Positive Distribution

Question

The joint distribution in a Markov Network can be represented as:

$P(X=x) = \frac{1}{Z}\phi_k(x_k)$

where $\phi_k$ represents the $k^{th}$ factor.

While reading Improving Markov Network Structure Learning Using Decision Trees, I came across a line that mentions "Any probability distribution that can be represented as a product of potential functions over the cliques of the graph, as in Equation (1), satisfies these independencies; for positive distributions, the converse holds as well", with equation (1) referring to the joint distribution representation as mentioned.

What goes wrong when the distribution is not positive?

Answer 1

The forward direction is actually quite a deep result, known as the Hammersley-Clifford Theorem. The counterexample for non-positive distributions was found by Moussouris, and you can see it on page 12 here, and the explanation that follows on page 13. The given network is not factorable.

In case the link goes stale, consider a distribution 4 nodes that form a square, with vertices labeled $(a,b,c,d)$ in clockwise order. Then define a uniform distribution on 8 of the following configurations (with the other 8 having zero probability):

1----1    1----1
|    |    |    |
|    |    |    |
1----1    0----1

1----0    0----1
|    |    |    |
|    |    |    |
1----0    0----1

1----0    0----0
|    |    |    |
|    |    |    |
0----1    0----1

0----0    0----0
|    |    |    |
|    |    |    |
1----0    0----0

The proof is to then assume the distribution factorizes. An exhaustive search on the above configurations will show all four factors are positive. This is a contradiction since the remaining 8 states have 0 probability.