论文标题
循环和环状因果模型的统一实验设计方法
A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
论文作者
论文摘要
我们研究实验设计，以识别简单SCM的因果图，该图可能包含周期。结构中的循环的存在引入了实验设计的主要挑战，因为与无环图不同，从观测分布中学习可能不可能学习具有周期的因果图的骨骼。此外，介入此类图中的变量并不一定会导致将所有偶然的边缘定向。在本文中，我们提出了一种实验设计方法，该方法可以学习循环图和无环图，因此可以统一两种图形的实验设计任务。我们提供了在最坏情况下保证因果图独特识别所需的实验数量的下限，这表明所提出的方法在实验数量上是最佳的订单 - 最高到添加剂对数项。此外，我们将结果扩展到每个实验的大小由常数界定的设置。对于这种情况，我们表明，在最坏情况下，我们的方法是唯一识别因果图所需的最大实验的大小。
We study experiment design for unique identification of the causal graph of a simple SCM, where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skeleton of causal graphs with cycles may not be possible from merely the observational distribution. Furthermore, intervening on a variable in such graphs does not necessarily lead to orienting all the edges incident to it. In this paper, we propose an experiment design approach that can learn both cyclic and acyclic graphs and hence, unifies the task of experiment design for both types of graphs. We provide a lower bound on the number of experiments required to guarantee the unique identification of the causal graph in the worst case, showing that the proposed approach is order-optimal in terms of the number of experiments up to an additive logarithmic term. Moreover, we extend our result to the setting where the size of each experiment is bounded by a constant. For this case, we show that our approach is optimal in terms of the size of the largest experiment required for uniquely identifying the causal graph in the worst case.
