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>.
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.
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.
This documentation describes version 1.0 of GraphicalModels.
The source code from which this documentation is derived is in the file GraphicalModels.m2.