Hyperplane Representations of Interventional Characteristic Imset Polytopes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909183982436352 |
|---|---|
| author | Hollering, Benjamin Johnson, Joseph Solus, Liam |
| author_facet | Hollering, Benjamin Johnson, Joseph Solus, Liam |
| contents | Characteristic imsets are 0/1-vectors representing directed acyclic graphs whose edges represent direct cause-effect relations between jointly distributed random variables. A characteristic imset (CIM) polytope is the convex hull of a collection of characteristic imsets. CIM polytopes arise as feasible regions of a linear programming approach to the problem of causal disovery, which aims to infer a cause-effect structure from data. Linear optimization methods typically require a hyperplane representation of the feasible region, which has proven difficult to compute for CIM polytopes despite continued efforts. We solve this problem for CIM polytopes that are the convex hull of imsets associated to DAGs whose underlying graph of adjacencies is a tree. Our methods use the theory of toric fiber products as well as the novel notion of interventional CIM polytopes. Our solution is obtained as a corollary of a more general result for interventional CIM polytopes. The identified hyperplanes are applied to yield a linear optimization-based causal discovery algorithm for learning polytree causal networks from a combination of observational and interventional data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18500 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hyperplane Representations of Interventional Characteristic Imset Polytopes Hollering, Benjamin Johnson, Joseph Solus, Liam Combinatorics Statistics Theory 62E10, 62H22, 62D20, 62R01, 13P25, 13P10 Characteristic imsets are 0/1-vectors representing directed acyclic graphs whose edges represent direct cause-effect relations between jointly distributed random variables. A characteristic imset (CIM) polytope is the convex hull of a collection of characteristic imsets. CIM polytopes arise as feasible regions of a linear programming approach to the problem of causal disovery, which aims to infer a cause-effect structure from data. Linear optimization methods typically require a hyperplane representation of the feasible region, which has proven difficult to compute for CIM polytopes despite continued efforts. We solve this problem for CIM polytopes that are the convex hull of imsets associated to DAGs whose underlying graph of adjacencies is a tree. Our methods use the theory of toric fiber products as well as the novel notion of interventional CIM polytopes. Our solution is obtained as a corollary of a more general result for interventional CIM polytopes. The identified hyperplanes are applied to yield a linear optimization-based causal discovery algorithm for learning polytree causal networks from a combination of observational and interventional data. |
| title | Hyperplane Representations of Interventional Characteristic Imset Polytopes |
| topic | Combinatorics Statistics Theory 62E10, 62H22, 62D20, 62R01, 13P25, 13P10 |
| url | https://arxiv.org/abs/2404.18500 |