A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models
A Polynomial-Time Algorithm for Deciding Markov Equivalence of Directed Cyclic Graphical Models
复制标题
判定有向循环图模型马尔可夫等价性的多项式时间算法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Richardson
中科院分区：
文献类型：
--
作者：
T. Richardson
尽管 d 分离的概念最初是为有向无环图定义的（参见 Pearl 1988），但该概念可以自然扩展到有向循环图。当两个有向图中存在完全相同的一组 d-分离关系时，无论是循环还是非循环，我们都说它们是马尔可夫等价的。换句话说，当两个有向循环图是马尔可夫等价时，满足全局有向马尔可夫条件（Lauritzen 等人，1990）自然扩展的分布集对于每个图来说是完全相同的。有一个明显的指数（以顶点数计）时间算法来确定两个有向循环图的马尔可夫等价；只需检查每个图中的所有 d 分离关系即可。在本文中，我提出了一个定理，该定理给出了两个有向循环图的马尔可夫等价的必要和充分条件，其中每个条件都可以在多项式时间内检查。因此，该定理可以很容易地适应多项式时间算法，用于确定两个有向循环图的马尔可夫等价性。尽管空间限制了正确性证明的包含，但它们在 Richardson (1994b) 中得到了充分的描述。
Although the concept of d-separation was originally defined for directed acyclic graphs (see Pearl 1988), there is a natural extension of the concept to directed cyclic graphs. When exactly the same set of d-separation relations hold in two directed graphs, no matter whether respectively cyclic or acyclic, we say that they are Markov equivalent. In other words, when two directed cyclic graphs are Markov equivalent, the set of distributions that satisfy a natural extension of the Global Directed Markov Condition (Lauritzen et al. 1990) is exactly the same for each graph. There is an obvious exponential (in the number of vertices) time algorithm for deciding Markov equivalence of two directed cyclic graphs; simply check all of the d-separation relations in each graph. In this paper I state a theorem that gives necessary and sufficient conditions for the Markov equivalence of two directed cyclic graphs, where each of the conditions can be checked in polynomial time. Hence, the theorem can be easily adapted into a polynomial time algorithm for deciding the Markov equivalence of two directed cyclic graphs. Although space prohibits inclusion of correctness proofs, they are fully described in Richardson (1994b).