Markov random field

A Markov random field, Markov network or undirected graphical model is a set of variables having a Markov property described by an undirected graph. A Markov random field is similar to a Bayesian network in its representation of dependencies. It can represent certain dependencies that a Bayesian network cannot (such as cyclic dependencies); on the other hand, it can't represent certain dependencies that a Bayesian network can (such as induced dependencies). The prototypical Markov random field is the Ising model; indeed, the Markov random field was introduced as the general setting for the Ising model.^[1] A Markov random field is used to model various low- to mid-level tasks in image processing and computer vision.^[2] For example, MRFs are used for image restoration, image completion, segmentation, texture synthesis, super-resolution and stereo matching.

Definition

Given an undirected graph G = (V, E), a set of random variables X = (X_v)_v ∈ V indexed by V  form a Markov random field with respect to G  if they satisfy the following equivalent Markov properties:

Pairwise Markov property: Any two non-adjacent variables are conditionally independent given all other variables:

$X_u \perp\!\!\!\perp X_v | X_{V \setminus \{u,v\}} \quad \text{if } \{u,v\} \notin E$

Local Markov property: A variable is conditionally independent of all other variables given its neighbours:

$X_v \perp\!\!\!\perp X_{V\setminus \operatorname{cl}(v)} | X_{\operatorname{ne}(v)}$

where ne(v) is the set of neighbours of v, and cl(v) = {v} ∪ ne(v) is the closed neighbourhood of v.

Global Markov property: Any two subsets of variables are conditionally independent given a separating subset:

$X_A \perp\!\!\!\perp X_B | X_S$

where every path from a node in A to a node in B passes through S.

In other words, a graph G is considered a Markov random field with respect to the joint probability distribution P(X=x) over a set of random variables X if and only if graph separation in G implies conditional independence: If two nodes corresponding to $X_i \in X$ and $X_j \in X$ are separated in G after removing from G a set of nodes Z, then P(X=x) must assert that X_i and X_j are conditionally independent given the random variables corresponding to Z. If this condition is satisfied, we say that G is an independency map (or I-Map) of the probability distribution.

Many definitions go even further and require that G be a minimal I-Map, i.e. an I-Map from which none of the edges could be removed without destroying its I-Mapness. (It is reasonable to require this as it leads to the most compact representation, which involves as few dependencies as possible; note that a complete graph is trivially an I-Map.) In the case where G is not only an I-Map (i.e. it represents no independencies that are not indicated by P(X=x)) but also represents no dependencies that are not indicated by P(X=x), G is called a perfect map of P(X=x), as it represents precisely the set of independencies indicated by P(X=x).

Clique factorization

As the Markov properties of an arbitrary probability distribution can be difficult to establish, a commonly used class of Markov random fields are those that can be factorized according to the cliques of the graph.

Given a set of random variables X = (X_v)_v ∈ V for which the joint density (with respect to a product measure) can be factorized over the cliques of G:

$p(x) = \prod_{C \in \operatorname{cl}(G)} \phi_C (x_C)$

then X forms a Markov random field with respect to G, where cl(G) is the set of cliques of G (the definition is equivalent if only maximal cliques are used). The functions φ_C are often referred to as factor potentials or clique potentials.

Although some MRFs do not factorize (a simple example can be constructed on a cycle of 4 nodes^[3]), in certain cases they can be shown to be equivalent conditions:

• if the density is positive (by the Hammersley–Clifford theorem),
• if the graph is chordal (by equivalence to a Bayesian network).

When such a factorization does exist, it is possible to construct a factor graph for the network.

Examples

Log-linear models

A log-linear model is a Markov random field with feature functions f_k such that the full-joint distribution can be written as

$P(X=x) = \frac{1}{Z} \exp \left( \sum_{k} w_k^{\top} f_k (x_{ \{ k \}}) \right) = \frac{1}{Z} \exp \left( \sum_k \sum_{i=1}^{N_k} w_{k,i} \cdot f_{k,i}(x_{\{k\}}) \right)$

with partition function

$Z = \sum_{x \isin \mathcal{X}} \exp \left(\sum_{k} w_k^{\top} f_k(x_{ \{ k \} })\right)$.

where $\mathcal{X}$ is the set of possible assignments of values to all the network's random variables. Usually, the feature functions f_k,i are defined such that they are indicators of the clique's configuration, i.e. f_k,i(x_{k}) = 1 if x_{k} corresponds to the i-th possible configuration of the k-th clique and 0 otherwise. This model is thus equivalent to the general formulation above if N_k = | dom(C_k) | and the weight of a feature f_k,i corresponds to the logarithm of the corresponding clique potential, i.e. w_k,i = log ϕ(c_k,i), where c_k,i is the i-th possible configuration of the k-th clique, i.e. the i-th value in the domain of the clique C_k. Note that this is only possible if all clique potentials are non-zero, i.e. if none of the elements of $\mathcal{X}$ are assigned a probability of 0.

Log-linear models are especially convenient for their interpretation. A log-linear model can provide a much more compact representation for many distributions, especially when variables have large domains. They are convenient too because their negative log likelihoods are convex. Unfortunately, though the likelihood of a log-linear Markov network is convex, evaluating the likelihood or gradient of the likelihood of a model requires inference in the model, which is in general computationally infeasible.

Gaussian Markov random field

A multivariate normal distribution forms a Markov random field with respect to a graph G = (V, E) if the missing edges correspond to zeros on the precision matrix (the inverse covariance matrix):

$X=(X_v)_{v\in V} \sim \mathcal N (\boldsymbol \mu, \Sigma) \qquad \text{such that} \qquad (\Sigma^{-1})_{uv} =0 \quad \text{if} \quad \{u,v\} \notin E .$^[4]

Inference

As in a Bayesian network, one may calculate the conditional distribution of a set of nodes V' = {v₁,...,v_i} given values to another set of nodes W' = {w₁,...,w_j} in the Markov random field by summing over all possible assignments to $u \notin V',W'$; this is called exact inference. However, exact inference is a #P-complete problem, and thus computationally intractable in the general case. Approximation techniques such as Markov chain Monte Carlo and loopy belief propagation are often more feasible in practice. Some particular subclasses of MRFs, such as trees see Chow-Liu tree, have polynomial-time inference algorithms; discovering such subclasses is an active research topic. There are also subclasses of MRFs that permit efficient MAP, or most likely assignment, inference; examples of these include associative networks.

Conditional random fields

One notable variant of a Markov random field is a conditional random field, in which each random variable may also be conditioned upon a set of global observations o. In this model, each function φ_k is a mapping from all assignments to both the clique k and the observations o to the nonnegative real numbers. This form of the Markov network may be more appropriate for producing discriminative classifiers, which do not model the distribution over the observations.

See also

• Maximum entropy method
• Hopfield network
• Graphical model
• Markov chain
• Markov logic network
• Hammersley–Clifford theorem
• Markov-Gibbs properties

References

1. ^ Kindermann, Ross; Snell, J. Laurie (1980). Markov Random Fields and Their Applications. American Mathematical Society. ISBN 0-8218-5001-6. MR0620955. http://www.ams.org/online_bks/conm1/. 
2. ^ Li, S. Z. (2009). Markov Random Field Modeling in Image Analysis. Springer. 
3. ^ Moussouris, John (1974). "Gibbs and Markov random systems with constraints". Journal of Statistical Physics 10 (1): 11–33. doi:10.1007/BF01011714. MR0432132. 
4. ^ Rue, Håvard; Held, Leonhard (2005). Gaussian Markov random fields: theory and applications. CRC Press. ISBN 1584884320.