In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to be a Markov random field if it satisfies Markov properties. The concept originates from the Sherrington–Kirkpatrick model.^[1]

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 joint probability density of the random variables is strictly positive, it is also referred to as a Gibbs random field, because, according to the Hammersley–Clifford theorem, it can then be represented by a Gibbs measure for an appropriate (locally defined) energy function. The prototypical Markov random field is the Ising model; indeed, the Markov random field was introduced as the general setting for the Ising model.^[2] In the domain of artificial intelligence, a Markov random field is used to model various low- to mid-level tasks in image processing and computer vision.^[3]

Definition

Given an undirected graph ${\displaystyle G=(V,E)}$, a set of random variables ${\displaystyle X=(X_{v})_{v\in V}}$ indexed by ${\displaystyle V}$  form a Markov random field with respect to ${\displaystyle G}$  if they satisfy the local Markov properties:

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} }\mid X_{\operatorname {N} (v)}}$

where ${\textstyle \operatorname {N} (v)}$ is the set of neighbors of ${\displaystyle v}$, and ${\displaystyle \operatorname {N} =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:

Zdroj:https://en.wikipedia.org?pojem=Markov_random_field
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---