基于约束的发现算法：PC、FCI 算法的延伸

基于约束的算法是因果发现的根本方法。它们遵循的原则是，数据中观察到的统计关联和独立性，在某些条件成立的前提下，映照出潜在的因果结构。具体而言，这些方法运用了条件独立关系（$X \perp Y | Z$）与真实因果有向无环图（DAG）中d-分离的图形思想之间的关联。

支撑大多数基于约束方法的根本假设是忠实性：即指数据分布中存在的所有条件独立关系都是因果DAG中d-分离的结果，反之，DAG中所有d-分离都对应于分布中的条件独立性。违反忠实性（例如，不同路径上的效应精确抵消）会使这些算法得出错误结论。

PC算法：在因果充分性假设下发现结构

PC算法以其开发者Peter Spirtes和Clark Glymour的名字命名，可能是最广为人知的基于约束的方法。它在一项重要的假设下运行，即因果充分性，这意味着没有未被观测的共同原因（潜在混杂因素）影响多个测量变量。

PC算法分为两个主要阶段：

1. 邻接搜索（骨架识别）：

   • 从一个完全无向图开始，其中每个变量都与其他所有变量相连。
   • 迭代地移除变量对 $X$ 和 $Y$ 之间的边。如果找到了一个条件独立性 $X \perp Y | S$，其中 $S$ 是 $X$ 的邻居（不包括 $Y$）或 $Y$ 的邻居（不包括 $X$）的某个子集，则移除边 $X - Y$。
   • 算法首先测试大小为 0 的条件集合 $S$（$|S|=0$）。如果 $X \perp Y$，则移除边 $X-Y$。
   • 然后，它继续测试给定大小为 1 的条件集合（$|S|=1$）时的条件独立性，然后是大小为 2（$|S|=2$），依此类推，直至达到预定义的最大大小或不能再移除更多边为止。这个迭代过程有效地修剪了图。
   • 这个阶段的结果是一个无向图，表示因果骨架，其中保留的边表示直接的因果连接或混杂（后者已被因果充分性假设排除）。

2. 边的定向：

   • 算法根据邻接搜索阶段收集到的条件独立性信息对边进行定向。
   • 识别V型结构：搜索三元组 $X - Z - Y$，使得 $X$ 和 $Y$ 不相邻，但边 $X - Z$ 和 $Z - Y$ 未被移除。如果分离 $X$ 和 $Y$ 的条件集合 $S_{XY}$（即导致发现 $X \perp Y | S_{XY}$ 的集合）不包含 $Z$，则将边定向为 $X \rightarrow Z \leftarrow Y$。这在 $Z$ 处形成一个V型结构（或碰撞点）。
   • 应用定向规则：反复应用逻辑规则来定向剩余的边，确保不创建新的V型结构，也不形成有向环。例如：
     • 如果存在 $X \rightarrow Y - Z$ 且 $X$ 和 $Z$ 不相邻，则将 $Y \rightarrow Z$ 定向（以避免V型结构 $X \rightarrow Y \leftarrow Z$）。
     • 如果存在 $X \rightarrow Y \rightarrow Z$ 且存在一条边 $X - Z$，则将其定向为 $X \rightarrow Z$（以避免环 $X \rightarrow Y \rightarrow Z \rightarrow X$）。

PC算法的输出通常是完全部分有向无环图（CPDAG），它表示DAG的一个马尔可夫等价类。这个类中的所有DAG都共享相同的骨架和V型结构，并隐含相同的条件独立性集合。

PC算法阶段在三个变量A、B、C上的简化图示，假设真实结构为A -> B <- C且忠实性成立。步骤2展示了测试显示A和C在给定B的情况下独立后的骨架。步骤3展示了所得的V型结构定向。

优点与局限：

• 优点：与基于分数的算法相比，对于稀疏图计算效率高；提供对条件独立性结构的理解。
• 局限：对条件独立性测试中的误差高度敏感（有限数据下的统计误差，非线性关系）；需要因果充分性这一强假设；输出是一个等价类，不一定是单一的真实DAG。标准实现中的顺序依赖性会影响结果，尽管存在稳定版本（例如PC-Stable）。

FCI算法：处理潜在混杂因素

因果充分性假设在实践中通常不切实际。未被观测的共同原因（潜在混杂因素）可能导致虚假关联，从而使PC算法得出错误结论（例如，添加虚假边或错误定向现有边）。

**快速因果推断（FCI）**算法是一种基于约束的方法，明确设计用于处理潜在混杂因素可能存在的情况。它放宽了因果充分性假设。

与PC算法的主要区别：

