假设你现在是这座城市的交通规划师。经过前期的反复摸排，你手里已经拿到了一张“街区路网图”——哪些路口之间有道路直接相连，一目了然。这张图就是因果发现中的无向骨架：它告诉你变量之间有关联，却没告诉你每条路是单行还是双行、车流究竟朝哪个方向走。接下来的任务，就是像为道路标定行驶方向一样，为骨架上的每一条边确定因果方向。这个环节，被称为方向确定阶段。 但你要时刻记住一个交通常识：并不是每条路的方向都能从数据中唯一推断出来。有些路口的车流汇聚方式（比如两条路同时汇入同一条路，形成一个“人字形”）能让你果断拍板方向；有些路段则无论你观察多久，都分不清谁先谁后——这时候只能老老实实保留双向通行。方向确定阶段所做的全部工作，就是“能定向的定向、不能定向的保留无向”，最终输出一张诚实反映数据能力上限的因果方向图。

岗位关联

对 AI 从业者而言，方向确定阶段决定因果发现能“走多远”：没有它，你只能得到一堆关系连线；掌握它，你才能从数据中分辨出“谁影响谁”，这是从关联分析跃迁到因果推断的临门一脚。

目录
  1. 可视化演示
  2. 方向确定概述
  3. v-结构识别
  4. 方向传播规则
  5. 马尔可夫等价类
  6. 算法流程复杂度
  7. 实际应用场景
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示语句覆盖、分支覆盖、路径覆盖三种覆盖率度量方式的差异，动态演示控制流图中被覆盖节点与边的递进过程。

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

语句覆盖率度量 语句覆盖：每条可执行语句至少被执行一次 最弱覆盖准则，不检查分支条件和路径组合 覆盖率 = 已执行语句数 / 总语句数 × 100%

方向确定概述

你拿着那张街区路网图站在市政大厅里，领导问你对每条路的通行方向有什么看法。你仔细端详：有些路口呈现明显的“汇聚”形态，两条走进来的路交汇于一点，这让你想起了交警总结的一条铁律——两条路同时进入一个路口，却互不相通，那这个路口必然是个“汇聚点”，车流只能从两边进、从另外的路出。这个汇聚点，就是因果图里的v-结构（碰撞结构），它是方向确定的第一块多米诺骨牌。

找到全部汇聚点是第一步，随后你还需要一套“交通推断逻辑”：已知某条路是单行道，顺着它的上下游关系，可以逐步推断相邻道路的方向。这就是方向传播规则。两步合起来，就是方向确定阶段的全貌——先用v-结构敲定一批确定方向，再用传播规则把这些方向像涟漪一样扩散出去。

但这里有一个重要的提醒：你不必为每一条路都标上单行方向。如果数据里根本没有留下判断方向的线索，强行拍板方向反而会造成错误。方向确定阶段最可贵的品质，就是懂得“适可而止”——把能确定的方向全部确定，把不能确定的边诚实地保留为无向。这种“有所为有所不为”的边界感，正是数据能告诉你的因果方向信息上限。

Orient(G,I)=Prop⁡ ⁣(VStruct⁡(Gskel))\text{Orient}(G, \mathcal{I}) = \operatorname{Prop}\!\left(\operatorname{VStruct}(G_{\text{skel}})\right)
这个公式表示：骨架 $G_{\text{skel}}$ 先经过 v-结构检测函数 $\operatorname{VStruct}$ 得到初始定向，再经过传播函数 $\operatorname{Prop}$ 不断推出新方向，最终得到完整的方向结果。$\operatorname{Orient}$ 是方向确定的总入口函数，$\mathcal{I}$ 是条件独立性信息集合。
  1. 骨架输入$G_{\text{skel}}$ 是无向骨架，它只记录变量之间是否有边相连，不关心方向，相当于只有连线没有箭头的地图。
    Gskel=(V,E)G_{\text{skel}} = (V, E)
  2. 碰撞检测$\operatorname{VStruct}$ 在骨架中扫描每一条“V字形态”的三元组，用条件独立性检验判断它们是否真的构成碰撞结构，输出一组已定向的边。
    VStruct⁡↦{ X→Z←Y }\operatorname{VStruct} \mapsto \{\, X \to Z \leftarrow Y \,\}
  3. 规则传播$\operatorname{Prop}$ 把已定向的边作为种子，反复应用传播规则，直到没有新的边可以定向为止，输出最终的部分有向图。
    Prop⁡↦Dfinal\operatorname{Prop} \mapsto D_{\text{final}}

v-结构识别

