提出高效算法，快速找出因果效应的识别公式
Efficient Symbolic Computations for Identifying Causal Effects
- 基于符号计算构建低度识别公式的高效算法
- 在预设最大次数下，可准多项式时间求解识别公式
- 适合需要快速验证因果效应可识别性的研究者
在存在潜在混杂变量的情况下，从观测数据中判断因果效应是否可识别，是因果推断的核心挑战。对于线性结构因果模型，因果效应的可识别性可通过符号计算判定。然而，传统基于格罗伯纳基的方法因具有双重指数复杂度，在小规模场景外即不可行。本文研究如何实际应用符号计算来判断有理可识别性。我们提出一种高效算法，可严格找到最低次数的识别公式。对于感兴趣的因果效应，若存在指定最大次数的识别公式，该算法可在准多项式时间内返回该公式。
原文摘要 · Abstract (English)
Determining identifiability of causal effects from observational data under latent confounding is a central challenge in causal inference. For linear structural causal models, identifiability of causal effects is decidable through symbolic computation. However, standard approaches based on Gröbner bases become computationally infeasible beyond small settings due to their doubly exponential complexity. In this work, we study how to practically use symbolic computation for deciding rational identifiability. In particular, we present an efficient algorithm that provably finds the lowest degree identifying formulas. For a causal effect of interest, if there exists an identification formula of a prespecified maximal degree, our algorithm returns such a formula in quasi-polynomial time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。