计算力学

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

翻译自 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_{n \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】复杂性-熵图表编纂了。现在应当是清晰的,当我们使用单词“复杂性”,我们的意思是斑图的“程”度,而不是随机性的程度。

E. 因果

    我们试图让动态过程斑图的表征能有因果性——换句话说,事件的一个状态如果导向或产生另一个状态。尽管关键属性,因果进入我们的研究仅仅是一个非常微弱的感受,最弱的一个可以使用数学的方法,是休谟【56】的:一类导致其他的事件,如果后者一直随附到前者;效应的不变性演变成原因。作为一个好的非决定论者,接下来我们用概率替换不变-演变的因果观念,为单个不变的继任者代替同质继任的分布。(更精确的陈述出现在第Ⅳ节A部分因果态的定义。)这种方法是一种对因果纯粹的现象主义陈述,它因此以更强因果观念的方式服从经验主义——比如在参考文献【57】——不是。参考文献【58】单独形成本质上同样的因果概念,也就是我们通过哲学讨论形成的。

F. 斑图摘要

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

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

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

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

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

A. 隐式过程

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

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

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

定义1(一个过程)让A是一个可数集。让Ω=AZ是双向无穷序列,值由A的元素组成,Ti->A是返回双向无穷序列ω属于Ω第i个元素si的函数,而F是Ω柱集的域。添加一个概率测度P给我们一个概率空间(Ω, F, P),带有附加的随机变量S<->。一个过程是一个随机变量序列Si = Ti(S<->),i属于Z。 这里,自始至终地,我们遵从习惯,使用大写字母来表示随机变量,而使用小写字母来表示它们的特定取值。

    从定义延展过来,有一个对有限长度序列的良好定义的概率分布。让St->L是St, St+1, ..., St+L-1以St开始的L个随机变量,St->0=λ,是空序列。同样,St <-L代表结束于St的L个随机变量的序列,但并不包含St;St <- L = S t-L ->L。St ->L和St ->L都从sL属于集合AL中获取特定值。类似地,St ->和St <-是准无限序列,他们分别从t开始和结束于t,并相应从s->和s<-获取特定值。

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

定义2(稳态)一个过程Si是稳态的,当且仅当

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

对所有的t属于Z,L属于Z+,而且所有sL属于AL。 换句话来说,一个稳态过程是随时间不变的。结果就是,P(St -> = s ->) = P(S0 -> = s ->),并且P(St -> = s <-) = P(S0 <- = s <-),所以我们从现在开始去掉下标。

B. 水池

    我们的目标是使用一个函数,利用S<-的一部分来作为输入,预测S->所有或者部分。我们由获取S<-的集合开始,并将它划分成不同的相互独立的部分,连带综合各个子集。也就是说,我们构建一个过去子集的类R。(参阅图1的示意图的例子)每一个ρ属于R将被称为一个状态或一个有效状态。当现在的历史s<-包含在集合ρ中,我们会说过程处于状态ρ中。因此,我们定义从历史到有效状态的函数: μ: S<- |->R. (4) 一个特定的单独的历史s<-属于S<-映射为一个特定的状态ρ属于R;过去的随机变量S<-映射到有效状态的随机变量R。这里有一点区别,对于我们是否将μ想象为从历史到历史子集的函数,还是从历史到子集标签的函数。每一种解释在不同时间都有其方便之处,我们两者都会用到。

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

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

    我们将所有历史集合R<-划分的聚集叫奥卡姆水池。

C. 一些信息论

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产生的平均不确定性的减少量。它是非负的,如同这里所有的熵,而且在两个变量间是对称的。

D. 系统中的斑图

    如果有一种讨论将来的不确定性将是十分方便地。直观地这将是H[S->],但是在一般情况下数值是无限的,操作起来也是十分棘手的。(H[S->]是有限的特殊情形已经在附录F中处理过。)正常情况下,我们由考虑H[S->L]来回避这个问题,下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)。更有,如果h[S->] = H[S],过程对应到的无关变量,实际上,实际上我们在这里仅仅关心统计过程。


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

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

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

E.历史的课程

    我们现在处在证明系统斑图结果的位置,可用于连接后续关于因果态的定理。     引理1(旧世界引理)对于所有的R和所有的L属于Z+,

[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],其中Lpast是满足[math]\displaystyle{ H[\overset{\to L}{S} \vert \overset{\leftarrow}{S}] \lt LH[S] }[/math]的L的最小值。    

F. 最小化和预测

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

定义4(因果态的复杂度)状态类R的统计复杂度是

[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]中提示我们它有着量化理论的特性,并且最终依赖于过程序列的分布,能导出状态上的测量。

    一个状态类的统计复杂度是平均不确定度(单位是比特),在此过程的当前状态。这个,换句话说,是跟平均存储数量(单位是比特)一样,过程看上去是在保持过去,在给定选定的状态类R的条件下。(我们晚一点,在定义12中,查看如果定义一个过程它自己的统计复杂度。)这个目标是在尽可能少的存储下完成。再次申明,我们希望最小化统计复杂度,并符合最大准确预测的限制。         之所以称呼S<-的所有划分为奥卡姆水池背后的想法也应当清楚了。一个原因就是想找到水池当中最浅层的地方。 这就是我们刚刚做的。

