Generalized Permutohedra from Probabilistic Graphical Models
© 2018 Society for Industrial and Applied Mathematics. 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 const...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135018 |
| _version_ | 1826194192356868096 |
|---|---|
| author | Mohammadi, Fatemeh Uhler, Caroline Wang, Charles Yu, Josephine |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Mohammadi, Fatemeh Uhler, Caroline Wang, Charles Yu, Josephine |
| author_sort | Mohammadi, Fatemeh |
| collection | MIT |
| description | © 2018 Society for Industrial and Applied Mathematics. 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. 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 and also for mixed graphical models containing undirected, directed, and bidirected edges, we give a construction of this polytope, up to equivalence of normal fans, 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. |
| first_indexed | 2024-09-23T09:52:22Z |
| format | Article |
| id | mit-1721.1/135018 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:52:22Z |
| publishDate | 2021 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1350182023-12-22T20:54:44Z Generalized Permutohedra from Probabilistic Graphical Models Mohammadi, Fatemeh Uhler, Caroline Wang, Charles Yu, Josephine Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Institute for Data, Systems, and Society © 2018 Society for Industrial and Applied Mathematics. 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. 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 and also for mixed graphical models containing undirected, directed, and bidirected edges, we give a construction of this polytope, up to equivalence of normal fans, 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. 2021-10-27T20:10:21Z 2021-10-27T20:10:21Z 2018 2019-07-09T17:55:00Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135018 en 10.1137/16M107894X SIAM Journal on Discrete Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Mohammadi, Fatemeh Uhler, Caroline Wang, Charles Yu, Josephine Generalized Permutohedra from Probabilistic Graphical Models |
| title | Generalized Permutohedra from Probabilistic Graphical Models |
| title_full | Generalized Permutohedra from Probabilistic Graphical Models |
| title_fullStr | Generalized Permutohedra from Probabilistic Graphical Models |
| title_full_unstemmed | Generalized Permutohedra from Probabilistic Graphical Models |
| title_short | Generalized Permutohedra from Probabilistic Graphical Models |
| title_sort | generalized permutohedra from probabilistic graphical models |
| url | https://hdl.handle.net/1721.1/135018 |
| work_keys_str_mv | AT mohammadifatemeh generalizedpermutohedrafromprobabilisticgraphicalmodels AT uhlercaroline generalizedpermutohedrafromprobabilisticgraphicalmodels AT wangcharles generalizedpermutohedrafromprobabilisticgraphicalmodels AT yujosephine generalizedpermutohedrafromprobabilisticgraphicalmodels |