马尔科夫链的粗粒化

马尔科夫链是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。一般的马尔科夫链包括 [math]\displaystyle{ N }[/math] 个状态，所有状态之间的概率转移构成了一个转移概率矩阵 [math]\displaystyle{ P }[/math]，该矩阵有 [math]\displaystyle{ N }[/math] 行[math]\displaystyle{ N }[/math]列，且满足概率归一化条件（所有元素位于0到1之间，所有行的和为1）。本词条限定在 平稳马尔科夫链 上的讨论，也就是[math]P[/math]不随时间和状态而变。

所谓的马尔科夫链的粗粒化，就是指找到一个新的马尔科夫链，它具有 [math]\displaystyle{ 1\lt M\lt N }[/math] 个状态，其对应的 [math]\displaystyle{ M }[/math] 行 [math]\displaystyle{ M }[/math] 列的概率转移矩阵为[math]\displaystyle{ P' }[/math]，它同样满足概率归一化条件，它可以看作是对 [math]\displaystyle{ P }[/math] 矩阵所描述的动力学过程的一种抽象近似的约简。

文献中一般着重强调对马尔科夫链做粗粒化的意义包括：

1. 我们在研究一个超多状态的复杂系统时，并不会关注每一个微观的状态，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而从微观尺度中总结一些中尺度或宏观尺度的规律；
2. 有些状态的转移概率非常相似，所以可以被看成同一类状态。对这些状态进行划分和归并可以减少马尔科夫链的冗余性，得到一个更简洁有效的表示；
3. 在用到马尔科夫决策过程的强化学习算法中，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练过程的样本效率和任务表现。

对任意马尔科夫链的转移概率矩阵做约简存在着无穷多可能的方法，然而在实际的粗粒化过程中，我们必须从这无穷多钟方法中做筛选，以使得约简后的矩阵[math]P'[/math]能够尽可能多地保留原矩阵的主要特征。于是，为了刻画这种原矩阵特征是否被保留的特性，人们提出了不同的标准，这些标准包括：

1. 首先，我们想尽量降低动力学在压缩后的维度；
2. 其次，我们想在压缩过程中尽量保留动力学中的信息；
3. 最后，我们希望压缩后的过程和原本的过程尽量保持一致。

在这个词条中，我们会围绕着这三个标准展开讨论，并介绍一系列针对马尔科夫链的实际可操作的粗粒化方法。

粗粒化

马尔科夫链不只是一个马尔科夫矩阵那么简单。它还涉及到了不同的状态，也会有状态之间的转移概率，所以我们可以从不同的角度来看待粗粒化：

1. 对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，状态转移的过程为一个粒子在节点间跳转，而粗粒化则是对这个网络做降维。
2. 对状态空间做粗粒化：我们这里讨论的是离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。
3. 对概率空间做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。

这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。

对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化（coarse-graining）、聚类/聚合（partitioning/lumping/clustering/aggregation）和降维（dimension reduction）是重叠等价的。

本词条只讨论离散时间马尔科夫链，且动力学 [math]\displaystyle{ P }[/math] 是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们可以定义微观状态空间为[math]\displaystyle{ S=\{s_1, s_2, ... ,s_n\} }[/math]，微观转移函数[math]\displaystyle{ P \in \mathcal{R}_{n \times n} }[/math]是一个大小为 n 的马尔科夫矩阵。同样的，粗粒化后的宏观状态空间为[math]\displaystyle{ S'=\{s'_1, s'_2, ... ,s'_r\} }[/math]，宏观转移函数[math]\displaystyle{ P' \in \mathcal{R}_{r \times r} }[/math]。 多数文献中会出现如图1的定义：

对状态空间 [math]\displaystyle{ S }[/math] 和转移函数 [math]\displaystyle{ P(t):S \rightarrow S }[/math]，我们需要一个状态分组的投影函数 [math]\displaystyle{ \Phi:S \rightarrow S' }[/math]，和一个在新状态空间上的转移函数 [math]\displaystyle{ P'(t):S' \rightarrow S' }[/math]，而且 [math]\displaystyle{ S' }[/math] 和[math]\displaystyle{ P' }[/math] 要符合马尔科夫链定义。

如果我们对这个降维/粗粒化过程进行分解的话，我们可以看到这个过程可以被分为三步。

1. 划分（对状态空间进行粗粒化）：对状态进行分组，得出[math]\displaystyle{ \Phi }[/math]，决定 [math]\displaystyle{ S }[/math] 空间中的状态要如何被投影到 [math]\displaystyle{ S' }[/math] 空间上。
2. 聚合（对转移概率进行粗粒化）：基于分组函数 [math]\displaystyle{ \Phi }[/math]，我们要决定如何把原来的状态转移矩阵[math]\displaystyle{ P }[/math]降维成新的[math]\displaystyle{ P' }[/math]。
3. 判断粗粒化方案 [math]\displaystyle{ \Phi }[/math] 和 [math]\displaystyle{ P' }[/math] 符合什么样的性质。

划分：对状态空间进行粗粒化

我们假设投影函数 [math]\displaystyle{ \Phi }[/math] 是一个 [math]\displaystyle{ n \times r }[/math] 的线性投影矩阵，且符合下列两个条件：(1)所有元素非负；(2)每行加和等于1。

马尔科夫链的粗粒化可以分成硬划分（Hard partitioning）和软划分（Soft partitioning）。硬划分是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而软划分则会有可能出现一个微观状态被分在属于多个宏观类的情况。

在硬划分的情况下，[math]\displaystyle{ \Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases} }[/math]，即一个表示[math]\displaystyle{ i }[/math]属于[math]\displaystyle{ j }[/math]列的零一分组矩阵。如果是软划分的话，[math]\displaystyle{ \Phi }[/math]则不一定会是零一矩阵。

在这个词条里，我们主要讨论硬划分。对软划分感兴趣的朋友可以自行参阅这两篇论文 。

聚合：对转移概率进行粗粒化

得出 [math]\displaystyle{ \Phi }[/math] 后，对微观马尔科夫矩阵 [math]\displaystyle{ P }[/math] 的降维可以表示为

[math]\displaystyle{ \begin{aligned} P' = W P \Phi, \end{aligned} }[/math]

(1)

其中 [math]\displaystyle{ W \in \mathbb{R}^{r \times n} }[/math]。Buchholz的文章中把 [math]\displaystyle{ W }[/math] 称作distributor matrix，而 [math]\displaystyle{ \Phi \in \mathbb{R}^{n \times r} }[/math] 称作collector matrix。

我们假设了[math]\displaystyle{ W, \Phi, P, P' }[/math]都是线性的，所以我们可以这样理解这个公式：从图1中从左上角的 t 时刻宏观状态出发，经过了一个‘逆向粗粒化’操作[math]\displaystyle{ W }[/math]，得到了 t 时刻微观状态，走微观动力学 [math]\displaystyle{ P }[/math] 得到了 t+1 时刻的微观状态，再经粗粒化 [math]\displaystyle{ \Phi }[/math] 得到 t+1 时刻的宏观状态。

式子1中我们发现，[math]\displaystyle{ \Phi }[/math] 和 [math]\displaystyle{ P }[/math] 都是给定的，所以我们在这一步要做的是决定 [math]\displaystyle{ W }[/math]。[math]\displaystyle{ W }[/math] 的基础限制是要使得 [math]\displaystyle{ P' }[/math] 符合马尔科夫矩阵定义，在此基础上有无限多种 [math]\displaystyle{ W }[/math] 的选项，而我们也能从中挑出符合我们想要的特征的 [math]\displaystyle{ W }[/math]。

粗粒化方案的要求和优化目标

目前我们还没找到一个严格的完备的马尔科夫粗粒化应该符合的定义。在这一章中，我们将简单梳理概括一些基本的概念，和不同粗粒化方法中使用到的要求、优化目标和评价指标。

问题拆分

当我们把“对一个马尔科夫链做粗粒化”看作一个完整的问题，可以把问题拆分成如下步骤：

1. 问题对象（Problem Definition）：研究的对象和结果
   1. 输入：给定的微观马尔科夫链，包括微观状态空间 [math]\displaystyle{ S }[/math]、微观转移矩阵 [math]\displaystyle{ P }[/math] 以及相应的稳态分布 [math]\displaystyle{ \pi }[/math]。
   2. 输出：一个宏观马尔科夫链，包括宏观状态空间 [math]\displaystyle{ S' }[/math]、宏观转移矩阵 [math]\displaystyle{ P' }[/math]。具体来说，需要确定划分矩阵 [math]\displaystyle{ \Phi }[/math]（哪些微观状态归为一组）和聚合方式 [math]\displaystyle{ W }[/math]（如何从微观动力学构建宏观动力学）。
2. 合法性条件（Requirements & Constraints）：要求一个粗粒化方案（必须或至少近似）满足合法的、符合物理直觉的的条件
   1. 宏观过程是（近似）马尔科夫的
      • 粗粒化后的宏观状态之间的转移只依赖当前宏观状态，不依赖于"是从哪个微观状态粗粒化而来的"。如果不满足，宏观过程会产生记忆效应，不再是马尔科夫链。
   2. 宏观和微观动力学的演化保持一致
      • 要求粗粒化与动力学两个算子可交换，即 [math]\displaystyle{ \Phi P' = P \Phi }[/math]
        • 在严格可交换的理想情况下，可以推导出成块性、因果态等结构性条件，从而实现最大可预测性和最小冗余
      • 在一般近似情形下，可以通过多种指标来量化宏观和微观的演化一致性，例如：
        • 在算子层面，直接度量 [math]\displaystyle{ \Phi P' }[/math] 和 [math]\displaystyle{ P \Phi }[/math] 之间的误差
        • 基于统计物理模型的配分函数差异、在宏观和微观过程进行随机游走的权重差异等
        • 将宏观动力学通过逆粗粒化算子还原到微观空间，与真实微观动力学比较所得的预测误差等
   3. 尊重稳态分布下的随机动力学吸引子结构：保留系统长期的动力学特性
      • 粗粒化不应破坏原系统在稳态分布下的基本拓扑结构，如常返类、瞬时态、周期类等。这些结构构成了一种"基准划分"，任何合理的粗粒化至少不应跨越这些结构边界
      • 稳态概率流网络中的主要流量通道结构不能在粗粒化过程中被破坏
3. 目标（Objectives）：在所有合法的粗粒化方案中，我们希望"最好"的那个满足什么
   1. 最大化预测性
      • 在给定尺度和约束下，使宏观状态对未来的预测能力尽可能接近微观最优预测，如最大化宏观状态与未来之间的互信息或最小化预测误差。成块性保证了宏观最大预测性，因果态保证了微观最大预测性。
   2. 最大化有效信息（EI）
      • 使系统在宏观层面的因果效应强度最大，从而揭示因果涌现最显著的尺度
      • 在粗粒化过程中截断线性相关的状态，消除信息冗余，提升因果通道的信息效率。
   3. 最小化随机性、信息损失
      • 在保证预测性和因果强度的前提下，尽量减少从微观到宏观的信息丢失，实现压缩与保真之间的平衡。
   4. 尺度闭合性：宏观动力学能够自洽地独立演化，无需回到微观层次来修正：
      • 因果闭合：宏观层面的因果结构在该尺度上是自洽和封闭的，无需回到微观层次来解释宏观演化
      • 信息闭合：宏观状态包含预测自身未来所需的全部信息，微观状态不会提供额外的预测信息
      • 计算闭合：宏观动力学更新可以完全在宏观层面上进行计算，无需显式访问微观状态
   5. 聚合转出模式相似的状态：
      • 将转出概率模式相似的状态划为一组
      • 将稳态下出流模式相似的状态划为一组
4. 方法 / 算法（Methods / Algorithms）：怎样在给定目标和约束下找到一个好的划分 [math]\displaystyle{ \Phi }[/math]
   1. 划分方法：确定状态的分组方式。包括逐层贪婪算法、谱分解方法（对 [math]\displaystyle{ F }[/math] 或 [math]\displaystyle{ P }[/math] 做 SVD + K-Means 聚类）、遗传算法、GNN 参数化划分等。不同的划分方法隐含了不同的优化目标——例如，对 [math]\displaystyle{ F }[/math] 做 SVD 后聚类右奇异向量是为了恢复成块结构，而对 [math]\displaystyle{ P }[/math] 做 SVD 后聚类降维行向量是为了最大化动力学可逆性。
   2. 聚合方法：确定 [math]\displaystyle{ W }[/math] 的选取方式，包括等权平均（仅适用于成块划分）、稳态分布加权平均（通过 [math]\displaystyle{ F' = \Phi^T F \Phi }[/math]）、高阶网络聚类（HOM）等。

粗粒化与时间演化算子的可交换性

首先，一个重要的粗粒化标准就是 粗粒化操作要和时间演化操作是可交换（commutative）的两个算符。以图（1）所示的情形为展示，我们从某个微观状态 [math]\displaystyle{ s^{(t)} }[/math] 出发，到达下一刻的宏观状态 [math]\displaystyle{ A^{(t+1)} }[/math] 具备两条不同的路径：

1. 先经过微观动力学的时间演化达到 [math]\displaystyle{ s^{(t+1)} }[/math]，再进行粗粒化得到 [math]\displaystyle{ A^{(t+1)} }[/math]
2. 先通过状态的粗粒化得到 [math]\displaystyle{ A^{(t)} }[/math]，再经过宏观动力学的演化到达 [math]\displaystyle{ A^{(t+1)} }[/math]

如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：从任意一个微观状态分布 [math]\displaystyle{ s^{(t)} }[/math] 出发，走这两条路径得到的 [math]\displaystyle{ A^{(t+1)} }[/math] 的分布是一样的，即

[math]\displaystyle{ \begin{aligned} s^{(t)} \Phi P' = s^{(t)} P \Phi \end{aligned} }[/math]

(2)

这两条路径的一致性在粗粒化领域是非常重要，并被反复提及的概念。满足一致性的粗粒化方案能够充分的保留动力学中有效的信息，并丢弃掉无用的信息。具体来说，宏观状态已经捕捉了与未来演化相关的所有“慢变量”或“相关信息”，而被粗粒化掉的那些微观细节，只影响瞬时的噪声或快速弛豫过程，而不会长期地、系统性地改变宏观演化。

对于马尔科夫链，粗粒化时我们通常希望得到一个新的马尔科夫过程：宏观态的转移只依赖当前宏观态，而不依赖更久远的历史。式子（2）说明了，如果粗粒化满足可交换性，那么宏观过程可以写成一个真正意义上的马尔科夫链，拥有一个明确的宏观转移矩阵 [math]\displaystyle{ P' }[/math]，而且宏观态的演化不需要记忆“刚才具体是哪个微观态导致了这个宏观态”。如果不满足，那宏观态的演化一般会带有记忆效应，未来的转移概率还会依赖这个宏观态是如何形成的，也就是依赖过去的轨迹。

成块性

马尔科夫链的成块性（Lumpability）是一种描述马尔科夫链是否可聚类或可粗粒化性质的概念，最早由Kemeny和Snell在其1969年著作Finite Markov Chains中阐述。Lump一词有‘块’的意思。判断一个马尔科夫链是否可成块（lumpable），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其动力学特征的简化链。这种划分需确保：虽然抹除了聚类内部状态的微观差异，但能精确保持块间转移机制。这一特性为状态空间的合理划分提供了严格的数学判据。

符合成块性的粗粒化方案有很多很好的性质，如保证了对宏观层面上的最大预测性、保证了微观与宏观过程的一致性等。这使得成块性成为马尔科夫链维度约简研究中最常用的标准之一。

成块性的初始定义比较复杂，详见马尔科夫链的成块性。在这里，我们介绍其定义的充分必要条件，一个更直观的解析。在某些文献中，作者们会直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的。

成块性的充分必要条件

设[math]\displaystyle{ p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k) }[/math]，[math]\displaystyle{ p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m} }[/math]，[math]\displaystyle{ p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i) }[/math]，作者提出了判断一个马尔科夫链对给定划分 [math]\displaystyle{ A }[/math] 是否成块的充分必要条件为：

对于任意一对[math]\displaystyle{ A_i, A_j }[/math]，每一个属于[math]\displaystyle{ A_i }[/math]的状态[math]\displaystyle{ s_k }[/math]的[math]\displaystyle{ p_{s_k \rightarrow A_j} }[/math]都是一样的。也就是说，[math]\displaystyle{ A_i }[/math]里的每一个状态[math]\displaystyle{ s_k }[/math]转移到[math]\displaystyle{ A_j }[/math]中的所有状态的转移概率之和是相同的，

[math]\displaystyle{ \forall i, j, \forall s_k, s_m \in A_i, p_{s_k \rightarrow A_j} = p_{s_m \rightarrow A_j} }[/math]

(3)

成块性充分必要条件实例

满足这个条件后，我们就可以将[math]\displaystyle{ A_j }[/math]中的所有微观状态[math]\displaystyle{ s_l }[/math]合并为一个宏观状态[math]\displaystyle{ A_j }[/math]，因为它们从其他宏观状态的转入概率是一致的。同样的，我们也可以将[math]\displaystyle{ A_i }[/math]中的所有微观状态[math]\displaystyle{ s_k }[/math]合并为一个宏观状态[math]\displaystyle{ A_i }[/math]，因为这些微观状态[math]\displaystyle{ s_k }[/math]（和[math]\displaystyle{ A_i }[/math]）到其他宏观状态的转出概率是一致的。

例如，在下图中，[math]\displaystyle{ s_1 }[/math]和[math]\displaystyle{ s_2 }[/math]都属于[math]\displaystyle{ A_1 }[/math]，它们到[math]\displaystyle{ A_1 }[/math]和[math]\displaystyle{ A_1 }[/math]的转移概率是一样的；同样，[math]\displaystyle{ s_3 }[/math]和[math]\displaystyle{ s_4 }[/math]都属于[math]\displaystyle{ A_2 }[/math]，它们到宏观状态的转移概率也是一样的。因此，[math]\displaystyle{ [[1,2], [3, 4]] }[/math]是[math]\displaystyle{ P }[/math]的一个成块划分。

基于这个条件，我们可以定义成块划分的宏观动力学[math]\displaystyle{ A^{(t)} = A^{(t-1)} P' }[/math]：

对于给定的微观状态 [math]\displaystyle{ S }[/math]，微观动力学 [math]\displaystyle{ p_{s_k \rightarrow s_m} }[/math] 和成块的划分 [math]\displaystyle{ A }[/math]，宏观动力学 [math]\displaystyle{ p_{A_i \rightarrow A_j} }[/math] 等于 [math]\displaystyle{ A_i }[/math] 中任意状态 [math]\displaystyle{ s_k }[/math] 到[math]\displaystyle{ A_j }[/math] 的概率：

[math]\displaystyle{ \begin{aligned} p_{A_i \rightarrow A_j} = p_{s_k \rightarrow A_j} = \sum_{s_m \in A_j} p_{s_k \rightarrow s_m}, k \in A_i \end{aligned} }[/math]

(4)

这个公式表明，群组[math]\displaystyle{ A_i }[/math]到群组[math]\displaystyle{ A_j }[/math]的转移概率 = 群组[math]\displaystyle{ A_i }[/math]中任意状态[math]\displaystyle{ s_k }[/math]到群组[math]\displaystyle{ A_j }[/math]的转移概率 = 群组[math]\displaystyle{ A_i }[/math]中任意状态[math]\displaystyle{ s_k }[/math]到群组[math]\displaystyle{ A_j }[/math]中的所有状态的转移概率之和。

我们也可以直接定义[math]\displaystyle{ P }[/math]和[math]\displaystyle{ P' }[/math]之间的关系：

[math]\displaystyle{ P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1} }[/math]，

其中，[math]\displaystyle{ \Phi^T \Phi }[/math]是一个对角阵，对角线上的元素为每个[math]\displaystyle{ A_i }[/math]包括了多少个微观状态的计数，其逆矩阵就是把对角线上的元素全部取倒数。

在讨论成块性时，必须明确状态划分的方式。不同的划分方式可能导致不同的结论。一个马尔科夫链可能在某种划分下是成块的，而在另一种划分下则不成块。这里用一个简单的例子提供正例和反例。

我们用到的是这样一个转移矩阵：

[math]\displaystyle{ \begin{aligned} P = P_{s_i \rightarrow s_j} = \left [ \begin{array}{ccc:c} 0.3 & 0.3 & 0.3 & 0.1 \\ 0.3 & 0.3 & 0.3 & 0.1 \\ 0.3 & 0.3 & 0.3 & 0.1 \\ \hdashline0.1 & 0.1 & 0.1 & 0.7 \end{array} \right ] \end{aligned} }[/math]

我们可以看到，123行都是一样的，所以把他们 [math]\displaystyle{ \{s_1, s_2, s_3\} }[/math] 分在一组 [math]\displaystyle{ A_1 }[/math]，并把状态 [math]\displaystyle{ s_4 }[/math] 分在另外一组 [math]\displaystyle{ A_2 }[/math]。这个分组 [math]\displaystyle{ \{\{s_1,s_2，s_3\}, \{s_4\}\} }[/math] 中每一个属于 [math]\displaystyle{ A_i }[/math] 的状态 [math]\displaystyle{ s_k }[/math] 的 [math]\displaystyle{ p_{s_k \rightarrow A_j} }[/math] 都是一样的，而这个分组对应的宏观转移矩阵为 [math]\displaystyle{ \begin{aligned} P = P_{A_k \rightarrow A_l} = \left [ \begin{array}{c:c} 0.9 & 0.1 \\ \hdashline0.3 & 0.7 \end{array} \right ] \end{aligned} }[/math]

而反例就是分组 [math]\displaystyle{ \{\{s_1,s_2\}, \{s_3,s_4\}\} }[/math]，并不满足成块性的条件定义。

成块性的主要性质

成块性作为一种较为严格的划分方式，虽然在压缩维度上可能不如其他方法显著，但它能够保留在宏观层面上所有有用的信息，并且确保粗粒化前后过程的一致性。

宏观最大预测性

宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们只用宏观状态就能预测后续的宏观状态。

具体来说，只需要知道宏观状态 [math]\displaystyle{ A^{(t)} }[/math]，就可以最大化 [math]\displaystyle{ A^{(t+1)} }[/math] 的预测效果，而微观状态 [math]\displaystyle{ s^{(t+1)} }[/math] 虽然能提供一些额外信息，但是对于预测 [math]\displaystyle{ A^{(t+1)} }[/math] 并无帮助。

这意味着条件互信息 [math]\displaystyle{ I(A^{(t+1)}; s^{(t+1)} | A^{(t)}) = 0 }[/math]。宏观动力学不需要任何来自微观状态的修正，就能独立且正确地反映系统在宏观层面上的演化。

尽管成块性划分能够准确预测宏观动力学，但它无法确保像计算力学中的因果态那样的微观最大预测性。因为在聚类过程中会损失微观状态的信息，使得我们无法辨别某个[math]\displaystyle{ A^{(t)} }[/math]具体是哪个微观态[math]\displaystyle{ s^{(t)} }[/math]。这个信息的损失是不可逆的，所以从微观粗粒化到宏观之后，就无法再还原到微观了。

成块划分和粗粒化的可交换性

我们在马尔科夫链的成块性中推导了结论：基于成块性划分的粗粒化方法满足粗粒化和动力学这两个算子的可交换性。

一致性Consistency

我们在马尔科夫链的成块性中推导了结论：基于成块性划分的粗粒化方法构建的宏观网络与微观网络是一致的。

因果态

此部分为对因果态的简略介绍，因果态相关详情请参照计算力学词条。

定义

在计算力学中，状态被理解为智能体所接收到的全部历史信息，所以将系统从过去到未来的变化用一个离散的稳定随机过程描述。状态空间为双（向）无限序列的集合 [math]\displaystyle{ \overleftrightarrow{S}=\{\cdots, s_{-2}, s_{-1}, s_0, s_1, s_2, \cdots\} }[/math]，即无限长的时间序列。基于当前的时刻 [math]\displaystyle{ t }[/math]，我们可以将 [math]\displaystyle{ \overleftrightarrow{S} }[/math] 分为单侧前向序列 [math]\displaystyle{ \overleftarrow{s_t}=\{\cdots, s_{t-3}, s_{t-2}, s_{t-1}\} }[/math] 和单侧后向序列 [math]\displaystyle{ \overrightarrow{s_t}=\{s_t, s_{t+1}, s_{t+2}, s_{t+3},\cdots\} }[/math] 两个部分。所有可能的未来序列 [math]\displaystyle{ \overrightarrow{s_t} }[/math] 形成的集合记作 [math]\displaystyle{ \overrightarrow{S} }[/math]，所有可能的历史序列 [math]\displaystyle{ \overleftarrow{s_t} }[/math] 形成的集合记作 [math]\displaystyle{ \overleftarrow{S} }[/math]。

因果态是一种对系统状态的粗粒化描述，并没有假设系统的马尔科夫性，为了把因果态和马尔科夫链的粗粒化理论进行比较，可以定义马尔科夫链的因果态：假设系统是一个[math]\displaystyle{ K }[/math]阶的马尔科夫链（系统在[math]\displaystyle{ t }[/math]时刻的状态分布是由前K个时刻的状态决定的），则可将 [math]\displaystyle{ \overleftarrow{S} }[/math] 重新定义为 [math]\displaystyle{ S^K }[/math]。

因果态示意图， t = 9 和 t = 13 为同一因果态

因果态是最优的划分方法得到的宏观态，具有最强的预测能力和最简洁的形式。形式化定义如下：

对于任意时刻 [math]\displaystyle{ t }[/math] 和 [math]\displaystyle{ t^{'} }[/math]，若给定过去状态 [math]\displaystyle{ \overleftarrow{s_t} }[/math] 和 [math]\displaystyle{ \overleftarrow{s_{t^{'}}} }[/math] 时，未来状态 [math]\displaystyle{ \overrightarrow{s} }[/math] 的分布完全相同，则称 [math]\displaystyle{ \overleftarrow{s_t} }[/math] 与 [math]\displaystyle{ \overleftarrow{s_{t^{'}}} }[/math] 等价，也叫预测等价性（predictive equivalence），记为：

[math]\displaystyle{ t \sim t^{'} \equiv \overleftarrow{s_{t^{'}}} \sim \overleftarrow{s_t} \triangleq P(\overrightarrow{s}|\overleftarrow{s_t} ) = P(\overrightarrow{s} |\overleftarrow{s_{t^{'}}} ) }[/math]

(4)

因果态可定义为映射 [math]\displaystyle{ \epsilon{:}\overleftarrow{S}\mapsto2^{\overset{\leftarrow}{S}} }[/math]，满足：[math]\displaystyle{ \epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\overrightarrow{S}=\overrightarrow{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\overrightarrow{S}=\overrightarrow{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime})，\mathrm{for~all~}\overrightarrow{s}\in\overrightarrow{S},\stackrel{\leftarrow}{s}^{\prime}\in\stackrel{\leftarrow}{S}\} }[/math]

所有的因果态的集合由预测等价关系"[math]\sim[/math]"诱导的商集定义：[math]\mathcal{S}=\stackrel{\leftarrow}{S}/\sim[/math]

如上图所示，[math]\displaystyle{ t_9 }[/math] 和 [math]\displaystyle{ t_{13} }[/math] 时刻对未来状态的预测分布相同，处于同一因果态；[math]\displaystyle{ t_{11} }[/math]时刻预测分布不同，处于不同的因果态。

因果态的主要性质

为什么我们要关注因果态这样一种特定的宏观态呢？下面是因果态的两个主要性质，能够体现出因果态是一种最理想的宏观态：

微观最大预测性

微观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们只用宏观状态就能预测后续的微观状态。

具体来说，只需要知道宏观状态 [math]\displaystyle{ A^{(t)} }[/math]，就可以最大化 [math]\displaystyle{ s^{(t+1)} }[/math] 的预测效果。

对于宏观态 [math]\displaystyle{ \mathcal{\forall R} }[/math] 和正整数 [math]\displaystyle{ L }[/math]，都有 [math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{R}]\geq H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] }[/math]，[math]\displaystyle{ \stackrel{\rightarrow}{S}^L }[/math] 为长度为 [math]\displaystyle{ L }[/math] 的未来序列集合，[math]\displaystyle{ \mathcal{S} }[/math] 为因果态划分，所有可能的历史序列记作 [math]\displaystyle{ \overleftarrow{S} }[/math]。[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{R}] }[/math] 和 [math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] }[/math] 是 [math]\displaystyle{ \stackrel{\rightarrow}{S}^L }[/math] 的条件熵。可以理解为因果态集合 [math]\displaystyle{ \mathcal{S} }[/math] 是在所有的划分宏观态集合 [math]\displaystyle{ \mathcal{R} }[/math]中，预测能力最强的一种宏观态，证明过程请参照计算力学词条。

最小随机性

设[math]\displaystyle{ \hat{\mathcal{R}} }[/math]和[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]为满足性质1中不等式等号成立的宏观态，则对于所有的[math]\displaystyle{ \hat{\mathcal{R}} }[/math]和[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]，都有[math]\displaystyle{ H[\hat{\mathcal{R}}^{\prime}|\hat{\mathcal{R}}]\geq H[\mathcal{S}^{\prime}|\mathcal{S}] }[/math]，其中[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]和[math]\displaystyle{ \mathcal{S}^{\prime} }[/math]分别是该过程的下一时刻状态和下一时刻因果态。

该性质可以被理解为在相同预测能力的前提下，因果态集合[math]\displaystyle{ \mathcal{S} }[/math]在所有的宏观态[math]\displaystyle{ \mathcal{R} }[/math]的集合中，随机性最小。

用互信息的角度去理解的话，上式等价于[math]\displaystyle{ I(\mathcal{S}^{\prime};\mathcal{S})\geq I(\hat{\mathcal{R}}^{\prime};\hat{\mathcal{R}}) }[/math]，可以理解为因果态为所有的与它自己的下一时刻的互信息中的最大的一个宏观态。

尺度闭合性

当我们做跨尺度粗粒化时，一个核心问题是：粗粒化得到的「宏观动力学」能不能自己演化、自己预测，而不用再依赖「微观动力学」的状态信息来修正？直观地说，就是看微观层和宏观层之间，计算和演化是不是可以“各自独立”。

在哲学中，这种现象常被叫做因果闭合（因果闭包）。Barnett 和 Anil Seth 在他们关于「动力学解耦」的工作中认为：在一个复杂系统中，在一个复杂系统里（比如动物身体），如果宏观动力学（肢体运动）可以自主演化、并且在预测时不需要回到微观动力学（细胞活动）去补充信息，那么我们就可以说这里出现了涌现。

而Rosas等人的工作进一步形式化了这个想法。他们提出，在评估“不同尺度是否能独立演化”时，可以考察三种不同尺度之间的闭合性：因果闭合、信息闭合和计算闭合。

这里的“闭合”指的是：在给定粗粒化方案下，宏观尺度对微观尺度是闭合的。一旦达到闭合，我们就可以说宏观尺度在某种意义上实现了“独立演化”。

单尺度因果态和ϵ-机器

因果态示例，出自Rosas于因果涌现读书会第五季第一期的分享

在前文关于「计算力学」的部分，我们已经简单介绍过因果态。这里为了和原文符号对应，再用更正式的方式回顾一下。

在时序系统中，ϵ-machine（ϵ-机器）使用历史记忆 [math]\displaystyle{ \overleftarrow{X_t}=\{... , X_{t-2}, X_{t-1}, X_t\} }[/math] 来预测未来状态的轨迹 [math]\displaystyle{ p(\overrightarrow{X}^L_t| \overleftarrow{X_t}) }[/math]，其中[math]\displaystyle{ \overrightarrow{X}^L_t=\{X_{t+1}, X_{t+2}, ... , X_{t+L}\} }[/math]，简写成[math]\displaystyle{ \overrightarrow{X_t} }[/math]。

因果态就是，把所有能给出相同未来预测分布的历史，被划到同一类：[math]\displaystyle{ E = \{E_t\}_{t \in \mathbb{N} }, E_t = \epsilon( \overleftarrow{X_t} ) }[/math]，[math]\displaystyle{ \overleftarrow{x_t} \equiv \overleftarrow{x_{t'}}\ \ \text{iff}\ \ p(\overrightarrow{x_t}| \overleftarrow{x_t} ) = p(\overrightarrow{x_{t'}}|\overleftarrow{x_{t'}}) }[/math]

所以，ϵ-机器做两件事：

1. 把当前历史 [math]\displaystyle{ \overleftarrow{X_t} }[/math] 映射到一个因果态 [math]\displaystyle{ E_t }[/math]；
2. 再用这个因果态来预测未来 [math]\displaystyle{ \overrightarrow{X_t} }[/math] 。

我们可以把ϵ-机器理解为最小解释模型：用尽可能少的宏观状态，既能稳定地描述系统，又能很好地预测未来。这个宏观状态就是因果态。

跨尺度因果态和υ-机器

三种因果态的示意图，摘录自文章原文

现在我们引入一个粗粒化函数 [math]\displaystyle{ f }[/math]，将微观过程 [math]\displaystyle{ X_t }[/math] 映射到宏观过程 [math]\displaystyle{ Z_t = f(X_t) }[/math]。普通的ϵ-机器只能在同一尺度上工作（[math]\displaystyle{ X }[/math] 空间），而Rosas 等人提出的υ-machine（υ-机器），专门处理微观→宏观的跨尺度预测。

他们把因果态中的未来状态从微观的 [math]\displaystyle{ X }[/math] 改为宏观的 [math]\displaystyle{ Z }[/math]，并定义微观状态 [math]\displaystyle{ X }[/math] 中的等价关系为

[math]\displaystyle{ \overleftarrow{x_t} \equiv \overleftarrow{x_{t'}} \ \ \text{iff}\ \ p( \overrightarrow{z_t} | \overleftarrow{x_t}) = p(\overrightarrow{z_{t'}}| \overleftarrow{x_{t'}}) }[/math]

(5)

也就是说，υ-机器把拥有同样 [math]\displaystyle{ p(\overrightarrow{z_t}| \overleftarrow{x_t}) }[/math] 的 [math]\displaystyle{ \overleftarrow{x_t} }[/math] 和 [math]\displaystyle{ \overleftarrow{x_{t'}} }[/math] 定义为υ-机器的因果态，[math]\displaystyle{ U = \{U_t\}_{t \in \mathbb{N} },\ U_t = υ( \overleftarrow{X_t} ) }[/math]

直观上，υ-机器在所有微观历史中，找到一个最粗的划分，同时又能对宏观未来 [math]\displaystyle{ \overleftarrow{Z_t} }[/math] 保持最大预测性，因此是一个“最优的信息瓶颈”。

所以，在给定粗粒化 [math]\displaystyle{ Z_t = f(X_t) }[/math] 后，可以有三种因果态：

1. 微观ϵ-机器，因果态为 [math]\displaystyle{ E }[/math]；

1. 宏观ϵ-机器，因果态为 [math]\displaystyle{ E' }[/math]；

1. 跨尺度υ-机器，因果态为 [math]\displaystyle{ U }[/math]；

这三种机器的区别大概是：

1. [math]\displaystyle{ U_t }[/math] 比 [math]\displaystyle{ E'_t }[/math] 更强（powerful），因为后者只包括了宏观的信息，而前者同时包括了宏观和微观的信息；
2. [math]\displaystyle{ E_t }[/math] 比 [math]\displaystyle{ U_t }[/math] 更强，因为 [math]\displaystyle{ U_t }[/math] 只保留了宏观的最大预测性，而 [math]\displaystyle{ E_t }[/math] 能保留微观的最大预测性（同时因为我们知道 [math]\displaystyle{ f }[/math] ，所以 [math]\displaystyle{ E_t }[/math] 也能保留宏观的最大预测性）。

由此可以得到两个关键结论（证明见不同尺度之间的闭合性）：

推断1：[math]\displaystyle{ I(\overleftarrow{X_t}; \overrightarrow{Z_t}) = I(U_t; \overrightarrow{Z_t}) }[/math]：υ-机器的因果态 [math]\displaystyle{ U_t }[/math] 完全概括了微观历史 [math]\displaystyle{ \overleftarrow{X_t} }[/math] 对宏观未来 [math]\displaystyle{ \overrightarrow{Z_t} }[/math] 的全部信息量。

推断2：υ-机器的因果态 [math]\displaystyle{ U_t }[/math] 对宏观 [math]\displaystyle{ \overrightarrow{Z_t} }[/math] 提供的信息量 大于等于 宏观本身的 ϵ-机器的因果态 [math]\displaystyle{ E'_t }[/math]。

了解了跨尺度因果态的定义后，我们就能逐个了解这篇文章中的三种闭合定义。

因果闭合 Causal Closure

定义：当宏观过程 [math]\displaystyle{ Z_t }[/math] 的 ϵ-机器 与 跨尺度的 υ-机器 的因果态分组相互一一对应，即 [math]\displaystyle{ E' }[/math] 和 [math]\displaystyle{ U }[/math] 之间存在双射（bijective）投影关系时，称粗粒化 [math]\displaystyle{ Z_t = f(X_t) }[/math] 满足因果闭合。

在这种情况下，所有微观历史 [math]\displaystyle{ \overleftarrow{X_t} }[/math] 在预测宏观未来 [math]\displaystyle{ Z }[/math] 上的差异，都会完整地体现在宏观历史 [math]\displaystyle{ \overleftarrow{Z_t} }[/math] （ϵ-机器）中，不会在粗粒化过程中被抹掉。所以，因果闭合的物理意义为：宏观上的干预，和它在微观层面的对应干预，在宏观结果上完全等价。

当我们对 [math]\displaystyle{ Z }[/math] 进行干预的时候，微观 [math]\displaystyle{ X }[/math] 的状态也会跟着改变，就像当我们加热了一锅水的时候，其中的水分子的能量也会改变。对 [math]\displaystyle{ Z }[/math] 空间进行的干预影响到 [math]\displaystyle{ X }[/math] 空间时，按照 [math]\displaystyle{ X }[/math] 的动力学进行演化后再粗粒化得到的 [math]\displaystyle{ Z }[/math]，与直接在 [math]\displaystyle{ Z }[/math] 空间上进行演化没有区别。

因此，一旦因果闭合成立，只用宏观动力学就能正确追踪干预后的演化，不必回到微观 [math]\displaystyle{ X }[/math] 层溯源。所以这就是宏观和微观之间因果闭合了，即宏观动力学在因果性上能做到独立的演化。

信息闭合 Information Closure

上面的因果闭合强调“干预–因果”，而信息闭合则从“预测–信息”出发。

用互信息来刻画[math]\displaystyle{ Z_t }[/math] 本身的ϵ-机器和 [math]\displaystyle{ Z_t = f(X_t) }[/math] 之间的υ-机器对宏观未来 [math]\displaystyle{ \overrightarrow{Z_t} }[/math]的预测能力，可以写成：

[math]\displaystyle{ I( \overleftarrow{Z_t} ; \overrightarrow{Z_t}) = I( \overleftarrow{X_t} ; \overrightarrow{Z_t}) }[/math]

(6)

这就是信息闭合的条件：宏观历史 [math]\displaystyle{ \overleftarrow{Z_t} }[/math] 和微观历史 [math]\displaystyle{ \overleftarrow{X_t} }[/math] 对宏观未来 [math]\displaystyle{ \overrightarrow{Z_t} }[/math] 提供的信息量完全相同。

因此，只知道 [math]\displaystyle{ \overleftarrow{Z_t} }[/math] 就足以做最优预测，再加上底层的 [math]\displaystyle{ \overleftarrow{X_t} }[/math] 也不能提升预测能力。也就是说，微观信息在预测宏观 [math]\displaystyle{ \overrightarrow{Z_t} }[/math] 时是冗余的。所以，一个尺度在信息意义上“闭合”，便是在说这个尺度上系统可以“自给自足”，不需要再考虑其他尺度。

根据跨尺度因果态介绍中的推断2，可以证明：对给定的 [math]\displaystyle{ Z_t = f(X_t) }[/math]，因果闭合和信息闭合这两个条件是等价的：由于[math]\displaystyle{ I(U_t ; \overrightarrow{Z_t}) = I(E'_t ; \overrightarrow{Z_t}) }[/math]，所以[math]\displaystyle{ I(U_t ; \overrightarrow{Z_t}) = I( \overleftarrow{X_t}; \overrightarrow{Z_t}) = I( \overleftarrow{Z_t} ; \overrightarrow{Z_t}) = I(E'_t ; \overrightarrow{Z_t}) }[/math]。

另外，当信息闭合时也满足： [math]\displaystyle{ I(\overrightarrow{Z_t}; \overleftarrow{X_t} | \overleftarrow{Z_t}) = I(\overleftarrow{Z_t}, \overleftarrow{X_t} ; \overrightarrow{Z_t}) - I(\overrightarrow{Z_t} ; \overleftarrow{Z_t}) = I(\overleftarrow{X_t} ; \overrightarrow{Z_t}) - I(\overrightarrow{Z_t} ; \overleftarrow{Z_t}) = 0 }[/math]

计算闭合 Computational Closure

计算闭合可交换性示意图，摘录自文章原文

定义：[math]\displaystyle{ Z }[/math] 的 ϵ-机器为计算闭合，当满足：存在粗粒化函数 [math]\displaystyle{ f^* }[/math]使得 [math]\displaystyle{ E'_t = f^*(E_t) }[/math]，其中[math]\displaystyle{ E_t }[/math] 和 [math]\displaystyle{ E'_t }[/math] 分别为 [math]\displaystyle{ X }[/math] 和 [math]\displaystyle{ Z }[/math] 的ϵ-机器的因果态。也就是说， 宏观因果态是微观因果态的“合并版本”（一对一或多对一）。

从 [math]\displaystyle{ X }[/math] 到 [math]\displaystyle{ E' }[/math] 有两条路径：

1. [math]\displaystyle{ X \stackrel{\epsilon}{\rightarrow} E \stackrel{f^*}{\rightarrow} E' }[/math]
2. [math]\displaystyle{ X \stackrel{f}{\rightarrow} Z \stackrel{\epsilon'}{\rightarrow} E' }[/math]

把 [math]\displaystyle{ f }[/math] 和 [math]\displaystyle{ f^* }[/math] 视作粗粒化算子，[math]\displaystyle{ \epsilon }[/math] 和 [math]\displaystyle{ \epsilon' }[/math] 视作因果态算子，那么我们看到，先粗粒化再找因果态 = 先找因果态再粗粒化，在机制层面是“可交换”的。

上面提到过 ϵ-机器可以看作最小解释模型，描述了动力学的机制。所以，因果态空间 [math]\displaystyle{ E }[/math] 和 [math]\displaystyle{ E' }[/math] 可以看作是动力学的‘机制空间’。而计算闭合的意义是指出，这种动力学不仅在本来的变量/状态空间中能够被粗粒化 [math]\displaystyle{ f:X \to Z }[/math] ，而且它的机制也能被对应的粗粒化 [math]\displaystyle{ f^*: E \to E' }[/math]。因此，宏观的计算机制可以看作是微观机制的简化版。

换句话说，如果一个系统在某个粗粒化 [math]\displaystyle{ f }[/math] 下是计算闭合的，那么我们可以从微观机器出发，在机制层面自然得到了宏观机器，从而实现一个干净的多尺度计算模型。

对于一台机器，我们肯定希望它的宏观的计算过程要更加的简洁，也就是说宏观的ϵ-机器最好是微观的ϵ-机器的一种粗粒化。难道宏观机器还可以不是微观机器的粗粒化吗？粗粒化意味着宏观变量是微观变量的单射，这个映射过程可能引入更多的噪音，导致宏观过程的因果态反而比微观的还要多。我们在不同尺度之间的闭合性中介绍了一个具体例子，请感兴趣的读者自行查阅。

计算闭合与前面的因果闭合/信息闭合之间的关系是：对同一个粗粒化函数 [math]\displaystyle{ Z_t = f(X_t) }[/math] ：若它是因果闭合 / 信息闭合的，那么它一定也是计算闭合的；反之不一定，也就是说，计算闭合是一个相对更“宽松”的条件。证明请参照不同尺度之间的闭合性。

尺度闭合 与 成块性

Geiger 和 Temmel 的工作把马尔可夫链的成块性与信息条件联系了起来。

对一个不可约（irreducible），和非周期性（aperiodic）的马尔科夫链 [math]\displaystyle{ X }[/math] ，若[math]\displaystyle{ Z_t=f(X_t) }[/math] 是状态空间上定义的粗粒化函数，有：

1. [math]\displaystyle{ X }[/math] 的强成块性 在其达到稳态（stationary）分布时 等价于 [math]\displaystyle{ H(Z_{t+1}|Z_t) = H(Z_{t+1}|X_t) }[/math]。

1. [math]\displaystyle{ X }[/math] 的弱成块性 在其达到稳态分布时 等价于 [math]\displaystyle{ H(Z_{t+1}|Z_t) = H(Z_{t+1}|Z_{\lt t}) }[/math]。

Rosas等人认为，当使用 [math]\displaystyle{ Z_t }[/math] 来预测 [math]\displaystyle{ Z_{t+1} }[/math] 时，可以拆分为两步：先利用宏观 [math]\displaystyle{ Z_t }[/math] 推断微观 [math]\displaystyle{ X_t }[/math]，再利用微观 [math]\displaystyle{ X_t }[/math] 估算宏观 [math]\displaystyle{ Z_{t+1} }[/math]。所以，

推断1：当一个马尔科夫链 [math]\displaystyle{ X_t }[/math] 存在粗粒化函数 [math]\displaystyle{ Z_t=f(X_t) }[/math]，而 [math]\displaystyle{ X_t }[/math] 对 [math]\displaystyle{ f }[/math] 强成块时，则 [math]\displaystyle{ Z_t }[/math] 满足因果闭合/计算闭合。（反之未必成立，详情请参考论文反例6）。证明请参考词条不同尺度之间的闭合性。

推断2：假设存在 [math]\displaystyle{ Z=f(E)=f(\epsilon(X)) }[/math]，[math]\displaystyle{ E }[/math] 为 [math]\displaystyle{ X_t }[/math] 的ϵ-机器的因果态，那么 [math]\displaystyle{ E }[/math] 对 [math]\displaystyle{ Z }[/math] 是弱成块的条件 等价于 [math]\displaystyle{ Z_t }[/math] 计算闭合的条件。证明请参考词条不同尺度之间的闭合性。

原文用一张关系图总结了这些概念：

1. 对给定 [math]\displaystyle{ f }[/math]，因果闭合性 等价于 信息闭合性。
2. 当 [math]\displaystyle{ f }[/math] 因果/信息闭合时，它一定计算闭合。
3. 当一个稳态的马尔科夫链 [math]\displaystyle{ X_t }[/math] 对 [math]\displaystyle{ Z_t = f(X_t) }[/math] 强成块时，则 [math]\displaystyle{ f }[/math] 一定因果/信息闭合。
4. 当稳态的 [math]\displaystyle{ X_t }[/math]的因果态 [math]\displaystyle{ E_t }[/math] 对 [math]\displaystyle{ Z_t = f(E_t) }[/math] 弱成块时，[math]\displaystyle{ Z_t }[/math] 计算闭合。

因果涌现：最大化有效信息

因果涌现（causal emergence）是指动力系统中的一类特殊的涌现现象，即系统在宏观尺度会展现出更强的因果特性。特别的，对于一类马尔科夫动力系统来说，在对其状态空间进行适当的粗粒化以后，所形成的宏观动力学会展现出比微观更强的因果特性——即更大的有效信息，那么我们称该系统发生了因果涌现。

定义

在马尔科夫链中，任意时刻的状态变量[math]X_t[/math]都可以看作是原因，而下一时刻的状态变量[math]X_{t+1}[/math]就可以看作是结果，这样马尔科夫链的状态转移矩阵就是它的因果机制。

有效信息（Effective Information，简称EI）是因果涌现 Causal Emergence理论中的一个核心概念，它可以用来衡量一个马尔科夫动力学的因果效应的强度。这里，因果效应是指把动力学看做一个黑箱，那么不同的输入分布就会导致不同的输出分布，二者之间联系的紧密程度就是因果效应：

[math]\displaystyle{ \begin{aligned} EI &= I(X_t,X_{t+1}|do(X_t\sim U(\mathcal{X})))=I(\tilde{X}_t,\tilde{X}_{t+1}) \\ &= \sum^N_{i=1}\sum^N_{j=1}Pr(\tilde{X}_t=i,\tilde{X}_{t+1}=j)\log \frac{Pr(\tilde{X}_t=i,\tilde{X}_{t+1}=j)}{Pr(\tilde{X}_t=i)Pr(\tilde{X}_{t+1}=j)} = \sum^N_{i=1}Pr(\tilde{X}_t=i)\sum^N_{j=1}Pr(\tilde{X}_{t+1}=j|\tilde{X}_t=i)\log \frac{Pr(\tilde{X}_{t+1}=j|\tilde{X}_t=i)}{Pr(\tilde{X}_{t+1}=j)}\\ &= \frac{1}{N}\sum^N_{i=1}\sum^N_{j=1}p_{ij}\log\frac{N\cdot p_{ij}}{\sum_{k=1}^N p_{kj}}=\frac{1}{N}\cdot \sum_{i=1}^N\left(P_i\cdot \log P_i - P_i\cdot\log \bar{P}\right)\\ &=\frac{1}{N}\sum_{i=1}^N D_{KL}(P_i||\bar{P}) \end{aligned} }[/math]

其中 [math]\displaystyle{ \tilde{X}_t,\tilde{X}_{t+1} }[/math] 分别为把 [math]\displaystyle{ t }[/math] 时刻的 [math]X_t[/math]干预为均匀分布后，前后两个时刻的状态。从上面式子不难看出，EI仅仅是概率转移矩阵 [math]P[/math] 的函数。将转移概率矩阵 [math]P[/math] 写成 [math]N[/math] 个行向量拼接而成的形式，即：[math]\displaystyle{ P=(P_1^T,P_2^T,\cdots,P_N^T)^T }[/math]。将矩阵每列求均值，可得到平均转移向量 [math]\displaystyle{ \overline{P}=\sum_{k=1}^N P_k/N }[/math]。因此，EI是转移矩阵每个行转移向量 [math]P_i[/math] 与平均转移向量 [math]\bar{P}[/math] 的KL散度的均值。

有效信息通常可以分解为两个部分：确定性（Determinism）和简并性（Degeneracy）： [math]\displaystyle{ EI = \frac{1}{N}\cdot \sum_{i=1}^N\left(P_i\cdot \log P_i - P_i\cdot\log \bar{P}\right) =\underbrace{-\langle H(P_i)\rangle}_{确定性项}+\underbrace{H(\bar{P})}_{非简并性项} }[/math]

确定性是指，在动力学的作用下，我们根据系统前一时刻的状态会以多大程度预测它下一时刻状态；简并性是指：果知道了系统的当前状态，能不能反推系统在上一时刻的状态的能力，如果可以推断，则这个马尔科夫矩阵的简并性就会比较低，也就是非简并的；而如果很难推断，则马尔科夫矩阵就是简并的，也即退化的。如果确定性越大，或简并性越小，则系统的有效信息就会越大。其他相关详情请参照有效信息词条。

下表展示的是三个不同的转移概率矩阵，以及它们的EI数值：

马尔科夫链示例

[math]\displaystyle{ P_1=\begin{pmatrix} &0 &0 &1 &0& \\ &1 &0 &0 &0& \\ &0 &0 &0 &1& \\ &0 &1 &0 &0& \\ \end{pmatrix} }[/math],	[math]\displaystyle{ P_2=\begin{pmatrix} &1/3 &1/3 &1/3 &0& \\ &1/3 &1/3 &1/3 &0& \\ &0 &0 &0 &1& \\ &0 &0 &0 &1& \\ \end{pmatrix} }[/math],	[math]\displaystyle{ P_3=\begin{pmatrix} &1/4 &1/4 &1/4 &1/4& \\ &1/4 &1/4 &1/4 &1/4& \\ &1/4 &1/4 &1/4 &1/4& \\ &1/4 &1/4 &1/4 &1/4& \\ \end{pmatrix} }[/math].
[math]EI(P_1)=2[/math] bits	[math]EI(P_2)=1[/math] bits	[math]EI(P_3)=0[/math] bits

上面所列 [math]\displaystyle{ P_1, P_2, P_3 }[/math] 的EI各为：2比特、1比特和0比特。由此可见，如果 [math]\displaystyle{ P_1, P_2, P_3 }[/math] 中出现更多的独热（one-hot）向量，则EI值就会更大。也就是说，如果在状态转移的过程中，从某一时刻到下一时刻的跳转越确定，则EI值就会倾向于越高。

最大化有效信息的划分

开头提到，对马尔科夫链做粗粒化的其中一个动机就是，想抹除一些微观动力学上的噪音，而得到在宏观上更具规律和因果性的动力学。所以，我们可以利用EI这一马尔科夫链的因果效应度量，来衡量聚类后的宏观动力学的因果强度。

但是，EI的大小和状态空间大小有关，这一性质在我们比较不同尺度的马尔科夫链的时候非常不方便，我们需要一个尽可能不受尺度效应影响的因果效应度量。因此，我们需要对有效信息EI做一个归一化处理，得到和系统尺寸无关的一个量化指标。根据Erik Hoel和Tononi等人的工作，要用均匀分布即最大熵分布下的熵值，即[math]\displaystyle{ \log N }[/math]来做分母对EI进行归一化，这里的[math]N[/math]为状态空间[math]\mathcal{X}[/math]中的状态的数量。那么归一化后的EI便等于：

[math]\displaystyle{ Eff=\frac{EI}{\log N} }[/math]

进一步定义归一化指标也称为有效性（effectiveness）。

有了有效信息这一度量指标后，我们便可以讨论马尔科夫链上的因果涌现了。对于一个马尔科夫链，观察者可以建立多尺度视角去观测，区分出微观和宏观。首先，原始的马尔科夫概率转移矩阵 [math]\displaystyle{ P_N }[/math] 即定义了微观动力学；其次，经过对微观态的粗粒化映射（coarse-graining）后（通常反映为对微观状态的分组），观察者可以得到对应的宏观状态（即分组），这些宏观状态彼此之间的概率转移可以用宏观的马尔科夫概率转移矩阵 [math]\displaystyle{ P_M }[/math] 来刻画。对两个动力学分别可以计算EI，如果宏观的EI大于微观EI，我们说该系统发生了因果涌现。

因果涌现示意图

可以定义一个新的指标直接度量因果涌现的程度：

[math]\displaystyle{ ce = Eff(P_M) - Eff(P_N) = \frac{EI(P_M)}{\log M} - \frac{EI(P_N)}{\log N} }[/math]

这里[math]P[/math]为微观状态的马尔科夫概率转移矩阵，维度为：[math]N\times N[/math]，这里N为微观的状态数；而[math]P'[/math]为对[math]P[/math]做粗粒化操作之后得到的宏观态的马尔科夫概率转移矩阵，维度为[math]M\times M[/math]，其中[math]M<N[/math]为宏观状态数。如果计算得出的[math]\displaystyle{ ce \gt 0 }[/math]，则称该系统发生了因果涌现，否则没有发生。

下面，我们展示一个具体的因果涌现的例子：

马尔科夫链示例

[math]\displaystyle{ P_m=\begin{pmatrix} &1/3 &1/3 &1/3 &0& \\ &1/3 &1/3 &1/3 &0& \\ &1/3 &1/3 &1/3 &0& \\ &0 &0 &0 &1& \\ \end{pmatrix} }[/math],	[math]\displaystyle{ P_M=\begin{pmatrix} &1 &0 & \\ &0 &1 & \\ \end{pmatrix} }[/math].
[math]\begin{aligned}&Det(P_m)=0.81\ bits,\\&Deg(P_m)=0\ bits,\\&EI(P_m)=0.81\ bits\end{aligned}[/math]	[math]\begin{aligned}&Det(P_M)=1\ bits,\\&Deg(P_M)=0\ bits,\\&EI(P_M)=1\ bits\end{aligned}[/math]

在这个例子中，微观态的转移矩阵是一个4*4的矩阵，其中前三个状态彼此以1/3的概率相互转移，这导致该转移矩阵具有较小的确定性，因此EI也不是很大为0.81。然而，当我们对该矩阵进行粗粒化，也就是把前三个状态合并为一个状态a，而最后一个状态转变为一个宏观态b。这样所有的原本三个微观态彼此之间的转移就变成了宏观态a到a内部的转移了。因此，转移概率矩阵也就变成了[math]P_M[/math]，它的EI为1。在这个例子中，可以计算它的因果涌现度量为：

[math]\displaystyle{ ce=Eff(P_M)-Eff(P_m)=1-0.405=0.595 }[/math]

当[math]\displaystyle{ ce }[/math]越大，说明宏观动力学的因果效应更强，也说明宏观动力学能够更好地表示系统的因果涌现。

最大化动力学可逆性 Dynamical Reversibility

基于可逆性的因果涌现理论是一种量化因果涌现的新框架，提出了近似动力学可逆性（[math]\displaystyle{ \Gamma_{\alpha} }[/math]）的概念，用于量化马尔科夫动力学接近可逆动力学的程度。 该理论的核心思想是指出所谓的因果涌现其实等价于动力学可逆性的涌现。该指标与有效信息具有高度的相关性，因而也可以用于刻画动力学的因果效应强度。

直观地说，如果将一个马尔科夫动力学看作是一个通信信道，那么，每一状态下的概率转移就看作是一个信息通路（information pathway），于是该系统发生因果涌现就等价于系统中存在着冗余的信息通路——存在着一些状态转移与其它状态转移相似或线性相关，而消除这些冗余通路的最好办法就是利用SVD找到等于零或接近于零的奇异值以及对应的奇异向量，这实际上正是最大化有效信息的精髓所在。事实上，我们可以证明，最大化宏观动力学有效信息的粗粒化方案近似等价于将系统的动力学向较大奇异值对应的奇异向量方向做投影的粗粒化方案。而且，系统所能达到的最大信息传输效率的提升（归一化的近似动力学可逆性），就可以定义为因果涌现的强度。

所以，给定一个系统的马尔科夫转移矩阵，通过对它进行奇异值分解，将奇异值 [math]\displaystyle{ \sigma_i }[/math]的 [math]\displaystyle{ \alpha }[/math] 次方之和定义为马尔科夫动力学的近似可逆性度量（[math]\displaystyle{ \Gamma_{\alpha}\equiv \sum_{i=1}^N\sigma_i^{\alpha} }[/math]），用以刻画最终指标偏向于衡量确定性或简并性的程度。通常我们取 [math]\displaystyle{ \alpha=1 }[/math]，表示平权考虑确定性或简并性对最终可逆性度量的影响。

基于可逆性的因果涌现理论与已有的其他因果涌现理论最大的区别就是不需要指定粗粒化策略，仅从马尔科夫转移矩阵的奇异值谱就能判断因果涌现的发生，直接定义所谓清晰因果涌现（clear causal emergence）和模糊因果涌现（vague causal emergence）的概念，在一定程度上规避了因果涌现结果依赖于粗粒化策略的问题和最大化有效信息的难以优化求解的问题。其次，这套理论指出一个动力系统的因果涌现特性仅仅是系统线性化算符的奇异值谱决定的，因而是一套更加反映系统动力学特性本身的因果涌现理论。相关详情请参照基于可逆性的因果涌现理论词条。

我们可以由矩阵 [math]\displaystyle{ P }[/math] 的秩 [math]\displaystyle{ r }[/math] 和矩阵的弗罗贝尼乌斯范数（Frobenius norm，F-norm）找到 [math]\displaystyle{ P }[/math] 的近似动力学可逆性与矩阵奇异值之间的联系。

首先，矩阵的秩可以被写作：[math]\displaystyle{ r=\sum_{i=1}^{N}\sigma_{i}^{0} }[/math]，其中 [math]\displaystyle{ \sigma_{i} }[/math] 是矩阵 [math]\displaystyle{ P }[/math] 的第 [math]\displaystyle{ i }[/math] 个奇异值，[math]\displaystyle{ N }[/math] 是马尔科夫链的状态数。

紧接着，矩阵的F-norm可以被写作：[math]\displaystyle{ {||P||}_{F}^{2}=\sum_{i=1}^{N}\sigma_{i}^{2} }[/math]。这也是所有奇异值的平方和。可以看出矩阵的秩和F-norm都与奇异值相联系。事实上，当且仅当 [math]\displaystyle{ P }[/math] 的行向量是独热向量的时候，矩阵P的弗罗贝尼乌斯范数取最大值。

由于绝大部分马尔科夫链的状态转移矩阵都不是置换矩阵，所以我们需要一个指标来刻画其靠近（可逆的）置换矩阵的程度。这就是矩阵 [math]\displaystyle{ P }[/math] 的 [math]\displaystyle{ \alpha }[/math] 阶近似动力学可逆性。定义为：

[math]\displaystyle{ \begin{aligned} \Gamma_{\alpha}=\sum_{i=1}^{N}\sigma_{i}^{\alpha}\end{aligned} }[/math]

其中[math]\displaystyle{ \alpha\in(0,2) }[/math]是参数。当 [math]\displaystyle{ \alpha\ge1 }[/math] 时，[math]\displaystyle{ \Gamma_{\alpha} }[/math] 是 [math]\displaystyle{ P }[/math] 的沙滕范数（Schatten norm）；当 [math]\displaystyle{ 0\lt \alpha\lt 1 }[/math] 时，[math]\displaystyle{ \Gamma_{\alpha} }[/math] 是 [math]\displaystyle{ P }[/math] 的准范数（quasinorm）。使用这个定义来刻画近似动力学可逆性是合理的，因为完全动力学可逆性可以通过最大化 [math]\displaystyle{ \Gamma_{\alpha} }[/math] 来得到。我们可以证明如下结论：对于任意 [math]\displaystyle{ \alpha\in(0,2) }[/math]，[math]\displaystyle{ \Gamma_{\alpha} }[/math] 的最大值是 [math]\displaystyle{ N }[/math]，当且仅当 [math]\displaystyle{ P }[/math] 是置换矩阵的时候能取到该最大值。

张江等人提供了一种基于奇异值分解的粗粒化方法，以获得宏观层面的简化TPM。其基本思想是将 [math]\displaystyle{ P }[/math] 中的行向量 [math]\displaystyle{ P_{i},\forall i \in [1,N] }[/math]投影到 [math]\displaystyle{ P }[/math] 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 [math]\displaystyle{ P }[/math] 的主要信息，并保持 [math]\displaystyle{ \Gamma }[/math] 不变。

最大化动力学可逆性的合理性来源于这套SVD方案定义的因果涌现与最大化有效信息的因果涌现定义的密切关系。在Erik Hoel因果涌现理论的框架内，给定马尔可夫动力学系统的因果涌现的大小依赖于粗粒化策略的选择，可以通过宏观动力学的EI最大化寻找最优的粗粒化策略。

我们可以证明，要想获得最大化有效信息的粗粒化策略也近似等价于是向最大奇异值对应的奇异向量方向投影的策略。严格推导可见基于有效信息的因果涌现理论。由于对于离散的马尔可夫链来说，粗粒化策略往往都是比较严格的0或1构成的向量，因此并不能简单地根据奇异向量来直接投影。但是，如果粗粒化策略尽可能地与最大的几个奇异向量平行，那么就可以让粗粒化后动力学的EI尽可能更大，因此最大化EI的必要条件近似可以认为就是往最大奇异值对应的奇异向量空间做投影。在实际应用中，粗粒化策略 [math]\displaystyle{ \phi }[/math] 的约束（例如，宏观动力学TPM的分组和归一化）会阻止 [math]\displaystyle{ \phi_j }[/math] 与奇异向量完美对齐。因此，基于SVD的粗粒化策略只是最大化EI的近似必要条件。

动力学一致性

好的粗粒化方案是能够尽可能保证原始的网络（或转移矩阵）和粗粒化后的网络（或转移矩阵）尽可能地相似。Erik Hoel 和 Klein 提出使用动力学一致性来衡量在原始网络和粗粒化后网络上演化的状态的轨迹的一致性。详情请见复杂网络中的因果涌现词条。

以下关于动力学的一致性检验的描述节选自复杂网络中的因果涌现：

定义微观网络 [math]\displaystyle{ G }[/math] 与宏观网络 [math]\displaystyle{ G_M }[/math]，分别在两个网络上进行随机游走。在某个时间 [math]\displaystyle{ t }[/math]，[math]\displaystyle{ G }[/math] 上的预期分布为 [math]\displaystyle{ P_m(t) }[/math]，而 [math]\displaystyle{ G_M }[/math] 上的预期分布为 [math]\displaystyle{ P_M(t) }[/math]。

将 [math]\displaystyle{ P_m(t) }[/math] 分布叠加到宏观宏观 [math]\displaystyle{ G_M }[/math] 的相同节点上，得到 [math]\displaystyle{ P_{M|m}(t) }[/math] 分布。通过计算 [math]\displaystyle{ P_M(t) }[/math] 和 [math]\displaystyle{ P_{M|m}(t) }[/math] 之间的KL散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下：

[math]\displaystyle{ inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)] }[/math]

也就是说，不一致性 表示了 宏观和微观网络节点在不同时刻的概率分布的KL散度之和。

动力学一致性在某种程度上反映了 动力学和粗粒化算子可交换性，但比可交换性更灵活宽松，可以计算不可交换但近似交换的程度。

稳态分布下的随机动力学划分

随机动力学为我们提供了另一个视角来讨论马尔科夫链的 状态分布。

需提醒的是，虽然马尔科夫链是一个随机过程，但一个马尔科夫链的 实例 在演化（根据 TPM 的随机选择）过程的每一步中，仍然是一个确定的状态，而不会变成一个分布；就像一个粒子在网络里流动，在 [math]\displaystyle{ t }[/math] 步以后它仍然是一个处于某个节点的粒子，而不是分裂成了 n 个散落在各个节点上的部分。

所以，马尔科夫链在 [math]\displaystyle{ t }[/math] 时刻的 状态分布 是指，当我们给定一个初始状态分布 [math]\displaystyle{ \mu }[/math] 时，推断/估计 这个系统在 [math]\displaystyle{ t }[/math] 时刻处在各个状态的概率是多少。

另一种视角是，我们可以复制无限多份并行的系统，让这些系统的初始状态服从分布 [math]\displaystyle{ \mu }[/math]，并各自演化（根据TPM的随机选择）[math]\displaystyle{ t }[/math] 步后，我们再去统计这一大群系统中处于每个状态的比例，就是 [math]\displaystyle{ t }[/math] 时刻的 状态分布 了。

现在，再看一下 稳态分布 的定义：马尔科夫链的状态分布为 [math]\displaystyle{ \pi }[/math]，使得 [math]\displaystyle{ \pi P = \pi }[/math]。也就是说，在 [math]\displaystyle{ t=0 }[/math] 时刻，并行的若干个系统的状态服从分布 [math]\displaystyle{ \pi }[/math]；在各自演化 [math]\displaystyle{ t=1 }[/math] 步后，虽然这些系统的状态发生了变化，但统计到的状态仍然服从分布 [math]\displaystyle{ \pi }[/math]。

这样，我们就能利用 随机动力学（Random Dynamical System）中的 不变性（Invariance） 要求来对马尔科夫链的稳态分布进行分析。详细的数学公式和定义请参考马尔科夫链中的随机动力学。

简单来说，一个随机动力系统描述的是一个被随机噪声驱动的演化过程。它由两部分组成：

1. 基础驱动系统（Base Driving System）：可以想象成一个源源不断产生随机影响的环境。它是一个无穷的噪声序列 [math]\displaystyle{ \Omega = \{ ... , \omega_{-1}, \omega_0, \omega_1, ... | \omega_i \in W \} }[/math] 。时间的流逝，就是这个序列不断向左移动（[math]\displaystyle{ \theta }[/math] 操作），让未来的噪声变成当前的噪声。

1. 演化余循环 （Evolution Cocycle）：这是一个演化规则[math]\displaystyle{ \phi }[/math]，它告诉我们系统在当前状态 [math]\displaystyle{ x }[/math] 和当前噪声 [math]\displaystyle{ \omega_0 }[/math] 的共同作用下，下一步会变成什么样。为了能准确的描述系统演化，这个规则必须保证演化的连续性，比如演化 [math]\displaystyle{ s+t }[/math] 步等于先演化 [math]\displaystyle{ s }[/math] 步再演化 [math]\displaystyle{ t }[/math] 步。

我们可以用随机动力学的框架来描述马尔科夫链：它的单步转移可以看作是演化规则 [math]\displaystyle{ \phi }[/math]，而每一步选择走哪条路径的随机性，就对应着噪声 [math]\displaystyle{ \omega }[/math]。

在将马尔科夫链严格定义为了一个随机动力系统 [math]\displaystyle{ (\theta, \phi) }[/math]之后，我们可以定义该系统的 不变性（Invariance），吸引性（Attraction） 和 随机吸引子（Attractor）。在确定的动力系统中，吸引子是系统演化最终会趋向并“陷落”进去的一个状态或区域。但在随机世界里，由于噪声的持续干扰，吸引子本身也变得不确定，它依赖于噪声的路径。这就是随机吸引子 (Random Attractor)：

一个随机集合（即状态的集合） [math]\displaystyle{ A(\omega) }[/math] 要成为吸引子，必须满足三个苛刻的条件：

1. 紧致性 (Compactness)：简单来说，吸引子自身不能是无限分散的。对于有限状态的马尔科夫链，这个条件天然满足。
2. 不变性 (Invariance)：这是最核心的性质，意味着吸引子结构在演化中能够一直保持在其内部。随着系统演化，一旦进入吸引子，就再也无法逃逸出去。而且，吸引子结构不会凭空产生。新吸引子 [math]\displaystyle{ A(\theta \omega) }[/math] 中的任何一个点，都必然是从旧吸引子 [math]\displaystyle{ A(\omega) }[/math] 中的某个点演化而来的。
3. 吸引性 (Pullback Attraction)：无论系统从哪里出发，只要时间足够长，最终都会被“拉回”到吸引子。就像你在旋涡周边的任意位置放下一艘船，让它顺着随机且难以预估的“水流”（噪声路径）漂流。当时间趋于无穷大时，你会发现，无论你最初在哪里放船，最终船都会被吸进旋涡里（即到达的位置都会无限接近于当前时刻的吸引子 [math]\displaystyle{ A(\omega) }[/math]）。

当我们定义了随机吸引子的概念之后，我们就可以非常清晰的解释，为什么在马尔科夫链中，大家经常会讨论可约、周期、滑过这些概念。因为他们展现出了在稳态情况下（经过一段时间的演化之后）的系统分组规律。

基础划分

首先先简单重温一下马尔科夫链中的一些基础定义。

滑过Transient和常返Recurrent

滑过Transient状态：从该状态出发后，经过任意n步也不存在回到该状态的可能路径。

常返Recurrent状态：从该状态出发后，经过n步后能够回到该状态。

我们可以定义一个常返状态组为：组中任意两个状态都互相可达。

所以，我们就能把一条马尔科夫链分解成多个常返状态组和若干个滑过态。

周期性

如果一个常返状态组存在步数 [math]\displaystyle{ n\gt 1 }[/math]，且每个常返状态 [math]\displaystyle{ i }[/math] 只会经过 [math]\displaystyle{ n }[/math] 步才会回到 [math]\displaystyle{ i }[/math]，那么就可以把这个常返状态组分解成 [math]\displaystyle{ n }[/math] 个子集。这里我们借用了知乎上的例子进行说明：

假设一个马尔科夫链的状态按照这样的周期（步数 [math]\displaystyle{ n=3 }[/math]）循环，

[math]\displaystyle{ \{s_1, s_2\} \rightarrow \{s_3, s_4, s_5\} \rightarrow \{s_6\} \rightarrow \{s_1, s_2\} }[/math]

我们就可以把状态划分成 [math]\displaystyle{ \{s_1, s_2\} }[/math]，[math]\displaystyle{ \{s_3, s_4, s_5\} }[/math]，[math]\displaystyle{ \{s_6\} }[/math] 三个子集。

稳态马尔科夫链中的随机吸引子和分组

我们考虑马尔科夫链的以下三种情况：

情况1：不可约、非周期的马尔科夫链

最普通的情况，不可约，没有周期循环的状态。这种马尔科夫链 存在唯一的全局随机吸引子，但它是一个平凡吸引子，即吸引随机集等于状态空间本身：[math]\displaystyle{ A(\omega) = X, \forall \omega }[/math]

情况2：可约的马尔科夫链

设 [math]\displaystyle{ S = T ∪ R_1 ∪ ... ∪ R_m }[/math]，其中 [math]\displaystyle{ T }[/math] 是滑过态（Transiant）集，[math]\displaystyle{ R_i }[/math] 是闭合常返（Recurrent）类。

这种系统会有 [math]\displaystyle{ m }[/math] 个确定性吸引子 [math]\displaystyle{ A_i = R_i }[/math]。系统一旦从过渡区进入某个孤岛 [math]\displaystyle{ R_i }[/math]，就再也出不来了。每一个孤岛 [math]\displaystyle{ R_i }[/math] 就是一个吸引子，它们不依赖于噪声，是固定的“陷阱”。

情况3：不可约、周期为 [math]\displaystyle{ d \gt 1 }[/math] 的马尔科夫链

这种链的所有状态虽然连通，但系统的演化表现出周期性。状态空间分解为 [math]\displaystyle{ d }[/math] 周期子类 [math]\displaystyle{ X = C_0 ∪ C_1 ∪ ... ∪ C_{d-1} }[/math]，系统在这些子类之间循环跳跃，[math]\displaystyle{ C_0 → C_1 → ... → C_{d-1} → C_0 }[/math]。

这里出现了真正意义上的 [math]\displaystyle{ 非平凡随机吸引子 }[/math]。在任何一个时刻，吸引子[math]\displaystyle{ A(\omega) }[/math] 就是当前的周期子类 [math]\displaystyle{ C_j }[/math]。它随着时间（噪声 [math]\displaystyle{ \omega }[/math] 的演化）在 [math]\displaystyle{ C_0, C_1, ... }[/math] 之间循环变化。

随机动力学的视角告诉我们，无论系统如何随机演化，它总会被拉向一个或多个“吸引子”结构。当系统演化到稳态分布之后，这些吸引子内的状态就会展现出相同的演化特性，因此我们能够根据吸引子来对状态进行分组。详细的数学公式和验证请参考马尔科夫链中的随机动力学。

不同粗粒化方法之间的异同

对上述的概念进行一个总结：

1. 粗粒化与时间演化算子的可交换性
   • 本质：要求 / 指标（既是理想要求，又可度量偏差）
2. 成块性
   • 本质：一种结构性性质
   • 作用：给出在“完全可交换、完全宏观马尔科夫”的极限下，粗粒化应满足的严格条件；也可以当作一种“硬约束目标”。
3. 因果态
   • 本质：结构 + 性质，“单尺度下实现最大预测性的最优表征”的理论工具。
4. 尺度闭合性（及因果/信息/计算闭合）
   • 本质：要求 / 性质，是从“多尺度因果结构”角度，对一个粗粒化是否“自洽”的刻画。
5. 因果涌现：最大化有效信息
   • 本质：优化目标 + 评价指标（EI、可逆性）
6. 稳态分布下的随机动力学划分
   • 本质：一种自然划分方式 + 结构性质，像是从随机动力系统视角导出的一类“基准划分”。

所以可以看到，

• 因果涌现相关的有效信息可逆性是纯粹的“优化目标 + 指标”；
• 而可交换性和尺度闭合性更像是“理想要求 / 准则”；
• 成块性、因果态和稳态分布下的随机动力学划分是“结构性性质 / 自然划分”的理论工具。

高阶网络聚类 Higher-order Macronodes v.s. 成块性

我们通过一个简单的成块划分例子来展示，成块性的粗粒化与HOM是如何对应的。该例子的状态转移图如下图所示：

与之相应的状态转移概率矩阵为： [math]\displaystyle{ \begin{aligned} P = P_{s_i \rightarrow s_j} = \left [ \begin{array}{c:c:cc:c:c} 0 & 0 & 0.3 & 0.1 & 0.6 & 0\\ \hdashline 0 & 0 & 0.2 & 0.3 & 0 & 0.5\\ \hdashline 0 & 0 & 0 & 0.7 & 0.2 & 0.1\\ 0 & 0 & 0.7 & 0 & 0.2 & 0.1\\ \hdashline 1.0 & 0 & 0 & 0 & 0 & 0\\ \hdashline 0 & 1.0 & 0 & 0 & 0 & 0\\ \end{array} \right ] \end{aligned} }[/math] 。对于这个转移概率矩阵，[math]\displaystyle{ \{1, 2, \{34\}, 5, 6\} }[/math]是一个成块的划分。其对应的宏观转移概率： [math]\displaystyle{ \begin{aligned} \left [ \begin{array}{c:c:c:c:c} 0 & 0 & 0.4 & 0.6 & 0\\ \hdashline 0 & 0 & 0.5 & 0 & 0.5\\ \hdashline 0 & 0 & 0.7 & 0.2 & 0.1\\ \hdashline 1.0 & 0 & 0 & 0 & 0\\ \hdashline 0 & 1.0 & 0 & 0 & 0\\ \end{array} \right ] \end{aligned} }[/math]

根据上一部分对HOM方法介绍，我们注意到，HOM中各情况的计算方式本质上都是对待合并节点[math]\displaystyle{ A }[/math]中各节点的出流[math]\displaystyle{ W_i^{out} }[/math]（即图中的红色连边）的加权求和。而成块性的特性决定了，群组里的各节点到其他群组的出流[math]\displaystyle{ W_i^{out} }[/math]都是一样的。所以，对相同的[math]\displaystyle{ W_i^{out} }[/math]进行任意加权平均的结果仍然是[math]\displaystyle{ W_i^{out} }[/math]。这意味着，无论根据哪种情况采用哪种加权方法，对于成块划分来说，最终的结果都是一致的，且与成块性的粗粒化结果相同。

由此，我们总结，成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。

成块性 v.s. 有效信息/动力学可逆性

当一个马尔科夫矩阵满足成块性时，同一组的行会受到约束而相似，所以这种成块的矩阵的EI或动力学可逆性也会很高。这就是成块性和因果涌现之间的物理联系。

但是，这两个概念并不完全等价。成块性的目标是想在保证宏观和微观动力学的一致性的情况下去对状态做分组，而因果涌现的主要目标是想最大化粗粒化之后宏观动力学的因果强度。

在普通的成块性例子里，它们粗粒化之后能得到一个EI或者可逆性很高的宏观动力学。但是，当我们考虑一些极端的例子，如下图所示，我们强行让每一组里的状态转移概率都尽可能的不一样，但是加起来又是一样的，满足了成块性的划分。按照这种成块的划分来去做粗粒化，它并不一定得到高的EI或可逆性。相反，我们用另一个不成块的分组来做粗粒化，得到的宏观动力学的EI和可逆性反而会更高。这现象说明：

1. 基于成块性的最优划分不一定等于基于可逆性的最优划分。

1. 成块性的分组数量是基于马尔科夫秩的，而可逆性的分组数量是对奇异值谱的截断位置。

划分方法

当我们想把 [math]\displaystyle{ N }[/math] 个状态的马尔科夫链划分成 [math]\displaystyle{ M }[/math] 组时，待选的划分数量可以由 第二类斯特林数（Stirling numbers of the second kind）表示，[math]\displaystyle{ S(N, M) = \frac{1}{M!} \sum_{k=0}^{M} (-1)^{M-k} \binom{M}{k} k^N }[/math]

待选的划分数量极大，比如[math]\displaystyle{ S(20,10)=1.107e32 }[/math]，几乎不可能通过遍历所有待选划分来寻找最优划分，所以，我们需要使用一些方法来有效的寻找到近似最优解。

逐层贪婪算法

在这个问题中，我们可以采取 自底向上合并（Bottom-Up）的层次聚类（Hierarchical Clustering）方法，即从最细粒度（每个状态单独成组，一共 [math]\displaystyle{ N }[/math] 组）开始，每一步合并两个最相似的组，直到达到目标分组数 [math]\displaystyle{ M }[/math] 。

具体步骤如下：

1. 初始化：每个状态单独成组，[math]\displaystyle{ A_0={{1},{2},…,{N}} }[/math]
2. 在每一层 [math]\displaystyle{ k }[/math] 内：
   1. 遍历所有组对 [math]\displaystyle{ G_p }[/math] 和 [math]\displaystyle{ G_q }[/math]：
      1. 合并为新组 [math]\displaystyle{ G_{new} = G_p \cup G_q }[/math]
      2. 获得新划分 [math]\displaystyle{ =A_k \setminus \{ G_p , G_q \} \cup G_{new} }[/math]
      3. 根据此划分获得新动力学 [math]\displaystyle{ P' }[/math]
      4. 计算 [math]\displaystyle{ P' }[/math] 对应的划分指标
   2. 更新划分 [math]\displaystyle{ A_{k} }[/math] 为该层最优的划分
3. 当剩余分组数 [math]\displaystyle{ |A_k| = M }[/math] 时停止

该算法的复杂度为 [math]\displaystyle{ O \left (\sum_{k=M}^N k^2 \right ) }[/math]，介乎[math]\displaystyle{ O \left ( N^2 \right ) }[/math]和[math]\displaystyle{ O \left ( N^3 \right ) }[/math]之间。

该算法的缺点在于其容易陷入局部最优。一旦进入了某一分支，就无法跳出。为了找到更好的解，我们可以在其基础上使用遗传算法等方法帮助跳出局部最优。

谱分解

谱分解（Spectral Clustering）的思想是利用矩阵的谱，即特征向量，所展示的物理含义进行聚类和划分。

最大化有效信息的谱分解方法

该方法是将原始网络对应的转移矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。

输入：原始包含 [math]\displaystyle{ N }[/math] 个状态的马尔科夫链 [math]\displaystyle{ P }[/math] 和距离超参 [math]\displaystyle{ \epsilon }[/math]；

1. 对 [math]\displaystyle{ P }[/math] 进行矩阵的特征值分解，得到特征值集合 [math]\displaystyle{ \Lambda=\{\lambda_i\}^N_{i=1} }[/math] 与特征向量集合 [math]\displaystyle{ E=\{e_i\}^N_{i=1} }[/math]；
2. 构建新的有偏的特征向量集合 [math]\displaystyle{ E’=\{\lambda_ie_i|\lambda_i≠0\}^N_{i=1} }[/math]，该集合中的每个向量被其对应的特征值所加权，同时去除了零特征值和对应的特征向量（新的状态数量为[math]\displaystyle{ N'=rank(A) }[/math]）。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应了动力学中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
3. 依据 [math]\displaystyle{ E' }[/math] 计算状态间的相似矩阵 [math]\displaystyle{ D_{N'×N'} }[/math]：
   1. 如果状态 [math]\displaystyle{ v_i }[/math] 和 [math]\displaystyle{ v_j }[/math] 分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cosine相似性作为两者间的相似度 [math]\displaystyle{ d_{ij} }[/math] 和 [math]\displaystyle{ d_{ji} }[/math]；
   2. 否则将两个节点间的相似度设为无穷大 [math]\displaystyle{ \infty }[/math]（可以设个比较大的值，如10000）；
4. 基于相似度矩阵[math]\displaystyle{ D_{N'×N'} }[/math]和一个超参[math]\displaystyle{ \epsilon }[/math]（需要线性搜索，可以选择EI最大的参数），使用OPTICS算法（是一种基于密度的划分算法，旨在识别数据集中不同密度的划分结构）进行划分，输出对应超参[math]\displaystyle{ \epsilon }[/math]下的划分方式。

该方案的时间复杂度为[math]\displaystyle{ O(N^3) }[/math]。

缺点：

1. 对大规模动力学进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
2. 聚类算法所需的距离超参[math]\displaystyle{ \epsilon }[/math]需要线性搜索，需要加入人为的先验知识

寻找成块划分的谱分解方法

当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的[math]\displaystyle{ P }[/math]，如图6中的[math]\displaystyle{ \bar{P} }[/math]所示，我们能够很快的找出它的成块划分[math]\displaystyle{ \Phi }[/math]。然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（6）中的[math]\displaystyle{ P_1 }[/math]），或者矩阵包含了如[math]\displaystyle{ P_2 }[/math]的噪声（如图6中的[math]\displaystyle{ P }[/math]，[math]\displaystyle{ P = P_1 + P_2 }[/math]，[math]\displaystyle{ P_1^TP_2 = 0 }[/math]）。在这种情况下，我们通常面临的是像[math]\displaystyle{ P }[/math]这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。

图6：Zhang 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0

针对这一问题，Anru Zhang提出了一种寻找最优划分的方法，其核心是利用稳态流矩阵（frequency matrix）[math]\displaystyle{ F = \mathrm{diag}(\pi) \cdot P }[/math] 的奇异值结构来恢复成块划分。 其中 [math]\displaystyle{ \pi }[/math] 是 [math]\displaystyle{ P }[/math] 的稳态分布，[math]\displaystyle{ F_{ij} = \pi_i P_{ij} }[/math] 可以理解为系统在稳态下从状态 [math]\displaystyle{ i }[/math] 流向状态 [math]\displaystyle{ j }[/math] 的长期概率流量。具体步骤如下

1. 获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样，并由此得到频率矩阵 [math]\displaystyle{ F }[/math]；
2. 获取马尔科夫秩[math]\displaystyle{ r\lt n }[/math] ，或指定一个[math]\displaystyle{ r }[/math]；
3. 对 [math]\displaystyle{ F }[/math] 进行SVD分解，[math]\displaystyle{ F = U \Sigma V^T }[/math]，其中 [math]\displaystyle{ U }[/math] 为左奇异向量，[math]\displaystyle{ V }[/math] 为右奇异向量，[math]\displaystyle{ \Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N}) }[/math] 是一个对角矩阵，包含所有有序奇异值。
4. 通过下列公式得到最优划分 [math]\displaystyle{ \Omega_1, \Omega_2, ... , \Omega_r }[/math]

[math]\displaystyle{ \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]\displaystyle{ v_s }[/math]是第[math]\displaystyle{ s }[/math]类[math]\displaystyle{ \Omega_s }[/math]的特征向量。这个算法的核心思想是：在最优的划分中，[math]\displaystyle{ \Omega_s }[/math]中的状态[math]\displaystyle{ i }[/math]的右奇异向量会和[math]\displaystyle{ v_s }[/math]距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。

这个算法看起来非常熟悉，实际上它与 k-Means 聚类算法非常相似。让[math]\displaystyle{ v_s }[/math]和组里的[math]\displaystyle{ V[i:r] }[/math]距离最小的方法，就是让[math]\displaystyle{ v_s }[/math]成为[math]\displaystyle{ V[i:r] }[/math]这若干个点的中心。回顾一下k-Means算法把n个点聚成r类的目标函数，其中第[math]\displaystyle{ i }[/math]个点被归到第[math]\displaystyle{ c^i }[/math]类，而[math]\displaystyle{ \mu_j }[/math]为第[math]\displaystyle{ j }[/math]类点的中心点：

[math]\displaystyle{ J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 }[/math]

我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。

为什么是对 [math]\displaystyle{ F }[/math] 做 SVD 而不是对 [math]\displaystyle{ P }[/math]？ 论文证明了，当马尔科夫链关于划分 [math]\displaystyle{ \Omega_1, \ldots, \Omega_r }[/math] 是成块的时，[math]\displaystyle{ F }[/math] 存在分解 [math]\displaystyle{ F = F_1 + F_2 }[/math]，其中 [math]\displaystyle{ F_1 }[/math] 是秩为 [math]\displaystyle{ r }[/math] 的成块部分，[math]\displaystyle{ F_2 }[/math] 是组内局部动力学部分，两者行空间正交（[math]\displaystyle{ F_1 F_2^T = 0 }[/math]）。[math]\displaystyle{ F_1 }[/math] 的右奇异向量 [math]\displaystyle{ V_{F_1} }[/math] 具有分段常数结构：同一组 [math]\displaystyle{ \Omega_k }[/math] 内的所有状态，其行向量 [math]\displaystyle{ (V_{F_1})_{[i,:]} }[/math] 完全相同，不同组之间则有明确间距。因此，K-Means 可以精确恢复分组。而[math]\displaystyle{ P }[/math] 的奇异向量并没有这个性质。

从物理上看，[math]\displaystyle{ F }[/math] 编码的是稳态下的概率流量结构，而 [math]\displaystyle{ P }[/math] 编码的是条件转移分布。对 [math]\displaystyle{ F }[/math] 做 SVD 相当于在稳态概率流网络中寻找主要的流量通道结构——低频状态对应的流量通道自然被压低权重，不会干扰大尺度结构的识别。

当系统存在明显的近成块结构时，[math]\displaystyle{ F }[/math] 的前 [math]\displaystyle{ r }[/math] 个奇异值主要反映的是组间的大尺度概率流通道，而后续的奇异值反映的是组内的局部流量波动。如果这两部分之间存在明显的谱间隙（singular value gap），即 [math]\displaystyle{ \sigma_r(F_1) \gg |F_2| }[/math]，那么 K-Means 聚类 [math]\displaystyle{ \hat{V}_F }[/math] 就能准确恢复成块划分。

这对应于一种特殊但常见的物理场景：系统各状态群之间的长期概率流量远弱于群内流量，形成类似"准吸引域"的结构——粒子长时间在群内游走，偶尔才跨越群边界。当 [math]\displaystyle{ P }[/math] 不是精确成块，而是近似成块（near-lumpable）时，该方法仍然可以工作，但需要满足一个关键条件：组间动力学 [math]\displaystyle{ F_1 }[/math] 的奇异值必须主导 [math]\displaystyle{ F }[/math] 的整体奇异值谱，即 [math]\displaystyle{ \sigma_r(F_1) \gg \|F_2\| }[/math]。

需要注意的是，成块性的数学定义本身并不要求并不要求准吸引域结构（群内流量强于群间流量）。成块性只要求同组状态到各组的转移概率总量相同，并不约束转移的方向强弱。论文给出了分组错误率的上界：

[math]\displaystyle{ \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]\displaystyle{ |F_2| \gtrsim \sigma_r(F_1) }[/math]），SVD 提取的前 [math]\displaystyle{ r }[/math] 个方向会反映组内的局部动力学模式而非组间的成块结构，此时该方法会给出错误的分组。

最大化可逆性的谱分解方法

张江等人动力学可逆性的文章提供了另一种基于 SVD 的粗粒化方法。该工作出发点与与上面寻找成块划分的方法不同：它不以恢复某种预设的结构性划分为目标，而是直接以最大化宏观动力学的可逆性为优化方向。其核心物理图像是：将马尔科夫动力学看作一个通信信道，每个状态下的概率转移看作一条信息通路（information pathway）。当系统的 [math]\displaystyle{ N }[/math] 条通路中存在线性相关的行向量时，这些通路是冗余的——它们要么传递极少的信息（对应接近零的奇异值），要么可以被其他通路的线性组合表示。

通过 SVD 可以识别出 [math]\displaystyle{ r_\epsilon }[/math] 条"核心通路"，其余 [math]\displaystyle{ N - r_\epsilon }[/math] 条是可以消除的冗余通路。粗粒化就是把状态按照它们在核心通路上的表现进行归组，让宏观动力学只保留这些高效通道。其基本思想是将 [math]\displaystyle{ P }[/math] 中的行向量 [math]\displaystyle{ P_{i},\forall i \in [1,N] }[/math] 投影到 [math]\displaystyle{ P }[/math] 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 [math]\displaystyle{ P }[/math] 的主要信息，并保持 [math]\displaystyle{ \Gamma }[/math] 不变。

与 EI 相比，[math]\displaystyle{ \Gamma_\alpha }[/math] 能捕捉到 EI 无法感知的信息：EI 基于 KL 散度，只能度量行向量之间的相似性；而 [math]\displaystyle{ \Gamma_\alpha }[/math] 基于线性代数，还能度量行向量之间的线性依赖性。两个行向量可以彼此很不像（KL 散度大），但仍然线性相关（一个是另一个的线性组合）。后一种情况下，EI 看不出冗余，但 [math]\displaystyle{ \Gamma_\alpha }[/math] 能通过秩亏反映出来。

算法具体步骤如下：

1. 给定含有 [math]\displaystyle{ N }[/math] 个状态的马尔科夫矩阵 [math]\displaystyle{ P }[/math]，对其做 SVD 分解 [math]\displaystyle{ P = U \Sigma V^T }[/math]；
2. 根据奇异值谱设定阈值 [math]\displaystyle{ \epsilon }[/math]，取前 [math]\displaystyle{ r_\epsilon }[/math] 个右奇异向量，构成 [math]\displaystyle{ V_{N \times r_\epsilon} }[/math]；
3. 对 [math]\displaystyle{ P }[/math] 的行向量做 PCA 降维：[math]\displaystyle{ \tilde{P} = P \cdot V_{N \times r_\epsilon} }[/math]，得到每个状态在核心通路子空间上的投影；这一步的物理含义是：[math]\displaystyle{ P^T P }[/math] 是转移概率矩阵的自相关矩阵，其特征向量 [math]\displaystyle{ V }[/math] 给出了"哪些目的地模式是相关联的"这一信息的主轴。[math]\displaystyle{ \tilde{P}i = P_i \cdot V{N \times r_\epsilon} }[/math] 是状态 [math]\displaystyle{ i }[/math] 的出转移分布在这些主要模式上的投影——保留了该状态"在核心通路上的行为"，滤去了冗余通路上的波动。
4. 对 [math]\displaystyle{ \tilde{P} }[/math] 的行向量用 K-Means 聚类为 [math]\displaystyle{ r_\epsilon }[/math] 组，得到划分 [math]\displaystyle{ \Phi }[/math]；
5. 基于划分 [math]\displaystyle{ \Phi }[/math] 和稳态流矩阵 [math]\displaystyle{ F = \mathrm{diag}(\pi) P }[/math]，通过 [math]\displaystyle{ F' = \Phi^T F \Phi }[/math] 构建宏观稳态流矩阵，再对每行归一化得到宏观转移矩阵 [math]\displaystyle{ P' }[/math]。

最后用 [math]\displaystyle{ F' = \Phi^T F \Phi }[/math] 而非直接对 [math]\displaystyle{ P }[/math] 做行列聚合，可以保证粗粒化操作和时间演化算子具有可交换性，从而确保宏观动力学仍是合法的马尔科夫链。

虽然该工作与前面Zhang & Wang的方法都做了SVD + kmeans的步骤，但是两者之间存在差异：

1. Zhang & Wang的工作目标是在粗粒化过程中尽量保持马尔科夫性，并恢复成块结构；而动力学可逆性工作的目标是在粗粒化过程中减少 TPM 中的信道冗余性。
2. Zhang & Wang方法的 SVD 对象是 [math]\displaystyle{ V_F }[/math]，稳态流矩阵的右奇异向量，而动力学可逆性的SVD对象是 [math]\displaystyle{ V_P }[/math]，马尔科夫转移矩阵的右奇异向量。当 [math]\displaystyle{ P }[/math] 恰好是低秩的时，[math]\displaystyle{ V_F }[/math] 和 [math]\displaystyle{ V_P }[/math] 张成完全相同的子空间（因为 [math]\displaystyle{ F = \mathrm{diag}(\pi) P }[/math]，两者秩相同时列空间一致）。当 [math]\displaystyle{ P }[/math] 是近似低秩（满秩但有奇异值谱间隔）时，稳态分布 [math]\displaystyle{ \pi }[/math] 的加权效应会使两者产生差异：对 [math]\displaystyle{ F }[/math] 做 SVD 天然压低了低频状态的影响，而直接对 [math]\displaystyle{ P }[/math] 做 SVD 则给所有状态平权。

其他方法

寻找最优划分本质上是个组合优化问题，所以我们也能使用其他合适的方法来解决该问题。

首先是遗传算法。它是一种受生物进化启发的全局优化算法，通过模拟自然选择（选择适应度高的个体作为父代）、交叉（通过父代基因重组生成子代）和变异（以一定概率随机改变子代基因）等机制，在解空间中搜索最优解。其核心流程包括：

1. 种群初始化：随机生成候选解的群体。
2. 在每一步迭代过程中：
   1. 选择：选择最大化目标（划分标准）的个体作为父代。
   2. 交叉：通过父代基因重组生成子代。
   3. 变异：以一定概率随机改变子代基因。

所以，我们可以把上述的逐层贪婪算法和谱分解方法的解作为初始解，通过遗传算法，帮助跳出局部最优解，并寻找到新的全局更优解。

另外，我们也能使用梯度下降方法，搭配深度学习方法，比如图神经网络，来寻找最优划分。比如，在Klein和Hoel等人的论文，以及Griebenow 等人的文献中，把粗粒化方案写成一个分组矩阵，同时将这个分组矩阵参数化，这样把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积，并由此计算EI。之后，使用自动微分方法执行梯度下降算法从而优化分组矩阵，以使得EI最大化。

输入：包含 [math]\displaystyle{ N }[/math] 个节点的原始网络 [math]\displaystyle{ G }[/math]，其对应邻接矩阵为：[math]\displaystyle{ A }[/math]，粗粒化后的网络所包含的节点数：[math]\displaystyle{ K }[/math]；输出：宏观网络 [math]\displaystyle{ G' }[/math]，对应的邻接矩阵为：[math]\displaystyle{ B }[/math]，以及对应的从 [math]\displaystyle{ A }[/math] 到 [math]\displaystyle{ B }[/math] 的粗粒化矩阵：[math]\displaystyle{ M }[/math]

1. 针对一个含有[math]\displaystyle{ N }[/math]个节点的网络[math]\displaystyle{ A }[/math]，随机初始化一个分组矩阵[math]\displaystyle{ M\in \mathbb{R}^{N×K} }[/math]，[math]\displaystyle{ K }[/math]表示分组的大小，其中矩阵里面的每个元素[math]\displaystyle{ m_{iμ}=Pr⁡(v_i\in v_{\mu}) }[/math]，表示微观节点[math]\displaystyle{ v_i }[/math]属于宏观节点[math]\displaystyle{ v_{\mu} }[/math]的概率
2. 根据微观网络和分组矩阵构建宏观网络 [math]\displaystyle{ B }[/math] ，具体计算方法分为两个步骤：1）[math]\displaystyle{ M^T A M }[/math]；2）归一化前一步骤得到的矩阵。
3. 使用带动量的梯度下降方法优化 [math]\displaystyle{ M }[/math] ，优化目标是最大化宏观网络的有效信息EI。

时间复杂度：[math]\displaystyle{ O(N^3) }[/math]

缺点：

1. 初始化分组矩阵的选择，多次重复实验会得到不一样的结果。
2. 依赖神经网络的超参，如学习率、迭代次数等。

对划分的限制

在上述的算法介绍中，并未强调各方法对划分节点的限制。但在实际问题场景里，我们可能需要在寻找划分时加入限制来满足问题的特性。

比如，在社区检测问题中，具有只允许相邻的节点聚合在一起的约束。这要求状态划分必须遵循状态转移图的拓扑结构，同一聚合状态内的节点必须在状态转移图中直接相连或通过短路径可达（如K-邻域）。这种限制确保聚合状态具有空间连贯性，同时大幅减少可行划分数量。

在因果涌现分组问题中，要求同属一组的状态需同属一个马尔科夫毯（Markov blanket）。在一个概率图中，一个节点的马尔科夫毯包括其父节点、子节点以及子节点的其他父节点（配偶节点）。这些节点共同作用，使得该节点与图中的其他节点条件独立，起到一个“信息防火墙”、确保组内状态动态仅通过固定接口与外部交互的作用。该约束确保：

1. 因果独立性：当我们把整个组看作一个宏观状态时，由于组内所有状态的马尔科夫毯相同，意味着这个宏观状态与外部状态的交互（输入和输出）在统计上是一致的；
2. 信息压缩与模式识别：具有相同马尔科夫毯的状态在系统中扮演相似的角色（即它们与其他状态之间的依赖关系相同）。将这些状态聚合成一个宏观状态，相当于识别出了系统中的一个功能模块或模式；
3. 因果涌现：在复杂系统中，这种聚合可能导致宏观层面出现新的因果特性（即涌现）。如果聚合后的宏观状态能产生比单个状态更明确、更强大的因果作用，则称为因果涌现。此时，宏观状态的马尔可夫转移模型可以更有效地预测系统行为。

但也有其他的划分问题不需遵从这类限制。比如在学术网络、网页流网络的场景上的模式识别时，我们可能会判断某些从未合作过的学者具有相似的行为模式，而把他们划分在一组内。

聚合方法

当我们决定了最优的划分之后，就能根据该划分得到聚合后的矩阵了。

假设划分是把若干个状态合成一组，而其他状态各为一组，我们要做的是对原本的矩阵内，待聚合状态对应的若干行和若干列聚合成一行和一列，而其他元素则保持不动。

把一个 [math]\displaystyle{ N \times N }[/math]的矩阵聚合成 [math]\displaystyle{ N' \times N' }[/math]的矩阵 可以分成两步：

1. 把待聚合的列直接进行相加，得到 [math]\displaystyle{ N \times N' }[/math] 的矩阵；
2. 把待聚合的行进行加权平均，得到 [math]\displaystyle{ N \times N }[/math] 的矩阵

入流的聚合方法：直接加和

我们可以把马尔科夫链看做一个状态为节点，转移概率为边。

我们把待聚合节点都放进一个大节点的框 [math]\displaystyle{ M }[/math] 里，会发现每个外面的节点转移进大节点的概率就等于转移进 [math]\displaystyle{ M }[/math] 中所有节点的概率的和，即[math]\displaystyle{ p_{iM} = \sum_{j \in M} p_{ij} }[/math]。如此就能满足每行加和为一的条件。

所以，对入流（若干列）的聚类方法就是把这若干列直接加和，得到的列等于各节点转移到大节点的概率。

出流的聚合方法：加权平均

计算大节点的入流比较简单，而计算大节点的出流会相对较复杂，需要考虑待聚合节点之间的随机游走和状态分布，来计算流出到每个节点的概率。我们可以把出流的聚合看作是对若干行的线性加权平均。

权重一致的平均

在现有的方法中，大多采用最简单的思路：对状态进行权重一致的平均。当我们只看矩阵本身，认为所有的状态都是平等的，应该分配同等的权重，即[math]\displaystyle{ p_{Mj} = \frac{1}{n} \sum_{j \in M} p_{ji} }[/math]。

但是，这种情况只适用于成块的状态划分：由于成块性的同属于一组的微观状态转移到另一组的概率相同的性质，这样的平权平均是没有问题的。但是，当我们对不成块的状态划分进行平权平均时，就会导致宏观和微观的马尔科夫动力学不一致的情况。

权重为平稳分布的平均

当一个随机游走粒子进入到大节点时，它下一步游走到大节点里或大节点外的其他节点的概率时，应考虑其当前处于大节点内的哪个小节点的概率。

设游走粒子在 [math]\displaystyle{ t }[/math] 时刻处于小节点 [math]\displaystyle{ j }[/math] 的概率为[math]\displaystyle{ s_j(t) }[/math]，其下一步游走到其他粒子的概率应为[math]\displaystyle{ p_{Mj}(t) = \frac{1}{\sum_{j \in M} s_j(t)} \sum_{j \in M} s_j(t)\ p_{ji} }[/math] 。

假设游走已达到了平稳分布[math]\displaystyle{ \pi }[/math]，游走粒子处于不同小节点 [math]\displaystyle{ j }[/math] 的概率为[math]\displaystyle{ \pi_j }[/math]，所以其下一步游走到其他粒子的概率应为[math]\displaystyle{ p_{Mj} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j\ p_{ji} }[/math]，而留在大节点的概率为[math]\displaystyle{ p_{MM} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j \ p_{jj} }[/math] 。按照权重为平稳分布对若干行进行加权平均，得到的行仍会满足加和为一的条件。

为了说明如何获得简化的TPM，首先定义一个矩阵，称为稳态流矩阵：[math]\displaystyle{ F_{ij} \equiv \pi_i \cdot P_{ij}, \, \forall i,j \in [1, N], }[/math]。其中，[math]\displaystyle{ \pi }[/math] 是 [math]\displaystyle{ P }[/math] 的稳态分布，即满足[math]\displaystyle{ \pi P = \pi }[/math]。

其次，我们将根据 [math]\displaystyle{ \Phi }[/math] 和 [math]\displaystyle{ F }[/math] 得到粗粒化后的稳态流矩阵：

[math]\displaystyle{ F' = \Phi^T \cdot F \cdot \Phi, }[/math]

其中，[math]\displaystyle{ F' }[/math] 是粗粒化后的平稳流矩阵。在归并的过程中，保持所有矩阵上的流量总量是不变的。

最后，粗粒化后的 [math]\displaystyle{ P' }[/math] 可直接通过归一化每一行得到：

[math]\displaystyle{ P'_i = \frac{F'_i}{ \sum_{j=1}^{N} (F'_i)_j }, \, \forall i \in [1, N]. }[/math]

将 [math]\displaystyle{ N }[/math] 个 [math]\displaystyle{ P'_i }[/math] 拼在一起就能得到最终的 [math]\displaystyle{ P' }[/math] 。可以证明，这样的粗粒化方案可以保证让粗粒化操作和时间演化操作具有可交换的性质（证明可以参考）。

按照该方法进行加和平均，得到的宏观和微观的马尔科夫动力学就会满足一致的条件。虽然该方法直观明了，该方法的问题在于其需要在系统演变到平稳分布前，计算每个 [math]\displaystyle{ t }[/math] 时刻的状态分布概率 [math]\displaystyle{ s_j(t) }[/math]。在达到平稳分布前直接使用[math]\displaystyle{ \pi }[/math]来聚合还是不会满足一致性，所以比较麻烦，而HOM的计算方式则可以解决这个问题。

高阶网络聚类 Higher-Order Macronodes (HOM)

在Klein等人的论文，以及Griebenow 等人的文献中，作者们采用了高阶依赖项建模（HOMs）来对网络节点进行聚合。其目的是为了保证聚合后的宏观网络与原始的微观网络具有相同的随机游走动力学特性。该方法也可以用于对马尔科夫链状态进行合并。

Higher-order Macronodes，是由Jian Xu等人提出，根据给定的微观马尔科夫链和节点划分方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。下面将简单介绍构建宏观 HOM 转移概率矩阵的计算方法。具体方法请参考网络归并。

假设我们把若干个节点视为待合并的节点[math]\displaystyle{ A }[/math]。

1. 计算合并节点的入流：对于其他节点到待合并节点[math]\displaystyle{ A }[/math]的连边，直接加和即可。
2. 计算合并节点的出流：对于待合并节点[math]\displaystyle{ A }[/math]到其他节点的连边，需要考虑三种情况：
   1. 当待合并节点[math]\displaystyle{ A }[/math]间存在连边时；
   2. 当待合并节点[math]\displaystyle{ A }[/math]指向同一个输出节点时；
   3. 当待合并节点[math]\displaystyle{ A }[/math]指向不同输出节点时；
3. 待合并节点[math]\displaystyle{ A }[/math]的出流的计算方式都不一样，如图（7）所示：

图7：HOM节点边权合并示意图

论文中提到，原始的微观动力学和使用该方法聚合后的宏观动力学和能满足其定义的一致性。

复杂网络中的粗粒化方法

复杂网络与马尔科夫链之间存在密不可分的联系。许多复杂网络上的分析方法，比如随机游走等，会利用马尔科夫链动力学的理论。而马尔科夫链同样也会使用到复杂网络的理论分析方法，比如统计物理中的配分函数等。这部分简要介绍了复杂网络中的三种粗粒化方法，具有巨大的应用在马尔科夫链粗粒化问题上的研究潜力。

复杂网络与马尔科夫链的相似性

对一个复杂网络的而言，并不具备一定的动力学，所以需要人为定义一套动力学，借助随机游走子的概念，在网络上定义了一套随机游走动力学。

假设游走子在每一步都会按照边权来进行转移，这种节点间的转移动力学可以用马尔科夫链表示。马尔科夫链的状态对应着复杂网络上的节点，而转移概率对应着网络节点之间的连边权重。

考虑一个连通图 [math]\displaystyle{ G }[/math]，邻接矩阵为 [math]\displaystyle{ A }[/math]，假设图上有 [math]\displaystyle{ N }[/math] 个节点，分别为 [math]\displaystyle{ 1,2,...,N }[/math]，我们定义从节点 [math]\displaystyle{ i\in\left\{1,2,...,N\right\} }[/math] 到节点 [math]\displaystyle{ j\in\left\{1,2,...,N\right\} }[/math] 的转移概率为 [math]\displaystyle{ w_{ij}=\frac{a_{ij}}{\sum_{j}a_{ij}} }[/math]（即对边权进行行归一化），其中 [math]\displaystyle{ a_{ij} }[/math] 表示邻接矩阵的第 [math]\displaystyle{ i }[/math] 行第 [math]\displaystyle{ j }[/math] 列元素，对应从节点 [math]\displaystyle{ i }[/math] 到节点 [math]\displaystyle{ j }[/math] 的边的权重。

由于该网络是连通图，所以分母 [math]\displaystyle{ \sum_{j}a_{ij} }[/math] 会大于[math]\displaystyle{ 0 }[/math]，而且满足行归一化，即 [math]\displaystyle{ \sum_{j=1}^N {w_{ij}}=1 }[/math]。这样我们就定义了一个马尔科夫链，状态空间为 [math]\displaystyle{ \left\{1,2,...,N\right\} }[/math]，从状态 [math]\displaystyle{ i }[/math] 到状态 [math]\displaystyle{ j }[/math] 的转移概率为 [math]\displaystyle{ w_{ij} }[/math]，转移矩阵为 [math]\displaystyle{ W=\left\{w_{ij}\right\}_{N \times N} }[/math]。。

复杂网络的粗粒化方法

谱粗粒化

复杂网络可以被建模为一个马尔科夫过程，它的动力学由邻接矩阵 [math]\displaystyle{ A }[/math] 构建的随机矩阵 [math]\displaystyle{ W }[/math]（或称转移概率矩阵）所描述，定义为 [math]\displaystyle{ W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}} }[/math] 表示从节点 [math]\displaystyle{ j }[/math] 转移到节点 [math]\displaystyle{ i }[/math] 的概率。为实现网络的降维与简化，研究一种基于谱理论的粗粒化方法。该方法的核心在于选取随机矩阵前 [math]\displaystyle{ S }[/math] 个最大非平凡特征向值 [math]\displaystyle{ \lambda^2, \lambda^3, \ldots, \lambda^{S+1} }[/math] 对应的左特征向量 [math]\displaystyle{ \langle u^2 |, \langle u^3 |, \ldots, \langle u^{S+1} | }[/math]，将网络节点映射到该特征向量张成的特征空间。在此基础上，将每个特征向量的值域划分为 [math]\displaystyle{ I }[/math] 个区间，在所有 [math]\displaystyle{ S }[/math] 个特征向量均落入相同区间的节点合并为一个超级节点。从概率角度可以对此粗粒化过程可以解释为，将新超级节点的出边概率为原节点的出边概率的加权平均，其流入概率为原节点的流入概率相加，其他没有合并节点的转移概率保持不变。

结合统计物理与机器学习的网络流方法

我们用扩散方程 [math]\displaystyle{ \frac{d\psi}{d\tau}=-L\psi }[/math] 来描述网络的扩散过程，其中拉普拉斯矩阵 [math]\displaystyle{ L=D-A }[/math] 描述网络的拓扑结构，[math]\displaystyle{ A }[/math] 是邻接矩阵，[math]\displaystyle{ D }[/math] 是度矩阵。扩散方程的解为 [math]\displaystyle{ \psi_{\tau}=e^{-\tau L}\psi_0 }[/math]，体现了信息随时间的演化，其中 [math]\displaystyle{ e^{-\tau L} }[/math] 为时间演化算子，[math]\displaystyle{ [e^{-\tau L}]_{ij} }[/math] 表示经过时间 [math]\displaystyle{ \tau }[/math] 后从节点 [math]\displaystyle{ j }[/math] 到节点 [math]\displaystyle{ i }[/math] 的流量。

利用配分函数 [math]\displaystyle{ Z_{\tau}=Tr(e^{-\tau L}) }[/math]，我们能量化矩阵的全局信息量。矩阵 [math]\displaystyle{ e^{-\tau L} }[/math] 的每个对角元 [math]\displaystyle{ [e^{-\tau L}]_{ii} }[/math] 是第 [math]\displaystyle{ i }[/math] 个节点的信息保留量，对所有对角元求和则能得到所有节点的信息保留量。

通过图神经网络（GNN）的消息传递机制，得到每个节点的向量表征，对节点向量应用Softmax函数，得到分组矩阵 [math]\displaystyle{ S_{N\times M} }[/math]，其中元素 [math]\displaystyle{ s_{ij} }[/math] 表示节点 [math]\displaystyle{ i }[/math] 分到第 [math]\displaystyle{ j }[/math] 个超级节点的概率。

通过 [math]\displaystyle{ \hat{A}=\frac{M}{N}S^{T}AS }[/math] 得到宏观邻接矩阵 [math]\displaystyle{ \hat{A}_{M\times M} }[/math]，其中 [math]\displaystyle{ A_{N\times N} }[/math] 原始网络的邻接矩阵。归一化配分函数 [math]\displaystyle{ \frac{Z}{N} }[/math] 的平均绝对误差（MAE）作为训练图神经网络的损失函数，通过梯度下降优化GNN的参数。

网络规模从 [math]\displaystyle{ N }[/math] 压缩到 [math]\displaystyle{ N^{'} }[/math] 后，得到新的拉普拉斯矩阵 [math]\displaystyle{ L^{'} }[/math] 和配分函数 [math]\displaystyle{ Z^{'} }[/math]，原始网络和压缩后的网络的配分函数的关系是 [math]\displaystyle{ Z=\gamma Z^{'} }[/math]，并且压缩后的配分函数和原始网络的配分函数要尽可能相似，不随时间变化而且误差最小。当 [math]\displaystyle{ \tau=0 }[/math] 时，[math]\displaystyle{ Z=N,Z^{'}=N^{'} }[/math]，为了使之成立，[math]\displaystyle{ \gamma=\frac{N}{N^{'}} }[/math]，所以乘数的有效值为 [math]\displaystyle{ \frac{N}{N^{'}} }[/math]。

马尔科夫链是描述状态仅依赖当前状态的随机过程，通过拉普拉斯矩阵与转移概率的关系，将上述方法应用到马尔科夫链中，在离散时间马尔科夫链中，转移概率矩阵为 [math]\displaystyle{ P }[/math]；在连续时间马尔科夫链中，[math]\displaystyle{ P(t)=e^{-tL} }[/math] 是经过时间 [math]\displaystyle{ t }[/math] 的转移概率矩阵。配分函数 [math]\displaystyle{ Z_t=Tr(e^{-tL}) }[/math] 可以理解为马尔科夫链的所有状态的信息保留总和。

进行稳态分析的时候，当 [math]\displaystyle{ t\rightarrow \infty }[/math] 时，[math]\displaystyle{ e^{-tL} }[/math] 的极限与稳态分布有关，配分函数的渐近行为反映链的长期信息保留特性。通过分析 [math]\displaystyle{ e^{-tL} }[/math] 的特征向量来识别马尔科夫链的状态聚类。

具有自非相似性的复杂网络的粗粒化方法

方法在电子电路（ISCAS89基准电路）和生物信号网络（哺乳动物蛋白质相互作用网络）成功应用，只要网络存在功能模块的重复级联，这个方法就可以应用。它们抽象出来一个“自非相似性”的特性。自非相似性是指复杂网络的不同粗粒化层面，粗粒化单元和网络模体与整体网络的拓扑结构存在显著差异，而不是保持部分与整体的相似性。不同粗粒化层级的粗粒化单元和网络模体通过功能分化实现整体功能。

定义粗粒化单元（CGU）：是最优地作为网络粗粒化节点的模式，具有明确输入、输出端口和内部计算节点的基本电路组件。CGU的集合构成“元素字典”，粗粒化网络为版本由该字典构建。部分节点被CGU替换，实现网络压缩。

CGU的评价维度（优化的属性）：简洁性、简单性和覆盖度。

1. 简洁性：字典中CGU的总数尽可能的少。
2. 简单性：单个CGU的结构尽简单，由黑箱数 [math]\displaystyle{ H }[/math] 决定，[math]\displaystyle{ H }[/math] 越少越简单。 [math]\displaystyle{ H=I+O+2M }[/math]， [math]\displaystyle{ I }[/math] 为输入节点，[math]\displaystyle{ O }[/math] 为输出节点，[math]\displaystyle{ M }[/math] 为混合节点。
3. 覆盖度：粗粒化后消除的节点和边数尽可能多，被CGU覆盖的节点数 [math]\displaystyle{ P_{covered} }[/math] 和边数 [math]\displaystyle{ E_{covered} }[/math] 尽可能多。

针对CGU的评分函数：[math]\displaystyle{ S=[E_{covered}+\alpha P_{covered}]-[\alpha \sum_{i=1}^{N}n_i H_i+\beta N+\gamma\sum_{i=1}^{N} T_i] }[/math]

1. 正向项：对应覆盖度，覆盖度高，得分越高。
2. 负向项：对应简洁性和简单性，CGU 类型越少，内部节点越少，得分越高。

最大化 S 倾向于选择“高频出现、内部节点多且混合节点少” 的 CGU。

采用模拟退化法寻找粗粒化最优的CGU集合，仅以网络模体（在原始网络中出现频率显著高于随机网络的子图）作为候选CGU。 候选CGU的获取方式：先检测 3-6 节点的所有网络模体，再根据每个模体出现的连接特征向量，同一模体不同特征向量的出现视为不同 CGU 候选。

找到最优的粗粒化CGU集合，通过将每个CGU的每一次出现替换为一个节点，形成粗粒化网络。算法可在粗粒化网络上重复执行，获得更高层级的粗粒化。