Markov random field

A Markov network, also called a Markov random field, is represented by:

- an undirected graph $G=(V,E)$, where each vertex $v\in V$ represents a random variable and each edge $e=\lbrace u,v\in E\rbrace$ represents a dependency between random variables $u$ and $v$,

- a set of potential functions $\Phi =\phi _{c_{i}}:A_{c_{i}}\rightarrow R^{+}$, where each $c_{i}=\lbrace i_{1},i_{2},...i_{|c_{i}|}\rbrace$ represents a clique in $G$, and $A_{c_{i}}$ is the set of all possible assignments to the random variables represented by $v_{i_{1}},v_{i_{2}},...v_{i_{|c_{i}|}}$. In other words, each clique has associated with it a function from possible assignments to all nodes to the nonnegative real numbers.

The potential functions used in a Markov network do not necessarily have a probabilistic interpretation by themselves, but a higher value indicates a more probable assignment to the variables in a clique. The network is used to represent the joint distribution over all variables represented by nodes in the graph. The probability of an assignment $v_{1},v_{2},...v_{|V|}$ to all nodes in the network is given by ${\frac {1}{Z}}\prod _{i=1}^{|\Phi |}\phi _{c_{i}}(v_{i_{1}},v_{i_{2}},...v_{i_{c_{i}}})$, where $Z$ is a normalizing constant $\sum _{v_{1},v_{2},...v_{|V|}}\prod _{i=1}^{|\Phi |}\phi _{c_{i}}(v_{i_{1}},v_{i_{2}},...v_{i_{c_{i}}})$ summing over all possible assignments to all nodes in the network.

The Markov blanket of a node $v_{i}$ in a Markov network is defined to be every node with an edge to $v_{i}$, i.e. all $v_{j}$ such that $\lbrace v_{i},v_{j}\rbrace \in E$. Every node $v$ in a Markov network is conditionally independent of every other node given the Markov blanket of $v$.

A Markov network is similar to a Bayesian network in its representation of dependencies, but a Markov network can represent dependencies that a Bayesian network can not. A Bayesian network, for instance, can not represent cyclic dependencies, while a Markov network can.

As in a Bayesian network, one may calculate the conditional distribution of a set of nodes $V'=\lbrace v_{1}...v_{k}\rbrace$ given values to another set of nodes $W'=\lbrace w_{1}...w_{l}\rbrace$ in the Markov network by summing over all possible assignments to $u\notin V',W'$; this is called exact inference. However, exact inference is a #P-complete problem, and thus computationally intractable. Approximation techniques such as Markov chain Monte Carlo and belief propagation are more feasible in practice.