What's the difference between a Markov Random Field and a Conditional Random Field?

Question

If I fix the values of the observed nodes of an MRF, does it become a CRF?

Answer 1

Ok, I found the answer myself:

Conditinal Random Fields (CRFs) are a special case of Markov Random Fields (MRFs).

1.5.4 Conditional Random Field

A Conditional Random Field (CRF) is a form of MRF that defines a posterior for variables x given data z, as with the hidden MRF above. Unlike the hidden MRF, however, the factorization into the data distribution P (x|z) and the prior P (x) is not made explicit [288]. This allows complex dependencies of x on z to be written directly in the posterior distribution, without the factorization being made explicit. (Given P (x|z), such factorizations always exist, however—infinitely many of them, in fact—so there is no suggestion that the CRF is more general than the hidden MRF, only that it may be more convenient to deal with.)

Source: Blake, Kohli and Rother: Markov random fields for vision and image processing. 2011.

A conditional random field or CRF (Lafferty et al. 2001), sometimes a discriminative random field (Kumar and Hebert 2003), is just a version of an MRF where all the clique potentials are conditioned on input features: [...]

The advantage of a CRF over an MRF is analogous to the advantage of a discriminative classifier over a generative classifier (see Section 8.6), namely, we don’t need to “waste resources” modeling things that we always observe. [...]

The disadvantage of CRFs over MRFs is that they require labeled training data, and they are slower to train[...]

Source: Kevin P. Murphy: Machine Learning: A Probabilistic Perspective

Answering my question:

If I fix the values of the observed nodes of an MRF, does it become a CRF?

Yes. Fixing the values is the same as conditioning on them. However, you should note that there are differences in training, too.

Watching many of the lectures about PGM (probabilistic graphical models) on coursera helped me a lot.

Answer 2

Let's contrast conditional inference under MRFs with modeling using a CRF, settling on definitions along the way, and then address the original question.

MRF

A Markov Random Field (MRF) with respect to a graph $G$ is

1. a set of random variables (or random "elements" if you like) corresponding to the nodes in $G$ (thus, a "random field")
2. with a joint distribution that is Markov with respect to $G$; that is, the joint probability distribution associated with this MRF is subject to the Markov constraint given by G: for any two variables, $V_i$ and $V_j$, the value of $V_i$ is conditionally independent of $V_j$ given its neighbors $\mathcal{B}_i$. In this case, it is said that the joint probability distribution $P(\{V_i\})$ factorizes according to $G$.

Conditional Inference Under an MRF

Since an MRF represents a joint distribution over many variables that obeys Markov constraints, then we can compute conditional probability distributions given observed values of some variables.

For example, if I have a joint distribution over four random variables: IsRaining, SprinklerOn, SidewalkWet, and GrassWet, then on Monday I might want to infer the joint probability distribution over IsRaining and SprinklerOn given that I have observed SidewalkWet=False and GrassWet=True. On Tuesday, I might want to infer the joint probability distribution over IsRaining and SprinklerOn given that I have observed SidewalkWet=True and GrassWet=True.

In other words, we can use the same MRF model to make inferences in these two different situations, but we wouldn't say that we've changed the model. In fact, although we observed SidewalkWet and GrassWet in both cases described here, the MRF itself doesn't have "observed variables" per se---all variables have the same status in the eyes of the MRF, so the MRF also models, e.g., the joint distribution of SidewalkWet and GrassWet.

CRF

In contrast, we can define a Conditional [Markov] Random Field (CRF) with respect to a graph $G$ as

1. a set of random variables corresponding to the nodes in $G$, a subset $\{X_i\}_{i=1}^n$ of which are assumed to always be observed and remaining variables $\{Y_i\}_{i=1}^m$
2. with a conditional distribution $P(\{Y_i\}_{i=1}^m|\{X_i\}_{i=1}^n)$ that is Markov with respect to $G$

The Difference

For both MRFs and CRFs, we typically fit a model that we can then use for conditional inference in diverse settings (as in the rain example above). However, while the MRF has no consistently designated "observed variables" and needs a joint distribution over all variables that adheres to the Markov constraints of $G$, a CRF:

1. designates a subset of variables as "observed"

2. only defines a conditional distribution on non-observed given observed variables; it does not model the probability of the observed variables (if distributions are expressed in terms of parameters, this is often seen as a benefit since parameters are not wasted in explaining the probability of things that will always be known)

3. needs only obey Markov constraints with respect to the unobserved variables (i.e. the distribution over unobserved variables can depend arbitrarily on the observed variables while inference is at least as tractable as for the MRF on $G$)

Since a CRF does not need to obey Markov constraints on the observed variables $\{X_i\}$, these are typically not even shown in graphical representations of a CRF (possibly a point of confusion sometimes). Instead, the CRF on $G$ is defined as an MRF on a graph $G'$ where nodes are only included for the $\{Y_i\}$s and where the parameters of the joint distribution of $\{Y_i\}$s are functions of the $\{X_i\}$s, thus conditionally defining a distribution of $\{Y_i\}$s given the $\{X_i\}$s.

Example

As a final example, the following linear-chain MRF would indicate that all of the $Y_i$ variables are conditionally independent of $X_1, X_2, ... X_{n-1}$ given a known value of $X_n$:

In contrast, a CRF defined on the same $G$ with the same designation of $\{X_i\}$s as being always observed, would allow for distributions of the $\{Y_i\}$s that depend arbitrarily on any of the $\{X_i\}$s.

Conclusion

So, although ("yes") the conditional distribution of a MRF on $G$ given designated observed variables can be considered to be a CRF with respect to $G$ (since it defines a conditional distribution that obeys the Markov constraints of $G$), it is somewhat degenerate, and does not achieve the generality of CRFs on $G$. Instead, the appropriate recipe would be, given an MRF on $G$, define an MRF on the non-observed subset of $G$ with parameters of the MRF expressed as the output of parameterized functions of the observed variables, training the function parameters to maximize the likelihood of the resulting conditional MRFs on labeled data.

In addition to the potential savings of model paramters, increased expressiveness of conditional model, and retention of inference efficiency, a final important point about the CRF recipe is that, for discrete models (and a large subset of non-discrete models), despite the expressiveness of the CRF family, the log-likelihood can be expressed as a convex function of the function parameters allowing for global optimization with gradient descent.

See also: the original crf paper and this tutorial

Answer 3

MRF vs Bayes nets: Unpreciesly (but normally) speaking, there are two types of graphical models: undirected graphical models and directed graphical models(one more type, for instance Tanner graph). The former is also known as Markov Random Fields/Markov network and the later Bayes nets/Bayesian network. (Sometimes the independence assumptions in both can be represented by chordal graphs)

Markov implies the way it factorizes and random field means a particular distribution among those defined by an undirected model.

CRF $\in$ MRF: When some variables are observed we can use the same undirected graph representation(as the undirected graphs) and parameterization to encode a conditional distribution $P(Y|X)$ where $Y$ is a set of target variables and $X$ is a (disjoint) set of observed variables.

And the only difference lies in that for a standard Markov network the normalization term sums over X and Y but for CRF the term sums over only Y.

Reference:

1. Undirected graphical models (Markov random fields)
2. Probabilistic Graphical Models Principles and Techniques (2009, The MIT Press)
3. Markov random fields