812
个编辑
更改
跳到导航
跳到搜索
第619行：
第619行： − + + + + + + + + + + + + + + + + + + + + + + 第630行：
第651行： − + 第649行：
第670行： − + − + − − '''1)''' 对P进行SVD分解（假设P是不可归约的，且具有周期性，从而存在平稳分布）： − <blockquote> − <math>P=U\cdot \Sigma \cdot V^{T},</math> − </blockquote> − 其中，<math>U</math>和<math>V</math>是两个尺寸为N×N的正交归一化矩阵，<math>\Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N})</math> 是一个对角矩阵，包含所有有序奇异值。 − − '''2)'''选择一个<math>\epsilon</math>作为阈值来截断奇异值谱，并得到<math>r_{\epsilon}</math>作为保留状态的个数； − − '''3)'''通过计算<math>\tilde{P}\equiv P\cdot V_{N\times r_{\epsilon}}</math>对P中的所有<math>P_{i}</math>进行降维，其中<math>V_{N\times r_{\epsilon}}</math>由<math>P\cdot P^{T}</math>的前<math>r_{\epsilon}</math>个特征向量构成； − '''4)''' 通过 K-means 算法将<math>\tilde{P}</math>中的所有行向量聚类为r组，得到投影矩阵<math>\Phi</math>，其定义为:+ + + + 第673行：
第687行： − 对<math>\forall i,j \in [1,N]</math>都成立。+ + + +
→划分方法
===基于成块性的粗粒化方法（未给定成块的划分的情况）===
===最大化有效信息的谱分解方法===
该方法是将原始网络对应的转移矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。
'''输入'''：原始包含 <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≠0\}^N_{i=1}</math>，该集合中的每个向量被其对应的特征值所加权，同时去除了零特征值和对应的特征向量（新的状态数量为<math>N'=rank(A)</math>）。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应了动力学中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
# 依据<math>E'</math>计算状态间的相似矩阵<math>D_{N'×N'}</math>：
## 如果状态 <math>v_i</math> 和 <math>v_j</math> 分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cosine相似性作为两者间的相似度 <math>d_{ij}</math> 和 <math>d_{ji}</math>
## 否则将两个节点间的相似度设为无穷大 <math>\infty</math>（可以设个比较大的值，如10000）
# 基于相似度矩阵<math>D_{N'×N'}</math>和一个超参<math>\epsilon</math>（需要线性搜索，可以选择EI最大的参数），使用[[OPTICS]]算法（是一种基于密度的划分算法，旨在识别数据集中不同密度的划分结构）进行划分，输出对应超参<math>\epsilon</math>下的划分方式
该方案的时间复杂度为<math>O(N^3)</math>
'''缺点'''：
# 对大规模动力学进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
===寻找成块划分的谱分解方法===
当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图6中的<math>\bar{P}</math>所示，我们能够很快的找出它的成块划分<math>\Phi</math>。然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（6）中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。在这种情况下，我们通常面临的是像<math>P</math>这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。
当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图6中的<math>\bar{P}</math>所示，我们能够很快的找出它的成块划分<math>\Phi</math>。然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（6）中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。在这种情况下，我们通常面临的是像<math>P</math>这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。
#获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
#获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
#获取<math>r<n</math> 的马尔科夫秩，或指定一个<math>r</math>；
#获取<math>r<n</math> 的马尔科夫秩，或指定一个<math>r</math>；
#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。
#对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>\Omega_1, \Omega_2, ... , \Omega_r</math>
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
<br/>
<br/>
==基于可逆性的TPM矩阵的粗粒化方法==
===最大化可逆性的谱分解方法===
动力学可逆性的文章<ref name="reversibility"/>提供了另一种基于奇异值分解的粗粒化方法，以获得宏观层面的简化TPM。其基本思想是将 <math>P</math> 中的行向量 <math>P_{i},\forall i \in [1,N]</math> 投影到 <math>P</math> 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 <math>P</math> 的主要信息，并保持 <math>\Gamma</math> 不变。
动力学可逆性的文章<ref name="reversibility"/>提供了另一种基于奇异值分解的粗粒化方法，以获得宏观层面的简化TPM。其基本思想是将 <math>P</math> 中的行向量 <math>P_{i},\forall i \in [1,N]</math> 投影到 <math>P</math> 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 <math>P</math> 的主要信息，并保持 <math>\Gamma</math> 不变。
跟上面的方法类似，该方法的基本思路是将P中的所有行向量 <math>P_{i}</math> 视为维数为 <math>N</math> 的数据向量。首先对这些行向量进行PCA降维，其次将其聚类为 <math>r</math> 个簇，其中 <math>r</math> 是根据奇异值谱的阈值<math>\epsilon</math>截取的。
跟上面的方法类似，该方法的基本思路是将P中的所有行向量 <math>P_{i}</math> 视为维数为 <math>N</math> 的数据向量。首先对这些行向量进行PCA降维，其次将其聚类为 <math>r</math> 个簇，其中 <math>r</math> 是根据奇异值谱的阈值<math>\epsilon</math>截取的：
# 对P进行SVD分解：<math>P=U\cdot \Sigma \cdot V^{T},</math>
# 选择一个<math>\epsilon</math>作为阈值来截断奇异值谱，并得到<math>r_{\epsilon}</math>作为保留状态的个数；
# 通过计算<math>\tilde{P}\equiv P\cdot V_{N\times r_{\epsilon}}</math>对P中的所有<math>P_{i}</math>进行降维，其中<math>V_{N\times r_{\epsilon}}</math>由<math>P\cdot P^{T}</math>的前<math>r_{\epsilon}</math>个特征向量构成；
# 通过 K-means 算法将 <math>\tilde{P}</math> 中的所有行向量聚类为 <math>r</math> 组，得到投影矩阵<math>\Phi</math>，其定义为：
<blockquote>
<blockquote>
<math>
<math>
\end{cases}</math>
\end{cases}</math>
</blockquote>
</blockquote>
上述有关因果涌现的定义以及相应的基于动力学可逆性的合理性来源于这套SVD方案定义的因果涌现与最大化有效信息的因果涌现定义的密切关系，我们可以证明，要想获得最大化有效信息的粗粒化策略也近似等价于是向最大奇异值对应的奇异向量方向投影的策略。在[[基于有效信息的因果涌现理论|Erik Hoel因果涌现理论]]的框架内，给定马尔可夫动力学系统的因果涌现的大小依赖于粗粒化策略的选择，可以通过宏观动力学的EI最大化寻找最优的粗粒化策略。由于对于离散的马尔可夫链来说，粗粒化策略往往都是比较严格的0或1构成的向量，因此并不能简单地根据奇异向量来直接投影，但是如果粗粒化策略尽可能地与最大的几个奇异向量平行，那么就可以让粗粒化后动力学的EI尽可能更大，因此最大化EI的必要条件近似可以认为就是往最大奇异值对应的奇异向量空间做投影。严格推导可见[[基于有效信息的因果涌现理论]]
<br/>
=聚合方法=
=聚合方法=