Huajishe Notes

1-PC算法

9 min read

PC算法 (PC Algorithm)

定位: PC算法是一种经典的约束式因果发现算法,通过对观测数据进行条件独立检验来恢复因果骨架并定向边,最终输出等价类CPDAG。

前置知识: 图论基础、有向无环图(DAG)、条件概率与条件独立、贝叶斯网络马尔可夫等价类

核心直觉

核心直觉: 在因果图中,如果两个变量X和Y之间的直接连接被其他变量S所”屏蔽”,那么给定S后,X和Y应该条件独立。这一性质允许我们通过统计检验来发现因果结构,而无需参数化假设。

约束式方法的核心思想是:因果结构编码了变量间的条件独立关系。通过系统性检验这些独立关系,可以反向推断出哪些变量之间存在直接因果连接,以及连接的方向。

数学推导

1. 基本假设

设为观测数据,假设数据由某个DAG 生成。核心假设:

  • 忠诚性假设(FA): DAG中的条件独立关系恰好对应观测中的条件独立关系,无额外巧合独立
  • 马尔可夫假设(MA): 给定父节点,每个节点条件独立于其非后代节点

2. 条件独立检验 (CI Test)

对于连续数据(高斯分布),使用偏相关系数进行条件独立检验:

其中为协方差矩阵,为X对Z中变量的偏回归系数向量。

检验统计量: , 近似服从分布。

对于离散数据,使用条件互信息:

在零假设()下, 近似服从 分布。

3. PC算法步骤

阶段一: 骨架恢复

对变量集进行条件独立检验,逐步增加条件集大小:

for k = 0 to max_degree:
    for each pair (X, Y):
        for each subset S of neighbors(X) with |S| = k:
            if CI_test(X, Y; S) holds:
                remove edge X - Y
                store separation set SepSet(X, Y) = S
  • : 检验边缘独立
  • : 检验给定一阶邻居后的独立
  • : 检验给定二阶邻居后的独立
  • 最多检验到degree-1阶邻居

阶段二: 定向边

v-structure识别规则: 对于三个变量,若且且,则定向为。

其他边定向规则:

  1. 盾牌规则: 若且,且与之间无边,则定向
  2. 传递性规则: 若,则
  3. 最终一致性规则: 应用所有定向规则直到不动点

4. PC-stable算法

原始PC算法存在顺序依赖问题,PC-stable通过不在线删除边,而是在骨架搜索结束后统一处理来解决:

关键区别: 搜索邻居时,使用”稳定”的条件集大小,避免因删除边而改变其他节点的邻居集。

5. 输出: CPDAG

PC算法输出完全部分有向无环图(Completed PDAG),表示马尔可夫等价类:

  • 所有等价DAG共享相同的骨架和v-structure
  • 非v-structure的边可以双向,表示方向不确定

训练与估计

参数估计

PC算法本身不进行参数估计,仅输出图结构。若需要参数:

高斯线性模型: 估计协方差矩阵,通过回归系数计算直接因果效应

离散模型: 估计条件概率表

计算复杂度

  • 时间复杂度: 其中为最大邻居数,为样本数
  • 实际上受限于条件集大小和节点数:
    • 最坏情况:
  • 空间复杂度: 存储骨架和分离集

推理/干预/反事实

干预与do操作

PC算法发现的因果结构允许进行do演算:

do-删除规则:

  • 后,移除指向的所有入边
  • 干预后的分布:

反事实推理

给定干预后的结构,可以进行反事实计算:

  1. 先验推理: 计算观察到特定证据时的后验
  2. 干预: 修改某些变量值
  3. 更新: 基于修改后的图重新计算后验

优点与局限

优点

  1. 理论基础坚实: 基于马尔可夫等价类的严格理论
  2. 无需参数假设: 约束式方法不假设特定的函数形式
  3. 输出等价类: CPDAG完整表示所有与数据兼容的DAG
  4. 计算效率高: 相比评分式方法,在大规模问题上更高效

局限

  1. 高维稀疏性: 条件集搜索空间随维度指数增长
  2. CI检验敏感性: 对样本量、检验阈值敏感
  3. 忠诚性假设: 违背忠诚性假设会导致错误结构
  4. 无法处理隐藏变量: FCI等扩展需要处理潜伏 confounders

与其他笔记的连接

  • 前置: 图论基础 DAG概念 → 本笔记PC算法
  • 延伸: GES算法(评分式) → NOTEARS(连续优化) → GraN-DAG
  • 应用: 因果发现评测指标 → 验证PC算法输出的CPDAG质量
  • 时间序列: PCMCI是PC算法在时序数据上的扩展

可复现性说明

关键参数

参数建议值说明
0.01-0.05CI检验显著性水平
max_cond_size3-5最大条件集大小
检验方法partial correlation(G) / G-test(离散)取决于数据分布

常用实现

  • Python: causal-learn库(原pyBN), pgmpy
  • R: pcalg包
  • Matlab: BNT toolbox

数据生成测试

import numpy as np
from scipy.stats import pearsonr
 
def ci_test_gaussian(X, Y, S, data, alpha=0.05):
    """Partial correlation CI test for Gaussian data"""
    from sklearn.linear_model import LinearRegression
 
    # Residualize X and Y on S
    X_res = residualize(X, S, data)
    Y_res = residualize(Y, S, data)
 
    r, p = pearsonr(X_res, Y_res)
    n = len(X_res)
    t_stat = r * np.sqrt(n - len(S) - 2)
    p_value = 2 * (1 - t_dist.cdf(abs(t_stat), df=n-len(S)-2))
 
    return p_value > alpha

章节总结

  • PC算法通过系统性的条件独立检验恢复因果骨架,是约束式因果发现的基础算法
  • 骨架阶段逐步增加条件集大小,利用CI检验删除独立边,时间复杂度为
  • v-structure识别基于”不对撞”结构: 中,X和Y给定Z外变量条件独立
  • 输出CPDAG表示马尔可夫等价类,非v-structure边方向不确定
  • PC-stable版本解决了原始算法的顺序依赖问题,更稳定
  • 忠诚性假设是关键:若违背,算法可能输出错误结构
  • CI检验方法取决于数据类型:偏相关(连续高斯)、G-test(离散)
  • 干预后的分布通过do演算计算,不同于条件概率
  • PC算法可扩展到时序数据(PCMCI)和含隐藏变量情形(FCI)
  • 评测指标SHD/CPDAG用于量化算法输出的结构误差

关键词: PC算法, 条件独立检验, CPDAG, v-structure, 马尔可夫等价类, 骨架恢复, 约束式方法

Graph View