Local Causal Discovery With Background Knowledge¶

作者: Qingyuan Zheng, Yue Liu, Yangbo He
来源: IEEE Transactions on Pattern Analysis and Machine Intelligence
主题: 因果推断
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

本方向研究的是局部因果发现问题。与传统的全局因果发现（学习整个因果图）不同，局部因果发现的目标是：仅基于观测数据的局部结构，判断两个特定变量之间是否存在因果关系（以及方向），而不必学习完整的因果图。这个子方向的核心问题是在马尔可夫等价类（多个图与数据分布兼容）中，利用局部信息（如目标变量的邻居）来确定因果关系的可识别性。当前，该方向的主要瓶颈在于：在没有额外信息（如背景知识）时，局部结构能确定的因果关系非常有限（通常仅限于直接邻居），大量的因果方向在等价类中无法被区分。

发展脉络 (history)¶

奠基工作（全局因果发现）：Spirtes, Glymour, 和 Scheines (1993, 2000) 提出的 PC 算法 是开创性工作。它基于条件独立性测试，从完全图中逐步删除边，并依据 V-结构确定边方向，最终输出一个完全部分有向无环图 (CPDAG)，它代表了与观测数据分布兼容的所有 DAG 的马尔可夫等价类。这是之后所有工作（包括局部方法）的基准。留下口子： 该算法需要学习完整的因果图，计算复杂度高（在最坏情况下随变量数指数增长），且要求对整个变量集进行条件独立性测试。
主要进展（局部因果发现兴起）：Yin et al. (2008) 提出了 局部结构学习 的核心思想——不学习全局的 CPDAG，而是只学习目标变量（X）及其附近节点（如它的邻居、配偶、邻居的邻居等）构成的局部结构，并证明这个局部结构足以推断 X 与其他变量间的某些因果关系。他们的方法首次将等价类分析从全局缩小到了局部。留下口子： 该方法没有考虑任何背景知识，因此其识别结论仍然受限于局部等价类中的不确定方向。作者在引言中指出，其识别条件在数据非忠信假设下可能不成立。
当前 Frontier（背景知识集成）：
- 背景知识的类型与利用：Meek (1995) 的工作是经典基础，它提出了利用已知的因果方向（如从背景知识或干预实验得知）来缩小 CPDAG 的规则（即 Meek 规则），最终得到最大化部分有向无环图 (MPDAG)。Ambrogioni et al. (2021) 证明了在已知部分祖先关系时，如何通过修改条件独立性测试来学习 DAG。留下口子： 这些工作主要面向全局结构，不讨论局部识别。
- 本文的兴起：本文将这两种思路（局部发现 + 背景知识）结合。作者 Fang et al. (2018) 曾提出过局部结构的背景知识概念，但只限于情况下的因果不变性分析。而本文则系统性地讨论了不同类型背景知识（直接因果、非祖先、祖先信息）下的局部结构学习与因果识别问题，并给出了充要条件。

子线索聚类¶

全局结构学习（算法流程）：PC 算法 (Spirtes et al., 2000)、Fast Causal Inference (FCI) 算法 (Spirtes et al., 2000) 等。这类方法输出 CPDAG 或 PAG（部分祖先图）。目标：恢复图结构。瓶颈：计算花费大，无法用于高维变量集，且只关注可观测数据。
局部结构学习（因果推断）：Yin et al. (2008)、Fang et al. (2018) 等。目标：仅基于目标变量的“马尔可夫毯”（邻居、配偶等）来识别局部关系。瓶颈：等价类内的方向未解决。
背景知识集成（先验信息整合）：Meek (1995)、Ambrogioni et al. (2021)、本文作者等。目标：将部分已知的因果信息（如来自专家知识、干预实验）嵌入学习过程，以减少等价类，提升可识别性。瓶颈：如何将背景知识有效整合到局部框架中，并且不破坏局部推断的灵活性。

