提出可验证因果边方向的发现方法,用证书标记每条边的可识别性。
Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound
- 为每条边生成可验证的可识别性证书,区分数据支持与假设依赖的方向
- 在四个真实数据集上仅需1+K次专家提问即可完全恢复因果图
- 设计五层识别机制和两类查询,适合需要高可信度因果推断的研究者
因果发现算法输出有向图,但无法区分由数据确定的方向与依赖假设的方向。在标准马尔可夫性和忠实性条件下,观测分布仅能确定一个马尔可夫等价类,类内边方向无法仅通过增加样本恢复,必须依赖函数约束或干预。本文提出连续数据上的观测因果发现协议,为每个候选边附带离散的不可能性证书:RESOLVED代码记录所依据的可识别性定理,IMPOSSIBLE代码记录失败模式及领域专家需回答的具体问题。扩展双变量级联为五个带门控的可识别性层级(LSNM、IGCI、Stein、MDL、PEIT),当预条件测试失败时选择弃权。引入两种预言机原语——元枢纽查询与节点子节点查询,联合证明任意有向无环图(DAG)可在1+K次专家交互内恢复,其中K为非叶节点数。在理想预言机假设下,该界在asia、sachs、child、alarm基准上精确达到。
原文摘要 · Abstract (English)
Causal-discovery algorithms return a directed graph, yet provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption. Under the standard Markov and faithfulness conditions, the observational distribution identifies only a Markov equivalence class; orientations within that class are not determined by the joint distribution and cannot be recovered from additional samples alone, but require either a functional restriction or an intervention. We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem under which the direction was committed, while an IMPOSSIBLE code records the failure mode together with the specific question a domain expert must answer to resolve it. The bivariate cascade is extended with five gated identifiability tiers LSNM, IGCI, Stein, MDL, and PEIT that abstain when their precondition test rejects. Two oracle primitives, the meta-hub query and the node-children query, jointly establish an upper bound of $1+K$ expert interactions sufficient to recover any DAG, where $K$ denotes the number of non-leaf vertices. Under an ideal-oracle assumption, the bound is met exactly on the asia, sachs, child, and alarm benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。