计算力学
翻译自 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部分——计算力学的中心假定概要——并从那里继续。
II. 斑图
为了介绍我们的方法——同时去论证有些方法是必要的——发现和描述自然界中的斑图，我们开始引用豪尔赫·路易斯·博尔赫斯（Jorge Luis Borges ，1899年8月24日-1986年6月14日，男，阿根廷诗人、小说家、散文家兼翻译家，被誉为作家中的考古学家。）：
这些含糊，多余，缺失让人想起弗兰茨·库恩（Dr. Franz Kuhn，德国汉学家）在一本特定的中文百科全书所描绘的特性，标题为“善意学问的中国百家（Celestial Emporium of Benevolent Knowledge）”。在这些远古的书中写到：动物分成（a）属于帝王的，（b）做过防腐处理的，（c）训练过的