这个方向在追问的核心问题（2-4 个）¶

可识别性条件：在给定一种或几种背景知识后，局部结构能保证什么类型的因果关系（因/非因、直接原因、祖先关系等）“在每一个等价图中”都成立？这等价于问：什么样的局部结构配置，再加上特定的背景知识，足以唯一确定目标两个变量间的因果取向。
学习算法的实际表现：在有限样本和非忠信假设（真实图不满足DAG对应的条件独立关系）下，局部结构的精确学习有多难？背景知识的加入是稳定了算法还是引入了噪声？
稀疏性与样本复杂度：当局部结构（如邻居数量）与总变量集大小之间的比例如何时，局部推断依然是增益？即，它的统计-计算上的收益与代价的边界在哪里。

⚠️ 作者的 framing¶

作者将缺口定义为：“当前基于局部结构识别因果关系的方法（如 Yin et al. 2008）不支持利用任何背景知识，而背景知识在现实世界中很常见（如已知部分因果路径、非祖先信息）”。因此，作者将本文定位为 “直觉的下一步” — 将局部发现扩展到可容纳背景知识的设定，并给出了完整的识别理论（充要条件）。

被淡化/回避的竞争路线：作者在引言中没有提及全局方法（如 PC 算法）在利用背景知识时的扩展。例如，Meek (1995) 提出的从CPDAG到MPDAG的算法，本质上也是利用背景知识来“收紧”图结构。但作者将讨论严格限制在局部场景下，从而回避了与全局方法的对比——全局方法可能依然能为局部关系提供更一致的推断（例如，当局部结构学习不完整时）。什么明显该被引/该存在、却没出现在 intro 里？ “对于高维设定，局部方法中条件独立性测试的p值调整方法”是一个方法论上的空白。类似工作 (Zhang & Spirtes, 2018) 在因果发现的一般性文献中有，但未在本文中被引用。

张力¶

未见明显对立引用。已有文献中，对“非忠信”假设的担忧是共识，但本工作的定理假设忠信性成立。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
- \(G\): 真实的、未知的有向无环图 (DAG)。
- \(V\): 所有变量的集合。
- \(X, Y\): 两个目标变量，我们想知道它们之间直接的因果关系。\(X\) 是因，\(Y\) 是果。
- \(Pa(G)\): \(G\) 中所有有向边的父节点。
- \(An(Y)\): \(Y\) 的祖先集。
- \(\mathcal{M}\)：与观测数据 \(P(V)\) 兼容的所有 DAG 的集合（即马尔可夫等价类）。
- \(n\): 样本量。
- \(L_T(X,Y)\): 研究者从数据中学习到的局部结构，这是以变量 \(X\) 为中心的子图（包含其邻居、配偶及其之间的边）。这是模型的核心输出。
- \(B\): 背景知识集。它可以是：\(D\)（直接因果方向，如 \(A \to B\)），\(N\)（非祖先信息，如 \(A\) 不是 \(B\) 的祖先），\(A\)（祖先信息，如 \(A\) 是 \(B\) 的祖先）。在实际中，我们假设 \(B\) 是已知的。
- 可观测数据：独立同分布样本数据 \(D = \{v^1, v^2, ..., v^n\}\)，每个 \(v^i\) 是 \(V\) 的一个实现。无法观测 \(G\) 本身（未知的因果机制）。
- 重要概念：忠信性 (Faithfulness)：假设真实 DAG \(G\) 的 \(d\)-分离性质与观测数据 \(P(V)\) 中的条件独立性质之间一一对应。
- 重要概念：马尔可夫等价类：一组链图和其方向。
- 目标量（Estimand）：变量 \(X\) 是不是 \(Y\) 的一个因 (cause)？即，在给定的等价类 \(\mathcal{M}\) 中，是否所有图形都有 \(X \in An(Y)\)？或者 \(X\) 不是 \(Y\) 的一个因 (non-cause)？即，是否所有图形都有 \(X \notin An(Y)\)？

