Macaulay2 » Documentation
Packages » Markov :: Markov
next | previous | forward | backward | up | index | toc

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 0.836364 seconds

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

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

  • Luis David Garcia Puente
  • Mike Stillman

Version

This documentation describes version 1.3 of Markov.

Source code

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

Exports

  • Types
    • Graph (missing documentation)
  • Functions and commands
    • displayGraph (missing documentation)
    • gaussIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
    • gaussMinors (missing documentation)
    • gaussRing -- ring of gaussian correlations on n random variables
    • gaussTrekIdeal (missing documentation)
    • globalMarkovStmts (missing documentation)
    • hideMap (missing documentation)
    • localMarkovStmts (missing documentation)
    • makeGraph (missing documentation)
    • marginMap (missing documentation)
    • markovIdeal (missing documentation)
    • markovMatrices (missing documentation)
    • markovRing -- ring of probability distributions on several discrete random variables
    • pairMarkovStmts (missing documentation)
    • removeRedundants (missing documentation)
    • writeDotFile (missing documentation)
  • Methods
    • gaussIdeal(Ring,Graph) -- see gaussIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
    • gaussIdeal(Ring,List) -- see gaussIdeal -- correlation ideal of a Bayesian network of joint Gaussian variables
    • gaussRing(ZZ) -- see gaussRing -- ring of gaussian correlations on n random variables
  • Other things
    • dotBinary (missing documentation)

For the programmer

The object Markov is a package.