计算力学

翻译自 http://arxiv.org/abs/cond-mat/9907176v2

标题

计算力学：斑图和预测，结构和简化

Cosma Rohilla Shalizi∗ 和 James P. Crutchfield

圣塔菲研究所，1399 Hyde 公园路，圣塔菲，NM 87501

电子邮箱地址：{shalizi,chaos}@santafe.edu

（2008年2月1日）

计算力学是一种方法，用来结构化复杂性，定义一个过程的因果态，并给出一个找出它们的步骤。我们揭示了因果态的表征-一个ε机制-拥有最小复杂度的同时又能拥有最准确的预测能力。我们在ε机制最优化和唯一性上，以及如何将ε机制同其他表征相比较上，获得了一些成果。更多结果和测量随机性和结构复杂度有关联，这些关联是从ε机制到一些遍历及信息理论获得的。

圣塔菲研究所 研究论文 99-07-044

关键字：复杂性，计算，熵，信息，斑图，统计力学 页眉：计算力学

02.50.Wp, 05.45, 05.65+b, 89.70.+c

目录

简介

代数斑图

图灵机：斑图和有效过程

带错误的斑图

随机性：斑图的对立面吗？

因果

斑图概览

在奥卡姆水池周边填充

隐含过程

过程定义

稳态

水池

一点信息论

熵的定义

联合和条件熵

互信息

系综中的斑图

定义捕获的斑图

历史一课

旧世界引理

最小化和预测

状态类的复杂度

计算力学

因果态

定义过程的因果态

构型

在某一因果态条件下过去和未来的独立性

同质性

强同质性

弱同质性

因果态的强同质性

因果态到状态转移

因果转移

转移概率

ε机制

ε机制的定义

ε机制是系综

ε机制是决定性的

因果态是无关的

ε机制的重建

最优化和唯一性

ε机制可以最大化预测

ε机制足够统计性

预测平替定义

改进引理

因果态是最小化的

一个过程的统计复杂性

因果态是唯一的

ε机制具有最小随机性

边界

扩展熵

扩展的边界

条件不影响熵

比率

控制论

结论补充

讨论

现有成果的不足

未来工作的结论和方向

附录

信息论公式

导出因果态的等价关系

时间反演

ε机制是幺半群

改进引理的另一种证明

准无限未来的有限熵

有限控制论

G 同其他领域的关系

1 时间序列建模

2 决策理论的问题

3 随机过程

4 形式语言理论和语法推理

5 计算和统计学习理论

6 描述长度原则和统一编码理论

7 测量复杂性

8 层级缩放复杂性

9 连续动态计算

参考文献

符号表

Ⅰ. 简介

有组织的物质在自然界中是广泛存在的，物理学的分支应该可以处理它-统计力学-只是缺乏一致性，原则性的方式去描述，测量，以及检测这么多自然展示出来的不同结构。统计力学有好的测量无序的热力学熵，以及相关的量化方法，比如自由能。当扩展关键模式和斑图形式的时候，它也能够拥有非常好的成功方法，来分析从对称性破缺中形成的斑图。在均衡态和最近的非均衡态都能应用。不幸的是，这些成功包含了很多技巧性处理——比如说猜测序参量，为扰动扩展标识小参量，和给空间拆分选择合适的功能基。目前这些方法还远不够清晰，还不能处理所有在自然界中遇到的多样性组织，特别是那些生物形成的过程。

计算力学【5】是一种直接定位斑图、结构和组织议题的方法。同时保留了大家已经熟悉的统计力学的概念和数学工具，它同后者不同又补充了后者。在本质上，不管是从经验数据还是从行为的概率描述上，它都显示了怎样去推断一个生成观测到的行为隐藏过程的模型。这种表征——ε机制——用一种能反应过程因果结构的方式捕捉到观测数据中的斑图和法则。把这个模型放在手上，是很有用的，它能对观测到的原始数据进行外推，从而对将来的行为做出预测。更多的是，在一个良好定义的语境里，也是下面的一个主题：这个ε-机制对观测到的生成数据来说，是唯一最大有效的模型。

