Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

技术摘要：基于每边不可能性证书的迭代因果发现

问题陈述
当前的因果发现算法通常返回一个完全定向的有向无环图（DAG），但无法区分由数据识别出的边方向与算法为满足输出约束而强加的方向。在标准的马尔可夫条件和忠实性条件下，观测数据仅能识别马尔可夫等价类；不在 v-结构上的边方向由联合分布无法确定。现有方法要么在未可识别的边上强制定向（例如 NOTEARS、DAGMA），却缺乏诊断依据；要么将其保留为无向边（例如 FCI），却未指明解决它们所需的具体先验信息。此外，连续优化方法已被证明会利用数据伪影（例如变量排序性 varsortability）来模仿真实的识别结果。目前缺乏一种原则性协议，能够提供每边的可审计性，明确区分数据驱动的可识别性与算法强加性，并识别解决未可识别边所需的具体专家问题。

方法论
本文提出了一种针对连续数据观测因果发现的确定性三阶段协议。该协议在仅基于数据的骨架图中，为每个候选边发出离散的“不可能性证书”，将边分类为已解决（数据识别或中介）或不可能（数据不足，需要专家输入）。

1. 阶段 1：骨架与中介搜索

   • 使用 FDR 控制的 HSIC 检验构建骨架，剔除边际独立的变量对。
   • 执行多层级中介搜索，识别并剔除由观测变量中介的边。

2. 阶段 2：门控可识别性级联

   • 一个八层级的级联评估剩余边。层级包括经典方法（线性 ANM $L_0$、非线性 ANM $L_1$、高阶 HOC LiNGAM $L_2$）以及本文引入的五个新层级：LSNM（位置 - 尺度噪声）、IGCI（信息几何）、Stein（分数匹配）、MDL（算法马尔可夫条件）和PEIT（熵 - 反转检验）。
   • 门控机制：每个层级均以统计检验（如 Shapiro–Wilk 非高斯性检验、异方差性检验）为前提条件。如果某层级的先决条件未满足，则选择弃权而非强制定向。
   • 跨层级一致性：设置“分歧防护”机制，若更高精度的层级（IGCI、Stein、MDL）与 $L_0$ 的判定方向相矛盾，则降级 $L_0$ 的确认，将该边重标记为 impossible_l0_disagrees_with_high_tier。
   • 未被任何层级解决的边将获得 impossible_* 标签，该标签编码了具体的失败模式（例如潜在混杂、弱非线性）以及解决该问题所需的领域专家具体问题。

3. 阶段 3：针对性神谕查询

   • 该协议仅针对标记为 impossible_* 的边与领域专家进行交互。
   • 查询原语：
     • 每边查询：询问方向（前向 FWD/后向 BWD）或不存在。
     • 元枢纽查询：询问出度最高的前 $K$ 个节点。
     • 节点子节点查询：询问特定节点的直接子节点，同时确认所有出边。
   • 自动传播：每次神谕确认后，系统运行零成本的自动解析过程（无环性检查、Meek 规则、传递性 d-分离），在不进行额外查询的情况下解析更多边。

主要贡献

1. 每边证书：协议为每条边分配一个离散代码。resolved_* 代码引用证明方向的具体定理（例如 $L_{Stein}$），而 impossible_* 代码记录失败模式及解决该问题所需的具体问题。
2. 层级感知弃权：引入五个新的门控层级（LSNM、IGCI、Stein、MDL、PEIT），确保仅在满足特定可识别性定理时才确认方向。如果先决条件失败，系统将弃权而非强制一个可能虚假的定向。
3. $1+K$ 交互界限：本文建立了恢复任意真实 DAG 所需专家交互的信息论上限为 $1+K$，其中 $K$ 为非叶节点的数量。这是通过结合单次元枢纽查询（用于识别目标）与 $K$ 次节点子节点查询来实现的。
4. 针对性 elicitation：与可能请求完整拓扑序或广泛干预的主动学习方法不同，该协议仅隔离未可识别的边，并请求解决它们所需的具体信息。

实验结果
该协议在四个标准基准（Asia、Sachs、Child、Alarm）以及旨在对特定层级进行压力测试的合成数据上进行了评估。

• 理想神谕性能：在假设存在完美神谕的情况下，该协议在所有四个基准上均使用恰好 $1+K$ 次交互，以 Precision = Recall = F1 = 1.000 恢复了真实 DAG。
  • Alarm (V=37)：在 27 次交互中恢复了 46 条边。
  • Sachs (V=11)：在 8 次交互中恢复了 17 条边。
• 级联效能：在 Sachs 数据集上，仅靠级联就从数据中解决了 19 条真实边中的 5 条。当分歧防护机制激活时，新增的安全层级将方向精度从基础 $L_0$-$L_2$ 的 61.5% 提升至 66.7%。
• 层级特异性：合成压力测试证实，每个新层级在其原生机制下均具有正向精度（例如 LLSNM 在位置 - 尺度噪声下，LIGCI 在近确定性数据下），并在非机制数据上弃权（触发 0/40），从而防止假阳性。
• 帕累托前沿：在 Sachs 数据集上，该协议展示了查询数量与 F1 分数之间的权衡。仅使用“安全”方法（无神谕的级联）以 5 次查询实现了 F1=0.571，而完整协议使用 13 次查询实现了 F1=1.000（利用级联减少神谕负担）。

意义与主张
本文声称解决了因果发现中的一个根本性差距：当前方法无法区分数据识别的方向与算法强加的方向。通过为每条边附加“证书”，该协议提供了透明的审计轨迹。

• 理论贡献：$1+K$ 界限代表了主动因果发现中干预预算界限在 elicitation 侧的对应物，量化了在拥有专家知识时解决 DAG 所需的最小信息量。
• 实用价值：该协议允许从业者将专家精力 exclusively 集中在未可识别的边上，通过提出具体的、机制感知的问题而非原始边方向，从而降低认知负荷。
• 局限性：作者明确指出，当前范围仅限于连续变量；离散贝叶斯网络仅作为神谕层的鲁棒性检查。该协议假设存在完美神谕；处理有噪声或概率性的专家响应被确定为未来工作。此外，骨架构建阶段施加了召回率限制，因为初始 HSIC 检验剔除的边无法被恢复。

该工作并非旨在替代可扩展的连续优化或基于约束的方法，而是作为一种正交方法，优先考虑每边的可审计性，并通过针对性的、基于证书的查询来最小化专家 elicitation 的成本。