计算力学

计算力学（Computational Mechanics）是一套用于量化涌现的框架。它以一种计算的视角，研究观察者建立的模型在识别涌现时，模型发生的变化。计算力学以信息论和生物进化的思想为基础，是目前最早的对涌现的定量化研究。在应用当中，该理论提出了对复杂性度量的新指标，即统计复杂度，同时还提出了一套识别涌现的算法。

历史渊源

计算力学源于 20 世纪 70 年代和 80 年代早期非线性物理学领域对流体力学领域湍流问题的研究。为了识别流体湍流中的混沌动力学，Packard和 Crutchfield等人开发了一套吸引子重构方法，使用测量的时间序列来重构流体动力系统的状态空间，可以在其中观察混沌吸引子并定量测量它们的不稳定程度及其伴随的复杂性。这套重构方法的有效性在 1983 年通过实验得到了验证，之后就被广泛用于识别和量化确定性混沌系统的行为。但是，这套方法无法简明扼要地表达被重构系统的内部结构。为了解决这个问题，计算力学理论应运而生。

计算力学的首次提出是在1989年，Crutchfield在他的一篇论文中，基于时间序列重构的状态空间 和自动机理论定义了一种预测等价关系。利用这种关系分析时间序列数据，识别和量化其中有规律的部分，计算力学就可以构建一个能够预测系统未来行为的模型。

计算力学的核心概念是因果态（Causal State），它是一种与微观状态预测等价的特殊的宏观态。基于这种预测等价性的宏观态划分思想可以追溯到70年代的马尔科夫链的成块性（Lumpability）理论。Kemeny和Snell在1969年针对马尔科夫链提出成块性这一概念，目的在于判断一个马尔科夫动力系统是否是可被简化归并的。对于任意一个马尔科夫链，我们可以判断某种划分是否是成块的。成块的划分要求对状态的归并要尽可能地保留马尔可夫链中的原始重要信息，并保证划分操作与动力学操作的可交换性。不过在马尔科夫链中，成块性只是对于划分的一种要求，而没有追求最优的划分。对成块性的进一步了解，请参考词条马尔科夫链的成块性。与之相比，计算力学首先关注的不只是马尔科夫动力学，而是要囊括更广泛的动力学形式。此外，计算力学试图提出一种最优的划分，能极大地保留对预测有用的信息。此外，当一般的动力学过程退化到马尔科夫动力学的时候，成块性的成立条件实际上与因果态的定义具有一定的相似性。

问题背景

自然和社会现象中的涌现

有一些自然和社会现象非常引人入胜，但也很令人困惑，比如行为简单的蚂蚁可以形成复杂的社会，在没有控制中心的情况下自发产生特异化的社会分工。 在没有领导者引导的情况下成群的鸟以步调一致的队形飞行，成群的鱼以连贯的阵列游动，突然一起转向。经济中商品的最佳定价似乎源于主体遵守局部的商业规则。这些现象中的全局协调是如何出现的？是否有共同的机制引导着这些不同现象的出现？在复杂系统理论中把这类许多独立子系统相互作用后产生高度结构化的集体行为的现象称作涌现。

目前对涌现的研究理论有基于有效信息的因果涌现理论、基于信息分解的因果涌现理论、基于可逆性的因果涌现理论，基于转移熵的动力学解耦理论、基于格兰杰因果的G-emergence理论等等。计算力学是基于统计复杂度对涌现的定量化研究理论，它提出的时间最早，虽然对涌现的的研究方法与上述理论均不同，但有很多研究思路是相似的，它定义的统计复杂度、因果态、斑图重构机器等概念对涌现的研究有很大启发和借鉴意义。

计算力学中的涌现

什么是涌现？从直觉上来说，涌现现象就是系统出现了新的特征。但是什么是“新特征”呢？特征的新又“新”在哪里？所以，我们还需要更精确的语言对涌现的概念进行描述。涌现通常被理解为一个过程，该过程所产生的结构并不能直接由控制系统的定义所约束以及被瞬时力所描述。比如一堆随机运动的粒子，虽然它们受到的瞬时力可以用运动方程描述，但是从宏观尺度上却会表现出诸如压强、体积以及温度等新特征。我们需要引入斑图的概念来明确说明什么是新特征，否则涌现这一概念几乎没有内容，因为几乎任何时间依赖的系统都会表现出涌现特征。

在计算力学中，斑图通常指的是从时间序列中总结出的规律性结构。实际上，检测到的斑图通常是通过观察者选择的统计数据来隐含假定的，可能某些斑图的功能表现与其数学模型一致，但这些模型本身依赖于一系列理论假设。简而言之，斑图通常是被猜测出来的，观察者通过固定的规律库来预测这些结构，然后再进行验证。可以用通信信道做一个类比，观察者就像是一个已经手握密码本的接收者，任何未能通过密码本解码的信号本质上都是噪声，即观察者未能识别的斑图。

在系统内部的协调行为中，有一种斑图变得尤为重要，这种斑图会相对于该系统的其他结构显现其“新颖性”。由于没有外部的参照来定义这种新颖性，我们可以将这个过程称为内在涌现（Intrinsic Emergence）。比如在高效的资本市场中，主体根据从集体行为中涌现出的最优定价，调整其个人生产-投资和股票所有权策略。对于主体的资源配置决策而言，通过市场的集体行为涌现出的价格是准确的信号，它完全反映了所有可用信息。内在涌现的独特之处在于系统形成的斑图赋予了系统额外的功能性，并支持全局信息处理，如设定最优价格等。更具体地说，内在涌现可以直接嵌入系统非线性计算过程之中，能够被系统直接利用，这样就赋予了系统额外的功能性。

总而言之，计算力学区分了三个概念：