ε-机制他们也揭示出，用一种直接的方式，信息是如何存储在过程中，以及存储的信息是怎样随新的输入和时间的流逝转换的。这也说明，不使用计算机来做仿真和数值计算，就使计算力学成为“力学”，在一种“计算理论”的语境里。

计算力学的基本想法在十年前介绍过。从那时起，他们用于用于动态系统，蜂窝自动化，隐式马尔可夫模型，改进的空间计算，随机共振，全局耦合的地图，和水龙头滴水实验。尽管有这些成功的应用记录，关于这个主题的数学基础，还存在一些不确定的东西。从结构方面来看，ε-机制在捕捉一个过程固有的斑图和用最小方式实现上，是很显然的，这个里面发表没有特定的证明。更多地，这里面还没有证明，如果ε-机制是以这种方式最优的，它是一个过程唯一的最优表征。这些微小需要的间隙已经补充上了。（译者注：间隙之所以little-needed，是因为想法提出以后，形成了一些成功样例，但是离完整证明还有一段距离。这段距离虽然有点微不足道 ，但也是需要的。本篇文章就来完成想法到证明到成功应用的完整过程。）对于那些（是有道理的）在一个过程的统计特征约束的议题，我们证明了ε-机制确实是唯一最优的因果模型（译者注：之所以谈到统计特征约束的议题，应该是证明结果可用于统计特征约束）。这些结果的严格证明是这篇文章的主要内容。我们给出最优结果的初步版本——但并不是唯一性理论，关于唯一性理论有新的文献——请移步参考文献【15】。

本篇阐述的大纲按下述过程进行。我们先开始展示计算力学，在斑图，随机性，和因果上，是如何关联到其它方法的。这样做的要点也是将我们的注意力聚焦于统计系统中的斑图上，以及他们概率的表征。使用从信息论来的一些想法，我们为这些表征，陈述奥卡姆剃刀一个定量性的版本。在这一点上我们定义因果态，等价于行为类别，以及在因果态之间转换的结构——ε-机制。随后我们揭示从奥卡姆剃刀的角度看，因果态在获取最大可能预测上的能力，是理想的。更多是的，我们揭示了因果态是唯一最优的。这些结合优势让我们可以去证明，关联到ε-机制最优结果的，一系列其他内容。我们检查了在继承最优结果时做出的断言，同时我们备注了他们其中的一些可以在不需要过度扰乱理论的条件下获得提升。我们也在一个过程的内生力学上建立了边界，这些边界为ε-机制和定量化信息，以及遍历理论所揭示。最后，我们用回顾本篇展示了什么，以及在计算力学的数学基础上，什么可以视为许诺将来工作方向，来作为结束。

一系列附录提供了附加材料，有信息论，等价关系和类，用于时间反演过程的ε-机制，半群理论，计算力学和其他领域的联系和区别。

为了给延续数学和提出在这里使用的假定打好基础，我们现在开始回顾以前在斑图、随机性和因果关系的工作。我们鼓励只对数学前沿感兴趣的读者跳到第二节F部分——计算力学的中心假定概要——并从那里继续。

Ⅱ. 斑图

为了介绍我们的方法——同时去论证有些方法是必要的——发现和描述自然界中的斑图，我们开始引用豪尔赫·路易斯·博尔赫斯（Jorge Luis Borges ，1899年8月24日-1986年6月14日，男，阿根廷诗人、小说家、散文家兼翻译家，被誉为作家中的考古学家。）：

