期望传播

1. EP核心原理

1.1 算法概述

期望传播（Expectation Propagation, EP）是一种用于近似贝叶斯推断的确定性算法，由Minka在2001年提出。¹ EP统一并扩展了两种先前技术：假设密度滤波（Assumed-Density Filtering, ADF）和环状信念传播（Loopy Belief Propagation）。¹

EP的核心思想是：通过迭代地将精确因子替换为近似因子来近似后验分布。与变分推断（VI）类似，EP选择一个近似分布族来逼近真实后验；与信念传播（BP）不同，EP传播的是充分统计量的期望（如均值和方差），而非精确的信念状态。

1.2 与变分推断的关系

变分推断（VI）和期望传播都是近似贝叶斯推断的框架，但存在关键区别：

特性	变分推断 (VI)	期望传播 (EP)
优化方向	$\text{KL}(q\Vert p)$，即 ${\min }_q\text{KL}(q\Vert p)$	$\text{KL}(p\Vert q)$，即 ${\min }_q\text{KL}(p\Vert q)$
近似形式	全局变分分布 $q(\theta )$	局部近似因子的乘积 $q(\theta )\propto {\prod }_i{\tilde{f}}_i(\theta )$
消息传递	坐标上升或梯度下降	迭代因子精炼（refinement）
准确性	通常低估后验不确定性	通常更准确，保留更多后验结构

从数学上看，EP通过最小化 $\text{KL}(q^{+}\Vert q)$ 来投影”精炼分布”到近似族，而VI通过最小化 $\text{KL}(q\Vert p)$ 来直接匹配真实后验。这里 $q^{+}$ 是将精确因子融入近似分布后的中间分布。²

1.3 与粒子滤波的关系

EP与粒子滤波（Particle Filtering）共享”序贯重要性采样”的思想：

• ADF：相当于在线版本的EP，像卡尔曼滤波一样序贯处理观测
• EP：通过迭代精炼弥补ADF的缺陷，允许后续观测的信息修正早期决策

EP的核心迭代步骤如下（以高斯近似为例）：

1. 初始化：设置初始近似分布 $q_0(\theta )$（通常为均匀分布或先验）
2. 选择因子：选择要精炼的因子 $f_{\alpha }$
3. 移除近似：从当前近似中移除旧近似 ${\tilde{f}}_{\alpha }$，得到腔分布（cavity distribution）：
   $q^{\setminus \alpha }(\theta )\propto \frac{q(\theta )}{{\tilde{f}}_{\alpha }({\theta }_{\alpha })}$
4. 融入精确因子：结合精确因子得到精炼分布：
   $q^{+}(\theta )\propto f_{\alpha }({\theta }_{\alpha })\cdot q^{\setminus \alpha }(\theta )$
5. 矩匹配：将 $q^{+}$ 投影回近似族（匹配一阶和二阶矩）：
   $q^{\text{new}}(\theta )=\arg {\min }_q\text{KL}(q^{+}\Vert q)$

1.4 消息传递机制

EP的消息传递机制是其核心。当近似因子的形式为指数族时，投影步骤等价于矩匹配——即匹配充分统计量的期望：

${\mathbb{E}}_q[{\varphi }_k(\theta )]={\mathbb{E}}_{q^{+}}[{\varphi }_k(\theta )],\forall k$

这解释了”期望传播”名称的由来：传播的是期望值，而非整个分布。

---

2. 因子图视角

2.1 因子图表示方法

因子图（Factor Graph）是一种二分图表示方法，特别适合描述和实现EP算法。² 因子图包含两类节点：

• 变量节点：对应随机变量 ${\theta }_i$
• 因子节点：对应局部势函数 $f_{\alpha }({\theta }_{\alpha })$

联合分布定义为：
$p(\theta )=\frac{1}{Z}{\prod }_{\alpha }{f}_{\alpha }({\theta }_{\alpha })$

其中 $Z$ 是归一化常数（配分函数）。

图示结构：

    f_a       f_b       f_c       f_d
     ●────────●────────●────────●
     │        │        │        │
    θ₁       θ₂       θ₃       θ₄

(a) 原始因子图，(b) 全因子化近似图，(c) EP精炼后的图

2.2 消息传递规则推导

EP的核心是将每个精确因子 $f_{\alpha }$ 替换为近似因子 ${\tilde{f}}_{\alpha }$，使得：
$q(\theta )\propto {\prod }_{\alpha }{\tilde{f}}_{\alpha }({\theta }_{\alpha })$

