计算力学

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
涌现仿真讨论 | 贡献2024年7月27日 (六) 12:01的版本 →‎简介 首次加入脚注,或称引用。
跳到导航 跳到搜索

计算力学(Computational Mechanics)是一套方案,用来给具有一定复杂程度的事物建立相应结构,定义一个过程的因果态,并给出一个找出它们的步骤。我们揭示了因果态的表征-一个ϵ-机器-拥有最小复杂度的同时又能拥有最准确的预测能力。我们在ϵ-机器最优化和唯一性上,以及如何将ϵ-机器同其他表征进行比较上,获得了一些成果。更多结果关联了随机性测量和结构复杂度,获得于ϵ-机器,可遍历性以及信息理论。

简介

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

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

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

计算力学的基本想法在十年前介绍过。从那时起,他们用于用于动态系统,蜂窝自动化,隐式马尔可夫模型,改进的空间计算,随机共振,全局耦合的地图,和水龙头滴水实验。尽管有这些成功的应用记录,关于这个主题的数学基础,还存在一些不确定的东西。从结构方面来看,ϵ-机制在捕捉一个过程固有的斑图和用最小方式实现上,是很显然的,这个里面发表没有特定的证明。更多地,这里面还没有证明,如果ϵ-机制是以这种方式最优的,它是一个过程唯一的最优表征。这些微小需要的间隙已经补充上了。(译者注:间隙之所以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)美人鱼,(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如何被表征;也就是说,他们的区别是它是如何在一些形式语法的词典被表达的。

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

代数斑图

    虽然斑图发现的问题出现得较早,在柏拉图的美诺篇(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】。

图灵机制:斑图和有效过程

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

    特别地,考虑[math]\displaystyle{ \mathcal{O} }[/math]前面的n个字符[math]\displaystyle{ \mathcal{O}_n }[/math],和生成他们的最短程序[math]\displaystyle{ \mathcal{P}_n }[/math]。我们询问,下式的极限会怎么样

[math]\displaystyle{ \lim_{n \to \infty} \frac{\lvert \mathcal{P}_n \rvert} {n}, }[/math]

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

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

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

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

带有误差的斑图

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

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

随机性:斑图的对立面?

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

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

因果

诸子希望百家对处于动态过程中的斑图所蕴涵的表征具有因果性——即是说明事件的单个状态如何引导或促成另一状态。尽管是个关键性质,我们的研究对因果性的感知却非常微弱,求其弱者是使用数学的休谟【56】:如果事件的一个聚类作为前因总是被后果所跟随,那么可以抽象成前者促成了后者;效应的不变性使其成为原因。作为优秀的非决定论者,接下来我们使用一种基于概率的形式来替换因果继任不变性的概念,用同质继任者们的分布来代换单个不变的继任者。(一个更精确的陈述出现在Ⅳ节A部分因果态的定义里。)这个方法来自对因果性单纯现象级陈述的结果,所以它应该用基于实验性以更强的因果性概念的方式来检验——比如,参考文献【57】的那种——然而并没有。参考文献【58】独立地完成了本质上同我们通过哲学讨论达成的一样的因果性的概念。

斑图摘要

    经过了这些观察,理想的,综合性的斑图方法应该立现:

  • 1. 代数的,让我们以一种明确的方式将斑图拆分或解构成它的部件;
  • 2. 计算性,展示过程如何存储和利用信息;
  • 3. 算术的,分析或系统性近似;
  • 4. 因果,告诉我们斑图实例是如何确切生成的;和
  • 5. 天然地随机性,不单单容忍噪声,而且明确地用系综术语公理化。

综合后确实就是我们声明的佳酿,不谦虚地说,可以随时取用。

系综中的斑图:奥卡姆水池周边的补充

    有一个斑图P是允许我们预测的一些知识,比偶然稍好一些,如果可能的话,是从系综O描绘的序列未来:P需要是统计上精确的,而且同时赋予一些杠杆作用或优势。让我们修正一些观念并陈述稍后让我们证明基本结果的假设。

隐式过程

    我们限制我们在离散值,离散时间稳态随机过程。(参阅Ⅶ节 B部分关于这些假设的讨论)直观地,这些过程是一序列的随机变量[math]\displaystyle{ S_i }[/math],值是从可数集[math]\displaystyle{ \mathcal{A} }[/math]中描述的。我们让i覆盖所有整数范围,因此得到一个双向无穷序列

[math]\displaystyle{ \overleftrightarrow{S} = \cdots S_{-1} S_0 S_1 \cdots . \tag {2} }[/math]

实际上,我们用分布的术语定义一个过程;cf. 参考文献【59】。

定义1(一个过程)让[math]\displaystyle{ \mathcal{A} }[/math]是一个可数集。让[math]\displaystyle{ Ω=\mathcal{A}^Z }[/math]是双向无穷序列,值由[math]\displaystyle{ \mathcal{A} }[/math]的元素组成,[math]\displaystyle{ T_i : Ω \mapsto \mathcal{A} }[/math]是返回双向无穷序列[math]\displaystyle{ ω \in Ω }[/math][math]\displaystyle{ i^{th} }[/math]个元素[math]\displaystyle{ s_i }[/math]的函数,而F是Ω柱集的域。添加一个概率测度P给我们一个概率空间(Ω, F, P),带有附加的随机变量[math]\displaystyle{ \overleftrightarrow{S} }[/math]。一个过程是一个随机变量序列[math]\displaystyle{ S_ i = T_ i(\overleftrightarrow{S}),\ i \in \mathbb{Z} }[/math]。 这里,自始至终地,我们遵从习惯,使用大写字母来表示随机变量,而使用小写字母来表示它们的特定取值。

    从定义延展过来,有一个对有限长度序列的良好定义的概率分布。让[math]\displaystyle{ \overset{\to L}{S_ t} }[/math][math]\displaystyle{ S_ t, \ S_ {t+1}, \ \cdots, S_ {t+L-1} }[/math][math]\displaystyle{ S_ t }[/math]开始的L个随机变量,[math]\displaystyle{ \overset{\to 0}{S_ t} \equiv \lambda }[/math],是空序列。同样,[math]\displaystyle{ \overset{\leftarrow L}{S_ t} }[/math]代表结束于[math]\displaystyle{ S_t }[/math]的L个随机变量的序列,但并不包含[math]\displaystyle{ S_t }[/math][math]\displaystyle{ \overset{\leftarrow L}{S_ t} = \overset{\to L}{S}_ {t-L} }[/math][math]\displaystyle{ \overset{\to L}{S_ t} }[/math][math]\displaystyle{ \overset{\leftarrow L}{S_ t} }[/math]都从[math]\displaystyle{ s_L \in \mathcal{A}^L }[/math]中获取特定值。类似地,[math]\displaystyle{ \overset{\to L}{S_ t} }[/math][math]\displaystyle{ \overset{\leftarrow L}{S_ t} }[/math]是准无限序列,他们分别从t开始和结束于t,并相应从[math]\displaystyle{ \overset{\to}{s} }[/math][math]\displaystyle{ \overset{\leftarrow }{s} }[/math]获取特定值。

    直观地,我们可以想象,开始于有限长度序列的分布,并逐步向两端扩展,直到达到无限长度的序列才停止。当然把这个放在意识中是有用的图景,这样来定义过程引起了一些微妙的测量理论上的问题,比如如何把有限空间分布限制在无限空间里【60,ch. 7】。为了避免这些问题,我们从无限空间分布开始。

定义2(稳态)一个过程[math]\displaystyle{ S_i }[/math]是稳态的,当且仅当

[math]\displaystyle{ P(\overset{\to L}{S_ t} = \mathcal{s}^L) = P(\overset{\to L}{S_ 0} = \mathcal{s}^L), \tag {3} }[/math]

对所有的[math]\displaystyle{ t \in \mathbb{Z} }[/math][math]\displaystyle{ L \in \mathbb{Z}^+ }[/math],而且所有[math]\displaystyle{ s^L \in \mathcal{A}^L }[/math]。 换句话来说,一个稳态过程是随时间不变的。结果就是,[math]\displaystyle{ P(\overset{\to}{S_ t} = \overset{\to}{s}) = P(\overset{\to}{S_ 0} = \overset{\to}{s}) }[/math],并且[math]\displaystyle{ P(\overset{\gets}{S_ t} = \overset{\gets}{s}) = P(\overset{\gets}{S_ 0} = \overset{\gets}{s}) }[/math],所以我们从现在开始去掉下标。

水池

    我们的目标是使用一个函数,利用[math]\displaystyle{ \overset{\gets}{S} }[/math]的一部分来作为输入,预测[math]\displaystyle{ \overset{\to}{S} }[/math]所有或者部分。我们由获取[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]的集合开始,并将它划分成不同的相互独立的部分,连带综合各个子集。也就是说,我们构建一个过去子集的类[math]\displaystyle{ \mathbfcal{R} }[/math]。(参阅图1的示意图的例子)每一个[math]\displaystyle{ ρ \in \mathbfcal{R} }[/math]将被称为一个状态或一个有效状态。当现在的历史[math]\displaystyle{ \overset{\gets}{s} }[/math]包含在集合ρ中,我们会说过程处于状态ρ中。因此,我们定义从历史到有效状态的函数:

[math]\displaystyle{ η: \overset{\gets}{\mathbf{S}} \mapsto \mathbfcal{R}. \tag{4} }[/math]

一个特定的单独的历史[math]\displaystyle{ \overset{\gets}{s} \in \overset{\gets}{\mathbf{S}} }[/math]映射为一个特定的状态[math]\displaystyle{ ρ \in \mathbfcal{R} }[/math];过去的随机变量[math]\displaystyle{ \overset{\gets}{S} }[/math]映射到有效状态的随机变量R。这里有一点区别,对于我们是否将η想象为从历史到历史子集的函数,还是从历史到子集标签的函数。每一种解释在不同时间都有其方便之处,我们两者都会用到。

注意到我们可以使用任意定义在[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]上的函数,用来分割对应集合。赋予同样的ρ给所有的[math]\displaystyle{ \overset{\gets}{s} }[/math]的历史,该函数能获得同样的值。类似地,任意在[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]上的等价关系也能分割它。(请参阅附录B以获取更多等价关系)由于我们定义过程分布的方式,每个实际状态都有良好定义的未来分布,通过非必然的唯一值。指定实际状态的数值去作为关于过程未来的预测。所有附属于给定实际状态的历史在预测未来的目标上是等价的。(在这种方法里,框架形式上结合了传统的时间序列分析方法;参阅附录G1。)

图1。一张集合[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]的分区示意图,所有的历史都分到一些实际状态类中:[math]\displaystyle{ \mathbfcal{R} = \{\mathcal{R}_i :i = 1,2,3,4\} }[/math]。注意到[math]\displaystyle{ \mathcal{R}_i }[/math]不能形式紧致集;我们以清晰明了的方式简单地绘制他们。有人应该意识到康托集或其他更病态的结构。

我们将所有历史集合[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]的所有划分[math]\displaystyle{ \mathbfcal{R} }[/math]的聚集叫奥卡姆水池。

一些信息论

1. 熵的定义

    给定一个从可数集合中取值的随机变量X,X的熵是

[math]\displaystyle{ H [X] \equiv - \sum_{x \in \mathcal A } P(X = x)\log_{2}P(X = x). \tag {5} }[/math]

加入 0log0 = 0。注意到H[X]是[math]\displaystyle{ -\log_2P(X=x) }[/math]的期望值,而且测量单位是信息比特。特别注意“当和收敛到有限值”的形式在所有状态中是隐性的,这些关于熵的状态出自可数集A。     香农将H[X]表示成X的不确定度。(这些对任何主观部分的猜疑,比如“不确定”的观念,可以就地读作“实现变量”。)他展示了,比如,H[X]是对和错问题数量的均值,这些问题需要在重复实验中能选定X的值,如果这些问题被选中去最小化这个平均值【55】。

2.联合和条件熵     我们以直观的方式定义两个变量X(从A中取值)和Y(从B从取值)的联合熵H(X, Y) ,

[math]\displaystyle{ H [X, Y] \equiv - \sum_{(x,y) \in \mathcal A \times \mathcal B} P(X = x, Y = y)\log_{2}P(X = x, Y = y). \tag {6} }[/math]

我们定义一个随机变量的条件熵H(X|Y),是在已知Y值的情况下,得到的条件熵

[math]\displaystyle{ H [X \vert Y] \equiv H [X, Y] - H [Y]. \tag {7} }[/math]

这是从条件概率的定义自然衍生出来的,毕竟[math]\displaystyle{ P(X = x \vert Y = y) \equiv P(X = x, Y = y) / P(Y = y) }[/math]。H[X | Y] 测量一旦我们已知Y值时保留在X中的不确定性。

3. 互信息     两个变量之间的互信息I[X;Y]定义为 [math]\displaystyle{     I(X;Y) \equiv H(X) - H(X \vert Y). \tag{8} }[/math] 这是固定Y时关于X产生的平均不确定性的减少量。它是非负的,如同这里所有的熵,而且在两个变量间是对称的。

系统中的斑图

    如果有一种讨论将来的不确定性将是十分方便地。直观地这将是[math]\displaystyle{ H[\overset{\to}{S}] }[/math],但是在一般情况下数值是无限的,操作起来也是十分棘手的。([math]\displaystyle{ H[\overset{\to}{S}] }[/math]是有限的特殊情形已经在附录F中处理过。)正常情况下,我们由考虑[math]\displaystyle{ H[\overset{\to L}{S}] }[/math]来回避这个问题,下L个符号的不确实性,由L的函数处理。在一些时候,我们将参考每一个符号的熵或熵速率【55,62】:

[math]\displaystyle{ h[\overset{\to}{S}] \equiv \lim_{L \to \infty} \frac{1}{L} H[\overset{\to L}{S}]. \tag{9} }[/math]

并且条件熵速率,

[math]\displaystyle{ h[\overset{\to}{S} \vert X] \equiv \lim_{L \to \infty} \frac{1}{L} H[\overset{\to L}{S} \vert X]. \tag{10} }[/math]

其中,X是一些随机变量,而且极限存在。对于统计随机过程,极限一直存在【62,定理 4.2.1,p. 64】。

    这些熵速率也是一直存在H[S]的上限;特殊情况是等式(附录3)。更有,如果[math]\displaystyle{ h[\overset{\to}{S}] = H[S] }[/math],过程对应到的无关变量,实际上,实际上我们在这里仅仅关心统计过程。


定义3(捕捉斑图)R捕获一个斑图当且仅当存在一个L,使得

[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] \lt LH[S]. \tag{11} }[/math]

这就是说[math]\displaystyle{ \mathbfcal{R} }[/math]捕获一个斑图,当它能告诉我们影响彼此的过程,各部分的分布:[math]\displaystyle{ \mathbfcal{R} }[/math]展示了它们的依赖关系。(我们也说η,关联于过于的函数,捕获了一个斑图,自从隐含了[math]\displaystyle{ \mathbfcal{R} }[/math]获捉一个斑图。)假设这些部分不影响彼此,然后我们拥有IID随机变量,他们最接近直观的“斑图”的概念,因为它可以被数学化地陈述。注意到,因为在联合熵上的不相关界限(Eq.(A3)),如果不相等条件由一些L所满足,它也为每个[math]\displaystyle{ L' \gt L }[/math]所满足。因此,我们可以考虑差值[math]\displaystyle{ H[S] - H[\overset{\to L}{S} \vert \mathcal{R}]/L }[/math],找到最短不是零的L,作为由[math]\displaystyle{ \mathbfcal{R} }[/math]捕获的斑图的长度。我们将给斑图长度标记一个上界(引理1);后续我们将展示如何取得这个上界(定理1)。

历史的课程

我们现在处在证明系统斑图结果的位置,可用于连接后续关于因果态的定理。

引理1(旧世界引理)对于所有的[math]\displaystyle{ \mathbfcal{R} }[/math]和所有的[math]\displaystyle{ L \in \mathbb{Z}^+ }[/math]

[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] \ge H[\overset{\to L}{S} \vert \overset{\leftarrow}{S}]. \tag{12} }[/math]

    证明。由构造可知(等式4),对于所有L,

[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] = H[\overset{\to L}{S} \vert η(\overset{\leftarrow}{S})]. \tag{13} }[/math]

