Markov random field

In the domain of

A Markov network or MRF is similar to a Bayesian network in its representation of dependencies; the differences being that Bayesian networks are directed and acyclic, whereas Markov networks are undirected and may be cyclic. Thus, a Markov network can represent certain dependencies that a Bayesian network cannot (such as cyclic dependencies ^{[further explanation needed]}); on the other hand, it can't represent certain dependencies that a Bayesian network can (such as induced dependencies ^{[further explanation needed]}). The underlying graph of a Markov random field may be finite or infinite.

When the

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

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\smallsetminus \{u,v\}}}$

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

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\smallsetminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}$

where ${\textstyle \operatorname {N} (v)}$ is the set of neighbors of ${\displaystyle v}$, and ${\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)}$ is the

closed neighbourhood

of ${\displaystyle v}$.

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

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

where every path from a node in ${\displaystyle A}$ to a node in ${\displaystyle B}$ passes through ${\displaystyle S}$.

The Global Markov property is stronger than the Local Markov property, which in turn is stronger than the Pairwise one.^[4] However, the above three Markov properties are equivalent for positive distributions^[5] (those that assign only nonzero probabilities to the associated variables).

The relation between the three Markov properties is particularly clear in the following formulation:

• Pairwise: For any ${\displaystyle i,j\in V}$ not equal or adjacent, ${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$.
• Local: For any ${\displaystyle i\in V}$ and ${\displaystyle J\subset V}$ not containing or adjacent to ${\displaystyle i}$, ${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$.
• Global: For any ${\displaystyle I,J\subset V}$ not intersecting or adjacent, ${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$.

Clique factorization

As the Markov property 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 ${\displaystyle X=(X_{v})_{v\in V}}$, let ${\displaystyle P(X=x)}$ be the probability of a particular field configuration ${\displaystyle x}$ in ${\displaystyle X}$—that is, ${\displaystyle P(X=x)}$ is the probability of finding that the random variables ${\displaystyle X}$ take on the particular value ${\displaystyle x}$. Because ${\displaystyle X}$ is a set, the probability of ${\displaystyle x}$ should be understood to be taken with respect to a joint distribution of the ${\displaystyle X_{v}}$.

If this joint density can be factorized over the cliques of ${\displaystyle G}$ as

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})}$

then ${\displaystyle X}$ forms a Markov random field with respect to ${\displaystyle G}$. Here, ${\displaystyle \operatorname {cl} (G)}$ is the set of cliques of ${\displaystyle G}$. The definition is equivalent if only maximal cliques are used. The functions ${\displaystyle \varphi _{C}}$ are sometimes referred to as factor potentials or clique potentials. Note, however, conflicting terminology is in use: the word potential is often applied to the logarithm of ${\displaystyle \varphi _{C}}$. This is because, in statistical mechanics, ${\displaystyle \log(\varphi _{C})}$ has a direct interpretation as the potential energy of a configuration ${\displaystyle x_{C}}$.

Some MRF's do not factorize: a simple example can be constructed on a cycle of 4 nodes with some infinite energies, i.e. configurations of zero probabilities,^[6] even if one, more appropriately, allows the infinite energies to act on the complete graph on ${\displaystyle V}$.^[7]

MRF's factorize if at least one of the following conditions is fulfilled:

• the density is positive (by the Hammersley–Clifford theorem)
• 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.

Exponential family

Any positive Markov random field can be written as exponential family in canonical form with feature functions ${\displaystyle f_{k}}$ such that the full-joint distribution can be written as

${\displaystyle P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)}$

where the notation

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})}$

is simply a dot product over field configurations, and Z is the partition function:

${\displaystyle Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right).}$

Here, ${\displaystyle {\mathcal {X}}}$ denotes the set of all possible assignments of values to all the network's random variables. Usually, the feature functions ${\displaystyle f_{k,i}}$ are defined such that they are indicators of the clique's configuration, i.e. ${\displaystyle f_{k,i}(x_{\{k\}})=1}$ if ${\displaystyle x_{\{k\}}}$ corresponds to the i-th possible configuration of the k-th clique and 0 otherwise. This model is equivalent to the clique factorization model given above, if ${\displaystyle N_{k}=|\operatorname {dom} (C_{k})|}$ is the cardinality of the clique, and the weight of a feature ${\displaystyle f_{k,i}}$ corresponds to the logarithm of the corresponding clique factor, i.e. ${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$, where ${\displaystyle 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 ${\displaystyle C_{k}}$.

The probability P is often called the Gibbs measure. This expression of a Markov field as a logistic model is only possible if all clique factors are non-zero, i.e. if none of the elements of ${\displaystyle {\mathcal {X}}}$ are assigned a probability of 0. This allows techniques from matrix algebra to be applied, e.g. that the trace of a matrix is log of the determinant, with the matrix representation of a graph arising from the graph's incidence matrix.

The importance of the partition function Z is that many concepts from

Correlation functions are computed likewise; the two-point correlation is:

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

Unfortunately, though the likelihood of a logistic Markov network is convex, evaluating the likelihood or gradient of the likelihood of a model requires inference in the model, which is generally computationally infeasible (see 'Inference' below).

Examples

Gaussian

A multivariate normal distribution forms a Markov random field with respect to a graph ${\displaystyle G=(V,E)}$ if the missing edges correspond to zeros on the

${\displaystyle (\Sigma ^{-1})_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.}$[8]

Inference

As in a

${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$

${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$

${\displaystyle u\notin V',W'}$

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 ${\displaystyle o}$. In this model, each function ${\displaystyle \varphi _{k}}$ is a mapping from all assignments to both the clique k and the observations ${\displaystyle 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. CRFs were proposed by John D. Lafferty, Andrew McCallum and Fernando C.N. Pereira in 2001.^[12]

Varied applications

Markov random fields find application in a variety of fields, ranging from

References