next | previous | forward | backward | up | top | index | toc | Macaulay2 web site

Markov -- Markov ideals, arising from Bayesian networks in statistics

Description

This package is used to construct ideals corresponding to discrete graphical models, as described in several places, including the paper: Garcia, Stillman and Sturmfels, "The algebraic geometry of Bayesian networks", J. Symbolic Comput., 39(3-4):331–355, 2005.

The paper also constructs Gaussian ideals, as described in the paper by Seth Sullivant: "Algebraic geometry of Gaussian Bayesian networks", Adv. in Appl. Math. 40 (2008), no. 4, 482--513.

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 4 --> 2,3 --> 1.
i1 : R = markovRing(2,2,2,2)

o1 = R

o1 : PolynomialRing
i2 : G = makeGraph{{},{1},{1},{2,3}}

o2 = Graph{1 => set {}    }
           2 => set {1}
           3 => set {1}
           4 => set {2, 3}

o2 : Graph
i3 : S = globalMarkovStmts G

o3 = {{{1}, {4}, {2, 3}}, {{2}, {3}, {4}}}

o3 : List
i4 : I = markovIdeal(R,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
Sometime an ideal can be simplified by changing variables. Very often, by using marginMap (missing documentation), such ideals can be transformed to binomial ideals. This is the case here.
i5 : F = marginMap(1,R)

o5 = 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

o5 : RingMap R <--- R
i6 : J = F I;

o6 : Ideal of R
i7 : netList pack(2,J_*)

     +-------------------------------------+-------------------------------------+
o7 = |- 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 is the one that has statistical significance. The significance of the other components is still poorly understood.
i8 : time netList primaryDecomposition J
     -- used 1.12883 seconds

     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
o8 = |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                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          |
     +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

Caveat

The parts of the package involving graphs might eventually be changed to use a package dealing specifically with graphs. This might change the interface to this package.

Authors

Version

This documentation describes version 1.2 of Markov.

Source code

The source code from which this documentation is derived is in the file Markov.m2.

Exports