你在路口观察了一天车流，发现一个很有意思的现象：A路和C路看起来完全不搭界——它们的车流没有任何直接交流的迹象，但两条路都汇入了中间那条B路。你大胆推断：这不是巧合，B路就是那个“汇聚型路口”：A路的车和C路的车都流向B路，而A、C之间从不互流。翻译成因果语言：A和C在给定B之后仍然相关（因为B同时受二者影响），这个“V字汇聚”正是碰撞结构的标志。

在技术实现上，v-结构的识别不能只看形状。假设骨架上有三条边 $X—Z—Y$，要确认 $Z$ 是碰撞节点，需要验证两个硬性条件：第一，$X$ 和 $Y$ 之间没有直接相连的边；第二，在给定其他任何变量集合时，$X$ 和 $Y$ 的条件独立性检验都不能用 $Z$ 来解释两者的关系——换句话说，$Z$ 不在 $X$ 与 $Y$ 的分离集里。只有同时满足这两个条件，才能把这段“人字形”道路定向为 $X \to Z \leftarrow Y$。

识别v-结构就好比你在城市里标出所有“汇聚点”，这是整个方向确定大工程的第一块基石。没有这些汇聚点，后面所有传播规则都无从谈起——它们就像第一块多米诺骨牌，推倒它，后续的方向推断才能接连发生。

若 X 与 Y 不相邻，且 Z∉Sep⁡(X,Y)，则 X→Z←Y\text{若 } X \text{ 与 } Y \text{ 不相邻，且 } Z \notin \operatorname{Sep}(X, Y)，\text{则 } X \to Z \leftarrow Y
分离集 $\operatorname{Sep}(X,Y)$ 是一组使 $X$ 和 $Y$ 在该条件下变得条件独立的变量集合。$Z \notin \operatorname{Sep}(X,Y)$ 意味着：给定 $Z$ 时 $X,Y$ 并不独立，这刚好与碰撞结构的性质吻合。
  1. 不相邻检查先确认骨架中 $X$ 与 $Y$ 没有直连边，也就是说地图上 $X$ 和 $Y$ 不直接通车。若它们直连，$Z$ 的中间角色无法被唯一确定。
    X∉Adj⁡(Y)X \notin \operatorname{Adj}(Y)
  2. 分离集验证检查 $Z$ 是否出现在 $X$ 与 $Y$ 的分离集中。分离集是“一旦给定这些变量，$X$ 和 $Y$ 就相互独立”的集合。$Z$ 不在其中，说明 $Z$ 不能“解释掉” $X,Y$ 的相关性。
    Z∉Sep⁡(X,Y)Z \notin \operatorname{Sep}(X, Y)
  3. 碰撞判定两个条件同时成立，说明 $X$ 和 $Y$ 的共同影响源是 $Z$，于是把两条边都定向为指向 $Z$ 的箭头，形成 $X \to Z \leftarrow Y$ 的碰撞结构。
    定向：X→Z←Y\text{定向：} X \to Z \leftarrow Y

方向传播规则

现在你的地图上有了一串汇聚点，每条汇聚点都带来两个“已定方向”的箭头。但你并不满足——很多路的方向还悬而未决。于是你拿出交警的方向推断手册，里面记录了三条铁律。每一条都是基于一个朴素的交通直觉：方向不能引发矛盾。

R1（链式传播）：如果某条单行道 $X \to Y$，而 $Y$ 还有一条无向边连着 $Z$，且 $X$ 与 $Z$ 之间没有路，那么 $Y$ 必然指向 $Z$。为什么？因为如果 $Z \to Y$，就会在 $Y$ 处凭空制造一个新的汇聚点，而 $X$ 和 $Z$ 又不相连，这个汇聚点没有数据支撑。

R2（避免有向环）：如果 $X \to Y$ 且 $Y \to Z$，而 $X$ 与 $Z$ 之间还有一条无向边，那么这条无向边必须定向为 $X \to Z$。想象你开车沿着 $X \to Y \to Z$ 走了一圈，如果最后 $Z \to X$，你就陷入一个永无止境的回路——因果世界不允许这种循环出现。

R3（碰撞延伸）：若 $X \to Y$ 且 $Z \to Y$（$Y$ 是已知汇聚点），$Y$ 还有一条无向边连着 $W$，且 $X$ 与 $Z$ 不相邻，则 $Y$ 必然指向 $W$。这就像汇入路口的车流必须从另一个出口离开，既然已经有了两个进方向，$W$ 这条路就只能是出去的方向。

这三条规则就像交通规划师手里的“方向推断三段论”，每一条都从已有的单行方向推出新的单行方向，而且永远不会自相矛盾。你一遍遍翻阅手册、反复应用，直到某一次循环下来再也没有新方向能够推出——这时，方向确定的核心推理就圆满完成了。

