无向图、势函数与因子图

层级：C｜建议先修：05-05、07-01、08-01

无向概率图模型用没有方向的边表达变量之间的局部相互作用。它不强调生成先后，适合描述空间一致性、约束和对称关系。

1. Markov 随机场

设无向图 $G=(V,E)$ 的每个节点对应随机变量 $X_v$。一个对图满足 Markov 性质的正分布，可按最大团分解为

其中：

• $\mathcal C$ 是团的集合，常取最大团；
• $\psi_C(\mathbf x_C)>0$ 是势函数；
• $Z$ 是配分函数。

2. 势函数不是概率

势函数给不同局部配置分配非负权重，但它通常不归一化，也不一定有独立概率含义。联合分布由所有势函数相乘后再统一归一化。

配分函数为

或连续情形下的积分。高维模型中计算 $Z$ 往往是主要难点。

3. 能量形式

令 $\psi_C(\mathbf x_C)=e^{-E_C(\mathbf x_C)}$，则

低能量状态概率高，高能量状态概率低。这种形式连接了统计物理、Boltzmann 机和能量模型。

4. 图分离与条件独立

在无向图中，规则比 DAG 简单：若节点集合 $S$ 截断了 $A$ 到 $B$ 的所有路径，则

局部 Markov 性质是：给定节点的所有邻居后，该节点与图中其余非邻居条件独立。

5. Hammersley–Clifford 定理

若联合分布处处为正，则它对无向图满足全局 Markov 性质，当且仅当它可按图的团进行势函数分解。正性条件很重要；含零概率的硬约束模型需要更谨慎处理。

6. 成对 Markov 随机场

若只有单节点势和边势，

例如图像去噪中，$\psi_i$ 衡量像素标签与观测的一致性，$\psi_{ij}$ 鼓励相邻像素取相同标签。

7. Ising 模型示例

令 $x_i\in\{-1,+1\}$，

若 $J_{ij}>0$，相邻变量倾向相同；若 $J_{ij}<0$，倾向相反。它是二元 Markov 随机场与 Boltzmann 机的基本原型。

8. 因子图

因子图是二部图，包含：

• 变量节点 $x_i$；
• 因子节点 $f_a$；
• 若因子 $f_a$ 依赖变量 $x_i$，二者之间连边。

联合函数写为

因子图比普通无向图更明确地显示每个因子的作用域，也是和积算法、最大乘积算法等消息传递的自然表示。

9. 条件随机场

条件随机场（CRF）直接建模 $p(\mathbf y\mid\mathbf x)$：

它无需给输入 $\mathbf x$ 建模，适合序列标注等条件预测任务。线性链 CRF 可用动态规划高效计算配分函数和边缘概率。

10. DAG 与无向图的差别

• DAG 用局部条件概率，归一化通常自动成立；
• 无向图用势函数，通常需要全局配分函数；
• DAG 的独立性使用 d-分离；无向图使用普通图分离；
• DAG 适合表示有方向的生成过程；无向图适合对称相互作用。

二者可以相互转换一部分结构，但可能引入额外边，且独立语义不总能完全保留。

11. 易错点

1. 势函数值大于 1 完全可以，因为它不是概率。
2. 只写 $p\propto\prod\psi$ 时不能忘记配分函数会依赖参数。
3. 参数学习时 $\nabla\log Z$ 往往需要模型分布下的期望，可能很难计算。
4. 无向边不表示双向因果。

常见问答

Q1：为什么要求势函数非负？
相乘后要形成概率权重，负值无法归一化成合法概率。常用严格正值以满足相关定理条件。

Q2：配分函数只是一个常数，为什么麻烦？
对给定参数它对状态是常数，但参数学习时它随参数变化；其求和覆盖指数多的联合状态。

Q3：因子图和 Bayesian 网络一样吗？
不一样。因子图显式表示函数因子，可表示有向或无向模型的分解；Bayesian 网络则有明确的有向条件概率语义。

Q4：什么时候更适合使用 CRF？
当目标是给定输入预测结构化标签，且希望灵活使用相互依赖的特征而无需为输入建立生成模型时。

练习

1. 写出三节点链 $X_1-X_2-X_3$ 的成对势函数分解。
2. 说明给定 $X_2$ 后为何 $X_1\perp X_3$。
3. 将 $p(\mathbf x)\propto e^{-E(\mathbf x)}$ 写成团能量之和的形式。
4. 画出因子分解 $f_1(x_1,x_2)f_2(x_2,x_3)f_3(x_3)$ 的因子图。

答案与提示

1. 如 $p=Z^{-1}\psi_1(x_1)\psi_2(x_2)\psi_3(x_3)\psi_{12}(x_1,x_2)\psi_{23}(x_2,x_3)$。
2. $X_2$ 截断了 $X_1$ 到 $X_3$ 的唯一图路径。
3. 令 $E=\sum_CE_C$，则每个势函数 $\psi_C=e^{-E_C}$。
4. 使用三类方形因子节点，分别连接其参数中的圆形变量节点。