812
个编辑
更改
跳到导航
跳到搜索
第919行：
第919行： − + + − + − + − + 第938行：
第939行： − + + + + + + + + + + + + + + + +
→寻找成块划分的谱分解方法
针对这一问题，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" />提出了一种寻找最优划分的方法。通过这种方法，我们可以找到最优的划分，并基于这个划分判断一个马尔科夫矩阵是否成块。具体步骤如下：
针对这一问题，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>\pi</math> 是 <math>P</math> 的稳态分布，<math>F_{ij} = \pi_i P_{ij}</math> 可以理解为系统在稳态下从状态 <math>i</math> 流向状态 <math>j</math> 的长期概率流量。具体步骤如下
#获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
#获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样，并由此得到频率矩阵 <math>F</math>；
#获取<math>r<n</math> 的马尔科夫秩，或指定一个<math>r</math>；
#获取马尔科夫秩<math>r<n</math> ，或指定一个<math>r</math>；
#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中 <math>U</math> 为左奇异向量，<math>V</math> 为右奇异向量，<math>\Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N})</math> 是一个对角矩阵，包含所有有序奇异值。
#对 <math>F</math> 进行SVD分解，<math>F = U \Sigma V^T</math>，其中 <math>U</math> 为左奇异向量，<math>V</math> 为右奇异向量，<math>\Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N})</math> 是一个对角矩阵，包含所有有序奇异值。
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
论文<ref name=":4" />中并未提供使用右奇异向量向量进行聚类的物理原因，但提供了该算法的解与最优解的差距的上界。
为什么是对 <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>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 的聚类结果就不再对应成块划分，方法会失效。
论文<ref name=":4" />中提供了该算法的解与最优解的误差的上界：
<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>
分子中第一项是有限样本的统计误差，第二项是近似成块带来的结构偏差，分母是组间动力学的信号强度。只有当两者都远小于分母时，成块划分才能被可靠地恢复。所以，该方法要求 <math>F</math> 的组间动力学信号主导整体奇异值谱，在组间转移强、组内差异大的链上会给出错误的划分。
<br/>
<br/>