A Discovery Algorithm for Directed Cyclic Graphs
A Discovery Algorithm for Directed Cyclic Graphs
复制标题
有向循环图的发现算法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Richardson
中科院分区：
文献类型：
--
作者：
T. Richardson
有向无环图已经被卓有成效地用来表示因果结构（Pearl 1988）。然而，在社会科学和其他领域，经常使用的模型在因果关系和统计上都对应于有向循环的有向图（Spirtes 1995）。Pearl（1993）讨论了在这类模型中预测干预的效果，即所谓的线性非递归结构方程模型。这就提出了一个问题，即是否有可能从样本数据中推断出具有周期的因果结构。特别是是否存在一般的，翔实的，可行的和可靠的程序推断因果结构的条件独立的变量之间的关系，在一个未知的因果结构所产生的样本？在本文中，我提出了一个发现算法，这是正确的大样本限制，通常（但往往是隐含的）提出了合理的假设，并提供有关存在或不存在的因果路径从一个变量到另一个的信息。该算法是稀疏图上的多项式算法。
Directed acyclic graphs have been used fruitfully to represent causal structures (Pearl 1988). However, in the social sciences and elsewhere models are often used which correspond both causally and statistically to directed graphs with directed cycles (Spirtes 1995). Pearl (1993) discussed predicting the effects of intervention in models of this kind, so-called linear nonrecursive structural equation models. This raises the question of whether it is possible to make inferences about causal structure with cycles, from sample data. In particular do there exist general, informative, feasible and reliable procedures for inferring causal structure from conditional independence relations among variables in a sample generated by an unknown causal structure? In this paper I present a discovery algorithm that is correct in the large sample limit, given commonly (but often implicitly) made plausible assumptions, and which provides information about the existence or non-existence of causal pathways from one variable to another. The algorithm is polynomial on sparse graphs.