I'm reading the notes here. The formal definiton states

A Markov Random Field (MRF) is a probability distribution $p$ over variables $x_1,\ldots,x_n$ defined by an undirected graph $G$ in which nodes correspond to variables $x_i$. The probability $p$ has the form $p(x_1,\ldots,x_n)=\frac{1}{Z} \Pi_{c \in C} \phi_c(x_c)$, where $C$ denotes the set of cliques of $G$.

Question 1: In this notation, what does $x_c$ mean? I'm guessing it's some sort of restriction of the variables in clique $c$ to the values $x_1, \ldots, x_n$?

Question 2: They go on to write:

Note that we do not need to specifiy a factor for each clique.

But the above product runs over all possible cliques, so how does this work? Technically we can specify no factors at all?


1 Answer 1


Let's take the 4-node example further up on the page you linked to. The set of all cliques is $C = \{\{A\},\{B\},\{C\},\{D\},\{A,B\},\{B,C\},\{C,D\},\{A,D\}\}$.

  1. For each clique $c\in C$, $X_c$ represents the set of random variables in that clique. Similarly, $x_c$ is a particular assignment of values to those random variables.

  2. $p(a,b,c,d)$ is a valid MRF if and only if it factors over the cliques in the graph, i.e. it can be written in the form $$\begin{align*} p(a,b,c,d) & = \frac{1}{Z} \prod_{c \in C} \phi_c(x_c) \\ & = \frac{1}{Z} \phi_A(a)\phi_B(b) \phi_C(c)\phi_D(d)\phi_{A,B}(a,b)\phi_{B,C}(b,c)\phi_{C,D}(c,d)\phi_{A,D}(a,d). \end{align*} $$ In the example, they only assign "real" factors to the 2-member cliques: $$p(a,b,c,d) = \frac{1}{Z}\phi_{A,B}(a,b)\phi_{B,C}(b,c)\phi_{C,D}(c,d)\phi_{A,D}(a,d).$$ This is what is meant by the fact that not every clique must have a corresponding factor. (Note, however, that every factor must have a corresponding clique in the graph.) To reconcile this with the fact that the product ranges over every clique in $C$, we can simply consider the factors assigned to the singleton cliques $\{A\},\{B\},\{C\},\{D\}$ to be equal to 1. In this view, every clique has a factor, but only some have nontrivial factors.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.