MRF

Let's consider a set of random variables, x_i, organized in an undirected graph, G=(V, E), as shown in the following diagram: 

 Example of a probabilistic undirected graph

Two random variables, a and b, are conditionally independent given the random variable, c if:

Now, consider the graph again; if all generic couples of subsets of variables S_i and S_j are conditionally independent given a separating subset, S_k (so that all connections between variables belonging to S_i to variables belonging to S_j pass through S_k), the graph is called a Markov random field (MRF). 

Given G=(V, E), a subset containing vertices such that every couple is adjacent is called a clique (the set of all cliques is often denoted as cl(G)). For example, consider the graph shown previously; (x₀, x₁) is a clique and if x₀ and x₅ were connected...