1
$\begingroup$

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!

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Can you define "MRF" & "CRF"? $\endgroup$ – gung - Reinstate Monica Oct 22 '13 at 16:06
  • 1
    $\begingroup$ @gung Markov random field and Conditional random field. $\endgroup$ – David J. Harris Oct 22 '13 at 16:18
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Aaah, I think after reading your interpretation of the sentence, I just misunderstood it. The thing is that my colleague argued that once additional edges are added from y variables to the x variables (as you typically have in CRFs), you would no longer have a MRF. He pointed me to this document for an explanation, but I wasn't really satisfied as his statement contradicted what I believed to know about MRFs. Thank you a lot for this answer! $\endgroup$ – Pandoro Oct 22 '13 at 16:54
  • $\begingroup$ If you add directed edges (like in CRFs), then it's not an MRF anymore, but undirected edges (like in Boltzmann Machines) are totally fine. $\endgroup$ – David J. Harris Oct 22 '13 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.