马尔可夫链提速新招！谱算法+加权k均值，收敛加速有奇效
Spectral partitioning for $k$-block averaging kernels of finite Markov chains
📖 AI 总结
本文提出了一种基于谱分解的算法，用于为有限、遍历且可逆的马尔可夫链选择状态空间划分，以定义平均核。通过将划分问题转化为对底层非平凡特征函数的加权k均值聚类，作者推导出目标函数的精确迹与归一化割表示，并揭示其等价于Pearson卡方互信息，赋予矩阵目标以概率解释。在二块情形下，阈值扫描可精确求解；对一般k，则通过加权k均值对嵌入进行舍入，并以子空间距离刻画近似误差。方法还扩展到加性混合、有限时域及折扣无限时域目标。与经典归一化谱聚类使用顶部模态寻找低流持久簇不同，该方法利用底部模态促进大归一化交叉块流和块标签信息的快速丢失。实验表明，在受控谱图、平均场伊辛模型和贝叶斯变量选择中，该方法显著提升了每步迭代的收敛速度和统计估计效果。
🔑 关键词速览
| 谱算法 | 利用矩阵特征值或特征向量进行数据或结构分析的算法。 |
| 吉布斯核 | 一种基于平稳条件分布进行重采样的马尔可夫链转移核。 |
| 加权 k-均值 | 一种聚类方法，通过最小化加权距离平方和将数据点划分为 k 个簇。 |
| 归一化割 | 衡量图划分质量的一种指标，考虑簇间边权重与簇内边权重的比例。 |
| Pearson χ² 互信息 | 基于卡方统计量度量两个随机变量之间依赖性的信息论量。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