Generalized permutohedra from probabilistic graphical models

Mohammadi F, Uhler C, Wang C, Yu J. 2018. Generalized permutohedra from probabilistic graphical models. SIAM Journal on Discrete Mathematics. 32(1), 64–93.

Download (ext.)

Journal Article | Published | English
Author
Mohammadi, FatemehISTA; Uhler, CarolineISTA ; Wang, Charles; Yu, Josephine
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. SIAM. 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. SIAM, 2018. 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. SIAM, 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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

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

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar