Markov random field
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. 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 ); on the other hand, it can't represent certain dependencies that a Bayesian network can (such as induced dependencies ). 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. 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 formula_1, a set of random variables formula_2 indexed by formula_3  form a Markov random field with respect to formula_4  if they satisfy the local Markov properties: The Global Markov property is stronger than the Local Markov property, which in turn is stronger than the Pairwise one. However, the above three Markov properties  are equivalent for positive distributions (those that assign only nonzero probabilities to the associated variables). 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 formula_2, let formula_16 be the probability of a particular field configuration formula_17 in formula_18. That is, formula_16 is the probability of finding that the random variables formula_18 take on the particular value formula_17. Because formula_18 is a set, the probability of formula_17  should be understood to be taken with respect to a "joint distribution" of the formula_24. If this joint density can be factorized over the cliques of formula_4: then formula_18 forms a Markov random field with respect to formula_4. Here, formula_29 is the set of cliques of formula_4. The definition is equivalent if only maximal cliques are used. The functions formula_31 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 formula_31. This is because, in statistical mechanics, formula_33 has a direct interpretation as  the potential energy of a configuration formula_34. 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, even if one, more appropriately, allows the infinite energies to act on the complete graph on formula_3. MRF's factorize if at least one of the following conditions is fulfilled: 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  formula_36 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, formula_40 denotes the set of all possible assignments of values to all the network's random variables. Usually, the feature functions formula_41 are defined such that they are indicators of the clique's configuration, "i.e." formula_42 if formula_43 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 formula_44 is the cardinality of the clique, and  the weight of a feature formula_41 corresponds to the logarithm of the corresponding clique factor, "i.e." formula_46, where formula_47 is the "i"-th possible configuration of the "k"-th clique, "i.e." the "i"-th value in the domain of the clique formula_48. 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 formula_40 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 "J", for each vertex "v" of the graph, to the partition function to get: Formally differentiating with respect to "J" gives the expectation value of the random variable "X" associated with the vertex "v": Correlation functions are computed likewise; the two-point correlation is: 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 formula_1 if the  missing edges correspond to zeros on the precision matrix (the inverse covariance matrix): such that Inference. As in a Bayesian network, one may calculate the conditional distribution of a set of nodes formula_56 given values to another set of nodes formula_57 in the Markov random field by summing over all possible assignments to formula_58; 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. Another interesting sub-class is the one of decomposable models (when the graph is chordal): 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 formula_59. In this model, each function formula_60 is a mapping from all assignments to both the clique "k" and the observations formula_59 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, machine learning or computational biology. 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, 3D image inference from 2D images, 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.