论文标题
马尔可夫等效的更快算法
Faster algorithms for Markov equivalence
论文作者
论文摘要
最大祖先图（MAG）具有许多理想的特性。特别是，在存在潜在和选择变量的情况下，它们可以完全描述有条件独立性从定向的无环图（DAG）。但是，不同的mag可以编码相同的条件独立性，据说是\ emph {Markov等效}。因此，确定等效的必要条件对于结构学习至关重要。已经存在几个标准，但是在本文中，我们根据离散模型的参数化中出现的头部和尾部给出了新的非参数表征。我们还提供一个多项式时间算法（$ O（ne^{2}）$，其中$ n $和$ e $分别是顶点和边缘的数量），以验证等效性。此外，我们将标准扩展到ADMG和摘要图，并提出了一种将ADMG或摘要图转换为多项式时间（$ 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.