这些含糊，多余，缺失让人想起弗兰茨·库恩（Dr. Franz Kuhn，德国汉学家）在一本特定的中文百科全书所描绘的特性，标题为“仁者智识里的中国百家（Celestial Emporium of Benevolent Knowledge）”。在这些远古的书中写到：动物分成（a）属于帝王的，（b）做过防腐处理的，（c）训练过的，（d）哼哼吸鼻子的猪，（e）美人鱼（译者注：星巴克，Startbulks），（f）神话中的精灵，（g）迷茫的狗子，（h）那些已经包含中这些分类的，（i）那些疯狂到颤抖的，（j）多得数不清的东西，（k）那些用很好的骆驼毛刷绘制的，（l）其他的，（m）那些只是打碎过一个花瓶的，（n）那些从远处看有些象苍蝇的。

    J. L. 博尔赫斯，“约翰·威尔金斯（John Wilkins）的分析语言”，参考文献【16，103页】；也可以参看文献【17】当中的讨论。

这篇小短文显示出斑图和从斑图继承的类别之间的鸿沟，对于世界万物来说是适用的，并能帮助我们去理解它和那些斑图，那些可能如同法律条文般正统，并没有全部提及。

    是什么形成了中国百家的语法固然没有无法令天满意的答案，也不是说够奇特，而是说它根本没有告诉我们关于动物的知识。我们希望在一个过程中找到斑图，可以“在交叉处分开，如自然之启迪，不象糟糕的雕塑家那样把肢体弄断”【18，265D部分】。

    计算力学不会直接关注于斑图固有信息，虽然我们猜测它最终会在那个领域会有实用价值。它也不关注于斑图识别，虽然后者在神经科学【19】，心理物理学【20】，认知行为学【21】，计算机工程【22】，和信号及图像处理【23，24】产生了实际影响。相反，它关注于这个问题：斑图是什么以及斑图该怎么表征。一个路径去标出差别是去回想这些斑图的发现，而不是斑图的识别。

    智知篇章的主体在于讲清什么斑图达到了哲学层次。在广阔的红笔书就的数学逻辑上已经作出了一个清晰的分组。这里面还包含方法，一方面说，（高度）使用抽象代数和关系理论表现；别一方面说，那些方法斑图依靠算法理论和有效过程。

    一般想法是，在两种途径里，一些物体O有斑图P——O有斑图“表征”，“描述”，“捕获”，由P所达成——当且仅当我们可以使用P去预测或压缩O。注意到预测的能力预示着压缩的能力，但反过来却不行；这里我们偏向于预测。代数和算法最后的不同点主要在于P如何被表征；也就是说，他们的区别是它是如何在一些形式语法的词典被表达的。

    在这里我们要强调的是，“斑图”在这里体现了一种规范，结构，对称，组织，以及如此等等。相反地，通常的用法有时可以接受，比如，讨论关于像素的“斑图”，在一小部分片段-通道视频“雪原”；但我们更希望说什么是像素的配置。

A. 代数斑图

    虽然斑图发现的问题出现得较早，在柏拉图的美诺篇（Plato's Meno，“美诺”可以看作是音译，也可以意译为美好的诺言。）【25】中，有一个例子，有可能第一次将“斑图”概念在数学上做严格定义的，是怀特海和罗素的数学原理。他们将斑图视为属性而非集合，但是属于在集合内或之间的关系，而且相应地他们作出了精心构思的关系-代数【26， vol. II，part IV】；cf. 【27，ch. 5-6】。这开创了定义两个集合之间一个关系的关系数，使得所有关系构成的类别，在一对一，到映射两个集合的意义上，是等价的。在这个框架中，关系享有常见的斑图或结构，如果他们拥有相同的关系数。举例来说，所有的方形晶格拥有相似的结构，因为他们的元素共享相同的邻接关系；所有的六边形晶格也是如此。尽管六边形和方形晶格，展现不同斑图，因为他们邻接关系不是同构的-也就是说，因为他们拥有不同的关系数。（也可参阅定义在参考文献【28】中的记录等价）在这上面所做的工作比期望的——尤其是罗素——要少些。这个或许可以延续到参考文献【26】第二卷一般性缺失的部分。

    更近地试图开发一种代数方法用于斑图构建的是半群理论和它的克罗恩-罗德（Krohn-Rhodes）分解定理。参考文献【30】讨论了一定范围内这种方法在斑图上的应用。介绍了这么多，罗德和Nehaniv还尝试过将半群复杂理论应用于生物进化【31】。他们的结论是生物结构的复杂性可以用描述该结构的子群分解自动机的数量来测量。

    也有另一个代数方法被格列南德（Grenander）和他的同事开发出发，主要用于斑图识别【32】。本质上来讲，这对于为斑图问题发明一个生成器和约束最小集是至关重要的。生成器可以串联彼此，在一个合适的n维空间上，仅当他们的约束是兼容的。每一个兼容的约束对，同时指定一个二值代数操作，和一个从生成器构建出来的配置可观测元素。（我们在附录D中建立，用字符串连接来链接一个代数操作，是一种类似的粗陋方式。）可能性可以被附加到这些约束上，以自然方式导向到一个在整个配置之上的（吉布斯（Gibbsian））概率分布。格列南德和他的同僚们使用过这些方法去描述特征，其中也包括，几种生物范式【33，34】。

