城市里来了一位擅长从观察中找真相的侦探。他接到一个古怪的委托：不看任何人际档案，只凭一群人日常活动的同步记录，画出一张“谁真正影响谁”的有向关系网。侦探的思路很朴素：第一步，先假设所有人两两之间都可能有关联，画一张密不透风的嫌疑网，再用统计证据把“伪关联”一条条划掉——比如两个人总是同时出现，但控制住他们共同的上线后，两人的默契立刻消失，于是这条线就是假的。第二步，对剩下的关系判断方向。他先嗅出“两个互不往来的人却都汇聚到同一个人身上”的罕见结构，再像推多米诺骨牌一样，把箭头方向逐步传播到全网。 这套破案流程，正是因果发现领域大名鼎鼎的 PC 算法：先用条件独立性检验找出因果图的骨架，再用 V 结构和 Meek 规则把无向边定向为因果箭头。本文就用侦探的视角，带你完整走一遍这两个阶段，并亲手实现一个能跑的 PC 算法。

岗位关联

掌握 PC 算法的骨架发现与 Meek 规则定向，是进入因果结构学习的第一道门槛。无论你要做可解释 AI、反事实推理还是政策评估，这项技能都能让你从纯观测数据中逼出因果方向。

目录
  1. 可视化演示
  2. 算法整体流程
  3. 条件独立性检验
  4. 骨架发现算法
  5. V结构定向
  6. Meek规则定向
  7. 马尔可夫等价类
  8. 复杂度与优化
  9. 应用与局限
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

动态演示PC算法骨架发现与Meek规的核心机制，通过输入/处理/存储/输出四种模式展示关键概念与交互流程。

本节配有交互动效（进入视口后自动加载，约 3KB）。

PC算法骨架发现与Meek规：PC算法 PC算法骨架发现的独立性检验策 骨架学习的具体算法流程与优化 核心机制可视化 PC算法骨架发现与Meek规整体架构与关键组件

算法整体流程

侦探接手案子后，并不急着追问“谁指挥谁”。他心里清楚，方向判断是难题，得放在后面。第一轮工作只是“盘关系网”：先假设所有人都两两有联系，再用证据一条条划掉虚假联系。等网眼稀疏了，才进入第二轮，研究每个联系的箭头指向。这种“先结构、后方向”的分工，正是 PC 算法的灵魂。

PC 算法由 Peter Spirtes、Clark Glymour 和 Richard Scheines 提出，名字取自两位作者的首字母。它把因果发现拆成两个可独立优化的子问题：第一阶段，从完全无向图出发，通过条件独立性检验逐条删除“可以被其他变量解释掉”的边，得到骨架；第二阶段，先识别对撞结构（V 结构）作为定向的种子，再反复套用 Meek 规则把方向传递给剩余的无向边。整个过程如图：

侦探的这份报告分两卷：第一卷是无向关系图，第二卷才标箭头。PC 算法也是一样，先保证结构不出错，再安心定方向——两阶段的严谨分工，是它几十年仍是因果发现基准算法的原因。

G0  →  条件独立性检验    Gs  →  V结构+Meek规则    P^\displaystyle G_0 \;\xrightarrow{\;\text{条件独立性检验}\;}\; G_s \;\xrightarrow{\;\text{V结构}+\text{Meek规则}\;}\; \hat{\mathcal{P}}
  1. G0 完全图初始状态，每个变量都与其他所有变量有一条无向边，代表“暂时无法排除任何联系”。
    G0=(V,(V2))G_0 = (V, \binom{V}{2})
  2. 第一次箭头对每对变量，在给定其他某些变量的条件下做独立性检验。若条件独立成立，就删除这对变量之间的边。
    if X⊥ ⁣ ⁣ ⁣⊥Y∣Z, then remove X−Y\text{if } X \perp\!\!\!\perp Y \mid \mathbf{Z}, \text{ then remove } X - Y
  3. Gs 骨架删边后的剩余无向图，只保留“数据还不足以否认直接关联”的边。
    Gs=(V,Es)G_s = (V, E_s)
  4. 第二次箭头先找出 V 结构定出第一批方向，再让 Meek 规则把方向一条条传播出去。
    Orientation(Gs)→P^\text{Orientation}(G_s) \to \hat{\mathcal{P}}
  5. P̂ 输出最终得到部分有向无环图，有的边带箭头，有的边仍是无向，表示数据无法再区分的方向。
    P^={G′:G′ 与数据条件独立关系一致}\hat{\mathcal{P}} = \{ G' : G' \text{ 与数据条件独立关系一致} \}

