GraphicalModels -- A package for discrete and Gaussian statistical graphical models

Description

This package extends Markov.m2. It is used to construct ideals corresponding to discrete graphical models, 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.

The package 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; Seth Sullivant, Kelli Talaska and Jan Draisma, "Trek separation for Gaussian graphical models", Annals of Statistics 38 no.3 (2010) 1665--1685.

Further, the package 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.

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 which satisfy the conditional independence statements coming from the "diamond" graph d --> c,b --> a.

i1 : G = digraph  {{a,{}},{b,{a}},{c,{a}},{d,{b,c}}}

o1 = Digraph{a => set {}    }
             b => set {a}
             c => set {a}
             d => set {b, c}

o1 : Digraph

i2 : R = markovRing (2,2,2,2)

o2 = R

o2 : PolynomialRing

i3 : S = globalMarkov G

o3 = {{{a}, {d}, {b, c}}, {{b}, {c}, {d}}}

o3 : List

i4 : I = markovIdeal(R,G,S)

o4 = ideal (- p       p        + p       p       , - p       p        +
               1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2     1,1,2,2 2,1,2,1  
     ------------------------------------------------------------------------
     p       p       , - p       p        + p       p       , -
      1,1,2,1 2,1,2,2     1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2   
     ------------------------------------------------------------------------
     p       p        + p       p       , - p       p        +
      1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2     1,1,2,1 1,2,1,1  
     ------------------------------------------------------------------------
     p       p        + p       p        - p       p        -
      1,1,1,1 1,2,2,1    1,2,2,1 2,1,1,1    1,2,1,1 2,1,2,1  
     ------------------------------------------------------------------------
     p       p        - p       p        + p       p        +
      1,1,2,1 2,2,1,1    2,1,2,1 2,2,1,1    1,1,1,1 2,2,2,1  
     ------------------------------------------------------------------------
     p       p       , - p       p        + p       p        +
      2,1,1,1 2,2,2,1     1,1,2,2 1,2,1,2    1,1,1,2 1,2,2,2  
     ------------------------------------------------------------------------
     p       p        - p       p        - p       p        -
      1,2,2,2 2,1,1,2    1,2,1,2 2,1,2,2    1,1,2,2 2,2,1,2  
     ------------------------------------------------------------------------
     p       p        + p       p        + p       p       )
      2,1,2,2 2,2,1,2    1,1,1,2 2,2,2,2    2,1,1,2 2,2,2,2

o4 : Ideal of R

i5 : netList pack(2,I_*)

     +-------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
o5 = |- p       p        + p       p                                                                                                                         |- p       p        + p       p                                                                                                                         |
     |   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2                                                                                                                  |   1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2                                                                                                                  |
     +-------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
     |- p       p        + p       p                                                                                                                         |- p       p        + p       p                                                                                                                         |
     |   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2                                                                                                                  |   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       |- 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|   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. Very often, by using marginMap such ideals can be transformed to binomial ideals. 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 : I = F I

o7 = ideal (- p       p        + p       p       , - p       p        +
               1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2     1,1,2,2 2,1,2,1  
     ------------------------------------------------------------------------
     p       p       , - p       p        + p       p       , -
      1,1,2,1 2,1,2,2     1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2   
     ------------------------------------------------------------------------
     p       p        + p       p       , - p       p        +
      1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2     1,1,2,1 1,2,1,1  
     ------------------------------------------------------------------------
     p       p       , - p       p        + p       p       )
      1,1,1,1 1,2,2,1     1,1,2,2 1,2,1,2    1,1,1,2 1,2,2,2

o7 : Ideal of R

i8 : netList pack(2,I_*)

     +-------------------------------------+-------------------------------------+
o8 = |- p       p        + p       p       |- p       p        + p       p       |
     |   1,1,1,2 2,1,1,1    1,1,1,1 2,1,1,2|   1,1,2,2 2,1,2,1    1,1,2,1 2,1,2,2|
     +-------------------------------------+-------------------------------------+
     |- p       p        + p       p       |- p       p        + p       p       |
     |   1,2,1,2 2,2,1,1    1,2,1,1 2,2,1,2|   1,2,2,2 2,2,2,1    1,2,2,1 2,2,2,2|
     +-------------------------------------+-------------------------------------+
     |- 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,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 and are still poorly understood.

i9 : netList primaryDecomposition I

     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
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,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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
     |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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

The following example illustrates the caveat below.

i10 : H = digraph {{d,{b,a}},{c,{}},{b,{c}},{a,{c}}}

o10 = Digraph{a => set {c}   }
              b => set {c}
              c => set {}
              d => set {a, b}

o10 : Digraph

i11 : T = globalMarkov H

o11 = {{{a}, {b}, {d}}, {{c}, {d}, {b, a}}}

o11 : List

i12 : J = markovIdeal(R,H,T);