但是

[math]\displaystyle{ H[\overset{\to L}{S} \vert η(\overset{\leftarrow}{S})] \ge H[\overset{\to L}{S} \vert \overset{\leftarrow}{S}]. \tag{14} }[/math]

因此在一个变量上的条件熵永不大于一个变量上的函数的条件熵(Eq.(A14)). 证毕。

    备注1。也就是说,在全部过去的条件下,最大程度地降地了在将来的不确定性。从全部准无限的过去中截取是笨重和不安以及前景有些灰暗的。用不同的方式来做:我们希望尽可能多忘掉过去,以致能减少负担。这个目标跟等式(12)的结果是相反的,所以引发我们叫它旧世界引理。         备注2。引理1如前所述建立了斑图强度的上界,也就是,斑图的强度最多就是[math]\displaystyle{ H[S] - H[\overset{\to L}{S} \vert \overset{\leftarrow}{S}]/L_{past} }[/math],其中[math]\displaystyle{ L_{past} }[/math]是满足[math]\displaystyle{ H[\overset{\to L}{S} \vert \overset{\leftarrow}{S}] \lt LH[S] }[/math]的L的最小值。    

最小化和预测

    让我们引用奥卡姆剃刀原则:“有些事情只需抓住关键点,做得太多的话就是徒劳”【63】。为了使用剃刀,我们需要修正什么是“完成”和什么是“更多”和“更少”的含义。我们希望完成的工作是准确地预测,比如,尽可以地降低条件熵[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] }[/math]。目标就变成了获取由引理1导出的界限。我们希望尽可能简单地完成它,尽可能使用最少的资源。在见识过这两个约束的道路上——最小化不确定性和最小化资源——我们需要有第二者的测量方法。因为[math]\displaystyle{ P(\overset{\gets}{S} = \overset{\gets}{s}) }[/math]是定义好的,这里有一个在η-状态之上的简化测量方法;比如,[math]\displaystyle{ P(\mathcal{R} = ρ) }[/math],处于任意单个实际状态的概率,也定义好了。对应地,我们定义资源的测量方法。

定义4(因果态的复杂度)状态类[math]\displaystyle{ \mathbfcal{R} }[/math]统计复杂度

[math]\displaystyle{ \begin{aligned} C_{μ}(\textbf {R}) & \equiv H[R] \ (15) \\  & = - \sum_{ρ \in \mathcal R } P(\mathcal R = ρ)\log_{2}P(\mathcal R = ρ). \\ \end{aligned} }[/math]

当和收敛到一个有限值。

μ中[math]\displaystyle{ C_{μ} }[/math]中提示我们它有着量化理论的特性,并且最终依赖于过程序列的分布,能导出状态上的测量。

一个状态类的统计复杂度是平均不确定度(单位是比特),在此过程的当前状态。这个,换句话说,是跟平均存储数量(单位是比特)一样,过程看上去是在保持过去,在给定选定的状态类[math]\displaystyle{ \mathbfcal{R} }[/math]的条件下。(我们晚一点,在定义12中,查看如果定义一个过程它自己的统计复杂度。)这个目标是在尽可能少的存储下完成。再次申明,我们希望最小化统计复杂度,并符合最大准确预测的限制。

之所以称呼[math]\displaystyle{ \overset{\gets}{S} }[/math]的所有划分为奥卡姆水池背后的想法也应当清楚了。一个原因就是想找到水池当中最浅层的地方。 这就是我们刚刚做的。

计算力学

那些擅长射箭运动的人,是从弓,而非从弋射手上习得。那些知道如何驾船的人,是从船,而非从倭人所习得。

——佚名参考文献【64】。

    计算力学的最终目标是去识别过程内在的斑图。也就是说,最可能地,目标是让过程描述自己,用它自己的词语,不需要诉诸于一个关于过程结构的前提假设。这里我们简单地在这些目标中探寻一致性和规范定义。当然,实际约束或许让我们只需极度地多或少逼近这些想法,而无需做太多。更自然地,这些问题,在实现中总是会出现,如果我们开始于安全的基础,是很容易定位的。

因果态

定义5(一个过程的因果态)一个过程的因果态是一系列函数ϵ的成员,[math]\displaystyle{ ϵ : \overset{\leftarrow}{\mathbf{S}} \mapsto 2^{\overset{\leftarrow}{\mathbf{S}}} }[/math]——[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]的幂集:

[math]\displaystyle{ ϵ[\overset{\leftarrow}{S}] \equiv \{\overset{\leftarrow '}{s} \vert P(\overset{\to}{S} = \overset{\to}{s} \vert \overset{\leftarrow}{S} = \overset{\leftarrow}{s}) = P(\overset{\to}{S} = \overset{\to}{s} \vert \overset{\leftarrow}{S} = \overset{\leftarrow '}{s}), 对所有\ \overset{\to}{s} \in \overset{\to}{S}, \overset{\leftarrow '}{s} \in \overset{\leftarrow}{S} \} \tag{16} }[/math]

它将历史映射到历史集合,我们将第i个[math]\displaystyle{ i^{th} }[/math]因果态写成[math]\displaystyle{ S_i }[/math],并将所有因果态的集合写成[math]\displaystyle{ \mathbfcal{S} }[/math];对应的随机变量描述成[math]\displaystyle{ \mathcal{S} }[/math],它的实现写为[math]\displaystyle{ σ }[/math]

    [math]\displaystyle{ \mathbfcal{S} }[/math]的基数没有特别说明。[math]\displaystyle{ \mathbfcal{S} }[/math]可以是有限的,可数无限的,一个连续体,一个康托集,或一些奇异定格。这些例子在参考文献【5】和【10】中给出;特别查阅那里给出的隐马尔可夫模型的例子。     可替换的也是等价的,我们可以定义等价关系[math]\displaystyle{ 〜_ϵ }[/math]如两段历史是等价的当且仅当它们拥有相同的未来条件分布,并且定义因果态为由[math]\displaystyle{ 〜_ϵ }[/math]生成的等价类。(实际上,这是文献【6】的原始方法。)不管什么方法,[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]的这种划分的切分由区域建成,这些区域使我们在不同条件下对未来有一些无知。

    最后的陈述建议了另一种,仍然等价,对ϵ的描述:

[math]\displaystyle{ ϵ[\overset{\leftarrow}{S}] \equiv \{\overset{\leftarrow '}{s} \vert P(\overset{\to L}{S} = \overset{\to L}{s} \vert \overset{\leftarrow}{S} = \overset{\leftarrow}{s}) = P(\overset{\to L}{S} = \overset{\to L}{s} \vert \overset{\leftarrow}{S} = \overset{\leftarrow '}{s}), \overset{\to L}{s} \in \overset{\to L}{S},\overset{\leftarrow '}{s} \in \overset{\leftarrow}{S}, L \in \mathbb{Z}^+ \} \tag{17} }[/math]

使用这个我们可以构建初始的定义,等式【16】,将所有在每个新划分的历史空间[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]划分成序列就更加直观了。使用L+1导出,是对使用L导出的细化。在最粗糙的级别上,最前面的划分(L = 1)组成了那些历史,对于每一个下个观测有相同分布。这些类就使用下两个观测值的分布做细分,然后是下三个,四个,以此类推。这些划分序列的极限——到那个点,点里每个类中的每个成员都有着对未来相同分布,不管长度如何,同那个类中的每个其它成员一样——是由∼ϵ导出的[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]的划分。参阅附录B以获取更详细的讨论并查看∼ϵ的等价关系。

    虽然他们不会直接关心以下的部分,因为时间渐近的限制存在,有短暂的因果态添加到在等式【16】中定义的(循环)因果态。大致地说,短暂的因果态描述了怎样延长观测序列(一段历史)以使我们去用标识循环因果态并提升准确性。可查阅附录B和参考文献【10】和【65】中的发展,以了解瞬时因果态的详情。         因果态是实际状态的一种特殊种类,他们拥有对实际状态来说普遍的属性(第Ⅲ节B部分)。在特殊情况下,每个因果态[math]\displaystyle{ \mathcal{S}_i }[/math]拥有若干结构附加:     1. 索引i——状态的“名称”。

2.将过程带到[math]\displaystyle{ \mathcal{S}_i }[/math]的历史集合,我们视为[math]\displaystyle{ \{\overset{\gets L}{s} \in \mathcal{S}_i\} }[/math]

3.在未来的条件分布,表示为[math]\displaystyle{ P(\overset{\to}{S} \vert \mathcal{S}_i) }[/math],并等于[math]\displaystyle{ P(\overset{\to}{S} \vert \overset{\gets}{s}),\overset{\gets}{s} \in \mathcal{S}_i }[/math]。自从我们倾向于分布频率这一种,而且自从它是“未来的图景”,我们称它为状态的变体。

理想情况下,这些的每一个都应由不同的符号表示,而且应该是清晰的函数,链接每个结构到他们的因果态。为了保持术语增涨受控,尽管这样,我们还是战略性地模糊掉他们的区别。读者或许以各种方式绘制ϵ为映射历史到(i)简单索引,(ii)历史的子集,或(iii)索引、子集、和变体的有序三元组;或甚至某人让ϵ没有解释性,如同偏好所向,不干涉随后的发展。

图 2. 一个表示将所有历史的集合[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]划分到因果态[math]\displaystyle{ \mathcal{S}_i \in \mathbfcal{S} }[/math]的示意图。在每个因果态中所有的单独历史[math]\displaystyle{ \overset{\gets}{s} }[/math]拥有相同的变体——对将来对测相同的条件分布[math]\displaystyle{ P(\overset{\to}{S} \vert \overset{\gets}{s}) }[/math]

1. 变体

    每一个因果态拥有独特的变体,比如,没有两个因果态拥有对未来相同的条件分布。这条直接来自定义5,而且它一般不是实际状态。另一个定义的直接结果是

[math]\displaystyle{ P(\overset{\to}{S}= \overset{\to}{s} \vert S = ϵ(\overset{\leftarrow}{s})) = P(\overset{\to}{S} = \overset{\to}{s} \vert \overset{\leftarrow}{S} = \overset{\leftarrow}{s}). \tag{18} }[/math]

(再一次,这点对实际状态通常不是真的。)这种观测让我们证明一个有用的引理,关于过去[math]\displaystyle{ \overset{\gets}{S} }[/math]和未来[math]\displaystyle{ \overset{\to}{S} }[/math]条件无关。

引理2 过去和未来是无关的,在因果态的分布上。

    证明。回忆起两个随机变量X和Z是条件无关的,当且仅当有第三个变量Y符合

[math]\displaystyle{ P(X = x, Y = y, Z = z) = P(X = x \vert Y = y)P(Z = z \vert Y = y)P(Y = y) . \tag{19} }[/math]

也就是,所有Z在X上的依赖,已经被Y斡旋了。为了接下来的描述方便,我们提出,重构条件分布,等同于约束:

[math]\displaystyle{ P(X = x, Y = y, Z = z) = P(Z = z \vert Y = y)P(Y = y \vert X = x)P(X = x) . \tag{20} }[/math]


    让我们考虑[math]\displaystyle{ P(\overset{\leftarrow}{S}=\overset{\leftarrow}{s}, S = σ, \overset{\to}{S}=\overset{\to}{s}). }[/math]

[math]\displaystyle{ \begin{aligned} P & (\overset{\leftarrow}{S}=\overset{\leftarrow}{s}, S = σ, \overset{\to}{S}=\overset{\to}{s}) \ (21) \\ & = P(\overset{\to}{S}=\overset{\to}{s} \vert S = σ, \overset{\leftarrow}{S}=\overset{\leftarrow}{s})P(S = σ, \overset{\leftarrow}{S}=\overset{\leftarrow}{s}) \\ & = P(\overset{\to}{S}=\overset{\to}{s} \vert S = σ, \overset{\leftarrow}{S}=\overset{\leftarrow}{s})P(S = σ \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s})P(\overset{\leftarrow}{S}=\overset{\leftarrow}{s}) . \end{aligned} }[/math]


现在,[math]\displaystyle{ P(\mathcal{S} = ρ \vert \overset{\gets}{S} = \overset{\gets}{s}) = 0 }[/math], 直到[math]\displaystyle{ ρ = ϵ(\overset{\gets}{s}) }[/math], 在这种情况[math]\displaystyle{ P(\mathcal{S} = ρ\vert \overset{\gets}{S} = \overset{\gets}{s}) = 1 }[/math]. 每种情况,在等式(21)最后一行前面两个因子可以写成等式(18),

[math]\displaystyle{ P(\overset{\to}{S}=\overset{\to}{s} \vert S = σ, \overset{\leftarrow}{S}=\overset{\leftarrow}{s})P(S = σ \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s}) \tag{22} \\ = P(\overset{\to}{S}=\overset{\to}{s} \vert S = σ)P(S = σ \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s}) , }[/math]

因此,将等式(22)替换回等式(21),

[math]\displaystyle{ P(\overset{\leftarrow}{S}=\overset{\leftarrow}{s}, S = σ, \overset{\to}{S}=\overset{\to}{s}) \tag{23} \\ = P(\overset{\to}{S}=\overset{\to}{s} \vert S = σ)P(S = σ \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s})P(\overset{\leftarrow}{S}=\overset{\leftarrow}{s}) . }[/math]

