arXiv:2608.21466stat.MLcs.IT2026-08

用谱方法优化马尔可夫链分块,加速收敛与统计推断。

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

论文配图:Spectral partitioning for $k$-block averaging kernels of finite Markov chains
图 1 · 摘自论文原文
  • 基于低频特征函数的加权k-means分块,构造高效平均核。
  • 分块后每步迭代收敛速度提升显著,实验验证效果明显。
  • 适合需要快速收敛的马尔可夫链蒙特卡洛应用,如贝叶斯推断。

我们为有限、遍历且可逆的马尔可夫链设计了基于谱的分块算法,用于构建平均核。对于分块集 $\ackslash\mathcal O$,Gibbs核 $G_{\\ackslashmathcal O}$ 在当前块内按平稳条件分布重采样;当该更新可行时,将其与基线核 $P$ 组合或混合可加速收敛。通过舍入 $P^2$ 的最低非恒定特征函数,或对加性混合使用 $P$ 的代数最小特征函数,采用加权 $k$-means 进行分块选择。定义目标函数 $F(\ackslashmathcal O)=\ackslash|G_{\ackslashmathcal O}P-Π\ackslash|_{F,π}^2$,我们导出其迹和归一化割的精确表达式,并证明 $F$ 等于初始块标签与一次转移后状态之间的皮尔逊 $χ^2$-互信息,赋予矩阵目标明确的概率意义。在两分块情形下,阈值扫描可精确求解一维加权双均值问题。对一般 $k \\'geq 2$,采用底 $(k-1)$-维嵌入的加权 $k$-means 分块,再以 $F$ 重新评分;舍入误差对应子空间距离,给出谱逼近界。方法扩展至加性混合、有限时域及折扣无限时域目标。不同于经典归一化谱聚类(利用顶部非恒定模态寻找低流持久簇),本方法使用底部模态以促进大归一化跨块流和块标签信息快速丢失。在可控谱图、平均场伊辛模型及贝叶斯变量选择上的实验显示,收敛速度和统计估计均有显著提升。

原文摘要 · Abstract (English)

We develop spectral algorithms for selecting state-space partitions that define averaging kernels for finite, ergodic and reversible Markov chains. For a partition $\mathcal O$, the Gibbs kernel $G_{\mathcal O}$ resamples within the current block from the stationary conditional distribution; when this update is tractable, composing or mixing it with a baseline kernel $P$ can accelerate convergence. We select $\mathcal O$ by rounding the bottom nonconstant eigenfunctions of $P^2$, or the algebraically smallest eigenfunctions of $P$ for additive mixtures, using weighted $k$-means. For $F(\mathcal O)=\|G_{\mathcal O}P-Π\|_{F,π}^2$, we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $χ^2$-mutual information between the initial block label and the state after one transition, giving this matrix objective a natural probabilistic interpretation. In the two-block case, a threshold sweep exactly solves the associated one-dimensional weighted two-means rounding problem. For general $k \geq 2$, weighted $k$-means rounds the bottom $(k-1)$-dimensional embedding, after which candidates are rescored by $F$; the rounding distortion is a distance between subspaces that yields spectral approximation bounds. We extend the framework to additive mixtures, finite-horizon objectives, and discounted infinite-horizon objectives. In contrast to classical normalized spectral clustering, which uses top nonconstant modes to find low-flow persistent clusters, our method uses bottom modes to favor large normalized cross-block flow and rapid loss of block-label information. Experiments on a controlled-spectrum graph, a mean-field Ising model, and Bayesian variable selection show notable per-iteration improvements in convergence and statistical estimation.

马尔可夫链谱聚类加速采样统计推断

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。