The windowEM algorithm

“windowEM 算法”技术摘要

问题陈述
期望最大化（EM）算法是处理含有隐变量模型的极大似然估计的标准方法。然而，在处理大规模数据集（例如包含数十亿个数据点的基因组数据）时，标准的 EM 算法在计算上变得不切实际，因为它要求在每次迭代中都要处理整个数据集。虽然研究者已经提出了随机版本（使用小批量/mini-batches）的 EM 来加速收敛，但这些方法往往会产生粗糙或带有噪声的参数估计，尤其是在参数空间复杂或某些隐变量在数据中分布稀疏的情况下。这种噪声可能导致人工伪影，例如在估计的位点频率谱（SFS）等分布中产生人为的“凸起”，并可能导致过拟合。

方法论：windowEM 算法
作者提出了 windowEM，这是一种将数据划分为 $B$ 个块并将其排列在圆周上的随机 EM 算法变体。该算法通过以下机制运行：

1. 分块（Block Partitioning）： 将数据分为 $B$ 个块（$x_1, \dots, x_B$）。这些块的大小和分布可能各不相同，且不假设它们是独立的。
2. 顺序更新（Sequential Updates）： 算法执行一系列更新，其中当前块 $k$ 的估计值是利用前一个块 $k-1$ 的估计值作为种子推导而来的。具体而言，通过在当前块 $b(t+1)$ 上使用当前参数估计 $\theta_t$ 进行一次标准 EM 迭代，得到初步估计 $\psi_{t+1}$：
   $$\psi_{t+1} = f_{b(t+1)}(\theta_t) = \arg\max_{\theta'} Q_{b(t+1)}(\theta' | \theta_t)$$
3. 滚动窗口平均（Rolling Window Averaging）： 为了抵消单块更新带来的噪声，算法维护了一个估计值的“种群”。给定步骤的最终估计值 $\theta_t$ 是在大小为 $w$ 的滚动窗口内最近 $w$ 个初步估计值的平均值：
   $$\theta_t = \frac{1}{w} \sum_{i=t-w+1}^{t} \psi_i$$
4. 循环迭代（Circular Iteration）： 这些块是循环排列的。如果 $B$ 是有限的，算法会重复遍历这些块（轮次/epochs）。如果 $B = \infty$，算法则会通过一个无限的唯一块序列进行推进。
5. 最终估计（Final Estimation）： 可以通过对 $B$ 个估计值的种群进行平均来产生单个点估计。

作者指出，虽然该算法受到了 Polyak-Ruppert 平均法的启发，但其不同之处在于它将平均应用于在圆形数据排列下通过顺序 EM 步骤生成的估计值，而不是以标准随机梯度下降的方式对梯度或更新进行平均。

关键理论贡献
论文研究了 windowEM 在两种场景下的收敛特性：有限 $B$ 和无限 $B$。

• 有限 $B$： 作者利用收缩理论（contraction theory）。他们证明了如果更新函数是一个收缩映射，则块估计序列会收敛。一个关键发现是，如果一个块存在不动点，则所有块都存在不动点。这些块估计值的分布取决于窗口大小 $w$；从经验上看，较大的窗口尺寸会导致块估计值之间的方差更低。
• 无限 $B$： 对于 $B = \infty$（或足够大以至于块不会重复）的情况，作者应用了针对相关数据的随机迭代理论。他们提供了在块索引较大时估计值收敛到不动点的条件。此外，他们还确立了保证当 $B \to \infty$ 时块估计值的遍历平均（ergodic average）收敛的条件。
• 指数族（Exponential Families）： 该分析对于指数族特别严谨。作者证明，对于均值参数化形式，更新函数通常是充分统计量的线性函数。在指数族分布混合的情况下，更新函数仍然是对观测统计量进行加权后的线性函数，权重由估计的类别概率决定。
• 特殊情况： 论文分析了特定配置，例如 $w=1$（这退化为没有平均的顺序 EM）和 $w=B$（此时更新变为对所有块的平均，在满足线性假设的情况下，可能产生等同于标准 EM 解的不动点）。

实证结果
论文使用两个主要示例验证了该算法：

1. 说明性二项分布示例： 一个基因频率估计问题。结果显示，windowEM 能迅速收敛至极大似然估计（MLE）。随着窗口大小 $w$ 的增加，估计值的方差会减小，尽管较大的 $w$ 可能会略微减慢收敛速度。
2. 单变量高斯混合模型： 算法在混合高斯分布上进行了测试。
   • 在一个包含 $n=10^5$ 个数据点和 $B=10$ 个块的模拟中，windowEM 比标准 EM 更快地达到了接近完全数据 MLE 的对数似然值。
   • 值得注意的是，虽然标准 EM 最终达到了比 windowEM 更高的对数似然值，但它也超过了完全数据 MLE，这表明存在过拟合。通过对估计值种群进行平均得到的 windowEM 估计值表现出了正则化作用，更接近真实的底层分布，没有出现标准 EM 中观察到的“超调”现象。
   • 在较小（$n=10^4$）和较大（$n=10^6$）的数据集上也观察到了类似的趋势，其中 windowEM 比标准 EM 更快地稳定在接近完全数据 MLE 的位置。

意义与主张
作者声称，windowEM 为标准 EM 难以应对、而标准随机 EM 噪声过大的大规模推理问题提供了一个切实可行的解决方案。其主要意义在于通过在滚动窗口内对估计值种群进行平均所产生的正则化效应。

• 防止过拟合： 基于基因组学（SFS 估计）和高斯混合模型的经验证据，论文推测 windowEM 有助于防止过拟合。通过平滑掉可能由特定块中的稀有事件人为放大的估计值，该算法能产生更稳定的参数估计。
• 理论基础： 论文对这种特定方案的收敛性进行了首次理论研究，区分了有限块和无限块场景，并利用了收缩理论和随机迭代理论。
• 谦逊的态度： 作者对自己的主张保持了克制，指出虽然 windowEM 可能并不总是能达到绝对的极大似然估计（甚至可能比标准 EM 的对数似然值更低），但由于方差降低，所得估计值可能更具鲁棒性和统计意义。他们并未声称 windowEM 在所有情况下都优于标准 EM，而是强调了在大数据环境下，在稳定性与速度之间的一种权衡。