B. 图灵机制：斑图和有效过程

    另外找寻斑图的路径可以沿着逻辑基础数学的传统探究来进行，象弗雷格、希尔伯特所表达的和丘奇、哥德尔、波斯特、罗素、图灵、和怀特海所先行的。最近的，也是和流行更有关联的方法则是回到柯尔莫哥洛夫和蔡汀，他们的研究领域恰巧在于重构单独的物件【35，38】；尤其是，他们聚焦于离散符号系统，而不是（说）实数或其他数学物件。用于表征斑图P的备选项有通用图灵机（Universal Turing machine, UTM）程序——尤其是，刚好生成物件O的最短UTM程序。这个程序的长度被叫作O的柯尔莫哥洛夫和蔡汀复杂度。注意到任何体系——自动机，语法，又或者有什么不是——这些是图灵等价的，而且对那些“长度”的观念是定义优良的，将用于表征体系。自从我们可以将这些一个设备转换到另一个——比如说，从一个波斯特标记系统【39】到图灵机——对第一个系统只使用有限的描述，当使用这种方法来衡量复杂性时，这类约束容易被融合到一块。

    特别地，考虑O前面的n个字符On，和生成他们的最短程序Pn。我们询问，下式的极限会怎么样

[math]\displaystyle{ \lim_{x \to \infty} \frac{\lvert P_n \rvert}{n}, }[/math]

当|P|是程序P的比特长度时？从一方面来看，如果有一个固定长度的程序P能生成O的任意若干比特位，那么这个极限将会消失。在我们感兴趣的绝大多数域里，有理数或无理数——比如π, e,√2——属于这个域。这些数域是非常压缩的：程序P是压缩的描述，所以它能捕捉符合描绘O序列的斑图。如果这个极限趋于1，从另一方面来看，我们拥有一个完全未压缩的描述和结论，按柯尔莫哥洛夫和蔡汀的观点，O是随机的【35-38，40，41】。这个结论正是需要的：柯尔莫哥洛夫和蔡汀框架建立了，至少在形式上，单个物体的随机性，不在提出概率描述或重构事件系综。它之所以能做到这样，是涉及到一个确定性的，算法表征——通用图灵机（UTM）。

    将柯尔莫哥洛夫复杂度应用于自然过程，有一些众所周知的困难。首先，作为数量，它却不能进行通用计算，因为有停机问题【38】。第二，对随机过程它是最大化的。这些可以被建构起来，如同称心的一样，如同刚刚提到的。或者捕捉斑图失败，看个人的目标了。第三，它只能应用于一个过程；再一次地这可能是优点，也可能是缺点。第四，它没有为噪音或失误预留，要求准确地重构。最后，lim n->∞|Pn|/n可能消失，尽管需要运行程序的可计算资源，比如时间和存储，增长到无界。

    这个障碍并不能阻止研究者在实际任务中放弃使用柯尔莫哥洛夫-蔡汀复杂度——比如测量自然物体（例子在参考文献【42】），作为归纳推理的理论基石【43，44】，也是捕捉斑图的一般意义【45】。如Rissanen【46， p. 49】所说，这个同“用写程序来学习【数据集】的属性，希望能找到最短的一个”类似。

    所列出的各种困难，由后续的工作做了阐述。本内特的逻辑深度统计了时间资源【47】。（实际上它是生成O的最小长度程序所需时间）Koppel的复杂性试图从随机性，或者实际指定的输入数据，分离出程序的“法则”部分【48，49】。最终，这些扩展和泛化保留在了通用图灵机（UTM）中，精确重现设置和继承固有的不可计算性。

