Are MRFs with edges to all observed data possible? I have been discussing the following issue with a colleague of mine and I can't seem to wrap my head around it. I have a computer vision background, so I'm mostly familiar with 2D MRFs/CRFs for image restoration and segmentation. 
What is clear to me is that MRFs typically have a simple 2D grid structure for p(x) and each underlying variable x_i has an edge to the corresponding pixel y_i in the graph for the posterior p(y|x). In CRFs you have an edge to each pixel y in the image. I can fully understand that CRFs are trained in a discriminative way and thus they are tractable and that it wouldn't be possible to really learn a generative model based on such a CRF graph. However in all the literature it seems that by definition the MRF model cannot have edges from a x_i to all pixels y, as it then would no longer be a MRF. For example the following states: 

If the conditional independence assumption is not used, the posterior will usually not be a MRF making the inference difficult.

Now that it would not be tractable to actually learn such a model I can understand, but why would it no longer be an MRF and also what would it be then? Because I don't see why it would by definition become a CRF, as we do not NEED to condition it on the data. 
I really hope someone can tell me what I am missing here, or where my mistake is!
 A: Restricted Boltzmann Machines are Markov random fields that usually have complete connectivity between the hidden and visible variables.  If we drop the "restricted" part and look at Boltzmann Machines more generally, there can also be complete connectivity among the visible variables (pixels).
So yes, they're possible.
I haven't read the whole paper you linked to, but here is my assessment of what they mean.


*

*If $p(x)$ is an MRF, and all the elements of $y$ are conditionally independent of one another given $x$, then $p(x, y)$ is also an MRF.

*If the $y$ variables are not conditionally independent of one another, then this will not necessarily be true (although it still could be).  For instance, if there were directed connections among the $y$ variables, then you wouldn't have an MRF anymore.
However, the case you seem to be thinking about, where there are undirected connections between the variables (like the Boltzmann Machines I linked to) are still considered MRFs because all their pieces are MRFs.