条件独立性检验

侦探手里需要一件“测谎仪”，用来判断两人在某个中间人在场时是否还真的同步。如果他发现“控制住上线后，两人的默契就消失了”，那就说明他们之间没有直接关系。这件测谎仪，就是统计里的条件独立性检验。

在连续型数据且近似高斯分布的场景下，PC 算法最常用的检验工具是偏相关检验。偏相关系数衡量的是“剔除 Z 的影响后，X 和 Y 还剩下多少线性关联”。如果偏相关为零，就说 X 和 Y 在给定 Z 的条件下独立：

实际做假设检验时，样本偏相关 $\hat{\rho}$ 的分布有偏，通常先做 Fisher Z 变换再查正态分布：

侦探的测谎仪校准好了：只要控制条件集后测得“偏相关为零”，他就在嫌疑网中划掉一条线。这个判断标准贯穿整个骨架发现阶段。

ρXY⋅Z=0⟺X⊥ ⁣ ⁣ ⁣⊥Y∣Z\displaystyle \rho_{XY\cdot \mathbf{Z}} = 0 \quad \Longleftrightarrow \quad X \perp\!\!\!\perp Y \mid \mathbf{Z}
  1. 样本偏相关$\hat{\rho}$ 是从观测样本中估计出的偏相关系数，是真实值的近似。
  2. 对数变换把 [-1, 1] 区间上的相关系数映到整个实数轴，分布更接近正态。
  3. 正态近似零假设下 T 近似服从均值为 0、方差为 $1/(n-|\mathbf{Z}|-3)$ 的正态分布，n 是样本量。
  4. 决策规则若 |T| 超过正态分布临界值，则拒绝“条件独立”；否则接受独立性，删掉这条边。

骨架发现算法

侦探拿着测谎仪，开始动手清理嫌疑网。他给自己定下规矩：先从最简单的场景查起——不带任何中间人的对话。两人若毫无互动，直接划掉线；若互动显著，则暂保留。接着升级难度，每轮“约谈”时引入一个中间人、两个中间人……直到所有可疑关系都被审过。

PC 的骨架发现正是这种从低阶到高阶的层进搜索。记 $k$ 为条件集大小，算法从 $k=0$ 开始，对每对还有边的变量，尝试所有大小为 $k$ 的候选条件集。只要找到一个条件集使它们条件独立，就删除这条边，并把该条件集记为分离集：

在每次删除边的同时，算法会悄悄记下一笔：“X 和 Y 之所以无关，是因为给定 $\mathbf{S}$ 之后它们才独立”。这笔记录就是分离集 $\mathrm{Sep}(X,Y)=\mathbf{Z}$。别小看它，V 结构定向全靠这份“不在场证明”。当所有剩余边的邻居数都小于当前 k 时，就再也没有更大的条件集可试，骨架阶段提前终止。

侦探画完了稀疏的关系网，但他没急着高兴，因为每条被划掉的线旁边都标着“他们在谁在场时反而不交流”——这些备注，就是后面判断箭头方向的破案线索。

