Markov random field
In plain wordsA model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which.
An undirected probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together. in which each node is a random variable and every variable is conditionally independent of all the others given its neighbors in the graph. By the Hammersley–Clifford theorem, any strictly positive distribution with this property factorizes as a normalized product of non-negative potential functions over the graph's cliques — equivalently, a Gibbs distribution whose energy is a sum of clique terms. The normalizing constant (partition function) is generally intractable, so learning and inference rely on approximations such as Gibbs sampling, belief propagationbelief propagation, n.: A way for a network of uncertain quantities to reach conclusions by having each node pass short messages to its neighbors about what it currently believes, until the beliefs settle down., graph cuts or pseudo-likelihood. Markov random fields suit symmetric interactions with no natural direction: neighboring pixels in image denoising and segmentation, spins in the Ising model of magnetism, contacts between residues in proteins. Boltzmann machines and conditional random fieldsconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time. are variants, and energy-based modelsenergy-based model, n.: A model that scores how well things fit together by giving each possibility an 'energy': low for plausible combinations, high for implausible ones, like a ball settling into the lowest valleys. generalize the idea.
Origin
Grew from the Ising model of ferromagnetism (1920s). Roland Dobrushin's work on random fields (1968) and Frank Spitzer's paper 'Markov Random Fields and Gibbs Ensembles' (1971) set out the mathematics; who first used the name is not established. John Hammersley and Peter Clifford proved the factorization theorem in an unpublished 1971 manuscript. Julian Besag (1974) brought them into spatial statistics, and Stuart and Donald Geman (1984) into image analysis, introducing Gibbs sampling.
Related
- probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together.
- Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence.
- conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time.
- belief propagationbelief propagation, n.: A way for a network of uncertain quantities to reach conclusions by having each node pass short messages to its neighbors about what it currently believes, until the beliefs settle down.
- Markov chain Monte CarloMarkov chain Monte Carlo, n.: A family of methods for drawing random examples from a complicated probability distribution by taking a long, carefully designed random walk that eventually visits each region in proportion to its probability.
- energy-based modelenergy-based model, n.: A model that scores how well things fit together by giving each possibility an 'energy': low for plausible combinations, high for implausible ones, like a ball settling into the lowest valleys.
- Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence.
Sources
- Besag, J. (1974). Spatial Interaction and the Statistical Analysis of Lattice Systems. Journal of the Royal Statistical Society B 36(2), 192–236.
- Geman, S. & Geman, D. (1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence 6(6), 721–741.
Mentioned in
Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence., conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time., probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together., belief propagationbelief propagation, n.: A way for a network of uncertain quantities to reach conclusions by having each node pass short messages to its neighbors about what it currently believes, until the beliefs settle down., Markov logic networkMarkov logic network, n.: A way of combining logical rules with probabilities, so that a rule like 'friends usually like the same music' can sometimes be broken, with each rule given a weight saying how strongly it holds.