Markov network

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 brace represents a dependency between random variables u and v,

- a set of .

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_ to all nodes in the network is given by frac{1}{Z} prod_{i = 1}^ 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_} prod_{i = 1}^ 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 brace 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 brace given values to another set of nodes W = lbrace w_1 ... w_l brace in the Markov network by summing over all possible assignments to u otin V ,W ; this is called exact inference. However, exact inference is a Sharp-P-complete problem, and thus computationally intractable. Approximation techniques such as Markov chain Monte Carlo and belief propagation are more feasible in practice.