马尔科夫链的粗粒化

马尔科夫链是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。它可以看作一个n维的状态的序列[math]\displaystyle{ s^{(t)}\ = \{1, ..., n\}^{(t)} }[/math]，每一步的状态转换都有马尔科夫矩阵（满足每一行和为1的条件的方阵）[math]\displaystyle{ P }[/math]决定，即[math]\displaystyle{ p(s^{(t+1)}) = p(s^{(t)}) P }[/math]。[math]\displaystyle{ P }[/math]的每一行对应的每个状态转移到其他状态的概率，即[math]\displaystyle{ p_{ij} = p(s^{(t+1)} = j | s^{(t)} = i) }[/math]。比如，当[math]\displaystyle{ s^{(t)} }[/math]等于第一个状态的时候，[math]\displaystyle{ P }[/math]的第一行展示了[math]\displaystyle{ s^{(t+1)} }[/math]状态的概率。

对马尔科夫链做粗粒化的意义是什么呢？我们看到文献中着重强调这三点：

1. 我们在研究一个超大的系统的时候，比如复杂城市系统时，并不会关注每一个微观的状态的变化，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而从中微观尺度中总结一些中尺度或宏观尺度的规律；
2. 有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；
3. 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练过程的样本效率和任务表现。【Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).】

在粗粒化过程中，我们有很多目标。首先，我们想尽量降低压缩后的动力学维度；其次，我们想在压缩过程中尽量保留动力学中的信息；最后，我们想要压缩后的过程和原本的过程尽量保持一致。在这篇文章里，我们会围绕着这三个维度展开讨论，并介绍一系列针对马尔科夫链的粗粒化方法。

粗粒化

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

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

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

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

多数文献中会出现如图1的定义：

图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]要符合马尔科夫链定义。

我们能看出[math]\displaystyle{ \Phi }[/math]是一个对状态空间[math]\displaystyle{ S }[/math]的分组函数（得到[math]\displaystyle{ S' }[/math]）。而且，我们还需要把[math]\displaystyle{ P }[/math]降维成[math]\displaystyle{ P' }[/math]。

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