1. 输出表示：FCI算法输出部分祖先图（PAG）。PAG比DAG或CPDAG更复杂，使用边标记 (token)来表示潜在潜在变量引入的不确定性。常见的边标记包括：

   • $X \rightarrow Y$：确定 $X$ 导致 $Y$。
   • $X \leftrightarrow Y$：确定存在一个潜在混杂因素 $L$ 使得 $X \leftarrow L \rightarrow Y$。
   • $X \circ\rightarrow Y$：可能是 $X \rightarrow Y$ 或 $X \leftrightarrow Y$。
   • $X \circ - \circ Y$：邻接关系确定，但方向完全不确定（$X \rightarrow Y$、$X \leftarrow Y$ 或 $X \leftrightarrow Y$）。
   • $X - Y$：表示在骨架阶段建立的邻接关系，在定向规则进一步解析之前。

2. 独立性检验：FCI需要对条件独立性进行检验，这些检验对于通过以涉及潜在变量的碰撞点为条件可能引起的选择偏差是可靠的。这涉及更复杂的条件集合选择（使用“可能D-分离”集合）。

3. 定向规则：定向规则比PC算法的复杂得多，旨在推断祖先关系（例如，$X$ 是 $Y$ 的祖先）以及混杂因素的存在，即使不直接观测它们。

PC和FCI算法输出的比较，给定一个真实结构，其中X和Y之间存在潜在混杂因素L，且X和Y都导致Z。PC算法可能推断出虚假边或错误的方向。FCI使用PAG边标记正确表示不确定性，表明潜在的混杂（$X \circ - \circ Y$）和不确定的直接因果关系（$X \circ\rightarrow Z$, $Y \circ\rightarrow Z$）。

优点与局限：

• 优点：即使存在潜在混杂因素（在忠实性和测试假设下），也能提供渐近正确的估计结果。提供了一种处理缺失变量的合理方法。
• 局限：计算上比PC算法要求更高。输出的PAG可能比DAG复杂，且不易理解，可能使许多关系未被确定。仍然对独立性测试中的统计误差敏感。

延伸与变体

PC和FCI都催生了许多延伸和变体，旨在解决特定局限性或提升性能：

• PC-Stable, Conservative PC：对PC算法的修改，使得骨架识别阶段不受变量处理顺序的影响，从而提升了稳定性。Conservative PC在测试结果冲突时，在移除边方面更加谨慎。
• RFCI (Really Fast Causal Inference)：FCI的一个变体，旨在实现对潜在变量的类似鲁棒性，但计算速度显著提升，特别是在邻接搜索阶段。与标准FCI相比，其定向阶段提供的信息可能略少。
• COmbINE：将背景知识（例如，已知的时间顺序、禁止的边）直接整合到基于约束的搜索过程中。
• 基于核的测试（KCI）：用基于核的度量（例如，使用Hilbert-Schmidt独立性准则，HSIC）替换标准的条件独立性测试（如Fisher's Z或G平方）。这些可以更有效地检测非线性关系和处理非高斯数据，但通常伴随着更高的计算成本。
• 混合数据的基于约束算法：旨在同时处理包含连续和离散变量的数据集的延伸算法。

实现的实际考虑

有效应用基于约束的算法需要仔细考量多个因素：

1. 条件独立性测试的选择：选择适合您数据类型的测试（例如，用于多元高斯数据的Fisher-Z检验，用于离散数据的卡方或G方检验，用于非线性连续数据的核条件独立性（KCI）检验）。所选测试的假设必须得到合理满足。
2. 显著性水平（$\alpha$）：独立性测试中使用的阈值显著影响所得图。较小的 $\alpha$ 会导致移除的边更少（图更密集，假阴性更少，独立性的假阳性更多），而较大的 $\alpha$ 会导致移除的边更多（图更稀疏，假阴性更多，独立性的假阳性更少）。选择 $\alpha$ 通常涉及领域知识或模型选择技术。
3. 计算成本：复杂性随变量数量和真实图的密度迅速增长。考虑的条件集合的最大大小是影响运行时间的重要参数 (parameter)。对于高维数据，如果缺乏优化或稀疏性假设，这些方法可能在计算上变得过于昂贵。
4. 数据需求：基于约束的方法通常需要大量数据才能可靠地估计条件独立性，特别是当以更大的变量集合为条件时。数据不足时性能会显著下降。
5. 解释：请记住，PC算法输出马尔可夫等价类（CPDAG），而FCI算法输出PAG。这些表示与数据和假设一致的可能因果结构集合，不一定是单一的真实DAG。解释PAG中特定的边类型对于理解不确定性至关重要。

基于约束的方法提供了一个强大的框架来推断因果结构。尽管PC算法在因果充分性这一强假设下提供效率，FCI及其变体在更真实的环境中（可能存在潜在混杂因素）提供鲁棒性。理解它们的假设、局限性以及输出的性质，对于在高级因果推断流程中正确应用它们是根本的。