因子图与消息传递算法

1 引言

因子图（Factor Graph）是概率图模型中一种重要的表示形式，它将联合分布分解为多个局部函数的乘积，并通过消息传递算法进行高效推断。本章系统介绍因子图的基础理论、核心算法及其与深度学习的联系。

2 因子图基础

2.1 定义与表示

定义：因子图是一个二部图 $G=(X,F,E)$，包含：

• 变量节点集合 $X=\{x_1,x_2,\dots ,x_n\}$
• 因子节点集合 $F=\{f_1,f_2,\dots ,f_m\}$
• 边集合 $E\subseteq X\times F$，表示变量与因子的连接关系

因子函数的分解：

设 $X_a$ 表示与因子 $f_a$ 相连的变量集合，联合分布可以分解为：

$$p(X)=\frac{1}{Z}\prod _{a=1}^m{f}_a(X_a)$$

其中 $Z={\sum }_X{\prod }_a{f}_a(X_a)$ 是归一化常数（配分函数）。

2.2 例子：图像去噪

考虑一个简单的图像去噪问题。设观测图像为 $Y$，真实图像为 $X$（二值像素）。

因子分解：

$$p(X\mid Y)\propto \underset{\text{数据项}}{\underbrace{\prod _{i}p(y_i\mid x_i)}}\cdot \underset{\text{平滑项}}{\underbrace{\prod _{(i,j)\in E}\psi (x_i,x_j)}}$$

其中：

• $p(y_i\mid x_i)$ 是似然因子（数据保真）
• $\psi (x_i,x_j)$ 是平滑因子（鼓励相邻像素相似）

3 和-积算法

3.1 边缘分布计算

和-积算法（Sum-Product Algorithm）的目标是高效计算边缘分布：

$$p(x_i)=\sum _{X\setminus \{x_i\}}p(X)=\frac{1}{Z}\sum _{X\setminus \{x_i\}}\prod _a{f}_a(X_a)$$

3.2 消息传递规则

从变量到因子：

$${\mu }_{x_i\to f_a}(x_i)=\prod _{b\in N(i)\setminus a}{\mu }_{f_b\to x_i}(x_i)$$

从因子到变量：

$${\mu }_{f_a\to x_i}(x_i)=\sum _{X_a\setminus \{x_i\}}{f}_a(X_a)\prod _{j\in N(a)\setminus i}{\mu }_{x_j\to f_a}(x_j)$$

其中 $N(i)$ 表示变量 $x_i$ 的邻居因子集合。

3.3 边缘分布计算

当所有消息传递完成后，边缘分布为：

$$p(x_i)\propto \prod _{a\in N(i)}{\mu }_{f_a\to x_i}(x_i)$$

4 变分消息传递

4.1 变分推断框架

当精确推断困难时，使用变分消息传递进行近似：

$$q(X)\approx p(X\mid Y)$$

其中 $q(X)$ 是变分分布。

4.2 平均场近似

平均场假设：变分分布可以被分解为：

$$q(X)=\prod _{i=1}^n{q}_i(x_i)$$

目标：最小化 $\text{KL}(q\Vert p)$，等价于最大化ELBO。

4.3 变分消息更新

变量消息：

$$\log q_i(x_i)\propto {\mathbb{E}}_{q_{-i}}[\log p(X)]+\text{const}$$

因子消息：

$${\mu }_{f_a\to x_i}(x_i)\approx \exp \left({\mathbb{E}}_{q_{X_a\setminus \{x_i\}}}[\log f_a(X_a)]\right)$$

5 与神经网络的联系

5.1 消息传递作为神经网络层

消息传递规则可以重新解释为神经网络操作：

• 聚合操作 ≈ 注意力机制
• 消息函数 ≈ MLP层
• 更新操作 ≈ 残差连接

5.2 可微分消息传递

class DifferentiableSumProduct(nn.Module):
    """可微分的和-积算法"""
    
    def __init__(self, dim):
        super().__init__()
        self.msg_net = nn.Sequential(
            nn.Linear(dim, dim),
            nn.ReLU(),
            nn.Linear(dim, dim)
        )
        
    def forward(self, node_features, factor_msg):
        # 消息聚合
        aggregated = node_features.sum(dim=0, keepdim=True)
        # 消息函数
        return self.msg_net(aggregated)

6 总结

因子图和消息传递算法为概率推断提供了高效的计算框架，同时也是理解图神经网络和注意力机制的重要理论基础。

---

参考文献