9.5 推断算法：变量消除、信念传播与采样方法

9.5 推断算法：变量消除、信念传播与采样方法

在建立了概率图模型的结构与参数化形式后，核心任务之一是进行概率推断，即根据已知的观测变量（证据）计算查询变量的后验概率分布，或计算所有未观测变量的联合状态概率。由于模型通常涉及大量变量，直接对联合分布进行求和或积分在计算上是不可行的。推断算法的设计旨在利用图模型所编码的条件独立性结构，高效、准确地完成上述计算。本节将系统阐述三类核心推断算法：适用于任意图结构但可能计算复杂的精确推断算法变量消除；在树状结构上高效精确、并可推广至一般图进行近似推断的信念传播；以及处理高维、复杂分布时必不可少的采样方法。

9.5.1 精确推断：变量消除算法

变量消除是精确推断中最基础、最直观的算法。其核心思想是通过动态地重新排列求和（或积分）顺序，并利用模型中的因子分解结构，逐步“消除”非查询变量，从而避免对整个高维联合概率表的直接计算[1]。

9.5.1.1 算法原理与步骤

考虑一个由变量集X={ X1,X2,...,Xn}\mathbf{X} = \{X_1, X_2, ..., X_n\}X={X1​,X2​,...,Xn​}构成的概率图模型（贝叶斯网络或马尔可夫网络），其联合分布由一组因子的乘积表示：P(X)=∏iϕi(Di)P(\mathbf{X}) = \prod_{i} \phi_i(\mathbf{D}_i)P(X)=∏i​ϕi​(Di​)，其中Di\mathbf{D}_iDi​是因子ϕi\phi_iϕi​的作用变量集。给定证据E=e\mathbf{E} = \mathbf{e}E=e，我们欲计算查询变量YYY的后验边缘概率P(Y∣E=e)P(Y | \mathbf{E}=\mathbf{e})P(Y∣E=e)。

根据贝叶斯规则和边缘化，有：
P(Y∣e)∝P(Y,e)=∑zP(Y,e,Z=z) P(Y | \mathbf{e}) \propto P(Y, \mathbf{e}) = \sum_{\mathbf{z}} P(Y, \mathbf{e}, \mathbf{Z} = \mathbf{z})P(Y∣e)∝P(Y,e)=z∑​P(Y,e,Z=z)
其中Z=X∖{ Y,E}\mathbf{Z} = \mathbf{X} \setminus \{Y, \mathbf{E}\}Z=X∖{Y,E}是需要被边缘化的所有非查询非证据变量。将联合分布代入：
P(Y,e)=∑z∏iϕi(Di,e) P(Y, \mathbf{e}) = \sum_{\mathbf{z}} \prod_{i} \phi_i(\mathbf{D}_i, \mathbf{e})P(Y,e)=z∑​i∏​ϕi​(Di​,e)
变量消除算法通过以下步骤计算该和：

1. 因子乘积：将所有涉及证据变量E\mathbf{E}E的因子进行实例化（将E\mathbf{E}E固定为e\mathbf{e}e），并与其余因子相乘，得到一组新的因子{ τj}\{\tau_j\}{τj​}。
2. 逐个消除变量：选择一个变量消除顺序π\piπ（例如Z1,Z2,...,ZmZ_1, Z_2, ..., Z_mZ1​,Z2​,...,Zm​）。对于顺序中的每个变量ZkZ_kZk​：
   a. 找出所有包含ZkZ_kZ