有向无环图、拓扑序与因子分解

层级：B｜建议先修：08-01、05-03、05-08

有向无环图（DAG）既能描述依赖方向，又避免循环定义。Bayesian 网络用 DAG 把高维联合分布分解成一组局部条件概率。

1. DAG 的定义

有向图中，边 $u\to v$ 表示从 $u$ 指向 $v$ 。若不存在沿箭头方向出发又回到原节点的有向环，则称为有向无环图。

对节点 $X_i$ ：

DAG 的拓扑序是节点的一个线性排列，使每条边的起点都出现在终点之前。一个图存在拓扑序，当且仅当它是 DAG。

Kahn 算法：

拓扑序通常不唯一。它表示一种与依赖方向兼容的计算或生成顺序。

任意联合分布都可按某个变量顺序分解：

p(x_1,\ldots,x_n) =\prod_{i=1}^np(x_i\mid x_1,\ldots,x_{i-1}).

这个恒等式本身不带独立假设，但后面的条件集合会越来越大。

若一个联合分布对 DAG $G$ 因子分解，则

p(x_1,ldots,x_n) =\prod_{i=1}^np(x_i\mid \operatorname{Pa}(X_i)).

每个变量只依赖自己的父节点，而无需依赖拓扑序中全部前驱。这能大幅减少参数数量并暴露条件独立结构。

例如 $A\to B$ 、 $A\to C$ 、 $B\to D$ 、 $C\to D$ ，则

p(a,b,c,d)=p(a)p(b\mid a)p(c\mid a)p(d\mid b,c).

在 Bayesian 网络中，每个节点在给定其父节点后，与自己的非后代条件独立。形式上，

X_i\perp \operatorname{NonDesc}(X_i)\mid \operatorname{Pa}(X_i),

其中要排除父节点本身。这个局部性质与因子分解密切相关。

可按拓扑序采样：

因此 DAG 不仅是计算图，也可定义数据的联合生成过程。

三个节点有三种典型连接：

链和分叉中，给定中间节点 $Z$ 会阻断 $X,Y$ 的路径；对撞结构中，不观测 $Z$ 时路径阻断，观测 $Z$ 或其后代反而可能让 $X,Y$ 相关。这是 d-分离的核心。

不同方向的 DAG 可能表达相同的条件独立集合。两个 DAG 若具有相同骨架和相同对撞结构，则 Markov 等价。

因此只从观察数据中的独立关系，通常无法识别所有边方向；因果方向还需要时间顺序、干预数据或额外假设。

若 $n$ 个二值变量完全联合建模，需要 $2^n-1$ 个自由参数。若某 DAG 中每个节点最多有 $k$ 个父节点，每个条件概率表的规模约为 $2^k$ ，总参数规模约为 $O(n2^k)$ 。稀疏图以结构假设换取统计和计算效率。

Q1：任何联合分布都能用 DAG 表示吗？
可以用完全 DAG 按链式法则表示，但未必得到参数节省。稀疏 DAG 需要真实的条件独立结构。

Q2：删除一条边意味着什么？
意味着加入某种条件独立假设，使子节点的条件分布不再直接依赖该父节点候选。

Q3：为什么 DAG 不能有环？
有环时无法给出父先子后的拓扑生成顺序，局部条件分布也未必能组成合法联合分布。

Q4：神经网络计算图也是 Bayesian 网络吗？
普通确定性计算图描述数值运算，不一定表示随机变量联合分布。若节点具备概率语义并满足相应分解，才是概率图模型。