1. 对状态空间进行粗粒化：对状态进行分组，决定[math]\displaystyle{ S }[/math]空间中的状态要如何被投影到[math]\displaystyle{ S' }[/math]空间上，也就是得出[math]\displaystyle{ \Phi }[/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{ 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]。

对状态空间进行粗粒化

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

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

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

在这个词条里，我们主要讨论Hard partitioning，主要参考的是，对Soft state aggregation感兴趣的朋友可以自行参阅S. P. Singh, T. Jaakkola, and M. I. Jordan, “Reinforcement learning with soft state aggregation"和Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." Advances in Neural Information Processing Systems 32 (2019).

对转移概率进行粗粒化

得出[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时刻的宏观状态。

而

[math]\displaystyle{ \begin{aligned} W = D^{-1}(\Phi)^T, D = diag(\alpha \Phi), \end{aligned} }[/math]

(2)

其中[math]\displaystyle{ \alpha }[/math]是一个非负对角矩阵。

所以，我们能看到，对马尔科夫链做粗粒化的时候，不仅要对状态空间做降维([math]\displaystyle{ \Phi }[/math])，还要对马尔科夫矩阵都要做降维，当中也包含了对概率空间的降维([math]\displaystyle{ W }[/math])。 [math]\displaystyle{ W }[/math] 式子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]。

判断粗粒化方案符合的性质

最基本的粗粒化方法的约束是要确保粗粒化后的新的[math]\displaystyle{ S' }[/math]和[math]\displaystyle{ T' }[/math]要符合马尔科夫链定义。除此之外也有一些其他的规则，比如：

粗粒化的交换律commutative

按照上面的定义，[math]\displaystyle{ s^{(t)} }[/math]有两个路径能达到[math]\displaystyle{ s'^{(t+1)} }[/math]：

1. 先得到下一步的[math]\displaystyle{ s^{(t+1)} = s^{(t)} P }[/math]，再做粗粒化得到[math]\displaystyle{ s'^{(t+1)} = s^{(t+1)} \Phi }[/math]
2. 先做粗粒化得到[math]\displaystyle{ s'^{(t)} = (s^{(t)}\Phi }[/math]，再得到下一步的[math]\displaystyle{ s'^{(t+1)} = s'^{(t)} P' }[/math]

而交换律则要求从这两条路径得到的结果应该是一样的，即[math]\displaystyle{ s_{t} P \Phi = s_{t} \Phi 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] 是否成块的充分必要条件为：

定理1：

给定划分 [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]：

定义1：成块性的宏观动力学

对于给定的微观状态[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]，看起来像是一个合理的正例。接下来我们来计算一下。

第1组[math]\displaystyle{ A_1 }[/math]的状态[math]\displaystyle{ s_1 }[/math]到第1组[math]\displaystyle{ A_1 }[/math]，[math]\displaystyle{ p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} + p_{s_1 \rightarrow s_3} = 0.3 \times 3 = 0.9 }[/math]

第1组[math]\displaystyle{ A_1 }[/math]的状态[math]\displaystyle{ s_1 }[/math]到第2组[math]\displaystyle{ A_2 }[/math]，[math]\displaystyle{ p_{s_1 \rightarrow A_2} = p_{A_1 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_4} = 0.1 }[/math]

第2组[math]\displaystyle{ A_2 }[/math]的状态[math]\displaystyle{ s_4 }[/math]到第1组[math]\displaystyle{ A_1 }[/math]，[math]\displaystyle{ p_{s_4 \rightarrow A_1} = p_{A_2 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} + p_{s_4 \rightarrow s_3} = 0.1 \times 3 = 0.3 }[/math]

第2组[math]\displaystyle{ A_2 }[/math]的状态[math]\displaystyle{ s_4 }[/math]到第2组[math]\displaystyle{ A_2 }[/math]，[math]\displaystyle{ p_{s_4 \rightarrow A_2} = p_{A_2 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_4} = 0.7 }[/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]

反例

现在我们来看一个反例：把状态12分为一组，状态34分为另一组。同样的，我们来计算一下。这次我们需要对3和4分开计算了。

第1组[math]\displaystyle{ A_1 }[/math]的状态[math]\displaystyle{ s_1 }[/math]到第1组[math]\displaystyle{ A_1 }[/math]，[math]\displaystyle{ p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} = 0.3 \times 2 = 0.6 }[/math]

第1组[math]\displaystyle{ A_1 }[/math]的状态[math]\displaystyle{ s_1 }[/math]到第2组[math]\displaystyle{ A_2 }[/math]，[math]\displaystyle{ p_{s_1 \rightarrow A_2} = p_{A_1 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_3} + p_{s_1 \rightarrow s_4} = 0.4 }[/math]

第2组[math]\displaystyle{ A_2 }[/math]的状态[math]\displaystyle{ s_3 }[/math]到第1组[math]\displaystyle{ A_1 }[/math]，[math]\displaystyle{ p_{s_3 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_3 \rightarrow s_m} = p_{s_3 \rightarrow s_1} + p_{s_3 \rightarrow s_2} = 0.3 \times 2 = 0.6 }[/math]

第2组[math]\displaystyle{ A_2 }[/math]的状态[math]\displaystyle{ s_4 }[/math]到第1组[math]\displaystyle{ A_1 }[/math]，[math]\displaystyle{ p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 }[/math]

这里我们就能看到，[math]\displaystyle{ p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1} }[/math]，当同一组的两个状态[math]\displaystyle{ s_3 }[/math]和[math]\displaystyle{ s_4 }[/math]对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道[math]\displaystyle{ p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1} }[/math]还是[math]\displaystyle{ p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1} }[/math]），假设[math]\displaystyle{ p_{A_2 \rightarrow A_1} = 0.6 }[/math]，我们会发现这样的粗粒化结果违背了成块性一开始的定义（公式(1)），即粗粒化后的转移概率对所有的初始微观状态[math]\displaystyle{ \pi }[/math]都适用。因为当[math]\displaystyle{ \pi = s_4 }[/math]的时候，[math]\displaystyle{ p_{A_2 \rightarrow A_1} = 0.6 }[/math]这个转移概率就是错的，即使[math]\displaystyle{ \pi \neq s_4 }[/math]，任何初始微观状态[math]\displaystyle{ \pi }[/math]都会在某时刻[math]\displaystyle{ n }[/math]达到[math]\displaystyle{ 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]。这个信息的损失是不可逆的，所以从微观粗粒化到宏观之后，就无法再还原到微观了。

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

