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

层级：C｜建议先修：05-08、08-02、08-04、08-06

概率图模型定义了联合分布，但实际问题通常只需要某些边缘概率、条件概率或最可能配置。精确推断的关键是利用因子分解，避免枚举全部联合状态。

1. 推断任务

给定联合分布 $p(\mathbf x)$ 和证据 $X_E=e$ ，常见查询包括：

边缘： $p(X_Q)$ ；
条件边缘： $p(X_Q\mid X_E=e)$ ；
归一化常数或证据概率： $p(X_E=e)$ ；
MAP： $\arg\max_{x_Q}p(x_Q\mid e)$ ；
MPE：所有未观测变量的最可能联合赋值。

求和推断与最大化推断形式相似，但运算顺序不能随意互换。

2. 暴力枚举的代价

若有 $n$ 个 $K$ 状态变量，完整联合表有 $K^n$ 项。计算一个边缘概率若直接遍历所有隐藏变量，复杂度指数增长。

图模型的分解让我们可以利用分配律：

\sum_x f(x)g(y)=g(y)\sum_xf(x),

把与被消元变量无关的因子留在求和之外。

3. 变量消元算法

设联合函数分解为 $\prod_af_a(\mathbf x_a)$ ，要消去变量 $Z$ ：

找出所有包含 $Z$ 的因子；
将这些因子相乘；
对 $Z$ 求和，生成一个不含 $Z$ 的新因子；
用新因子替换原因子；
按选定顺序继续消元。

最后对查询变量归一化。

4. 一个链式例子

若

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

要计算 $p(d)$ ，可依次构造

m_1(b)=\sum_ap(a)p(b\mid a),

m_2(c)=\sum_bm_1(b)p(c\mid b),

p(d)=\sum_cm_2(c)p(d\mid c).

中间因子始终只涉及一个变量，而不是构造完整四维表。

5. 消元顺序决定复杂度

不同消元顺序会产生大小悬殊的中间因子。消去一个变量时，其所有尚存邻居会在诱导图中互相连接，这叫填边。

最大中间团的大小由诱导宽度控制；最佳消元顺序的寻找本身通常是困难问题。常用启发式包括：

min-degree：优先消当前邻居最少的变量；
min-fill：优先消引入填边最少的变量；
weighted min-fill：同时考虑变量状态数。

6. 树宽

图的树宽可理解为最佳消元顺序下“最大团大小减一”。精确推断复杂度通常对树宽呈指数增长，而不是简单对节点数指数增长。

因此很长的链树宽只有 1，可以高效推断；节点不多但高度稠密的图仍可能非常困难。

7. 和积消息传递

在无环因子图上，边缘概率可通过 sum-product 算法精确计算。变量到因子的消息为

m_{i\to a}(x_i)=\prod_{b\in N(i)\setminus a}m_{b\to i}(x_i),

因子到变量的消息为

m_{a\to i}(x_i) =\sum_{\mathbf x_{a\setminus i}} f_a(\mathbf x_a) \prod_{j\in N(a)\setminus i}m_{j\to a}(x_j).

节点边缘与所有入消息的乘积成正比。

8. 最大乘积与最大和

把 sum-product 中的求和换成最大值，得到 max-product，用于寻找最可能配置。在对数域中，乘积变成求和，称为 max-sum。

要恢复完整 MAP 配置，需要像 Viterbi 一样保存每次最大化的回溯指针。

9. 树上的消息为何精确

树中任意两点只有一条路径。沿一条边切开树后，两侧变量仅通过边界节点或因子相连，因此消息可以概括一整侧子树对边界变量的贡献，不会重复计数。

通常先从叶到根收集消息，再从根到叶分发消息；经过两个方向后可得到所有节点边缘。

10. 有环图上的 loopy belief propagation

在有环图上仍可迭代相同消息公式，称为 loopy BP。它可能收敛并给出不错近似，也可能振荡或不收敛；即便收敛，通常也不保证边缘精确。

阻尼更新

m^{new}\leftarrow(1-\rho)m^{old}+\rho\tilde m

有时可改善稳定性，但不是普遍保证。

11. Junction tree

一般图可通过道德化、三角化和构造团树转化为 junction tree，再在团之间传递消息实现精确推断。团节点的状态空间随团大小指数增长，因此其复杂度仍由树宽决定。

12. 易错点

证据变量应先把对应因子限制到观察值，减少因子维度。
求和与最大化不总能交换，边缘 MAP 比纯求和或纯最大化更复杂。
消元顺序影响效率，不影响精确结果。
在有环图上直接套 BP 公式变成近似算法，不能再声称一定精确。

常见问答

Q1：变量消元和动态规划是什么关系？
二者都利用分解和分配律缓存中间结果。前向算法、Viterbi 都可看作特定链图上的变量消元。

Q2：为何链很长也容易推断？
链的树宽固定为 1，中间因子最多只连接相邻少数变量，复杂度随长度线性增长。

Q3：消息需要归一化吗？
理论上比例常数可在最终边缘统一归一化；实践中经常每步归一化以避免上溢或下溢。

Q4：精确推断失败是因为节点太多吗？
更准确地说是树宽和变量状态数太大。许多节点组成的树仍可高效推断。

练习

对因子 $f(a,b)g(b,c)h(c,d)$ 写出消元 $a,b,c$ 后求关于 $d$ 的函数的步骤。
解释消元时为什么会在变量的邻居之间产生填边。
写出树形因子图上变量节点的未归一化 belief。
比较 sum-product 与 max-product 的目标。

答案与提示

$m_1(b)=\sum_af(a,b)$ ， $m_2(c)=\sum_bm_1(b)g(b,c)$ ， $m_3(d)=\sum_cm_2(c)h(c,d)$ 。
包含被消元变量的因子相乘并求和后，新因子同时依赖其所有剩余邻居，使它们形成团。
$b_i(x_i)\propto\prod_{a\in N(i)}m_{a\to i}(x_i)$ 。
前者对隐藏配置求和并算边缘，后者对隐藏配置取最大值并找最佳联合赋值。