论文标题
在定向无环图中快速因果方向学习
Fast Causal Orientation Learning in Directed Acyclic Graphs
论文作者
论文摘要
一组变量之间的因果关系通常由有向的无环图表示。因果DAG中某些边缘的方向可以从观察/介入数据中发现。可以通过迭代应用所谓的Meek规则来定位进一步的边缘。从一些以前的方向边缘推断边缘的方向，我们称之为因果方向学习（COL）是各种因果发现任务中的一个常见问题。在这些任务中，通常需要解决多个COL问题，因此应用温柔的规则可能很耗时。在Meek规则的激励下，我们介绍了可以用于解决COL问题的温柔功能。特别是，我们表明这些功能具有一些理想的属性，从而使我们能够加快应用温柔规则的过程。特别是，我们提出了一种基于动态编程（DP）的方法来应用温柔功能。此外，基于提出的DP方法，我们对由于干预而导致的边缘数量提出了一个下限。我们还提出了一种检查某些方向的边缘是否属于因果DAG的方法。实验结果表明，在运行时间方面，所提出的方法可以在几个因果发现任务中胜过以前的工作。
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.