R1: X→Y,  Y−Z, X⊥ ⁣ ⁣ ⁣⊥Z⇒Y→ZR2: X→Y,  Y→Z, X−Z⇒X→ZR3: X→Y,  Z→Y, Y−W, X⊥ ⁣ ⁣ ⁣⊥Z⇒Y→W\begin{aligned}\text{R1: } & X \to Y,\; Y-Z,\, X \perp\!\!\!\perp Z \Rightarrow Y \to Z \\\text{R2: } & X \to Y,\; Y \to Z,\, X-Z \Rightarrow X \to Z \\\text{R3: } & X \to Y,\; Z \to Y,\, Y-W,\, X \perp\!\!\!\perp Z \Rightarrow Y \to W\end{aligned}
三条规则的本质都是在“已有方向”的基础上做无矛盾的延伸。$X \perp\!\!\!\perp Z$ 表示 $X$ 和 $Z$ 条件独立（不相邻），它防止你制造出没有数据支撑的新碰撞点。规则的应用不是一次性的，而是要不断循环，直到没有新方向可推出为止。
  1. R1 链式传播前提是 $X \to Y$ 且 $Y$ 连到无向的 $Z$，$X$ 与 $Z$ 不相邻。此时若反向为 $Z \to Y$，$Y$ 会变成碰撞点，但 $X$、$Z$ 不相邻不满足碰撞条件，所以只能 $Y \to Z$。
    X→Y,  Y−Z, X≁Z⇒Y→ZX \to Y,\; Y-Z,\, X \not\sim Z \Rightarrow Y \to Z
  2. R2 避免有环$X \to Y \to Z$ 形成一条有向链，$X$ 与 $Z$ 还连着无向边。若把这条边定为 $Z \to X$，就构成 $X \to Y \to Z \to X$ 的有向环，违反因果无环假设，因此必须是 $X \to Z$。
    X→Y,  Y→Z, X−Z⇒X→ZX \to Y,\; Y \to Z,\, X-Z \Rightarrow X \to Z
  3. R3 碰撞延伸$Y$ 已有两个父亲 $X$ 和 $Z$，$Y$ 还有无向邻居 $W$。$X$ 与 $Z$ 不相邻，$W$ 不能反向指向 $Y$（否则 $Y$ 处会出现没有支撑的第三个碰撞），所以只能 $Y \to W$。
    X→Y,  Z→Y, Y−W, X≁Z⇒Y→WX \to Y,\; Z \to Y,\, Y-W,\, X \not\sim Z \Rightarrow Y \to W

马尔可夫等价类

当你把能定方向的路都定完之后，地图上还剩几条无向边。这时候，一个更深刻的问题浮现出来：这些无向边背后，到底是“数据量不够”还是“本质上就无法区分”？答案是后者。要理解这一点，你得引入马尔可夫等价类的概念。

想象两座极其相似的城市：它们的路网结构完全一样，汇聚点也都一模一样，只是某几条单行道的方向细节略有不同。对任何一个观测者而言，这两座城市产生的交通数据模式完全相同——你根本无法从数据中分辨出哪座城市是哪座。这样的两个因果图，就属于同一个马尔可夫等价类。等价类的判定标准非常朴素：骨架相同，且 v-结构集合相同。只要满足这两个条件，两幅图在数据层面就是“双胞胎”。

马尔可夫等价类给你吃了一颗定心丸：留下来没定方向的那几条边，并不是因为你的算法不够努力，而是数据本身就没提供判断依据。就像两条平行单行道之间，你无论站多久也看不出哪条车流先出发。保留无向边，恰恰是对“数据能告诉你的信息上限”最诚实的致敬。

