Efficient Intervention Design for Causal Discovery with Latents
Efficient Intervention Design for Causal Discovery with Latents
复制标题
DOI：
--
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Raghavendra Addanki;S. Kasiviswanathan;A. Mcgregor;Cameron Musco
中科院分区：
文献类型：
--
作者：
Raghavendra Addanki;S. Kasiviswanathan;A. Mcgregor;Cameron Musco
我们考虑在存在潜在变量的情况下恢复因果图，在这种情况下，我们寻求将恢复过程中使用的干预成本降至最低。我们考虑了两个干预成本模型：(1)线性成本模型，其中对变量子集的干预成本具有线性形式；(2)身份成本模型，其中干预成本是相同的，无论它是什么变量，即目标只是最小化干预次数。在线性成本模型下，我们给出了一个算法来识别潜在因果图的祖先关系，从而在最优干预成本的$2倍内实现。在一些较温和的限制下，对于任何$\epsilon；>0$，这个近似因子都可以提高到$1+\epsilon$。在一致性成本模型下，我们通过一种特殊类型的对撞器，使用因果图的参数化来限制恢复包括潜在变量在内的整个因果图所需的干预次数。特别地，我们引入了$p$-碰撞器的概念，它是因果图中因特定类型的条件而产生的节点对之间的碰撞器，并提供了作为因果图中任意两个节点之间的$p$-碰撞器最大数目的函数的干预次数的上界。
We consider recovering a causal graph in presence of latent variables, where we seek to minimize the cost of interventions used in the recovery process. We consider two intervention cost models: (1) a linear cost model where the cost of an intervention on a subset of variables has a linear form, and (2) an identity cost model where the cost of an intervention is the same, regardless of what variables it is on, i.e., the goal is just to minimize the number of interventions. Under the linear cost model, we give an algorithm to identify the ancestral relations of the underlying causal graph, achieving within a $2$-factor of the optimal intervention cost. This approximation factor can be improved to $1+\epsilon$ for any $\epsilon > 0$ under some mild restrictions. Under the identity cost model, we bound the number of interventions needed to recover the entire causal graph, including the latent variables, using a parameterization of the causal graph through a special type of colliders. In particular, we introduce the notion of $p$-colliders, that are colliders between pair of nodes arising from a specific type of conditioning in the causal graph, and provide an upper bound on the number of interventions as a function of the maximum number of $p$-colliders between any two nodes in the causal graph.