近似因子的形式通常为指数族：
${\tilde{f}}_{\alpha }({\theta }_{\alpha })=\exp \{⟨{\eta }_{\alpha },{\varphi }_{\alpha }({\theta }_{\alpha })⟩-A({\eta }_{\alpha })\}$

消息传递规则（以完全因子化的近似为例）：

对于因子 $f_{st}({\theta }_s,{\theta }_t)$，其近似形式为：
${\tilde{f}}_{st}({\theta }_s,{\theta }_t)\approx m_{st}({\theta }_t)\cdot m_{ts}({\theta }_s)$

消息更新规则为：
$m_{st}^{\text{new}}({\theta }_t)={\sum }_{{\theta }_s}{f}_{st}({\theta }_s,{\theta }_t){\prod }_{u\in N(s)\setminus t}{m}_{us}({\theta }_s)$

这与信念传播的消息传递规则形式相同，但EP中消息代表近似因子参数而非精确边际分布。²

2.3 似然消息、预测消息、后验消息

在EP框架中，消息有三种主要类型：

1. 似然消息（Likelihood Message）
${\tilde{f}}_i(\theta )=\frac{q^{\text{new}}(\theta )}{q^{\setminus i}(\theta )}$
表示第 $i$ 个数据点对参数的”软似然”贡献。

2. 预测消息（Prediction Message）
用于计算新数据点的预测分布：
$p(y^{\ast }|x^{\ast },D)\approx \int p(y^{\ast }|x^{\ast },\theta )q(\theta )d\theta$

3. 后验消息（Posterior Message）
最终的后验近似：
$q(\theta )\propto {\prod }_i{\tilde{f}}_i(\theta )$

腔分布（Cavity Distribution）
${\tilde{q}}^{\setminus i}(\theta )\propto \frac{q(\theta )}{{\tilde{f}}_i(\theta )}$
表示移除第 $i$ 个因子后的近似分布，是EP更新中的关键中间量。

---

3. EP的收敛性与数值稳定性

3.1 矩匹配原则（Mean and Variance Matching）

当近似族为高斯分布时，矩匹配等价于匹配均值和方差：

${\mu }_q={\mathbb{E}}_{q^{+}}[\theta ]={\mu }_{q^{+}}$

${\Sigma }_q={\mathbb{E}}_{q^{+}}[(\theta -\mu )(\theta -\mu {)}^{\top }]={\Sigma }_{q^{+}}$

对于高斯近似，精炼分布 $q^{+}$ 通常不是高斯分布，但其均值和协方差可以直接计算（可能需要数值积分）。³

3.2 稳定性问题与解决方案

EP面临的主要稳定性问题包括：

1. 近似因子不正定
当精炼分布的协方差为负时，可能导致近似因子失去物理意义。

2. 振荡与发散
参数更新可能引起振荡甚至发散，尤其在近似族与真实后验差异较大时。

解决方案：

• 步长控制（Step-size control）：引入学习率 $\eta \in (0,1]$：
  ${\theta }^{\text{new}}=(1-\eta ){\theta }^{\text{old}}+\eta {\theta }^{\text{target}}$
  标准EP使用 $\eta =1$，但 $\eta <1$ 可改善数值稳定性。⁴

• 约束投影：将更新后的参数投影到稳定区域。

• 对数域计算：在数值精度更好的对数域进行运算。

3.3 截断与混合策略

截断策略（Truncation）

当近似因子包含太多参数时（如高维高斯），可以采用：

• 低秩近似：只保留主导特征模式
• 稀疏近似：将协方差矩阵稀疏化
• 对角近似：简化为对角协方差

混合策略（Hybrid Approaches）

• EP + MC：用蒙特卡洛采样估计难以解析计算的矩
• EP + VI：先用VI快速获得初始点，再用EP精炼
• Power EP：引入 $\alpha$-散度，使用 $\alpha \in (0,1)$ 控制近似保守程度

3.4 收敛性理论

EP的固定点存在性可以通过能量函数证明。¹ EP固定点对应于目标函数的稳定点：

$\mathcal{F}(\eta ,{\eta }^{\setminus })={\sum }_i\log Z_i({\eta }^{\setminus i})-{\sum }_i\text{KL}(p_i\Vert q_i)$

其中 $Z_i$ 是精炼分布的归一化常数。

在大数据极限下，EP渐近等价于牛顿迭代法，在后验趋于高斯时恢复精确极限。⁵

