变量消元、消息传递与精确推断

推断查询先写成未归一权重

设联合分布已分解为因子乘积 $p(x)=\prod_a f_a(x_a)$，查询变量为 $Q$，证据为 $E=e$，其余隐藏变量为 $H$。先把证据值代入所有相关因子，再计算

这得到每个 $q$ 的未归一权重。最后除以

才有 $p(q\mid e)$。分母也是证据似然，可用于核对：归一化后所有查询配置之和应为一。若 $p(e)=0$，条件分布在当前模型中没有定义，不能用除零后的任意数替代。

直接枚举全部隐藏配置的成本随变量数指数增长。精确推断的关键不是改变结果，而是利用分配律，把只涉及局部变量的因子先相乘、及时求和，避免重复计算。

边缘概率与最可能配置不是同一个查询

边缘推断对隐藏变量求和，保留查询变量的全部概率质量；联合最大后验则寻找使 $p(x\mid e)$ 最大的一整组配置，常把求和替换为最大并保存回溯指针。单变量边缘各自最可能取值拼在一起，未必构成联合最可能配置，因为变量间约束可能让该组合概率很低甚至为零。

若只对部分变量取最大、对其余隐藏变量求和，得到边缘最大后验查询。求和与最大通常不可交换：先消去哪些变量会改变目标含义，不再只是成本选择。实现前应明确需要完整后验、单点边缘、联合最可能配置还是部分最大化；本章以下的 sum-product 主要计算边缘与条件概率。

因子运算围绕作用域展开

因子 $f(X_A)$ 是变量子集 $A$ 上的非负表或函数。两个因子相乘时，结果作用域是并集，共享变量按相同取值对齐；对变量 $Z$ 求和时，从因子作用域中删除 $Z$：

代入证据也会删除已固定变量维度。运算顺序影响最大中间表，却不改变精确代数结果。实现中应在每一步记录变量顺序和域大小，否则同名维度错位会产生看似归一但错误的答案。

变量消元逐个缩并隐藏变量

给定一个隐藏变量消元顺序。处理变量 $Z$ 时，取出所有包含 $Z$ 的因子，先把它们相乘，再对 $Z$ 求和，把新因子放回集合。没有 $Z$ 的因子暂时不动。全部隐藏变量消完后，相乘剩余因子得到查询的未归一权重，再归一化。

这一过程相当于动态规划：新因子总结已经消去部分对其边界变量的全部贡献。同一变量只能在收集了所有含它的当前因子后消去；漏掉一个因子会错误地把相关项拆开。查询变量不消去，证据变量先固定。

消元顺序决定中间因子大小

消去变量时，它当前所有邻居会共同出现在新因子作用域中；图上可理解为先把这些邻居连接成团，再删除该变量，新添的连接叫填充边。若变量域大小至多为 $K$，作用域含 $r$ 个变量的稠密表需要 $O(K^r)$ 存储和运算，所以最大中间作用域比因子数量更关键。

寻找最小宽度顺序一般困难，常用最小度、最小填充等启发式：每步优先消去当前邻居少或新增边少的变量。启发式不保证全局最优，应在实际域大小上估计中间表，而不是只数顶点；一个有上千取值的变量可能比多个二元变量更昂贵。

诱导宽度与树宽解释指数项

某个消元顺序的诱导宽度可定义为消去每个变量时其尚存邻居数的最大值，等价地比最大生成团大小少一。图的树宽是所有顺序中最小诱导宽度。对最大域大小 $K$ 的离散模型，典型精确消元成本含 $K^{w+1}$ 的指数项，其中 $w$ 为所用顺序宽度；变量数主要乘在外面。

树的树宽为一，因此局部消息可在线性数量的边上完成。网格即使每个节点度数不大，消元仍会形成越来越宽的边界，树宽随较短边增长。稀疏不等于低树宽，局部邻居少也不保证精确推断容易。

树宽属于图结构，但有效成本还取决于证据、确定性、稀疏因子和上下文特定独立。通用稠密表上界可能很保守；若实现利用零值或代数结构，可以更快。不过没有说明利用方式时，不能用特殊实例否认最坏复杂度。

树上 sum-product 是有缓存的局部消元

在树状因子图上，从任意变量选根。先从叶向根收集消息，再从根向叶分发。变量到因子的消息是除目标因子外所有入站消息的乘积；因子到变量的消息对该因子其余变量求和：

变量 $i$ 的未归一边缘是所有相邻因子消息之积，再归一化。树上任意子树只通过一条边与其余部分连接，所以一条消息正是该子树消元后的边界因子；每个方向计算一次即可复用。若只要一个根边缘，收集一遍足够；若要所有单点边缘，需要再分发一遍。

有环图上的普通消息不再自动精确

若因子图有环，沿边反复使用同一局部消息会重复计入信息。所谓 loopy belief propagation 有时收敛并给出有用近似，但一般不保证收敛，也不保证精确。若任务要求精确结果，应使用变量消元或先构造团树，而不能因为更新公式相同就沿环运行后宣称精确。

团树把消元产生的团作为节点，相邻团共享分隔集，并满足运行交集性质：含某变量的全部团在树上连通。把原因子分配到包含其作用域的团，执行团间和积消息，校准后可读出团边缘。团树把一般图转为树上计算，但团状态数仍由树宽指数控制。

数值缩放与零证据必须显式处理

长链上许多小概率相乘会下溢。树消息可在每步除以正比例常数，并累计缩放因子；边缘归一化不受消息整体正缩放影响。对最大积或对数线性因子常在对数域计算，求和时使用稳定的对数和指数技巧。零势需要保留为真正不可能配置，不能为避免对数零而无依据改成小正数。

证据似然是重要诊断。若归一化常数极小，后验可能对参数误差敏感；若为零，说明证据与模型支持冲突或实现有误。单点边缘之和为一、相邻团在分隔集上的边缘一致、直接枚举小实例与消元一致，都是精确实现的基本核对。

精确结果仍受模型假设限制

精确推断表示对给定因子和浮点容差准确计算，不表示图结构、参数或数据机制正确。错误的条件独立、未建模潜变量和分布偏移会让精确后验精确地回答错误模型。应把计算误差、近似误差、参数不确定性和模型错设分开。

练习

关系与资源

• 贝叶斯网络与 Markov 随机场 提供条件因子、势函数和图分离语义。
• 动态规划与图算法 支持消元顺序、树遍历和结果复用。
• 条件概率 解释证据归一化和后验查询。
• 图、连通性与匹配 提供团、路径和树结构语言。
• EM 算法与变分推断 使用后验边缘并处理精确推断不可行的情形。
• 无监督学习与概率图模型综合复习 汇总结构、推断与近似边界。