812
个编辑
更改
→谱分解
# Zhang & Wang的工作目标是在粗粒化过程中尽量保持马尔科夫性，并恢复成块结构；而动力学可逆性工作的目标是在粗粒化过程中减少 TPM 中的信道冗余性。
# Zhang & Wang的工作目标是在粗粒化过程中尽量保持马尔科夫性，并恢复成块结构；而动力学可逆性工作的目标是在粗粒化过程中减少 TPM 中的信道冗余性。
# Zhang & Wang方法的 SVD 对象是 <math>V_F</math>，稳态流矩阵的右奇异向量，而动力学可逆性的SVD对象是 <math>V_P</math>，马尔科夫转移矩阵的右奇异向量。当 <math>P</math> 恰好是低秩的时，<math>V_F</math> 和 <math>V_P</math> 张成完全相同的子空间（因为 <math>F = \mathrm{diag}(\pi) P</math>，两者秩相同时列空间一致）。当 <math>P</math> 是近似低秩（满秩但有奇异值谱间隔）时，稳态分布 <math>\pi</math> 的加权效应会使两者产生差异：对 <math>F</math> 做 SVD 天然压低了低频状态的影响，而直接对 <math>P</math> 做 SVD 则给所有状态平权。
# Zhang & Wang方法的 SVD 对象是 <math>V_F</math>，稳态流矩阵的右奇异向量，而动力学可逆性的SVD对象是 <math>V_P</math>，马尔科夫转移矩阵的右奇异向量。当 <math>P</math> 恰好是低秩的时，<math>V_F</math> 和 <math>V_P</math> 张成完全相同的子空间（因为 <math>F = \mathrm{diag}(\pi) P</math>，两者秩相同时列空间一致）。当 <math>P</math> 是近似低秩（满秩但有奇异值谱间隔）时，稳态分布 <math>\pi</math> 的加权效应会使两者产生差异：对 <math>F</math> 做 SVD 天然压低了低频状态的影响，而直接对 <math>P</math> 做 SVD 则给所有状态平权。
<br/>
谱分解（Spectral Clustering）的思想，是利用矩阵的谱，也就是特征向量所展示的物理含义来进行聚类和划分。
===最大化有效信息的谱分解方法===
此方法先对转移矩阵做特征分解，把状态嵌入到由特征向量张成的谱空间中，再根据谱空间中的几何邻近性来聚类，最后据此构造宏观动力学。它的优点是能把“哪些状态在动力学上相似”转化为一个可操作的聚类问题。
'''输入'''：原始包含 <math>N</math> 个状态的马尔科夫链 <math>P</math> 和距离超参 <math>\epsilon</math>；
# 对 <math>P</math> 进行矩阵的[[特征值分解]]，得到特征值集合 <math>\Lambda=\{\lambda_i\}^N_{i=1}</math> 与特征向量集合 <math>E=\{e_i\}^N_{i=1}</math>；
# 构建有偏特征向量集合 <math>E’=\{\lambda_ie_i|\lambda_i\neq 0\}</math>。这里用特征值对特征向量加权，并去掉零特征值对应的方向，因为后者更多反映动力学的简并性，而非真正有区分度的大尺度结构；
# 依据 <math>E'</math> 计算状态间的相似矩阵 <math>D</math>：如果两个状态位于彼此的马尔科夫毯中，就用谱嵌入后的 cosine 相似度来衡量其接近程度；否则把它们视为“不可直接聚类”的状态对，赋予极大距离；
# 基于相似度矩阵 <math>D</math> 和超参 <math>\epsilon</math>，使用[[OPTICS]]算法在谱空间中聚类，得到候选划分，并从中选出 EI 较高的结果。
忽略零特征值对应的特征向量，实际上是在排除那些不携带有效区分信息的方向；保留下来的谱坐标则更能刻画状态在动力学中的“角色相似性”。该方案的时间复杂度约为 <math>O(N^3)</math>，局限在于特征分解本身成本较高，而且聚类阈值 <math>\epsilon</math> 往往需要线性搜索或人为调参。
<br/>
===寻找成块划分的谱分解方法===
当马尔科夫矩阵存在成块或近成块结构时，谱方法也可以直接用来恢复划分。实际问题中的难点在于：状态顺序常常被打乱，矩阵里还会混入噪声，因此我们往往既不知道它是否严格成块，也不知道应当分成几组。
[[文件: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>，再利用它的奇异值结构来恢复成块划分。其中 <math>\pi</math> 是 <math>P</math> 的稳态分布，<math>F_{ij} = \pi_i P_{ij}</math> 表示稳态下从状态 <math>i</math> 流向状态 <math>j</math> 的长期概率流量。
# 获取一个 <math>n\times n</math> 维的马尔科夫矩阵 <math>P</math>，或者马尔科夫链的频率采样，并由此得到频率矩阵 <math>F</math>；
# 获取马尔科夫秩 <math>r</math>，或者把 <math>r</math> 视为待选超参；
# 对 <math>F</math> 进行 SVD 分解，<math>F = U \Sigma V^T</math>；
# 取前 <math>r</math> 个右奇异向量，把每个状态映射成向量 <math>V_{[i,:r]}</math>，再在这些点上做聚类。等价地，可以写成寻找下式对应的最优划分 <math>\Omega_1,\Omega_2,\ldots,\Omega_r</math>：
<math>
\Omega_1, \Omega_2, ... , \Omega_r = argmin_{\Omega_1, \Omega_2, ... , \Omega_r} min_{v_1, v_2, ... , v_r} \sum_{s=1}^r \sum_{i \in \Omega_s} || V_{[i,:r]} - v_s ||_2^2
</math>
其中 <math>v_s</math> 是第 <math>s</math> 类的中心向量。这个目标函数和 K-Means 本质上是同一类问题：让同一组状态在主奇异子空间中的坐标尽可能靠近。因此，实践中常常直接对这些谱坐标做 K-Means 聚类。
为什么是对 <math>F</math> 做 SVD，而不是直接对 <math>P</math> 做 SVD？因为 <math>P</math> 编码的是条件转移分布，而 <math>F</math> 编码的是'''稳态下的长期概率流结构'''。对 <math>F</math> 做 SVD，相当于在稳态流网络中寻找最主要的流通道，也会自然压低低频状态的干扰。对于精确成块的情形，同一组状态在主右奇异向量上的坐标会呈现近似分段常数结构，因此能够被较稳定地恢复出来。
这种方法最适合用于'''近成块'''且存在明显谱间隙的系统：前几个奇异值主要反映组间的大尺度流动，后面的奇异值更多对应组内局部波动。这对应于一种特殊但常见的物理场景：系统各状态群之间的长期概率流量远弱于群内流量，形成类似“准吸引域”的结构，粒子长时间在群内游走，偶尔才跨越群边界。当 <math>P</math> 不是精确成块，而是近似成块（near-lumpable）时，该方法仍然可以工作，但需要满足一个关键条件：'''组间动力学的奇异值必须主导 <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>\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>），SVD 提取的前 <math>r</math> 个方向会反映组内的局部动力学模式而非组间的成块结构，此时该方法会给出错误的分组。
<br/>
===基于动力学可逆性的谱分解方法===
张江等人关于动力学可逆性的文章<ref name="reversibility"/>提供了另一种基于 SVD 的粗粒化方法。它的目标不是恢复某种预设的成块结构，而是把马尔科夫动力学看作一个通信信道，删除马尔科夫动力学中的'''冗余通路'''。这里每个状态的出转移分布都可以看作一条信息通路；如果若干行向量彼此线性相关，那么这些通路在信息上就是冗余的，即使它们在概率分布上看起来并不相似。
这也是它和 EI 的一个重要差别：EI 只能度量行向量之间的分布相似性，而动力学可逆性 <math>\Gamma_\alpha</math> 还能捕捉线性依赖关系。换句话说，两个状态的出流模式可以彼此很不像，但只要在代数上是冗余的，<math>\Gamma_\alpha</math> 仍能识别出来。
算法的基本流程如下：
# 给定含有 <math>N</math> 个状态的马尔科夫矩阵 <math>P</math>，对其做 SVD 分解 <math>P = U \Sigma V^T</math>；
# 根据奇异值谱设定阈值 <math>\epsilon</math>，保留前 <math>r_\epsilon</math> 个右奇异向量，构成 <math>V_{N \times r_\epsilon}</math>；
# 对 <math>P</math> 的行向量做投影：<math>\tilde{P} = P \cdot V_{N \times r_\epsilon}</math>，得到每个状态在“核心通路”子空间中的表示；
# 对 <math>\tilde{P}</math> 的行向量用 K-Means 聚类为 <math>r_\epsilon</math> 组，得到划分 <math>\Phi</math>；
# 基于划分 <math>\Phi</math> 和稳态流矩阵 <math>F = \mathrm{diag}(\pi) P</math>，通过 <math>F' = \Phi^T F \Phi</math> 构建宏观稳态流矩阵，再对每行归一化得到宏观转移矩阵 <math>P'</math>。
这里的投影 <math>\tilde{P}</math> 可以理解为：只保留转移矩阵中最主要的几条信息通道，把冗余或近乎无效的方向滤掉，再按照这些主导模式来归组状态。最后用 <math>F' = \Phi^T F \Phi</math> 而不是直接对 <math>P</math> 做行列聚合，是为了保证粗粒化与时间演化尽可能可交换，从而使宏观动力学仍然是合法的马尔科夫链。
虽然它与前面的 Zhang & Wang 方法都包含 “SVD + K-Means” 这一步，但两者的目标不同：前者更关心从稳态流结构中恢复成块划分，后者更关心删除 TPM 中的冗余信道。相应地，前者分解的是 <math>F=\mathrm{diag}(\pi)P</math>，因此天然带有稳态权重；后者直接分解 <math>P</math>，更强调转移矩阵本身的线性冗余结构。
<br/>
<br/>