GraphicalModels -- a package for discrete and Gaussian statistical graphical models
Description
Graphical Models is a package for algebraic statistics. It constructs ideals of discrete and Gaussian graphical models. This package supercedes Markov.m2.
This package constructs ideals of discrete Bayesian networks (directed acyclic graphs) as described in several places, including the paper: Luis David Garcia, Michael Stillman and Bernd Sturmfels, The algebraic geometry of Bayesian networks, J. Symbolic Comput., 39(3-4):331--355, 2005.
It also constructs ideals of Gaussian Bayesian networks and Gaussian graphical models (graphs containing both directed and bidirected edges), as described in the papers: Seth Sullivant, Algebraic geometry of Gaussian Bayesian networks, Adv. in Appl. Math. 40 (2008), no. 4, 482--513; and Seth Sullivant, Kelli Talaska and Jan Draisma, "Trek separation for Gaussian graphical models", Annals of Statistics 38 no.3 (2010) 1665--1685.
The package also contains procedures to solve the identifiability problem for Gaussian graphical models as described in the paper: Luis D. Garcia-Puente, Sarah Spielvogel and Seth Sullivant, Identifying causal effects with computer algebra, Proceedings of the 26th Conference of Uncertainty in Artificial Intelligence.
Here is a typical use of this package. We create the ideal in 16 variables whose zero set represents the probability distributions on four binary random variables satisfying the conditional independence statements coming from the "diamond" graph 4 →3, 4 →2, 3 →1, 2 →1.
i1 : G = digraph {{1,{}},{2,{1}},{3,{1}},{4,{2,3}}}
o1 = Digraph{1 => {} }
2 => {1}
3 => {1}
4 => {2, 3}
o1 : Digraph
|
i2 : R = markovRing (2,2,2,2) -- this ring corresponds to four binary random variables o2 = R o2 : PolynomialRing |
i3 : S = globalMarkov G
o3 = {{{1}, {4}, {2, 3}}, {{2}, {3}, {4}}}
o3 : List
|
i4 : I = conditionalIndependenceIdeal (R,S); o4 : Ideal of R |
i5 : netList I_*
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
o5 = |- p p + p p |
| 1,1,1,2 2,1,1,1 1,1,1,1 2,1,1,2 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
|- p p + p p |
| 1,1,2,2 2,1,2,1 1,1,2,1 2,1,2,2 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
|- p p + p p |
| 1,2,1,2 2,2,1,1 1,2,1,1 2,2,1,2 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
|- p p + p p |
| 1,2,2,2 2,2,2,1 1,2,2,1 2,2,2,2 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
|- p p + p p + p p - p p - p p - p p + p p + p p |
| 1,1,2,1 1,2,1,1 1,1,1,1 1,2,2,1 1,2,2,1 2,1,1,1 1,2,1,1 2,1,2,1 1,1,2,1 2,2,1,1 2,1,2,1 2,2,1,1 1,1,1,1 2,2,2,1 2,1,1,1 2,2,2,1|
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
|- p p + p p + p p - p p - p p - p p + p p + p p |
| 1,1,2,2 1,2,1,2 1,1,1,2 1,2,2,2 1,2,2,2 2,1,1,2 1,2,1,2 2,1,2,2 1,1,2,2 2,2,1,2 2,1,2,2 2,2,1,2 1,1,1,2 2,2,2,2 2,1,1,2 2,2,2,2|
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
|
Sometimes an ideal can be simplified by changing variables. For example, conditional independence ideals are often transformed to binomial ideals by using marginMap. This is the case here.
i6 : F = marginMap (1,R)
o6 = map(R,R,{p - p , p - p , p - p , p - p , p - p , p - p , p - p , p - p , p , p , p , p , p , p , p , p })
1,1,1,1 2,1,1,1 1,1,1,2 2,1,1,2 1,1,2,1 2,1,2,1 1,1,2,2 2,1,2,2 1,2,1,1 2,2,1,1 1,2,1,2 2,2,1,2 1,2,2,1 2,2,2,1 1,2,2,2 2,2,2,2 2,1,1,1 2,1,1,2 2,1,2,1 2,1,2,2 2,2,1,1 2,2,1,2 2,2,2,1 2,2,2,2
o6 : RingMap R <--- R
|
i7 : J = F I; o7 : Ideal of R |
i8 : netList J_*
+-------------------------------------+
o8 = |- p p + p p |
| 1,1,1,2 2,1,1,1 1,1,1,1 2,1,1,2|
+-------------------------------------+
|- p p + p p |
| 1,1,2,2 2,1,2,1 1,1,2,1 2,1,2,2|
+-------------------------------------+
|- p p + p p |
| 1,2,1,2 2,2,1,1 1,2,1,1 2,2,1,2|
+-------------------------------------+
|- p p + p p |
| 1,2,2,2 2,2,2,1 1,2,2,1 2,2,2,2|
+-------------------------------------+
|- p p + p p |
| 1,1,2,1 1,2,1,1 1,1,1,1 1,2,2,1|
+-------------------------------------+
|- p p + p p |
| 1,1,2,2 1,2,1,2 1,1,1,2 1,2,2,2|
+-------------------------------------+
|
This ideal has 5 primary components. The first component is the one that has statistical significance. It is the defining ideal of the variety parameterized by the the factorization of the probability distributions according to the graph G. The remaining components lie on the boundary of the simplex.
i9 : netList primaryDecomposition J
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
o9 = |ideal (p p - p p , p p - p p , p p - p p , p p - p p , p p - p p , p p - p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p , p p p p - p p p p )|
| 1,2,2,2 2,2,2,1 1,2,2,1 2,2,2,2 1,2,1,2 2,2,1,1 1,2,1,1 2,2,1,2 1,1,2,2 2,1,2,1 1,1,2,1 2,1,2,2 1,1,1,2 2,1,1,1 1,1,1,1 2,1,1,2 1,1,2,2 1,2,1,2 1,1,1,2 1,2,2,2 1,1,2,1 1,2,1,1 1,1,1,1 1,2,2,1 2,1,1,1 2,1,2,2 2,2,1,2 2,2,2,1 2,1,1,2 2,1,2,1 2,2,1,1 2,2,2,2 1,1,1,1 2,1,2,2 2,2,1,2 2,2,2,1 1,1,1,2 2,1,2,1 2,2,1,1 2,2,2,2 1,1,2,2 2,1,1,1 2,2,1,2 2,2,2,1 1,1,2,1 2,1,1,2 2,2,1,1 2,2,2,2 1,1,1,1 1,1,2,2 2,2,1,2 2,2,2,1 1,1,1,2 1,1,2,1 2,2,1,1 2,2,2,2 1,2,1,2 2,1,1,1 2,1,2,2 2,2,2,1 1,2,1,1 2,1,1,2 2,1,2,1 2,2,2,2 1,1,1,1 1,2,1,2 2,1,2,2 2,2,2,1 1,1,1,2 1,2,1,1 2,1,2,1 2,2,2,2 1,2,2,2 2,1,1,2 2,1,2,1 2,2,1,1 1,2,2,1 2,1,1,1 2,1,2,2 2,2,1,2 1,1,2,1 1,2,2,2 2,1,1,2 2,2,1,1 1,1,2,2 1,2,2,1 2,1,1,1 2,2,1,2 1,2,1,1 1,2,2,2 2,1,1,2 2,1,2,1 1,2,1,2 1,2,2,1 2,1,1,1 2,1,2,2 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|ideal (p , p , p , p , p p - p p , p p - p p ) |
| 1,2,2,2 1,2,2,1 1,2,1,2 1,2,1,1 1,1,2,2 2,1,2,1 1,1,2,1 2,1,2,2 1,1,1,2 2,1,1,1 1,1,1,1 2,1,1,2 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|ideal (p , p , p , p , p p - p p , p p - p p ) |
| 1,2,1,2 1,2,1,1 1,1,1,2 1,1,1,1 1,2,2,2 2,2,2,1 1,2,2,1 2,2,2,2 1,1,2,2 2,1,2,1 1,1,2,1 2,1,2,2 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|ideal (p , p , p , p , p p - p p , p p - p p ) |
| 1,2,2,2 1,2,2,1 1,1,2,2 1,1,2,1 1,2,1,2 2,2,1,1 1,2,1,1 2,2,1,2 1,1,1,2 2,1,1,1 1,1,1,1 2,1,1,2 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|ideal (p , p , p , p , p p - p p , p p - p p ) |
| 1,1,2,2 1,1,2,1 1,1,1,2 1,1,1,1 1,2,2,2 2,2,2,1 1,2,2,1 2,2,2,2 1,2,1,2 2,2,1,1 1,2,1,1 2,2,1,2 |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|
The ideal in the next example corresponds to a Gaussian graphical model on a graph with directed and bidirected edges. The method trekIdeal computes the ideal based on the trek separation statements of the mixed graph.
i10 : G = mixedGraph (digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})
o10 = MixedGraph{Bigraph => Bigraph{a => {d}} }
d => {a}
Digraph => Digraph{b => {c, d}}
c => {d}
d => {}
Graph => Graph{}
o10 : MixedGraph
|
i11 : R = gaussianRing G o11 = R o11 : PolynomialRing |
i12 : J = trekIdeal (R,G); o12 : Ideal of R |
i13 : J / print; s a,b s a,c - s s + s s a,c b,b a,b b,c - s s + s s a,c b,b a,b b,c - s s + s s a,c b,c a,b c,c s s - s s a,c b,d a,b c,d |
The following ideal corresponds to a set of conditional statements of 5 Gaussian random variables.
i14 : R=gaussianRing 5 o14 = R o14 : PolynomialRing |
i15 : S={{{1},{2},{3,4}}, {{2,3},{1},{5}}}
o15 = {{{1}, {2}, {3, 4}}, {{2, 3}, {1}, {5}}}
o15 : List
|
i16 : I=conditionalIndependenceIdeal (R,S); o16 : Ideal of R |
i17 : I / print;
2
- s s s + s s s + s s s - s s - s s s + s s s
1,4 2,4 3,3 1,4 2,3 3,4 1,3 2,4 3,4 1,2 3,4 1,3 2,3 4,4 1,2 3,3 4,4
- s s + s s
1,3 2,5 1,2 3,5
- s s + s s
1,5 2,5 1,2 5,5
- s s + s s
1,5 3,5 1,3 5,5
|
The following people have generously contributed their time and effort to this project:
Alexander Diaz,
Shaowei Lin<http://math.berkeley.edu/~shaowei/>,
David Murrugarra<http://people.math.gatech.edu/~davidmur/Home.html>.
Caveat
GraphicalModels requires Graphs.m2. This package allows the user to create graphs whose vertices are labeled arbitrarily. However, several functions in GraphicalModels sort the vertices of the graph. Hence, graphs used as input to methods in GraphicalModels must have sortable vertex labels, e.g., all numbers or all letters.
Authors
Certification 
Version 1.0 of this package was accepted for publication in volume 5 of the journal The Journal of Software for Algebra and Geometry on 2013-03-05, in the article Graphical Models. That version can be obtained from the journal or from the Macaulay2 source code repository, http://github.com/Macaulay2/M2/blob/master/M2/Macaulay2/packages/GraphicalModels.m2, commit number 68f41d641fadb0a1054023432eb60177f1d7cbd9.
Version
This documentation describes version 1.0 of GraphicalModels.
Source code
The source code from which this documentation is derived is in the file GraphicalModels.m2.
Exports
-
Functions and commands
- bidirectedEdgesMatrix -- the matrix corresponding to the bidirected edges of a mixed graph
- conditionalIndependenceIdeal -- the ideal of a list of conditional independent statements
- covarianceMatrix -- the covariance matrix of a Gaussian graphical model
- directedEdgesMatrix -- the matrix corresponding to the directed edges of a mixed graph
- discreteVanishingIdeal -- the vanishing ideal of a discrete graphical model
- gaussianMatrices -- matrices whose minors generate the Gaussian conditional independence ideal
- gaussianParametrization -- the parametrization of the covariance matrix in terms of treks
- gaussianRing -- ring of Gaussian correlations on n random variables
- gaussianVanishingIdeal -- the vanishing ideal of a Gaussian graphical model
- globalMarkov -- global Markov statements for a graph or a directed graph
- hiddenMap -- linear map between the ring of a model with one hidden variable and the ring of the corresponding fully observed model
- identifyParameters -- solve the identifiability problem for Gaussian graphical models
- inverseMarginMap -- computes the inverse of the marginMap
- localMarkov -- local Markov statements for a graph or a directed graph
- marginMap -- generates a linear map on joint distributions for discrete random variables replacing marginals for indeterminates
- markovMatrices -- the matrices whose minors form the ideal of a list of independence statements
- markovRing -- ring of joint probability distributions on several discrete random variables
- pairMarkov -- pairwise Markov statements for a graph or a directed graph
- trekIdeal -- the trek separation ideal of a mixed graph
- trekSeparation -- the trek separation statements of a mixed graph
- undirectedEdgesMatrix -- the matrix corresponding to the edges of an undirected graph
-
Symbols
- Coefficients -- optional input to choose the base field
- kVariableName -- optional input to choose variable name for concentration matrix in gaussianRing
- lVariableName -- optional input to choose the variable name for the regression matrix
- pVariableName -- optional input to choose the variable name for the error covariance matrix
- SimpleTreks -- optional input for gaussianParametrization
- sVariableName -- optional input to choose the variable for the covariance matrix
- VariableName -- optional input to choose indeterminate name in markovRing