论文标题
因果效应识别的实验设计
Experimental Design for Causal Effect Identification
论文作者
论文摘要
Pearl's Do Colculus是一种从观察数据中学习可识别的因果效应的完整公理方法。如果无法识别这种效果，则有必要在系统中执行经常昂贵的干预措施以学习因果效应。在这项工作中，我们考虑了设计干预措施收集的问题，并以最低成本确定所需的效果。首先，我们证明了这个问题是NP-HARD，随后提出了一种可以找到最佳解决方案或对数因子近似值的算法。这是通过建立我们的问题与最小击球设置问题之间的联系来完成的。此外，我们提出了几种多项式启发式算法来解决问题的计算复杂性。尽管这些算法可能会偶然发现亚最佳解决方案，但我们的模拟表明它们在随机图上产生了小的遗憾。
Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the causal effect. In this work, we consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic-factor approximation of it. This is done by establishing a connection between our problem and the minimum hitting set problem. Additionally, we propose several polynomial-time heuristic algorithms to tackle the computational complexity of the problem. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs.
