Markov graphs

Section of Graphical models, part of Statistical learning

Markov graphs

Type Section
Taught in Graphical models
Part Statistical learning

To say that a correlation is carried by a third variable, one needs names for paths and for the set of variables that every path must cross. Those names are the graph.

Graph terminology

Main article: Graph terminology

Definition 1 (Undirected graph) A graph G=(V,E) is a set of vertices, or nodes, V along with a set of edges E\subseteq V\times V joining pairs of vertices. Self-edges are excluded, and only undirected edges are considered: (j,k)\in E implies (k,j)\in E. Edges are listed in any convenient order of the pair, with the reverse understood to be present.

Article: Undirected graph →

  • Two connected vertices are adjacent. A graph is complete if every node is adjacent to every other node.
  • If A\subseteq V, the subgraph G_A=(A,E_A) has E_A=E\cap(A\times A): keep every edge for which both vertices are in A. A subset is complete if it induces a complete subgraph. A complete subset that is maximal with respect to inclusion is a clique: a complete subset that cannot be made into a larger complete subset by adding any vertex.
  • In an undirected graph, the boundary \mathrm{bd}(A) of a subset A is the set of vertices in V\setminus A that are adjacent to vertices in A. The closure of A is \mathrm{cl}(A)=A\cup\mathrm{bd}(A).
  • A path X_1,\ldots,X_k is a sequence of vertices joined in a sequence: X_i is adjacent to X_{i+1} for i=1,\ldots,k-1. A subset C\subseteq V is a (j,k)-separator if all paths from j to k intersect C. The set C separates A from B if it is a (j,k)-separator for every j\in A and k\in B.

In a graphical model each vertex represents a random variable, and an edge permits conditional dependence between its endpoints. In a minimal Gaussian concentration graph with nonzero precision entries on edges, the edge represents conditional dependence given all remaining variables. The absence of an edge indicates that the two variables are conditionally independent given the values of all the other variables. For many models the conditioning set is smaller than the full remainder, and the graph says which set.

The six-vertex graph used below has edges 12, 13, 23, 24, 34, 45, 46 and 56. Its cliques are \{1,2,3\}, \{2,3,4\} and \{4,5,6\}. Vertex 4 separates the left group \{1,2,3\} from vertices 5 and 6.

Conditional independence

Main article: Conditional independence

Conditional independence is a statement about the conditional distribution, not about the marginal correlation. If X,Y,Z are random variables with joint distribution P, then X is conditionally independent of Y given Z, written X\perp Y\mid Z, if for any measurable set A in the sample space of X there exists a conditional probability of A given Y and Z that is a function of Z alone. For discrete variables,

X\perp Y\mid Z \iff \mathbb{P}(X=x,Y=y\mid Z=z) =\mathbb{P}(X=x\mid Z=z)\,\mathbb{P}(Y=y\mid Z=z),

and when X,Y,Z have a joint density on a product measure,

\begin{aligned} X\perp Y\mid Z &\iff f_{XY\mid Z}(x,y\mid z)=f_{X\mid Z}(x\mid z)\,f_{Y\mid Z}(y\mid z)\\ &\iff f_{XYZ}(x,y,z)\,f_Z(z)=f_{XZ}(x,z)\,f_{YZ}(y,z), \end{aligned}

almost surely (for all z with f_Z(z)>0 if the densities are continuous). The following properties hold (Lauritzen, 1996).

  • If X\perp Y\mid Z then Y\perp X\mid Z.
  • If X\perp Y\mid Z and U=h(X) then U\perp Y\mid Z.
  • If X\perp Y\mid Z and U=h(X) then X\perp Y\mid (Z,U).
  • If X\perp Y\mid Z and X\perp W\mid (Y,Z) then X\perp (W,Y)\mid Z.

And X\perp Y\mid Z is equivalent to each of the following, almost surely, with f the density of its arguments:

\begin{aligned} f(x,y,z)&=f(x,z)\,f(y,z)/f(z),\\ f(x\mid y,z)&=f(x\mid z),\\ f(x,z\mid y)&=f(x\mid z)\,f(z\mid y),\\ f(x,y,z)&=g(x,z)\,h(y,z)\quad\text{for some }g,h,\\ f(x,y,z)&=f(x\mid z)\,f(y,z). \end{aligned}

The third line follows from the second, because f(x,z\mid y)=f(x\mid y,z)\,f(z\mid y). The factorisation f(x,y,z)=g(x,z)\,h(y,z) is the form that generalises to graphs. Also, if C separates A from B, then X_A\perp X_B\mid X_C for a graphical model with the global Markov property below.

Markov properties and factorisation

Main article: Markov properties and factorisation

Undirected graphical models are also known as Markov random fields. A probability measure on X may have any of the following properties with respect to a graph G.

  • Pairwise. For any pair of non-adjacent vertices j,k\in V, X_j\perp X_k\mid X_{V\setminus\{j,k\}}.
  • Local. For any vertex j\in V, X_j\perp X_{V\setminus\mathrm{cl}(j)}\mid X_{\mathrm{bd}(j)}.
  • Global. For any triple (A,B,S) of disjoint subsets of V such that S separates A from B, X_A\perp X_B\mid X_S.

The global property implies the local property, which implies the pairwise property. The reverse implications need additional conditions. They are not true for every distribution. To connect them, introduce factorisation. A distribution factorises over G when its density relative to a product measure can be written as a product of nonnegative functions, each involving only variables from a complete subset:

f(x)=\prod_{a\text{ complete}}\psi_a(x_a).

Without loss of generality the sets a can be limited to the cliques of G:

f(x)=\frac{1}{Z}\prod_{c\in\mathcal{C}}\psi_c(x_c),

where \mathcal{C} is the set of cliques, the \psi_c are the clique potentials (typically not densities), and Z is a normalising constant. The functions \psi_a are not unique: groups of them can be combined by multiplication. If the distribution factorises, it has the global Markov property.

Theorem 1 (Hammersley–Clifford) A probability distribution with positive and continuous density f with respect to a product measure satisfies the pairwise Markov property with respect to an undirected graph G if and only if it factorises according to G.

Article: Hammersley–Clifford →

Under the positivity assumptions of the theorem, factorisation and the global, local, and pairwise Markov properties coincide. Positivity matters: zeros in the support can break the implication from conditional-independence statements to factorisation. This is a statement about distributions. It is not an assertion that every fitting problem for every graphical model is convex. The Gaussian precision-matrix likelihood below is a specific convex optimisation problem after a change of sign.

Used in

See also

Undirected graph · Hammersley–Clifford · A zero precision entry is conditional independence · Maximum likelihood for a known graph · Graphical lasso · Graph terminology · Conditional independence · Markov properties and factorisation

Glossary and index