证毕。

    2.同质性         根据参考文献【58】,我们介绍两个新定义和一个引理,后面需要用到,尤其在证明引理7和依赖这个引理的定理过程中。     定义6 (强同质性)一个集合X是强同质性的,对应着一个指定的随机变量Y,当关于Y的条件分布P(Y|X)对所有X的子集都相同。

定义7(弱同质性)一个集合X是弱同质性的,如果对应Y不是强同质性,但X\X0(在X中将X0移除后的集合)是,当X0是测度为0的X的子集。

引理3 (因果态的强同质性) 一个过程的因果态是历史的最大子集,对应所有长度的未来是强同质性的。

    证明. 我们必须展示,首先,因果态是强同质性,对应所有长度的未来,其次,没有做成更大的历史的强同质性子集。第一个要领,因果态的强同质性,证据来自等式(17):由建造方法,因果态的所有元素有相同的变体,因此因果态的任意部分将拥有作为全部状态的相同变体。第二点就是同样根据等式(17),自从因果态自构造时包含了所有带有变体的历史。所有其他的集合对应未来的强同质性必然小于一个因果态,而且任何包含作为适当子集的因果态集合不能是强同质性。证毕。         备注。统计解释用语应该说因果态是“为因果解释的统计-关系基础”。这种基础的元素是,准确地说,无关变量的集合的最大类,对关联变量带有同质分布。参阅参考文献【58】以获取更多关于这些内容的讨论。

因果状态到状态的转换

        在任意给定时间的因果态和观测过程的下一个值共同决定新的因果态;这点在引理5中做了简短证明。因此,一段因果态继任者有自然联系。回忆第二节E部分关于原因的讨论。更多地,给定当前因果态,所有可能的下一个值已经定好定义了条件分布。实际上,由构建可知全部准无限未来也如此。因此,有良好定义的过程的分布[math]\displaystyle{ T_{ij}^{(s)} }[/math]生成的值[math]\displaystyle{ s \in \mathcal{A} }[/math]并转换到因果态[math]\displaystyle{ \mathcal{S}_j }[/math],如果它在[math]\displaystyle{ \mathcal{S}_i }[/math]状态中。

定义8(因果转换)已经标记的转换概率[math]\displaystyle{ T_{ij}^{(s)} }[/math]是促成状态Si到Sj转换的概率,并发出符号[math]\displaystyle{ s \in \mathcal{A} }[/math]:

[math]\displaystyle{ T_{ij}^{(s)} \equiv P(S'=S_{j}, \overset{\to 1}{S}=s \vert S = S_i), \tag{24} }[/math]

其中S是当前因果态,并且S'是它发出s的继任者。我们用[math]\displaystyle{ \mathbf{T} }[/math]表示集合[math]\displaystyle{ T_{ij}^{(s)} : s \in \mathcal{A} }[/math]

引理4(转移概率)[math]\displaystyle{ T_{ij}^{(s)} }[/math]由下式给出

[math]\displaystyle{ \begin{aligned} T_{ij}^{(s)} & = P(\overset{\leftarrow}{s}s \in S_{j} \vert \overset{\leftarrow}{s} \in S_{i}) \ (25) \\ & = \frac{P(\overset{\leftarrow}{s} \in S_{i}, \overset{\leftarrow}{s}s \in S_{j})}{P(\overset{\leftarrow}{s} \in S_{i})} , \ (26) \end{aligned} }[/math] 其中[math]\displaystyle{ \overset{\gets}{s}s }[/math]读作准无限序列,由在[math]\displaystyle{ \overset{\gets}{s} }[/math]的末尾连接[math]\displaystyle{ s \in \mathcal{A} }[/math]获得。

    证明。 [math]\displaystyle{ \begin{aligned} T_{ij}^{(s)} & = P(S'=S_{j}, \overset{\to 1}{S}=s \vert S = S_i) \ (27) \\ & = \frac{P(S'=S_{j}, \overset{\to 1}{S}=s, S = S_i)}{P(S = S_i )}. \ (28) \end{aligned} }[/math]

现在 [math]\displaystyle{ \mathcal{S} = \mathcal{S}_i }[/math]当有仅当 [math]\displaystyle{ \overset{\gets}{s} \in \mathcal{S}_i }[/math], 并且 [math]\displaystyle{ \mathcal{S}' = \mathcal{S}_j }[/math]当且仅当[math]\displaystyle{ \overset{\gets '}{s} \in \mathcal{S}_j }[/math],其中[math]\displaystyle{ \overset{\gets '}{s} }[/math]我们表示紧随[math]\displaystyle{ \overset{\gets }{s} }[/math]其后的历史;为了统一,[math]\displaystyle{ \overset{\gets '}{s} = \overset{\gets}{s}s }[/math]。所以我们可以重写等式(28)如