---

4. 实际应用

4.1 大规模高斯过程近似

高斯过程（GP）分类和回归面临 $\mathcal{O}(N^3)$ 的计算复杂度，EP可用于近似：

稀疏GP + EP：

• 将似然函数分解为 $N$ 个局部近似
• 每个局部近似 ${\tilde{f}}_i$ 对应一个诱导点
• EP迭代精炼这些局部近似

可扩展GP分类：
Hernández-Lobato等人提出了基于EP的大规模GP分类方法，可处理数百万数据点。⁶

核心思想：

1. 将数据划分为多个小批量
2. 对每个数据点独立计算局部EP更新
3. 使用随机优化框架聚合结果

深度高斯过程：
EP被用于训练深度高斯过程分类器，通过反向传播与EP的结合实现高效学习。⁷

4.2 近似后验采样

从EP的近似后验 $q(\theta )$ 采样：

直接采样：如果 $q$ 是高斯或共轭分布，可以直接采样。

重要性重采样：

1. 从提议分布 $r(\theta )$ 采样
2. 计算权重 $w(\theta )\propto \frac{q(\theta )}{r(\theta )}$
3. 通过重采样获得后验样本

用于模型选择：
EP的近似边际似然可用于模型比较和超参数调优：
$\log p(D)\approx {\sum }_i\log Z_i$

4.3 与LoVE、随机变分推断的比较

LoVE（Leave-One-Out Variational EP）

LoVE是一种基于EP的留一交叉验证近似方法：⁸

• 核心思想：利用EP的腔分布近似LOO预测
• 优势：无需重新训练即可估计预测性能
• 适用场景：模型选择、超参数调优

随机变分推断（Stochastic Variational Inference, SVI）

SVI通过随机优化扩展VI到大规模数据：⁹

特性	EP	SVI
更新方式	局部因子精炼	全局参数随机梯度
计算开销	$\mathcal{O}(N)$ 每次更新	$\mathcal{O}(M)$ 每次更新（M为小批量大小）
准确性	通常更高	受随机近似影响
收敛保证	弱	强（SGD保证）

随机期望传播（Stochastic Expectation Propagation, SEP）

SEP结合了EP和VI的优点：⁹

• 维护全局后验近似（像VI一样）
• 但以局部方式更新（像EP一样）
• 计算效率接近SVI，但准确性更接近标准EP

4.4 其他应用场景

贝叶斯点机（Bayes Point Machine）：
EP为线性分类器提供了一种计算高效的贝叶斯方法，类似于SVM但具有概率输出。¹

混合模型：
高斯混合模型等复杂模型的近似推断。

稀疏编码：
用于学习过完备表示的后验近似。

---

参考文献

Footnotes

1. Minka, T. P. (2001). Expectation Propagation for Approximate Bayesian Inference. UAI 2001. https://tminka.github.io/papers/ep/minka-ep-uai.pdf ↩ ↩² ↩³ ↩⁴

2. Sutton, C. (2005). Expectation Propagation in Factor Graphs: A Tutorial. University of Edinburgh. https://homepages.inf.ed.ac.uk/csutton/publications/ep-tutorial.pdf ↩ ↩² ↩³

3. Minka, T. P. (2001). A Family of Algorithms for Approximate Bayesian Inference. PhD Thesis, MIT. ↩

4. Seeger, M. (2011). Fast Convergent Algorithms for Expectation Propagation. AISTATS 2010. http://proceedings.mlr.press/v15/seeger11a/seeger11a.pdf ↩

5. Dehaene, G. & Barthelmé, S. (2015). Expectation Propagation in the Large-Data Limit. arXiv:1503.08060. ↩

6. Hernández-Lobato, D. & Hernández-Lobato, J. M. (2016). Scalable Gaussian Process Classification via Expectation Propagation. AISTATS 2016. https://proceedings.mlr.press/v51/hernandez-lobato16.html ↩

7. Bui, T. D. et al. (2016). Deep Gaussian Processes using Stochastic Expectation Propagation. AISTATS 2016. ↩

8. Vehtari, A. et al. (2016). Bayesian Leave-One-Out Cross-Validation Approximations for Gaussian Latent Variable Models. JMLR. https://jmlr.org/papers/volume17/14-540/14-540.pdf ↩

9. Li, Y. et al. (2015). Stochastic Expectation Propagation. NIPS 2015. https://papers.nips.cc/paper/5760-stochastic-expectation-propagation ↩ ↩²