812
个编辑
更改
跳到导航
跳到搜索
第923行：
第923行： − 第948行：
第947行： − + + + − + + + + + − 论文<ref name=":4" />中提供了该算法的解与最优解的误差的上界：+ − − − − 分子中第一项是有限样本的统计误差，第二项是近似成块带来的结构偏差，分母是组间动力学的信号强度。只有当两者都远小于分母时，成块划分才能被可靠地恢复。所以，该方法要求 <math>F</math> 的组间动力学信号主导整体奇异值谱，在处理组间转移强、组内差异大的链上会给出错误的划分。
→寻找成块划分的谱分解方法
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
针对这一问题，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />提出了一种寻找最优划分的方法，其核心是利用'''稳态流矩阵'''（frequency matrix）<math>F = \mathrm{diag}(\pi) \cdot P</math> 的奇异值结构来恢复成块划分。
针对这一问题，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />提出了一种寻找最优划分的方法，其核心是利用'''稳态流矩阵'''（frequency matrix）<math>F = \mathrm{diag}(\pi) \cdot P</math> 的奇异值结构来恢复成块划分。
为什么是对 <math>F</math> 做 SVD 而不是对 <math>P</math>？
为什么是对 <math>F</math> 做 SVD 而不是对 <math>P</math>？
论文证明了，当马尔科夫链关于划分 <math>\Omega_1, \ldots, \Omega_r</math> 是成块的时，<math>F</math> 存在分解 <math>F = F_1 + F_2</math>，其中 <math>F_1</math> 是秩为 <math>r</math> 的成块部分，<math>F_2</math> 是组内局部动力学部分，两者行空间正交（<math>F_1 F_2^T = 0</math>）。<math>F_1</math> 的右奇异向量 <math>V_{F_1}</math> 具有'''分段常数'''结构：同一组 <math>\Omega_k</math> 内的所有状态，其行向量 <math>(V_{F_1})_{[i,:]}</math> 完全相同，不同组之间则有明确间距。这使 K-Means 可以精确恢复分组。而<math>P</math> 的奇异向量并没有这个性质。
论文证明了，当马尔科夫链关于划分 <math>\Omega_1, \ldots, \Omega_r</math> 是成块的时，<math>F</math> 存在分解 <math>F = F_1 + F_2</math>，其中 <math>F_1</math> 是秩为 <math>r</math> 的成块部分，<math>F_2</math> 是组内局部动力学部分，两者行空间正交（<math>F_1 F_2^T = 0</math>）。<math>F_1</math> 的右奇异向量 <math>V_{F_1}</math> 具有'''分段常数'''结构：同一组 <math>\Omega_k</math> 内的所有状态，其行向量 <math>(V_{F_1})_{[i,:]}</math> 完全相同，不同组之间则有明确间距。因此，K-Means 可以精确恢复分组。而<math>P</math> 的奇异向量并没有这个性质。
从物理上看，<math>F</math> 编码的是'''稳态下的概率流量结构'''，而 <math>P</math> 编码的是'''条件转移分布'''。对 <math>F</math> 做 SVD 相当于在稳态概率流网络中寻找主要的流量通道结构——低频状态对应的流量通道自然被压低权重，不会干扰大尺度结构的识别。
当系统存在明显的近成块结构时，<math>F</math> 的前 <math>r</math> 个奇异值主要反映的是组间的大尺度概率流通道，而后续的奇异值反映的是组内的局部流量波动。如果这两部分之间存在明显的谱间隙（singular value gap），即 <math>\sigma_r(F_1) \gg |F_2|</math>，那么 K-Means 聚类 <math>\hat{V}_F</math> 就能准确恢复成块划分。
当系统存在明显的近成块结构时，<math>F</math> 的前 <math>r</math> 个奇异值主要反映的是组间的大尺度概率流通道，而后续的奇异值反映的是组内的局部流量波动。如果这两部分之间存在明显的谱间隙（singular value gap），即 <math>\sigma_r(F_1) \gg |F_2|</math>，那么 K-Means 聚类 <math>\hat{V}_F</math> 就能准确恢复成块划分。
这对应于一种特殊但常见的物理场景：系统各状态群之间的长期概率流量远弱于群内流量，形成类似"准吸引域"的结构——粒子长时间在群内游走，偶尔才跨越群边界。然而需要注意，成块性的数学定义本身并'''不要求'''群内流量强于群间流量。成块性只要求同组状态到各组的转移概率总量相同，并不约束转移的方向强弱。因此，当系统虽然满足成块性、但组间转移概率反而很大时（即 <math>|F_2| \gtrsim \sigma_r(F_1)</math>），<math>F</math> 的前 <math>r</math> 个奇异向量将被组内动力学主导，K-Means 的聚类结果就不再对应成块划分，方法会失效。
这对应于一种特殊但常见的物理场景：系统各状态群之间的长期概率流量远弱于群内流量，形成类似"准吸引域"的结构——粒子长时间在群内游走，偶尔才跨越群边界。当 <math>P</math> 不是精确成块，而是近似成块（near-lumpable）时，该方法仍然可以工作，但需要满足一个关键条件：'''组间动力学 <math>F_1</math> 的奇异值必须主导 <math>F</math> 的整体奇异值谱'''，即 <math>\sigma_r(F_1) \gg \|F_2\|</math>。
需要注意的是，成块性的数学定义本身并'''不要求并不要求准吸引域结构（群内流量强于群间流量）'''。成块性只要求同组状态到各组的转移概率总量相同，并不约束转移的方向强弱。论文给出了分组错误率的上界：
<math>
\text{Misclassification rate} \leq C \frac{\pi_{\max} r \tau^* \log^2(n)/n + (r\|F_2\|^2) \wedge \|F_2\|_F^2}{\sigma_r^2(F_1)}
</math>
分子中第一项是有限样本的统计误差，第二项是近似成块带来的结构偏差，分母是组间动力学的信号强度。因此，当系统虽然满足成块性、但组间转移概率反而很大时（即 <math>|F_2| \gtrsim \sigma_r(F_1)</math>），<math>F</math> 的前 <math>r</math> 个奇异向量将被组内动力学主导，K-Means 的聚类结果就不再对应成块划分，方法会失效。
<math>\mathbb{E},M(\hat{\Omega}_1, \ldots, \hat{\Omega}r) \leq C \cdot \frac{\pi{\max} r \tau^* \log^2(n)/n + (r|F_2|^2) \wedge |F_2|_F^2}{\sigma_r^2(F_1)} \wedge r</math>
<br/>
<br/>