Equivalent Markov Random Fields

Hi,

Is it possible to have topologically different Markov Random Fields (few different edges) and yet yielding the same inference results ?

Thanks!

-
I don't see any interesting mathematical quesion here. Any two independent variables $X_u,X_v$ define a MRF with respect to the discrete graph on $u$ and $v$, but also define a MRF with respect to the graph on $u$ and $v$ with one edge $uv$. –  Colin McQuillan Mar 16 '13 at 12:59
In the case of Bayesian networks: "It has been noted that different Bayesian networks may be equivalent in the sense that they actually represent the same joint probability distribution (and thus conditional independency information as well), even though they have different graphical structures." (cs.uregina.ca/Research/Techreports/2002-02.ps). I am asking the same question for MRFs. –  Raskol Mar 18 '13 at 10:32
MRFs can encode any Bayesian network, so yes, they can. It's been a while since I did any of this, but I seem to remember that, additionally, every MRF has a canonical, normalized form (as long as all potentials are nonzero) based on cliques. –  Neil Toronto Jun 9 '13 at 2:55
@raskol you need to clarify the allowed form of the clique factors. If you don't, the answer is trivially "yes", as shown by Collin McQuilan. For example, you could impose that any clique factor may not be assumed to further factorize. –  Kelly Davis Aug 29 '13 at 21:17
@Neil MRF's can't encode all Baysian networks. See for example section 8.3.4 in PRML. –  Kelly Davis Aug 29 '13 at 21:24

If two distributions have graphs that are Markov equivalent then that means that they are both a factorization of the same probability distribution.

Example: if

$p_{X_1, X_2, X_2} = p_{X_1}p_{X_2\mid X_1}p_{X_3\mid X_2}$

then there also exists other factorizations.

To evaluate these factorizations would be equivalent to evaluating the joint distribution.

Another example: $\arg\max_x P(A\in x,B) = \arg\max_x P(A\in x \mid B)P(B) = \arg\max_x P(B\mid A\in x)P(A\in x)$.

The answer is therefore yes, it is possible to have differing edges and still obtain the same result.

-