Ⅳ. 计算力学

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

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

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

A.因果态

定义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个因果态写成Si,并将所有因果态的集合写成S;对应的随机变量描述成S,它的实现写为σ。

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

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

[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】,将所有在每个新划分的历史空间S<-划分成序列就更加直观了。使用L+1导出,是对使用L导出的细化。在最粗糙的级别上,最前面的划分(L = 1)组成了那些历史,对于每一个下个观测有相同分布。这些类就使用下两个观测值的分布做细分,然后是下三个,四个,以此类推。这些划分序列的极限——到那个点,点里每个类中的每个成员都有着对未来相同分布,不管长度如何,同那个类中的每个其它成员一样——是由∼ε导出的S<-的划分。参阅附录B以获取更详细的讨论并查看∼ε的等价关系。

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

2.将过程带到Si的历史集合,我们视为{s<- ∈ Si}。

3.在未来的条件分布,表示为P(S->|Si),并等于P(S->|s<-),s<-∈Si。自从我们倾向于分布频率这一种,而且自从它是“未来的图景”,我们称它为状态的变换。

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

图 2. 一个表示将所有历史的集合S<-划分到因果态Si ∈S的示意图。在每个因果态中所有的单独历史s<-拥有相同的变体——对将来对测相同的条件分布P(S->|s<-)。

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]

(再一次,这点对实际状态通常不是真的。)这种观测让我们证明一个有用的引理,关于过去S<-和未来S->条件无关。

引理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]


现在,P(S = ρ|S<- = s<-) = 0, 直到ρ = ϵ(s<-), 在这种情况P(S = ρ| S<- = s<-) = 1. 每种情况,在等式(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】以获取更多关于这些内容的讨论。

B. 因果状态到状态的转换

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

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

[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的继任者。我们用T表示集合[math]\displaystyle{ {T_{ij}^{(s)} : s \in 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] 其中s<-s读作准无限序列,由在s<-的末尾连接s∈A获得。

    证明。 [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]

现在 S = Si当有仅当 s<-∈Si, 并且 S' = Sj当且仅当s<-'∈Sj,其中s<-'我们表示紧随s<-其后的历史;为了统一,s<-' = s<-s。所以我们可以重写等式(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]

在第三行我们使用S<-=s<-和S<-'=s<-s的事实联合表明S->1 = s,使得条件相同。证毕。

    注意到Tij(λ) = δij;也就是,由空符号λ标志的转换是同一个。    

C. ϵ-机制

    从历史到因果态带有标记的转换概率Tij(s)的函数ϵ组合称作过程的ϵ-机制【5,6】。     定义9(一个ϵ-机制定义)

一个过程的ϵ-机制是有序对{ϵ,T},其中ϵ是因果态函数而T是由ϵ定义的状态转换矩阵。

等同地,我们或许由{S, T}表示一个ϵ-机制。

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

命题 1(ϵ-机制是幺半群)由ϵ-机制{ϵ, T}生成的代数是带单位元的半群, 也就是,它是幺半群。

证明。参看附录D。

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

引理 5(ϵ-机制是决定性的)对于每一个Si和s∈A,Tij(s)>0只对于那些Sj对于ϵ(s<-s)=Sj当且仅当ϵ(s<-)=Si,对于所有的过去s<-。

证明。这个引理是断言的等价,对所有s∈A和S<-,S<-'∈S<-,如果ϵ(s<-) = ϵ(s<-'),则ϵ(s<-s) = ϵ(s<-'s)。(s<-s是另一段历史且附属于这个或那个因果态。)

    假设这点不对。就有存在至少一个将来的s->符合

[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]

尽管ϵ(s<-) = ϵ(s<-')。等价地,我们应该有

[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]

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

[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]

这也是在说有一个未来ss->有不同的概率依赖于我们是用s<-还是s<-'的条件。但是这个对立面假设这两段历史附属于相同的因果态。因此,没有这样的未来s->,而引理替换的描述是真的。证毕。

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

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

备注3。很清楚的是,如果Tij(s) >0,那么Tij(s) = P(S->1 = s|S = Si)。在自动化理论里这个“不允许”转换(Tij(s) = 0)有时候是明显存在的,并且导向一个“弹出”状态指示对应部分历史没有发生。

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

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

[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(ϵ-机制重构)

ϵ-机制重构是任意给定一个过程P(S<->),或P(S<->)的一个近似,生成这个过程的ϵ-机制{S, T}的流程。

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

Ⅴ. 最佳性和唯一性

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

图例3。一个可供替代的状态的类R划分S<-覆盖在因果态S上(由实线绘出)。这里,作为例子,S2包含R1, R2, R3和R4的部分。这些所有可供替代的部分的集合构成了奥卡姆的水池。再次注意到Ri需要不是紧致的也不是简单连接的,如所绘制的那样。

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

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

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

对于所有的R和所有的L∈Z+,

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

证明。我们已经看到H[S->L|R]>=H[S->L|S<-](引理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]

自从熵仅依赖于概率分布,H[S->L|S] = H[S->L|S<-],对于每个L。因此,H[S->L | R] >= H[S->L | S],对于所有的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]

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