论文标题
在特征IMSET多面体的边缘
On the Edges of Characteristic Imset Polytopes
论文作者
论文摘要
最近证明，特征性IMSET多层的边缘，$ \ operatatorName {cim} _p $，与因果发现具有很强的连接，因为许多算法都可以解释为贪婪的限制性边缘 - 尽管仅知道边缘的一个严格子集。为了更好地理解多层的一般边缘结构，我们用清晰的组合解释描述了面部的边缘结构：对于任何无向图$ g $，我们都有face $ \ operatotorname {cim} _g $，skeleton $ g $ dags的特征imsets的凸面。当$ g $是一棵树时，我们给出了$ \ permatatorname {cim} _g $的完整边缘描述，从而导致与其他多面体的有趣连接。特别是，当$ g $是一棵树时，可以作为$ \ operatatorName {cim} _g $的面孔恢复了良好的稳定套件。在此连接的基础上，当$ g $是一个周期时，我们还可以对$ \ operatorname {cim} _g $的所有边缘进行描述，这表明可能有可能进行概括。然后，我们介绍了一种从数据中学习定向树的算法，利用我们新发现的边缘，在模拟高斯数据上的经典方法优于经典方法。
The edges of the characteristic imset polytope, $\operatorname{CIM}_p$, were recently shown to have strong connections to causal discovery as many algorithms could be interpreted as greedy restricted edge-walks, even though only a strict subset of the edges are known. To better understand the general edge structure of the polytope we describe the edge structure of faces with a clear combinatorial interpretation: for any undirected graph $G$ we have the face $\operatorname{CIM}_G$, the convex hull of the characteristic imsets of DAGs with skeleton $G$. We give a full edge-description of $\operatorname{CIM}_G$ when $G$ is a tree, leading to interesting connections to other polytopes. In particular the well-studied stable set polytope can be recovered as a face of $\operatorname{CIM}_G$ when $G$ is a tree. Building on this connection we are also able to give a description of all edges of $\operatorname{CIM}_G$ when $G$ is a cycle, suggesting possible inroads for generalization. We then introduce an algorithm for learning directed trees from data, utilizing our newly discovered edges, that outperforms classical methods on simulated Gaussian data.