∀X, ∀Y∈Adj(X), Z⊆Adj(X)∖{Y}, ∣Z∣=k:X⊥ ⁣ ⁣ ⁣⊥Y∣Z  ⇒  删除边 X−Y\displaystyle \forall X,\ \forall Y \in \mathrm{Adj}(X),\ \mathbf{Z} \subseteq \mathrm{Adj}(X)\setminus\{Y\},\ |\mathbf{Z}| = k: \quad X \perp\!\!\!\perp Y \mid \mathbf{Z} \;\Rightarrow\; \text{删除边 } X-Y
  1. 邻接集合Adj(X) 是当前骨架中 X 的邻居集合，初始时等于除 X 外的所有变量。
    Adj(X)={Y:X−Y∈E}\mathrm{Adj}(X) = \{ Y : X - Y \in E \}
  2. 条件集限制条件集 Z 只能从 X 的邻居中挑选，且不包含 Y。这是 PC 算法控制搜索量的关键。
  3. k 阶检验k 从 0 开始逐级递增，先做无条件独立性检验，再做一阶、二阶……逐层加码。
  4. 删除边只要找到一组 Z 让两者条件独立，边就永久删除，邻接关系随之更新，后续搜索范围也跟着缩小。

V结构定向

侦探盯着关系网，发现了一个奇特的三人局面：A 和 C 从无直接往来，却都不约而同地与 B 保持频繁互动。这意味着 B 是那个“汇合点”——在因果结构里，这可能是最关键的对撞结构（V 结构）：两个独立的箭头同时指向同一个节点。

在骨架图中识别 V 结构，要寻找“非相邻对 X、Y 的共同邻居 Z”。如果 Z 不在 X 和 Y 的分离集中，说明 Z 并不能解释两者的独立性，反而会让两者在给定 Z 时变得相关——这正是对撞子的特征。于是定向为：

识别出第一个 V 结构后，定向工作就有了“种子”。就像侦探抓住了一个关键证人，突破口一旦打开，剩下的方向就可以顺着逻辑链条层层推进。

X≁Y,X−Z∈Gs,Z−Y∈Gs,Z∉Sep(X,Y)  ⇒  X→Z←Y\displaystyle X \not\sim Y, \quad X - Z \in G_s, \quad Z - Y \in G_s, \quad Z \notin \mathrm{Sep}(X,Y) \;\Rightarrow\; X \to Z \leftarrow Y
  1. 非相邻对在骨架中 X 与 Y 之间没有边，这是对撞结构的前提条件。
    X≁YX \not\sim Y
  2. 共同邻居 ZZ 同时与 X 和 Y 相连，构成“人字形”结构。
    X−Z−YX - Z - Y
  3. 分离集判据骨架阶段记录了 Sep(X,Y)，即“能让 X、Y 独立的变量集合”。
  4. 定向结论若 Z 不在分离集中，说明 Z 是典型的对撞子，两条边都应指向 Z。
    X→Z←YX \to Z \leftarrow Y

Meek规则定向

侦探拿到了第一批箭头，但网里还剩不少无向边。他总结出几条铁律：只要满足某些局部图案，方向就能唯一确定。这组铁律由 Meek 于 1995 年系统整理，称为 Meek 规则。其中最核心的是 R1、R2、R3 三条。

除了 R1-R3 之外，还存在一条处理复杂嵌套路径的 R4 补充规则，它在实际数据中触发频率极低，多数教科书把它作为完整性的收尾。

侦探的箭头像多米诺骨牌：R1 推出一个方向，这个方向又触发新的 R2、R3 条件，直到所有能定的方向都定完。当然，总有些边无论怎么推都定不出方向——那就留下来，成为“悬案”。

R1:A→B,B−C,A≁C  ⇒  B→C\displaystyle R1:\quad A \to B, \quad B - C, \quad A \not\sim C \;\Rightarrow\; B \to C
  1. 同源节点A 同时指向 B 和 C，A 是两个箭头的共同源头。
  2. 待定向边B 与 C 之间是无向边。
  3. 一致性若反过来定向 C→B，会改变 A 与 B、A 与 C 的既有父子关系，破坏条件独立集。
  4. 结论定向为 B→C。

马尔可夫等价类

侦探最后发现，有些箭头无论证据多充分都分不清。比如“甲影响乙”和“乙影响甲”这两张因果图，只要它们的骨架一样、对撞结构一样，观察数据就永远无法区分。这组“无法被数据区分的因果图”，被称为同一个马尔可夫等价类。

