Faster algorithms for Markov equivalence
Faster algorithms for Markov equivalence
复制标题
更快的马尔可夫等价算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
R. Evans
中科院分区：
文献类型：
--
作者：
Zhongyi Hu;R. Evans
最大祖先图（MAG）有许多理想的属性，特别是他们可以充分描述条件独立的有向无环图（DAG）在潜变量和选择变量的存在下。然而，不同的MAG可以对相同的条件独立性进行编码，并且被称为是等价的。因此，确定等价的必要和充分条件是结构学习的必要条件。这已经存在的几个标准，但在本文中，我们给出了一个新的非参数化的头部和尾部的离散模型的参数化方面的特征。我们还提供了一个多项式时间算法（$O（ne^{2}）$，其中$n$和$e$分别是顶点和边的数目）来验证等价性。此外，我们扩展我们的标准ADMG和摘要图，并提出了一个算法，转换ADMG或摘要图到一个等价的MAG在多项式时间（$O（n^{2}e）$）。因此，通过结合这两种算法，我们也可以验证两个汇总图或ADMG之间的等价性。
Maximal ancestral graphs (MAGs) have many desirable properties; in particular they can fully describe conditional independences from directed acyclic graphs (DAGs) in the presence of latent and selection variables. However, different MAGs may encode the same conditional independences, and are said to be emph{Markov equivalent}. Thus identifying necessary and sufficient conditions for equivalence is essential for structure learning. Several criteria for this already exist, but in this paper we give a new non-parametric characterization in terms of the heads and tails that arise in the parameterization for discrete models. We also provide a polynomial time algorithm ($O(ne^{2})$, where $n$ and $e$ are the number of vertices and edges respectively) to verify equivalence. Moreover, we extend our criterion to ADMGs and summary graphs and propose an algorithm that converts an ADMG or summary graph to an equivalent MAG in polynomial time ($O(n^{2}e)$). Hence by combining both algorithms, we can also verify equivalence between two summary graphs or ADMGs.
DOI：
--
发表时间：
2018-08
期刊：
Uncertainty in artificial intelligence : proceedings of the ... conference. Conference on Uncertainty in Artificial Intelligence
影响因子：
--
作者：
I. Shpitser;R. Evans;T. Richardson
通讯作者：
I. Shpitser;R. Evans;T. Richardson