812
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − + − 所谓的马尔科夫链的粗粒化，就是指找到一个新的马尔科夫链，它具有 <math>1<M<N</math> 个状态，其对应的 <math>M</math> 行 <math>M</math> 列的概率转移矩阵为<math>P'</math>，它同样满足概率归一化条件，它可以看作是对 <math>P</math> 矩阵所描述的动力学过程的一种抽象近似的约简。+ − + − 对任意马尔科夫链的转移概率矩阵做约简存在着无穷多可能的方法，然而在实际的粗粒化过程中，我们必须从这无穷多钟方法中做筛选，以使得约简后的矩阵[math]P'[/math]能够尽可能多地保留原矩阵的主要特征。于是，为了刻画这种原矩阵特征是否被保留的特性，人们提出了不同的标准，这些标准包括：+ 第21行：
第21行： − 马尔科夫链不只是一个马尔科夫矩阵那么简单。它还涉及到了不同的状态，也会有状态之间的转移概率，所以我们可以从不同的角度来看待粗粒化：+ 第27行：
第27行： − 这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。+ − 对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化（coarse-graining）、聚类/聚合（partitioning/lumping/clustering/aggregation）和降维（dimension reduction）是重叠等价的。+ − + 第40行：
第40行： − 如果我们对这个降维/粗粒化过程进行分解的话，我们可以看到这个过程可以被分为三步。+ 第52行：
第52行： − + − + 第74行：
第74行： − 我们假设了<math>W, \Phi, P, P'</math>都是线性的，所以我们可以这样理解这个公式：从图1中从左上角的 t 时刻宏观状态出发，经过了一个‘逆向粗粒化’操作<math>W</math>，得到了 t 时刻微观状态，走微观动力学 <math>P</math> 得到了 t+1 时刻的微观状态，再经粗粒化 <math>\Phi</math> 得到 t+1 时刻的宏观状态。+ − 式子{{EquationRef|1}}中我们发现，<math>\Phi</math> 和 <math>P</math> 都是给定的，所以我们在这一步要做的是决定 <math>W</math>。<math>W</math> 的基础限制是要使得 <math>P'</math> 符合马尔科夫矩阵定义，在此基础上有无限多种 <math>W</math> 的选项，而我们也能从中挑出符合我们想要的特征的 <math>W</math>。+ 第82行：
第82行： − 目前我们还没找到一个严格的完备的马尔科夫粗粒化应该符合的定义。在这一章中，我们将简单梳理概括一些基本的概念，和不同粗粒化方法中使用到的要求、优化目标和评价指标。+ − 当我们把“对一个马尔科夫链做粗粒化”看作一个完整的问题，它本质上并不是单纯的“把若干状态聚成几类”的聚类问题，而是一个同时涉及'''尺度选择、动力学闭合、信息压缩和目标优化'''的多层问题。我们在粗粒化过程中需要找到'''哪些微观差异只是会被快速混合掉的局部噪声、快变量或冗余通路，哪些差异则决定了系统未来的主要演化方向、稳态概率流以及跨尺度的因果结构。'''+ − 从物理直觉上说，一个好的宏观态应当把“对外行为几乎一样”的微观状态吸收到同一组里，把“长期命运不同”的状态分开。前者例如具有相似的转出概率模式、相似的稳态流角色、相似的未来条件分布；后者例如属于不同常返类、不同周期类，或通向不同吸引子结构。若把后一类状态强行合并，宏观过程往往会出现记忆效应，或者丢掉最关键的慢变量。+ − − 沿着这个思路，可以把粗粒化问题拆成以下几层： − − # '''问题对象与尺度选择（Problem Definition & Scale Choice）''' − ## '''输入'''：给定的微观马尔科夫链，包括微观状态空间 <math>S</math>、转移矩阵 <math>P</math>、稳态分布 <math>\pi</math>。在更具体的问题里，还常常需要额外指定'''关心的时间尺度'''、'''预测视野'''、'''允许的划分限制'''（例如是否只允许拓扑上相邻的状态合并）以及'''目标宏观维度 <math>r</math>'''。 − ## '''输出'''：不仅是一个宏观转移矩阵 <math>P'</math>，而是一个完整的粗粒化方案：包括宏观状态空间 <math>S'</math>、划分矩阵 <math>\Phi</math>（哪些微观状态被视为同一宏观态）、聚合方式 <math>W</math>（如何从微观动力学构建宏观动力学），以及必要时由算法自动选择的尺度 <math>r</math>。 − ## '''核心问题'''：我们在粗粒化过程中想保留哪一类“有效自由度”？是长期稳态流结构、块结构、可预测性、因果效应？不同答案会导向不同的粗粒化标准。 − # '''合法性与自洽性条件（Requirements & Constraints）'''：要求一个粗粒化方案（必须或至少近似）满足合法的、符合物理直觉的的条件 − ## '''宏观过程必须仍然是一个合法的（或近似合法的）马尔科夫过程''' − ##* 形式上，<math>P'</math> 需要满足概率归一化；物理上，更重要的是宏观态之间的转移尽量只依赖当前宏观态，而不依赖“这个宏观态内部的具体某个微观态”。如果不满足，粗粒化后就会出现记忆效应。 − ## '''宏观和微观动力学的演化保持一致''' − ##* 理想情形下，粗粒化算子与时间演化算子可交换，即 <math>\Phi P' = P \Phi</math>。这意味着“先演化再粗粒化”和“先粗粒化再演化”给出相同的宏观结果。 − ##* 它的物理意义是：被丢弃的微观细节只对应快弛豫、局部涨落或冗余差异，不会系统性改变宏观未来；真正决定未来演化的慢变量，已经被宏观态保留下来了。 − ##* 在严格极限下，这一要求会导向'''成块性'''等结构性条件；从预测角度看，它也与'''因果态'''所捕捉的未来相关信息密切相关。 − ## '''宏观尺度应当尽量闭合''' − ##* 因果闭合、信息闭合和计算闭合，分别回答：宏观干预是否足够、宏观历史是否足够、宏观计算机制是否足够。它们讨论的都是同一件事：'''宏观动力学能否在本尺度上自洽地独立运行，而无需不断回到底层微观细节去修正。''' − ## '''粗粒化不应任意破坏系统的长期结构''' − ##* 至少在稳态分布下，合理的粗粒化通常应尊重常返类、瞬时态、周期类以及随机吸引子（吸引域）等基础结构。这些结构刻画了系统的长期命运，是一种“先验不能轻易跨越的边界”。 − ##* 从稳态流矩阵 <math>F=\mathrm{diag}(\pi)P</math> 的角度看，粗粒化过程不应严重扭曲主要概率流通道 <ref name=":4" />。 − # '''优化目标（Objectives）'''：在所有合法的粗粒化方案中，我们希望"最好"的那个满足什么 − ## '''压缩维度'''：在可接受的误差范围内，尽可能用更少的宏观状态描述系统。这是最直接的降维目标，也是所有后续目标的前提。 − ## '''最大化预测性''' − ##* 若一组微观状态对未来给出几乎相同的条件分布，那么从预测角度看，它们就应当属于同一宏观态。 − ##* 成块性保证了'''宏观最大预测性'''，即宏观态足以预测后续宏观态；因果态则对应更强的'''微观最大预测性'''，即宏观表征尽可能保留对未来微观轨迹的预测能力。 − ##* 优化目标：预测误差、条件互信息 − ## '''最小化随机性与信息损失''' − ##* 好的粗粒化不只是“压得更小”，还要尽量少丢信息。它要在压缩和保真之间找到平衡：既滤掉无关细节，又不抹掉决定长期行为的结构。 − ## '''最大化因果效应''' − ##* 使系统在宏观层面的因果效应强度最大（状态转移更确定、更少简并），从而揭示因果涌现最显著的尺度。 − ##* 在粗粒化过程中，把截动力学信道中彼此冗余（线性相关）的通路截断掉，保留核心通路，提升动力学的信息传输效率 <ref name="reversibility"/>。 − ##* 优化目标：因果效应强度、有效信息（EI）、动力学可逆性 − ## '''增强组内同质性、组间可分性''' − ##* 在状态分组时，同组状态具有相似的转出概率模式<ref name="reversibility"/>、相似的稳态出流角色<ref name=":4" />、相似的未来条件分布，而不同组之间在这些量上尽量可分。 − ##* 找到“组内快速混合、组间较慢跃迁”或“组内通路冗余、组间通路主导”的结构。 − ##* 实现方法：对转移概率矩阵、稳态流矩阵进行SVD分解+K-Means分组。 − # '''方法 / 算法（Methods / Algorithms）''' − ## '''划分方法'''：决定 <math>\Phi</math>。包括逐层贪婪算法、谱分解方法、SVD + K-Means、遗传算法、GNN 参数化划分等。 − ## '''聚合方法'''：决定 <math>W</math> 和 <math>P'</math> 如何构建，包括等权平均（通常只适用于成块或近成块情形）、稳态分布加权平均、通过 <math>F'=\Phi^T F \Phi</math> 构建宏观流矩阵、高阶网络聚类（HOM）等。 − ## '''方法背后的物理假设并不相同'''：对 <math>F</math> 做 SVD 更强调稳态概率流和近成块结构；对 <math>P</math> 做 SVD 更强调转移通路的线性冗余与动力学可逆性；基于因果态或闭合性的方案则更强调跨尺度预测与机制自洽。 − − 从这个角度看，后文中出现的各种概念其实分别处在不同层次上： − # '''成块性、因果态、稳态吸引子结构'''更像是在回答“什么样的状态天然适合被合并”； − # '''可交换性、尺度闭合性'''是在回答“合并以后宏观动力学是否仍然自洽”； − # '''有效信息、动力学可逆性'''是在回答“在众多可行方案中，哪个尺度最有信息价值”； − # 而各类聚类、谱分解与优化算法，则是在回答“这些目标具体怎么求”。 − − 这样一来，全文讨论的就不再是若干彼此并列的定义，而是同一个粗粒化问题在不同层次上的不同答案。 第141行：
第94行： − 首先，一个重要的粗粒化标准就是 '''粗粒化操作要和时间演化操作是可交换（commutative）的两个算符'''。以图（1）所示的情形为展示，我们从某个微观状态 <math>s^{(t)}</math> 出发，到达下一刻的宏观状态 <math>A^{(t+1)}</math> 具备两条不同的路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：+ − + − + 第155行：
第108行： − 这两条路径的一致性在粗粒化领域是非常重要，并被反复提及的概念。满足一致性的粗粒化方案能够充分的保留动力学中有效的信息，并丢弃掉无用的信息。具体来说，宏观状态已经捕捉了与未来演化相关的所有“慢变量”或“相关信息”，而被粗粒化掉的那些微观细节，只影响瞬时的噪声或快速弛豫过程，而不会长期地、系统性地改变宏观演化。+ 第163行：
第116行： − + − 成块性的初始定义比较复杂，详见[[马尔科夫链的成块性]]。在这里，我们介绍其定义的充分必要条件，一个更直观的解析。在某些文献中，作者们会直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的<ref name=":1" />。+ 第173行：
第126行： − + 第186行：
第139行： − + 第200行：
第153行： − + − + − + − 在讨论成块性时，必须明确状态划分的方式。不同的划分方式可能导致不同的结论。一个马尔科夫链可能在某种划分下是成块的，而在另一种划分下则不成块。这里用一个简单的例子提供正例和反例。+ − − 我们用到的是这样一个转移矩阵： − − − − P = P_{s_i \rightarrow s_j} = \left [ − − 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} − − \end{aligned} − − − 我们可以看到，123行都是一样的，所以把他们 <math>\{s_1, s_2, s_3\}</math> 分在一组 <math>A_1</math>，并把状态 <math>s_4</math> 分在另外一组 <math>A_2</math>。这个分组 <math>\{\{s_1,s_2，s_3\}, \{s_4\}\}</math> 中每一个属于 <math>A_i</math> 的状态 <math>s_k</math> 的 <math>p_{s_k \rightarrow A_j}</math> 都是一样的，而这个分组对应的宏观转移矩阵为 − <math> − \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>\{\{s_1,s_2\}, \{s_3,s_4\}\}</math>，并不满足成块性的条件定义。 第273行：
第197行： − 在计算力学中，状态被理解为智能体所接收到的全部历史信息，所以将系统从过去到未来的变化用一个离散的稳定[[随机过程]]描述。状态空间为双（向）无限序列的集合 <math>\overleftrightarrow{S}=\{\cdots, s_{-2}, s_{-1}, s_0, s_1, s_2, \cdots\}</math>，即无限长的时间序列。基于当前的时刻 <math>t</math>，我们可以将 <math>\overleftrightarrow{S}</math> 分为单侧前向序列 <math>\overleftarrow{s_t}=\{\cdots, s_{t-3}, s_{t-2}, s_{t-1}\}</math> 和单侧后向序列 <math>\overrightarrow{s_t}=\{s_t, s_{t+1}, s_{t+2}, s_{t+3},\cdots\}</math> 两个部分。所有可能的未来序列 <math>\overrightarrow{s_t}</math> 形成的集合记作 <math>\overrightarrow{S}</math>，所有可能的历史序列 <math>\overleftarrow{s_t}</math> 形成的集合记作 <math>\overleftarrow{S}</math>。+ − 因果态是一种对系统状态的粗粒化描述，并没有假设系统的马尔科夫性，为了把因果态和马尔科夫链的粗粒化理论进行比较，可以定义马尔科夫链的因果态：假设系统是一个<math>K</math>阶的马尔科夫链（系统在<math>t</math>时刻的状态分布是由前K个时刻的状态决定的），则可将 <math> \overleftarrow{S}</math> 重新定义为 <math> S^K</math>。+ 第293行：
第217行： − + 第304行：
第228行： − 为什么我们要关注因果态这样一种特定的宏观态呢？下面是因果态的两个主要性质，能够体现出因果态是一种最理想的宏观态：+ 第330行：
第254行： − 当我们做跨尺度粗粒化时，一个核心问题是：粗粒化得到的「宏观动力学」能不能自己演化、自己预测，而不用再依赖「微观动力学」的状态信息来修正？直观地说，就是看微观层和宏观层之间，计算和演化是不是可以“各自独立”。+ − − 在哲学中，这种现象常被叫做因果闭合（因果闭包）。Barnett 和 Anil Seth 在他们关于「动力学解耦」的工作<ref name=":23"> Barnett, L., & Seth, A. K. (2023). Dynamical independence: discovering emergent macroscopic processes in complex dynamical systems. Physical Review E, 108(1), 014304</ref>中认为：在一个复杂系统中，在一个复杂系统里（比如动物身体），如果宏观动力学（肢体运动）可以自主演化、并且在预测时不需要回到微观动力学（细胞活动）去补充信息，那么我们就可以说这里出现了涌现。 − − 而Rosas等人的工作<ref name="closure">Rosas, F. E., Geiger, B. C., Luppi, A. I., Seth, A. K., Polani, D., Gastpar, M., & Mediano, P. A. (2024). Software in the natural world: A computational approach to hierarchical emergence. arXiv preprint arXiv:2402.09090.</ref>进一步形式化了这个想法。他们提出，在评估“不同尺度是否能独立演化”时，可以考察三种[[不同尺度之间的闭合性]]：因果闭合、信息闭合和计算闭合。 − − 这里的“闭合”指的是：在给定粗粒化方案下，宏观尺度对微观尺度是闭合的。一旦达到闭合，我们就可以说宏观尺度在某种意义上实现了“独立演化”。 − − − − ===单尺度因果态和ϵ-机器=== − − [[文件:因果态示例.png|缩略图|500x500像素|因果态示例，出自Rosas于因果涌现读书会第五季第一期的分享]] − − 在前文关于「计算力学」的部分，我们已经简单介绍过因果态。这里为了和原文符号对应，再用更正式的方式回顾一下。 − − 在时序系统中，ϵ-machine（ϵ-机器）使用历史记忆 <math>\overleftarrow{X_t}=\{... , X_{t-2}, X_{t-1}, X_t\}</math> 来预测未来状态的轨迹 <math>p(\overrightarrow{X}^L_t| \overleftarrow{X_t})</math>，其中<math>\overrightarrow{X}^L_t=\{X_{t+1}, X_{t+2}, ... , X_{t+L}\}</math>，简写成<math>\overrightarrow{X_t}</math>。 − − 因果态就是，把所有能给出相同未来预测分布的历史，被划到同一类：<math>E = \{E_t\}_{t \in \mathbb{N} }, E_t = \epsilon( \overleftarrow{X_t} )</math>，<math>\overleftarrow{x_t} \equiv \overleftarrow{x_{t'}}\ \ \text{iff}\ \ p(\overrightarrow{x_t}| \overleftarrow{x_t} ) = p(\overrightarrow{x_{t'}}|\overleftarrow{x_{t'}})</math> − − 所以，ϵ-机器做两件事： − # 把当前历史 <math>\overleftarrow{X_t}</math> 映射到一个因果态 <math>E_t</math>； − # 再用这个因果态来预测未来 <math>\overrightarrow{X_t}</math> 。 − − 我们可以把ϵ-机器理解为最小解释模型：用尽可能少的宏观状态，既能稳定地描述系统，又能很好地预测未来。这个宏观状态就是因果态。 − − − [[文件:三种因果态.png|缩略图|400x400像素|三种因果态的示意图，摘录自文章原文]]+ − 现在我们引入一个粗粒化函数 <math>f</math>，将微观过程 <math>X_t</math> 映射到宏观过程 <math>Z_t = f(X_t)</math>。普通的ϵ-机器只能在同一尺度上工作（<math>X</math> 空间），而Rosas 等人提出的υ-machine（υ-机器），专门处理微观→宏观的跨尺度预测。+ − − 他们把因果态中的未来状态从微观的 <math>X</math> 改为宏观的 <math>Z</math>，并定义微观状态 <math>X</math> 中的等价关系为 − + − 也就是说，υ-机器把拥有同样 <math>p(\overrightarrow{z_t}| \overleftarrow{x_t})</math> 的 <math>\overleftarrow{x_t}</math> 和 <math>\overleftarrow{x_{t'}}</math> 定义为υ-机器的因果态，<math>U = \{U_t\}_{t \in \mathbb{N} },\ U_t = υ( \overleftarrow{X_t} ) </math>+ − 直观上，υ-机器在所有微观历史中，找到一个最粗的划分，同时又能对宏观未来 <math>\overleftarrow{Z_t}</math> 保持最大预测性，因此是一个“最优的信息瓶颈”。+ + + + − 所以，在给定粗粒化 <math>Z_t = f(X_t)</math> 后，可以有三种因果态：+ − # 微观ϵ-机器，因果态为 <math>E</math>；+ − # 宏观ϵ-机器，因果态为 <math>E'</math>；+ − # 跨尺度υ-机器，因果态为 <math>U</math>；+ − 这三种机器的区别大概是：+ − # <math>U_t</math> 比 <math>E'_t</math> 更强（powerful），因为后者只包括了宏观的信息，而前者同时包括了宏观和微观的信息； − # <math>E_t</math> 比 <math>U_t</math> 更强，因为 <math>U_t</math> 只保留了宏观的最大预测性，而 <math>E_t</math> 能保留微观的最大预测性（同时因为我们知道 <math>f</math> ，所以 <math>E_t</math> 也能保留宏观的最大预测性）。 − 由此可以得到两个关键结论（证明见[[不同尺度之间的闭合性]]）：+ − − '''推断1'''：<math>I(\overleftarrow{X_t}; \overrightarrow{Z_t}) = I(U_t; \overrightarrow{Z_t})</math>：υ-机器的因果态 <math>U_t</math> 完全概括了微观历史 <math>\overleftarrow{X_t}</math> 对宏观未来 <math>\overrightarrow{Z_t}</math> 的全部信息量。 − − '''推断2'''：υ-机器的因果态 <math>U_t</math> 对宏观 <math>\overrightarrow{Z_t}</math> 提供的信息量 大于等于 宏观本身的 ϵ-机器的因果态 <math>E'_t</math>。 − − − − 了解了跨尺度因果态的定义后，我们就能逐个了解这篇文章中的三种闭合定义。 − − <br/> − − ===因果闭合 Causal Closure=== − − 定义：当宏观过程 <math>Z_t</math> 的 ϵ-机器 与 跨尺度的 υ-机器 的因果态分组相互一一对应，即 <math>E'</math> 和 <math>U</math> 之间存在双射（bijective）投影关系时，称粗粒化 <math>Z_t = f(X_t)</math> 满足因果闭合。 − − 在这种情况下，所有微观历史 <math>\overleftarrow{X_t}</math> 在预测宏观未来 <math>Z</math> 上的差异，都会完整地体现在宏观历史 <math>\overleftarrow{Z_t}</math> （ϵ-机器）中，不会在粗粒化过程中被抹掉。所以，因果闭合的物理意义为：'''宏观上的干预，和它在微观层面的对应干预，在宏观结果上完全等价。''' − − 当我们对 <math>Z</math> 进行干预的时候，微观 <math>X</math> 的状态也会跟着改变，就像当我们加热了一锅水的时候，其中的水分子的能量也会改变。对 <math>Z</math> 空间进行的干预影响到 <math>X</math> 空间时，按照 <math>X</math> 的动力学进行演化后再粗粒化得到的 <math>Z</math>，与直接在 <math>Z</math> 空间上进行演化没有区别。 − − 因此，一旦因果闭合成立，只用宏观动力学就能正确追踪干预后的演化，不必回到微观 <math>X</math> 层溯源。所以这就是宏观和微观之间因果闭合了，即宏观动力学在因果性上能做到独立的演化。 − − <br/> − − ===信息闭合 Information Closure=== − − 上面的因果闭合强调“干预–因果”，而信息闭合则从“预测–信息”出发。 − − 用互信息来刻画<math>Z_t</math> 本身的ϵ-机器和 <math>Z_t = f(X_t)</math> 之间的υ-机器对宏观未来 <math>\overrightarrow{Z_t}</math>的预测能力，可以写成： − + − 这就是信息闭合的条件：宏观历史 <math>\overleftarrow{Z_t}</math> 和微观历史 <math>\overleftarrow{X_t}</math> 对宏观未来 <math>\overrightarrow{Z_t}</math> 提供的信息量完全相同。+ + + − 因此，只知道 <math>\overleftarrow{Z_t}</math> 就足以做最优预测，再加上底层的 <math>\overleftarrow{X_t}</math> 也不能提升预测能力。也就是说，微观信息在预测宏观 <math>\overrightarrow{Z_t}</math> 时是冗余的。所以，一个尺度在信息意义上“闭合”，便是在说这个尺度上系统可以“自给自足”，不需要再考虑其他尺度。 + + + − 根据跨尺度因果态介绍中的推断2，可以证明：对给定的 <math>Z_t = f(X_t)</math>，'''因果闭合和信息闭合这两个条件是等价的'''：由于<math>I(U_t ; \overrightarrow{Z_t}) = I(E'_t ; \overrightarrow{Z_t})</math>，所以<math>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> − 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> − − <br/> − − ===计算闭合 Computational Closure=== − − [[文件:计算闭合可交换性.png|缩略图|计算闭合可交换性示意图，摘录自文章原文]] − − 定义：<math>Z</math> 的 ϵ-机器为计算闭合，当满足：'''存在粗粒化函数 <math>f^*</math>使得 <math>E'_t = f^*(E_t)</math>，其中<math>E_t</math> 和 <math>E'_t</math> 分别为 <math>X</math> 和 <math>Z</math> 的ϵ-机器的因果态。'''也就是说， 宏观因果态是微观因果态的“合并版本”（一对一或多对一）。 − − 从 <math>X</math> 到 <math>E'</math> 有两条路径： − − # <math>X \stackrel{\epsilon}{\rightarrow} E \stackrel{f^*}{\rightarrow} E'</math> − # <math>X \stackrel{f}{\rightarrow} Z \stackrel{\epsilon'}{\rightarrow} E'</math> − − 把 <math>f</math> 和 <math>f^*</math> 视作粗粒化算子，<math>\epsilon</math> 和 <math>\epsilon'</math> 视作因果态算子，那么我们看到，先粗粒化再找因果态 = 先找因果态再粗粒化，在机制层面是“可交换”的。 − − − − 上面提到过 ϵ-机器可以看作最小解释模型，描述了动力学的机制。所以，因果态空间 <math>E</math> 和 <math>E'</math> 可以看作是动力学的‘机制空间’。而计算闭合的意义是指出，这种动力学不仅在本来的变量/状态空间中能够被粗粒化 <math>f:X \to Z</math> ，而且它的机制也能被对应的粗粒化 <math>f^*: E \to E'</math>。因此，宏观的计算机制可以看作是微观机制的简化版。 − − 换句话说，如果一个系统在某个粗粒化 <math>f</math> 下是计算闭合的，那么我们可以从微观机器出发，在机制层面自然得到了宏观机器，从而实现一个干净的多尺度计算模型。 − − 对于一台机器，我们肯定希望它的宏观的计算过程要更加的简洁，也就是说宏观的ϵ-机器最好是微观的ϵ-机器的一种粗粒化。难道宏观机器还可以不是微观机器的粗粒化吗？粗粒化意味着宏观变量是微观变量的单射，这个映射过程可能引入更多的噪音，导致宏观过程的因果态反而比微观的还要多。我们在[[不同尺度之间的闭合性]]中介绍了一个具体例子，请感兴趣的读者自行查阅。 − − − − 计算闭合与前面的因果闭合/信息闭合之间的关系是：对同一个粗粒化函数 <math>Z_t = f(X_t)</math> ：若它是因果闭合 / 信息闭合的，那么它一定也是计算闭合的；反之不一定，也就是说，计算闭合是一个相对更“宽松”的条件。证明请参照[[不同尺度之间的闭合性]]。 − − <br/> − Geiger 和 Temmel 的工作<ref name=":Geiger">B. C. Geiger and C. Temmel, “Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability,” J. Appl. Probab., vol. 51, no. 4, pp. 1114–1132, Dec. 2014, extended version: arXiv:1212.4375.</ref>把马尔可夫链的成块性与信息条件联系了起来。+ − − 对一个不可约（irreducible），和非周期性（aperiodic）的马尔科夫链 <math>X</math> ，若<math>Z_t=f(X_t)</math> 是状态空间上定义的粗粒化函数，有： − − # <math>X</math> 的强成块性 '''在其达到稳态（stationary）分布时''' 等价于 <math>H(Z_{t+1}|Z_t) = H(Z_{t+1}|X_t) </math>。 − − # <math>X</math> 的弱成块性 '''在其达到稳态分布时''' 等价于 <math>H(Z_{t+1}|Z_t) = H(Z_{t+1}|Z_{<t}) </math>。 − − − − Rosas等人<ref name="closure" />认为，当使用 <math>Z_t</math> 来预测 <math>Z_{t+1}</math> 时，可以拆分为两步：先利用宏观 <math>Z_t</math> 推断微观 <math>X_t</math>，再利用微观 <math>X_t</math> 估算宏观 <math>Z_{t+1}</math>。所以， − − '''推断1'''：当一个马尔科夫链 <math>X_t</math> 存在粗粒化函数 <math>Z_t=f(X_t)</math>，而 <math>X_t</math> 对 <math>f</math> 强成块时，则 <math>Z_t</math> 满足因果闭合/计算闭合。（反之未必成立，详情请参考论文<ref name="closure" />反例6）。证明请参考词条[[不同尺度之间的闭合性]]。 − − '''推断2'''：假设存在 <math>Z=f(E)=f(\epsilon(X))</math>，<math>E</math> 为 <math>X_t</math> 的ϵ-机器的因果态，那么 <math>E</math> 对 <math>Z</math> 是弱成块的条件 等价于 <math>Z_t</math> 计算闭合的条件。证明请参考词条[[不同尺度之间的闭合性]]。 − + − − 原文<ref name="closure" />用一张关系图总结了这些概念： − + − # 对给定 <math>f</math>，因果闭合性 等价于 信息闭合性。 − # 当 <math>f</math> 因果/信息闭合时，它一定计算闭合。 − # 当一个'''稳态的'''马尔科夫链 <math>X_t</math> 对 <math>Z_t = f(X_t)</math> 强成块时，则 <math>f</math> 一定因果/信息闭合。 − # 当'''稳态的''' <math>X_t</math>的因果态 <math>E_t</math> 对 <math>Z_t = f(E_t)</math> 弱成块时，<math>Z_t</math> 计算闭合。 第504行：
第323行： − + 第513行：
第332行： − \begin{aligned}+ − − &= \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} − + 第530行：
第344行： − 确定性是指，在动力学的作用下，我们根据系统前一时刻的状态会以多大程度预测它下一时刻状态；简并性是指：果知道了系统的当前状态，能不能反推系统在上一时刻的状态的能力，如果可以推断，则这个马尔科夫矩阵的简并性就会比较低，也就是非简并的；而如果很难推断，则马尔科夫矩阵就是简并的，也即退化的。如果确定性越大，或简并性越小，则系统的有效信息就会越大。其他相关详情请参照[[有效信息]]词条。+ 第573行：
第387行： − 开头提到，对马尔科夫链做粗粒化的其中一个动机就是，想抹除一些微观动力学上的噪音，而得到在宏观上更具规律和因果性的动力学。所以，我们可以利用EI这一马尔科夫链的因果效应度量，来衡量聚类后的宏观动力学的因果强度。+ − 但是，EI的大小和状态空间大小有关，这一性质在我们比较不同尺度的[[马尔科夫链]]的时候非常不方便，我们需要一个尽可能不受尺度效应影响的[[因果效应度量]]。因此，我们需要对有效信息EI做一个归一化处理，得到和系统尺寸无关的一个量化指标。根据[[Erik Hoel]]和[[Tononi]]等人的工作，要用[[均匀分布]]即[[最大熵分布]]下的熵值，即<math>\log N</math>来做分母对EI进行归一化，这里的[math]N[/math]为状态空间[math]\mathcal{X}[/math]中的状态的数量<ref name="hoel_2013">{{cite journal|last1=Hoel|first1=Erik P.|last2=Albantakis|first2=L.|last3=Tononi|first3=G.|title=Quantifying causal emergence shows that macro can beat micro|journal=Proceedings of the National Academy of Sciences|volume=110|issue=49|page=19790–19795|year=2013|url=https://doi.org/10.1073/pnas.1314922110}}</ref>。那么归一化后的EI便等于：+ 第585行：
第399行： − 有了有效信息这一度量指标后，我们便可以讨论马尔科夫链上的因果涌现了。对于一个马尔科夫链，观察者可以建立多尺度视角去观测，区分出微观和宏观。首先，原始的马尔科夫概率转移矩阵 <math>P_N</math> 即定义了微观动力学；其次，经过对微观态的粗粒化映射（coarse-graining）后（通常反映为对微观状态的分组），观察者可以得到对应的宏观状态（即分组），这些宏观状态彼此之间的概率转移可以用宏观的马尔科夫概率转移矩阵 <math>P_M</math> 来刻画。对两个动力学分别可以计算EI，如果宏观的EI大于微观EI，我们说该系统发生了因果涌现。+ 第622行：
第436行： − 在这个例子中，微观态的转移矩阵是一个4*4的矩阵，其中前三个状态彼此以1/3的概率相互转移，这导致该转移矩阵具有较小的确定性，因此EI也不是很大为0.81。然而，当我们对该矩阵进行粗粒化，也就是把前三个状态合并为一个状态a，而最后一个状态转变为一个宏观态b。这样所有的原本三个微观态彼此之间的转移就变成了宏观态a到a内部的转移了。因此，转移概率矩阵也就变成了[math]P_M[/math]，它的EI为1。在这个例子中，可以计算它的[[因果涌现度量]]为：+ 第636行：
第450行： − + − 该理论的核心思想是指出所谓的'''因果涌现其实等价于动力学可逆性的涌现'''。'''该指标与[[有效信息]]具有高度的相关性，因而也可以用于刻画动力学的[[因果效应强度]]。''' − 直观地说，如果将一个马尔科夫动力学看作是一个通信信道，那么，每一状态下的概率转移就看作是一个信息通路（information pathway），于是该系统发生因果涌现就等价于系统中存在着冗余的信息通路——存在着一些状态转移与其它状态转移相似或线性相关，而消除这些冗余通路的最好办法就是利用SVD找到等于零或接近于零的奇异值以及对应的奇异向量，这实际上正是最大化有效信息的精髓所在。事实上，我们可以证明，最大化宏观动力学有效信息的粗粒化方案近似等价于将系统的动力学向较大奇异值对应的奇异向量方向做投影的粗粒化方案。而且，系统所能达到的最大信息传输效率的提升（归一化的近似动力学可逆性），就可以定义为因果涌现的强度。+ − + − 基于可逆性的因果涌现理论与已有的其他因果涌现理论最大的区别就是不需要指定粗粒化策略，仅从马尔科夫转移矩阵的奇异值谱就能判断因果涌现的发生，直接定义所谓'''清晰因果涌现'''（clear causal emergence）和'''模糊因果涌现'''（vague causal emergence）的概念，在一定程度上规避了因果涌现结果依赖于粗粒化策略的问题和最大化有效信息的难以优化求解的问题。其次，这套理论指出一个动力系统的因果涌现特性仅仅是系统线性化算符的奇异值谱决定的，因而是一套更加反映系统动力学特性本身的因果涌现理论。相关详情请参照[[基于可逆性的因果涌现理论]]词条。+ − 我们可以由矩阵 <math>P</math> 的秩 <math>r</math> 和矩阵的弗罗贝尼乌斯范数（Frobenius norm，F-norm）找到 <math>P</math> 的近似动力学可逆性与矩阵奇异值之间的联系。 + − − 首先，'''矩阵的秩'''可以被写作：<math>r=\sum_{i=1}^{N}\sigma_{i}^{0}</math>，其中 <math>\sigma_{i}</math> 是矩阵 <math>P</math> 的第 <math>i</math> 个奇异值，<math>N</math> 是马尔科夫链的状态数。 − − 紧接着，'''矩阵的F-norm'''可以被写作：<math>{||P||}_{F}^{2}=\sum_{i=1}^{N}\sigma_{i}^{2}</math>。这也是所有奇异值的平方和。可以看出矩阵的秩和F-norm都与奇异值相联系。事实上，当且仅当 <math>P</math> 的行向量是独热向量的时候，矩阵P的弗罗贝尼乌斯范数取最大值。 − − 由于绝大部分马尔科夫链的状态转移矩阵都不是置换矩阵，所以我们需要一个指标来刻画其靠近（可逆的）置换矩阵的程度。这就是矩阵 <math>P</math> 的 <math>\alpha</math> 阶近似动力学可逆性。定义为： 第659行：
第466行： − + − + − 最大化动力学可逆性的合理性来源于这套SVD方案定义的因果涌现与最大化有效信息的因果涌现定义的密切关系。在[[基于有效信息的因果涌现理论|Erik Hoel因果涌现理论]]的框架内，给定马尔可夫动力学系统的因果涌现的大小依赖于粗粒化策略的选择，可以通过宏观动力学的EI最大化寻找最优的粗粒化策略。+ − 我们可以证明，要想获得最大化有效信息的粗粒化策略也近似等价于是向最大奇异值对应的奇异向量方向投影的策略。严格推导可见[[基于有效信息的因果涌现理论]]。由于对于离散的马尔可夫链来说，粗粒化策略往往都是比较严格的0或1构成的向量，因此并不能简单地根据奇异向量来直接投影。但是，如果粗粒化策略尽可能地与最大的几个奇异向量平行，那么就可以让粗粒化后动力学的EI尽可能更大，因此最大化EI的必要条件近似可以认为就是往最大奇异值对应的奇异向量空间做投影。在实际应用中，粗粒化策略 <math>\phi</math> 的约束（例如，宏观动力学TPM的分组和归一化）会阻止 <math>\phi_j</math> 与奇异向量完美对齐。因此，基于SVD的粗粒化策略只是最大化EI的近似必要条件。+ 第673行：
第480行： − 好的粗粒化方案是能够尽可能保证原始的网络（或转移矩阵）和粗粒化后的网络（或转移矩阵）尽可能地相似。Erik Hoel 和 Klein <ref name=":19" /> 提出使用动力学一致性来衡量在原始网络和粗粒化后网络上演化的状态的轨迹的一致性。详情请见[[复杂网络中的因果涌现]]词条。+ 第679行：
第486行： − + − 也就是说，不一致性 表示了 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。+ − 动力学一致性在某种程度上反映了 动力学和粗粒化算子可交换性，但比可交换性更灵活宽松，可以计算不可交换但近似交换的程度。+ 第693行：
第500行： − 需提醒的是，虽然马尔科夫链是一个随机过程，但一个马尔科夫链的 '''实例''' 在演化（根据 TPM 的随机选择）过程的每一步中，仍然是一个确定的状态，而不会变成一个分布；就像一个粒子在网络里流动，在 <math>t</math> 步以后它仍然是一个处于某个节点的粒子，而不是分裂成了 n 个散落在各个节点上的部分。+ − − 所以，马尔科夫链在 <math>t</math> 时刻的 '''状态分布''' 是指，当我们给定一个初始状态分布 <math>\mu</math> 时，'''推断/估计''' 这个系统在 <math>t</math> 时刻处在各个状态的概率是多少。 − − 另一种视角是，我们可以复制无限多份并行的系统，让这些系统的初始状态服从分布 <math>\mu</math>，并各自演化（根据TPM的随机选择）<math>t</math> 步后，我们再去统计这一大群系统中处于每个状态的比例，就是 <math>t</math> 时刻的 '''状态分布''' 了。 − − − − 现在，再看一下 '''稳态分布''' 的定义：马尔科夫链的状态分布为 <math>\pi</math>，使得 <math>\pi P = \pi</math>。也就是说，在 <math>t=0</math> 时刻，并行的若干个系统的状态服从分布 <math>\pi</math>；在各自演化 <math>t=1</math> 步后，虽然这些系统的状态发生了变化，但统计到的状态仍然服从分布 <math>\pi</math>。 − − 这样，我们就能利用 '''随机动力学（Random Dynamical System）'''中的 '''不变性（Invariance）''' 要求来对马尔科夫链的稳态分布进行分析。详细的数学公式和定义请参考[[马尔科夫链中的随机动力学]]。 − − 简单来说，一个随机动力系统描述的是一个被随机噪声驱动的演化过程。它由两部分组成： − − # '''基础驱动系统（Base Driving System）'''：可以想象成一个源源不断产生随机影响的环境。它是一个无穷的噪声序列 <math>\Omega = \{ ... , \omega_{-1}, \omega_0, \omega_1, ... | \omega_i \in W \}</math> 。时间的流逝，就是这个序列不断向左移动（<math>\theta </math> 操作），让未来的噪声变成当前的噪声。 − − # '''演化余循环 （Evolution Cocycle）'''：这是一个'''演化规则'''<math>\phi</math>，它告诉我们系统在当前状态 <math>x</math> 和当前噪声 <math>\omega_0</math> 的共同作用下，下一步会变成什么样。为了能准确的描述系统演化，这个规则必须保证演化的连续性，比如演化 <math>s+t</math> 步等于先演化 <math>s</math> 步再演化 <math>t</math> 步。 − − 我们可以用随机动力学的框架来描述马尔科夫链：它的单步转移可以看作是演化规则 <math>\phi</math>，而每一步选择走哪条路径的随机性，就对应着噪声 <math>\omega</math>。 − − 在将马尔科夫链严格定义为了一个随机动力系统 <math>(\theta, \phi)</math>之后，我们可以定义该系统的 '''不变性（Invariance）'''，'''吸引性（Attraction）''' 和 '''随机吸引子（Attractor）'''。在确定的动力系统中，吸引子是系统演化最终会趋向并“陷落”进去的一个状态或区域。但在随机世界里，由于噪声的持续干扰，吸引子本身也变得不确定，它依赖于噪声的路径。这就是随机吸引子 (Random Attractor)： − 一个'''随机集合（即状态的集合）''' <math>A(\omega)</math> 要成为吸引子，必须满足三个苛刻的条件：+ − # '''紧致性 (Compactness)'''：简单来说，吸引子自身不能是无限分散的。对于有限状态的马尔科夫链，这个条件天然满足。+ − # '''不变性 (Invariance)'''：这是最核心的性质，意味着吸引子结构在演化中能够一直保持在其内部。随着系统演化，一旦进入吸引子，就再也无法逃逸出去。而且，吸引子结构不会凭空产生。新吸引子 <math>A(\theta \omega)</math> 中的任何一个点，都必然是从旧吸引子 <math>A(\omega)</math> 中的某个点演化而来的。 − # '''吸引性 (Pullback Attraction)'''：无论系统从哪里出发，只要时间足够长，最终都会被“拉回”到吸引子。就像你在旋涡周边的任意位置放下一艘船，让它顺着随机且难以预估的“水流”（噪声路径）漂流。当时间趋于无穷大时，你会发现，无论你最初在哪里放船，最终船都会被吸进旋涡里（即到达的位置都会无限接近于当前时刻的吸引子 <math>A(\omega)</math>）。 + + + − + − 当我们定义了随机吸引子的概念之后，我们就可以非常清晰的解释，为什么在马尔科夫链中，大家经常会讨论可约、周期、滑过这些概念。因为他们展现出了'''在稳态情况下（经过一段时间的演化之后）的系统分组规律'''。 − − 首先先简单重温一下马尔科夫链中的一些基础定义<ref name=":8">概率论与统计学5——马尔科夫链（Markov Chain） - 做大饼馅儿的韭菜的文章 - 知乎 <nowiki>https://zhuanlan.zhihu.com/p/274775796</nowiki></ref>。+ − − ====滑过Transient和常返Recurrent==== − − 滑过Transient状态：从该状态出发后，经过任意n步也不存在回到该状态的可能路径。 − − 常返Recurrent状态：从该状态出发后，经过n步后能够回到该状态。 − 我们可以定义一个常返状态组为：组中任意两个状态都互相可达。+ − 所以，我们就能把一条马尔科夫链分解成多个常返状态组和若干个滑过态。+ + + + − + − ====周期性==== − − 如果一个常返状态组存在步数 <math>n>1</math>，且每个常返状态 <math>i</math> 只会经过 <math>n</math> 步才会回到 <math>i</math>，那么就可以把这个常返状态组分解成 <math>n</math> 个子集。这里我们借用了知乎上的例子<ref name=":8"/>进行说明： − − 假设一个马尔科夫链的状态按照这样的周期（步数 <math>n=3</math>）循环， − − <math> − \{s_1, s_2\} \rightarrow \{s_3, s_4, s_5\} \rightarrow \{s_6\} \rightarrow \{s_1, s_2\} − </math> − − 我们就可以把状态划分成 <math>\{s_1, s_2\}</math>，<math>\{s_3, s_4, s_5\}</math>，<math>\{s_6\}</math> 三个子集。 − − <br/> − − ===稳态马尔科夫链中的随机吸引子和分组=== − − 我们考虑马尔科夫链的以下三种情况： − − − − 最普通的情况，不可约，没有周期循环的状态。这种马尔科夫链 存在唯一的全局随机吸引子，但它是一个'''平凡吸引子'''，即吸引随机集等于状态空间本身：<math>A(\omega) = X, \forall \omega</math> − − − '''情况2：可约的马尔科夫链''' − − 设 <math>S = T ∪ R_1 ∪ ... ∪ R_m </math>，其中 <math>T</math> 是滑过态（Transiant）集，<math>R_i</math> 是闭合常返（Recurrent）类。 − − 这种系统会有 <math>m</math> 个'''确定性吸引子''' <math>A_i = R_i</math>。系统一旦从过渡区进入某个孤岛 <math>R_i</math>，就再也出不来了。每一个孤岛 <math>R_i</math> 就是一个吸引子，它们不依赖于噪声，是固定的“陷阱”。 − − − '''情况3：不可约、周期为 <math>d > 1</math> 的马尔科夫链''' − − 这种链的所有状态虽然连通，但系统的演化表现出周期性。状态空间分解为 <math>d</math> 周期子类 <math>X = C_0 ∪ C_1 ∪ ... ∪ C_{d-1}</math>，系统在这些子类之间循环跳跃，<math>C_0 → C_1 → ... → C_{d-1} → C_0</math>。 − − 这里出现了真正意义上的 <math>非平凡随机吸引子</math>。在任何一个时刻，吸引子<math>A(\omega)</math> 就是当前的周期子类 <math>C_j</math>。它随着时间（噪声 <math>\omega</math> 的演化）在 <math>C_0, C_1, ... </math> 之间循环变化。 − − − − 随机动力学的视角告诉我们，无论系统如何随机演化，它总会被拉向一个或多个“吸引子”结构。当系统演化到稳态分布之后，这些吸引子内的状态就会展现出相同的演化特性，因此我们能够根据吸引子来对状态进行分组。详细的数学公式和验证请参考[[马尔科夫链中的随机动力学]]。 第806行：
第550行： − + − − ===高阶网络聚类 Higher-order Macronodes v.s. 成块性=== − − 我们通过一个简单的成块划分例子来展示，成块性的粗粒化与HOM是如何对应的。该例子的状态转移图如下图所示： − − [[文件:Lumpability例子示意图.png|图6：例子示意图|300像素]] − − 与之相应的状态转移概率矩阵为： − <math> − \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>\{1, 2, \{34\}, 5, 6\}</math>是一个成块的划分。其对应的宏观转移概率： − <math> − \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>A</math>中各节点的出流<math>W_i^{out}</math>（即图中的红色连边）的加权求和。而成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的。所以，对相同的<math>W_i^{out}</math>进行任意加权平均的结果仍然是<math>W_i^{out}</math>。这意味着，无论根据哪种情况采用哪种加权方法，对于成块划分来说，最终的结果都是一致的，且与成块性的粗粒化结果相同。 − − 由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。''' − − 第866行：
第558行： − 在普通的成块性例子里，它们粗粒化之后能得到一个EI或者可逆性很高的宏观动力学。但是，当我们考虑一些极端的例子，如下图所示，我们强行让每一组里的状态转移概率都尽可能的不一样，但是加起来又是一样的，满足了成块性的划分。按照这种成块的划分来去做粗粒化，它并不一定得到高的EI或可逆性。相反，我们用另一个不成块的分组来做粗粒化，得到的宏观动力学的EI和可逆性反而会更高。这现象说明：+ 第878行：
第570行： − + − 待选的划分数量极大，比如<math>S(20,10)=1.107e32</math>，几乎不可能通过遍历所有待选划分来寻找最优划分，所以，我们需要使用一些方法来有效的寻找到近似最优解。+ 第886行：
第578行： − 在这个问题中，我们可以采取 自底向上合并（Bottom-Up）的层次聚类（Hierarchical Clustering）方法，即从最细粒度（每个状态单独成组，一共 <math>N</math> 组）开始，每一步合并两个最相似的组，直到达到目标分组数 <math>M</math> 。+ 第908行：
第600行： − + − 该方法是将原始网络对应的转移矩阵做特征值分解，并使用这些特征向量来对节点进行聚类，之后再归并网络。+ − + − + 第933行：
第625行： − + − + − + − + − + − + 第951行：
第643行： − + 第966行：
第658行： − 这对应于一种特殊但常见的物理场景：系统各状态群之间的长期概率流量远弱于群内流量，形成类似"准吸引域"的结构——粒子长时间在群内游走，偶尔才跨越群边界。当 <math>P</math> 不是精确成块，而是近似成块（near-lumpable）时，该方法仍然可以工作，但需要满足一个关键条件：'''组间动力学 <math>F_1</math> 的奇异值必须主导 <math>F</math> 的整体奇异值谱'''，即 <math>\sigma_r(F_1) \gg \|F_2\|</math>。+ − + 第980行：
第672行： − 张江等人动力学可逆性的文章<ref name="reversibility"/>提供了另一种基于 SVD 的粗粒化方法。该工作出发点与与上面寻找成块划分的方法不同：它不以恢复某种预设的结构性划分为目标，而是将马尔科夫动力学看作一个通信信道，每个状态下的概率转移看作一条信息通路（information pathway）。当系统的 <math>N</math> 条通路中存在线性相关的行向量时，这些通路是冗余的——它们要么传递极少的信息（对应接近零的奇异值），要么可以被其他通路的线性组合表示。+ − + 第992行：
第684行： − + 第1,000行：
第692行： − 虽然该工作与前面Zhang & Wang的方法都做了SVD + kmeans的步骤，但是两者之间存在差异：+ 第1,009行：
第701行： − 寻找最优划分本质上是个组合优化问题，所以我们也能使用其他合适的方法来解决该问题。+ 第1,019行：
第711行： − 所以，我们可以把上述的逐层贪婪算法和谱分解方法的解作为初始解，通过遗传算法，帮助跳出局部最优解，并寻找到新的全局更优解。+ − 另外，我们也能使用梯度下降方法，搭配深度学习方法，比如图神经网络，来寻找最优划分。比如，在Klein和Hoel等人的论文<ref name=":19"/>，以及Griebenow 等人<ref name=":Griebenow">Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.</ref>的文献中，把粗粒化方案写成一个分组矩阵，同时将这个分组矩阵参数化，这样把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积，并由此计算EI。之后，使用自动微分方法执行[[梯度下降算法]]从而优化分组矩阵，以使得EI最大化。+ 第1,041行：
第733行： − 在上述的算法介绍中，并未强调各方法对划分节点的限制。但在实际问题场景里，我们可能需要在寻找划分时加入限制来满足问题的特性。+ 第1,048行：
第740行： − + 第1,056行：
第748行： − 当我们决定了最优的划分之后，就能根据该划分得到聚合后的矩阵了。+ − 假设划分是把若干个状态合成一组，而其他状态各为一组，我们要做的是对原本的矩阵内，待聚合状态对应的若干行和若干列聚合成一行和一列，而其他元素则保持不动。+ 第1,064行：
第756行： − + − + − 我们可以把马尔科夫链看做一个状态为节点，转移概率为边。+ 第1,084行：
第776行： − 计算大节点的入流比较简单，而计算大节点的出流会相对较复杂，需要考虑待聚合节点之间的随机游走和状态分布，来计算流出到每个节点的概率。我们可以把出流的聚合看作是对若干行的线性加权平均。+ 第1,090行：
第782行： − 在现有的方法中，大多采用最简单的思路：对状态进行权重一致的平均。当我们只看矩阵本身，认为所有的状态都是平等的，应该分配同等的权重，即<math>p_{Mj} = \frac{1}{n} \sum_{j \in M} p_{ji}</math>。+ − 但是，这种情况只适用于成块的状态划分：由于成块性的同属于一组的微观状态转移到另一组的概率相同的性质，这样的平权平均是没有问题的。但是，当我们对不成块的状态划分进行平权平均时，就会导致宏观和微观的马尔科夫动力学不一致的情况。+ 第1,098行：
第790行： − 当一个随机游走粒子进入到大节点时，它下一步游走到大节点里或大节点外的其他节点的概率时，应考虑其当前处于大节点内的哪个小节点的概率。+ − + − 假设游走已达到了平稳分布<math>\pi</math>，游走粒子处于不同小节点 <math>j</math> 的概率为<math>\pi_j</math>，所以其下一步游走到其他粒子的概率应为<math>p_{Mj} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j\ p_{ji}</math>，而留在大节点的概率为<math>p_{MM} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j \ p_{jj}</math> 。按照权重为平稳分布对若干行进行加权平均，得到的行仍会满足加和为一的条件。+ 第1,115行：
第807行： − + − + − + − 按照该方法进行加和平均，得到的宏观和微观的马尔科夫动力学就会满足一致的条件。虽然该方法直观明了，该方法的问题在于其需要在系统演变到平稳分布前，计算每个 <math>t</math> 时刻的状态分布概率 <math>s_j(t)</math>。在达到平稳分布前直接使用<math>\pi</math>来聚合还是不会满足一致性，所以比较麻烦，而HOM的计算方式则可以解决这个问题。+ 第1,128行：
第820行： − 在Klein等人的论文<ref name=":19">Klein B, Hoel E. The emergence of informative higher scales in complex networks[J]. Complexity, 2020, 20201-12.</ref>，以及Griebenow 等人<ref name=":Griebenow">Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.</ref>的文献中，作者们采用了高阶依赖项建模（[[HOMs]]）<ref name="HOMs">Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>来对网络节点进行聚合。其目的是为了保证聚合后的宏观网络与原始的微观网络具有相同的随机游走动力学特性。该方法也可以用于对马尔科夫链状态进行合并。+ − + 第1,143行：
第835行： − + − − − 复杂网络与马尔科夫链之间存在密不可分的联系。许多复杂网络上的分析方法，比如随机游走等，会利用马尔科夫链动力学的理论。而马尔科夫链同样也会使用到复杂网络的理论分析方法，比如统计物理中的配分函数等。这部分简要介绍了复杂网络中的三种粗粒化方法，具有巨大的应用在马尔科夫链粗粒化问题上的研究潜力。+ − 对一个复杂网络的而言，并不具备一定的动力学，所以需要人为定义一套动力学，借助随机游走子的概念，在网络上定义了一套随机游走动力学。+ 第1,169行：
第859行： − + 第1,201行：
第891行： − 定义粗粒化单元（CGU）：是最优地作为网络粗粒化节点的模式，具有明确输入、输出端口和内部计算节点的基本电路组件。CGU的集合构成“元素字典”，粗粒化网络为版本由该字典构建。部分节点被CGU替换，实现网络压缩。+ − + − + 第1,216行：
第906行： − 采用模拟退化法寻找粗粒化最优的CGU集合，仅以网络模体（在原始网络中出现频率显著高于随机网络的子图）作为候选CGU。+ 第1,222行：
第912行： − − − −
无编辑摘要
[[马尔科夫链]]是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。一般的[[马尔科夫链]]包括 <math>N</math> 个状态，所有状态之间的概率转移构成了一个转移概率矩阵 <math>P</math>，该矩阵有 <math>N</math> 行<math>N</math>列，且满足概率归一化条件（所有元素位于0到1之间，所有行的和为1）。本词条限定在 '''平稳马尔科夫链''' 上的讨论，也就是[math]P[/math]不随时间和状态而变。
[[马尔科夫链]]是一类特殊的随机过程：在给定当前状态后，对未来状态的预测不再依赖更早的过去状态。一般的[[马尔科夫链]]包括 <math>N</math> 个状态，所有状态之间的概率转移构成一个转移概率矩阵 <math>P</math>。该矩阵有 <math>N</math> 行 <math>N</math> 列，且满足概率归一化条件（所有元素位于 0 到 1 之间，所有行的和为 1）。本词条限定在 '''平稳马尔科夫链''' 上讨论，也就是[math]P[/math]不随时间和状态而变。
所谓马尔科夫链的粗粒化，是指找到一个新的马尔科夫链，它具有 <math>1<M<N</math> 个状态，其对应的 <math>M</math> 行 <math>M</math> 列概率转移矩阵为<math>P'</math>。它同样满足概率归一化条件，可以看作对 <math>P</math> 所描述动力学过程的一种抽象近似约简。
文献中一般着重强调对马尔科夫链做粗粒化的意义包括：
文献中一般着重强调对马尔科夫链做粗粒化的意义包括：
# 我们在研究一个超多状态的[[复杂系统]]时，并不会关注每一个微观的状态，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而从微观尺度中总结一些中尺度或宏观尺度的规律；
# 当我们研究一个状态极多的[[复杂系统]]时，往往并不会关注每一个微观状态。在粗粒化中，我们希望过滤掉不感兴趣的噪声和异质性，从微观尺度中总结出一些中尺度或宏观尺度的规律；
# 有些状态的转移概率非常相似，所以可以被看成同一类状态。对这些状态进行划分和归并可以减少马尔科夫链的冗余性，得到一个更简洁有效的表示；
# 有些状态的转移概率非常相似，所以可以被看成同一类状态。对这些状态进行划分和归并可以减少马尔科夫链的冗余性，得到一个更简洁有效的表示；
# 在用到[[马尔科夫决策过程]]的[[强化学习]]算法中，对马尔科夫链做粗粒化可以减少[[状态空间]]的大小，提高训练过程的样本效率和任务表现<ref name=":10">Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).</ref>。
# 在用到[[马尔科夫决策过程]]的[[强化学习]]算法中，对马尔科夫链做粗粒化可以减少[[状态空间]]的大小，提高训练过程的样本效率和任务表现<ref name=":10">Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).</ref>。
对任意马尔科夫链的转移概率矩阵做约简，都存在无穷多种可能的方法。然而在实际粗粒化过程中，我们必须从这些方法中做筛选，使约简后的矩阵[math]P'[/math]尽可能保留原矩阵的主要特征。为刻画这些特征是否被保留，人们提出了不同的标准，包括：
# 首先，我们想尽量'''降低'''动力学在压缩后的'''维度'''；
# 首先，我们想尽量'''降低'''动力学在压缩后的'''维度'''；
=粗粒化=
=粗粒化=
马尔科夫链不只是一个马尔科夫矩阵。它还涉及不同的状态，以及状态之间的转移概率，所以我们可以从不同角度来看待粗粒化：
# 对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，状态转移的过程为一个粒子在节点间跳转，而粗粒化则是对这个网络做降维。
# 对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，状态转移的过程为一个粒子在节点间跳转，而粗粒化则是对这个网络做降维。
# 对概率空间做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。
# 对概率空间做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。
这三种出发点彼此相关，但具体关注的对象不同：第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。
对马尔科夫链做粗粒化并没有统一定义，目前该主题也没有完整的文献综述。在许多文献中，粗粒化（coarse-graining）、聚类/聚合（partitioning/lumping/clustering/aggregation）和降维（dimension reduction）往往是重叠乃至近似等价的。
本词条只讨论离散时间马尔科夫链，且动力学 <math>P</math> 是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们可以定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为 n 的马尔科夫矩阵。同样的，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。
本词条只讨论离散时间马尔科夫链，且动力学 <math>P</math> 是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为 n 的马尔科夫矩阵。同样，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。
多数文献中会出现如图1的定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
多数文献中会出现如图1的定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
对状态空间 <math>S</math> 和转移函数 <math>P(t):S \rightarrow S</math>，我们需要'''一个状态分组的投影函数 <math>\Phi:S \rightarrow S'</math>'''，和'''一个在新状态空间上的转移函数 <math>P'(t):S' \rightarrow S'</math>'''，而且 '''<math>S'</math> 和<math>P'</math> 要符合马尔科夫链定义'''。
对状态空间 <math>S</math> 和转移函数 <math>P(t):S \rightarrow S</math>，我们需要'''一个状态分组的投影函数 <math>\Phi:S \rightarrow S'</math>'''，和'''一个在新状态空间上的转移函数 <math>P'(t):S' \rightarrow S'</math>'''，而且 '''<math>S'</math> 和<math>P'</math> 要符合马尔科夫链定义'''。
如果把这个降维/粗粒化过程拆开看，它可以分为三步。
# '''划分'''（对状态空间进行粗粒化）：对状态进行分组，得出<math>\Phi</math>，决定 <math>S</math> 空间中的状态要如何被投影到 <math>S'</math> 空间上。
# '''划分'''（对状态空间进行粗粒化）：对状态进行分组，得出<math>\Phi</math>，决定 <math>S</math> 空间中的状态要如何被投影到 <math>S'</math> 空间上。
我们假设投影函数 <math>\Phi</math> 是一个 <math>n \times r</math> 的线性投影矩阵，且符合下列两个条件：'''(1)所有元素非负；(2)每行加和等于1。'''
我们假设投影函数 <math>\Phi</math> 是一个 <math>n \times r</math> 的线性投影矩阵，且符合下列两个条件：'''(1)所有元素非负；(2)每行加和等于1。'''
马尔科夫链的粗粒化可以分成硬划分（Hard partitioning）和软划分（Soft partitioning）。硬划分是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而软划分则会有可能出现一个微观状态被分在属于多个宏观类的情况。
马尔科夫链的粗粒化可以分成硬划分（Hard partitioning）和软划分（Soft partitioning）。硬划分是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类；软划分则可能出现一个微观状态同时属于多个宏观类的情况。
在硬划分的情况下，<math>\Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases}</math>，即一个表示<math>i</math>属于<math>j</math>列的零一分组矩阵。如果是软划分的话，<math>\Phi</math>则不一定会是零一矩阵<ref name=":12" />。
在硬划分的情况下，<math>\Phi_{i, j} = \begin{cases} 1\text{, if}\ s_i \in s_j', \\ 0\text{, otherwise} \end{cases}</math>，即一个表示 <math>i</math> 属于 <math>j</math> 类的零一分组矩阵。如果是软划分，<math>\Phi</math> 则不一定是零一矩阵<ref name=":12" />。
在这个词条里，我们主要讨论硬划分<ref name=":4" />。对软划分感兴趣的朋友可以自行参阅这两篇论文<ref>Singh, Satinder, Tommi Jaakkola, and Michael Jordan. "Reinforcement learning with soft state aggregation." ''Advances in neural information processing systems'' 7 (1994).</ref> <ref name=":11">Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." ''Advances in Neural Information Processing Systems'' 32 (2019).</ref>。
在这个词条里，我们主要讨论硬划分<ref name=":4" />。对软划分感兴趣的朋友可以自行参阅这两篇论文<ref>Singh, Satinder, Tommi Jaakkola, and Michael Jordan. "Reinforcement learning with soft state aggregation." ''Advances in neural information processing systems'' 7 (1994).</ref> <ref name=":11">Duan, Yaqi, Tracy Ke, and Mengdi Wang. "State aggregation learning from markov transition data." ''Advances in Neural Information Processing Systems'' 32 (2019).</ref>。
其中 <math>W \in \mathbb{R}^{r \times n}</math>。Buchholz<ref name=":12">Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>的文章中把 <math>W</math> 称作distributor matrix，而 <math>\Phi \in \mathbb{R}^{n \times r}</math> 称作collector matrix。
其中 <math>W \in \mathbb{R}^{r \times n}</math>。Buchholz<ref name=":12">Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>的文章中把 <math>W</math> 称作distributor matrix，而 <math>\Phi \in \mathbb{R}^{n \times r}</math> 称作collector matrix。
我们假设<math>W, \Phi, P, P'</math>都是线性的，所以可以这样理解这个公式：从图1左上角的 t 时刻宏观状态出发，先经过一个“逆向粗粒化”操作<math>W</math>得到 t 时刻微观状态，再经微观动力学 <math>P</math> 得到 t+1 时刻的微观状态，最后经粗粒化 <math>\Phi</math> 得到 t+1 时刻的宏观状态。
从式子{{EquationRef|1}}可以看到，<math>\Phi</math> 和 <math>P</math> 都是给定的，所以这一步要做的是决定 <math>W</math>。<math>W</math> 的基本限制是使 <math>P'</math> 符合马尔科夫矩阵定义；在此基础上，<math>W</math> 仍有无限多种选项，我们可以从中挑出更符合目标特征的方案。
<br/>
<br/>
=粗粒化方案的要求和优化目标=
=粗粒化方案的要求和优化目标=
目前还没有一个严格、完备的马尔科夫链粗粒化定义。在这一章中，我们将简要梳理一些基本概念，以及不同粗粒化方法中用到的要求、优化目标和评价指标。
==问题拆分==
==问题拆分==
粗粒化并不只是“把若干状态聚成几类”的聚类问题。我们需要同时考虑多个层面：'''保留什么尺度上的信息、如何保证宏观动力学仍然自洽、以及如何在压缩和保真之间做权衡'''。我们需要区分：'''哪些微观差异只是会被快速混合掉的局部噪声、快变量或冗余通路，哪些差异则决定了系统未来的主要演化方向、稳态概率流以及跨尺度的因果结构'''。
更直观地说，一个好的宏观态应当把'''“对外行为几乎一样”的微观状态并在一起，把“长期命运明显不同”的状态分开'''。后文提到的成块性、因果态、尺度闭合、有效信息和动力学可逆性，分别对应这个问题的不同侧面：有的在回答“哪些状态适合合并”，有的在回答“合并后是否仍然自洽”，有的则在回答“哪个尺度最有信息价值”。
<br/>
<br/>
==粗粒化与时间演化算子的可交换性==
==粗粒化与时间演化算子的可交换性==
首先，一个重要的粗粒化标准是：'''粗粒化操作和时间演化操作应当是可交换（commutative）的两个算符'''。以图（1）所示情形为例，我们从某个微观状态 <math>s^{(t)}</math> 出发，到达下一刻宏观状态 <math>A^{(t+1)}</math> 有两条不同路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
# 先经过微观动力学的时间演化达到 <math>s^{(t+1)}</math>，再进行粗粒化得到 <math>A^{(t+1)}</math>
# 先经过微观动力学的时间演化达到 <math>s^{(t+1)}</math>，再进行粗粒化得到 <math>A^{(t+1)}</math>；
# 先通过状态的粗粒化得到 <math>A^{(t)}</math>，再经过宏观动力学的演化到达 <math>A^{(t+1)}</math>
# 先通过状态的粗粒化得到 <math>A^{(t)}</math>，再经过宏观动力学的演化到达 <math>A^{(t+1)}</math>。
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：'''从任意一个微观状态分布 <math>s^{(t)}</math> 出发，走这两条路径得到的 <math>A^{(t+1)}</math> 的分布是一样的'''，即
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：'''从任意一个微观状态分布 <math>s^{(t)}</math> 出发，走这两条路径得到的 <math>A^{(t+1)}</math> 的分布是一样的'''，即
|{{EquationRef|2}}}}
|{{EquationRef|2}}}}
这两条路径的一致性在粗粒化领域中非常重要，也被反复提及。满足一致性的粗粒化方案能够充分保留动力学中的有效信息，并丢弃无用信息。具体来说，宏观状态已经捕捉了与未来演化相关的所有“慢变量”或“相关信息”，而被粗粒化掉的那些微观细节，只影响瞬时噪声或快速弛豫过程，不会长期、系统性地改变宏观演化。
对于马尔科夫链，粗粒化时我们通常希望得到一个新的马尔科夫过程：宏观态的转移只依赖当前宏观态，而不依赖更久远的历史。式子（2）说明了，如果粗粒化满足可交换性，那么宏观过程可以写成一个真正意义上的马尔科夫链，拥有一个明确的宏观转移矩阵 <math>P'</math>，而且宏观态的演化不需要记忆“刚才具体是哪个微观态导致了这个宏观态”。如果不满足，那宏观态的演化一般会带有记忆效应，未来的转移概率还会依赖这个宏观态是如何形成的，也就是依赖过去的轨迹。
对于马尔科夫链，粗粒化时我们通常希望得到一个新的马尔科夫过程：宏观态的转移只依赖当前宏观态，而不依赖更久远的历史。式子（2）说明了，如果粗粒化满足可交换性，那么宏观过程可以写成一个真正意义上的马尔科夫链，拥有一个明确的宏观转移矩阵 <math>P'</math>，而且宏观态的演化不需要记忆“刚才具体是哪个微观态导致了这个宏观态”。如果不满足，那宏观态的演化一般会带有记忆效应，未来的转移概率还会依赖这个宏观态是如何形成的，也就是依赖过去的轨迹。
==成块性==
==成块性==
[[马尔科夫链的成块性]]（Lumpability）是一种描述马尔科夫链是否可聚类或可粗粒化性质的概念，最早由Kemeny和Snell在其1969年著作Finite Markov Chains<ref name=":1">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>中阐述。Lump一词有‘块’的意思。判断一个[[马尔科夫链]]是否可成块（lumpable），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其动力学特征的简化链。这种划分需确保：虽然抹除了聚类内部状态的微观差异，但能精确保持块间转移机制。这一特性为状态空间的合理划分提供了严格的数学判据。
[[马尔科夫链的成块性]]（Lumpability）是一种描述马尔科夫链是否可聚类或可粗粒化的概念，最早由Kemeny和Snell在其1969年著作Finite Markov Chains<ref name=":1">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>中阐述。Lump一词有“块”的意思。判断一个[[马尔科夫链]]是否可成块（lumpable），就是判定是否存在一种状态划分方式，能够将原始马尔科夫链压缩为一条保留其动力学特征的简化链。这种划分需确保：虽然抹除了聚类内部状态的微观差异，但能精确保持块间转移机制。这一特性为状态空间的合理划分提供了严格的数学判据。
符合成块性的粗粒化方案有很多很好的性质，如保证了对宏观层面上的最大预测性、保证了微观与宏观过程的一致性等。这使得成块性成为马尔科夫链维度约简研究中最常用的标准之一。
符合成块性的粗粒化方案有很多很好的性质，如保证了对宏观层面上的最大预测性、保证了微观与宏观过程的一致性等。这使得成块性成为马尔科夫链维度约简研究中最常用的标准之一。
成块性的原始定义比较复杂，详见[[马尔科夫链的成块性]]。这里我们介绍其充分必要条件，作为一个更直观的解析。在一些文献中，作者会直接使用这一通俗版解释，而且它与原定义之间存在充分必要条件关系<ref name=":1" />。
===成块性的充分必要条件===
===成块性的充分必要条件===
设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>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>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：
设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>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>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：
'''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都是一样的。也就是说，<math>A_i</math>里的每一个状态<math>s_k</math>转移到<math>A_j</math>中的所有状态的转移概率之和是相同的，'''
'''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都相同。也就是说，<math>A_i</math>里的每一个状态<math>s_k</math>转移到<math>A_j</math>中所有状态的转移概率之和是相同的。'''
{{NumBlk|:|
{{NumBlk|:|
满足这个条件后，我们就可以将<math>A_j</math>中的所有微观状态<math>s_l</math>合并为一个宏观状态<math>A_j</math>，因为它们从其他宏观状态的转入概率是一致的。同样的，我们也可以将<math>A_i</math>中的所有微观状态<math>s_k</math>合并为一个宏观状态<math>A_i</math>，因为这些微观状态<math>s_k</math>（和<math>A_i</math>）到其他宏观状态的转出概率是一致的。
满足这个条件后，我们就可以将<math>A_j</math>中的所有微观状态<math>s_l</math>合并为一个宏观状态<math>A_j</math>，因为它们从其他宏观状态的转入概率是一致的。同样的，我们也可以将<math>A_i</math>中的所有微观状态<math>s_k</math>合并为一个宏观状态<math>A_i</math>，因为这些微观状态<math>s_k</math>（和<math>A_i</math>）到其他宏观状态的转出概率是一致的。
例如，在下图中，<math>s_1</math>和<math>s_2</math>都属于<math>A_1</math>，它们到<math>A_1</math>和<math>A_1</math>的转移概率是一样的；同样，<math>s_3</math>和<math>s_4</math>都属于<math>A_2</math>，它们到宏观状态的转移概率也是一样的。因此，<math>[[1,2], [3, 4]]</math>是<math>P</math>的一个成块划分。
例如，在下图中，<math>s_1</math>和<math>s_2</math>都属于<math>A_1</math>，它们到<math>A_1</math>和<math>A_2</math>的转移概率相同；同样，<math>s_3</math>和<math>s_4</math>都属于<math>A_2</math>，它们到各宏观状态的转移概率也相同。因此，<math>[[1,2], [3, 4]]</math>是<math>P</math>的一个成块划分。
基于这个条件，我们可以定义成块划分的宏观动力学<math>A^{(t)} = A^{(t-1)} P'</math>：
基于这个条件，我们可以定义成块划分的宏观动力学<math>A^{(t)} = A^{(t-1)} P'</math>：
|{{EquationRef|4}}}}
|{{EquationRef|4}}}}
这个公式表明，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的所有状态的转移概率之和。
这个公式表明，群组 <math>A_i</math> 到群组 <math>A_j</math> 的转移概率 = 群组 <math>A_i</math> 中任意状态 <math>s_k</math> 到群组 <math>A_j</math> 的转移概率 = 群组 <math>A_i</math> 中任意状态 <math>s_k</math> 到群组 <math>A_j</math> 中的所有状态的转移概率之和。
我们也可以直接定义<math>P</math>和<math>P'</math>之间的关系：
我们也可以直接定义 <math>P</math> 和 <math>P'</math> 之间的关系：
<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>，
<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>，
其中，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，其逆矩阵就是把对角线上的元素全部取倒数。
其中，<math>\Phi^T \Phi</math> 是一个对角阵，对角线上的元素为每个 <math>A_i</math> 包括了多少个微观状态的计数，其逆矩阵就是把对角线上的元素全部取倒数。
在讨论成块性时，必须明确状态划分的方式。不同的划分方式可能导致不同的结论。一个马尔科夫链可能在某种划分下是成块的，而在另一种划分下则不成块。比如上图例子中，分组 <math>\{\{s_1,s_2\}, \{s_3,s_4\}\}</math> 是成块的，但是当我们考虑分组 <math>\{\{s_1,s_2，s_3\}, \{s_4\}\}</math> 时，组内状态的 <math>p_{s_k \rightarrow A_j}</math> 并不相同，因此不满足成块性的条件定义。
<math>
\begin{aligned}
\begin{array}{ccc:c}
\right ]
</math>
===定义===
===定义===
在计算力学中，状态被理解为智能体接收到的全部历史信息，因此系统从过去到未来的变化被描述为一个离散的平稳[[随机过程]]。状态空间为双（向）无限序列的集合 <math>\overleftrightarrow{S}=\{\cdots, s_{-2}, s_{-1}, s_0, s_1, s_2, \cdots\}</math>，即无限长的时间序列。基于当前时刻 <math>t</math>，我们可以将 <math>\overleftrightarrow{S}</math> 分为单侧前向序列 <math>\overleftarrow{s_t}=\{\cdots, s_{t-3}, s_{t-2}, s_{t-1}\}</math> 和单侧后向序列 <math>\overrightarrow{s_t}=\{s_t, s_{t+1}, s_{t+2}, s_{t+3},\cdots\}</math> 两部分。所有可能的未来序列 <math>\overrightarrow{s_t}</math> 形成的集合记作 <math>\overrightarrow{S}</math>，所有可能的历史序列 <math>\overleftarrow{s_t}</math> 形成的集合记作 <math>\overleftarrow{S}</math>。
因果态是一种对系统状态的粗粒化描述，并不预设系统具有马尔科夫性。为了把因果态和马尔科夫链的粗粒化理论进行比较，可以定义马尔科夫链的因果态：假设系统是一个<math>K</math>阶的马尔科夫链（系统在<math>t</math>时刻的状态分布由前 K 个时刻的状态决定），则可将 <math>\overleftarrow{S}</math> 重新定义为 <math>S^K</math>。
[[文件:因果态的定义.jpg|缩略图|因果态示意图， t = 9 和 t = 13 为同一因果态 |400x400px|替代=]]
[[文件:因果态的定义.jpg|缩略图|因果态示意图， t = 9 和 t = 13 为同一因果态 |400x400px|替代=]]
因果态可定义为映射 <math>\epsilon{:}\overleftarrow{S}\mapsto2^{\overset{\leftarrow}{S}}</math>，满足：<math>
因果态可定义为映射 <math>\epsilon{:}\overleftarrow{S}\mapsto2^{\overleftarrow{S}}</math>，满足：<math>
\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}\}
\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>
===因果态的主要性质===
===因果态的主要性质===
为什么我们要关注因果态这样一种特定的宏观态？下面是因果态的两个主要性质，它们体现了因果态为何是一种理想的宏观态：
==尺度闭合性==
==尺度闭合性==
尺度闭合性讨论的是：粗粒化后的宏观动力学，能否在不反复回到底层微观细节的情况下，自洽地演化、预测和解释。换句话说，我们关心的是：在给定粗粒化 <math>Z_t=f(X_t)</math> 后，宏观尺度是否已经“足够独立”，可以单独承担预测、干预和机制描述的任务<ref name="closure">Rosas, F. E., Geiger, B. C., Luppi, A. I., Seth, A. K., Polani, D., Gastpar, M., & Mediano, P. A. (2024). Software in the natural world: A computational approach to hierarchical emergence. arXiv preprint arXiv:2402.09090.</ref>。关于尺度闭合性的详细讨论请见[[不同尺度之间的闭合性]]。
===跨尺度因果态和υ-机器===
===跨尺度因果态和υ-机器===
前文已经介绍过因果态和 ϵ-机器。在跨尺度问题里，我们还需要一个专门处理“微观历史预测宏观未来”的对象。
设微观过程为 <math>X_t</math>，粗粒化后的宏观过程为 <math>Z_t=f(X_t)</math>。宏观的 ϵ-机器是用宏观历史 <math>\overleftarrow{Z_t}</math> 去预测宏观未来 <math>\overrightarrow{Z_t}</math>；而 Rosas 等人提出的 υ-机器，则是用微观历史 <math>\overleftarrow{X_t}</math> 去预测宏观未来 <math>\overrightarrow{Z_t}</math>。它在微观历史上定义的等价关系为：
{{NumBlk|:|
{{NumBlk|:|
<math>
<math>
\overleftarrow{x_t} \equiv \overleftarrow{x_{t'}} \ \ \text{iff}\ \ p( \overrightarrow{z_t} | \overleftarrow{x_t}) = p(\overrightarrow{z_{t'}}| \overleftarrow{x_{t'}})
\overleftarrow{x_t} \equiv \overleftarrow{x_{t'}} \ \ \text{iff}\ \ p(\overrightarrow{z_t}|\overleftarrow{x_t}) = p(\overrightarrow{z_{t'}}|\overleftarrow{x_{t'}})
</math>
</math>
|{{EquationRef|5}}}}
|{{EquationRef|5}}}}
也就是说，若两段微观历史对宏观未来给出的预测分布完全相同，它们就属于同一个跨尺度因果态。把这些等价类记作 <math>U_t=υ(\overleftarrow{X_t})</math>。直观地看，υ-机器保留的是“对宏观未来真正有用的那部分微观信息”，因此可以把它理解为一种面向跨尺度预测的最优压缩。
在给定粗粒化 <math>Z_t=f(X_t)</math> 后，可以同时出现三种相关状态表征：
# 微观 ϵ-机器的因果态 <math>E_t</math>，保留了对微观未来最完整的预测信息；
# 宏观 ϵ-机器的因果态 <math>E'_t</math>，只保留宏观历史中的信息；
# 跨尺度 υ-机器的因果态 <math>U_t</math>，保留了微观历史中对宏观未来仍然有用的信息。
===三种闭合===
====因果闭合 Causal Closure====
若宏观过程 <math>Z_t</math> 的 ϵ-机器因果态 <math>E'_t</math> 与跨尺度 υ-机器的因果态 <math>U_t</math> 之间存在一一对应关系，那么称该粗粒化满足'''因果闭合'''。
它的物理意义是：微观层面上那些会影响宏观未来的因果差异，已经被宏观历史完整表达出来了。因此，在宏观层面实施干预，与在微观层面做出对应干预后再投影到宏观层，二者在宏观结果上是等价的。若因果闭合成立，我们就不必为了分析宏观干预效果而不断回到底层微观细节。
====信息闭合 Information Closure====
信息闭合强调的不是“干预”，而是“预测”。它要求宏观历史与微观历史对宏观未来提供的信息量相同，即
{{NumBlk|:|
{{NumBlk|:|
<math>
<math>
I( \overleftarrow{Z_t} ; \overrightarrow{Z_t}) = I( \overleftarrow{X_t} ; \overrightarrow{Z_t})
I(\overleftarrow{Z_t};\overrightarrow{Z_t}) = I(\overleftarrow{X_t};\overrightarrow{Z_t})
</math>
</math>
|{{EquationRef|6}}}}
|{{EquationRef|6}}}}
这意味着：若我们已经知道宏观历史 <math>\overleftarrow{Z_t}</math>，再额外补充微观历史 <math>\overleftarrow{X_t}</math>，也不会提升对宏观未来的预测能力。它的物理意义是，宏观尺度在信息上已经“自给自足”，微观细节对宏观预测来说是冗余的。
对给定的粗粒化函数 <math>f</math> 而言，因果闭合和信息闭合是等价的<ref name="closure" />。前者从干预与因果的角度表达同一件事，后者从预测与信息的角度表达同一件事。
====计算闭合 Computational Closure====
计算闭合更关注“机制能否一起被粗粒化”。若存在一个对应于机制层的粗粒化函数 <math>f^*</math>，使得微观 ϵ-机器的因果态 <math>E_t</math> 可以被粗粒化成宏观 ϵ-机器的因果态 <math>E'_t</math>，即 <math>E'_t=f^*(E_t)</math>，那么称该粗粒化满足'''计算闭合'''。
它的物理意义是：宏观动力学不只是状态层面上的简化，也可以看作微观计算机制的一种简化版。也就是说，先找微观机制再粗粒化，与先粗粒化再找宏观机制，在原则上是兼容的。
三者之间的关系可以概括为：对同一个粗粒化 <math>Z_t=f(X_t)</math>，'''因果闭合 = 信息闭合'''，而它们又都会推出计算闭合；反过来则未必成立。因此，计算闭合是三者中相对更宽松的条件。
===尺度闭合 与 成块性===
===尺度闭合 与 成块性===
成块性和尺度闭合都关心“粗粒化后是否仍然自洽”，但它们关注的角度不同。'''成块性'''是马尔科夫链内部的严格结构条件，强调宏观过程仍然是一个真正的马尔科夫链；'''尺度闭合'''则更强调跨尺度的预测、干预和机制是否能够独立成立。
Geiger 和 Temmel 的工作<ref name=":Geiger">B. C. Geiger and C. Temmel, “Lumpings of Markov chains, entropy rate preservation, and higher-order lumpability,” J. Appl. Probab., vol. 51, no. 4, pp. 1114–1132, Dec. 2014, extended version: arXiv:1212.4375.</ref>，以及 Rosas 等人的工作<ref name="closure" />，给出了两者之间的联系，如下图所示。'''在稳态条件下，强成块通常会对应更强的闭合性质：粗略地说，若一个马尔科夫链对给定粗粒化是强成块的，那么宏观层往往也会满足因果/信息闭合；而计算闭合则更宽松，未必要求达到成块性那么严格的结构条件'''。
[[文件:闭合性的概念.png|500px]]
[[文件:闭合性的概念.png|500px]]
因此，可以把二者的关系理解为：'''成块性更像“严格的单尺度动力学闭合”，尺度闭合性则更像“跨尺度上的自洽与独立”'''。前者要求更强，但结论也更干净；后者覆盖的情形更广，更适合讨论涌现、跨尺度预测和机制简化等问题。关于该概念更详细丰富的讨论请见[[不同尺度之间的闭合性]]。
<br/>
<br/>
==因果涌现：最大化有效信息==
==因果涌现：最大化有效信息==
[[因果涌现]]（causal emergence）是指动力系统中的一类特殊的[[涌现]]现象，即系统在宏观尺度会展现出更强的因果特性。特别的，对于一类[[马尔科夫动力系统]]来说，在对其状态空间进行适当的[[粗粒化]]以后，所形成的宏观动力学会展现出比微观更强的因果特性——即更大的[[有效信息]]，那么我们称该系统发生了因果涌现<ref name="ei">Hoel E P, Albantakis L, Tononi G. Quantifying causal emergence shows that macro can beat micro[J]. Proceedings of the National Academy of Sciences, 2013, 110(49): 19790-19795.</ref><ref name=":25">Hoel E P. When the map is better than the territory[J]. Entropy, 2017, 19(5): 188.</ref>。
[[因果涌现]]（causal emergence）是指动力系统中的一类特殊[[涌现]]现象，即系统在宏观尺度展现出更强的因果特性。特别地，对于一类[[马尔科夫动力系统]]来说，在对其状态空间进行适当[[粗粒化]]以后，形成的宏观动力学会展现出比微观更强的因果特性，也就是更大的[[有效信息]]，那么我们称该系统发生了因果涌现<ref name="ei">Hoel E P, Albantakis L, Tononi G. Quantifying causal emergence shows that macro can beat micro[J]. Proceedings of the National Academy of Sciences, 2013, 110(49): 19790-19795.</ref><ref name=":25">Hoel E P. When the map is better than the territory[J]. Entropy, 2017, 19(5): 188.</ref>。
===定义===
===定义===
<math>
<math>
EI = I(X_t,X_{t+1}|do(X_t\sim U(\mathcal{X})))=\frac{1}{N}\sum_{i=1}^N D_{KL}(P_i||\bar{P})
EI &= I(X_t,X_{t+1}|do(X_t\sim U(\mathcal{X})))=I(\tilde{X}_t,\tilde{X}_{t+1}) \\
</math>
</math>
其中 <math>\tilde{X}_t,\tilde{X}_{t+1}</math> 分别为把 <math>t</math> 时刻的 [math]X_t[/math][[干预]]为[[均匀分布]]后，前后两个时刻的状态。从上面式子不难看出，EI仅仅是概率转移矩阵 [math]P[/math] 的函数。将[[转移概率矩阵]] [math]P[/math] 写成 [math]N[/math] 个行向量拼接而成的形式，即：<math>P=(P_1^T,P_2^T,\cdots,P_N^T)^T</math>。将矩阵每列求均值，可得到平均转移向量 <math>\overline{P}=\sum_{k=1}^N P_k/N</math>。因此，EI是转移矩阵每个行转移向量 [math]P_i[/math] 与平均转移向量 [math]\bar{P}[/math] 的[[KL散度]]的均值。
其中 <math>\bar{P}</math> 是转移矩阵各行的平均转移向量。这个表达式说明，EI 本质上度量的是：不同初始状态所对应的转移分布，与“平均转移分布”之间到底有多可区分。若各行彼此差异很大，动力学的因果效应就更强；若各行非常相似，EI 就会较小。
</math>
</math>
确定性是指，在动力学作用下，我们根据系统前一时刻的状态能在多大程度上预测它下一时刻的状态；简并性是指：如果知道了系统当前状态，能否反推系统上一时刻状态的能力。如果可以较好地推断，则这个马尔科夫矩阵的简并性较低，也就是非简并；如果很难推断，则马尔科夫矩阵就是简并的，也即退化的。如果确定性越大，或简并性越小，则系统的有效信息就越大。其他相关详情请参照[[有效信息]]词条。
下表展示的是三个不同的转移概率矩阵，以及它们的EI数值：
下表展示的是三个不同的转移概率矩阵，以及它们的EI数值：
===最大化有效信息的划分===
===最大化有效信息的划分===
开头提到，对马尔科夫链做粗粒化的一个动机，就是想抹除一些微观动力学上的噪音，从而得到在宏观上更具规律性和因果性的动力学。所以，我们可以利用 EI 这一马尔科夫链的因果效应度量，来衡量聚类后宏观动力学的因果强度。
但是，EI 的大小和状态空间大小有关，这一性质在比较不同尺度的[[马尔科夫链]]时很不方便。我们需要一个尽可能不受尺度效应影响的[[因果效应度量]]，因此需要对有效信息 EI 做归一化处理，得到一个和系统尺寸无关的量化指标。根据[[Erik Hoel]]和[[Tononi]]等人的工作，应使用[[均匀分布]]即[[最大熵分布]]下的熵值 <math>\log N</math> 作为分母对 EI 进行归一化，这里的[math]N[/math]为状态空间[math]\mathcal{X}[/math]中的状态数<ref name="hoel_2013">{{cite journal|last1=Hoel|first1=Erik P.|last2=Albantakis|first2=L.|last3=Tononi|first3=G.|title=Quantifying causal emergence shows that macro can beat micro|journal=Proceedings of the National Academy of Sciences|volume=110|issue=49|page=19790–19795|year=2013|url=https://doi.org/10.1073/pnas.1314922110}}</ref>。那么归一化后的 EI 为：
<math>
<math>
有了有效信息这一度量指标后，我们便可以讨论马尔科夫链上的因果涌现。对于一个马尔科夫链，观察者可以建立多尺度视角来区分微观和宏观。首先，原始的马尔科夫概率转移矩阵 <math>P_N</math> 定义了微观动力学；其次，经过对微观态的粗粒化映射（coarse-graining）后，观察者可以得到对应的宏观状态（即分组），这些宏观状态彼此之间的概率转移可以用宏观的马尔科夫概率转移矩阵 <math>P_M</math> 来刻画。对两个动力学分别计算 EI 后，如果宏观的 EI 大于微观 EI，我们就说该系统发生了因果涌现。
[[文件:CE.png|缩略图|因果涌现示意图|500x500像素]]
[[文件:CE.png|缩略图|因果涌现示意图|500x500像素]]
|}
|}
在这个例子中，微观态的转移矩阵是一个 4×4 的矩阵，其中前三个状态彼此以 1/3 的概率相互转移。这导致该转移矩阵的确定性较小，因此 EI 也不高，仅为 0.81。对该矩阵进行粗粒化时，我们把前三个状态合并为一个状态 a，把最后一个状态视为另一个宏观态 b。这样，原本三个微观态之间的转移就变成了宏观态 a 的内部转移，因此转移概率矩阵变成了[math]P_M[/math]，其 EI 为 1。在这个例子中，可以计算其[[因果涌现度量]]为：
<math>
<math>
===最大化动力学可逆性 Dynamical Reversibility===
===最大化动力学可逆性 Dynamical Reversibility===
[[基于可逆性的因果涌现理论]]是一种量化[[因果涌现 Causal Emergence|因果涌现]]的新框架，提出了近似动力学可逆性（<math>\Gamma_{\alpha}</math>）的概念，用于量化[[马尔科夫动力学]]接近可逆动力学的程度<ref name="reversibility">Zhang, J., Tao, R., Leong, K.H. et al. Dynamical reversibility and a new theory of causal emergence based on SVD. npj Complex 2, 3 (2025).</ref>。
[[基于可逆性的因果涌现理论]]是一种量化[[因果涌现 Causal Emergence|因果涌现]]的新框架，提出了近似动力学可逆性（<math>\Gamma_{\alpha}</math>）的概念，用于量化[[马尔科夫动力学]]接近可逆动力学的程度<ref name="reversibility">Zhang, J., Tao, R., Leong, K.H. et al. Dynamical reversibility and a new theory of causal emergence based on SVD. npj Complex 2, 3 (2025).</ref>。该理论的核心思想是：'''因果涌现其实等价于动力学可逆性的涌现'''。'''该指标与[[有效信息]]高度相关，因此也可以用来刻画动力学的[[因果效应强度]]。'''
直观地说，如果把一个马尔科夫动力学看作通信信道，那么每一状态下的概率转移就可以看作一条信息通路（information pathway）。于是，系统发生因果涌现就等价于系统中存在冗余的信息通路，也就是某些状态转移彼此相似或线性相关。消除这些冗余通路的最好办法，就是利用 SVD 找到等于零或接近于零的奇异值及其对应的奇异向量，这实际上正是最大化有效信息的精髓所在。事实上，我们可以证明，最大化宏观动力学有效信息的粗粒化方案，近似等价于将系统动力学投影到较大奇异值对应的奇异向量方向上的方案。而系统所能达到的最大信息传输效率提升（归一化的近似动力学可逆性），就可以定义为因果涌现的强度。
所以，给定一个系统的马尔科夫转移矩阵，通过对它进行[[奇异值分解]]，将奇异值 <math>\sigma_i</math>的 <math>\alpha</math> 次方之和定义为马尔科夫动力学的近似可逆性度量（<math>\Gamma_{\alpha}\equiv \sum_{i=1}^N\sigma_i^{\alpha}</math>），用以刻画最终指标偏向于衡量确定性或简并性的程度。通常我们取 <math>\alpha=1</math>，表示平权考虑确定性或简并性对最终可逆性度量的影响。
所以，给定一个系统的马尔科夫转移矩阵，通过对它进行[[奇异值分解]]，我们把奇异值 <math>\sigma_i</math> 的 <math>\alpha</math> 次方之和定义为马尔科夫动力学的近似可逆性度量（<math>\Gamma_{\alpha}\equiv \sum_{i=1}^N\sigma_i^{\alpha}</math>），用以刻画最终指标更偏向衡量确定性还是简并性。通常取 <math>\alpha=1</math>，表示平权考虑确定性和简并性对最终可逆性度量的影响。
基于可逆性的因果涌现理论与其他因果涌现理论最大的区别在于：它不需要指定粗粒化策略，仅从马尔科夫转移矩阵的奇异值谱就能判断因果涌现是否发生，并直接定义'''清晰因果涌现'''（clear causal emergence）和'''模糊因果涌现'''（vague causal emergence）的概念。这在一定程度上规避了因果涌现结果依赖粗粒化策略、以及最大化有效信息难以优化求解的问题。其次，这套理论指出，一个动力系统的因果涌现特性仅由系统线性化算符的奇异值谱决定，因而是一套更能反映系统动力学特性本身的因果涌现理论。相关详情请参照[[基于可逆性的因果涌现理论]]词条。
在实际使用中，我们通常直接把矩阵 <math>P</math> 的 <math>\alpha</math> 阶近似动力学可逆性定义为：
<blockquote>
<blockquote>
<math>\begin{aligned}
<math>\begin{aligned}
</math>
</math>
</blockquote>
</blockquote>
其中<math>\alpha\in(0,2)</math>是参数。当 <math>\alpha\ge1</math> 时，<math>\Gamma_{\alpha}</math> 是 <math>P</math> 的[[沙滕范数]]（Schatten norm）；当 <math>0<\alpha<1</math> 时，<math>\Gamma_{\alpha}</math> 是 <math>P</math> 的准范数（quasinorm）<ref>Schatten norm from Wikipedia. https://en.wikipedia.org/wiki/Schatten norm</ref><ref>Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review 52(3), 471–501 (2010)</ref><ref>Chi, Y., Lu, Y.M., Chen, Y.: Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing 67(20), 52395269 (2019)</ref><ref name="Cui">Cui, S., Wang, S., Zhuo, J., Li, L., Huang, Q., Tian, Q.: Towards discriminability and diversity: Batch nuclear-norm maximization under label insufficient situations. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3941–3950 (2020)</ref>。使用这个定义来刻画近似动力学可逆性是合理的，因为完全动力学可逆性可以通过最大化 <math>\Gamma_{\alpha}</math> 来得到。我们可以证明如下结论：对于任意 <math>\alpha\in(0,2)</math>，<math>\Gamma_{\alpha}</math> 的最大值是 <math>N</math>，当且仅当 <math>P</math> 是置换矩阵的时候能取到该最大值。
其中 <math>\sigma_i</math> 是 <math>P</math> 的奇异值。对本文来说，保留这个直观定义就够了：'''<math>\Gamma_{\alpha}</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> 不变。
张江等人<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> 不变。
最大化动力学可逆性的合理性，来源于这套 SVD 方案定义的因果涌现与“最大化有效信息”的因果涌现定义之间的密切关系。在[[基于有效信息的因果涌现理论|Erik Hoel 因果涌现理论]]的框架内，给定马尔科夫动力学系统的因果涌现大小依赖于粗粒化策略的选择，而最优粗粒化策略可以通过最大化宏观动力学的 EI 来寻找。
我们可以证明，要获得最大化有效信息的粗粒化策略，近似等价于采用向最大奇异值对应的奇异向量方向投影的策略。严格推导可见[[基于有效信息的因果涌现理论]]。由于对离散马尔科夫链来说，粗粒化策略往往是由比较严格的 0 或 1 构成的向量，因此不能简单地按奇异向量直接投影。但是，如果粗粒化策略尽可能与最大的几个奇异向量平行，就可以让粗粒化后动力学的 EI 尽可能更大。因此，最大化 EI 的必要条件近似可以理解为：向最大奇异值对应的奇异向量空间做投影。在实际应用中，粗粒化策略 <math>\phi</math> 的约束（例如宏观动力学 TPM 的分组和归一化）会阻止 <math>\phi_j</math> 与奇异向量完美对齐。因此，基于 SVD 的粗粒化策略只是最大化 EI 的近似必要条件。
===动力学一致性===
===动力学一致性===
好的粗粒化方案，应当尽可能保证原始网络（或转移矩阵）和粗粒化后网络（或转移矩阵）彼此相似。Erik Hoel 和 Klein <ref name=":19" /> 提出使用动力学一致性来衡量状态轨迹在原始网络和粗粒化后网络上的一致程度。详情请见[[复杂网络中的因果涌现]]词条。
以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]：
以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]：
定义微观网络 <math>G</math> 与宏观网络 <math>G_M</math>，分别在两个网络上进行[[随机游走]]。在某个时间 <math>t</math>，<math>G</math> 上的预期分布为 <math>P_m(t)</math>，而 <math>G_M</math> 上的预期分布为 <math>P_M(t)</math>。
定义微观网络 <math>G</math> 与宏观网络 <math>G_M</math>，分别在两个网络上进行[[随机游走]]。在某个时间 <math>t</math>，<math>G</math> 上的预期分布为 <math>P_m(t)</math>，而 <math>G_M</math> 上的预期分布为 <math>P_M(t)</math>。
将 <math>P_m(t)</math> 分布叠加到宏观宏观 <math>G_M</math> 的相同节点上，得到 <math>P_{M|m}(t)</math> 分布。通过计算 <math>P_M(t)</math> 和 <math>P_{M|m}(t)</math> 之间的KL散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下：
将 <math>P_m(t)</math> 分布叠加到宏观网络 <math>G_M</math> 的相同节点上，得到 <math>P_{M|m}(t)</math> 分布。通过计算 <math>P_M(t)</math> 和 <math>P_{M|m}(t)</math> 之间的 KL 散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下：
<math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
<math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
也就是说，不一致性表示宏观和微观网络节点在不同时刻概率分布的[[KL散度]]之和。
动力学一致性在某种程度上反映了动力学与粗粒化算子的可交换性，但比可交换性更灵活、更宽松，可以计算“不可交换但近似交换”的程度。
<br/>
<br/>
随机动力学为我们提供了另一个视角来讨论马尔科夫链的 '''状态分布'''。
随机动力学为我们提供了另一个视角来讨论马尔科夫链的 '''状态分布'''。
当我们观察马尔科夫链的一个具体样本时，其在每一步都处于某个'''确定状态'''。而所谓状态分布，是指给定初始分布 <math>\mu</math> 后，系统在 <math>t</math> 时刻落在各个状态的概率。若存在分布 <math>\pi</math> 满足 <math>\pi P = \pi</math>，则称其为'''稳态分布'''。它表示系统在到达稳态后，再继续演化，整体分布会保持不变。
这样，我们就能把马尔科夫链放进'''随机动力系统（Random Dynamical System）'''的框架中来理解。简单来说，随机动力系统由两部分组成：<math>\theta</math> 表示噪声序列随时间的推进，<math>\phi</math> 表示状态在当前噪声作用下的演化规则。对马尔科夫链而言，每一步按 TPM 进行随机选择，就对应着由噪声驱动的演化过程 <math>(\theta,\phi)</math>。
在这个框架里，'''不变性（Invariance）'''是理解稳态分布的关键。稳态分布描述的是'''分布层面'''的不变，而随机吸引子描述的则是'''状态集合层面'''的不变：一个随机集合 <math>A(\omega)</math> 若要成为随机吸引子，通常需要满足三点：
# '''紧致性 (Compactness)'''：对有限状态马尔科夫链，这一点天然满足；
# '''不变性 (Invariance)'''：系统从 <math>A(\omega)</math> 出发演化后，仍落在下一时刻的吸引子中；
# '''吸引性 (Pullback Attraction)'''：从足够久远的过去出发，系统最终会被拉回到该集合附近。
因此，随机吸引子刻画的是系统长期反复停留、且不会轻易逃离的结构。也正是在这个意义上，可约、周期、滑过态这些概念可以被理解为'''稳态下的自然分组规律'''。
===基础划分===
===基础划分===
从长期行为看，马尔科夫链中的状态可以先分成两类：'''滑过态（Transient）'''和'''常返态（Recurrent）'''。滑过态只是在过渡阶段被访问，离开后最终可能不再返回；常返态则会被反复访问。常返态进一步组成'''闭合常返类'''：同一类中的状态彼此可达，而且一旦进入该类就不会再离开。若一个常返类的返回步数存在公因子 <math>d>1</math>，它还可以继续分解为 <math>d</math> 个'''周期子类'''，系统按固定顺序在这些子类之间循环。
===随机吸引子和对应分组===
在稳态视角下，马尔科夫链常见有三种情形：
# '''不可约、非周期'''：整个状态空间形成唯一的平凡吸引子 <math>A(\omega)=X</math>。这说明系统的长期活动遍及整个空间，因此随机动力学本身并不给出更细的自然分组。
# '''可约'''：设 <math>S=T \cup R_1 \cup \cdots \cup R_m</math>，其中 <math>T</math> 是滑过态集，<math>R_i</math> 是闭合常返类。此时每个 <math>R_i</math> 都对应一个确定性的吸引子 <math>A_i=R_i</math>。因此，自然分组就是把不同常返类分开；而滑过态属于过渡区，应与这些吸引子分开看待。
# '''不可约、周期为 <math>d>1</math>'''：状态空间可分解为 <math>X=C_0 \cup C_1 \cup \cdots \cup C_{d-1}</math>，并按 <math>C_0 \to C_1 \to \cdots \to C_{d-1} \to C_0</math> 循环。此时吸引子不再是固定集合，而是随时间在各周期子类之间切换的非平凡随机吸引子；相应的自然分组就是这些周期子类。
所以，随机动力学的意义不只是重新表述马尔科夫链，而是把'''长期命运相同的状态'''显式区分出来：常返类、周期类和滑过态之间的边界，本身就提供了一种值得优先尊重的粗粒化基准。详细的数学公式和证明可参考[[马尔科夫链中的随机动力学]]。
'''情况1：不可约、非周期的马尔科夫链'''
<br/>
<br/>
* 成块性、因果态和稳态分布下的随机动力学划分是“结构性性质 / 自然划分”的理论工具。
* 成块性、因果态和稳态分布下的随机动力学划分是“结构性性质 / 自然划分”的理论工具。
<br/>
===成块性 v.s. 有效信息/动力学可逆性===
===成块性 v.s. 有效信息/动力学可逆性===
但是，这两个概念并不完全等价。成块性的目标是想在保证宏观和微观动力学的一致性的情况下去对状态做分组，而因果涌现的主要目标是想最大化粗粒化之后宏观动力学的因果强度。
但是，这两个概念并不完全等价。成块性的目标是想在保证宏观和微观动力学的一致性的情况下去对状态做分组，而因果涌现的主要目标是想最大化粗粒化之后宏观动力学的因果强度。
在普通的成块性例子里，粗粒化之后往往能得到一个 EI 或可逆性都很高的宏观动力学。但是，当我们考虑一些极端例子时，如下图所示，我们可以强行让每一组里的状态转移概率尽可能不一样，但加总后又恰好一样，从而仍满足成块性的划分。按照这种成块划分去做粗粒化，并不一定会得到高的 EI 或可逆性。相反，用另一个不成块的分组来做粗粒化，得到的宏观动力学 EI 和可逆性反而可能更高。这一现象说明：
# 基于成块性的最优划分不一定等于基于可逆性的最优划分。
# 基于成块性的最优划分不一定等于基于可逆性的最优划分。
=划分方法=
=划分方法=
当我们想把 <math>N</math> 个状态的马尔科夫链划分成 <math>M</math> 组时，待选的划分数量可以由 第二类斯特林数（Stirling numbers of the second kind）表示，<math>S(N, M) = \frac{1}{M!} \sum_{k=0}^{M} (-1)^{M-k} \binom{M}{k} k^N</math>
当我们想把 <math>N</math> 个状态的马尔科夫链划分成 <math>M</math> 组时，待选划分的数量可以由第二类斯特林数（Stirling numbers of the second kind）表示：<math>S(N, M) = \frac{1}{M!} \sum_{k=0}^{M} (-1)^{M-k} \binom{M}{k} k^N</math>
待选划分的数量极大，比如<math>S(20,10)=1.107e32</math>，几乎不可能通过遍历所有划分来寻找最优解，所以我们需要使用一些方法来有效寻找近似最优解。
==逐层贪婪算法==
==逐层贪婪算法==
在这个问题中，我们可以采取自底向上合并（Bottom-Up）的层次聚类（Hierarchical Clustering）方法，即从最细粒度（每个状态单独成组，一共 <math>N</math> 组）开始，每一步合并两个最相似的组，直到达到目标分组数 <math>M</math>。
具体步骤如下：
具体步骤如下：
==谱分解==
==谱分解==
谱分解（Spectral Clustering）的思想是利用矩阵的谱，即特征向量，所展示的物理含义进行聚类和划分。
谱分解（Spectral Clustering）的思想，是利用矩阵的谱，也就是特征向量所展示的物理含义来进行聚类和划分。
===最大化有效信息的谱分解方法===
===最大化有效信息的谱分解方法===
这类方法的核心思路是：先对转移矩阵做特征分解，用特征值和特征向量构造状态间的相似性，再在嵌入空间中聚类，最后据此构造宏观动力学。
'''输入'''：原始包含 <math>N</math> 个状态的马尔科夫链 <math>P</math> 和距离超参 <math>\epsilon</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>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’=\{\lambda_ie_i|\lambda_i≠0\}^N_{i=1}</math>，该集合中的每个向量都被其对应的特征值加权，同时去除了零特征值及其对应的特征向量（新的状态数量为<math>N'=rank(P)</math>）。直观地说，忽略特征值为 0 的特征向量是有意义的，因为它对应了动力学中的简并性，而非零特征值及其对应特征向量则包含了丰富的网络拓扑结构信息；
# 依据 <math>E'</math> 计算状态间的相似矩阵 <math>D_{N'×N'}</math>：
# 依据 <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>v_i</math> 和 <math>v_j</math> 分别在对方的马尔科夫毯中，则通过新的特征向量计算两个节点的 cosine 相似性，作为两者间的相似度 <math>d_{ij}</math> 和 <math>d_{ji}</math>；
## 否则将两个节点间的相似度设为无穷大 <math>\infty</math>（可以设个比较大的值，如10000）；
## 否则将两个节点间的相似度设为无穷大 <math>\infty</math>（可以设个比较大的值，如10000）；
# 基于相似度矩阵<math>D_{N'×N'}</math>和一个超参<math>\epsilon</math>（需要线性搜索，可以选择EI最大的参数），使用[[OPTICS]]算法（是一种基于密度的划分算法，旨在识别数据集中不同密度的划分结构）进行划分，输出对应超参<math>\epsilon</math>下的划分方式。
# 基于相似度矩阵<math>D_{N'×N'}</math>和一个超参<math>\epsilon</math>（需要线性搜索，可以选择EI最大的参数），使用[[OPTICS]]算法（是一种基于密度的划分算法，旨在识别数据集中不同密度的划分结构）进行划分，输出对应超参<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>这样的矩阵：既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
[[文件: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> 的奇异值结构来恢复成块划分。
针对这一问题，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>\pi</math> 是 <math>P</math> 的稳态分布，<math>F_{ij} = \pi_i P_{ij}</math> 可以理解为系统在稳态下从状态 <math>i</math> 流向状态 <math>j</math> 的长期概率流量。具体步骤如下：
#获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样，并由此得到频率矩阵 <math>F</math>；
# 获取一个 <math>n\times n</math> 维的马尔科夫矩阵 <math>P</math>，或者马尔科夫链的频率采样，并由此得到频率矩阵 <math>F</math>；
#获取马尔科夫秩<math>r<n</math> ，或指定一个<math>r</math>；
# 获取马尔科夫秩<math>r<n</math>，或指定一个<math>r</math>；
#对 <math>F</math> 进行SVD分解，<math>F = U \Sigma V^T</math>，其中 <math>U</math> 为左奇异向量，<math>V</math> 为右奇异向量，<math>\Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N})</math> 是一个对角矩阵，包含所有有序奇异值。
# 对 <math>F</math> 进行 SVD 分解，<math>F = U \Sigma V^T</math>，其中 <math>U</math> 为左奇异向量，<math>V</math> 为右奇异向量，<math>\Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N})</math> 是一个对角矩阵，包含所有有序奇异值；
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
# 通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
<math>
<math>
其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。这个算法的核心思想是：在最优的划分中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。
其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。这个算法的核心思想是：在最优的划分中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。
这个算法看起来非常熟悉，实际上它与 k-Means 聚类算法非常相似。让<math>v_s</math>和组里的<math>V[i:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i:r]</math>这若干个点的中心。回顾一下k-Means算法把n个点聚成r类的目标函数，其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点：
这个算法看起来非常熟悉，实际上它与 K-Means 聚类算法非常相似。让<math>v_s</math>和组里的<math>V_{[i,:r]}</math>距离最小的方法，就是让<math>v_s</math>成为这些点的中心。回顾一下 K-Means 算法把 n 个点聚成 r 类的目标函数，其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点：
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
当系统存在明显的近成块结构时，<math>F</math> 的前 <math>r</math> 个奇异值主要反映的是组间的大尺度概率流通道，而后续的奇异值反映的是组内的局部流量波动。如果这两部分之间存在明显的谱间隙（singular value gap），即 <math>\sigma_r(F_1) \gg |F_2|</math>，那么 K-Means 聚类 <math>\hat{V}_F</math> 就能准确恢复成块划分。
当系统存在明显的近成块结构时，<math>F</math> 的前 <math>r</math> 个奇异值主要反映的是组间的大尺度概率流通道，而后续的奇异值反映的是组内的局部流量波动。如果这两部分之间存在明显的谱间隙（singular value gap），即 <math>\sigma_r(F_1) \gg |F_2|</math>，那么 K-Means 聚类 <math>\hat{V}_F</math> 就能准确恢复成块划分。
这对应于一种特殊但常见的物理场景：系统各状态群之间的长期概率流量远弱于群内流量，形成类似“准吸引域”的结构，粒子长时间在群内游走，偶尔才跨越群边界。当 <math>P</math> 不是精确成块，而是近似成块（near-lumpable）时，该方法仍然可以工作，但需要满足一个关键条件：'''组间动力学 <math>F_1</math> 的奇异值必须主导 <math>F</math> 的整体奇异值谱'''，即 <math>\sigma_r(F_1) \gg \|F_2\|</math>。
需要注意的是，成块性的数学定义本身并'''不要求并不要求准吸引域结构（群内流量强于群间流量）'''。成块性只要求同组状态到各组的转移概率总量相同，并不约束转移的方向强弱。论文给出了分组错误率的上界：
需要注意的是，成块性的数学定义本身并'''不要求准吸引域结构（群内流量强于群间流量）'''。成块性只要求同组状态到各组的转移概率总量相同，并不约束转移的方向强弱。论文给出了分组错误率的上界：
<math>
<math>
===基于动力学可逆性的谱分解方法===
===基于动力学可逆性的谱分解方法===
张江等人关于动力学可逆性的文章<ref name="reversibility"/>提供了另一种基于 SVD 的粗粒化方法。该工作的出发点与上面寻找成块划分的方法不同：它不以恢复某种预设的结构性划分为目标，而是把马尔科夫动力学看作一个通信信道，把每个状态下的概率转移看作一条信息通路（information pathway）。当系统的 <math>N</math> 条通路中存在线性相关的行向量时，这些通路就是冗余的，它们要么传递极少的信息（对应接近零的奇异值），要么可以被其他通路的线性组合表示。
通过 SVD 可以识别出 <math>r_\epsilon</math> 条"核心通路"，其余 <math>N - r_\epsilon</math> 条是可以消除的冗余通路。粗粒化就是把状态按照它们在核心通路上的表现进行归组，让宏观动力学只保留这些高效通道。其基本思想是将 <math>P</math> 中的行向量 <math>P_{i},\forall i \in [1,N]</math> 投影到 <math>P</math> 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 <math>P</math> 的主要信息，并保持 <math>\Gamma</math> 不变。
通过 SVD 可以识别出 <math>r_\epsilon</math> 条“核心通路”，其余 <math>N - r_\epsilon</math> 条则是可以消除的冗余通路。粗粒化就是把状态按照它们在核心通路上的表现进行归组，让宏观动力学只保留这些高效通道。其基本思想是将 <math>P</math> 中的行向量 <math>P_{i},\forall i \in [1,N]</math> 投影到 <math>P</math> 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 <math>P</math> 的主要信息，并尽量保持 <math>\Gamma</math> 不变。
与 EI 相比，<math>\Gamma_\alpha</math> 能捕捉到 EI 无法感知的信息：EI 基于 KL 散度，只能度量行向量之间的'''相似性'''；而 <math>\Gamma_\alpha</math> 基于线性代数，还能度量行向量之间的'''线性依赖性'''。两个行向量可以彼此很不像（KL 散度大），但仍然线性相关（一个是另一个的线性组合）。后一种情况下，EI 看不出冗余，但 <math>\Gamma_\alpha</math> 能通过秩亏反映出来。
与 EI 相比，<math>\Gamma_\alpha</math> 能捕捉到 EI 无法感知的信息：EI 基于 KL 散度，只能度量行向量之间的'''相似性'''；而 <math>\Gamma_\alpha</math> 基于线性代数，还能度量行向量之间的'''线性依赖性'''。两个行向量可以彼此很不像（KL 散度大），但仍然线性相关（一个是另一个的线性组合）。后一种情况下，EI 看不出冗余，但 <math>\Gamma_\alpha</math> 能通过秩亏反映出来。
# 给定含有 <math>N</math> 个状态的马尔科夫矩阵 <math>P</math>，对其做 SVD 分解 <math>P = U \Sigma V^T</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>\epsilon</math>，取前 <math>r_\epsilon</math> 个右奇异向量，构成 <math>V_{N \times r_\epsilon}</math>；
# 对 <math>P</math> 的行向量做 PCA 降维：<math>\tilde{P} = P \cdot V_{N \times r_\epsilon}</math>，得到每个状态在核心通路子空间上的投影；这一步的物理含义是：<math>P^T P</math> 是转移概率矩阵的自相关矩阵，其特征向量 <math>V</math> 给出了"哪些目的地模式是相关联的"这一信息的主轴。<math>\tilde{P}i = P_i \cdot V{N \times r_\epsilon}</math> 是状态 <math>i</math> 的出转移分布在这些主要模式上的投影——保留了该状态"在核心通路上的行为"，滤去了冗余通路上的波动。
# 对 <math>P</math> 的行向量做 PCA 降维：<math>\tilde{P} = P \cdot V_{N \times r_\epsilon}</math>，得到每个状态在核心通路子空间上的投影；这一步的物理含义是：<math>P^T P</math> 是转移概率矩阵的自相关矩阵，其特征向量 <math>V</math> 给出了“哪些目的地模式是相关联的”这一信息的主轴。<math>\tilde{P}_i = P_i \cdot V_{N \times r_\epsilon}</math> 是状态 <math>i</math> 的出转移分布在这些主要模式上的投影，保留了该状态“在核心通路上的行为”，滤去了冗余通路上的波动。
# 对 <math>\tilde{P}</math> 的行向量用 K-Means 聚类为 <math>r_\epsilon</math> 组，得到划分 <math>\Phi</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>\Phi</math> 和稳态流矩阵 <math>F = \mathrm{diag}(\pi) P</math>，通过 <math>F' = \Phi^T F \Phi</math> 构建宏观稳态流矩阵，再对每行归一化得到宏观转移矩阵 <math>P'</math>。
虽然该工作与前面 Zhang & Wang 的方法都包含 SVD + K-Means 这一步，但两者之间仍存在差异：
# Zhang & Wang的工作目标是在粗粒化过程中尽量保持马尔科夫性，并恢复成块结构；而动力学可逆性工作的目标是在粗粒化过程中减少 TPM 中的信道冗余性。
# Zhang & Wang的工作目标是在粗粒化过程中尽量保持马尔科夫性，并恢复成块结构；而动力学可逆性工作的目标是在粗粒化过程中减少 TPM 中的信道冗余性。
==其他方法==
==其他方法==
寻找最优划分本质上是一个组合优化问题，所以我们也能使用其他合适的方法来解决它。
首先是遗传算法。它是一种受生物进化启发的全局优化算法，通过模拟自然选择（选择适应度高的个体作为父代）、交叉（通过父代基因重组生成子代）和变异（以一定概率随机改变子代基因）等机制，在解空间中搜索最优解。其核心流程包括：
首先是遗传算法。它是一种受生物进化启发的全局优化算法，通过模拟自然选择（选择适应度高的个体作为父代）、交叉（通过父代基因重组生成子代）和变异（以一定概率随机改变子代基因）等机制，在解空间中搜索最优解。其核心流程包括：
## 变异：以一定概率随机改变子代基因。
## 变异：以一定概率随机改变子代基因。
所以，我们可以把上述逐层贪婪算法和谱分解方法的解作为初始解，再借助遗传算法帮助跳出局部最优，从而找到新的全局更优解。
另外，我们也可以使用梯度下降，搭配图神经网络等深度学习方法来寻找最优划分。比如，在 Klein 和 Hoel 等人的论文<ref name=":19"/>，以及 Griebenow 等人<ref name=":Griebenow">Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.</ref>的文献中，作者把粗粒化方案写成一个分组矩阵，并将其参数化，这样就能把最终的粗粒化网络表达为分组矩阵与原始网络邻接矩阵的乘积，并由此计算 EI。之后，再使用自动微分方法执行[[梯度下降算法]]来优化分组矩阵，使 EI 最大化。
'''输入'''：包含 <math>N</math> 个节点的原始网络 <math>G</math>，其对应邻接矩阵为：<math>A</math>，粗粒化后的网络所包含的节点数：<math>K</math>；'''输出'''：宏观网络 <math>G'</math>，对应的邻接矩阵为：<math>B</math>，以及对应的从 <math>A</math> 到 <math>B</math> 的粗粒化矩阵：<math>M</math>
'''输入'''：包含 <math>N</math> 个节点的原始网络 <math>G</math>，其对应邻接矩阵为：<math>A</math>，粗粒化后的网络所包含的节点数：<math>K</math>；'''输出'''：宏观网络 <math>G'</math>，对应的邻接矩阵为：<math>B</math>，以及对应的从 <math>A</math> 到 <math>B</math> 的粗粒化矩阵：<math>M</math>
==对划分的限制==
==对划分的限制==
在上述算法介绍中，并未特别强调各方法对划分节点的限制。但在实际问题场景里，我们往往需要在寻找划分时加入限制，以满足问题本身的特性。
比如，在社区检测问题中，具有只允许相邻的节点聚合在一起的约束。这要求状态划分必须遵循状态转移图的拓扑结构，同一聚合状态内的节点必须在状态转移图中直接相连或通过短路径可达（如K-邻域）。这种限制确保聚合状态具有空间连贯性，同时大幅减少可行划分数量。
比如，在社区检测问题中，具有只允许相邻的节点聚合在一起的约束。这要求状态划分必须遵循状态转移图的拓扑结构，同一聚合状态内的节点必须在状态转移图中直接相连或通过短路径可达（如K-邻域）。这种限制确保聚合状态具有空间连贯性，同时大幅减少可行划分数量。
# '''因果独立性'''：当我们把整个组看作一个宏观状态时，由于组内所有状态的马尔科夫毯相同，意味着这个宏观状态与外部状态的交互（输入和输出）在统计上是一致的；
# '''因果独立性'''：当我们把整个组看作一个宏观状态时，由于组内所有状态的马尔科夫毯相同，意味着这个宏观状态与外部状态的交互（输入和输出）在统计上是一致的；
# '''信息压缩与模式识别'''：具有相同马尔科夫毯的状态在系统中扮演相似的角色（即它们与其他状态之间的依赖关系相同）。将这些状态聚合成一个宏观状态，相当于识别出了系统中的一个功能模块或模式；
# '''信息压缩与模式识别'''：具有相同马尔科夫毯的状态在系统中扮演相似的角色（即它们与其他状态之间的依赖关系相同）。将这些状态聚合成一个宏观状态，相当于识别出了系统中的一个功能模块或模式；
# '''因果涌现'''：在复杂系统中，这种聚合可能导致宏观层面出现新的因果特性（即涌现）。如果聚合后的宏观状态能产生比单个状态更明确、更强大的因果作用，则称为因果涌现。此时，宏观状态的马尔可夫转移模型可以更有效地预测系统行为。
# '''因果涌现'''：在复杂系统中，这种聚合可能导致宏观层面出现新的因果特性（即涌现）。如果聚合后的宏观状态能产生比单个状态更明确、更强大的因果作用，则称为因果涌现。此时，宏观状态的马尔科夫转移模型可以更有效地预测系统行为。
但也有其他的划分问题不需遵从这类限制。比如在学术网络、网页流网络的场景上的模式识别时，我们可能会判断某些从未合作过的学者具有相似的行为模式，而把他们划分在一组内。
但也有其他的划分问题不需遵从这类限制。比如在学术网络、网页流网络的场景上的模式识别时，我们可能会判断某些从未合作过的学者具有相似的行为模式，而把他们划分在一组内。
=聚合方法=
=聚合方法=
当我们决定了最优划分之后，就能根据该划分得到聚合后的矩阵。
假设划分是把若干个状态合成一组，而其他状态各自成组，我们要做的是把原矩阵中待聚合状态对应的若干行和若干列，分别聚合成一行和一列，而其他元素保持不动。
[[文件:矩阵聚合.png|500像素]]
[[文件:矩阵聚合.png|500像素]]
把一个 <math>N \times N</math>的矩阵聚合成 <math>N' \times N'</math>的矩阵 可以分成两步：
把一个 <math>N \times N</math> 的矩阵聚合成 <math>N' \times N'</math> 的矩阵，可以分成两步：
# 把待聚合的列直接进行相加，得到 <math>N \times N'</math> 的矩阵；
# 把待聚合的列直接进行相加，得到 <math>N \times N'</math> 的矩阵；
# 把待聚合的行进行加权平均，得到 <math>N \times N</math> 的矩阵
# 把待聚合的行进行加权平均，得到 <math>N' \times N'</math> 的矩阵。
==入流的聚合方法：直接加和==
==入流的聚合方法：直接加和==
我们可以把马尔科夫链看作一个以状态为节点、以转移概率为边的网络。
我们把待聚合节点都放进一个大节点的框 <math>M</math> 里，会发现每个外面的节点转移进大节点的概率就等于转移进 <math>M</math> 中所有节点的概率的和，即<math>p_{iM} = \sum_{j \in M} p_{ij}</math>。如此就能满足每行加和为一的条件。
我们把待聚合节点都放进一个大节点的框 <math>M</math> 里，会发现每个外面的节点转移进大节点的概率就等于转移进 <math>M</math> 中所有节点的概率的和，即<math>p_{iM} = \sum_{j \in M} p_{ij}</math>。如此就能满足每行加和为一的条件。
==出流的聚合方法：加权平均==
==出流的聚合方法：加权平均==
计算大节点的入流比较简单，而计算大节点的出流则相对复杂，需要考虑待聚合节点之间的随机游走和状态分布，来计算流向每个节点的概率。我们可以把出流聚合看作对若干行做线性加权平均。
===权重一致的平均===
===权重一致的平均===
在现有方法中，很多都采用最简单的思路：对状态做权重一致的平均。当我们只看矩阵本身，认为所有状态是平等的，就会给它们分配相同权重，即<math>p_{Mi} = \frac{1}{n} \sum_{j \in M} p_{ji}</math>。
但是，这种情况只适用于成块的状态划分：由于成块性要求同属一组的微观状态转移到另一组的概率相同，所以这样的平权平均没有问题。但当我们对不成块的状态划分进行平权平均时，就会导致宏观和微观的马尔科夫动力学不一致。
===权重为平稳分布的平均===
===权重为平稳分布的平均===
当一个随机游走粒子进入大节点时，它下一步游走到大节点内或大节点外其他节点的概率，应当取决于它当前更可能位于大节点内的哪个小节点。
设游走粒子在 <math>t</math> 时刻处于小节点 <math>j</math> 的概率为<math>s_j(t)</math>，其下一步游走到其他粒子的概率应为<math>p_{Mj}(t) = \frac{1}{\sum_{j \in M} s_j(t)} \sum_{j \in M} s_j(t)\ p_{ji}</math> 。
设游走粒子在 <math>t</math> 时刻处于小节点 <math>j</math> 的概率为<math>s_j(t)</math>，则聚合节点到外部节点 <math>i</math> 的下一步概率可写为<math>p_{Mi}(t) = \frac{1}{\sum_{j \in M} s_j(t)} \sum_{j \in M} s_j(t)\ p_{ji}</math>，而留在聚合节点内部的概率为<math>p_{MM}(t) = \frac{1}{\sum_{j \in M} s_j(t)} \sum_{j \in M} s_j(t)\sum_{k \in M} p_{jk}</math>。
假设游走已经达到平稳分布<math>\pi</math>，游走粒子处于不同小节点 <math>j</math> 的概率为<math>\pi_j</math>，则聚合节点到外部节点 <math>i</math> 的概率为<math>p_{Mi} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j\ p_{ji}</math>，而留在聚合节点内部的概率为<math>p_{MM} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j\sum_{k \in M} p_{jk}</math>。按照平稳分布为权重对若干行做加权平均，得到的行仍会满足加和为一的条件。
其中，<math>F'</math> 是粗粒化后的平稳流矩阵。在归并的过程中，保持所有矩阵上的流量总量是不变的。
其中，<math>F'</math> 是粗粒化后的平稳流矩阵。在归并的过程中，保持所有矩阵上的流量总量是不变的。
最后，粗粒化后的 <math>P'</math> 可直接通过归一化每一行得到：
最后，粗粒化后的 <math>P'</math> 可以通过归一化每一行直接得到：
<blockquote>
<blockquote>
<math>P'_i = \frac{F'_i}{ \sum_{j=1}^{N} (F'_i)_j }, \, \forall i \in [1, N].
<math>P'_i = \frac{F'_i}{ \sum_{j=1}^{N'} (F'_i)_j }, \, \forall i \in [1, N'].
</math>
</math>
</blockquote>
</blockquote>
将 <math>N</math> 个 <math>P'_i</math> 拼在一起就能得到最终的 <math>P'</math> 。可以证明，这样的粗粒化方案可以保证让粗粒化操作和时间演化操作具有可交换的性质（证明可以参考<ref name="reversibility"/>）。
将 <math>N'</math> 个 <math>P'_i</math> 拼在一起就能得到最终的 <math>P'</math>。可以证明，这样的粗粒化方案能够保证粗粒化操作和时间演化操作具有可交换性（证明可以参考<ref name="reversibility"/>）。
按照该方法进行加和平均，得到的宏观和微观马尔科夫动力学就会满足一致条件。虽然这个方法直观明了，但它的问题在于：在系统演变到平稳分布之前，需要计算每个 <math>t</math> 时刻的状态分布概率 <math>s_j(t)</math>。在达到平稳分布前，直接使用<math>\pi</math>来聚合仍不会满足一致性，因此操作起来比较麻烦；而 HOM 的计算方式则可以解决这个问题。
===高阶网络聚类 Higher-Order Macronodes (HOM)===
===高阶网络聚类 Higher-Order Macronodes (HOM)===
在 Klein 等人的论文<ref name=":19">Klein B, Hoel E. The emergence of informative higher scales in complex networks[J]. Complexity, 2020, 20201-12.</ref>，以及 Griebenow 等人<ref name=":Griebenow">Griebenow R, Klein B, Hoel E. Finding the right scale of a network: efficient identification of causal emergence through spectral clustering[J]. arXiv preprint arXiv:190807565, 2019.</ref>的文献中，作者采用了高阶依赖项建模（[[HOMs]]）<ref name="HOMs">Xu, J., Wickramarathne, T. L., & Chawla, N. V. Representing higher-order dependencies in networks[J]. Science advances, 2016, 2(5), e1600028.</ref>来对网络节点进行聚合。其目的是保证聚合后的宏观网络与原始微观网络具有相同的随机游走动力学特性。该方法也可以用于合并马尔科夫链的状态。
Higher-order Macronodes，是由Jian Xu等人<ref name="HOMs" />提出，根据给定的微观马尔科夫链和节点划分方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。下面将简单介绍构建宏观 HOM 转移概率矩阵的计算方法。具体方法请参考[[网络归并]]。
Higher-order Macronodes 是由 Jian Xu 等人<ref name="HOMs" />提出的一种方法：根据给定的微观马尔科夫链和节点划分方案，得出一个与微观转移矩阵保持一致的宏观转移矩阵。下面将简单介绍构建宏观 HOM 转移概率矩阵的计算方法。具体方法请参考[[网络归并]]。
假设我们把若干个节点视为待合并的节点<math>A</math>。
假设我们把若干个节点视为待合并的节点<math>A</math>。
[[文件:HOM示例.png|缩略图|图7：HOM节点边权合并示意图|替代=|500像素|无]]
[[文件:HOM示例.png|缩略图|图7：HOM节点边权合并示意图|替代=|500像素|无]]
论文<ref name=":19" />中提到，原始的微观动力学和使用该方法聚合后的宏观动力学和能满足其定义的一致性。
论文<ref name=":19" />中提到，原始微观动力学与使用该方法聚合后的宏观动力学能够满足其定义的一致性。
<br/>
<br/>
=复杂网络中的粗粒化方法=
=复杂网络中的粗粒化方法=
复杂网络与马尔科夫链之间存在密不可分的联系。许多复杂网络上的分析方法，比如随机游走，会利用马尔科夫链动力学理论；而马尔科夫链的研究同样也会借用复杂网络中的理论分析方法，比如统计物理中的配分函数等。这部分简要介绍复杂网络中的三种粗粒化方法，它们在马尔科夫链粗粒化问题上具有很大的研究潜力。
==复杂网络与马尔科夫链的相似性==
==复杂网络与马尔科夫链的相似性==
对一个复杂网络而言，它并不天然具备某种动力学，所以需要人为定义一套动力学。常见做法是借助随机游走子的概念，在网络上定义一套随机游走动力学。
假设游走子在每一步都会按照边权来进行转移，这种节点间的转移动力学可以用马尔科夫链表示。马尔科夫链的状态对应着复杂网络上的节点，而转移概率对应着网络节点之间的连边权重。
假设游走子在每一步都会按照边权来进行转移，这种节点间的转移动力学可以用马尔科夫链表示。马尔科夫链的状态对应着复杂网络上的节点，而转移概率对应着网络节点之间的连边权重。
===谱粗粒化===
===谱粗粒化===
复杂网络可以被建模为一个马尔科夫过程，它的动力学由邻接矩阵 <math>A</math> 构建的随机矩阵 <math>W</math>（或称转移概率矩阵）所描述，定义为 <math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math> 表示从节点 <math>j</math> 转移到节点 <math>i</math> 的概率。为实现网络的降维与简化，研究一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。该方法的核心在于选取随机矩阵前 <math>S</math> 个最大非平凡特征向值 <math>\lambda^2, \lambda^3, \ldots, \lambda^{S+1}</math> 对应的左特征向量 <math>\langle u^2 |, \langle u^3 |, \ldots, \langle u^{S+1} |</math>，将网络节点映射到该特征向量张成的特征空间。在此基础上，将每个特征向量的值域划分为 <math>I</math> 个区间，在所有 <math>S</math> 个特征向量均落入相同区间的节点合并为一个超级节点。从概率角度可以对此粗粒化过程可以解释为，将新超级节点的出边概率为原节点的出边概率的加权平均，其流入概率为原节点的流入概率相加，其他没有合并节点的转移概率保持不变。
复杂网络可以被建模为一个马尔科夫过程，它的动力学由邻接矩阵 <math>A</math> 构建的随机矩阵 <math>W</math>（或称转移概率矩阵）所描述，定义为 <math>W_{ij} = \frac{A_{ij}}{\sum_k A_{kj}}</math>，表示从节点 <math>j</math> 转移到节点 <math>i</math> 的概率。这里采用的是'''列归一化写法'''：每一列的和为 1，因此指标 <math>j</math> 表示出发节点，<math>i</math> 表示到达节点。为了实现网络的降维与简化，研究者提出了一种基于谱理论的粗粒化方法<ref>Gfeller D, De Los Rios P. Spectral coarse graining of complex networks[J]. Physical review letters, 2007, 99(3): 038701.</ref>。该方法的核心在于选取随机矩阵前 <math>S</math> 个最大非平凡特征值 <math>\lambda^2, \lambda^3, \ldots, \lambda^{S+1}</math> 对应的左特征向量 <math>\langle u^2 |, \langle u^3 |, \ldots, \langle u^{S+1} |</math>，将网络节点映射到这些特征向量张成的特征空间。在此基础上，将每个特征向量的值域划分为 <math>I</math> 个区间，在所有 <math>S</math> 个特征向量上都落入相同区间的节点会被合并为一个超级节点。从概率角度看，这一粗粒化过程可以理解为：新超级节点的出边概率由原节点的出边概率加权平均得到，其流入概率则由原节点的流入概率直接相加，其他未合并节点的转移概率保持不变。
<br/>
<br/>
定义粗粒化单元（CGU）：它是最适合作为网络粗粒化节点的模式，具有明确输入、输出端口和内部计算节点，可视为一种基本电路组件。CGU 的集合构成“元素字典”，粗粒化网络则可视为由该字典构建的版本。部分节点被 CGU 替换，从而实现网络压缩。
CGU的评价维度（优化的属性）：'''简洁性'''、'''简单性'''和'''覆盖度'''。
CGU的评价维度（优化的属性）：'''简洁性'''、'''简单性'''和'''覆盖度'''。
#'''简洁性'''：字典中CGU的总数尽可能的少。
#'''简洁性'''：字典中 CGU 的总数尽可能少。
#'''简单性'''：单个CGU的结构尽简单，由黑箱数 <math>H</math> 决定，<math>H</math> 越少越简单。 <math>H=I+O+2M</math>， <math>I</math> 为输入节点，<math>O</math> 为输出节点，<math>M</math> 为混合节点。
#'''简单性'''：单个 CGU 的结构尽可能简单，由黑箱数 <math>H</math> 决定，<math>H</math> 越少越简单。 <math>H=I+O+2M</math>， <math>I</math> 为输入节点，<math>O</math> 为输出节点，<math>M</math> 为混合节点。
#'''覆盖度'''：粗粒化后消除的节点和边数尽可能多，被CGU覆盖的节点数 <math>P_{covered}</math> 和边数 <math>E_{covered}</math> 尽可能多。
#'''覆盖度'''：粗粒化后消除的节点和边数尽可能多，被CGU覆盖的节点数 <math>P_{covered}</math> 和边数 <math>E_{covered}</math> 尽可能多。
最大化 S 倾向于选择“高频出现、内部节点多且混合节点少” 的 CGU。
最大化 S 倾向于选择“高频出现、内部节点多且混合节点少” 的 CGU。
采用模拟退火法寻找粗粒化最优的 CGU 集合，仅以网络模体（在原始网络中出现频率显著高于随机网络的子图）作为候选 CGU。
候选CGU的获取方式：先检测 3-6 节点的所有网络模体，再根据每个模体出现的连接特征向量，同一模体不同特征向量的出现视为不同 CGU 候选。
候选CGU的获取方式：先检测 3-6 节点的所有网络模体，再根据每个模体出现的连接特征向量，同一模体不同特征向量的出现视为不同 CGU 候选。
找到最优的粗粒化CGU集合，通过将每个CGU的每一次出现替换为一个节点，形成粗粒化网络。算法可在粗粒化网络上重复执行，获得更高层级的粗粒化。
找到最优的粗粒化CGU集合，通过将每个CGU的每一次出现替换为一个节点，形成粗粒化网络。算法可在粗粒化网络上重复执行，获得更高层级的粗粒化。
<references />
<references />