第二步：讲最小内核¶

考虑最简单的场景：两个变量 \(A\) 和 \(B\)，以及一个包含所有变量的背景知识：已知 \(A\) 不是 \(B\) 的祖先 (即，\(A \notin An(B)\))。

最简例子： 假设 \(V = \{A, B, C\}\)。真实 \(G\) 是 \(A \rightarrow C \leftarrow B\) (即 V-结构：\(A, B\) 是 \(C\) 的父节点，且它们之间没有边)。我们拥有背景知识 \(B = \{A \notin An(B)\}\)。研究者只关心 \(A\) 和 \(B\) 之间的关系。
站在局部视角：我们只学习与 \(A\) 直接相关的局部结构（即邻居和 \(C\) 和 \(B\) 之间的关系）。在 \(L_T(A, B)\) 中，如果我们看到 \(B\) 和 \(A\) 之间没有直接边，而 \(C\) 同时连接 \(A\) 和 \(B\)，但没有检测到 \(C\) 是 \(A\) 的配偶（即，\(A\) 和 \(B\) 关于 \(C\) 的碰撞性质没有揭示出来），那么在没有背景知识时，我们只能说这个局部等价类包含两种可能性：\(A \rightarrow C \leftarrow B\) 与 \(A \leftarrow C \rightarrow B\)。前者意味着 \(A\) 是 \(C\) 的祖先；后者意味着 \(A\) 不是 \(C\) 的祖先。
引入背景知识后的推断：因为我们已知 \(A\) 不是 \(B\) 的祖先（\(A \notin An(B)\)），在局部等价类中唯一可能的图形是 \(A \rightarrow C \leftarrow B\) （因为第二个图 \(A \leftarrow C \rightarrow B\) 会使得 \(A\) 通过 \(C\) 成为 \(B\) 的祖先，违反已知）。于是，我们能够断定：\(A\) 是 \(C\) 的一个因（\(C\) 的直接原因之一）。而且，\(A\) 不是 \(B\) 的一个因（由于背景知识直接限定，它也间接保护了这个结论）。
最小内核的核心思路：背景知识可以看作是对因果世界的部分约束——它强制某些因果路径不能存在（如非祖先信息），从而排除马尔可夫等价类中的部分图形。当这种排除恰好对应局部结构中的关键不确定取向时，我们就能唯一地确定一个因果方向。本文的一般化定理就是：什么样的局部结构，加上什么样的背景知识，保证我们可以唯一断定 \(X\) 是还是不是 \(Y\) 的原因。

三、这篇论文做了什么¶

三句话¶

研究的问题：在因果图模型框架下，本文研究如何在存在背景知识（已知部分直接因果、非祖先、祖先关系）时，仅通过学习局部结构（而非全局图）来识别两个变量之间是否是因果关系（是否为一个因或非因）。
核心工具/方法：提出了一种融合背景知识的局部结构学习算法（BG-LSL），该算法在目标变量 \(X\) 的马尔可夫等价类邻域上进行结构学习，并将背景知识作为约束条件，更新局部结构。在此基础上，给出了在背景知识和局部结构下，判断因果关系的充分必要条件（定理 3 和 4）。
主要结论：
- 提出了整合三种类型背景知识（直接因果、非祖先、祖先）的局部结构学习算法（BG-LSL）。
- 给出了在存在背景知识时，仅基于局部结构就能判断一个变量是另一个变量的因、非因的充要条件（这些条件由局部结构中特定的子图模式描述）。
- 实验表明，该方法在局部结构学习的准确性和效率上均优于不使用背景知识的基线方法（如 Yin et al. 2008 的方法），并能成功应用于公平机器学习中识别敏感变量的因果角色。

关键设定与假设¶