图3：粗粒化图例

图（3）展示了从某个微观状态[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{ A^{(t+1)} }[/math]的分布是一样的，即，[math]\displaystyle{ s^{(t)} \Phi P' = s^{(t)} P \Phi }[/math]。

证明如下：

对于一个成块的[math]\displaystyle{ P }[/math]，和它的成块划分[math]\displaystyle{ \Phi }[/math]，我们针对[math]\displaystyle{ \Phi = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{array} \right ) }[/math]的例子，其他情况类似。

对于这个[math]\displaystyle{ \Phi }[/math]，我们知道[math]\displaystyle{ P_{11}=A_{11} }[/math]，[math]\displaystyle{ P_{12}+P_{13}+P_{14}=A_{12} }[/math]，[math]\displaystyle{ P_{21}=P_{31}=P_{41}=A_{21} }[/math]，[math]\displaystyle{ P_{22}+P_{23}+P_{24}=P_{32}+P_{33}+P_{34}=P_{42}+P_{43}+P_{44}=A_{22} }[/math]。

由于[math]\displaystyle{ A_{21} }[/math]和[math]\displaystyle{ A_{22} }[/math]的等于关系，[math]\displaystyle{ P \Phi = \left ( \begin{array}{cc} P_{11}' & P_{12}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \end{array} \right ) }[/math]。这相当于将[math]\displaystyle{ P }[/math]的每一行按照划分进行加总，而[math]\displaystyle{ P \Phi }[/math]中同一组的行是相同的。

另一方面，[math]\displaystyle{ \Phi P' }[/math]的含义是将[math]\displaystyle{ P' }[/math]的每一行按照[math]\displaystyle{ \Phi }[/math]复制到对应的微观状态的行中。所以，我们会发现[math]\displaystyle{ \Phi P' }[/math]和[math]\displaystyle{ P \Phi }[/math]的结果是一样的。

一致性Consistency

这一小节里讨论马尔科夫链的成块划分 与 HOM（Higher-order Macronodes，详情请参考复杂网络中的因果涌现）之间的关系，以及它们与一致性的联系。

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

定义微观网络[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散度之和。

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

成块性和粗粒化

基于成块性的粗粒化方法（未给定成块的划分的情况）

从前面的成块性公式（2）和例子中，我们可以直观地理解：当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的[math]\displaystyle{ P }[/math]，如图6中的[math]\displaystyle{ \bar{P} }[/math]所示，我们能够根据上面的定理（1）很快的找出它的成块划分[math]\displaystyle{ \Phi }[/math]，并通过定义（3）迅速计算出对应的[math]\displaystyle{ P' }[/math]。

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

然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（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]这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。

针对这一问题，Anru Zhang提出了一种寻找最优划分的方法。通过这种方法，我们可以找到最优的划分，并基于这个划分判断一个马尔科夫矩阵是否成块。具体步骤如下：

1. 获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
2. 获取[math]\displaystyle{ r\lt n }[/math] 的马尔科夫秩，或指定一个[math]\displaystyle{ r }[/math]；
3. 对P进行SVD分解，[math]\displaystyle{ P = U \Sigma V^T }[/math]，其中U为左奇异向量，V为右奇异向量。
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 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。

因果涌现

有效信息

有效信息相关详情请参照因果涌现词条。

Dynamical Reversibility 动力学可逆性

动力学可逆性相关详情请参照因果涌现词条。

因果态

因果态相关详情请参照计算力学词条。

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

动力学可逆性 v.s. Lumpability

在lumpability的图6中我们提到了lumpable的马尔科夫矩阵可以被重新排列成几个block，这种lumpable的矩阵的动力学可逆性也会很高，在这种情况下动力学可逆性和 Lumpability是一致的。

在没有明显block结构的情况下，我们可以使用上述的SVD+kMeans方式找到最优的lumpability partition并决定它的lumpability。我们在一个动力学可逆性比较高（有明显的因果涌现）的国际贸易网的例子上尝试了一下，却发现该网络上的最优lumpability partition宏观结果的动力学可逆性并不高。这现象说明：

1. Lumpability最优的partition不等于可逆性最优的partition。

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

（未完待续）