计算力学
计算力学（Computational Mechanics）是一套用于量化涌现的框架。它以一种计算的视角，研究观察者建立的模型在识别涌现时，模型发生的变化。计算力学以信息论和生物进化的思想为基础，是目前最早的对涌现的定量化研究。在应用当中，该理论提出了对复杂性度量的新指标，即计算复杂度，同时还提出了一套识别涌现的算法。
历史渊源
计算力学源于 20 世纪 70 年代和 80 年代早期非线性物理学领域对流体力学领域湍流问题的研究。为了识别流体湍流中的混沌动力学，Packard和 Crutchfield等人开发了一套吸引子重构方法[1][2]，使用测量的时间序列来重构流体动力系统的状态空间，可以在其中观察混沌吸引子并定量测量它们的不稳定程度及其伴随的复杂性。这套重构方法的有效性在 1983 年通过实验得到了验证[3]，之后就被广泛用于识别和量化确定性混沌系统的行为。但是，这套方法无法简明扼要地表达被重构系统的内部结构。为了解决这个问题，计算力学理论应运而生。
计算力学的首次提出是在1989年，Crutchfield的一篇论文[4]中，它基于时间序列重构的状态空间[1] 和自动机理论[5][6][7]定义了一种预测等价关系。利用这种关系分析时间序列数据，识别和量化其中有规律的部分，计算力学就可以构建一个能够预测系统未来行为的模型。
计算力学的核心概念是因果态（Causal State），它是一种与微观状态预测等价的特殊的宏观态。基于这种预测等价性的宏观态划分思想可以追溯到70年代的马尔科夫链上的成块性（Lumpability）理论。Kemeny, Snell在1969年针对马尔科夫动力学系统提出成块性这一概念，目的在于判断一个马尔科夫动力系统是否是可被归并的。对于任意一个马尔科夫链，我们可以判断某种划分是否是成块的。可成块的划分要求对状态的归并要尽可能地保留马尔可夫链中的重要信息，并保证划分操作与动力学的可交换性。不过在马尔科夫链中，成块儿性只是对于划分的一种要求，而没有追求最优的划分。对成块性的进一步的了解，请参考词条马尔科夫链的粗粒化。与之相比，计算力学首先关注的不只是马尔科夫动力学，而是要囊括更广泛的动力学形式。此外，计算力学试图提出一种最优的划分，能极大地保留对预测有用的信息。此外，当一般的动力学过程退化到马尔科夫动力学的时候，成块性的成立条件实际上与因果态的定义是一致的。
问题背景
自然和社会现象中的涌现
有一些自然和社会现象非常引人入胜，但也很令人困惑，比如行为简单的蚂蚁可以形成复杂的社会，在没有控制中心的情况下自发产生特异化的社会分工[8]。 在没有领导者引导的情况下成群的鸟以步调一致的队形飞行，成群的鱼以连贯的阵列游动，突然一起转向[9]。经济中商品的最佳定价似乎源于主体遵守当地的商业规则[10]。这些现象中的全局协调是如何出现的？是否有共同的机制引导着这些不同现象的出现？在复杂系统理论中把这类许多独立子系统相互作用后产生高度结构化的集体行为的现象称作涌现。
目前对涌现的研究理论有基于有效信息的因果涌现理论、基于信息分解的因果涌现理论、基于可逆性的因果涌现理论，基于转移熵的动力学解耦理论[11]、基于格兰杰因果的G-emergence理论[12]等等。计算力学是基于统计复杂度对涌现的定量化研究理论，它提出的时间最早，虽然对涌现的的研究方法与上述理论均不同，但有很多研究思路是相似的，它定义的统计复杂度、因果态、斑图重构机器等概念对涌现的研究有很大启发和借鉴意义。
计算力学中的涌现
我们直觉中对涌现的定义就是系统出现了新的特征，但是该定义并没有说明“新特征”是什么，以及它“新”在哪里。所以还需要更精确的语言对涌现的概念进行描述。涌现通常被理解为一个过程，该过程所产生的结构并不能直接由控制系统的定义所约束以及被瞬时力所描述。比如一堆随机运动的粒子，虽然它们受到的瞬时力可以用运动方程描述，但是从宏观尺度上却会表现出诸如压强、体积以及温度等新特征。我们需要引入斑图的概念来明确说明什么是新特征，否则涌现这一概念几乎没有内容，因为几乎任何时间依赖的系统都会表现出涌现特征。
在计算力学中[13]，斑图通常指的是从时间序列中总结出的规律性结构。实际上，检测到的斑图通常是通过观察者选择的统计数据来隐含假定的，可能某些斑图的功能表现与其数学模型一致，但这些模型本身依赖于一系列理论假设。简而言之，斑图通常是被猜测出来的，观察者通过固定的规律库来预测这些结构，然后再进行验证。可以用通信频道做一个类比，观察者就像是一个已经手握密码本的接收者，任何未能通过密码本解码的信号本质上都是噪声，即观察者未能识别的斑图。
在系统内部的协调行为中，有一种斑图变得尤为重要，这种斑图会相对于该系统的其他结构显现其“新颖性”。由于没有外部的参照来定义这种新颖性，我们可以将这个过程称为内在涌现（Intrinsic Emergence）。比如在高效的资本市场中，主体根据从集体行为中涌现出的最优定价，控制其个人生产-投资和股票所有权策略[10]。对于主体的资源配置决策而言，通过市场的集体行为涌现出的价格是准确的信号，完全反映了所有可用信息，这一点至关重要。内在涌现的独特之处在于形成的斑图赋予了系统额外的功能性，支持全局信息处理，如设定最优价格。更具体地说，内在涌现可以直接嵌入系统非线性计算过程之中，能够被系统直接利用，这样就赋予了系统额外的功能性。
总而言之，计算力学区分了三个概念：
- 对涌现的直觉定义：系统中出现任何可以被称为新颖的特征。
- 斑图涌现（Pattern Formation）：观察者在系统中识别出的有规律的结构。
- 内在涌现（Intrinsic Emergence）：系统本身捕捉并利用它自身出现的斑图。
进化的系统模型
我们可以用生物进化的思想来阐述内在涌现的问题[13]，从而解释一个高度有序的系统是怎么从混沌中涌现的，但是它在解释生命形式的多样性方面依然预测能力有限。因此要将系统限制在一个结构和生物特征明确的确定性动力系统（Deterministic Dynamical Systems，简称DS）中，并把它简化为包括一个环境和一组适应性的观察者或“智能体”的模型，这样才能清晰地定义智能体的性质。智能体（Agent）试图构建和维持一个对其环境具有最大预测能力的内部模型。每个智能体的环境是其他智能体的集合，可以视为一个随机动力系统（Stochastic Dynamical Systems，简称SDS）。在任何给定的时刻，智能体感知到的是当前环境状态的投影。随着时间的推移，感官装置产生一系列测量，这些测量引导智能体利用其可用资源（下图中的“基层”）来构建环境模型。基于环境模型捕捉到的规律，智能体通过效应器采取行动，最终改变环境状态。
上图为以智能体为中心的环境视图：宇宙可以被视为一个确定性动力系统，即使规则和初始条件是确定的，随着规模的增长，系统也会变得极为复杂。每个智能体所看到的环境是一个由所有其他智能体组成的随机动力系统。其随机性源于其内在的随机性和有限的计算资源。每个智能体本身也是一个随机动力系统，因为它可能会从其基层和环境刺激中采样或受到无法控制的随机性所困扰。基层代表了支持和限制信息处理、模型构建和决策的可用资源。箭头表示信息流入和流出智能体的方向。
智能体面临的基本问题是基于对环境状态的建模和对未来环境的预测。这需要一个量化的理论来描述智能体如何处理信息和构建模型。
因果态和复杂度
智能体需要一种有效的描述方式处理接受到的环境信息，使其可以把环境信息压缩成一个有限的状态空间，并存储于内部环境模型中。为了找到这种有效的描述方式，我们首先需要定义所谓的状态的概念，状态可以理解为智能体所接收到的全部信息历史。之后，我们将引入"因果态"的概念，它相当于是对状态的一种粗粒化描述。
状态的定义
智能体对环境的测量精度一般都是有限的，测量结果只能描述环境状态的投影。我们可以将环境从过去到未来的变化用一个离散的稳定随机过程描述，状态的取值空间则为双无限序列可数集合[math]\displaystyle{ \overleftrightarrow{S}=\cdots s_{-2} s_{-1} s_0 s_1 s_2\cdots }[/math]，也就是说，一个状态指的是一个无限长的时间序列。
基于当前的时刻[math]\displaystyle{ t }[/math]，我们可以将[math]\displaystyle{ \overleftrightarrow{S} }[/math]分为单侧前向序列[math]\displaystyle{ \overrightarrow{s_t}=s_t s_{t+1} s_{t+2} s_{t+3}\cdots }[/math]和单侧后向序列[math]\displaystyle{ \overleftarrow{s_t}=\cdots s_{t-3} s_{t-2} s_{t-1} }[/math]两个部分，所有可能的未来序列[math]\displaystyle{ \overrightarrow{s_t} }[/math]形成的集合记作[math]\displaystyle{ \overrightarrow{S} }[/math]，所有可能的历史序列[math]\displaystyle{ \overleftarrow{s_t} }[/math]形成的集合记作[math]\displaystyle{ \overleftarrow{S} }[/math]。某一个时刻的状态指的是截止到当前时刻的历史序列。
然后我们将定义一个叫做“因果态”的概念。
因果态的定义
划分
通过对状态空间进行划分（partition），智能体可以用一种更加粗糙的方式来描述同样的状态，这一过程也被人们叫做粗粒化。划分可以被理解为一种映射，[math]\displaystyle{ \eta{:}\overleftarrow{S}\mapsto\mathcal{R} }[/math]，其中[math]\displaystyle{ \mathcal{R} }[/math]是状态空间的子集的集合，要满足其元素彼此互斥，而且所有元素的并集等于[math]\displaystyle{ \overset{\leftarrow}{S} }[/math]的条件。通过划分映射，智能体可以得到的子集都可以被视为对应着一个宏观态。
上图为某种划分的示意图[14]，将集合[math]\displaystyle{ \overset{\leftarrow}{S} }[/math]划分为某类宏观态的子集[math]\displaystyle{ \mathcal{R}=\{\mathcal{R}_i:i=1,2,3,4\} }[/math]，值得注意的是，[math]\displaystyle{ \mathcal{R}_i }[/math]不必形成紧致集，也可以是康托集或其他更特殊的结构，上图为了示意清楚才这样画的。
于是，智能体就需要学习到一种有效的划分，即如何从观测到的状态（可以称之为微观态）到智能体压缩后得到的隐空间上的状态（可以称为宏观态）能够很好对应，使得宏观态更加有效地反映微观态中的重要信息。那么，什么叫做有效呢？
因果态
对于集合[math]\displaystyle{ \overset{\leftarrow}{S} }[/math]的划分可以有很多种，若某一种划分能够在预测能力最强的同时又非常简洁，那么它肯定是最优的划分，我们把这种用最优的划分方法得到的宏观态称为因果态。因果态就是智能体对测量结果进行处理后，根据其内部模型（尤其是状态结构）识别出的斑图，并且这种斑图不随时间发生变化。形式化定义为：对于任意的时刻[math]\displaystyle{ t }[/math] 和[math]\displaystyle{ t^{'} }[/math]，给定过去状态[math]\displaystyle{ \overleftarrow{s_t} }[/math]的条件下，未来状态[math]\displaystyle{ \overrightarrow{s} }[/math]的分布与给定过去状态[math]\displaystyle{ \overleftarrow{s_{t^{'}}} }[/math]的条件下，未来状态[math]\displaystyle{ \overrightarrow{s} }[/math]的分布相同。那么[math]\displaystyle{ t }[/math] 和[math]\displaystyle{ t^{'} }[/math]的关系就记作[math]\displaystyle{ t\sim t^{'} }[/math]，“[math]\displaystyle{ ∼ }[/math] ” 表示由等效未来状态所引起的等价关系，也叫预测等价性（predictive equivalence），可以用公式表示为：[math]\displaystyle{ t\sim t^{'} \triangleq Pr(\overrightarrow{s}|\overleftarrow{s_t} )=Pr(\overrightarrow{s} |\overleftarrow{s_{t^{'}}} ) }[/math]，若[math]\displaystyle{ t }[/math] 和[math]\displaystyle{ t^{'} }[/math]对未来状态预测的分布相同，则定义它们具有相同的因果态（casual state）。
因果态的划分映射可以记作[math]\displaystyle{ \epsilon }[/math]，公式为[math]\displaystyle{ \epsilon{:}\overleftarrow{S}\mapsto2^{\overset{\leftarrow}{S}} }[/math]，其中[math]\displaystyle{ 2^{\overset{\leftarrow}{S}} }[/math]是[math]\displaystyle{ \overleftarrow{S} }[/math]的幂集。根据因果态的定义，则存在如下关系：[math]\displaystyle{ { \epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\overrightarrow{S}=\overrightarrow{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\overrightarrow{S}=\overrightarrow{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime})，\mathrm{for~all~}\overrightarrow{s}\in\overrightarrow{S},\stackrel{\leftarrow}{s}^{\prime}\in\stackrel{\leftarrow}{S}\} } }[/math]，其中[math]\displaystyle{ \mathcal{S} }[/math]为因果态的集合，[math]\displaystyle{ \stackrel{\leftarrow}{s} }[/math]为历史序列的随机变量。
如上图所示[13]，左侧的数字代表[math]\displaystyle{ t }[/math]时刻的状态序列，右侧的箭头形状代表对未来状态预测的分布，可以观察到[math]\displaystyle{ t_9 }[/math]和[math]\displaystyle{ t_{13} }[/math]时刻的箭头形状完全相同，说明它们对未来状态预测的分布相同，则处于相同的因果态；同样的道理，在[math]\displaystyle{ t_{11} }[/math]时刻，它的箭头形状与[math]\displaystyle{ t_9 }[/math]和[math]\displaystyle{ t_{13} }[/math]时刻不同，则处于不同的因果态。
预测等价性（predictive equivalence）是计算内在涌现（简称内在计算，intrinsic computation）的核心思想[15]，即系统的历史能够用来预测其未来行为的程度。通过构建预测模型，内在计算能够识别系统中的结构，并量化这些结构的复杂性和稳定性。它可以让我们能够将自组织视为系统中规律性和规则性的涌现，而这些规律性和规则性是系统在特定的初始条件和外部驱动下自发形成的。内在计算的一个重要应用是在理解从完全规则到完全无序之间的组织结构。比如，木星的大红斑是一个经典的自组织现象，其规模和稳定性无法通过简单的流体力学方程直接解释。然而，内在计算能够通过分析该现象的历史数据，构建出一个能够准确预测其未来行为的模型，从而揭示出其背后的自组织机制。
因果态的主要性质
为什么我们要关注因果态这样一种特定的宏观态呢？下面是因果态的两个主要性质，其体现出因果态是一种最理想的宏观态：
性质1（因果态具有最大预测性）：对于宏观态[math]\displaystyle{ \mathcal{∀R} }[/math]和正整数[math]\displaystyle{ L }[/math]，都有[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{R}]\geq H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] }[/math]，[math]\displaystyle{ \stackrel{\rightarrow}{S}^L }[/math]为长度为[math]\displaystyle{ L }[/math]的未来序列集合，所有可能的历史序列记作[math]\displaystyle{ \overleftarrow{S} }[/math]。[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{R}] }[/math]和[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] }[/math]是[math]\displaystyle{ \stackrel{\rightarrow}{S}^L }[/math]的条件熵。可以理解为因果态集合[math]\displaystyle{ \mathcal{S} }[/math]在所有的划分宏观态集合[math]\displaystyle{ \mathcal{R} }[/math]中，它的预测能力最强，证明过程如下：
根据因果态的定义可知：[math]\displaystyle{ \epsilon(\stackrel{\leftarrow}{s})\equiv\{\stackrel{\leftarrow}{s}^{\prime}|\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s})=\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}^{\prime})\} }[/math]
上式等价于[math]\displaystyle{ \mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s} |\mathcal{S}=\epsilon(\stackrel{\leftarrow}{s}))=\mathrm{P}(\stackrel{\rightarrow}{S}=\stackrel{\rightarrow}{s}\mid\stackrel{\leftarrow}{S}=\stackrel{\leftarrow}{s}) }[/math]
因为[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{S}]~=~H[\stackrel{\rightarrow}{S}^L|~\stackrel{\leftarrow}{S}] }[/math]，且[math]\displaystyle{ H[\stackrel{\to}{S}^L|\mathcal{R}] \geq H[\stackrel{\to}{S}^L|\stackrel{\leftarrow}{S}] }[/math]
所以[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{R}]\geq H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] }[/math]
性质2（因果态具有最小随机性）：设[math]\displaystyle{ \hat{\mathcal{R}} }[/math]和[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]为满足性质1中不等式等号成立的宏观态，则对于所有的[math]\displaystyle{ \hat{\mathcal{R}} }[/math]和[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]，都有[math]\displaystyle{ H[\hat{\mathcal{R}}^{\prime}|\hat{\mathcal{R}}]\geq H[\mathcal{S}^{\prime}|\mathcal{S}] }[/math]，其中[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]和[math]\displaystyle{ \mathcal{S}^{\prime} }[/math]分别是该过程的下一时刻状态和下一时刻因果态。可以理解为在相同预测能力的前提下，因果态集合[math]\displaystyle{ \mathcal{S} }[/math]在宏观态集合[math]\displaystyle{ \mathcal{R} }[/math]的所有类型中，它的随机性最小。
用互信息的角度去理解的话，上式等价于[math]\displaystyle{ I(\mathcal{S}^{\prime};\mathcal{S})\geq I(\hat{\mathcal{R}}^{\prime};\hat{\mathcal{R}}) }[/math]，可以理解为任意宏观态对它自己下一时刻的互信息中，其中因果态的互信息最大。
若想更深入的理解因果态的性质可以阅读Cosma Rohilla Shalizi 和James Crutchfield合写的一篇论文[14]，里面有因果态更多的性质和对应的形式化证明过程。
斑图重构机器
前面给出了因果态的定义，接下来讨论一个智能体是如何从观测到的时间序列数据中，自动地发现因果态的问题。为了解决这个问题，计算力学建立了名为斑图重构机器（ϵ-machine）的模型，其中因果态所对应的划分映射被记为[math]\displaystyle{ \epsilon }[/math]。它可以重构测量结果中的序列，去除随机噪声后识别其中的因果态。它的形式化定义可以用公式表示为[math]\displaystyle{ M=(\mathcal{S},T) }[/math]，[math]\displaystyle{ \mathcal{S} }[/math]为因果态的集合，[math]\displaystyle{ T }[/math]为状态到状态跳转的集合，它类似于一个粗粒化后的宏观动力学。[math]\displaystyle{ T }[/math]可以表示为[math]\displaystyle{ \{T_{ij}^{(s)}:s\in\mathcal{A}\} }[/math]，其中[math]\displaystyle{ \mathcal{A} }[/math]为可数集。[math]\displaystyle{ T_{ij}^{\left ( s \right )} }[/math]的定义为：
[math]\displaystyle{ T_{ij}^{(s)} \equiv P({S}' = {S}_{j}, \vec{S}^{1} = s | {S} = {S}_{i}) }[/math]
其中： [math]\displaystyle{ {S} }[/math]表示当前因果态。 [math]\displaystyle{ {S}' }[/math]表示下一时刻因果态。 [math]\displaystyle{ \vec{S}^{1} }[/math]代表从历史序列中获取的下一个符号。 [math]\displaystyle{ s }[/math]是从可数集[math]\displaystyle{ \mathcal{A} }[/math]中取值的单个符号，表示过程在某一步产生的输出。 [math]\displaystyle{ {S}_{i} }[/math]和[math]\displaystyle{ {S}_{j} }[/math]分别表示第[math]\displaystyle{ i }[/math]个和第[math]\displaystyle{ j }[/math]个因果态，它们是对历史序列的一种划分。 [math]\displaystyle{ T_{ij}^{(s)} }[/math]表示在当前因果态为[math]\displaystyle{ {S}_{i} }[/math]的条件下，下一个因果态变为[math]\displaystyle{ {S}_{j} }[/math]且过程产生的下一个符号为[math]\displaystyle{ s }[/math]的转移概率。 通过这个公式，可以描述斑图重构机器中因果态之间的转移关系以及与过程输出符号的对应关系，从而刻画了过程的动态行为和内在结构。
每个[math]\displaystyle{ \mathcal{S} }[/math]都对应一个[math]\displaystyle{ \epsilon }[/math]映射，它和[math]\displaystyle{ T }[/math]函数一起组成一个有序对[math]\displaystyle{ \left \{ \epsilon,T \right \} }[/math]。后文“模型的重构”一节中会介绍，智能体的内在模型会根据观测到的新数据，动态更新[math]\displaystyle{ \epsilon }[/math]映射和[math]\displaystyle{ T }[/math]函数。
统计复杂度
智能体在构建和优化斑图重构机器的过程中，由于计算资源的限制，不能无限制地增加模型的大小。因此我们需要一个能够量化模型复杂度的指标，以便监控和调整模型的大小，确保模型能匹配已有的计算资源。柯式复杂度[math]\displaystyle{ K(x) }[/math]，也就是在通用确定性图灵机（Universal Turing Machine，简称UTM）上运行时生成字符串[math]\displaystyle{ x }[/math]的最小程序长度，是人们常用的一个复杂性度量指标。
然而，柯式复杂度存在两个明显的问题，第一个问题是它的不可计算性，柯氏复杂度仅仅是一个理想化的概念；第二个问题是它可能无法度量程序的结构和动态特性。因为柯式复杂度[math]\displaystyle{ K(x) }[/math]需要考虑字符串中的所有比特，这就包括随机生成的比特。因此，柯氏复杂度会在随机生成的比特上计算出较大的复杂性，而这与我们的直觉不符：复杂性不能等价于随机性。
为了解决这两个明显问题，计算力学提出了统计复杂度[math]\displaystyle{ C_μ(x) }[/math]的概念，用来量化模型的复杂性，它可以反映[math]\displaystyle{ x }[/math]的结构和动态特性，以及能够计算出有效建模所需的计算资源。它的公式为：
[math]\displaystyle{ C_{\mu}(x)=\left\|M_{\min }(x \mid \mathrm{BTM})\right\| }[/math]
这里， [math]\displaystyle{ C_{\mu}(x) }[/math]是统计复杂度[4]，表示时间序列[math]\displaystyle{ x }[/math]的复杂性度量。它反映了在给定精度[math]\displaystyle{ \mu }[/math]下，能够生成该序列的最小伯努利图灵机的程序长度。
这里，伯努利图灵机（Bernoulli-Turing machine，简称BTM）是确定性通用图灵机的一种扩展。它通过引入随机数发生器，可以生成离散的随机序列。伯努利图灵机包含输入纸带、输出纸带、有限状态控制单元和工作纸带。在运行过程中，伯努利图灵机按照常规图灵机的方式读取纸带上的符号和自身的当前状态，并依据内置的规则表进行操作。与普通图灵机不同的是，其规则表中有一些与随机相关的规则时，它会根据随机数发生器的采样结果来决定具体的执行路径。例如，在某个状态下，图灵机可能有两种可选的操作，普通图灵机根据确定的规则选择其中一种，而伯努利图灵机则通过随机源（即随机数发生器）以一定的概率来决定执行哪一种操作。
[math]\displaystyle{ M_{\min }(x \mid \mathrm{BTM}) }[/math]代表在能够捕捉数据[math]x[/math]条件下的所有伯努利图灵机中的最小的模型[16]。这个模型是能够有效预测[math]\displaystyle{ x }[/math]的最简单形式，且在该模型中尽量减少其复杂性。[math]\displaystyle{ \left\|⋅\right\| }[/math]这个符号表示对模型复杂度的量化，例如图灵机的指令表长度。
由于内部模型（ϵ-machine）作为一种伯努利图灵机，本身也是用字符串（因果态）来描述，所以可以用长度、香农熵等指标来度量内部模型的复杂度。当我们使用香农熵来刻画内部模型的复杂度时，我们可以给出对于观测序列来说一个等价的可计算的定义[4]：
[math]\displaystyle{ C_\mu(\mathcal{x})\equiv H[\mathcal{S}] }[/math]，
其中[math]\displaystyle{ \mathcal{S} }[/math]为观测数据[math]\displaystyle{ \mathcal{x} }[/math]的因果态集合。
统计复杂度的一个特征是，对于完全随机对象，有[math]\displaystyle{ C_μ(x)=0 }[/math]，如抛硬币产生的序列。同时对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]时，也有[math]\displaystyle{ C_μ(x)=0 }[/math]。因此，统计复杂度的值对于（简单的）周期性过程和完全随机过程都很小。所以，与柯氏复杂度相比，统计复杂度[math]\displaystyle{ C_μ(x) }[/math]剔除了通用图灵机在模拟随机比特时所花费的计算努力。
下图展示了柯式复杂度和统计复杂度随着序列从简单周期性变为完全随机的过程中二者的差异。如图(a)所示，柯式复杂度会随着序列随机性的增加而单调递增。相反，统计复杂度在周期和随机两个极端点上均为零，并在中间达到最大值（见图(b)）。这反映出如下的观点：随机性在统计上是简单的，一个完全随机的过程具有零统计复杂度；周期性在统计上也是简单的，一个完全周期性过程具有较低的统计复杂度。复杂过程在这两个极端之间产生，并且是可预测机制和随机机制的混合，有中等程度随机性的数据具有最大的统计复杂度。
香农熵率
上文中提到的一个序列的随机性可以用香农熵率（Shannon Entropy Rate）来度量，香农熵率是信息论中的一个概念，它是香农熵的扩展，主要用于描述时间序列在单位时间上的平均信息量。在这里，香农熵率可以定义为：
[math]\displaystyle{ h_\mu=\lim_{L\to\infty}\frac{H(\Pr(s^L))}L }[/math]
其中，[math]\displaystyle{ s^L }[/math]是环境信息生成的离散符号序列，[math]\displaystyle{ L }[/math]为序列的长度，[math]\displaystyle{ \Pr(s^L) }[/math]是序列[math]\displaystyle{ s^L }[/math]的边际分布，[math]\displaystyle{ H }[/math]是香农熵。在建模框架中，[math]\displaystyle{ h_μ }[/math]可以解释为智能体在预测序列[math]\displaystyle{ s^L }[/math]的后续符号时的误差率。由该公式可见，熵率也就是自信息的平均值。
香农熵率是归一化的度量信息不确定性程度的指标，信息的不确定性越高，香农熵率越大。对于简单的周期性过程，如[math]\displaystyle{ x=00000000…0 }[/math]，香农熵率为0，对于完全随机的对象，如抛硬币产生的序列，香农熵率为1。香农熵率记作[math]\displaystyle{ h_μ }[/math]，它与柯式复杂度[math]\displaystyle{ K(x) }[/math]的关系为：
[math]\displaystyle{ \frac{K\left(s^{L}\right)}{L}\underset{L\to\infty}{\operatorname*{\operatorname*{\operatorname*{\rightarrow}}}}h_{\mu} , }[/math]
上文中我们介绍了柯式复杂度、统计复杂度和香农熵率这三个与复杂性相关的指标，其实这三者之间存在一个近似关系，可以用公式表示为：
[math]\displaystyle{ K(s^L )≈C_μ (s^L )+h_μ L }[/math]
如果在已确定描述语言（程序）的情况下，柯式复杂度[math]\displaystyle{ K(s^L ) }[/math]可以理解为描述[math]\displaystyle{ s^L }[/math]所用的总信息量。[math]\displaystyle{ h_μ L }[/math]为允许损失的信息量。统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。
模型重构
由于智能体的计算资源是有限的，当测量结果中的数据量超过模型能够处理的极限时，我们就需要对生成序列的原有模型进行重构。这样做的目的是在保持计算资源不变的情况下，确保智能体仍然能够对外界进行有效的预测。进一步，因果态可以被看做是原始状态序列，因此智能体可以在因果态基础上再次重构生成该因果态的模型。于是，这便形成了一系列不断升级的层级化的重构过程。
重构的方法主要是通过寻找原有模型中不同状态组之间的相似性，也就是说，在原有模型已经识别出的因果态中，我们进一步抽象出更高层级的因果态组。这样，随着数据量的增大，我们就可以不断的在上一层级抽象出更高的层级，从而在计算资源有限的情况下，仍然能够应对更大量的数据。譬如，当智能体观测到“121212”时，会把“12”看成是一个模块，用一个字符“A”来表示，于是原本的微观态字符串就可以被重构为“AAA”这样的宏观态字符串，复杂度就降低了。而当模型进一步观测到更长的字符串是“12121231212123”时，它便需要跳出原本的分组，而把“1212123”看成是一个新的模块，可以用一个字符“B”来表示，于是内部模型可以进一步用“BB”这样的新字符串来表示同一个观测对象。这便是一次模型重构不断升级的过程。下表中列举了一种模型重构的可能途径：
上表为因果时间序列建模层级，展示了可能的前四个层级，每个层级根据其模型类别定义。但这个过程仅仅是一个示例，可以不止四个层级。模型本身由状态（圆圈或方块）和转移（标记箭头）组成，每个模型都有一个独特的起始状态，由一个双重圆圈表示。数据流本身是最低层级，通过将序列测量分组为重复子序列，从数据流中构建出深度为[math]\displaystyle{ D }[/math]的树。下一个层级的模型，即具有状态和转移的有限自动机（Finite Automaton，简称FA），可以通过将树节点分组从树中重构。图中所示的最后一个层级，字符串生成机器（Pattern Matching，简称PM），可以通过将有限状态自动机的状态进行分组并推断出操控寄存器中字符串的生成规则来构建。
考虑一个由[math]\displaystyle{ m }[/math]个测量结果构成的数据流[math]\displaystyle{ s }[/math]，如果它是周期性的，那么第0级（Level 0），即测量结果本身，它的表示方法依赖于[math]\displaystyle{ m }[/math]。在极限[math]\displaystyle{ m\to\infty }[/math]情况下，第0级会产生一个复杂度无穷大的表示。当然，第0级是最准确的数据模型，尽管它几乎没有任何帮助，几乎不值得被称为“模型”。相比之下，一个深度为[math]\displaystyle{ D }[/math]的树将给出一个有限表示，即使数据流的长度是无限的，只要数据流具有小于等于[math]\displaystyle{ D }[/math]的周期。这个树有长度为[math]\displaystyle{ D }[/math]的路径，由数据流的周期给出。这些路径中的每一个都对应于[math]\displaystyle{ s }[/math]中重复模式的一个不同阶段。如果[math]\displaystyle{ s }[/math]是非周期性的，那么树模型类将不再是有限的，并且与[math]\displaystyle{ m }[/math]无关。 事实上，如果数据流具有正熵率（[math]\displaystyle{ h_μ＞0 }[/math]），那么树的大小将呈指数增长，[math]\displaystyle{ \approx\left\|\mathcal{A}\right\|^{Dh_{\mu}} }[/math] ，因为[math]\displaystyle{ D }[/math]的增加解释了[math]\displaystyle{ s }[/math] 中长度[math]\displaystyle{ D }[/math]不断增加的子序列。粗略地说，如果数据流具有随时间衰减得足够快的相关性，则下一级（随机）有限自动机将给出有限表示。状态数[math]\displaystyle{ \left\|\mathrm{V}\right\| }[/math]表示数据流中的内存量，因此表示[math]\displaystyle{ s }[/math]中测量值之间存在相关性的典型时间长度。但也有可能第 2 级不提供有限表示。那么就需要另一个级别（第 3 级）。
模型重构算法
上面介绍了斑图重构机器，是智能体识别因果态的一种方式。若结合模型重构的概念，我们可以给出斑图重构机器的完整定义：斑图重构机器（ϵ-machine）是能够用最少的计算资源对测量结果进行有限描述同时复杂度最小的模型。模型重构的算法步骤如下：
1. 在最低水平上，设定0级模型为描述数据本身，即[math]\displaystyle{ M_0=s }[/math]，将初始层级[math]\displaystyle{ l }[/math]设置为比0级高一级，即[math]\displaystyle{ l=1 }[/math]；
2. 从更低模型重构模型[math]\displaystyle{ M_l=M_{l-1}/∼ }[/math]，其中[math]\displaystyle{ ∼ }[/math]表示[math]\displaystyle{ l }[/math]级上的因果等价类；
[math]\displaystyle{ M_l=M_{l-1}/∼ }[/math]的含义是，在[math]\displaystyle{ l-1 }[/math]级上被区别对待的状态在[math]\displaystyle{ l }[/math]级上可以被视为同一个因果态。此时因果态集合[math]\displaystyle{ \mathcal{S} }[/math]和因果态上的转移概率映射集合[math]\displaystyle{ T }[/math]都被更新了；
3. 收集更多的数据，增大序列长度[math]\displaystyle{ L }[/math]，得到更加精确的一系列模型[math]\displaystyle{ M_l }[/math]；
4. 如果随着[math]\displaystyle{ L }[/math]增大，模型的复杂度发散，即[math]\displaystyle{ C_μ(M_l) = \lVert M_l \rVert \underset{L \to 0}{\to} \infty }[/math]，那么回到第二步，得到更高级模型[math]\displaystyle{ M_{l+1} }[/math]；
5. 如果模型复杂度收敛，意味着算法已经重建好了一个合适的斑图重构机器，程序退出。
混沌动力学实例
逻辑斯谛映射
接下来将演示如何将计算力学和模型重构算法应用于一个具体的实际案例[13]。这个案例是混沌动力学中的逻辑斯谛映射(logistic map)，作者特别展示了算法在周期倍增的混沌路径上的表现。用于重建模型的数据流来自逻辑斯谛映射的轨迹，该轨迹是通过迭代映射[math]\displaystyle{ x_{n+1}=f(x_n) }[/math]生成的，迭代函数为[math]\displaystyle{ f(x) = rx(1-x) }[/math]，其中非线性参数[math]\displaystyle{ \begin{matrix}r&\in&[0,4]\end{matrix} }[/math]，初始条件[math]\displaystyle{ x_0\in[0,1] }[/math]，迭代函数的最大值出现在[math]\displaystyle{ x_c = \frac12 }[/math]。
上图为迭代函数[math]\displaystyle{ f(x) = rx(1-x) }[/math]中极限状态[math]\displaystyle{ x }[/math]与参数[math]\displaystyle{ r }[/math]的关系图[13]，当[math]\displaystyle{ r＜3.5699... }[/math]时函数存在倍周期现象，当[math]\displaystyle{ r＞3.5699... }[/math]时会出现混沌现象。由于观察者观测的精细程度有限，若要识别混沌中的有序结构，就需要对[math]\displaystyle{ x }[/math]进行粗粒化操作，方法是通过二元分割观察轨迹[math]\displaystyle{ \mathbf{x}=x_0x_1x_2x_3\ldots }[/math] ，将其转换为离散序列[math]\displaystyle{ \mathcal{P}=\{x_n\in[0,x_c)\Rightarrow s=0,x_n\in[x_c,1]\Rightarrow s=1\} }[/math]，这种划分是“生成”的，这意味着足够长的二进制序列来自任意小的初始条件间隔。因此，可以使用粗粒化的观测[math]\displaystyle{ \mathcal{P} }[/math]来研究逻辑斯谛映射中的信息处理。
统计复杂度-熵率图
上图（a）为逻辑斯谛映射中统计复杂度[math]\displaystyle{ C_μ }[/math]与香农熵率[math]\displaystyle{ H(L)/L }[/math]的关系[13]，三角形表示[math]\displaystyle{ (C_μ ,H(L)/L) }[/math]的大概位置，对应非线性参数[math]\displaystyle{ r }[/math]的 193 个取值，其中子序列长度[math]\displaystyle{ L=16 }[/math]，覆盖部分实验数据的粗实线是[math]\displaystyle{ C_μ =0 }[/math]时对[math]\displaystyle{ H(L)/L }[/math]得出的解析解曲线。
本图表现了两个重要特征。第一个特征是熵率的极值导致零复杂度，也就是说在[math]\displaystyle{ H(L)/L=0 }[/math]处最简单的周期过程和在[math]\displaystyle{ H(L)/L=1 }[/math]处最随机的过程在统计复杂性上看都是简单的，它们都具有零复杂度，因为它们是由具有单一状态的斑图重构机器描述的；第二个特征是在两个极端情况之间，复杂度明显升高，并在临界熵率值[math]\displaystyle{ H_c }[/math]附近出现明显峰值（此处[math]\displaystyle{ r=3.5699... }[/math]）。[math]\displaystyle{ r_c=3.5699... }[/math]刚好是逻辑斯蒂映射的临界相变点，当[math]r<r_c[/math]时，模型处于周期行为；当[math]r>r_c[/math]时，模型进入混沌行为区域。因此，当熵率[math]\displaystyle{ H(L)/L \lt H_c }[/math]时，此时的数据集是由呈周期性（包括在混沌区域也呈周期性的参数）变化的参数下产生，大于[math]\displaystyle{ H_c }[/math]时数据集由混沌的参数下产生。本图可以对照统计复杂度小节中的图（b）一起理解。
上图（b）为逻辑斯谛映射中在[math]\displaystyle{ H_c }[/math]（[math]\displaystyle{ r=3.5699... }[/math]）处，[math]\displaystyle{ L }[/math]与宏观态数量[math]\displaystyle{ \left|\mathbf{V}\right| }[/math]的关系，序列的长度[math]\displaystyle{ L=64 }[/math]时，[math]\displaystyle{ \left|\mathbf{V}\right|=196 }[/math]，从图中可以看出，随着[math]\displaystyle{ L }[/math]的增长，[math]\displaystyle{ \left|\mathbf{V}\right| }[/math]的值是发散的，若要用有限的[math]\displaystyle{ L }[/math]来描述[math]\displaystyle{ \left|\mathbf{V}\right| }[/math]，就需要将模型进行重构，升级为描述能力更强的模型。
模型升级
下面三张图[13]展示了模型重构升级进化的一种路径。(a),(b),(c)三张图分别对应了由低到高不同阶次的重构机器的状态转移图。图中的圆圈代表状态，连边代表状态之间的转移，连边上的数字代表一次伯努利过程采样的0或1。
上图（a）为逻辑斯谛映射在[math]\displaystyle{ H_c }[/math]（[math]\displaystyle{ r=3.5699... }[/math]）处，序列长度[math]\displaystyle{ L=16 }[/math]时用斑图重构机器重构后的47个状态的状态转移图。图中每条闭合的链路长度都是16步，例如初始圆圈-1-3-5-9-12-16-19-21-23-27-31-35-39-41-43-45这条路径，它的总步数为16，每两步之间的数字是通过伯努利过程采样的二元分割的结果，每个分支代表它经历了一次伯努利随机过程。但是图（a）捕捉到的规律并不明显，我们将它进行一个简单的转换，用每两步之间的数字组成的序列替换机器中未分支的路径后就得到图（b），图（b）中的分支状态相当有规律。更进一步将图（b）升级为用字符生成器来描述增长的规律性就得到了图（c）。该图的有限自动机有两种状态（原有类型用圆圈表示，新类型用方块表示）和两个寄存器 A 和 B，A 和 B用于保存二进制字符串，初始状态 A 中保存的是0，B中保存的是1，B'表示对保存在B中的字符串的最后一位取反。
图（b）中的字符串操作可以通过将 A 的内容副本附加到 B 上，并用 B 的内容的两个副本替换 A 的内容来描述。这些字符串在方块处迭代，迭代式表示为[math]A\rightarrow BB[/math] 和[math] B\rightarrow BA[/math]。例如图（c）中从起始点-2-4-7-13这条链路，起始字符是1，可以用B描述，在4-7处发生变化，用B'描述，在7处产生了新的类型，B中字符变为10，在这里B'就是11，依此类推，就得到了图（c）。显然（c）的描述方式比（a）的方式更加节省计算资源，它的描述能力也更强。
与相关研究的比较
计算力学与因果涌现
概念对比
计算力学的许多概念上都可以在因果涌现理论框架下找到对应，通过进行两者之间的对应和比较，我们可以拓展对涌现的理解和研究。
| 序号 | 计算力学概念 | 因果涌现概念 | 概念的比较 |
|---|---|---|---|
| 1 | 观测序列 | 微观态 | 它们都在状态空间上描述，是系统观测到的最原始的数据，计算力学中的观测序列可以是无限长度的，微观态背后的动力学假设是马尔可夫的。 |
| 2 | 宏观态[math]\displaystyle{ \mathcal{R}_i \in \mathcal{R} }[/math] | 宏观态 | 它们都是从微观数据变换而来，计算力学中的宏观态[math]\displaystyle{ \mathcal{R}_i \in \mathcal{R} }[/math]是通过划分函数得到的，因果涌现的宏观态是将微观态经过粗粒化得到的。 |
| 3 | 划分映射[math]\displaystyle{ \eta }[/math] | 粗粒化策略 | 它们都是定义在状态空间上的，而粗粒化策略有时也指代变量空间上的映射关系。 |
| 4 | 因果态及其转移映射 | 最大化有效信息的宏观态及其动力学 | 它们都是理论上的最佳信息压缩方法，因果态的映射函数[math]\displaystyle{ \epsilon }[/math]根据预测等价性定义出来的，不损失微观上的信息，而最大化有效信息的粗粒化策略可能因为损失过多微观的信息得到平凡解。 |
斑图重构机器与NIS+（神经信息压缩机）的对比
计算力学中的斑图重构机器（ϵ-machine）和因果涌现中的NIS+（神经信息压缩机）也有相似的地方，比如斑图重构机器可以识别因果态和预测未来状态，神经信息压缩机可以识别和生成最大化有效信息的宏观态，都能够最大化的保留有用信息。香农熵率在NIS+的框架中可以理解为，宏观动力学预测结果解码后对微观预测的误差的允许程度。这保证了我们得到的宏观动力学不仅简洁，而且保留的确实是对微观预测最有用的信息。
计算力学与马尔科夫链的成块性理论
马尔科夫链是指一个有[math]\displaystyle{ N }[/math]个离散状态的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。在离散时间里，时间步之间的状态转移概率可以用一个状态转移概率矩阵[math]\displaystyle{ P }[/math]表示。该矩阵需满足马尔科夫条件，即每行加总等于1。
马尔科夫链的成块性Lumpability是一种描述马尔科夫链的状态是否可聚类的性质。Lump有‘块’的意思。判断一个马尔科夫链是否lumpable，是看它的马尔科夫状态转移矩阵这个大方块中的元素能不能结成一个个小方块。
具体来说，对于成块的马尔科夫链来说，我们可以把[math]\displaystyle{ N }[/math]个微观状态划分成[math]\displaystyle{ M \lt N }[/math]个宏观状态，在这个划分过程中，我们能定义微观状态[math]\displaystyle{ s_1 }[/math]到宏观状态[math]\displaystyle{ A_1 }[/math]的转移概率就等于[math]\displaystyle{ s_1 }[/math]到[math]\displaystyle{ A_1 }[/math]中的各个微观状态的转移概率的加和。
我们会发现，在成块的马尔科夫链中，宏观状态中的每一个微观状态转移到另一个宏观状态的转移概率都是一样的。这样会使得马尔科夫状态转移概率矩阵[math]\displaystyle{ P }[/math]这个方阵中，出现一个个方块，所以称之为成块性。
因果态和成块性的区别主要有以下三点：
- 因果态并没有马尔科夫性的假设，而成块性是马尔科夫链的一个性质，只能应用在马尔科夫链上。
- 我们也能在马尔科夫链上定义因果态，然后比较因果态和成块性。我们会发现，因果态是比成块性更严格的限制，因为它要求的是在[math]\displaystyle{ P }[/math]中的同一个因果态中的状态的行必须完全一致。存在因果态是马尔科夫链成块的充分条件，或者说，因果态的划分是一种成块的状态划分。因为因果态比成块性更严格，会出现我们能对因果态继续聚类得出更化简的成块划分的情况。
- 继续比较马尔科夫链的因果态和成块划分的话，我们还能看到，成块性保证了在聚类到宏观后，能保留宏观状态的所有信息。而因果态强调的是，在聚类中，不仅保留了宏观状态的信息，还能保留微观状态的信息。
斑图重构机器与世界模型
参考文献
- ↑ 1.0 1.1 N. H. Packard, J. P. Crutchfield, J. D. Farmer, and R. S. Shaw. Geometry from a time series. Phys. Rev. Let., 45:712, 1980.
- ↑ F. Takens. Detecting strange attractors in fluid turbulence. In D. A. Rand and L. S. Young, editors, Symposium on Dynamical Systems and Turbulence, volume 898, page 366, Berlin, 1981. Springer-Verlag
- ↑ A. Brandstater, J. Swift, Harry L. Swinney, A. Wolf, J. D. Farmer, E. Jen, and J. P. Crutchfield. Lowdimensional chaos in a hydrodynamic system. Phys. Rev. Lett., 51:1442, 1983
- ↑ 4.0 4.1 4.2 ] J. P. Crutchfield and K. Young. Inferring statistical complexity. Phys. Rev. Let., 63:105–108, 1989.
- ↑ M. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, New Jersey, 1967
- ↑ N. Chomsky. Three models for the description of language. IRE Trans. Info. Th., 2:113–124, 1956
- ↑ J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. AddisonWesley, Reading, 1979
- ↑ B. Holldobler and E. O. Wilson. The Ants. Belknap Press of Harvard University Press, Cambridge, Massachusetts, 1990.
- ↑ C. W. Reynolds. Flocks, herds, and schools: A distributed behavioral model. Computer Graphics, 21:25 – 34, 1987
- ↑ 10.0 10.1 E. F. Fama. Efficient capital markets II. J. Finance, 46:1575 – 1617, 1991
- ↑ Barnett L, Seth AK. Dynamical independence: discovering emergent macroscopic processes in complex dynamical systems. Physical Review E. 2023 Jul;108(1):014304.
- ↑ A. K. Seth, Measuring emergence via nonlinear granger causality., in: alife, Vol. 2008, 2008, pp. 545–552.
- ↑ 13.0 13.1 13.2 13.3 13.4 13.5 13.6 James P. Crutchfield. The Calculi of Emergence: Computation, Dynamics, and Induction. SFI 94-03-016. 1994
- ↑ 14.0 14.1 Shalizi, C. R.. & Crutchfield, J. P. (2001). Computational Mechanics: Pattern and Prediction, Structure and Simplicity,Journal of Statistical Physics,104(3/4).817-879.
- ↑ Rupe, A., & Crutchfield, J. P. (2024). On principles of emergent organization. Physics Reports.https://doi.org/10.1016/j.physlet.2024.06.017
- ↑ C. H. Bennett. Dissipation, information, computational complexity, and the definition of organization. In D. Pines, editor, Emerging Syntheses in the Sciences. Addison-Wesley, Redwood City, 1988.