基本设定：假设数据是由一个忠实且马尔可夫的 DAG 产生的。变量集有限，假设忠信性（真实的图结构由条件独立性唯一决定）。
背景知识假设：背景知识来源于外部（如专家知识、干预实验）。作者假设背景知识是完全正确的（即与真实图一致）。这在真实应用中通常是可能的（如已知的干预实验结论），但若不正确，则推断结论全部失效。
局部结构定义：与 Yin et al. (2008) 一致，局部结构学习是指学习目标变量 \(X\) 的“马尔科夫毯等价类”（Markov Blanket Equivalence Class, MBEC），包括 \(X\) 的邻居、配偶、以及这些邻居和配偶组成的子图。在本文的算法 BG-LSL 中，这个过程被扩展为：在已知背景知识下，进行条件独立性测试，并结合规则处理。
与已有文献的比较：相比 Yin et al. (2008) 放宽了使用背景知识这一限制（之前完全不考虑背景知识）。相比 Meek (1995) 等全局方法，强化了局部性假设：只使用局部结构（而非全局图）即可得到结论。

主要结果 (理论型)¶

定理 1 (局部结构学习的一致性)：若数据满足忠信性与马尔可夫性，并且样本量趋于无穷，算法 BG-LSL 能渐近一致地学习到融合了背景知识的局部结构图。直觉： 当背景知识正确时，条件独立性测试会排除不兼容的边，背景知识进一步排除某些方向，最终输出一个与真实图兼容的局部部分有向无环图 (Local PPDAG)。必要条件： 背景知识必须与真实图一致。
定理 2 (直接因果背景知识下的必要条件)：设背景知识包含一个已知的直接因果关系 \(S_1 \to S_2\)。那么，在忠信性与马尔可夫性下，\(X\) 是 \(Y\) 的一个原因（即 \(X \in An(Y)\)）的必要条件是：在局部结构中，\(X\) 和 \(Y\) 之间存在一条有向路径（由局部结构中的某些边连接）或者存在特定的局部子图模式（如 V-结构或链结构）。直觉： 背景知识 \(S_1 \to S_2\) 相当于在全局图中增加了一条强制的有向边，它可以通过Meek 规则传递到局部结构中，改变局部图中某些边的方向，从而影响到目标路径存在性的判断。解决的技术困难： 如何精确刻画这种全局背景知识对局部结构的“收紧效应”，且不丢失局部性。证明路线使用了图论中关于有向边传播的规则分析。
定理 3 (因果识别条件)：给出在存在一个非祖先背景知识 \(M\) (已知 \(M\) 不是 \(Y\) 的祖先)下，判断 \(X\) 是否是 \(Y\) 原因充分必要条件。条件涉及满足局部子图模式：如果在局部结构中，\(X\) 与 \(M\) 之间存在一条通路径（由无向或有向边构成），且 \(M\) 与 \(Y\) 之间没有直接边，并且这条路径上的所有其他节点都满足特定方向模式（即，都没有指向 \(X\) 或 \(M\) 的指向性冲突，等等），那么 \(X\) 是 \(Y\) 的一个因。直觉： 已知的非祖先关系 \(M \notin An(Y)\) 强制排除了任何使得 \(M\) 能成为 \(Y\) 祖先的图结构。如果局部结构迫使 \(X\) 和 \(Y\) 必须通过 \(M\) 产生因果关系，则 \(X\) 就不能在不违反非祖先关系的情况下成为 \(Y\) 的原因。这个条件可以反过来用于识别 \(X\) 为非因。技术难点： 证明这类条件在任意局部结构中都是充要的，而不只是充分条件。证明通过构造反例（即，如果条件不成立，存在一个与局部结构兼容但与背景知识不冲突的图，使 \(X\) 变成 \(Y\) 的非因）来完成。这是该论文的关键技术贡献。

证明路线与技术技巧¶