1. 对涌现的直觉定义：系统中出现任何可以被称为新颖的特征。
2. 斑图涌现（Pattern Formation）：观察者在系统中识别出的有规律的结构。
3. 内在涌现（Intrinsic Emergence）：系统本身捕捉并利用它自身出现的斑图。

进化的系统模型

我们可以从多智能体系统的视角来阐述内在涌现的问题，从而为一个高度有序的系统是怎么从混沌中涌现的提供一种可能的解释。但是该视角在解释生命形式的多样性方面依然能力有限。因此要将系统限制在一个结构和生物特征明确的确定性动力系统（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{ \overleftarrow{s_t}=\cdots s_{t-3} s_{t-2} s_{t-1} }[/math]和单侧后向序列[math]\displaystyle{ \overrightarrow{s_t}=s_t s_{t+1} s_{t+2} s_{t+3}\cdots }[/math]两个部分，所有可能的未来序列[math]\displaystyle{ \overrightarrow{s_t} }[/math]形成的集合记作[math]\displaystyle{ \overrightarrow{S} }[/math]，所有可能的历史序列[math]\displaystyle{ \overleftarrow{s_t} }[/math]形成的集合记作[math]\displaystyle{ \overleftarrow{S} }[/math]。某一个时刻的状态指的是截止到当前时刻的历史序列。

然后我们将定义一个叫做“因果态”的概念。

因果态的定义

划分

通过对状态空间进行划分（partition），智能体可以用一种更加粗糙的方式来描述同样的状态，这一过程也被人们叫做粗粒化。划分可以被理解为一种映射，[math]\displaystyle{ \eta{:}\overleftarrow{S}\mapsto\mathcal{R} }[/math]，其中[math]\displaystyle{ \mathcal{R} }[/math]是状态空间的子集的集合，要满足其元素彼此互斥，而且所有元素的并集等于[math]\displaystyle{ \overset{\leftarrow}{S} }[/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{ \overleftarrow{s_t} }[/math]与[math]\displaystyle{ \overleftarrow{s_{t^{'}}} }[/math]等价，记为：[math]\displaystyle{ \overleftarrow{s_t}\sim \overleftarrow{s_{t^{'}}} }[/math]，或简记为[math]\displaystyle{ t\sim t^{'} }[/math]，其中“[math]\displaystyle{ ∼ }[/math] ” 表示由等效未来状态所引起的等价关系，也叫预测等价性（predictive equivalence），可以用公式表示为：

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

也就是说，若[math]\displaystyle{ t }[/math] 和[math]\displaystyle{ t^{'} }[/math]对未来状态预测的分布相同，则它们对应的状态就都具有一种等价性，这就是因果态定义的来源。

因果态

我们可以直接将因果态定义为一个从状态集到状态子集的映射，即[math]\displaystyle{ \epsilon{:}\overleftarrow{S}\mapsto2^{\overset{\leftarrow}{S}} }[/math]，其中[math]\displaystyle{ 2^{\overset{\leftarrow}{S}} }[/math]是[math]\displaystyle{ \overleftarrow{S} }[/math]的幂集，且[math]\epsilon[/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{ \stackrel{\leftarrow}{s} }[/math]为历史序列的随机变量。

所有的因果态的集合，可以由预测等价关系"[math]\sim[/math]"诱导的对状态空间的一种划分来定义，即状态集与等价关系的商集：[math]\mathcal{S}=\stackrel{\leftarrow}{S}/\sim[/math]，其中[math]\displaystyle{ \mathcal{S} }[/math]为因果态划分。

举例说明

为了说明因果态的概念，我们绘制下面的示意图以举例说明：

如上图所示，左侧的数字代表[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]时刻不同，则处于不同的因果态。

小结

内在计算（intrinsic computation）的核心思想是预测等价性，即系统的历史能够用来预测其未来行为的一种等价性。通过构建预测模型，内在计算能够识别系统中的结构，并量化这些结构的复杂性和稳定性。它可以让我们能够将自组织视为系统中规律性和规则性的涌现，而这些规律性和规则性是系统在特定的初始条件和外部驱动下自发形成的。内在计算的一个重要应用是在于理解从完全规则到完全无序之间组织结构的差异和过渡。比如，木星的大红斑是一个经典的自组织现象，其规模和稳定性无法通过流体力学方程的求解而获得直接解释。然而，内在计算能够通过分析该现象的历史数据，构建出一个能够准确预测其未来行为的模型，从而揭示出其背后的自组织机制。

因果态的主要性质

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

最大预测性

性质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{ \mathcal{S} }[/math]为因果态划分，所有可能的历史序列记作[math]\displaystyle{ \overleftarrow{S} }[/math]。[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{R}] }[/math]和[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^L|\mathcal{S}] }[/math]是[math]\displaystyle{ \stackrel{\rightarrow}{S}^L }[/math]的条件熵。可以理解为因果态集合[math]\displaystyle{ \mathcal{S} }[/math]是在所有的划分宏观态集合[math]\displaystyle{ \mathcal{R} }[/math]中，预测能力最强的一种宏观态，证明过程如下：

根据因果态的定义可知：[math]\displaystyle{ \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合写的一篇论文，里面有因果态更多的性质和对应的形式化证明过程。

斑图重构机器

前面给出了因果态的定义，接下来讨论一个智能体是如何从观测到的时间序列数据中，自动地发现因果态的问题。为了解决这个问题，计算力学建立了名为斑图重构机器（ϵ-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{ s }[/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]，这就是“斑图重构机器”（ϵ-machine）。后文“模型的重构”一节中会详细介绍如何获得这个斑图重构机器，以及智能体的内在模型会如何根据观测到的新数据，动态更新[math]\displaystyle{ \epsilon }[/math]映射和[math]\displaystyle{ T }[/math]函数。