Markov properties and factorisation
Section of Graphical models, part of Statistical learning
Markov properties and factorisation
| Type | Section |
| Taught in | Graphical models |
| Part | Statistical learning |
| Questions using it | 1 |
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.
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
- Taught in Graphical models
- Questions that use it (1) — Cliques and separators
- All 8 questions on Graphical models
See also
Hammersley–Clifford · Separating set · Undirected graph · A zero precision entry is conditional independence · Maximum likelihood for a known graph · Graphical lasso · Markov graphs · Graph terminology