Spectral partitioning for $k$-block averaging kernels of finite Markov chains

技术摘要：有限马尔可夫链 $k$-块平均核的谱划分研究

问题陈述
本文解决了为有限、遍历且可逆的马尔可夫链选择最优状态空间划分 $\mathcal{O} = \{O_1, \dots, O_k\}$ 以定义“平均核”时的计算瓶颈问题。虽然通过补充基准核 $P$ 的吉布斯核 $G_\mathcal{O}$（在块内根据平稳条件分布进行重采样）或加性混合核 $A_\mathcal{O} = (P + G_\mathcal{O})/2$ 可以加速收敛，但寻找能使这种加速最大化的划分在组合优化上是难以处理的。作者寻求一种谱算法来选择 $\mathcal{O}$，从而避免穷举搜索，其具体目标是抑制棘手的模态并加速混合。

方法论
核心方法是将划分选择建模为一个谱舍入（spectral rounding）问题。作者基于 $\pi$-加权 Frobenius 距离到平稳分布的平方定义了目标函数，并利用马尔可夫算子的特征函数推导了其连续松弛形式。

1. 目标函数与松弛：

   • 单步 Frobenius 目标 ($F$)： 定义为 $F(\mathcal{O}) = \|G_\mathcal{O}P - \Pi\|_{F,\pi}^2$。作者证明其等于迹 $\text{Tr}((G_\mathcal{O} - \Pi)P^2)$。其连续松弛受 $P^2$ 的底层非常数特征函数（最小特征值）控制。最小化 $F$ 等价于最大化两步链 $P^2$ 的多路归一化切分（multiway normalized cut）。
   • 加性混合目标 ($H$)： 定义为 $H(\mathcal{O}) = \|A_\mathcal{O} - \Pi\|_{F,\pi}^2$。该目标的松弛依赖于 $P$ 的代数最小特征函数（保持符号，这与 $P^2$ 不同）。
   • 多时界目标： 该框架扩展到了滞后型 ($F(P^t, \mathcal{O})$) 和折扣无限时界目标 ($F^\infty_\gamma$)，这些目标聚合了随时间变化的信息。它们使用 $P^2$ 的谱滤波器，但如果特征值顺序得以保持，则保留与单步目标相同的底层谱子空间。

2. 信息论解释：
   本文确立了 $F(\mathcal{O})$ 正好是初始块标签 $Z$ 与经过一次转移后的状态 $X_1$ 之间的 Pearson $\chi^2$-互信息 $I_{\chi^2}(Z; X_1)$。因此，最小化 $F$ 对应于最大化单步内块标签信息的损失，从而倾向于具有大归一化跨块流（normalized cross-block flow）的划分。

3. 谱舍入算法：

   • 嵌入： 使用相关算符（对于 $F$ 为 $P^2$，对于 $H$ 为 $P$）的底层 $k-1$ 个特征函数将状态嵌入到 $\mathbb{R}^{k-1}$ 中。
   • 舍入： 使用加权 $k$-means（权重为 $\pi(x)$）将嵌入结果舍入为 $k$-块划分。作者证明舍入误差 $\delta(\mathcal{O})$ 是松弛谱子空间与块常数函数子空间之间的弦距离平方。
   • 重评分： 由于几何代理指标 $\delta(\mathcal{O})$ 并不总是能最小化原始目标，算法通过 $k$-means 生成候选划分，然后通过评估精确目标（$F, H,$ 或 $F^\infty_\gamma$）来选择最终划分。
   • 两块情形： 对于 $k=2$，问题简化为一维加权两类均值问题，可通过底层特征函数的阈值扫描（threshold sweep）来精确求解。

主要贡献

• 谱定向： 本文引入了一种谱聚类方法，它是对经典归一化谱聚类的“反向”应用。经典方法使用高频（低频相对于拉普拉斯算子 $I-P$）的顶层非常数模态来寻找通信缓慢的簇（小边界）；而本方法使用底层模态（相对于拉普拉斯算子 $I-P^2$ 的高频模态）来寻找具有大归一化跨块流的划分。
• 精确迹与切分表示： 作者推导了将 Frobenius 目标与 $P^2$ 的归一化切分以及 Pearson $\chi^2$-互信息联系起来的精确恒等式。
• 理论保证： 文中提供了“谱三明治”（spectral sandwich）界限，将舍入误差 $\delta(\mathcal{O})$ 与目标值 $F(\mathcal{O})$ 联系起来。这些界限取决于特征间隙（eigengap）和谱宽度，为谱扫描相对于最优划分的次优性提供了保证。
• 向加性混合与多时界的扩展： 该框架通过使用 $P$ 而非 $P^2$ 推广到了加性混合，并推广到了定义在有限或折扣无限时界上的目标，展示了不同时间尺度如何选择不同的划分。

实验结果
作者在三个不同的实验中验证了该方法：

1. 受控谱图： 一个具有可调正负特征值的加权哑铃图。实验表明，当 $P$ 具有显著负特征值时，加性混合目标 ($H$) 选择的划分与 Frobenius 目标 ($F$) 不同，证实了保持谱符号的重要性。多时界目标被证明能选择出与单步目标不同的划分，从而在更长的时间尺度上提升性能。
2. 平均场 Ising 模型： 在 Curie-Weiss 模型上进行的精确有限状态实验（$d=8$）。谱扫描在降低目标值方面显著优于确定性基准（磁化强度分箱、坐标块）和随机划分。生成的划分并不类似于标准的亚稳态簇，而是旨在抑制持久谱模态的块。
3. 贝叶斯变量选择： 在一个拥有 4096 个状态的模型上的基准测试。研究强调，不受约束的谱舍入往往会产生高度不平衡的块（将质量坍缩至一个块），这可以作为一种类似预言机的诊断工具而非实际解决方案。施加块质量约束后，得到了平衡的划分，与基准 Metropolis 核相比，显著改善了统计估计误差（后验包含概率、模型大小分布和预测准确性）。

意义与主张
本文声称提供了一种原则性的、计算可行的方法，用于构建能够加速马尔可夫链 MCMC 收敛的平均核。它通过提供用于划分选择的具体谱算法，将自身与现有的组平均（group-averaged）MCMC 研究区分开来，而不仅仅是调整组动作。作者强调，其方法使用特征函数不仅是为了诊断收敛，更是为了构建一个新的、可模拟的、旨在更快混合的核。

其意义在于颠覆了谱聚类的范式：不是寻找“持久”的簇，而是寻找能使“块信息损失”最大化的划分，从而打破缓慢的模态。作者谦虚地指出，虽然谱候选生成是有效的，但变量选择实验中性能提升的主要驱动力是引入了带有受控块质量的非退化条件平均步骤，这表明谱方法是一个高质量候选者的鲁棒生成器，而非离散划分问题的全局优化器。