Generalized permutohedra from probabilistic graphical models

F. Mohammadi, C. Uhler, C. Wang, J. Yu, SIAM Journal on Discrete Mathematics 32 (2018) 64–93.


Journal Article | Published | English
Author
Abstract
A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations can be represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. We show that there is an analogous polytope for conditional independence relations coming from a regular Gaussian model, and it can be defined using multiinformation or relative entropy. For directed acyclic graphical models we give a construction of this polytope as a Minkowski sum of matroid polytopes. Finally, we apply this geometric insight to construct a new ordering-based search algorithm for causal inference via directed acyclic graphical models.
Publishing Year
Date Published
2018-01-01
Journal Title
SIAM Journal on Discrete Mathematics
Volume
32
Issue
1
Page
64-93
IST-REx-ID

Cite this

Mohammadi F, Uhler C, Wang C, Yu J. Generalized permutohedra from probabilistic graphical models. SIAM Journal on Discrete Mathematics. 2018;32(1):64-93. doi:10.1137/16M107894X
Mohammadi, F., Uhler, C., Wang, C., & Yu, J. (2018). Generalized permutohedra from probabilistic graphical models. SIAM Journal on Discrete Mathematics, 32(1), 64–93. https://doi.org/10.1137/16M107894X
Mohammadi, Fatemeh, Caroline Uhler, Charles Wang, and Josephine Yu. “Generalized Permutohedra from Probabilistic Graphical Models.” SIAM Journal on Discrete Mathematics 32, no. 1 (2018): 64–93. https://doi.org/10.1137/16M107894X.
F. Mohammadi, C. Uhler, C. Wang, and J. Yu, “Generalized permutohedra from probabilistic graphical models,” SIAM Journal on Discrete Mathematics, vol. 32, no. 1, pp. 64–93, 2018.
Mohammadi F, Uhler C, Wang C, Yu J. 2018. Generalized permutohedra from probabilistic graphical models. SIAM Journal on Discrete Mathematics. 32(1), 64–93.
Mohammadi, Fatemeh, et al. “Generalized Permutohedra from Probabilistic Graphical Models.” SIAM Journal on Discrete Mathematics, vol. 32, no. 1, SIAM, 2018, pp. 64–93, doi:10.1137/16M107894X.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar