Seminar Details

Seminar Details


Apr 22

3:30 pm

On the Toric Algebra of Graphical Models

Chris Meek


Microsoft Research

We formulate necessary and sufficient conditions for an arbitrary discrete probability distribution to factor according to an undirected graphical model, or a log-linear model, or other more general exponential models. This characterization generalizes the well-known Hammersley-Clifford Theorem. We show that for decomposable graphical models these conditions are equivalent to a set of statistical independence facts as in the Hammersley-Clifford Theorem but that for non-decomposable graphical models they are not. We also show that non-decomposable models can have non-rational maximum likelihood estimates. Finally, using these results, we provide a characterization of decomposable graphical models.

[This is joint work with Dan Geiger and Bernd Sturmfels].