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 supersedes 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 $26^{th}$ Conference of Uncertainty in Artificial Intelligence.

Furthermore, this package allows to construct the Gaussian rings of loopless mixed graphs (LMG) and the corresponding matrices of indeterminates as introduced in Kayvan Sadeghi and Steffen Lauritzen, Markov properties for mixed graphs, Bernoulli 20.2 (2014): 676-696.

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 \to 3, 4 \to 2, 3 \to 1, 2 \to 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       )                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         |
     |        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,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,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,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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |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 |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

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 and StatGraphs.m2. These packages allow 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.

The methods in GraphicalModels differ in the classes of acceptable graphs for input:

- functions used in package GraphicalModelsMLE (gaussianRing, covarianceMatrix, bidirectedEdgesMatrix, directedEdgesMatrix, directedEdgesMatrix, undirectedEdgesMatrix) and conditionalIndependenceIdeal accept Graph, Digraph, Bigraph and MixedGraph.

- conditional independence statement generators (pairMarkov, localMarkov and globalMarkov) accept only Graph or Digraph;

- the remaining functions that accepts graphs, only accept Graph, Digraph or MixedGraph without undirected edges.

Authors

Certification

Version 1.0 of this package was accepted for publication in volume 5 of 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.

Version

This documentation describes version 2.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 -- matrix corresponding to the bidirected edges of a bigraph or a mixed graph
- conditionalIndependenceIdeal -- ideal of a list of conditional independent statements
- covarianceMatrix -- covariance matrix of a Gaussian graphical model
- directedEdgesMatrix -- matrix corresponding to the directed edges of a digraph or a mixed graph
- discreteVanishingIdeal -- vanishing ideal of a discrete graphical model
- gaussianMatrices -- matrices whose minors generate the Gaussian conditional independence ideal
- gaussianParametrization -- parametrization of the covariance matrix in terms of treks
- gaussianRing -- ring of Gaussian correlations on n random variables or a graphical model
- gaussianVanishingIdeal -- 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 -- inverse of the marginMap
- localMarkov -- local Markov statements for a graph or a directed graph
- marginMap -- linear map on joint distributions for discrete random variables replacing marginals for indeterminates
- markovMatrices -- 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 -- trek separation ideal of a mixed graph
- trekSeparation -- trek separation statements of a mixed graph
- undirectedEdgesMatrix -- matrix corresponding to the edges of an undirected graph
Methods
- "bidirectedEdgesMatrix(Ring)" -- see bidirectedEdgesMatrix -- matrix corresponding to the bidirected edges of a bigraph or a mixed graph
- "conditionalIndependenceIdeal(Ring,List)" -- see conditionalIndependenceIdeal -- ideal of a list of conditional independent statements
- "conditionalIndependenceIdeal(Ring,List,List)" -- see conditionalIndependenceIdeal -- ideal of a list of conditional independent statements
- "covarianceMatrix(Ring)" -- see covarianceMatrix -- covariance matrix of a Gaussian graphical model
- "directedEdgesMatrix(Ring)" -- see directedEdgesMatrix -- matrix corresponding to the directed edges of a digraph or a mixed graph
- "discreteVanishingIdeal(Ring,Digraph)" -- see discreteVanishingIdeal -- vanishing ideal of a discrete graphical model
- "gaussianMatrices(Ring,List)" -- see gaussianMatrices -- matrices whose minors generate the Gaussian conditional independence ideal
- "gaussianParametrization(Ring)" -- see gaussianParametrization -- parametrization of the covariance matrix in terms of treks
- gaussianRing(Bigraph) -- ring of Gaussian correlations of a graphical model coming from a bigraph
- gaussianRing(Digraph) -- ring of Gaussian correlations of a graphical model coming from a digraph
- gaussianRing(Graph) -- ring of Gaussian correlations of a graphical model coming from an undirected graph
- gaussianRing(MixedGraph) -- ring of Gaussian correlations of a graphical model coming from a mixed graph
- gaussianRing(ZZ) -- ring of Gaussian correlations on n random variables
- "gaussianVanishingIdeal(Ring)" -- see gaussianVanishingIdeal -- vanishing ideal of a Gaussian graphical model
- "globalMarkov(Digraph)" -- see globalMarkov -- global Markov statements for a graph or a directed graph
- "globalMarkov(Graph)" -- see globalMarkov -- global Markov statements for a graph or a directed graph
- "hiddenMap(ZZ,Ring)" -- see hiddenMap -- linear map between the ring of a model with one hidden variable and the ring of the corresponding fully observed model
- "identifyParameters(Ring)" -- see identifyParameters -- solve the identifiability problem for Gaussian graphical models
- "inverseMarginMap(ZZ,Ring)" -- see inverseMarginMap -- inverse of the marginMap
- "localMarkov(Digraph)" -- see localMarkov -- local Markov statements for a graph or a directed graph
- "localMarkov(Graph)" -- see localMarkov -- local Markov statements for a graph or a directed graph
- "marginMap(ZZ,Ring)" -- see marginMap -- linear map on joint distributions for discrete random variables replacing marginals for indeterminates
- "markovMatrices(Ring,List)" -- see markovMatrices -- matrices whose minors form the ideal of a list of independence statements
- "markovMatrices(Ring,List,List)" -- see markovMatrices -- matrices whose minors form the ideal of a list of independence statements
- "markovRing(Sequence)" -- see markovRing -- ring of joint probability distributions on several discrete random variables
- "pairMarkov(Digraph)" -- see pairMarkov -- pairwise Markov statements for a graph or a directed graph
- "pairMarkov(Graph)" -- see pairMarkov -- pairwise Markov statements for a graph or a directed graph
- "trekIdeal(Ring,Digraph)" -- see trekIdeal -- trek separation ideal of a mixed graph
- "trekIdeal(Ring,Graph)" -- see trekIdeal -- trek separation ideal of a mixed graph
- "trekIdeal(Ring,MixedGraph)" -- see trekIdeal -- trek separation ideal of a mixed graph
- "trekSeparation(MixedGraph)" -- see trekSeparation -- trek separation statements of a mixed graph
- "undirectedEdgesMatrix(Ring)" -- see undirectedEdgesMatrix -- matrix corresponding to the edges of an undirected graph
Symbols
- Coefficients -- optional input to choose the base field
- compU -- key in hash table gaussianRingData: component of undirected edges in vertex set of a mixed graph
- compW -- key in hash table gaussianRingData: component of bidirected edges in vertex set of a mixed graph
- gaussianRingData -- hash table with main parameters of a gaussian ring
- graphType -- class of graph used to generate a gaussian ring
- kVar -- key in hash table gaussianRingData: labels of k variables
- kVariableName -- optional input to choose the variable names for concentration matrix in gaussianRing
- lVar -- key in hash table gaussianRingData: labels of l variables
- lVariableName -- optional input to choose the variable names for the regression matrix
- nn -- key in hash table gaussianRingData: total number of variables
- OldVersion -- optional argument in gaussianVanishingIdeal to use old method for gaussianRings coming from directed graphs
- pVar -- key in hash table gaussianRingData: labels of p variables
- pVariableName -- optional input to choose the variable names for the covariance matrix of the error terms
- SimpleTreks -- optional input for gaussianParametrization
- sVar -- key in hash table gaussianRingData: labels of s variables
- sVariableName -- optional input to choose the variable names for the covariance matrix
- VariableName -- optional input to choose indeterminate name in markovRing

For the programmer

The object GraphicalModels is a package.