Experimental Design for Learning Causal Graphs with Latent Variables
Experimental Design for Learning Causal Graphs with Latent Variables
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Murat Kocaoglu;Karthikeyan Shanmugam;E. Bareinboim
中科院分区：
文献类型：
--
作者：
Murat Kocaoglu;Karthikeyan Shanmugam;E. Bareinboim
我们考虑使用干预措施学习具有潜在变量的因果结构的问题。我们的目标不仅是学习观察到的变量之间的因果图，而且是找到可能混淆可观察到的关系的未观察变量。我们的方法是阶段：我们首先学习可观察的图，即可观察变量之间的诱导图。接下来，我们将了解可观察图的潜在变量的存在和位置。我们提出了一种有效的随机算法，该算法可以使用O（d \ log^2 n）干预措施学习可观察的图，其中d是图的程度。我们进一步提出了一种有效的确定性变体，该变体使用O（log n + L）干预措施，其中L是图中最长的有向路径。接下来，我们提出了一种仅使用O（d^2 log n）干预措施的算法，该干预措施可以学习非粘附变量和相邻变量之间的潜在。虽然天真的基线方法需要O（n^2）干预措施，但我们的组合算法可以使用O（d log^2 n + d^2 log（n））干预来学习因果图。
We consider the problem of learning causal structures with latent variables using interventions. Our objective is not only to learn the causal graph between the observed variables, but to locate unobserved variables that could confound the relationship between observables. Our approach is stage-wise: We first learn the observable graph, i.e., the induced graph between observable variables. Next we learn the existence and location of the latent variables given the observable graph. We propose an efficient randomized algorithm that can learn the observable graph using O(d\log^2 n) interventions where d is the degree of the graph. We further propose an efficient deterministic variant which uses O(log n + l) interventions, where l is the longest directed path in the graph. Next, we propose an algorithm that uses only O(d^2 log n) interventions that can learn the latents between both non-adjacent and adjacent variables. While a naive baseline approach would require O(n^2) interventions, our combined algorithm can learn the causal graph with latents using O(d log^2 n + d^2 log (n)) interventions.