“计算力学”的版本间的差异
（→柯式复杂度： 补充定理的公式） |
（→统计复杂度： 已经提前引用ϵ-机器，词条撰写仍需技巧。） |
||
| 第110行： | 第110行： | ||
拓扑复杂度 | 拓扑复杂度 | ||
| − | 当μ-阶图复杂度的μ为零时，μ-阶图复杂度也称为拓扑复杂度。由ϵ- | + | 当μ-阶图复杂度的μ为零时，μ-阶图复杂度也称为拓扑复杂度。由ϵ-机器的特征值给出。 |
统计复杂度 | 统计复杂度 | ||
2024年9月7日 (六) 05:51的版本
计算力学（Computational Mechanics）是一套数学框架，试图从历史序列的形态（Morph）系综中寻找、总结规律，并预测未来。“寻找、总结规律、预测未来”属于“智能活动”的一种，在许许多多的“智能活动”背后又有着潜在的更一般的规律。潜在的一般的规律，往往来源于对微观态进行粗粒化形成宏观态的因果涌现。计算力学从信息论出发，采用计算的视角，定义出模式，因果态，各态之间的转换等重要概念，并最终将“智能”抽象为支持通用计算的ϵ-机器。ϵ-机器被有关学者从理论上证明，有着宏观态上的信息封闭性和计算封闭性，可以展现出极大的预测能力和极小的复杂性。ϵ-机器有序对的因果态对所有长度未来[math]\displaystyle{ \overset{\to}{S} }[/math]而言还有着强同质性（Strict Homogeneity of Causal States）。
问题背景
自然和社会现象
复杂系统的涌现问题由来已久[1][2][3][4]。最吸引人的和使人迷惑的自然模式是那些在高度结构化的联合行为随着时间涌现于简单子系统的交互。鸟群以步调一致地形式飞行，鱼儿在没有领头带领以连贯的序列群组流转并突然共同转向的方式游动。蚊群形成复杂的社会，生存继承自特异化的社会分工，不是由中心领导所带领。几个世纪前，木星大气中五彩斑斓的混沌运动形成了被称之为“大红斑”的巨大漩涡，至少已存在二百到三百五十年，期间还在不断地改变颜色和形状。出现在经济系统中商品价格优化从主体服从本地商业规则中浮现。甚至在明显复杂系统处理玩家关键角色涌现全局信息。
这些观察构成直观的涌现定义,为了让它更可用，得有人说明“那些东西”是什么，并且它“新”在哪里。否则，表述就不够详细，甚至有些空洞。普通的机制能引导多样现象的涌现吗？同时代的科学和数学能提供什么语言去精确地描绘这些系统中涌现的不同组织？计算力学为您提供基于计算的视角来理解和预测涌现。
现象的计算视角
人们在生产生活中所用的计量方法及科学家们的计算机理论模型和实际计算设备。由于理论上已经证明图灵机、通用图灵机、元胞自动机、神经网络是计算等价的，所以计算力学词条选择一个等价关系来展开讲。这些计算包括算术方法和数理逻辑。
使用适当的假设和划分方法，在科学领域也称为映射，在复杂科学里一种特殊的映射可以称为粗粒化，能够获取一定程度上计算的下列特性：
- 封闭（完备）性。
- 一致性。
我们取智能体对环境的适应度为指标，可将绝大多数智能活动整理出层次性，数理和逻辑，从而纳入计算力学数学框架，进而使其和环境共同演化。
计算复杂度理论
实际的科研课题，往往具有以下特征：
这些课题转换为计算问题，则带有相当的复杂度，需要专门的计算复杂度理论加以研究。计算复杂度理论属于复杂系统理论一个分支，在复杂系统当中，对应的研究还有复杂网络超图等相关领域，各个领域都对所研究的课题准备了相应的分析和量化方法。计算力学在大量借助这些成熟的科学方法上，进行了相应的优化方法制定。
计算复杂度
二值计算
二值是符号里的0和1，是计算学所用的基本单位。通过组合0和1可以形成复杂的数学和逻辑，以及加入编解码器形成字符串。计算力学将经典复杂科学理论的部分核心“将自然过程二分为秩序和噪声”吸收了进来，也是相关文献[2]提到的创新方式。即我们可以利用复杂科学的粗粒化方法，将隐藏在自然现象中的过程压缩到极简的秩序（order，符号0）和随机（randomness，符号1），然后制定相应的运算法则，就能完成一种二值计算系统的建立，有兴趣的读者可以参阅布尔代数的相关内容。
在人工环境中使用二分法时，原始的随机过程，经过一定程度的累积，依赖于具体的粗粒化方法，有可能会呈现出一定的分布，导致计算复杂性的出现。这种计算复杂性经过抽象和形式化，使用不同的实体和规则，能形成不同的复杂度度量方法。
柯式复杂度
柯式复杂度是大家普遍公认的复杂度度量方法，在Jean-Paul Delahaye和Hector Zenil对复杂系统量化方法研究的工作中[5]，认为最天然的计算设备的模型需要有一定的表达能力，并定义一个字符串s对于通用图灵机U的柯尔莫哥洛夫-蔡汀(Kolmogorov-Chaitin)复杂度[math]\displaystyle{ K_{u}(s) }[/math]为输出该字符串s的最短程序p的二进制长度。
[math]\displaystyle{ K_{u}(s) = min\{\lvert p \rvert, U(p) = s \} }[/math]
下标u是对应通用图灵机的代号，U是运行程序p的通用图灵机的实体。
柯式复杂度的主要缺点是因为停机问题而导致的不可计算性，针对K式复杂度的主要评论是它高度依赖编程语言的选择。虽然柯式复杂度有上述问题，但仍能揭示计算和模拟的本质。不同的计算模型形成了复杂度的分水岭，智能体沿着复杂度的沟壑通向2050。
定理：总能找到一个常量E，对于任意的字符串s，两种计算模型U1和U2的柯式复杂度满足：
[math]\displaystyle{ \lvert K_{U_1}(s) - K_{U_2}(s) \rvert \lt E }[/math]
即，在误差条件E以内，有程序P能让计算模型U1模拟U2。
为提高通用性，忽略各图灵机之间的差异，将柯氏复杂度定义进一步定义为：
[math]\displaystyle{ K(s) := C_u(x) = min\{ \lvert \lang M,w \rang \rvert: 通用计算机M在输入w时停机并输出x \} }[/math]
按照前式标准化为：
[math]\displaystyle{ K(s) := C_u(x) = min\{ \lvert \lang M,w \rang \rvert: M(w) = x \} }[/math]
这里的w等于前式的p，即输出x的程序源代码字符串。
在文献[5]中确定柯式复杂度的定义时，使用了两种不同的计算模型：
- 确定性图灵机（deterministic Turing machines (TM)）。能够模拟神经元，一般以串行方式运行代码。
- 一维元胞自动机（CA）。以并行方式同时更新单时间步上的所有神经元。
做了计算性能的比较，实验结果显示两者有着很强的相互关联，而且两者均依靠输出字符串反转和计算对称性来进行分组。
统计复杂度
定义及符号[math]\displaystyle{ C_{μ} }[/math]
μ依赖于测度和分布
统计复杂度可用于线性系统的复杂性量化，也可用于非线性动态系统中复杂系统因果涌现复杂性的量化。香农熵基于概率分布，但对于确定性混沌却有些不足，统计复杂度则能量化宏观态上出现的确定性混沌。
统计复杂度（statistical complexity）是复杂系统深度的量化方式之一，用[math]\displaystyle{ C_{\mu} }[/math]符号来表示。其中μ依赖于测度和分布。跟统计力学中的量化理论有关，基于测度系统的定义。在部分混沌物理学的文献中，也被记作α。
在1989年《Inferring Statistical Complexity》[1]这篇文献里，复杂度的阶次符号为α，在2001年文献[4]中的符号为μ，这里我们统一使用μ。
μ-阶图复杂度
μ-阶图复杂度即为μ-阶图的概率算术复杂度，[math]\displaystyle{ C_{μ=0}=\log \lvert \mathbf{V} \rvert }[/math]。其中[math]\displaystyle{ \mathbf{V} }[/math]为μ-阶图的顶点集合。
在集智俱乐部的《因果涌现读书会》因果几何上，会对连续系统的因果涌现做更详细的介绍，有兴趣的可以参考下。
0-阶图复杂度([math]\displaystyle{ C_{μ=0} }[/math])和蔡汀-柯尔莫哥洛夫复杂度不同，0-阶图复杂度带有概率分布且依赖带有随机整数寄存器的图灵机。
μ-阶图复杂度（[math]\displaystyle{ C_{μ} }[/math]）是区别于信息论的量化复杂度的方法，后者基于维度[math]\displaystyle{ d_μ }[/math]和熵[math]\displaystyle{ h_μ }[/math]。
拓扑复杂度
当μ-阶图复杂度的μ为零时，μ-阶图复杂度也称为拓扑复杂度。由ϵ-机器的特征值给出。
统计复杂度
μ-阶图复杂度的μ = 1时，复杂度的量化方式为统计复杂度，带有热力学的“高温限制”。这里的统计复杂度也是1-阶图复杂度，即为香农熵。由ϵ-机器的物征向量给出。 统计复杂度（statistical complexity）是复杂系统深度的量化方式之一，用[math]\displaystyle{ C_{\mu} }[/math]符号来表示。这里的对应于因果涌现量化（有效信息EI），统计复杂度[math]\displaystyle{ C_{\mu} }[/math]越小，有效信息EI越大。
统计复杂度的下界，从周期行为和频段耦合中得出，是带二阶项的相位转换。
复杂度优化
经过演化，因果链能形成形式上的闭环，这里闭环在后文的因果态里，是指因果态在所有有效态中，统计复杂度最小等特征和属性。在管理学中，类似于使用组织行为学的知识，构建特定的反应链，从而完成特定目标。
几乎所有时间相关系统，经过复杂度的划分和优化，能展现出涌现属性。
因果态
因果态的定义
因为智能体对外部环境的测量精度一般都是有限的，测量结果一般为时间序列上的离散值，可以把它当做限制在离散值、离散时间上的稳定随机过程（ Process）。随机过程中所有序列的集合是一个双无限序列可数集合，记作[math]\displaystyle{ \overleftrightarrow{S}=⋯s_{-2} s_{-1} s_0 s_1 s_2… }[/math]。基于时间[math]\displaystyle{ t }[/math]可以将[math]\displaystyle{ \overleftrightarrow{S} }[/math]分为单侧前向序列[math]\displaystyle{ s_t^→=s_t s_{t+1} s_{t+2} s_{t+3}… }[/math]和单侧后向序列[math]\displaystyle{ s_t^←=⋯s_{t-3} s_{t-2} s_{t-1} s_t }[/math]两个部分，所有可能的未来序列[math]\displaystyle{ s_t^→ }[/math]形成的集合记作[math]\displaystyle{ \overrightarrow{S} }[/math]，所有可能的历史序列[math]\displaystyle{ \overleftarrow{s_t} }[/math]形成的集合记作[math]\displaystyle{ \overleftarrow{S} }[/math]。
为了捕捉[math]\displaystyle{ \overset{\leftarrow}{S} }[/math]中的有序结构，按照一定的划分方法（ partitioni）将[math]\displaystyle{ \overset{\leftarrow}{S} }[/math]划分为若干个互斥且全面的子集，那么每个子集就是一个有效态（effective state），这些有效态的集合记作[math]\displaystyle{ \mathcal{R} }[/math]，划分方法可以是任意函数映射[math]\displaystyle{ η }[/math]，用公式表示为[math]\displaystyle{ \eta{:}\tilde{\mathbf{S}}\mapsto\mathcal{R} }[/math]，也可以将有效态理解为将[math]\displaystyle{ \overset{\leftarrow}{S} }[/math]中的某段序列粗粒化后得到的宏观态。
上图为某种划分方法的示意图，将集合[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]不必形成紧致集，也可以是康托集或其他更特殊的结构，上图为了示意清楚才这样画的。
测量结果中的某个测量值可能对应某个“隐藏”状态（“隐藏”状态是智能体存储于其内部环境中的已知状态）。若在离散时间序列上不同的测量值对未来的预测有相同的模式，那么它们都对应一个相同的 “隐藏”状态，我们将这个“隐藏”状态称作这些不同测量值的因果态（casual state）。
如上图所示，在[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]时刻处于不同的因果态。
因果态的形式化定义可以按照如下方式描述：
属于相同因果态的两个状态[math]\displaystyle{ t }[/math] 和[math]\displaystyle{ t^{'} }[/math]，他们之间的关系可以表示为：[math]\displaystyle{ t∼t^{'} }[/math]，“[math]\displaystyle{ ∼ }[/math] ” 表示由等效未来形态所引起的等价关系。那么，就会有如下定义：
[math]\displaystyle{ t∼t^{'} \triangleq Pr(s^→ |s_t^← )=Pr(s^→ |s_{t^{'}}^← ) }[/math]
[math]\displaystyle{ Pr(s^→ |s_t^← ) }[/math]和[math]\displaystyle{ Pr(s^→ |s_{t^{'}}^← ) }[/math]为[math]\displaystyle{ s^→ }[/math]的条件概率分布，式中序列[math]\displaystyle{ t }[/math]和[math]\displaystyle{ t^{'} }[/math]通常是不同的，如果生成数据流[math]\displaystyle{ s }[/math]的过程是遍历的，上式可以理解为，如果[math]\displaystyle{ t∼t^{'} }[/math]，就算在不同时刻测量到了不同状态，智能体对未来状态的预测结果也会是相同的。
因果态的主要性质
按照最优的划分方法得到的有效态就是因果态，这些因果态的集合记作[math]\displaystyle{ \mathcal{S} }[/math]，[math]\displaystyle{ \mathcal{S} }[/math]是[math]\displaystyle{ \mathcal{R} }[/math]的一种最优形式，原因如下。
（1）在相同统计复杂度的前提下，因果态集合[math]\displaystyle{ \mathcal{S} }[/math]在有效态集合[math]\displaystyle{ \mathcal{R} }[/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{ 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]的条件熵。
（2）在相同预测能力的前提下，因果态集合[math]\displaystyle{ \mathcal{S} }[/math]在有效态集合[math]\displaystyle{ \mathcal{R} }[/math]的所有类型中，它的统计复杂度最小，用公式表示为[math]\displaystyle{ C_\mu(\hat{\mathcal{R}})\geq C_\mu(\mathcal{S}) }[/math]，[math]\displaystyle{ \hat{\mathcal{R}} }[/math]与[math]\displaystyle{ \mathcal{S} }[/math]有同等的预测能力，满足[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^{L}|\hat{\mathcal{R}}]=H[\stackrel{\rightarrow}{S}^{L}|\mathcal{S}] }[/math]。
上文中已经介绍了柯式复杂度和统计复杂度的基本概念，如果[math]\displaystyle{ s^L }[/math]表示对过程的测量结果的前[math]\displaystyle{ L }[/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_μ }[/math]为香农熵率，是信息不确定性程度的归一化指标，信息的不确定性越高，香农熵率越大。[math]\displaystyle{ h_μ }[/math]在这里可以理解为误差率， 则[math]\displaystyle{ h_μ L }[/math]为允许损失的随机信息量。
统计复杂度[math]\displaystyle{ C_μ (s^L ) }[/math]可以理解为允许存在误差率[math]\displaystyle{ h_μ }[/math]的情况下，描述[math]\displaystyle{ s^L }[/math]所用的最少信息量。
结合本条性质，求[math]\displaystyle{ C_μ (s^L ) }[/math]就是求[math]\displaystyle{ s^L }[/math]对应的因果态的统计复杂度，也就是说想要计算[math]\displaystyle{ C_μ (s^L ) }[/math]需要先找到[math]\displaystyle{ s^L }[/math]对应的因果态。
那么公式可以解释为：序列[math]\displaystyle{ s^L }[/math]的总信息量≈被归纳的因果态信息量+放弃归纳的随机信息量
（3）在相同预测能力的前提下，因果态集合[math]\displaystyle{ \mathcal{S} }[/math]在有效态集合[math]\displaystyle{ \mathcal{R} }[/math]的所有类型中，它的随机性最小，用公式表示为[math]\displaystyle{ H[\hat{\mathcal{R}}^{\prime}|\hat{\mathcal{R}}]\geq H[\mathcal{S}^{\prime}|\mathcal{S}] }[/math]，[math]\displaystyle{ \hat{\mathcal{R}} }[/math]满足[math]\displaystyle{ H[\stackrel{\rightarrow}{S}^{L}|\hat{\mathcal{R}}]=H[\stackrel{\rightarrow}{S}^{L}|\mathcal{S}] }[/math]，其中[math]\displaystyle{ \hat{\mathcal{R}}^{\prime} }[/math]和[math]\displaystyle{ \mathcal{S}^{\prime} }[/math]分别是该过程的下一时刻有效态和下一时刻因果态。
用互信息的角度去理解的话，上式等价于[math]\displaystyle{ I(S^{\prime};S)\geq I(\widehat{R}^{\prime};\widehat{R}) }[/math]，可以理解为任意有效态对它自己下一时刻的互信息中，其中因果态的互信息最大，若不考虑Do干预，因果态和因果涌现理论中最大化有效信息所得到的宏观态意义相同。
若想更深入的理解因果态的性质可以阅读James Crutchfield的两篇论文[1][6]，里面有因果态更多的性质和对应的形式化证明过程。
厄普西隆机器
厄普西隆机器（ϵ-machine） 此机器可以有效捕获模式，形式为有序对[math]\displaystyle{ \left \{ \epsilon, \mathbf{T} \right \} }[/math]。可以是信息源的生成机器，也可以是信息目的地重构出的机器。
ϵ-机器和图灵机不同，简单的图灵机是一种完全抽象的计算模型，它被实例化为冯·诺依曼架构，是现代计算机的理论模型。ϵ-机器可以通过和环境的互动，不断理解环境，更新自己的内秉属性，引入固定和随机变量而重构出来。
无限判定厄普西隆机器（ϵ-machine）可以表征为有限版本，并通过后续章节的重构算法形成字符生成器。
层次机器
多尺度
层次机器由多层ϵ-机器构成，其中单层ϵ-机器停留在水平因果态。层次机器从特定视角来看，是ϵ-机器的一个变体，是垂直方向的因果态。
层次机器具有多尺度自动建模的能力。
重构算法
1. 在最低水平上，设定0级模型为描述数据本身，即M0=s1s2s3...；
2. 从更低模型重构模型Ml=Ml-1/~，其中~表示l级上的因果等价类；操作的含义是，在l-1级上被区别对待的状态在l级上可以被视为同一个因果态。此时S和T都更新了；
3. 收集更多的数据，增大序列长度L，得到更加精确的一系列模型Ml；
4. 如果随着L增大，模型的复杂度发散，即[math]\displaystyle{ \lVert M_l \rVert \to \infty }[/math]，那么回到第二步，得到更高级模型Ml+1；
5. 如果模型复杂度收敛，意味着重建好了一个合适的ϵ-机器，程序退出。
实例
逻辑斯谛映射
逻辑斯谛（Logistic）映射求取迭代函数的极值，此极值可能呈现单周期、倍周期等现象。
元胞自动机
元胞自动机的复杂度的量化可使用0-阶图复杂度，即算术复杂度。
参考文献
- ↑ 1.0 1.1 1.2 James P. Crutchfield, Karl Young. Inferring Statistical Complexity. PHYSICAL REVIEW LETTERS, VOLUME 63, NUMBER 2. 10 JULY 1989
- ↑ 2.0 2.1 James P. Crutchfield. The Calculi of Emergence: Computation, Dynamics, and Induction. SFI 94-03-016. 1994
- ↑ James E. Hanson, James P. Crutchfield. Computational Mechanics of Cellular Automata: An Example. SFI WORKING PAPER: 1995-10-095
- ↑ 4.0 4.1 Cosma Rohilla Shalizi, James P. Crutchfield. Computational Mechanics: Pattern and Prediction, Structure and Simplicity. February 1, 2008
- ↑ 5.0 5.1 Jean-Paul Delahaye, Hector Zenil. Towards a stable definition of Kolmogorov-Chaitin complexity. Fundamenta Informaticae XXI 1–15. 2008
- ↑ Shalizi, C. R.. & Crutchfield, J. P. (2001). Computational Mechanics: Pattern and Prediction, Structure and Simplicity,Journal of Statistical Physics,104(3/4).817-879.
编者推荐
计算力学和因果涌现关系密切，计算力学借鉴了因果涌现大量的概念、算法以及模型，并提出了因果态和统计复杂度概念和涌现的量化方法。下面是一些链接能够帮助读者更好的了解因果涌现的相关信息：
因果涌现读书会
读书会通过阅读前沿文献，加深我们对因果、涌现等概念的理解；聚焦于寻找因果与涌现、多尺度等概念相结合的研究方向；并探索复杂系统多尺度自动建模的研究方向。并探索复杂系统多尺度自动建模的研究方向。分享近期发展起来的一些理论与工具，包括因果涌现理论、机器学习驱动的重整化技术，以及自指动力学正在发展一套跨尺度的分析框架等。
涌现与因果的结合创造了因果涌现的概念。这是一套利用因果性来定量刻画涌现的理论体系，本季读书会通过阅读前沿文献，加深我们对因果、涌现等概念的理解；聚焦于寻找因果与涌现、多尺度等概念相结合的研究方向；并探索复杂系统多尺度自动建模的研究方向。第二季读书会更加集中在探讨因果科学与因果涌现之间的关系，以及对涌现进行定量刻画，聚焦于寻找因果与涌现、多尺度等概念相结合的研究方向；并探索复杂系统多尺度自动建模的研究方向。
因果涌现第三季的读书会中，将进一步围绕因果涌现的核心研究问题『因果涌现的定义』以及『因果涌现的辨识』来进行深入的学习和讨论，对 Erik Hoel 提出的 Causal Emergence，Causal Geometry 等因果涌现的核心理论进行深入的探讨和剖析，并且详细梳理其中涉及到的方法论，包括从动力学约简、隐空间动力学学习等其他研究领域中学习和借鉴相关的研究思路，最后探讨因果涌现的应用，包括基于生物网络、脑网络或者涌现探测等问题展开扩展，发掘更多的实际应用场景。