Verma 与 Pearl 给出了一个漂亮的定理：两个 DAG 等价，当且仅当它们的骨架相同且 V 结构集合相同：

PC 算法输出的 PDAG（部分有向无环图）正是对等价类的紧凑表示：有向边就是等价类中所有图都一致的方向，无向边则表示“这条边的方向在等价类里可以取两种可能”。

侦探的最终报告没有强行编造无法确定的箭头，而是在那些边上标注“未定向”。这不是无能，而是诚实——观测数据的信息量本身就有限。

G≡G′  ⟺  Sk(G)=Sk(G′) 且 Vstr(G)=Vstr(G′)\displaystyle G \equiv G' \;\Longleftrightarrow\; \mathrm{Sk}(G) = \mathrm{Sk}(G') \ \text{且} \ \mathrm{Vstr}(G) = \mathrm{Vstr}(G')
  1. 骨架 Sk(G)去掉所有箭头方向后得到的无向图，代表变量间是否存在直接关联。
  2. V 结构集合 Vstr(G)图中所有对撞结构的集合，每个对撞结构都对应一条独特的条件独立模式。
  3. 等价条件两个条件同时成立，两个 DAG 编码的条件独立关系就完全相同。
  4. 实践含义观测数据最多把因果图定位到一个等价类，而不是单张图。

复杂度与优化

侦探的搜查策略如果太笨，会对所有嫌疑人的任意组合都做一次测谎，嫌疑人数一多，工作量立刻爆炸。PC 算法在最坏情况下也是如此：条件集要从所有其余变量中任意挑选，检验次数随变量数呈指数增长。

这让“邻接集合约束”成了 PC 最重要的剪枝手段：条件集只从当前邻居中取，而不是从所有变量中随便挑。每删一条边，所有相关节点的邻居数就减少一轮，后续搜索成本跟着骤降。再加上按 k 从低到高的层级终止策略，以及各变量对之间彼此独立的检验可并行化，PC 算法在高维稀疏问题上依然实用。

侦探的经验是：先锁定小圈子，再深入调查。现实世界的大多数因果图是稀疏的，PC 算法正是借了“稀疏”这个东风。

Ctests=O ⁣(∑k=0p−2(p−2k)k)⊆O(p22p−2)\displaystyle C_{\mathrm{tests}} = O\!\left( \sum_{k=0}^{p-2} \binom{p-2}{k} k \right) \subseteq O(p^2 2^{p-2})
  1. p 为变量数参与因果发现的变量个数，直接决定搜索空间大小。
  2. 组合数从 p-2 个候选变量中选 k 个作为条件集，组合数随 k 变化。
  3. 求和最坏情况下需要对所有可能的 k 都做一次穷举检验。
  4. 改进空间如果真实因果图的邻居数很小，条件集大小 k 被邻居数限制，检验次数会降到多项式级。

应用与局限

侦探在报告末尾总会加一行小字：“本结论假设不存在隐藏的干扰者。”这不是推卸责任，而是 PC 算法赖以成立的基石——忠实性假设：数据分布中的条件独立关系，必须与图结构中的 d-分离关系完全一致。

在基因调控网络推断中，研究者用基因表达数据跑 PC 算法，识别转录因子到靶基因的调控方向；在经济政策分析里，经济学家从宏观时间序列中寻找政策变量与消费、投资之间的因果方向。但无论场景多诱人，都要警惕：PC 输出的是等价类而非唯一真相，而且它对独立性检验的错误极其敏感——一次假阳性删边就可能传导出完全不同的结构。

侦探合上卷宗，总结道：PC 算法是观测数据中探索因果方向的强大工具，但它更像一张精心绘制的“嫌疑地图”，而不是盖了章的判决书。

分布 P 忠实于图 G  ⟺  I(G)=I(P)\displaystyle \text{分布 } P \text{ 忠实于图 } G \;\Longleftrightarrow\; I(G) = I(P)
  1. I(G)图中所有由 d-分离推导出的条件独立关系集合。
  2. I(P)观测数据分布中所有真实存在的条件独立关系集合。
  3. 等式成立图里的每个分离关系都能在数据中验证，反之亦然，二者一一对应。
  4. 条件脆弱如果存在隐藏的共同原因、选择偏差或严重的检验误差，等式可能被破坏。

AI 应用场景

基因调控网络推断

阶段：科学发现（因果结构学习）

解决的问题：传统相关性分析只能给出“哪些基因一起变化”，无法区分调控方向。生物学家想知道“哪个转录因子驱动了哪个靶基因”，这需要因果方向。PC 算法通过条件独立性检验删除间接关联，再用 V 结构和 Meek 规则推导出调控箭头，直接输出可解释的基因调控网络。

具体案例：某课题组拿到乳腺癌细胞系的 RNA-seq 表达矩阵（约 8000 个基因、300 个样本），先筛选出 50 个候选转录因子，再用 PC 算法学习子网络。结果发现某个已知癌基因被多个转录因子共同指向，形成清晰的 V 结构，这为后续湿实验验证提供了精准的靶点清单。

经济政策因果分析

阶段：因果推断（观测数据反事实分析）

解决的问题：经济学家无法对货币政策做随机对照实验，只能观察宏观时间序列。PC 算法可以从利率、通胀、就业等指标中梳理出“谁先变化、谁跟着变化”的因果次序，为政策评估提供骨架支撑，避免把相关性误当因果。

具体案例：某智库分析 2000-2020 年的季度宏观数据，用 PC 算法构建利率、货币供应量、CPI 和 GDP 之间的因果骨架。算法识别出“利率→货币供应量→CPI”的传导链，并借助 Meek 规则确定了方向，为后续结构向量自回归模型提供了先验结构。

推荐系统因果纠偏

阶段：反事实推理（用户行为因果建模）

解决的问题：推荐系统中的点击数据存在严重的曝光偏差：用户只能点击“被推荐的东西”，直接拟合点击率会把曝光机制当成用户偏好。PC 算法可以在用户特征、曝光物品、点击行为之间建立因果结构，识别出“曝光→点击”这一对撞结构，从而指导做反事实纠偏。

具体案例：某电商平台用用户活跃度、商品热度、是否曝光、是否点击四类变量跑 PC 算法，发现“用户活跃度→点击”和“商品热度→点击”构成 V 结构，而曝光是独立干扰项。基于这个结构，团队调整了排序模型的样本权重，离线 AUC 提升 3 个百分点。

Python 演示

python120 行
import mathfrom itertools import combinations import numpy as np  def gen_data(n=500, seed=42):    rng = np.random.default_rng(seed)    A = rng.normal(size=n)    C = rng.normal(size=n)    B = 0.5 * A + 0.5 * C + rng.normal(size=n) * 0.3    D = 0.5 * B + rng.normal(size=n) * 0.3    return np.column_stack([A, B, C, D])  def partial_corr(data, i, j, cond):    if not cond:        r = np.corrcoef(data[:, i], data[:, j])[0, 1]    else:        idx = [i, j] + list(cond)        cov = np.cov(data[:, idx].T)        prec = np.linalg.inv(cov)        r = -prec[0, 1] / math.sqrt(prec[0, 0] * prec[1, 1])    return r  def indep_pvalue(data, i, j, cond):    n = data.shape[0]    r = partial_corr(data, i, j, cond)    z = 0.5 * math.log((1 + r) / max(1 - r, 1e-12))    stat = abs(z) * math.sqrt(n - len(cond) - 3)    return 2 * (1 - 0.5 * (1 + math.erf(stat / math.sqrt(2))))  def skeleton(data, alpha=0.05):    n, p = data.shape    adj = [[True if i != j else False for j in range(p)] for i in range(p)]    sepset = {}    for k in range(p - 1):        changed = False        for i in range(p):            for j in range(i + 1, p):                if not adj[i][j]:                    continue                neigh = [c for c in range(p) if adj[i][c] and c != j]                if len(neigh) < k:                    continue                for cond in combinations(neigh, k):                    if indep_pvalue(data, i, j, list(cond)) > alpha:                        adj[i][j] = adj[j][i] = False                        sepset[(i, j)] = list(cond)                        changed = True                        break        if not changed and k >= 2:            break    return adj, sepset  def orient(adj, sepset):    p = len(adj)    E = [['' for _ in range(p)] for _ in range(p)]    for i in range(p):        for j in range(i + 1, p):            if adj[i][j]:                E[i][j] = 'u'                E[j][i] = 'u'    for x in range(p):        for y in range(p):            if x == y or adj[x][y]:                continue            for z in range(p):                if z == x or z == y:                    continue                if adj[x][z] and adj[y][z] and z not in sepset.get((x, y), []):                    E[x][z] = 'd'                    E[z][x] = ''                    E[y][z] = 'd'                    E[z][y] = ''    changed = True    while changed:        changed = False        for a in range(p):            for b in range(p):                if E[a][b] != 'd':                    continue                for c in range(p):                    if E[b][c] == 'u' and not adj[a][c]:                        E[b][c] = 'd'                        E[c][b] = ''                        changed = True                    if E[a][c] == 'd' and E[b][c] == 'u':                        E[b][c] = 'd'                        E[c][b] = ''                        changed = True                    if E[c][b] == 'd' and E[a][c] == 'u':                        E[a][c] = 'd'                        E[c][a] = ''                        changed = True    return E  def report(adj, E):    p = len(adj)    print('骨架边:')    for i in range(p):        for j in range(i + 1, p):            if adj[i][j]:                print(f'  {chr(65+i)} - {chr(65+j)}')    print('定向结果:')    for i in range(p):        for j in range(p):            if E[i][j] == 'd':                print(f'  {chr(65+i)} -> {chr(65+j)}')  if __name__ == '__main__':    data = gen_data()    adj, sepset = skeleton(data, alpha=0.05)    E = orient(adj, sepset)    report(adj, E)
目的：用 Python 从零实现 PC 算法的骨架发现与定向阶段。在人工构造的因果数据（A→B←C 且 B→D）上运行后，应输出正确的骨架和箭头方向。
  1. B = 0.5 * A + 0.5 * C + rng.normal(size=n) * 0.3生成数据时植入真实因果结构：A 和 C 共同驱动 B，B 再驱动 D。
  2. prec = np.linalg.inv(cov)对协方差矩阵求逆得到精度矩阵，偏相关可由精度矩阵元素一步导出。
  3. r = -prec[0, 1] / math.sqrt(prec[0, 0] * prec[1, 1])用精度矩阵计算偏相关，正负号来自矩阵求逆的代数结构。
  4. neigh = [c for c in range(p) if adj[i][c] and c != j]候选条件集只从当前邻居中取，这是 PC 算法控制搜索量的关键。
  5. for cond in combinations(neigh, k)遍历所有大小为 k 的条件集，从低阶到高阶逐一检验。
  6. sepset[(i, j)] = list(cond)记录分离集：这组变量能让 i 与 j 独立，是后续 V 结构定向的重要证据。
  7. if adj[x][z] and adj[y][z] and z not in sepset.get((x, y), [])V 结构判定核心：Z 是共同邻居且不在分离集中，则定向为对撞结构。
  8. if E[b][c] == 'u' and not adj[a][c]Meek 规则 R1：A→B 且 B-C 无向，而 A 与 C 不相邻时，定向 B→C。

常见误区

误区我以为 PC 的骨架发现就是计算所有变量两两之间的相关系数，显著的保留，不显著的删掉。条件独立性检验听起来很高级，但好像只是锦上添花。

正解零阶无条件检验只是第一层筛子。真实场景中，两个变量可能因为共同原因而表现出虚假相关，比如“夏天冰淇淋销量”和“溺水人数”高度相关，但它们之间没有直接因果边。PC 算法的核心是高阶条件独立性检验：在控制中间变量后，若两者仍相关才保留边。只做零阶检验会把大量间接关联误判为直接关联，骨架必然失真。

为何常见：零阶检验最容易理解，初学者往往先入为主地把它当成全部；且没有意识到“控制中间人后关系消失”恰恰是伪关联的信号。

误区我以为跑完 PC 算法，所有边都会被标上箭头，得到一张完整的因果有向图，可以直接交给业务方当最终结论。

正解当多个 DAG 属于同一马尔可夫等价类时，观测数据根本无法区分某些边的方向。PC 算法输出的是 PDAG/CPDAG，无向边表示“等价类内方向可翻转”。强行定向反而会给出无法用数据支撑的伪因果结论，误导后续分析。

为何常见：“因果发现”这个名字太有迷惑性，让人觉得输出就是确定答案；加上很多教程展示的玩具例子恰好所有边都能定向，掩盖了等价类的存在。

误区我总觉得只要独立性检验的 p 值大于 0.05，就证明两个变量百分之百条件独立，删掉这条边是绝对安全的。

正解假设检验只能给出概率证据，不能给出绝对结论。p 值大于阈值只表示“没有足够证据拒绝独立”，样本量小、信噪比低、分布偏离假设时都可能误判。PC 算法对检验错误极其敏感——一条边误删，后续分离集和 V 结构定向都会连锁出错，这被称为“检验误差传播”。

为何常见：统计检验中的“不拒绝原假设”与“接受原假设”在直觉上很难区分，初学者容易把两者画上等号。

误区我听说 PC 算法用 Meek 规则定向，就以为只要不断套用 R1、R2、R3，所有边都能自动定出方向，V 结构只是可选的补充。

正解V 结构定向是整个定向阶段的起点。Meek 规则只是一套传播机制，它需要已有的一些有向边作为“种子”。如果全图没有任何 V 结构可识别，Meek 规则面对一个完全无向的骨架也无从下手。先有 V 结构定出初始箭头，Meek 规则才能把方向逐条传播出去。

为何常见：文章标题常突出 Meek 规则，读者自然以为它是主角，忽略了它只是“放大器”而非“发电机”。

误区我认为 PC 算法是通用因果发现工具，不管有没有隐藏变量、不管数据是高斯的还是离散的，拿过来就能跑出正确答案。

正解PC 算法建立在两个关键假设上：忠实性假设（数据中的条件独立关系与图结构完全一致）和因果充足性假设（不存在未观测的共同原因）。如果存在隐藏变量，PC 会输出错误骨架；数据高度非线性或混合类型时，偏相关检验也不再适用，需要换用核方法或互信息类检验。面对复杂数据，应使用 FCI 算法或更稳健的非参数检验。

为何常见：很多教程只展示理想化数据上的成功案例，让人误以为 PC 是万能黑箱，忽略了它背后的强假设。

面试题

Q1. PC 算法的骨架发现阶段，初始图是什么？

单选题 · easy

  • A.空图，边逐步添加
  • B.完全无向图，边逐步删除← 正确答案
  • C.随机有向图
  • D.由先验知识决定

答案：B。PC 算法从完全无向图出发，假设所有变量都可能有直接关联，再通过条件独立性检验逐步删边。这与从空图加边的思路相反，也是它作为“约束方法”的典型特征。

Q2. 高斯数据下，PC 算法判断条件独立的主要工具是什么？

单选题 · easy

  • A.直接比较直方图
  • B.检验偏相关系数是否为零← 正确答案
  • C.最大似然估计参数
  • D.删除缺失值样本

答案：B。高斯分布中，偏相关为零等价于条件独立。PC 算法通常用 Fisher Z 变换检验偏相关系数的显著性，这也是它在连续数据场景下最常用的条件独立判定方式。

Q3. 关于分离集（Sepset）的描述，正确的是？

单选题 · mid

  • A.能使两变量条件独立的变量集合← 正确答案
  • B.使两变量相关性最强的变量集合
  • C.只在删边后丢弃不用的中间量
  • D.等于所有变量的全集

答案：A。骨架阶段删除边时记录的那组条件变量就是分离集。它随后用于 V 结构定向：如果共同邻居不在分离集中，说明该邻居是对撞子。分离集贯穿两阶段，绝非无用信息。

Q4. 识别 V 结构时，对三元组 X-Z-Y 的判定条件是什么？

单选题 · mid

  • A.X 与 Y 不相邻，且 Z 不在分离集中← 正确答案
  • B.X 与 Y 相邻，且 Z 在分离集中
  • C.X 与 Z 不相邻
  • D.三个变量完全相互独立

答案：A。V 结构 X→Z←Y 中，X 与 Y 在骨架中不相邻，且 Z 出现在两者共同邻居中。若 Z 不在 Sep(X,Y) 中，说明给定 Z 时 X 与 Y 反而相关，这是对撞子独有的特征。

Q5. 以下哪些属于 Meek 规则的定向逻辑？

多选题 · mid

  • A.已知 A→B 且 B-C 无向，A 与 C 不相邻，则 B→C← 正确答案
  • B.已知 A→B→C 且 A-C 无向，则定向 A→C← 正确答案
  • C.已知 A→B 且 A→C，B-C 无向，则定向 B→C← 正确答案
  • D.两变量无条件独立时直接删除该边

答案：ABC。A 是 R1（防新增对撞），B 是 R2（防有向环），C 是 R3（同源一致性）。D 属于骨架发现阶段的删边规则，不是 Meek 定向规则。

Q6. 两个 DAG 属于同一马尔可夫等价类的充要条件是？

单选题 · hard

  • A.有向边的数量相同
  • B.骨架相同且 V 结构集合相同← 正确答案
  • C.变量数量相同
  • D.条件概率表参数相同

答案：B。Verma-Pearl 定理指出，骨架和 V 结构集合共同决定条件独立关系，两者相同则 DAG 等价。边数、变量数或参数都远不足以刻画等价性。

Q7. PC 算法输出 PDAG 中的无向边表示？

多选题 · hard

  • A.该边方向无法由观测数据区分← 正确答案
  • B.等价类内该边可朝两个方向之一← 正确答案
  • C.该变量不在因果结构内
  • D.该边方向由先验知识强制确定

答案：AB。无向边是等价类中“方向未被确定”的边，可以在两个方向上翻转而不改变条件独立关系。它不是无关变量，也不是被先验固定的边。

Q8. PC 骨架搜索中，条件集 Z 为什么只从 X 的邻居中选取？

单选题 · easy

  • A.减少检验次数且保持算法统计性质← 正确答案
  • B.邻居变量更容易通过检验
  • C.随机选择会引入偏差
  • D.条件集大小必须固定为 1

答案：A。PC 的核心剪枝策略就是条件集仅从当前邻居中取。这大大缩小了候选集合的规模，使算法在高维稀疏图上可行，同时不破坏条件独立性判定的可靠性。

Q9. 在忠实性假设下，以下哪项描述成立？

单选题 · hard

  • A.图中 d-分离与数据条件独立一一对应← 正确答案
  • B.所有变量间都必须存在边
  • C.条件独立关系只与样本量有关
  • D.因果方向总可以被完全确定

答案：A。忠实性假设要求 I(G)=I(P)，即图中的 d-分离关系与数据中的条件独立关系完全一致。它保证了 PC 算法的正确性，但并不能突破等价类限制，方向仍可能无法完全确定。

Q10. 在高维小样本场景（p 接近甚至大于 n）下，PC 算法面临哪些困难？

多选题 · extreme

  • A.独立性检验误差迅速累积← 正确答案
  • B.候选条件集组合数量爆炸← 正确答案
  • C.输出结果反而更加精确
  • D.不再需要任何统计假设

答案：AB。高维下样本信息不足，偏相关估计不稳，检验错误会沿删边过程传导放大；同时条件集组合随邻居数指数增长。PC 并不会因此变得更准，忠实性等假设依旧不可或缺。