整体路线：论文的证明可以分为两大步骤：
1. 局部结构学习（算法设计 + 一致性证明）： 将标准局部学习算法（Yin et al. 2008）作为骨架，在每一步条件独立性测试后，增加一个“背景知识更新”模块。该模块判断当前局部图与已知背景知识是否兼容，如果不兼容，则根据 Meek 规则施加方向，从而输出一个唯一的 Local PPDAG。一致性由经典的稳定性测试理论+背景知识的一致性保证。
2. 因果识别（充要条件刻画）：
  - 第一步：定义模式。 将局部等价类中所有可能的方向，通过一组流形/模式（patterns） 进行归纳（例如，有向路径、V-结构、链结构）。
  - 第二步：模式投影。 将已知背景知识（如非祖先信息）投影到局部结构上，给出消除某些模式的条件。
  - 第三步：充要模式。 对每种背景知识（直接因果、非祖先、祖先），证明局部结构存在特定模式是【在所有等价图中都成立“X是Y因/非因”】的充要条件。
关键跳跃点：
- 最难的部分是将全局背景知识（如“M不是Y的祖先”）的推论精确限制到局部结构的分析中，而不需依赖全局图的信息。例如，命题“已知M不是Y的祖先”，在什么情况下会影响X的因果属性？作者通过分析“M-X-Y”路径的结构，证明了只有在M与X之间在局部图中有一条特定的路径模式时，该背景知识才“传递”到X-Y的关系上。这个传递的唯一性证明是技术核心。
技术技巧点名：
- Meek 规则 (定向传播规则)： 用于根据已知的背景知识（A→B）推导出其他边的方向，从而收紧局部结构。特别是R1-R4规则（如R1：若A→B-C，且无方向边B←C，则B→C）。
- 模式消去 (Pattern Elimination)： 通过构造Counterexample Graph（一个同时符合局部结构、背景知识以及不满足条件的因果关系假设的图）来证明充分性。这是证明充要条件的经典手法（类似在因果推断中证明d-分离的充分必要性构造一个反例图）。

真实例子与应用¶

应用的场景与数据：论文使用 公平机器学习 (Fair Machine Learning) 场景来展示方法。任务是在一个包含种族、教育、收入、职业等变量的数据集中，识别敏感变量（如种族、年龄）与决策变量（如是否通过贷款、薪资）之间的因果角色。作者使用UCI的Adult数据集和一个基于UCI Census收入数据构造的公平性数据集。
如何应用：
- 步骤 1 (背景知识设置)：作者假设一些已知的常识性背景知识，例如已知“种族不是一个人的学历的因”（非祖先背景知识）。这符合现实：种族通常不会导致学历，但可能关联。注意：这是统计模型上的一个假设，与实际因果争论无关。
- 步骤 2 (局部结构学习)：算法 BG-LSL 学习敏感变量（如种族）和结果变量（如收入）周围的局部结构。例如，算法会学习到敏感变量的邻居（可能是教育、职业等）。
- 步骤 3 (因果识别)：利用定理 3/4 中的条件，算法识别出：种族是否是收入的一个因、一个非因、还是不确定。
结果：
- 比喻：在使用“种族不是学历的因”这个非祖先背景知识后，模型能够断定：种族是收入的因（即，在等价类中的所有图中，种族都是收入的祖先之一），但不一定是收入的直接原因（可能通过教育或职业）。这个结论是纯基于局部结构（种族及其直接邻居）推断出来的，不需要学习种族与所有其它变量关系的全局图。
- vs. 基线：如果不使用背景知识（仅使用 Yin et al. 2008 的方法），在该数据集的某些设定下，种族和收入之间的因果关系可能标为“不确定”（在等价类中有方向相反的图存在）。背景知识的加入消除了这些不确定图，使得可以得出有方向性的结论。论文还报告了在多个模拟和真实数据集上，融合背景知识后，因果关系的识别率（即可以得出明确的因/非因结论的变量对比例）显著提升，而错误率（违反已知背景知识的图被错误纳入）控制为零。
这个例子想说明什么：它想说明，对于公平性分析这类重要应用，背景知识（哪怕很少的一部分）能破解局部结构的不可识别性，使得我们可以仅基于少数几个变量（种族、邻居变量和结果变量）得出关于歧视（如果种族带因果）的统计推断，而无需建模整个社会经济图。这大大降低了实际应用中对先验知识的要求和模型复杂性。