o12 : Ideal of R

i13 : netList pack(2,J_*)

      +-------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
o13 = |- 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,1,1 2,1,1,1    1,2,2,1 2,1,1,1    1,2,1,1 2,1,2,1    1,2,2,1 2,1,2,1    1,1,1,1 2,2,1,1    1,1,2,1 2,2,1,1    1,1,1,1 2,2,2,1    1,1,2,1 2,2,2,1|   1,2,1,2 2,1,1,2    1,2,2,2 2,1,1,2    1,2,1,2 2,1,2,2    1,2,2,2 2,1,2,2    1,1,1,2 2,2,1,2    1,1,2,2 2,2,1,2    1,1,1,2 2,2,2,2    1,1,2,2 2,2,2,2|
      +-------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
      |- p       p        + p       p                                                                                                                         |- p       p        + p       p                                                                                                                         |
      |   1,1,1,2 1,1,2,1    1,1,1,1 1,1,2,2                                                                                                                  |   1,2,1,2 1,2,2,1    1,2,1,1 1,2,2,2                                                                                                                  |
      +-------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+
      |- p       p        + p       p                                                                                                                         |- p       p        + p       p                                                                                                                         |
      |   2,1,1,2 2,1,2,1    2,1,1,1 2,1,2,2                                                                                                                  |   2,2,1,2 2,2,2,1    2,2,1,1 2,2,2,2                                                                                                                  |
      +-------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------+

i14 : F = marginMap(3,R);

o14 : RingMap R <--- R

i15 : J = F J;

o15 : Ideal of R

i16 : netList pack(2,J_*)

      +-------------------------------------+-------------------------------------+
o16 = |- p       p        + p       p       |- p       p        + p       p       |
      |   1,2,1,1 2,1,1,1    1,1,1,1 2,2,1,1|   1,2,1,2 2,1,1,2    1,1,1,2 2,2,1,2|
      +-------------------------------------+-------------------------------------+
      |- p       p        + p       p       |- p       p        + p       p       |
      |   1,1,1,2 1,1,2,1    1,1,1,1 1,1,2,2|   1,2,1,2 1,2,2,1    1,2,1,1 1,2,2,2|
      +-------------------------------------+-------------------------------------+
      |- p       p        + p       p       |- p       p        + p       p       |
      |   2,1,1,2 2,1,2,1    2,1,1,1 2,1,2,2|   2,2,1,2 2,2,2,1    2,2,1,1 2,2,2,2|
      +-------------------------------------+-------------------------------------+

Note that the graph H is isomorphic to G, we have just relabeled the vertices. Observe that the vertices of H are stored in lexicographic order. Also note that the this graph isomorphism lifts to an isomorphism of ideals.

Caveat

This package requires Graphs.m2, as a consequence it can do computations with graphs whose vertices are not necessarily labeled by integers. This could potentially create some confusion about what does p_{i₁i₂…i_n} mean. The package orders the vertices lexicographically, so p_{i₁i₂…i_n} = p(X₁ = i₁, X₂ = i₂, …, X_n = i_n) where the labels X₁,X₂,…,X_n have been ordered lexicographically. Therefore, the user is encouraged to label the vertices in a consistent way (all numbers, or all letters, etc).

Authors

Version

This documentation describes version 0.1 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
- covarianceMatrix -- the covariance matrix of a gaussian graphical model
- directedEdgesMatrix -- the matrix corresponding to the directed edges of a mixed graph
- gaussianIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
- gaussianMatrices -- Matrices whose minors form the ideal corresponding to a conditional independence statements.
- gaussianParametrization -- the parametrization of the covariance matrix in terms of treks
- gaussianRing -- ring of gaussian correlations on n random variables
- globalMarkov -- Global Markov statements for a directed graph.
- hiddenMap -- Creates a linear map from a ring of probability distributions among observed discrete random variables into a ring of probability distributions among observed variables and one hidden variable specified by the integer input.
- identifyParameters -- solving the identifiability problem: expressing each parameter in terms of covariances
- localMarkov -- Local Markov statements for a directed graph.
- marginMap -- Generates a linear map on joint probabilities for discrete variables that replaces marginals for indeterminates.
- markovIdeal -- Ideal of constraints associated to a list of independent statements among discrete random variables.
- markovMatrices -- The matrices whose minors form the ideal associated to the list of independence statements of the graph.
- markovRing -- Ring of probability distributions on several discrete random variables.
- pairMarkov -- Pairwise Markov statements for a directed graph.
- trekIdeal -- the edge elimination ideal of a directed graph, or the trek separation ideal of a mixed graph
- trekSeparation -- the trek separation statements of a mixed graph
Symbols
- Coefficients -- Optional input to choose the base field.
- SimpleTreks -- optional input to choose the type of parametrization in @TO gaussianParametrization@
- VariableName -- Optional input to choose the letter for the variable name.