Causal relationships among a set of variables are commonly represented by a directed acyclic graph. The orientations of some edges in the causal DAG can be discovered from observational/interventional data. Further edges can be oriented by iteratively applying so-called Meek rules. Inferring edges' orientations from some previously oriented edges, which we call Causal Orientation Learning (COL), is a common problem in various causal discovery tasks. In these tasks, it is often required to solve multiple COL problems and therefore applying Meek rules could be time-consuming. Motivated by Meek rules, we introduce Meek functions that can be utilized in solving COL problems. In particular, we show that these functions have some desirable properties, enabling us to speed up the process of applying Meek rules. In particular, we propose a dynamic programming (DP) based method to apply Meek functions. Moreover, based on the proposed DP method, we present a lower bound on the number of edges that can be oriented as a result of intervention. We also propose a method to check whether some oriented edges belong to a causal DAG. Experimental results show that the proposed methods can outperform previous work in several causal discovery tasks in terms of running-time.
翻译:一组变量之间的因果关系通常由定向环绕图代表。 从观测/干预数据中可以发现因果 DAG中某些边缘的定向。 进一步的边缘可以通过迭接应用所谓的Meek 规则来定位。 我们称之为Causal定向学习(COL),从一些以前面向的边缘推断边缘方向是各种因果发现任务中常见的一个问题。 在这些任务中,通常需要解决多种COL问题,因此适用Meek规则可能是耗时的。 根据Meek 规则,我们引入了可用于解决COL问题的Meek函数。特别是,我们显示这些功能具有一些可取的属性,使我们能够加快应用Meek 规则的进程。特别是,我们提议了一个基于Meek 功能的动态编程(DP) 方法。 此外,根据拟议的DP方法,我们对于可以作为干预结果的边缘数量提出了较低的约束。 我们还提出了一种方法来检查某些方向边缘是否属于因果的 DAG 。 实验结果显示, 在先前的因果发现任务中, 拟议的方法可以显示以前的因果性任务的形式。