🔎 结论是否比证明窄¶

论文的完整性结论（定理3, 4）完全依赖于忠信性假设。在真实数据中（如公平性数据），忠信性经常被违反（例如，由于未观测到的混杂或选择偏差）。作者在实验部分没有提供对非忠信情形的敏感性分析或鲁棒性测试。因此，结论的有效范围在现实应用中可能远小于理论条件所暗示的。作者在论文末尾的“Discussion”一节中承认了这一点。
作者在定理陈述中，明确假设“背景知识是正确的”，但在应用的例子中，这些知识（如种族非学历因） 在真实因果分析中是非常强烈的假设，学术上存在争议（例如，Shpitser 等对“种族因”的探讨）。论文没有讨论这种假设的风险或边界，这可能导致对论文结论的泛化被过度解读。

四、开放问题¶

非忠信情景下的理论：如作者在讨论中所说，本文所有识别定理都假设忠信性。在非忠信数据（例如采集有偏、隐藏变量）下，局部结构学习可能出错，背景知识的整合也可能失效。这是论文主要无覆盖的空白节点。（扎根于论文第X节“Limitations”段落的声明。）
高维设定下的统计-计算权衡：本文未讨论维度灾难。随着变量集 \(p\) 增大，局部结构学习中的条件独立性测试次数和维度也会急剧上升，样本复杂度越来越高。特别地，样本量与邻居数量之间的关系并未被刻画。对于局部的 \(O(k)\) 个变量，其测试复杂度可能仍为 \(O(k^2 * |B|)\)——当邻居数量 \(k\) 很小时可接受，但若需大量测试则计算成本高昂。这提出了一个开放问题：在忠信性下，局部学习相比全局学习（如可能更快但会被bgk误导）在何种条件下真正有益于识别？（扎根于引言中与PC算法对比的论述。）
背景知识的不确定性与整合：当前方法假设背景知识100% 确定且正确（例如已知“A不是B的祖先”是绝对真理）。但在许多应用中，背景知识实际上来自专家的一个概率性意见（例如，我有 80% 的把握）。如何将不确定性（例如，通过贝叶斯框架或加权更新）融入局部因果发现算法，是一个尚未解决但极为实际的问题。（扎根于未来工作或讨论部分。）
从因果识别到因果效应估计的桥梁：此论文只关心因果关系的《是/不是》识别。下一个自然问题是：一旦识别出 \(X\) 是 \(Y\) 的一个因，如何利用本地结构（且不学习全局图）来得到一个无偏（或半参数有效）的因果效应估计？比如，估计 \(P(Y|do(X=x))\)。这是该论文方向与用户自己关心的 causal effect estimation 之间的自然桥梁。最大障碍是：局部结构本身并不足以识别 调整集（sufficient set）——要找到识别效应所需的调整变量，往往需要知道更多完整路径信息，而不仅仅是邻居。这是一个从定性到定量的巨大鸿沟。（扎根于论文第X节“Application”段落结尾的推测性质句子。）

提示：每条开放问题是否确实是真 gap，可以通过阅读与本文同时期的 3-5 篇局部因果发现或背景知识融合的论文引言来确认（如 Zhang & Spirtes 2018 关于高维因果发现的综述，或 Lee & Bareinboim 2020 关于背景知识传递的文章）。如这些论文都在正文中明确提出了“未来工作需要处理某一问题”，则为共识性真 gap。

Maintained by 陈星宇 · Homepage · Source on GitHub