Separating set
Topic of Graphical models, part of Statistical learning · Also in Graphical models
Separating set
| Type | Topic |
| Taught in | Graphical models · Graphical models |
| Part | Statistical learning |
A set S of vertices separates A from B in a graph when every path from A to B passes through S. The global Markov property says that then X_A and X_B are conditionally independent given X_S.
In Graphical models
From Graphical models
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.
- 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.
In Graphical models, continued
From Graphical models
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 · Graphical models
- Also used in Neural units
- All 8 questions on Graphical models
See also
Markov properties and factorisation · Conditional independence · Undirected graph · Hammersley–Clifford · A zero precision entry is conditional independence · Maximum likelihood for a known graph · Graphical lasso · Markov graphs