[math]\displaystyle{ \begin{aligned} T_{ij}^{(s)} & = \frac{P(\overset{\leftarrow}{s} \in S_i, \overset{\to 1}{S}=s, \overset{\leftarrow '}{s} \in S_j)}{P(S = S_i)} \ (29) \\ & = \frac{P(\overset{\leftarrow}{s} \in S_i, \overset{\to 1}{S}=s, \overset{\leftarrow}{s}s \in S_j)}{P(S = S_i)} \ (30) \\ & = \frac{P(\overset{\leftarrow}{s} \in S_i, \overset{\leftarrow}{s}s \in S_j)}{P(S = S_i)}. \ (31) \end{aligned} }[/math]

在第三行我们使用[math]\displaystyle{ \overset{\gets}{S}=\overset{\gets}{s} }[/math][math]\displaystyle{ \overset{\gets '}{S}=\overset{\gets}{s}s }[/math]的事实联合表明[math]\displaystyle{ \overset{\gets 1}{S} = s }[/math],使得条件相同。证毕。

    注意到[math]\displaystyle{ T_{ij}^{(λ)} = δ_{ij} }[/math];也就是,由空符号λ标志的转换是同一个。    

ϵ-机器

从历史到因果态带有标记的转换概率[math]\displaystyle{ T_{ij}^{(s)} }[/math]的函数ϵ组合称作过程的ϵ-机器【5,6】。

定义9(一个ϵ-机器定义)

一个过程的ϵ-机器是有序对[math]\displaystyle{ \{ϵ,\mathbf{T}\} }[/math],其中ϵ是因果态函数而[math]\displaystyle{ \mathbf{T} }[/math]是由ϵ定义的状态转换矩阵。

等同地,我们或许由[math]\displaystyle{ \{\mathbfcal{S}, \mathbf{T}\} }[/math]表示一个ϵ-机器。

为了符合第II节F代数要求,我们显式构造同半群理解的联系。

命题 1(ϵ-机器是幺半群)由ϵ-机器[math]\displaystyle{ \{ϵ, \mathbf{T}\} }[/math]生成的代数是带单位元的半群, 也就是,它是幺半群。

证明。参看附录D。

备注。因为这个,ϵ-机制可以被解释为捕获一个过程的一般对称性。任意ϵ-机制的半群的子群是,其实,在更熟悉的意义上呈现对称。

引理 5(ϵ-机器是决定性的)对于每一个[math]\displaystyle{ \mathcal{S}_i }[/math][math]\displaystyle{ s \in \mathcal{A} }[/math][math]\displaystyle{ T_{ij}^{(s)}\gt 0 }[/math]只对于那些[math]\displaystyle{ \mathcal{S}_j }[/math]对于[math]\displaystyle{ ϵ(\overset{\leftarrow}{s}s)=\mathcal{S}_j }[/math]当且仅当[math]\displaystyle{ ϵ(\overset{\leftarrow}{s})=\mathcal{S}_i }[/math],对于所有的过去[math]\displaystyle{ \overset{\leftarrow}{s} }[/math]

证明。这个引理是断言的等价,对所有[math]\displaystyle{ s \in \mathcal{A} }[/math][math]\displaystyle{ \overset{\gets}{s},\overset{\gets '}{s} \in \overset{\gets}{\mathbf{S}} }[/math],如果[math]\displaystyle{ ϵ(\overset{\gets}{s}) = ϵ(\overset{\gets'}{s}) }[/math],则[math]\displaystyle{ ϵ(\overset{\gets}{s}s) = ϵ(\overset{\gets '}{s}s) }[/math]。([math]\displaystyle{ \overset{\gets}{s}s }[/math]是另一段历史且附属于这个或那个因果态。)

    假设这点不对。就有存在至少一个将来的[math]\displaystyle{ \overset{\to}{s} }[/math]符合

[math]\displaystyle{ P(\overset{\to}{S} = \overset{\to}{s} \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s}s) \not = P(\overset{\to}{S} = \overset{\to}{s} \vert \overset{\leftarrow}{S}=\overset{\leftarrow '}{s}s) \tag{32} }[/math]

尽管[math]\displaystyle{ ϵ(\overset{\gets}{s}) = ϵ(\overset{\gets '}{s}) }[/math]。等价地,我们应该有

[math]\displaystyle{ \frac{P(\overset{\leftrightarrow}{S} = \overset{\leftarrow}{s}s\overset{\to}{s})} {P( \overset{\leftarrow}{S}=\overset{\leftarrow}{s}s)} \not = \frac{P(\overset{\leftrightarrow}{S} = \overset{\leftarrow '}{s}s\overset{\to}{s})}{P( \overset{\leftarrow}{S}=\overset{\leftarrow '}{s}s)} \tag{33} }[/math]

其中我们将[math]\displaystyle{ s\overset{\to}{s} }[/math]读为准无限字符串,开始于s而由[math]\displaystyle{ \overset{\to}{s} }[/math]继续。(记住,我们打破随机过程的点从一个过去到一个未来是武断的。)尽管如此,在分母里的概率是等于[math]\displaystyle{ P(\overset{\to 1}{S} = s \vert \overset{\gets}{S} = \overset{\gets}{s})P(\overset{\gets}{S} = \overset{\gets}{s}) }[/math][math]\displaystyle{ P(\overset{\to 1}{S} = s \vert \overset{\gets}{S} = \overset{\gets '}{s})P(\overset{\gets}{S} = \overset{\gets '}{s}) }[/math],分别地,而且由假设[math]\displaystyle{ P(\overset{\to 1}{S} = s \vert \overset{\gets}{S} = \overset{\gets '}{s}) = P(\overset{\to 1}{S} = s \vert \overset{\gets}{S} = \overset{\gets}{s}) }[/math],由于[math]\displaystyle{ ϵ(\overset{\gets '}{s}) = ϵ(\overset{\gets}{s}) }[/math]。因此,我们应该需要

[math]\displaystyle{ \frac{P(\overset{\leftrightarrow}{S} = \overset{\leftarrow}{s}s\overset{\to}{s})} {P( \overset{\leftarrow}{S}=\overset{\leftarrow}{s})} \not = \frac{P(\overset{\leftrightarrow}{S} = \overset{\leftarrow '}{s}s\overset{\to}{s})}{P( \overset{\leftarrow}{S}=\overset{\leftarrow '}{s})} \tag{34} }[/math]

这也是一样的,然后,因为

[math]\displaystyle{ P(\overset{\to}{S} = s\overset{\to}{s} \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s}) \not = P(\overset{\to}{S} = s\overset{\to}{s} \vert \overset{\leftarrow}{S}=\overset{\leftarrow '}{s}). \tag{35} }[/math]

这也是在说有一个未来[math]\displaystyle{ s\overset{\to}{s} }[/math]有不同的概率依赖于我们是用[math]\displaystyle{ \overset{\gets}{s} }[/math]还是[math]\displaystyle{ \overset{\gets '}s }[/math]的条件。但是这个对立面假设这两段历史附属于相同的因果态。因此,没有这样的未来[math]\displaystyle{ \overset{\to}{s} }[/math],而引理替换的描述是真的。证毕。

    备注1。在自动化理论【66】中,一个状态的集合和转换说是决定性的,如果当前的状态和下一个输入——在这里,是原始随机过程的下一个结果——一并修正下一个状态。这个用语“决定性”通常容易混淆,因为很多随机过程(例如,简单的马尔可夫链)在这种语境下是决定性的。

备注2。从固定状态开始,一个给定的符号总是导向最多一个单状态,但这会有多个从一个状态到另一个的转换,每一个被标记会不同的符号。

备注3。很清楚的是,如果[math]\displaystyle{ T_{ij}^{(s)} \gt 0 }[/math],那么[math]\displaystyle{ T_{ij}^{(s)} = P(\overset{\to 1}{S} = s \vert \mathcal{S} = \mathcal{S}_i) }[/math]。在自动化理论里这个“不允许”转换([math]\displaystyle{ T_{ij}^{(s)} = 0 }[/math])有时候是明显存在的,并且导向一个“弹出”状态指示对应部分历史没有发生。

引理6(因果态是相互不依赖的)因果态上的概率分布在不同时间是条件无关的。

    证明。我们想展示的是,将因果态序列在三个连续的时间步写成[math]\displaystyle{ \mathcal{S}, \mathcal{S}',\mathcal{S}'' }[/math],在给定[math]\displaystyle{ \mathcal{S}' }[/math]后,[math]\displaystyle{ \mathcal{S} }[/math][math]\displaystyle{ \mathcal{S}'' }[/math]是条件无关的。我们可以直接做到这样:

[math]\displaystyle{ \begin{aligned} P & (S = σ, S' = σ', S'' = σ'') \ (36) \\ & = P(S'' = σ'' \vert S = σ, S' = σ')P(S = σ, S' = σ') \\ & = P(\overset{\to 1}{S} \in a \vert S = σ, S' = σ')P(S = σ, S' = σ') , \end{aligned} }[/math]

其中a是所有将σ'导向σ\'\'符号的子集。这是一个良好定义的子集,在引理5的即刻前述的铺垫里,也保证了我们使用过的条件概率相等。类似地,

[math]\displaystyle{ P(S'' = σ'' \vert S' = σ') = P(\overset{\to 1}{S} \in a \vert S' = σ') . \tag{37} }[/math]

但是,经构造式

[math]\displaystyle{ P(\overset{\to 1}{S} \in a \vert S = σ, S' = σ') = P(\overset{\to 1}{S} \in a \vert S' = σ') , \tag{38} }[/math]

并且因此

[math]\displaystyle{ P(S'' = σ'' \vert S' = σ') = P(S'' = σ'' \vert S = σ, S' = σ') , \tag{39} }[/math]

所以,可以继续,

[math]\displaystyle{ \begin{aligned} P & (S = σ, S' = σ', S'' = σ'') \ (40) \\ & = P(S'' = σ'' \vert S' = σ')P(S = σ, S' = σ') \\ & = P(S'' = σ'' \vert S' = σ')P(S' = σ' \vert S = σ) P(S = σ) . \end{aligned} }[/math]

最后一行遵从了概率分布并等价地更容易由表达式给出

[math]\displaystyle{ P(S'' \vert S')P(S \vert S')P(S') \tag{41} }[/math]

因此,由等式(41)导出后应用数学方法,因果态在不同时间片是独立的,条件是在中间的因果态。证毕。

备注1。这个引理加强了申明,该申明说因果态是,实际上,因果上有效的状态:给定当前状态的知识,已经过去之前的些,改变不了什么。(再次,回忆下在第II节E中哲学性的预备内容。)

备注2。这个结果指示出因果态,考虑成一个过程,定义了一个马尔可夫链。因此,因果态可以被大约考虑成马尔可夫状态的生成。我们说“一种”是因为ϵ-机制是基本上更丰富的【5,10】,和通常附加在马尔可夫链上的那些相比。

定义10(ϵ-机制重构)

ϵ-机制重构是任意给定一个过程[math]\displaystyle{ P(\overset{\harr}{S}) }[/math],或[math]\displaystyle{ P(\overset{\harr}{S}) }[/math]的一个近似,生成这个过程的ϵ-机器[math]\displaystyle{ \{\mathbfcal{S}, \mathbf{T}\} }[/math]的流程。

    给定一个过程的数学描述,有人可以经常计算分析它的ϵ-机制。(例如,查阅参考文献【65】中旋转系统的计算力学分析。)这里也有很多宽泛的算法可以从[math]\displaystyle{ P(\overset{\harr}{S}) }[/math]的经验模拟重构ϵ-机制。一些,比如那些在参考文献【5-7,69】中使用到的,操作在“批量”模式,将原始数据一起处理然后生成ϵ-机制。其他的可以操作在增量,处于“在线”模式,将因果态和它们的转移概率集合单独的测量和重新评估。    

最佳性和唯一性

我们现在展示这个:因果态是最高准确度的预测器并且是最小统计复杂度的;他们在共享两者属性中是唯一的;而且他们状态到状态的转换是最小随机性的。用其他的话说,他们满足从奥卡姆借用的两个约束条件,而且他们是唯一能做到这样的表示形式。这个非常重要的寓意在这里是因果态和ϵ-机制是任何学习或模型词汇的目标。该论点由证明最优化理论的久享盛名的意义上作出。我们指出,在我们的结论备注中(第Ⅶ节),在获取这些目标中已经包含了实的例子。

图例3。一个可供替代的状态的类[math]\displaystyle{ \mathbfcal{R} }[/math]划分[math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]覆盖在因果态[math]\displaystyle{ \mathbfcal{S} }[/math]上(由实线绘出)。这里,作为例子,[math]\displaystyle{ \mathcal{S}_2 }[/math]包含[math]\displaystyle{ \mathcal{R_1, R_2, R_3和R_4} }[/math]的部分。这些所有可供替代的部分的集合构成了奥卡姆的水池。再次注意到[math]\displaystyle{ \mathcal{R}_i }[/math]需要不是紧致的也不是简单连接的,如所绘制的那样。

作为我们策略的部分,然后,我们仍要证明几个不是最优化的结果;我们叫这些引理以标识他们的从属状态。所有我们的定理,和一些我们的引理,将由一些方法构造,包括比较因果态,由ϵ生成,用其他状态的等价态集合,由其他函数η生成。简而言之,没有竞争状态——没有其他斑图——可能构造因果态。

修正一些附加的标记法是很方便地。让[math]\displaystyle{ \mathcal{S} }[/math]是当前因果态的随机变量,[math]\displaystyle{ \overset{\to 1}{S} \in \mathcal{A} }[/math]是下一个我们从原始随机过程获得的“可观测的”量,[math]\displaystyle{ \mathcal{S}' }[/math]是下一个因果态,[math]\displaystyle{ \mathcal{R} }[/math]是对应到η的当前态,而[math]\displaystyle{ \mathcal{R}' }[/math]是下一个η状态。σ将表示[math]\displaystyle{ \mathcal{S} }[/math]的一个部分值(因果态),而ρ是[math]\displaystyle{ \mathcal{R} }[/math]的部分值。当我们量化因果态的可替代者时,我们在[math]\displaystyle{ \mathbfcal{R} }[/math]上量化。

定理1(因果态具有最大预测性)【15】

对于所有的[math]\displaystyle{ \mathbfcal{R} }[/math]和所有的[math]\displaystyle{ L \in \mathbb{Z}^+ }[/math]

[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] \ge H[\overset{\to L}{S} \vert \mathcal{S}] \tag{42} }[/math]

证明。我们已经看到[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] \ge H[\overset{\to L}{S} \vert \overset{\gets}{S}] }[/math](引理1)。但是由构造(定义5),

[math]\displaystyle{ P(\overset{\to L}{S} = \overset{\to L}{s} \vert \overset{\leftarrow}{S}=\overset{\leftarrow}{s}) = P(\overset{\to L}{S} = \overset{\to L}{s} \vert S = ϵ(\overset{\leftarrow}{s})) \tag{43} }[/math]

自从熵仅依赖于概率分布,[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{S}] = H[\overset{\to L}{S} \vert \overset{\gets}{S}] }[/math],对于每个L。因此,[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R}] \ge H[\overset{\to L}{S} \vert \mathcal{S}] }[/math],对于所有的L。证毕。

备注。这就是说,因果态在预测未来方面是一样优秀的——作为预测者——作为完整的历史。在这方面,他们符合最开始从奥卡姆处借用的要求。自从因果态是良好定义的,而且自从他们可以被系统性的逼近,我们已经展示了斑图强度(定义3和引理1,备注)的上界在实际上是可以达到的。直观地,因果态达到这个,是因为——不象一般的实际状态,他们没有丢弃任何关于未来的信息,可能包含在S<-中。用更通俗的话讲,为解释参考文献【70】中信息的定义,因果态记录制造不同(去到未来)的每个不同(关于过去)。我们实际上可以非常准确地制造这种直觉,使用定理的一个简单推论。

推论1(因果态是足够统计的)一个过程的因果态S用于预测它是足够统计的。

证明。它遵从于定义1和等式8,对于所有的L∈Z+,

[math]\displaystyle{ I[\overset{\to L}{S}; S] = I[\overset{\to L}{S}; \overset{\leftarrow}{S}], \tag{44} }[/math]

其中I由等式8定义。结果,因果态是足够统计——参阅参考文献【62,p.37】和【71,2.7-2.5节】——为预测任意长度的将来。证毕。

所有随后的结果关注于同因果态一样预知的竞争态。我们称呼这些预知竞争者并用R^将他们归为一类。

定义11(预知竞争者)预知竞争者R^是同因果态一样预知的状态;即,对于所有的L∈Z+,

[math]\displaystyle{ H[\overset{\to L}{S} \vert \hat{R}] = H[\overset{\to L}{S} \vert S], \tag{45} }[/math]

备注。预知竞争者也是足够统计的。

引理7(细化引理)对于所有的预知竞争者R^有对于每一个ρ∈R^,有一个σ∈S和测度为0的子集ρ0^⊂ρ^,可能是空集,可得ρ^\ρ0^⊆σ,其中\是集合相对差集。

证明。我们调用参考文献【62】定理2.7.3的一个直接扩展:如果X1, X2, ...,Xn是同一集合A上的随机变量,每一个带有单独的概率分布,Θ是在正整数之上的随机变量,符合P(Θ = i) = λi,并且Z是A之上的随机变量,符合Z = XΘ,于是

[math]\displaystyle{ \begin{aligned} H[Z] & = H[\sum_{i=1}^nλ_iX_i] \\ & \ge \sum_{i=1}^nλ_iH[X_i] . \end{aligned} }[/math]

可以说,混合概率的熵至少是那些分布熵的均值。这是成立的自从H是严格凹的,相反xlogx对于X≥0是严格凸的也成立。我们在等式(46)中获得量化当且仅当所有的λi是0或者1,例如,当且仅当Z最少是弱同质性的(定义7)。 对于每个竞争态ρ未来的条件分布可以写成一个或多个因果态变体的带权重混合。(Cf.图3)因此,由等式(46)得出,除非每一个ρ对于S->L(对每一个L)至少是强同质性,S->L在R上的条件熵将比最小值最高,在S上的条件熵。因此,在最大预测R^的情形下,每一个ρ^∈R^对于所有S->L必须至少是弱同质性的。但是因果态是最大的聚类,有着对于所有S->L的强同质性(引理3)。因此,每个ρ^∈R^的强同质性部分必须是子聚类,可能不适当的,是一些因果态σ∈S的。证毕。

备注1。一个可替换的证明出现在附录E中。

备注2。引理的内容可以很直观地生成,如果我们一时忽略历史中集合ρ0^测度为0的陈述。它也断言任何可替换划分R^是和因果态一样预知必须是因果态划分的细化。也就是,每个R^i必须是一个(可能不适当的)一些Sj的子集。否则,至少有一个Ri^应当必须至少包含两个因果态的部分。所以说,使用这个Ri^去预测未来的观测可能会导致关于S->比使用因果态更加的不确定。这点也在图4中做了说明,可以尝试和图3做对比。

将历史的测度0集合ρ0^添加到这个图示中并没有大幅改变启发式内容。准确地因为这些历史有0的概率,用“不恰当的”的方式来看待他们可以获得对预测、变体、凡此种种不可辨别的差异。这里有一个术语上的问题,尽管,自从他们看起来没有标准的名称来命名划分R^和S之间的关系。我们提议说前者是后者几乎无处不在的细化,或者,一个细化后处理(After Effect)。

注备3。没有人能用其他方法证明来展示因果态必须是等价预知R^状态的细化。这已经排除了因为应用借用自参考文献【62】的等式【46】定理,兴起于能够由指定选择哪一种分布来减少不确定性。自从因果态构建于对应未来的强同质性,没有这种情况。引理3和定理1一样保护了我们。

备注4。因为几乎所有每一个预知竞争者状态是完全地包含在一个单独的因果态,我们可以构建一个函数g:R^->S,符合,如果η(s<-) = ρ^,那么ϵ(s<-)=g(ρ^)几乎都成立。我们甚至可以说S = g(R^)几乎总成立,理解了这一点,意味着,对每一个ρ^,P(S = σ | R^ = ρ^) >0当且仅当σ = g(ρ^)。

图例4。一个预知竞争者划分R^必须是因果态划分的细化几乎到处如此。即,几乎所有每个R^i必须包含在一些Sj;例处就是,如果任何,一些历史集合测度为0。这里作为例子S2包含R^3,R^4和R^5的正测度部分。这里竞争态当中的一个,比如R^3,可以拥有在任意或所有其他因果态的历史成员,提供所有的这些异常历史的所有测度是0。Cf.图3。

定理2(因果态是最简的)【15】对所有预知竞争态R^,

[math]\displaystyle{ C_μ(\hat{\mathcal{R}}) \ge C_μ(\mathcal{S}) . \tag{47} }[/math]

证明。由引理7,备注4可得,有一个函数g符合S = g(R^)几乎总成立。但是H[f(X)]≤H(X)(等式(附录11))并且因此

[math]\displaystyle{ H[\mathcal{S}] = H[g(\hat{\mathcal{R}})] \le H[\hat{\mathcal{R}}]. \tag{48} }[/math]

但是[math]\displaystyle{ C_μ(\hat{\mathcal{R}}) = H[\hat{\mathcal{R}}] }[/math] (定义4)。证毕。

备注1。我们只是建立了没有竞争者斑图,能同因果态一样对观测预测的那么发,又或者是更简单,在定义4的意义下,相比于因果态来说。(这是参考文献【6】中的定理。)奥卡姆因此告诉我们不用使因果态是没有理由的。下一个定理展示了因果态是唯一最优的,并且因此奥卡姆剃刀是我们不得不使用的。

备注2。到这时它变得重要,我们试图预测S->的全部,而不是一些片段,S->L。假设两段历史s<-和s<-'对长度到L的未来有相同的条件分布,但是符合条件的是不同的个体。他们应该这时附属于不同的因果态。一个η状态合并了这两个因果态,尽管这样,应该拥有同因果态相同的预测S->L的能力。更多地,这些R-状应该更简单,意味着在当前状态下的不确定性应该更低。我们得出因果态是最优的,但是对于最难的工作——那些预测所有长度的未来。

备注3。我们已经看到(定理1,备注2)因果态对于预测所有长度的未来有足够统计量;所有的预知竞争者也一样。一个最简单足够统计是这样一个所有其他足够统计量的函数【62,p.38】。自从,在定理2的证明过程中,我们已经展现有一个从任意R^到S的函数g,我们也展示了因果态是最简单且具有足够统计量的。

我们现在或许可以,如同承诺,定义一个过程的统计复杂度【5,6】。

定义12(一个过程的统计复杂度)一个过程O的统计复杂度“Cμ(O) ”是它的因果态:Cμ(O) = Cμ(S)。

因为因果态的最简使我们看到统计复杂度度量存储在过程中的平均数量历史记忆。没有最简定理,这种表述将不可能,因为我们可以不厌其繁地精心设计内部状态,但仍然生成相同的观测过程。这些状态对应的Cμ将增长到无界并因此是随心所欲并不是过程的特征属性【17】。

定理3(因果态是唯一的)对所有预知竞争者R^,如果Cμ(R^) = Cμ(S),那么存在一个在R^和S之间不可逆函数几乎总是保持状态的相等:R^跟η和S及ϵ是相等的,相对而言,将测度为0的历史集合排除在外。

证明。从引理7,我们可知S = g(R^)几乎总成立。我们现在展示有一个函数f满足R^ = f(S)几乎总成立,表明g = f-1并且f是要求的两个集合之间的关系。为了做成这样,由等式(A12)足够展示H[R^|S]=0。现在,它遵循信息论唯一性(等式(A8))

[math]\displaystyle{ H[\mathcal{S}] - H[\mathcal{S} \vert \hat{\mathcal{R}}] = H[\hat{\mathcal{R}}] - H[\hat{\mathcal{R}} \vert \mathcal{S}]. \tag{49} }[/math]

自从,由引理7H[S|R^] = 0,等式(49)两边都等于H[S]. 但是,由假设可知,H[R^] = H[S]。因此,H[R^|S] = 0并且存在一个f满足R^ = f(S)几乎总成立。至此我们有f(g(R^)) = R^并且g(f(S)) = S,因此g = f-1。这表明f保留几乎一直状态的等价性:对几乎所有s<-,s<-' ∈S<-,η(S<-)= η(s<-')当且仅当ϵ(s<-) = ϵ(s<-')。

备注。作为细化引理7的情形,在定理的基础之上,测度0的注意事项看来是无可避免的。一个竞争对手同因果态拥有相同预测和简化(在定义4的意味上)能力,可以赋予测度0历史的集合以和ϵ机制区分状态,但没有更多了。这是有意义的:这样测度为0的集合无法区分,自从他们的成员从来无法观测,由定义可知。由同类的标记,尽管如此,没有什么阻止一个最简的,预知竞争者从不同意在这些历史上的ϵ机制。

定理4(ϵ机制是最简随机)【15】对所有的预知竞争者R^,

[math]\displaystyle{ H[\hat{\mathcal{R}}' \vert \hat{\mathcal{R}}] \ge H[\mathcal{S}' \vert \mathcal{S}]. \tag{50} }[/math]

其中S'和R^'是过程的下一个因果态并且是对应的下一个η态。

证明。从定理5可知,S'由S和S->1共同固定,因此由等式(A12)得出H[S'|S,S->1] = 0。因此,从对于熵的等式(A6)链式法则可知,

[math]\displaystyle{ H[\overset{\to 1}{S} \vert \mathcal{S}] = H[\mathcal{S}', \overset{\to 1}{S} \vert \mathcal{S}]. \tag{51} }[/math]

我们没有对于竞争者状态R^类似的决定性引理5的结果,但是熵是一直非负的:H[R^'|R^,S->1] ≥ 0。自从对于所有的L,H[S->L|R^] = H[S->L|S],由定义可知,定义(11),竞争态的,H[S->1|R^] = H[S->1|S]。现在我们再次应用链式法则,

[math]\displaystyle{ \begin{aligned} H[\hat{\mathcal{R}}', \overset{\to 1}{S} \vert \hat{\mathcal{R}}] & = H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}] + H[\hat{\mathcal{R}}' \vert \overset{\to 1}{S}, \hat{\mathcal{R}}] (52) \\ & \ge H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}] \\ & = H[\overset{\to 1}{S} \vert \mathcal{S}] \\ & = H[\mathcal{S}', \overset{\to 1}{S} \vert \mathcal{S}] \\ & = H[\mathcal{S}' \vert \mathcal{S}] + H[\overset{\to 1}{S} \vert \mathcal{S}',\mathcal{S}] . (56) \end{aligned} }[/math]

从等式(54)到等式(55)我们使用了等式(51),并且在是后一步我们再一次应用了链式法则。

最后一次使用链式法则,我们有

[math]\displaystyle{ H[\hat{\mathcal{R}}', \overset{\to 1}{S} \vert \hat{\mathcal{R}}] = H[\hat{\mathcal{R}}' \vert \hat{\mathcal{R}}] + H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}', \hat{\mathcal{R}}]. \tag{57} }[/math]

将这些扩展,等式(56)和(57),结合在一起我们得到

[math]\displaystyle{ H[\hat{\mathcal{R}}' \vert \hat{\mathcal{R}}] + H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}',\hat{\mathcal{R}}] \ge H[\mathcal{S}' \vert \mathcal{S}] + H[\overset{\to 1}{S} \vert \mathcal{S}', \mathcal{S}] \tag{58} \\ H[\hat{\mathcal{R}}' \vert \hat{\mathcal{R}}] - H[\mathcal{S}' \vert \mathcal{S}] \ge H[\overset{\to 1}{S} \vert \mathcal{S}', \mathcal{S}] - H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}', \hat{\mathcal{R}}] . }[/math]

从引理7,我们知道S = g(R^),因此这里有另一个函数g'从η状态的有序对到因果态的有序对:(S',S) = g'(R^',R^)。因此,等式(A14)表明

[math]\displaystyle{ H[\overset{\to 1}{S} \vert \mathcal{S}',\mathcal{S}] \ge H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}', \hat{\mathcal{R}}] \tag{59} . }[/math]

因此,我们有

[math]\displaystyle{ \begin{aligned} H[\overset{\to 1}{S} \vert \mathcal{S}',\mathcal{S}] - H[\overset{\to 1}{S} \vert \hat{\mathcal{R}}', \hat{\mathcal{R}}] & \ge 0 \\ H[\hat{\mathcal{R}}' \vert \hat{\mathcal{R}}] - H[\mathcal{S}' \vert \mathcal{S}] & \ge 0 \\ H[\hat{\mathcal{R}}' \vert \hat{\mathcal{R}}] & \ge H[\mathcal{S}' \vert \mathcal{S}] . (60) \end{aligned} }[/math]

证毕。

备注。这个定理是说在因果态的转换间没有更多的不确定性,比其他预知实际状态类别之间的转换更少。用其他的话来说,因果态的方式同完美的决定论很接近——在通常的理论中,非计算理论层面——因为任何竞争者在预测未来上一样好。这一类内部的决定论已经作为理想的科学模型【72】有一段时间了。

边界

在这一节我们研究结构复杂度和熵之间的测量,继承自ϵ机制和那些来自遍历性和信息论的,或许可能会让大家更熟悉一些。

定义13(扩展熵)一个过程的扩展熵E是它的准无穷过去和准无穷未来之间的互信息。:

[math]\displaystyle{ \mathbf{E} \equiv I[\overset{\to }{S};\overset{\leftarrow}{S}] . \tag{61} }[/math]

扩展熵是经常使用的随机过程复杂度的测量方法,也出现过多个名字;例如,“预测信息”,“存储信息”,“有效测量复杂度”,凡此种种【73-79】。E测量存储在关于过去可观测行为的外在信息。由于我们已经建立了,E不是,通常意义上的,过程存储于内部的关于过去的记忆数量;一个用Cμ量化测量。

定理5(扩展的边界)统计复杂度是扩展熵E的边界:

[math]\displaystyle{ \mathbf{E} \le C_μ , \tag{62} }[/math]

带着等价条件当且仅当[math]\displaystyle{ H[\mathcal{S} \vert \overset{\to }{S}] = 0 }[/math]

证明。[math]\displaystyle{ \mathbf{E} = I[\overset{\to }{S};\overset{\leftarrow}{S}] = H[\overset{\to }{S}] - H[\overset{\to }{S} \vert \overset{\leftarrow}{S}] }[/math]并且,由于因果态的构造,[math]\displaystyle{ H[\overset{\to }{S} \vert \overset{\leftarrow}{S}] = H[\overset{\to }{S} \vert \mathcal{S}] }[/math],所以

[math]\displaystyle{ \mathbf{E} = H[\overset{\to }{S}] - H[\overset{\to }{S} \vert \mathcal{S}] = I[\overset{\to }{S};\mathcal{S}]. \tag{63} }[/math]

所以有,自从两个变量间的互信息从不大于各自的信息量(等式(A9)),E ≤ H[S] = Cμ,带着等价条件当有仅当H[S|S->] = 0。证毕。

备注1。注意到我们有引用H[S->],而不是H[S->L],也只是在减去象H[S->|S<-]的数量。我们不需要担心,因此,关于一个有限L-> ∞极限H[S->L]的存在性,只是有限L->∞对于I[S->L;S<-]和I[S->L;S]的极限。有很多初级情形(例如,单纯的掷硬币过程)都是后者极限存在的同时前者不存在。

备注2。在第一眼看来,将E看作存储在过程中的信息数量是吸引人的。如定理5所示,这种吸引力应该抵制。E是过程存储关于它的历史,命名为Cμ,信息真实数量唯一下界。 我们可以,即使,说E量度了在过程中显现的信息,自从它是直接定义在观察序列术语上而非隐式术语,内生状态,如Cμ所是。

备注3。可能另一种描述什么是E所量度的是指出,由它的区块马尔可夫结构隐含假设,它接受序列区块作为状态。但即使对于区块马尔可夫源聚类,对于这种假设是适当的,扩展熵和统计复杂度量度不同种类的信息存储。参考文献【65】和【80】展现了在一维范围情形的R自旋系统,或者任何其他的区块马尔可夫源的区块配置是对因果态同构的。

[math]\displaystyle{ C_μ = \mathbf{E} + Rh_μ \ , \tag{64} }[/math]

对于有限的R。只有对于零熵速率区块马尔可夫源将扩展熵,一个直接从序列区块数量估计,等同于统计复杂度,存储在过程中的记忆数量。这些源的例子包括周期过程,对于这类我们有Cμ = E = log2p,其中p是周期。

推论2 对于所有的预知竞争态R^,

[math]\displaystyle{ \mathbf{E} \le H[\hat{\mathcal{R}}] \ . \tag{65} }[/math]

证明。这个直接遵循于定理2,自从H[R^]≥Cμ。证毕。

引理8(条件不影响熵速率)对于所有预知竞争态R^,

[math]\displaystyle{ h[\overset{\to }{S}] = h[\overset{\to }{S} \vert \hat{\mathcal{R}}] \ , \tag{66} }[/math]

其中熵速率h[S->]和条件熵速率h[S->|R^]已经定义在等式(9)和等式(10),相应地。

证明。从定理5和推论2,我们得出

[math]\displaystyle{ \lim_{L\to \infty}\left(H[\overset{\to L}{S}] - H[\overset{\to L}{S} \vert \hat{\mathcal{R}}]\right) \le \lim_{L\to \infty}H[\hat{\mathcal{R}}] \ , \tag{67} }[/math]

或者,

[math]\displaystyle{ \lim_{L\to \infty}\frac{H[\overset{\to L}{S}] - H[\overset{\to L}{S} \vert \hat{\mathcal{R}}]}{L} \le \lim_{L\to \infty}\frac{H[\hat{\mathcal{R}}]}{L} \ . \tag{68} }[/math]

自从,由等式(A4),H[S->L] - H[S->L | R^] ≥ 0,得出

[math]\displaystyle{ h[\overset{\to }{S}] - h[\overset{\to }{S} \vert \hat{\mathcal{R}}] = 0 \ . \tag{69} }[/math]

证毕。

备注。强制让过程进入一定的状态R^ = ρ^是相似的应用过控制器,一次。但在无限熵情形,H[S->L]->L->∞ ∞,带着我们关注的,未来可能包含(或者对应)一个无限扰动序列。面对这 种“重大的扰动”,有限控制的效果是简单地被清洗掉。

另一种看待这个的方式是反映出在h[S->]统计了对应整个准无限未来的所有部分的所有依赖效果的事实基础。这个,属于统计的时间转换不变,是等同于考虑整个过程所有的依赖,包括在过去和未来之间的那些。但是这是由h[S->|R^]捕获的。他不是在R上的条件使得降低我们关于未来的不确定性失效;他能做到,因为对所有有限时间,且在S上的条件能获得最大可能不确定性的减少。宁可,引理断言这些条件不能影响那些不确定性随时间增长的渐近速率。

定理6(控制定理)给定一个预知竞争者聚类R^,

[math]\displaystyle{ H[S] - h[\overset{\to }{S} \vert \hat{\mathcal{R}}] \le C_μ \ , \tag{70} }[/math]

其中H[S]是从可观测随机过程单个符号的熵。

证明。由于周知的原因(参考文献。【62,定理. 4.2.1,p. 64】),对于任意统计随机过程,

[math]\displaystyle{ \lim_{L\to \infty}\frac{H[\overset{\to L}{S}]}{L} = \lim_{L\to \infty}H[S_L \vert \overset{\to L-1}{S}] \ . \tag{71} }[/math]

更多地,这个极限总是存在。到了这个点,我们已经定义的h[S->]是用左手面的形式;回忆下等式(9)。接下来我们用右手面将是便利的。

从条件熵的定义可知,我们有

[math]\displaystyle{ \begin{aligned} H[\overset{\leftarrow L}{S}] &= H[\overset{\leftarrow 1}{S} \vert \overset{\leftarrow L-1}{S}] + H[\overset{\leftarrow L-1}{S}] (72) \\ &= H[\overset{\leftarrow L-1}{S} \vert \overset{\leftarrow 1}{S}] + H[\overset{\leftarrow 1}{S}] \ . \end{aligned} }[/math]

所以我们可以将过程过去生成的最后可测量的熵表示成

[math]\displaystyle{ \begin{aligned} H[\overset{\leftarrow 1}{S}] &= H[\overset{\leftarrow L}{S}] - H[\overset{\leftarrow L-1}{S} \vert \overset{\leftarrow 1}{S}] (73) \\ &= H[\overset{\leftarrow 1}{S} \vert \overset{\leftarrow L-1}{S}] + H[\overset{\leftarrow L-1}{S}] - H[\overset{\leftarrow L-1}{S} \vert \overset{\leftarrow 1}{S}] \\ &= H[\overset{\leftarrow 1}{S} \vert \overset{\leftarrow L-1}{S}] + I[\overset{\leftarrow L-1}{S};\overset{\leftarrow 1}{S}] \ . \end{aligned} }[/math]

我们由替换RHS对应H[S<-L]的等式(72)走过等式(73)和等式(74)。

考虑到L->∞ 的极限在LHS上没有作用,

[math]\displaystyle{ H[\overset{\leftarrow 1}{S}] = \lim_{L\to \infty}\left(H[\overset{\leftarrow 1}{S} \vert \overset{\leftarrow L-1}{S}] + I[\overset{\leftarrow L-1}{S};\overset{\leftarrow 1}{S}]\right) \ . \tag{76} }[/math]

自从过程是统计的,我们可以将极限中第一个术语倾向于[math]\displaystyle{ H[S_L \vert \overset{\to L-1}{S}] }[/math]。这个极限是[math]\displaystyle{ h[\overset{\to}{S}] }[/math],由等式(71)。进一步,因为统计性,[math]\displaystyle{ H[\overset{\leftarrow 1}{S}] = H[\overset{\to 1}{S}] = H[S] }[/math]。转移熵速率[math]\displaystyle{ h[\overset{\to}{S}] }[/math]到等式(76)的LHS并且再次请求时间转换,我们有

[math]\displaystyle{ \begin{aligned} H[S] - h[\overset{\to}{S}] &= \lim_{L\to \infty}I[\overset{\leftarrow L-1}{S};\overset{\leftarrow 1}{S}] \ (77) \\ &= I[\overset{\leftarrow}{S};\overset{\leftarrow 1}{S}] \ (78) \\ &= H[\overset{\to 1}{S}] - H[\overset{\to 1}{S} \vert \overset{\leftarrow}{S}] \ (79) \\ &= H[\overset{\to 1}{S}] - H[\overset{\to 1}{S} \vert \mathcal{S}] \ (80) \\ &= I[\overset{\to 1}{S};\mathcal{S}] \ (81) \\ & \le H[\mathcal{S}] = C_μ \ (82) \ , \end{aligned} }[/math]

其中最后一个不等式来自等式(A9)。证毕。

备注1。控制定理受此启发,也是一个版本,艾什比的多样必要性定律【81,ch. 11】。这点陈述了应用一个控制器会由最大化控制变量的熵来减少被控变量中的不确定性。(这个结果最近被重新在参考文献【82】中发现。)将控制变量考虑成因果态,我们在这里有一个在控制器减少熵速率能力上的极限。

备注2。这是长久以来唯一结果,在有限L和无限L情形之间的差别是很重要的。对于在有限情况的类似结果,可参阅附录F的定理7。

备注3。由应用定理2和引理8,我们可以从表示[math]\displaystyle{ H[S] - h[\overset{\to}{S} \vert \hat{\mathcal{R}}] \le H[\hat{\mathcal{R}}] }[/math]定理出发。这个具有良好的对称表现形式,但确实是一个更弱的极限,无论是在斑图的长度上,相等地,或是在控制可努力修正因果态(或他竞争者当中的一个)的数量。

结论备注

讨论

让我们审阅,非正式地,我们展现了什么。我们开始于斑图的自然和斑图发现的问题。我们在这些问题上的考察引导我们期待一种方式去描述斑图且至少是代数的,可计算的,固定随机性的,和因果的。我们在系统上定义了斑图,以一种非常通用和抽象的手法,作为历史的等价类,或隐状态的集合,用于预测。我们定义这些斑图的强度(由他们的广播能力和精确度)和他们的统计复杂度(由状态熵或关于历史的进程保留的信息量)。我们展现了从每个给定全部过去的预测能力的部分进度中获取的这些斑图有多强存在极限。以这种方式,我们窄化我们的目标以找到一个最大强度和最小复杂度的预测器。

最优化预测让我们导向等价关系~ϵ和函数ϵ,以及由因果态和他们的转移来表征斑图——这个ϵ机器。我们第一个定理展现了因果态是最大预测的;我们第二定理,他们是最强表征斑图的最简方式;我们第三定理,他们是唯一拥有双重优势的。后期结果展现了ϵ机器是捕获过程最大强度斑图和强调运用但隐式状态的最小随机方式,相比那些粗略的观察者,比如序列块。

为什么ϵ机制存在状态因果?首先,ϵ机制的结构(或者说,由它的半群代数给出)勾画出变体P(S->|S<-)之间的依赖关系,将每一个新符号决定着接下来的变体考虑成事件。因此,如果状态B跟着状态A那么A是B的原因且B是A的效应。第二,ϵ机制最简保证没有其他事件干扰从A到B渲染的无关性。

ϵ机制因此是过程所有斑图的一个因果表征。它是最大预测且最小复杂度。它是即时计算的,自从它展示过程如何存储信息(在因果态中)并且转换信息(在状态到状态的转移),并且代数(详情请参阅附录D)。它可以从给定的分布和经验数据系统性的方法中被解析计算。它满足在第Ⅱ节F中列出的基本约束。

这些备注表明计算力学和ϵ机制是关联的或对一些领域或许有兴趣。时间序列分析,决策理论,机器学习,和统一代码理论显式的或隐式的要求观测过程的模型。随机过程理论,形式语言和计算,和物理复杂的测量是所有为过程表征所关注的——关注哪些在现代形式的计算设备的设计中浮现的。这些领域的动机经常从计算力学中删除过多。但是它是有用的,如果仅仅通过对比的方式,去简要的接触这些领域并强调单个或多个和计算力学的连接,我们在附录G中去尝试。

当前结果的限制

让我们给一开始制定的和后来在开发中使用的限制假设编制目录。

1. 我们已知在一个过程的所有长度序列块之上的联合分布的精确值。

2. 观测的过程获取的为离散值。

3. 过程在时间上是离散的。

4. 过程是纯粹的时间序列;例如,没有空间扩展。

5. 被观测的过程是统计的。

6. 预测只能基于过程的过去,不能是其他外部的信息源。

问题就产生了,可以在不带来更多麻烦的同时,任何一条有放松的可能吗?

一种方式是提起第一个限制,而去发展统计误差理论,对应于ϵ机制推理指出的,也就是说,需要获得在带有一定数量的因果态的ϵ机制中的多少数据以得到指定水平的置信度。这个程序正在进行并且,给定他的初始过程,我们可以在下一节描述若干课题的更多细节。

第二个限制或许可以被解决掉,但是带有对应地增长数学的长足进步。我们使用过的信息论量化也在连续的随机变量上有定义。他就象许多贮存到连续设置中的结果一样。

第三个限制看起来也容易解决,自从连续时间随机过程理论是适度地良好发展的。这个或许包含熟练的概率理论或功能分析。

作为第四个限制,已经存在有一些技巧能将空间上扩展的系统视为时间序列。必要的,一些看起来所有的通往时空的路径,对待彼此如同它是时间序列。同时这些对于数据压缩工作良好,对于是否全部符合捕获结构它不是特别清晰【84】。在这些课题上有更多的工作需要去做。

在此刻仍不清晰的是怎么去放宽统计假设。有一个不会带来太多麻烦的可形式扩展在这篇文章中大多数结果为非统计过程的方法。它就是,尽管,这些扩展本质上内容有多不清晰,在任何情况下,一个非统计过程系统的聚类是(最好)在它的婴幼儿阶段。

最后,某人会说最后的限制是正向的特征当它倾向于考虑斑图和过程的内生结构。“斑图”是个含糊其辞的词汇,当然,但在平常的使用中它是唯一误以为在过程中包含事物,而不是宇宙的其余部分。给定两个文档的挎贝,其中一份挎贝的内容可以由对照着另一份挎贝被令人羡慕的准确度所预测。这告诉我们他们共享通用的结构,但是没有告知任何关于斑图是什么的内容。自从它确实只是良好地书写并紧密地辩论的科学文章(哪个很可能是高度组织化的)作为它是键盘前的猴子般胡言乱语的片段(哪个确实不是)。

结论和将来工作的方向

计算力学聚焦于理解斑图的自然和斑图发现。我们期待前述发展能确信读者我们即不过敏于当我们说我们已经为这些项目奠定了基础,也不于我们轻率,当我们说这些ϵ机制所表征的斑图和那些我们发现的它们由ϵ机制所重构。我们希望由标注我们的两个对未来工作是广泛林荫大道来结尾。

首先,考虑ϵ机制它们自己的数学。我们刚提到以提出在发展中做出的假设的形式做可能的扩展,但有许多其他方式值得尝试。一定数量的测量理论课题关联到因果态的定义(这里为了简洁而忽略)值得细心处理,沿着参考文献【10】的字里行间。理解好ϵ机制对于连续状态过程测量分辨率缩放属性,以及他们和Krohn-Rhodes分解自动理论【30】的关系,将很有帮助。谁经营着吸收参考文献【26】第二卷或许可能处于回答关于过程持有的,或许甚至给予ϵ机制纯关系理论叙述结构的有趣问题位置。我们已经在许多地方婉转提到预测性和复杂性之间的此消彼涨的关系。对于给定的过程,这里大概有一系列最优机器连接于单个状态,零复杂度机器,对ϵ机器带有最小预测性。路径的每个成员对一定度数的预测性而言是最小机器;知道什么,或者任何我们通常可以说的事情,是有于这个“预测前沿”的外形,将可能非常有趣。

其次,这里有ϵ机器的重构,一个关于哪个是我们说过无关的行动。曾经我们在上面(12页)提到过,已经有若干从数据重构机器的算法,甚至有“实时”版本。很明显这些算法将在无限时间和无限数据的限制中找到正确的机器。需要的是理解这些过程制造的各种失误的不同重构过程的误差统计【85】。理想状态下,我们希望找到对应于重构产物的“信任区域”。目标是计算(i)对于给定体积数据的不同重构误差的度数概率,(ii)需要确信一个在误差之上的修理边界数据的数量,又或者(iii)集中于ϵ机器在不同的重构过程的速率。目前为止,一个解析理论已经发展成预测估计的因果态的平均数量,作为当重构特定类型的过程使用的一定数量数据的函数【86】。一旦我们支配一个对于ϵ机器更完整的统计推理理论,类似地什么已经存在于计机学习理论也有可能,我们将处于开始分析的位置,显著地和严格地,自然世界展现的众多引人入胜的斑图和信息处理结构。

申明

我们感谢Dave Albers,Dave Feldman,Jon Fetter,Rob Haslinger,Wim Hordijk,Amihan Huesmann,Cris Moore,Mitch Porter,Erik van Nimwegen,和Karl Young在脚本上的建议;1998圣塔菲复杂系统暑期学校成员,麦迪逊概率研究会,麦迪逊物理系毕业学生迷你学术研讨会,和安娜堡复杂系统研讨会在这些结果的早期版本中提供了大量有帮助的建议。这个工作由圣塔菲研究所通过ONR授权N00014-95-1-0975,NSF授权PHY-9970158,和DARPA合同F30602-00-2-0583在计算、动态、和推理程序提供支持。

附录

信息论公式

下面的公式证明在开发中很有用。他们是相对直观的,给我们解释性,并且他们可以用比单纯代数多一点的东西去证明;参阅文献【62】。下面,f是一个函数。

[math]\displaystyle{ \begin{aligned} H[X,Y] &= H[X] + H[Y \vert X] \ (A1) \\ H[X,Y] &\ge H[X] \ (A2) \\ H[X,Y] &\le H[X] + H[Y] \ (A3) \\ H[X \vert Y] &\le H[X] \ (A4) \\ H[X \vert Y] &= H[X] \ iff \ X 和Y无关 \ (A5) \\ H[X, Y \vert Z] &= H[X \vert Z] + H[Y \vert X, Z] \ (A6) \\ H[X, Y \vert Z] &\ge H[X \vert Z] \ (A7) \\ H[X] - H[X \vert Y] &= H[Y] - H[Y \vert X] \ (A8) \\ I[X;Y] &\le H[X] \ (A9) \\ I[X;Y] &= H[X] \ iff \ H[X \vert Y] = 0 \ (A10) \\ H[f(X)] &\le H[X] \ (A11) \\ H[X \vert Y] &= 0 \ iff \ X = f(Y) \ (A12) \\ H[f(X) \vert Y] &\le H[X \vert Y] \ (A13) \\ H[X \vert f(Y)] &\ge H[X \vert Y] \ (A14) \end{aligned} }[/math]

等式(A1)和(A6)被称作熵的链式法则。严格来说,等式(A12)右手边应该读作“对每个[math]\displaystyle{ y, P(X = x \vert Y = y) \gt 0 }[/math]对一个,仅一个x”。

导出因果态的等价关系

任何反身的,对称的,和转换关系是等价关系。

考虑所有过去序列,任意长度集合[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]

[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} = \{\overset{\leftarrow L}{s}=s_{L-1} \dots s_{-1}:s_i \in \mathcal{A}, L \in \mathbb{Z}^+ \}. \tag{B1} }[/math]

回忆下[math]\displaystyle{ \overset{\leftarrow 0}{s} = λ }[/math],空字符串。我们由下式定义[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]之上的关系[math]\displaystyle{ \sim_ϵ }[/math]

[math]\displaystyle{ \overset{\leftarrow K}{s_i}\sim_ϵ\overset{\leftarrow L}{s_j} \Harr P(\overset{\to}{S} \vert \overset{\leftarrow K}{s_i}) = P(\overset{\to}{S} \vert \overset{\leftarrow L}{s_j}), \tag{B2} }[/math]

对所有准无限[math]\displaystyle{ \overset{\to}{S} = s_0s_1s_2\dots, }[/math] 其中[math]\displaystyle{ K,L \in \mathbb{Z}^+ }[/math]

这里我们由回顾关系的基本属性,等价类,和划分来展示[math]\displaystyle{ \sim_ϵ }[/math]是一个等价关系。(证明的细节是直观的并未包括在这里。查看参考文献【87】。)我们将丢弃长度变量K和L并由[math]\displaystyle{ \overset{\gets}{s},\overset{\gets'}{s},\overset{\gets''}{s} \in \overset{\gets''}{\mathbf{S}} }[/math]表征,是等式(B1)的集合[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]任意长度的成员。

首先,[math]\displaystyle{ \sim_ϵ }[/math]是在[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]上的关系,自从我们可以将它表示成笛卡儿积的子集

[math]\displaystyle{ \overset{\gets''}{\mathbf{S}} \times \overset{\gets''}{\mathbf{S}} = {(\overset{\gets}{s},\overset{\gets'}{s}):\overset{\gets}{s},\overset{\gets'}{s} \in \overset{\gets''}{\mathbf{S}}}. \tag{B3} }[/math]

其次,关系[math]\displaystyle{ \sim_ϵ }[/math][math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]上是等价关系自从它是

1.自反的:[math]\displaystyle{ \overset{\gets}{s}\sim_ϵ\overset{\gets}{s} }[/math],对于所有[math]\displaystyle{ \overset{\gets}{s} \in \overset{\gets}{\mathbf{S}} }[/math]

2.对称的:[math]\displaystyle{ \overset{\gets}{s}\sim_ϵ\overset{\gets'}{s}\Rarr\overset{\gets'}{s}\sim_ϵ\overset{\gets}{s} }[/math];并且

3.传递的:[math]\displaystyle{ \overset{\gets}{s}\sim_ϵ\overset{\gets'}{s} }[/math][math]\displaystyle{ \overset{\gets'}{s}\sim_ϵ\overset{\gets''}{s} \Rarr \overset{\gets}{s}\sim_ϵ\overset{\gets''}{s} }[/math]

再次,如果[math]\displaystyle{ \overset{\gets}{s} \in \overset{\gets}{\mathbf{S}} }[/math]的等价类是

[math]\displaystyle{ \lbrack \overset{\gets}{s} \rbrack = \{ \overset{\gets'}{s} \in \overset{\gets}{\mathbf{S}} : \overset{\gets'}{s}\sim_ϵ\overset{\gets}{s}\}. \tag{B4} }[/math]

[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]中的所有等价类集合表示成[math]\displaystyle{ \overset{\gets}{\mathbf{S}}/\sim_ϵ }[/math]并称作[math]\displaystyle{ \overset{\leftarrow}{\mathbf{S}} }[/math]对于[math]\displaystyle{ \sim_ϵ }[/math]的因子组。在第Ⅳ节A部分我们称单独的等价类为因果态Si并表征因果态的集合为[math]\displaystyle{ \mathbfcal{S} = \{ \mathcal{S}_i: i = 0, 1, \dots,k-1\} }[/math]。也就是,[math]\displaystyle{ \mathbfcal{S} = \overset{\gets}{\mathbf{S}}/\sim_ϵ }[/math]。(我们提到在主要开发中因果态基数[math]\displaystyle{ k = \lvert \mathbfcal{S} \rvert }[/math]或者不是有限的。)

最后,我们列出因果态等价类的若干基本属性

1.[math]\displaystyle{ \textstyle \bigcup_{ \overset{\gets}{s} \in \overset{\gets}{\mathbf{S}}} \lbrack \overset{\gets}{s} \rbrack = \overset{\gets}{\mathbf{S}} }[/math]

2.[math]\displaystyle{ \textstyle \bigcup_{ i=0} ^ {k-1} \mathcal{S}_i = \overset{\gets}{\mathbf{S}} }[/math].

3.[math]\displaystyle{ \lbrack \overset{\gets}{s} \rbrack = \lbrack \overset{\gets '}{s} \rbrack \Harr \overset{\gets}{s}\sim_ϵ\overset{\gets'}{s} }[/math].

4.如果[math]\displaystyle{ \overset{\gets}{s},\overset{\gets'}{s} \in \overset{\gets}{\mathbf{S}} }[/math],则 (a) [math]\displaystyle{ \lbrack \overset{\gets}{s} \rbrack \bigcap \lbrack \overset{\gets'}{s} \rbrack = \empty }[/math]或 (b)[math]\displaystyle{ \lbrack \overset{\gets}{s} \rbrack = \lbrack \overset{\gets'}{s} \rbrack }[/math].

5. 因果态[math]\displaystyle{ \mathbfcal{S} }[/math][math]\displaystyle{ \overset{\gets}{\mathbf{S}} }[/math]的一个划分。也就是,

(a)[math]\displaystyle{ \mathcal{S}_i \not = \empty }[/math]对每一个i,

(b)[math]\displaystyle{ \textstyle \bigcup_{ i=0} ^ {k-1} \mathcal{S}_i = \overset{\gets}{\mathbf{S}} }[/math],并且

(c)[math]\displaystyle{ \mathcal{S}_i \bigcap \mathcal{S}_j = \empty }[/math]对所有的[math]\displaystyle{ i \not = j }[/math]

我们用[math]\displaystyle{ \mathcal{S}_i }[/math]表征开始状态。开始状态是关联到[math]\displaystyle{ \overset{\gets}{s} = λ }[/math]。也就是说,[math]\displaystyle{ \mathcal{S}_0 = \lbrack \lambda \rbrack }[/math]

时间反演

由正向扫描序列观测到的因果态的定义和属性,例如,因果态[math]\displaystyle{ \overset{\to}{\mathbf{S}} / \sim_ϵ }[/math],遵从类似附录B的继承。更一般地,[math]\displaystyle{ \overset{\gets}{\mathbf{S}} / \sim_ϵ \not = \overset{\to}{\mathbf{S}} / \sim_ϵ }[/math]。也就是,过去的因果态是不必须和将来因果态相同;过去和将来变体可以不同;不象熵速率【15】,过去和将来统计复杂度必须不相等:[math]\displaystyle{ \overset{\gets}{C_μ} \not = \overset{\to}{C_μ} }[/math];凡此种种。出现或缺失这种时间反演对称类型,如这些不等式反映的,是一个过程的基本属性。

ϵ-机器是幺半群

一个半群是在关系二值操作下封闭的一系统元素,但不保证每一个,或者确保任意,元素有逆元【88】。一个半群和幺半群是群的一般化。就象群的代数结构是作为对称性的一般性表达,我们提出将半群的代数结构表示成对称性的一般化。在幺半群和其他半群之间的区别在这里变得很重要:只有有单位元的半群——比如,幺半群——可以包含子集是群并且表现为常规的对称性。

我们申明转换连接A中的符号字符串到其他字符串构成一个半群G,生成元是转换连接A中的单元。单位元由连接空符号λ所提供。字符串t的连接成字符串s是禁止的,当且仅当形成st的字符串在一个过程中有概率为零。所有这样的连接是由单个半群元素实现成∅。自从如果[math]\displaystyle{ P(st) = 0 }[/math],那么[math]\displaystyle{ P(stu) = P(ust) = 0 }[/math]对于任何字符串u,我们要求[math]\displaystyle{ \empty g = g \empty = \empty }[/math]对于所有的[math]\displaystyle{ g \in G }[/math]。我们可以提供一个这个半群的表征吗?

从我们对标识好的转换概率,[math]\displaystyle{ T_{ij}^{(λ)} = δ_{ij} }[/math]开始回想。可得出,[math]\displaystyle{ \mathbf{T}^{(λ)} }[/math]是一个单位元。这就说明使用标记好的转换矩阵来构成半群的矩阵表征。相对应地,首先定义[math]\displaystyle{ U_{ij}^{(s)} = 0 }[/math][math]\displaystyle{ T_{ij}^{(s)} = 0 }[/math]并且[math]\displaystyle{ U_{ij}^{(s)} = 1 }[/math]否则,移除概率。然后定义矩阵集合[math]\displaystyle{ \mathbf{U} = \{\mathbf{T}^{(λ)}\}⋃\{\mathbf{U}^{(s)},s \in \mathcal{A}\} }[/math]。最后,定义G作为由迭代乘法从集合U生成的所有矩阵的集合。也就是,G的一个元素g是

[math]\displaystyle{ g^{(ab \dots cd)} = \mathbf{U}^{(d)}\mathbf{U}^{(c)}\dots\mathbf{U}^{(b)}\mathbf{U}^{(a)}, \tag{D1} }[/math]

其中[math]\displaystyle{ a,b, \dots c,d \in \mathcal{A} }[/math]。很明确地,G对应一个在矩阵乘法下的半群。更多地,[math]\displaystyle{ g^{(a \dots bc)} = \mathbf{0} }[/math](所有元素为零的矩阵)当且仅当,忽略了符号a...b的顺序,我们必须从无法忽略符号c开始到达一种状态。也就是,零矩阵0是生成的当且仅当将c连接到a...b是禁止的。元素∅因此是所有元素为0的矩阵0,这是完全符号要求的限制条件。这完成了命题1的证明。

我们将矩阵的表征——等式(D1)从[math]\displaystyle{ \mathcal{A}^{\mathcal{k}} }[/math]从提取所有的单词——ϵ-机器[math]\displaystyle{ \{\mathbfcal{S},\mathbf{T}\} }[/math]的半群机器G。查阅参考文献【89】。

细化引理的另一种证明

引理7的证明从闲言片语中得来,但我们不但留后面。不幸的是,这意味着介绍两段新数学。

首先,我们需要是带有对于固定的L相对的[math]\displaystyle{ \overset{\to L}{S} }[/math]强同质性(定义6)的最大的聚类;他们是,也就是说,因果态的切片。对应地,我们将讨论[math]\displaystyle{ \mathcal{S}^L }[/math][math]\displaystyle{ σ^L }[/math],类似于S和σ。我们将需要去定义函数[math]\displaystyle{ ϕ_{σρ}^{L} \equiv P(\mathcal{S}^L = σ^L \vert \mathcal{R} = ρ) }[/math]

综上所述,对每个L我们将

[math]\displaystyle{ \begin{aligned} H[\overset{\to L}{S} \vert \mathcal{R} = ρ ] &= H[\sum_{σ^L}ϕ_{σρ}^{L}P(\overset{\to L}{S} \vert \mathcal{S}^L = σ^L )] \ (E1) \\ &\ge \sum_{σ^L}ϕ_{σρ}^{L}H[\overset{\to L}{S} \vert \mathcal{S}^L = σ^L ]. \ (E2) \end{aligned} }[/math]

因此,

[math]\displaystyle{ \begin{aligned} H[\overset{\to L}{S} \vert \mathcal{R}] &= \sum_{ρ}P(\mathcal{R} = ρ) H[\overset{\to L}{S} \vert \mathcal{R} = ρ] \ (E3) \\ &\ge \sum_{ρ}P(\mathcal{R} = ρ) \sum_{σ^L}ϕ_{σρ}^{L}H[\overset{\to L}{S} \vert \mathcal{S}^L = σ^L ] \ (E4) \\ &= \sum_{σ^L,ρ}P(\mathcal{R} = ρ) ϕ_{σρ}^{L}H[\overset{\to L}{S} \vert \mathcal{S}^L = σ^L ] \ (E5) \\ &= \sum_{σ^L,ρ}P(\mathcal{S}^L = σ^L, \mathcal{R} = ρ) H[\overset{\to L}{S} \vert \mathcal{S}^L = σ^L ] \ (E6) \\ &= \sum_{σ^L}P(\mathcal{S}^L = σ^L) H[\overset{\to}{S} \vert \mathcal{S}^L = σ^L ] \ (E7) \\ &= H[\overset{\to L}{S} \vert \mathcal{S}^L]. \ (E8) \end{aligned} }[/math]

也就是说,

[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R} ] \ge H[\overset{\to L}{S} \vert \mathcal{S}^L] \tag{E9} }[/math]

当且仅当每一个[math]\displaystyle{ ϕ_{σρ}^{L} }[/math]是0或1时两者相等。

因此,如果[math]\displaystyle{ H[\overset{\to L}{S} \vert \mathcal{R} ] = H[\overset{\to }{S} \vert \mathcal{S}^L] }[/math],每一个[math]\displaystyle{ \hat{ρ} }[/math]是完全包含在一些[math]\displaystyle{ σ^L }[/math]中;除非测度是0的可能子集。但是对于每一个L是真的——哪种呢?在预知竞争者[math]\displaystyle{ \hat{\mathcal{R}} }[/math]的情况,它是的——然后每一个[math]\displaystyle{ \hat{ρ} }[/math]是至少弱同质性(定义7)对应于所有[math]\displaystyle{ \overset{\to L}{S} }[/math]。所以,由引理3可知,它的所有成员,除开测度为0的相同子集,属于同一个因果态。证毕。

对于准-无限未来的有限熵

当情况处于[math]\displaystyle{ H[\overset{\to}{S}] }[/math]是有限的——更准确地,其中极限[math]\displaystyle{ \lim\nolimits_{L \to \infty}H[\overset{\to L}{S}] }[/math]存在且是有限的——或许是对信息理论家兴趣不大,他们对物理学家是更有兴趣的,因为他们相应地,相对于其他事情,是周期且有限循环行为。他们是,不管怎样,在主要研究过程中什么是真正的无限熵行为和有限熵之间只有两个重要的区别。

首先,我们可以简单地用[math]\displaystyle{ H[\overset{\to}{S}] }[/math]替换形如“对于所有的[math]\displaystyle{ L, H[\overset{\to L}{S}] \ \dots }[/math]”的陈述。例如,对于有限熵过程的最优预测理论(定理1)变成了对于所有的[math]\displaystyle{ \mathbfcal{R}, H[\overset{\to}{S} \vert \mathcal{R}] \ge H[\overset{\to}{S} \vert \mathcal{S}] }[/math]。详细的证明,不管怎样,完全是类似的。

其次,我们可以证明一个基本上更强的控制理论(定理6)版本。

定理7(有限控制理论)对于所有的预知竞争者[math]\displaystyle{ \hat{\mathcal{R}} }[/math]

[math]\displaystyle{ H[\overset{\to}{S} ] - H[\overset{\to}{S} \vert \hat{\mathcal{R}}] \le C_μ. \tag{F1} }[/math]

证明。由等式(A9)直接应用和互信息定义等式(8)可知,我们有

[math]\displaystyle{ H[\overset{\to}{S} ] - H[\overset{\to}{S} \vert \mathcal{S}] \le H[\mathcal{S}]. \tag{F2} }[/math]

但是,由预知竞争者的定义(定义11),[math]\displaystyle{ H[\overset{\to}{S} \vert \mathcal{S}] = H[\overset{\to}{S} \vert \hat{\mathcal{R}}] }[/math],并且,由定义,[math]\displaystyle{ C_μ = H[\mathcal{S}] }[/math]。等式中的基本等式赋予我们这个定理。证毕。

和其他领域的关系

时间序列建模

时间序列建模的目标是基于它的过去去预测一段测量序列的未来。更广义地说,这个可以被分成两部分:识别相等的过去并且然后生成对于每个相等过去聚类的一个预测。这就是,我们首先取得一个函数[math]\displaystyle{ η:\overset{\gets}{\mathbf{S}} \mapsto \mathbfcal{R} }[/math]并且取得另一个函数[math]\displaystyle{ p:\mathbfcal{R} \mapsto \overset{\to}{\mathbf{S}} }[/math]。当然,我们可以选择p将来的范围成一定的有限长度(长度1是挺流行的)又或者选择在这个上面的一个概率分布。同时实际的应用通常需要一个单独的确定的预测——“你将会遇见一个又高又黑的陌生事物”,有明显的优势去预测一个分布——“你有0.95的机会遇到又高又黑的陌生事物,而有0.05的机会遇见一个高大而熟悉的白色物种。”很显然,对于p最好的选择是对于[math]\displaystyle{ ρ \in \mathbfcal{R} }[/math]每个将来实际的条件分布。给定这个条件,问题就变成了最好的R是什么;例如,什么是最好的η?至少在试图理解整个过程的情况下,我们展示了最好的η是,一点也不含糊的,ϵ。因此,我们的讨论蕴涵地包容了那些传统时间序列建模。

计算力学——它集中于让过程自己通过(或许很贫乏)测量——沿着激发一个方向的精神去实证测试动态系统理论。特别地,它延续参考文献【90】和【91】中介绍的重构“从时间序列中来的几何”方法的精神。一个最近的并行的工作已经出现了,无论如何,后续的工作在于从数据序列的动态中估计最小等式【92】。

决策理论问题

经典的决策理论聚焦于“归纳行为原则”【93-95】。决策理论的问题定义是如何从观测数据中选择函数能抵达控制指定属性行动的航线。这个任务显然亲和于考虑ϵ的属性和它的竞争者η。我们可以继续讨论并且表示什么是我们已经完成的可以考虑成一个决策问题,其中合适的行动包括预测关于过程的未来。行为最佳原则的计算通常会遇到可怕的技术性细节,比如提供在关联这个世界侧面每个不同的假设下每个不同的行动路径一种使用上的估计。一边是,编造完全不使用ϵ的最优行动原则的时间序列任务不会太困难。另一边是,如果我们简单地瞄准预测过程于到未来的无限期地远,然后因为因果态对于未来的分布(定理2,备注4)是最小足够统计的,最优行动原则将使用ϵ。

随机过程

很明确地,计算力学方法到斑图和斑图发现以一种密切和无法分割的方式包含了随机过程。或许可能有,也是当然,一种都兴趣盎然地使用信息论工具来分析随机过程,部分是他们的遍历性行为【59,96-98】。也有相当多的工具是基于隐马尔科夫模型和基于来源数据或给定分布的过程推理模型最优预测文献【10,99-102】。从我们的知识的最好结果来看,无论如何,这两种方式在之间没有联合过。

或许在随机过程文献中最接近计算力学精神的方法是,出乎意料地,最优预测即新又经典的理论并梳理统计过程,由维纳和柯尔莫哥洛夫所发展。这两种理论共享信息论元语的使用,预测和结构的统一,坚信“时间序列的统计力学”是一种“条件非常远程的领域,比如热机统计力学和非常适合作为在活性有机体中正在发生的模型来应用的那些”【106,p.59】。目前为止我们已经可以学到,无论如何,没有人使用过这个理论去专门识别因果态和因果结构,让这些含蓄于预测和滤波操作的数学形式。此外,维纳-柯尔莫哥洛夫框架推动我们痛快地分割预测和滤波的线性和非线性方面,因为它在计算非线性操作上具有很多困难【105】。计算力学对该问题完全漠视的,自从它将过程的所有结构打包进ϵ-机器当中,也等于说在线性和强非线性情形下是可计算的。

形式语言理论和语法推理

形式语言是从有限字母表中拉出符号串的集合(“单词”或“合法的词语”)。每一种形式语言可能被描述成规则(一个“词法”)的集合去创建所有且仅被允许的词语,由一个也是由允许的词语生成的抽象的自动机,或者由一个允许词语而剔除所有“禁止”词语所接受的自动机。我们的ϵ-机器,概率分布的丝带,对应于这些自动化——在简单情形或分类上有生产力的,如果我们加入弹出态并当没有遇到允许的符号时移动到它。

自从乔姆斯基【107,108】,已经广为人知形式语言可以被分类成一个层级结构,更高层的拥有严格意义上更强的表达能力。这个层级结构由严格的语法规则形式定义或者,等价的,由限制数量和可用于的自动机内存种类获得。层级结构的最底层是常规语言,或者为Unix用户读者用来作为正则表达式。这些对应于有限状态机和有限维隐马尔科夫模型。在这种情形下,关联到我们的最小和唯一定理是非常好懂的【66】,并且因果态的构造是类似于“尼罗德等值班级”过程【66,109】。我们的定理,不管怎么样,不会限制在这种低存储,非-随机设置。

从观测数据中学习一个语言的问题已经被语言学家们,和对自然语言处理感兴趣的计算机科学家们,广泛地研究了。不幸的是,研究充分的学习技术只存在于乔姆斯基层级的两种最底层聚类,常规的和自由内容语言。(需要出色的过程请查阅参考文献【110】。)适应性和扩展这个工作去重构ϵ-机器应该构成一个有用的未来研究领域,这一点我们在结论备注部分婉转提到过。

计算和统计学习理论

计算学习理论【111,112】的目标是识别快速,可靠,和容易导向目标“概念”良好展现的算法。后者是典型的定义成特定属性或输入空间的一个二值二分法。部分聚焦于支持关于“可能性优化修正”(PAC)过程【113】的结果:那些拥有一个高度可能的搜索成员的一个固定“展现类”(比如,神经网络,选言正则形式的布尔函数,和确定性有限自动机)。这里关键的单词是“稳态”;作为在当代时间序列分析,知晓获得正确表征原则的实践者。(获取错误将使简单问题难以处理。)在实践中,无论如此,他们简单地拾取表征类作为给定的,甚至假设我们总能靠它拥有至少一种表征能够捕获目标概念。尽管这个是在大多数学统计里字里行间带有隐含假设,它似乎没有把握在真实世界去分析学习【5,114,115】。

在任何情况下,前人的研究没有做出这样的假设。计算力学的一个目标,准确来说,发掘最好的表征。这并不是说机器学习理论的结果不够显著可用和优雅,也不是说某人不应该拾取他们在实现ϵ-机器重构上每一种可能的优势。在我们的视角中,然后,这些理论更多属于满足推理,部分对应算法参数估计,对比于关于自然斑图和学习动态的基本问题。

最后,可感知的计算力学聚焦于因果态是一种对于一个过程某类结构分解的研究。这种分解几乎反映在因果态推导的过去和将来条件无关。这种分解提示条件无关在对于人工智能在现代方法中扮演的其中最重要的职能,都为了开发在有扰环境【116】的系统和图形模型更加完善的算法【117,118】。

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

Rissanen的最小描述长度(MDL)原则,比较完整地介绍在参考文献【46】,是一个过程,该过程在全部满足给定数据一致性要求的条件下的一整族模型里选择最简明生成模型。MDL方法开始于香农的连接概率分布和代码之间的结果。Rissanen的研究继承了由Solomonoff【43】介绍的归纳法框架。

假设我们选择了导向一个[math]\displaystyle{ \mathcal{M} }[/math]类的模型并给定数据集[math]\displaystyle{ X }[/math]的表征。MDL原则告诫我们拾取模型M[math]\displaystyle{ \in \mathcal{M} }[/math]使得给定M能最小化[math]\displaystyle{ X }[/math]的描述总长度,包含给定[math]\displaystyle{ \mathcal{M} }[/math]下的M的描述长度。[math]\displaystyle{ X }[/math]的描述长度采用[math]\displaystyle{ -logP(X \vert M) }[/math];cf.等式(5)。M的描述长度或被看作是由一些编码语法给定又或是,等价地,由[math]\displaystyle{ \mathcal{M} }[/math]的成员之上的一些分布。(尽管类似于在贝叶斯框架【119】中的模型估计,Rissanen并没有打破这个分布作为一个贝叶斯优先或视描述长度为证据支持的测量。)

因果态的构造是同Rissanen的上下文算法【46,120】的状态估计有几分类似(算法对应于由统一编码语法建造的“词典”,比如流行的Lempel-Ziv算法【121,122】)。尽管存在这种类似,仍然有一些明显的不同。对于随机源——对于那些只有单个因果态的情况——上下文算法估计一定数量的状态分歧于(至少是对数级别的)数据流的长度,而不是用一个状态推理,如同ϵ-机器所重构的。更进一步,我们忽略任何参考去编码竞争者模型或在他们之上去优先分布;[math]\displaystyle{ C_μ(\mathbfcal{R}) }[/math]不是一个描述长度。

测量复杂性

参考文献【75】提出了一个过程复杂度的合适的测量是对于最佳预测的“最小平均所需香农信息”。这个真测量复杂性曾被视为被一些最佳预测器所使用的状态的香农熵。同样的文献建议它应该由外部熵所近似(参见下文);这些被称为有效测量复杂性,在前文Ⅵ节提到的。这里有一个位置接近于联合了计算力学,Rissanen的MDL原则,和由“时间序列的几何”方法【90】所描述引入的最小嵌入。

对比于计算力学,无论如何,“最优预测”的关键概念仍然遗留者未定义。如同自然界和最优预测器状态的构造。实际上,使用过的预测器需要知道过程之下的运动等式。更进一步,统计复杂度[math]\displaystyle{ C_μ(\mathbfcal{S}) }[/math]同测量复杂性不同在于它是基于良好定义的因果态,它的最佳预测能力相反有精确定义。因此,计算力学是一种表述于于参考文献【75】洞见的操作和构建形式化。

层级缩放复杂性

介绍于参考文献【123,ch. 9】,这个方法查找,如同计算力学一样,去扩展统计物理特定的传统想法。简单来说,方法是构造一个[math]\displaystyle{ n^th }[/math]-阶马尔可夫模型的层级结构,并用[math]\displaystyle{ n\ \to \ \infty }[/math]可观测真实分布检验他们预测的收敛性。预测和真实之间的差异是,此外,定义在信息理论中,用相对熵或Kullback-Leibler距离【62,71】的术语。(我们还没有用过这种量化。)该方法实现了Weiss的发现对于有限状态源存在一个结构区别于块-马尔科夫源(有限类别的次级班次)和sofic系统。Weiss展示了,尽管他们有限内存,sofic系统是不断增加的大型块状-马尔科夫源【124】的无限序列的极限。

该层级-缩放-复杂方法有若干优势,尤其是它处理以自然方式(查阅参考文献【123,sec. 9.5】)缩放课题的能力。尽管如此,它没有实现第Ⅱ节F中的所有目标集合。它的马尔科夫预测器具有很多黑箱,几乎没有说明关于过程的隐状态,他们因果连接,或者由过程附带的内生计算。所有这些属性,象我们已经展示的,是ϵ-机器的展现。我们建议一个未来工作的生产线应该去调研层次缩放复杂性和计算力学之间的关系,并看看他们能否被同步。综上所述,层次结构复杂性提醒我们少许参考文献【5】中描述的层次ϵ-机器重构。

连续运态计算

使用动态系统作为计算机已经变得不断地增加着吸引力在过去十年或物理学家,计算机科学家,和其他探索计算的物理基础【125-128】也是如此。这些提议已有范围从关于如何在离散时间非线性连接映射【7,129】里嵌入图灵机的高度抽象主意到,更前沿地,特定的数值计算设计可以原则性被实现在当前的硬件上【130】。他们所有,不管怎样,已经被同步了,以他们关心设计动态系统以实现一个给定期望计算或计算族的方式。相对地,计算力学其中之一的中心问题实际上却反过来了:给定一个动态系统,谁如何能够检测到什么是它内生的计算?

我们相信拥有数学基础和系列工具回答这个问题对综合,开发动态计算方法是重要的。使用这些工具我们或许能够发现,比如说,嵌入到自然过程操作在高速新颖形式的计算,带有少量能源,并比当前可能带有更少物理自由度。