What Are Markov Random Fields?

Markov random fields are probabilistic graphical models that represent the joint distribution of a set of random variables through an undirected graph, where nodes correspond to variables and edges encode conditional independence relationships. A variable in a Markov random field is conditionally independent of all other variables given the values of its immediate neighbors, a neighborhood relationship known as the Markov blanket. The joint distribution factorizes as a product of potential functions over the cliques of the graph, with a normalizing constant called the partition function. This representation is suited to problems where dependencies are symmetric and local, in contrast to directed graphical models such as Bayesian networks, which impose a causal ordering.

The formal study of Markov random fields draws from statistical physics, probability theory, and information theory. The connection to statistical physics is direct: the Ising model and Potts model, used to describe spin interactions in ferromagnets, are examples of Markov random fields on lattice graphs. Research documented in the ScienceDirect overview of Markov random field models traces the introduction of MRFs into image analysis to Geman and Geman's 1984 paper, which applied Gibbs distributions on image lattices to formulate image restoration as a probabilistic inference problem.

Probabilistic Structure and Undirected Graphs

The defining structural property of a Markov random field is the factorization of the joint distribution over clique potentials. A clique is a fully connected subgraph; each clique potential assigns a non-negative score to a configuration of values for the variables in that clique. The product of all clique potentials, normalized by the partition function, defines the probability of any complete variable assignment. Pairwise MRFs, which include only edges and singleton nodes, are particularly common in practice because they are expressive enough for many spatial and relational models while admitting tractable inference algorithms. The lecture notes from Stanford's CS 228 course on probabilistic graphical models and undirected representations provide a systematic treatment of this factorization and its relationship to conditional independence.

Inference Methods

Computing marginal probabilities or finding the most probable configuration in a Markov random field is generally computationally hard because the partition function sums over an exponential number of configurations. In practice, approximate inference methods are used. Belief propagation passes probability messages between neighboring nodes iteratively and is exact on tree-structured graphs; on graphs with cycles, called loopy belief propagation, it often converges to accurate approximations in practice. Gibbs sampling, a Markov chain Monte Carlo method, draws samples from the joint distribution by iteratively resampling each variable conditioned on its neighbors, and is widely used when closed-form solutions are unavailable. Graph cut algorithms provide exact or approximate inference for specific classes of pairwise MRFs with submodular energy functions, and have become the standard approach in image segmentation and stereo matching. An arxiv preprint on exact and approximate inference in graphical models surveys the relative strengths and computational complexity tradeoffs across these inference families.

Parameter Learning and Applications in Vision

Learning an MRF from data requires estimating the parameters of the clique potentials that best fit observed variable configurations. Maximum likelihood estimation involves gradients of the log-partition function, which are themselves posterior expectations and require running inference at each gradient step, making exact learning intractable for large models. Pseudo-likelihood methods and contrastive divergence provide tractable approximations. In computer vision, learned MRFs are applied to image segmentation, texture synthesis, super-resolution, and scene labeling, where spatially correlated pixel labels benefit from the neighborhood dependency structure. A paper on block belief propagation for MRF parameter learning on arxiv describes an approach that scales learning to larger graphs by propagating only local blocks of variables at each iteration.

Applications

Markov random fields have applications in a wide range of disciplines, including:

• Computer vision, modeling spatial dependencies in image segmentation and stereo depth estimation
• Natural language processing, labeling sequences and parsing syntactic structure
• Computational biology, predicting protein structure contacts from evolutionary covariation
• Spatial statistics, modeling geographically correlated environmental measurements
• Communications, decoding low-density parity-check codes with belief propagation