E(D)={D′:skeleton⁡(D′)=skeleton⁡(D)  且  vstructures⁡(D′)=vstructures⁡(D)}\mathcal{E}(D) = \{ D' : \operatorname{skeleton}(D') = \operatorname{skeleton}(D) \;\text{且}\; \operatorname{vstructures}(D') = \operatorname{vstructures}(D) \}
$\mathcal{E}(D)$ 表示因果图 $D$ 所在的马尔可夫等价类，它包含了所有与 $D$ 共享同一骨架和同一 v-结构集合的因果图。这些图从数据角度完全无法区分，因此方向确定阶段最多只能输出一个“类”的表示，而不是唯一的图。
  1. 骨架相等图的边集完全一致——哪些节点之间有边、哪些没有，两张图一模一样，这是等价的基本前提。
    skeleton⁡(D′)=skeleton⁡(D)\operatorname{skeleton}(D') = \operatorname{skeleton}(D)
  2. 碰撞结构相等两张图不仅边相同，每条边附近的“汇聚点”（v-结构）也完全相同。这两项都相等，说明信息层面的差异已经无法用观测数据来分辨了。
    vstructures⁡(D′)=vstructures⁡(D)\operatorname{vstructures}(D') = \operatorname{vstructures}(D)
  3. 类大小概念$\mathcal{E}$ 里可能包含多个图，但它们互为“数据双胞胎”。方向确定输出的不是单一图，而是一个等价类的代表——也就是 CPDAG（部分有向无环图），用“有向边 + 无向边”的混合形式把整个类压缩表达。
    E(D)→代表CPDAG\mathcal{E}(D) \xrightarrow{\text{代表}} \text{CPDAG}

算法流程复杂度

你决定把整套方向确定流程固化成标准作业程序（SOP）。翻开经典的PC算法手册，你会发现方向确定只是其中的最后一章：前面几章已经完成了骨架学习，而方向确定阶段的职责，就是在这个骨架上做完最后的定向。整个流程环环相扣，每一环的得失都会传导到最终结果。

回顾PC算法的完整流水线：第一步，从零开始学习无向骨架——对所有节点对做条件独立性检验，剔除条件独立的边；第二步，确定每个节点对的分离集；第三步就是我们讨论的方向确定：先找v-结构，再用传播规则迭代。第三步的输入是前两步的输出，而第三步的输出就是最终交付的CPDAG。必须强调的是，骨架学习的好坏会直接影响方向确定——如果一条本应存在的边在第一步就被错误剔除，v-结构的识别就会跟着出错，方向传播也可能走向错误。

整个流程就像你给城市制定交通管理方案：先勘测路网（骨架学习），再标注汇聚点（v-结构识别），最后单向导流（传播规则）。每一步都有明确的输入输出，环环相扣，缺一不可。当流程跑完，你拿到的那张 CPDAG 就是整个城市交通方向规划的最终交付物。

T(n)=O ⁣(n2⋅2k)T(n) = \mathcal{O}\!\left(n^2 \cdot 2^{k}\right)
$T(n)$ 表示PC算法整体的时间复杂度。$n$ 是节点（变量）个数，$k$ 是条件集大小的上限（通常远小于 $n$）。$n^2$ 来自所有节点对两两组合的检查，$2^k$ 来自每个节点对需要尝试的潜在条件集合的指数级数量。
  1. 节点对组合需要对所有 $n$ 个节点做两两配对，所以存在 $n^2$ 量级的检查次数，这是复杂度下限的来源。
    (n2)=n(n−1)2=O(n2)\binom{n}{2} = \frac{n(n-1)}{2} = \mathcal{O}(n^2)
  2. 条件集检索对于每个节点对，还需要在它们邻居集合的子集中寻找最优的分离集，邻居数量上限为 $k$，候选子集数量是 $2^k$。
    ∑j=0k(kj)=2k\sum_{j=0}^{k} \binom{k}{j} = 2^k
  3. 总耗时两部分相乘，得到整体复杂度。现实中 $k$ 很小（稀疏图），因此算法在大规模稀疏图上依然可行；但若图变得稠密，$2^k$ 会迅速爆炸，这也是约束式方法面对高维数据时的瓶颈所在。
    O(n2⋅2k)\mathcal{O}(n^2 \cdot 2^k)

实际应用场景

方向确定阶段不是停留在理论层面的数学游戏，它在现实世界已经“驾驶”多年。每当你面对一张无向关联网络、想要从中提取有向因果关系时，v-结构识别和传播规则就会登场。

在基因调控网络推断中，科学家收集大量样本的基因表达量数据，先构建基因之间的关联网络（无向骨架），再套用方向确定算法识别调控方向——哪个基因是转录因子，哪条通路是它的下游目标。v-结构识别往往能锁定关键调控节点：两个基因都受第三个基因调控，这第三个基因很可能就是通路的核心开关。理解了方向，才能设计后续的基因敲除实验来验证。

在电商推荐的因果归因里，方向确定也大有用武之地。用户行为之间存在天然的因果链：看到广告 → 点击 → 加购 → 购买。如果只做关联分析，你分不清“点击”和“购买”谁是因谁是果；但在用户行为骨架图上应用v-结构识别，往往能找出“隐藏的混杂因素”（比如用户本身的购买意愿），从而更准确地归因每个环节对最终转化的真实贡献。有了方向，推荐系统才能回答“该干预哪个环节”的问题。

在工业故障根因分析中，大型设备的传感器节点组成一张庞大的告警关联图。方向确定阶段帮工程师从“哪些告警经常同时出现”升级到“哪个告警是源头、哪个告警是衍生”。识别出故障传播方向的v-结构后，运检人员能第一时间定位真正的故障点，而不是被一串连锁报警淹没。

从实验室的基因通路到电商平台的用户旅程，再到工厂车间的传感器网络，方向确定阶段一直在幕后默默“指路”。它做的事情始终如一：把无方向的关联升级为有方向的因果，同时诚实画出那条“数据无法逾越的红线”。

ρ=∣成功定向的边数∣∣骨架中的总边数∣\rho = \frac{|\text{成功定向的边数}|}{|\text{骨架中的总边数}|}
$\rho$ 衡量方向确定的有效性：成功定向的边占比越高，说明数据中蕴含的方向信息越充分。但$\rho$ 不高不代表算法失败——那些无法定向的边，正是马尔可夫等价类告诉你的“信息上限”。
  1. 定向边数经过 v-结构和传播规则后，最终被确定方向的有向边数量，代表数据中可识别的因果方向信息量。
    ∣有向边∣|\text{有向边}|
  2. 总边数无向骨架中的全部边数量，代表所有存在关联的变量对。
    ∣总边数∣|\text{总边数}|
  3. 比值意义$\rho$ 越接近1，说明因果方向越可识别；越接近0，说明数据中方向信息越稀缺。但无论$\rho$ 高低，输出CPDAG都忠实反映了当前数据能支持的最高方向粒度。
    0≤ρ≤10 \le \rho \le 1

AI 应用场景

基因调控网络中的方向推断

阶段：因果发现（约束式方法）中的方向确定环节

解决的问题：传统差异表达分析只能给出“哪些基因表达量变了”，无法回答“哪个基因调控哪个基因”。方向确定阶段在基因共表达网络上定位v-结构，识别上游转录因子与下游靶基因的调控方向，为 wet-lab 验证缩小候选范围。

具体案例：某癌症研究团队对 300 例肿瘤样本做 RNA-seq，构建无向基因共表达骨架后，用 v-结构识别锁定了一个同时在 TP53 与 MDM2 之间形成“汇聚点”的基因——ESR1。后续实验证实 ESR1 确实是两条通路交叉处的关键调控枢纽，为靶向药选择提供了新方向。

电商用户行为因果归因

阶段：因果推理（用户行为因果图谱构建）

解决的问题：AB测试只能验证单一干预的效果，但对于“看到广告 → 点击 → 加购 → 购买”的多环节链路，无法自动分辨每一环的真实因果方向。方向确定阶段在用户行为无向图上推出有向因果链，识别出真正的转化枢纽行为。

具体案例：某电商平台发现“加购”与“购买”高度相关，但方向不明。对用户行为骨架做方向确定后，发现“加购”和“收藏”共同指向“购买”（v-结构），说明二者都受用户购买意愿的驱动，而非互为因果。基于此，运营把优惠券策略从“促进收藏”调整为“直接刺激加购”，转化率提升12%。

工业设备故障根因定位

阶段：故障诊断（根因分析中的因果结构学习）

解决的问题：大型设备多个传感器告警同时触发时，传统关联规则只能告诉运维人员“它们经常一起出现”，无法指出“谁是源头”。方向的缺失导致运维人员逐个排查，平均故障恢复时间（MTTR）居高不下。

具体案例：某风电场 30 台风机频繁误报警，工程师对告警日志构建传感器关联骨架，方向确定阶段识别出“齿轮箱温度 → 主轴转速异常 ← 润滑压力低”的v-结构，定位润滑系统才是真正的故障根因。修复后，同一故障类型的误报警率下降70%。

Python 演示

python114 行
"""方向确定阶段：从无向骨架到马尔可夫等价类(CPDAG)的简化实现"""  def find_v_structures(nodes, adjacency, separators):    """识别v-结构：对三元组(X, Z, Y)，若X-Y不相邻，    且Z不在X与Y的分离集中，则定向为X→Z←Y"""    v_structs = []    n = len(nodes)    seen = set()    for x in range(n):        for y in range(n):            if x >= y or adjacency[x][y]:                continue            pair = (nodes[x], nodes[y])            sep = separators.get(pair, set())            for z in range(n):                if z == x or z == y:                    continue                if adjacency[x][z] and adjacency[y][z] and z not in sep:                    key = tuple(sorted([x, y, z]))                    if key not in seen:                        seen.add(key)                        v_structs.append((x, z, y))    return v_structs  def apply_rules(nodes, adjacency, directed):    """应用R1/R2/R3传播规则，直到没有新方向可确定"""    n = len(nodes)    changed = True    while changed:        changed = False        # R1: X→Y, Y-Z无向, X与Z不相邻 => Y→Z        for x in range(n):            for y in range(n):                if (x, y) not in directed:                    continue                for z in range(n):                    if z == x or z == y:                        continue                    ok = (adjacency[y][z] and not adjacency[x][z]                          and (y, z) not in directed and (z, y) not in directed)                    if ok:                        directed.add((y, z))                        changed = True        # R2: X→Y, Y→Z, X-Z无向 => X→Z        for x in range(n):            for y in range(n):                for z in range(n):                    if z == x or z == y:                        continue                    ok = ((x, y) in directed and (y, z) in directed                          and adjacency[x][z]                          and (x, z) not in directed and (z, x) not in directed)                    if ok:                        directed.add((x, z))                        changed = True        # R3: X→Y, Z→Y, Y-W无向, X与Z不相邻 => Y→W        for x in range(n):            for z in range(n):                if x == z or adjacency[x][z]:                    continue                for y in range(n):                    if y == x or y == z:                        continue                    if (x, y) not in directed or (z, y) not in directed:                        continue                    for w in range(n):                        if w == x or w == y or w == z:                            continue                        ok = (adjacency[y][w]                              and (y, w) not in directed and (w, y) not in directed)                        if ok:                            directed.add((y, w))                            changed = True    return directed  def main():    # 示例图：A-B、B-C、B-D，A与C不相邻    nodes = ['A', 'B', 'C', 'D']    n = len(nodes)    adjacency = [[False] * n for _ in range(n)]    for u, v in [('A', 'B'), ('B', 'C'), ('B', 'D')]:        i, j = nodes.index(u), nodes.index(v)        adjacency[i][j] = adjacency[j][i] = True    # 分离集：A与C的分离集不含B（本例中A-C不相邻，分离集设为空）    separators = {('A', 'C'): set()}    v_structs = find_v_structures(nodes, adjacency, separators)    print("识别到的v-结构：")    for x, z, y in v_structs:        print(f"  {nodes[x]} -> {nodes[z]} <- {nodes[y]}")    directed = set()    for x, z, y in v_structs:        directed.add((x, z))        directed.add((y, z))    directed = apply_rules(nodes, adjacency, directed)    print("\n定向结果（有向边列表）：")    for a, b in sorted(directed):        print(f"  {nodes[a]} -> {nodes[b]}")    undirected = []    for i in range(n):        for j in range(i + 1, n):            if (adjacency[i][j]                    and (i, j) not in directed                    and (j, i) not in directed):                undirected.append((i, j))    print("\n保留无向的边（等价类中不可定向）：")    for u, v in undirected:        print(f"  {nodes[u]} - {nodes[v]}")  if __name__ == "__main__":    main()
目的：在给定无向骨架和分离集信息的基础上，自动完成 v-结构识别与三条传播规则的迭代，最终输出一个部分有向图（CPDAG），完整复现方向确定阶段的核心流程。
  1. def find_v_structures(nodes, adjacency, separators):定义v-结构检测函数，三个参数分别表示节点列表、邻接矩阵和分离集字典，这是方向确定的第一棒。
  2. if x >= y or adjacency[x][y]: continue跳过重复组合和相邻节点对，只对不相邻的节点对寻找潜在的碰撞节点。
  3. if adjacency[x][z] and adjacency[y][z] and z not in sep:核心判定：Z同时与X、Y相邻，且Z不在X、Y的分离集中，说明Z是碰撞节点。
  4. directed.add((y, z))把检测到的v-结构方向记录到有向边集合中，为后续传播提供种子。
  5. while changed:传播规则的主循环，只要本轮有新的方向被确定，就继续下一轮，直到收敛。
  6. ok = (adjacency[y][z] and not adjacency[x][z] ... )R1规则的完整条件：Y-Z有边、X-Z无边、Y-Z尚未定向。
  7. for w in range(n):R3规则需要遍历Y的所有其他邻居，把“汇聚点”的出口方向全部推出。
  8. if __name__ == "__main__":程序入口，运行示例图定向流程并打印每个阶段的结果。

常见误区

误区方向确定阶段的目标就是给骨架上的每一条边都标上方向，如果留下无向边就说明算法不完善或者数据不够好。

正解这个想法就像要求交警必须给每条路都设成单行道，但现实中有些路就是双向通行的。因果方向也一样，马尔可夫等价类决定了某些边在观测数据中本质不可区分方向，无论增加多少样本量都无法定向。保留无向边不是算法的失败，而是对数据信息上限的诚实表达，CPDAG 正是这种“部分定向”的科学表示。

为何常见：初学者容易把“因果发现”误解为“一定能找到完整DAG”，忽略了同骨架同v-结构的不同图在统计上不可区分这一根本事实。

误区只要骨架中出现三条边构成V字形（X—Z—Y），就认定Z是碰撞节点，直接定向为X→Z←Y。

正解在实际的因果图中，X—Z—Y 的V字形也可能是“链式结构”X→Z→Y或者“分叉结构”X←Z→Y，两种结构在数据上都不违反条件独立性。要确认是碰撞结构，必须额外验证两个条件：X与Y不相邻，且Z不在X与Y的分离集中。只凭形状判断而跳过分离集验证，就像只看到路口形状相同就断定所有交汇路口都是汇聚点，必然会把链式通路误判成碰撞点。

为何常见：人脑对视觉形状非常敏感，V字形很容易被直觉当成碰撞结构的标志，但约束式方法的本质是“用条件独立性说话”，形状只是线索，检验才是依据。

误区R1、R2、R3三条规则反正最后都会收敛，先应用哪条都一样，随便写个循环就行。

正解虽然最终结果（CPDAG）是唯一确定的，但规则的应用顺序确实会影响中间过程，甚至影响能否应用某条规则。因为规则的应用前提是“某条边尚未定向”，一旦被其他规则抢先定向，另一条规则就可能不再适用。正确的做法是像上一节Python演示那样，用一个while循环反复扫描所有规则，直到某一轮完全没有新方向产生再停止——这样保证无论初始顺序如何，最终都收敛到同一个完整结果。

为何常见：人们天然地以为“逻辑规则具备可交换性”，但传播规则的触发条件彼此耦合，本质上是单调逻辑程序，必须以“不动点迭代”的方式运行。

误区现在定向不了是因为数据太少，只要收集更多样本，那些无向边最终都会被定向。

正解马尔可夫等价类告诉我们，某些边在任何规模的观测数据下都不可定向，因为同一等价类中的不同DAG会生成完全相同的联合分布。也就是说，这不是工程问题，而是理论边界。要突破这一边界，唯一的方法是引入额外信息：干预实验数据、时间先后顺序、背景知识中的部分方向约束等。增加样本量只能让骨架估计更精确，却无法消除等价类带来的方向模糊性。

为何常见：“量变引起质变”的直觉在小样本估计时成立，但碰到等价类这种结构上的不可辨识问题时，样本量再多也无效，这与估计误差完全不同。

误区先学好骨架，再做方向确定，两个阶段完全解耦，骨架的错误不会传导到方向结果。

正解v-结构识别的前提是“X与Y不相邻”，这个不邻接关系来自骨架学习阶段的条件独立性检验。如果骨架学习中某条边被误删（假阴性），原本能构成v-结构的路径就失效了；如果某条边被误留（假阳性），又可能伪造出虚假的碰撞结构。此外，分离集本身也是骨架学习阶段的副产品，它的准确性直接影响v-结构判定。因此方向确定阶段的可靠性严格受限于骨架学习的质量，二者是流水线上紧密咬合的齿轮，而不是两个孤立的模块。

为何常见：模块化封装容易让人误以为各阶段“各自扫地、互不打扰”，但流水线的特点是上一站的良率决定下一站的上限——骨架就是那道最容易被忽略的质量关卡。

面试题

Q1. 方向确定阶段的核心任务是什么？

单选题 · easy

  • A.学习变量之间的无向关联骨架
  • B.为骨架上的边确定因果方向并保留不可定向边← 正确答案
  • C.计算所有变量的条件独立检验
  • D.拟合回归模型预测变量取值

答案：B。方向确定是在骨架基础上进行的定向推理，核心是识别v-结构、应用传播规则，最终输出CPDAG。A是骨架学习阶段的任务，C是骨架学习的工具，D则是统计预测，均不属于方向确定。

Q2. v-结构（碰撞结构）在骨架中的典型形态是？

单选题 · easy

  • A.X—Y—Z，三条边呈直线链路
  • B.X→Y←Z，两侧箭头同时汇聚于Y← 正确答案
  • C.X—Y和Y—Z，且X与Z相邻
  • D.X←Y→Z，Y同时指向两侧

答案：B。v-结构的本质是两条边都指向同一个节点，即X→Y←Z，Y被称为碰撞节点。A是链式结构，C中的X-Z相邻破坏了碰撞条件，D是分叉结构，都不是v-结构。

Q3. 识别v-结构时，以下哪个条件不是必须验证的？

单选题 · mid

  • A.X与Y在骨架中不相邻
  • B.Z不在X与Y的分离集中
  • C.X与Y之间的偏相关系数为零← 正确答案
  • D.X与Z相邻且Y与Z相邻

答案：C。v-结构判定需要X-Y不相邻、Z同时与X、Y相邻、Z不在分离集中。C“偏相关系数为零”对应条件独立性成立，是"Z∈Sep(X,Y)"的等价表现，恰好是v-结构不成立的情形，因此不是必需验证条件，且情形相反。

Q4. R1传播规则的完整前提是什么？

单选题 · mid

  • A.X→Y且Y-Z有边且X与Z不相邻← 正确答案
  • B.X→Y且Y-Z有边且X与Z相邻
  • C.X→Y且X-Z无向边
  • D.X→Y且Y→Z且X-Z无向

答案：A。R1要求已有X→Y，Y连到未定向的Z，且X与Z不相邻，才推出Y→Z。B中X与Z相邻会形成新的碰撞嫌疑，C缺少Y-Z的边，D是R2的前提条件，均不正确。

Q5. 马尔可夫等价类中，两个DAG被认为是等价的，当且仅当？

单选题 · mid

  • A.有向边数量完全相同
  • B.骨架相同且v-结构集合相同← 正确答案
  • C.节点数相同且节点名称相同
  • D.拓扑排序完全相同

答案：B。等价类的定义是骨架（边集）和v-结构集合都相同。A只比较边的数量，无法保证结构一致；C只比较节点；D的拓扑排序依赖边的方向，不能作为等价判据。

Q6. 在PC算法中，方向确定阶段之后仍然保留的无向边表示什么？

单选题 · hard

  • A.算法尚未收敛，需要增加迭代次数
  • B.样本量不足，需要采集更多数据
  • C.该边在马尔可夫等价类内方向不可辨识← 正确答案
  • D.该边对应的变量之间不存在因果关系

答案：C。无向边意味着当前数据无法区分两个相反方向，即等价类内方向不可辨识。A和B是工程性误解——增加迭代或样本无法改变等价类的理论边界；D也不成立，无向边表示确实存在关联，只是方向未定。

Q7. 以下哪些操作可以突破马尔可夫等价类的方向模糊性？

多选题 · mid

  • A.增加观测样本的容量
  • B.进行随机干预实验（do-calculus）← 正确答案
  • C.融合时间先后顺序等背景知识← 正确答案
  • D.对数据进行Z-score标准化

答案：BC。干预实验能够改变因果结构下的分布模式，打破等价类的统计对称性；时间顺序等背景知识能直接排除某些方向。A增加样本只能提高骨架估计精度，无法消除等价类；D只是数据变换，不携带方向信息。

Q8. 关于v-结构识别错误的原因，以下说法正确的是？

多选题 · hard

  • A.骨架学习中误删一条边会导致真实v-结构无法被识别← 正确答案
  • B.分离集估计错误可能导致将链结构误判为v-结构← 正确答案
  • C.只要条件独立性检验足够准确，v-结构识别就不会出错
  • D.v-结构识别的错误在传播阶段会被放大，影响更多边的定向← 正确答案

答案：ABD。A正确——骨架边被误删后，碰撞条件“X与Y相邻”不满足，v-结构必然丢失。B正确——分离集判断错误是假阳性v-结构的主要来源。D正确——错误的种子方向会在传播规则中扩散。C错误——检验本身在高维或非线性场景难以做到绝对准确，且样本误差始终存在。

Q9. CPDAG（部分有向无环图）是什么？

单选题 · easy

  • A.所有边都有方向的完全因果图
  • B.同时包含有向边和无向边的等价类代表图← 正确答案
  • C.仅包含无向边的骨架图
  • D.仅保存v-结构的简化图

答案：B。CPDAG是马尔可夫等价类的代表性表示，其中可定向的边以有向箭头呈现，不可定向的边保留无向形式。A是完全DAG，C是无向骨架，D丢弃了非碰撞边的方向信息，都不完整。

Q10. 方向传播规则R2解决了什么问题？

多选题 · mid

  • A.防止因果图中出现有向环← 正确答案
  • B.将多个碰撞结构连接成完整方向图
  • C.利用已有链式路径推断缺失方向← 正确答案
  • D.消除无向骨架中的冗余边

答案：AC。R2的前提是有向链X→Y→Z加上无向边X-Z，它的定向X→Z避免了形成X→Y→Z→X的有向环，同时利用这条有向链推断了缺失方向，因此A和C正确。R2既不涉及多个碰撞结构的连接（那是R3及相关规则的功能），也不删除边（骨架学习才做删边），B和D错误。