C. 带有误差的斑图

    由这些理论困难和现实关切所触发，显然下一阶段是允许我们的斑图P在交换短描述时，带一定程度的近似或误差。结果就是，我们不能从斑图精确重构原始配置。在自然当中普通存在噪声条件下，这是能承受的小负担。我们也可以说有时候我们能接受同法则的一些小偏差，在不会真正关心精确的偏差是什么的条件下。如同参考文献【17】的结论所指出的，这就是真正在热力学描述中的首要动机，位于我们明确放弃的，也没有兴趣，对广阔数量的微观细节，为宏观观测找到一个可工作的描述。

    一些奇妙的哲学工作在有误差的斑图上，这些工作已经由丹尼特所完成，不仅带有询问关于自然斑图和他们的涌现，而且能引申到哲学的参考。这个直觉力来自真正的随机过程可以很容易建模——“为建模硬币投掷，投一枚硬币就好了。”任何跟假设完全无关，按照事实本身，更精确预测体制，也能在数据中捕捉斑图。因此有一系列潜在的斑图捕捉器，从纯噪声假设到数据的精确重构，如果那是可能的话。丹尼特提到在预测器的简单性和精确性之间通常有两难的情况，他也貌似有理地将涌现现象【51，52】描述为，斑图允许在复杂性上大量缩减，但在准确性上只有少减缩减。当然了，丹尼特并不一定一开始就考虑容许失误和噪声的预测体制；我们则讨论附录G中的一些早期的工作。尽量如此，对我们的认识而言，他是第一个制成了预测器的中间部分，明确了一系列斑图是什么。必须提到的是，这一序列缺少我们已经考虑到的其他方法的数学细节，而且它依赖于单个配置的不精确预测。实际上，它依赖于由噪声“刻意模糊”的预测器。尽管有噪声的引入，带来了概率分布，而且他们的自然设置位于系统当中。它位于这样一种设置，该设置是我们同丹尼特分享想法能收获合适数量的待遇。

D. 随机性：斑图的对立面？

    我们在这一点上应该说一点关于随机性，复杂性和结构之间的关系，至少我们在用这些词语。除了一些基础方面的问题，随机性实际上已经可以很好地理解和处理了，只需使用玻尔兹曼【53】；费希尔, 内曼, 和Pearson【54】；柯尔莫哥洛夫【35】；和香农【55】，以及其他人介绍的工具。一个传统的学习复杂科学的方法，实际上标记了复杂性带有随机性，而且，如同我们刚看到的，对于一些目标来说是有用的。这些目标即不是分析真实世界过程的斑图，也不是我们的。随机性的简化根本不是关于斑图或结构的观念，也不暗示，柯尔莫哥洛夫-蔡汀复杂度，也没受测量斑图所引发。

    尽管如此，一些复杂性方法混合了“结构”，带着随机性的对立面，按照惯例由物理方面的热力学熵或相关的量化方式，比如香农熵，来理解和测量。从效果来看，结构定义成“一减去无序”。相反地，我们看待斑图——结构，组织，规范，和其他——用坐标的“正交性”来描述一个过程随机性的程度。这说明，复杂性（从我们的感觉来看）和随机性都能捕捉有用的属性，这些属性对于描述一个过程如何操控信息是必要的。这种互补性甚至都被参考文献【6】复杂性-熵图表编纂了。现在应当是清晰的，当我们使用单词“复杂性”，我们的意思是斑图的“程”度，而不是随机性的程度。