In the domain of physics and probability, a Markov random field,
Markov network or undirected graphical model is a set of random 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; 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; on the other
hand, it can't represent certain dependencies that a Bayesian network
can. 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 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. 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.
Definition Given an undirected graph G =, a set of
random variables X =v ∈ V indexed by V form a Markov random field with respect
to G if they satisfy the local Markov properties:
Pairwise Markov property: Any two non-adjacent variables are conditionally
independent given all other variables: Local Markov property: A variable is
conditionally independent of all other variables given its neighbors:
where ne(v) is the set of neighbors 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:
where every path from a node in A to a node in B passes through S.
The above three Markov properties are not equivalent: The Local Markov
property is stronger than the Pairwise one, while weaker than the Global one.
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 =v ∈
V, let P(X = x) be the probability of a particular field configuration x in X.
That is, P(X = x) is the probability of finding that the random variables X take
on the particular value x. Because X is a set, the probability of x should be
understood to be taken with respect to a joint distribution of the Xv.
If this joint density can be factorized over the cliques of G:
then X forms a Markov random field with respect to G. Here, cl(G) is the set of
cliques of G. The definition is equivalent if only maximal cliques are
used. The functions φ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 φC. This is because, in
statistical mechanics, log(φC) has a direct interpretation as the potential
energy of a configuration xC. Although some MRFs do not factorize, in
certain cases they can be shown to be equivalent conditions:
if the density is positive, if the graph is chordal.
When such a factorization does exist, it is possible to construct a factor graph
for the network. Logistic model
Any Markov random field can be written as log-linear model with feature
functions such that the full-joint distribution can be written as
where the notation is simply a dot product over field
configurations, and Z is the partition function:
Here, denotes the set of all possible assignments of values to all the
network's random variables. Usually, the feature functions are defined such that
they are indicators of the clique's configuration, i.e. if 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 is
the cardinality of the clique, and the weight of a feature corresponds to the
logarithm of the corresponding clique factor, i.e. , where is the i-th
possible configuration of the k-th clique, i.e. the i-th value in the
domain of the clique . 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 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 statistical mechanics, such as entropy, directly
generalize to the case of Markov networks, and an intuitive understanding
can thereby be gained. In addition, the partition function allows variational
methods to be applied to the solution of the problem: one can attach a driving
force to one or more of the random variables, and explore the reaction of
the network in response to this perturbation. Thus, for example, one may
add a driving term Jv, for each vertex v of the graph, to the partition function
to get: Formally differentiating with respect to
Jv gives the expectation value of the random variable Xv associated with the
vertex v: Correlation functions are computed
likewise; the two-point correlation is: 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 logistic
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. Examples
= Gaussian Markov random field= A multivariate normal distribution forms
a Markov random field with respect to a graph G = if the missing edges
correspond to zeros on the precision matrix:
such that Inference
As in a Bayesian network, one may calculate the conditional distribution
of a set of nodes given values to another set of nodes in the Markov
random field by summing over all possible assignments to ; 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, 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. Another interesting sub-class is the one of
decomposable models: having a closed-form for the MLE, it is possible
to discover a consistent structure for hundreds of variables.
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 . In this model, each
function is a mapping from all assignments to both the clique k and the
observations 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.
Varied Applications Markov random fields find application in
a variety of fields, ranging from Computer Graphics to Computer Vision and
Machine Learning. MRFs are used in image processing to generate textures as they
can be used to generate flexible and stochastic image models. In image
modelling, the task is to find a suitable intensity distribution of a
given image, where suitability depends on the kind of task and MRFs are
flexible enough to be used for image and texture synthesis, image compression and
restoration, image segmentation, surface reconstruction, image registration,
texture synthesis, super-resolution, stereo matching and information
retrieval. They can be used to solve various computer vision problems which
can be posed as energy minimization problems or problems where different
regions have to be distinguished using a set of discriminating features, within a
Markov Random Field framework, to predict the category of the region.
Markov Random Fields were a generalization over the Ising model and
have, since then, been used widely in combinatorial optimizations and
networks. See also
Maximum entropy method Hopfield network
Graphical model Markov chain
Markov logic network Hammersley–Clifford theorem
Interacting particle system Ising Model
Probabilistic cellular automata Log-linear analysis
References External links
MRF implementation in C++ for regular 2D lattices