复杂系统模式发现——ε机理论和应用论文

《复杂系统模式发现——ε机理论和应用论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要计算力学是一个全新的理论框架，主要研究动力学系统中的几何状态空间如何支持符号推理计算。SantaFe研究所的Crutchfield教授从80年代开始从事这方面的工作。￡机是计算力学体系中的主要理论工具，它的目标在于用尽可能少的人为假设，去揭示系统隐含的固有模式。因此，本文称￡机是一个模式发现的理论。揭示系统隐含的模式或结构是复杂性研究的重要途径，在￡机理论中，称之为因果态重构。目前，最重要的￡机重构算法是Shalizi在2004年给出的因果态分割重构(CSSR)算法。CSSR算法分为3步：初始化、齐

2、次化、确定化，它以概率统计(如条件概率、KS检验)为工具，能够从平稳的符号序列中推理出系统的因果态。每个因果态都由一系列字符串组成，它们具有相同的变体——条件概率分布。￡机是复杂性研究中一个颇有价值但十分晦涩的理论，把它引入到工程研究中，是一项有意义的挑战。本文首先从￡机理论抽象出模式发现的思想，并把它同两个不同的问题——异常检测和强化学习相结合，给出了一系列新颖的算法和有意义的结论。其中，异常检测算法更多的表达了“模式”的思想，而强化学习算法更多的体现了“发现”的过程。多个实例分析证明了算法的有效性，

3、同时也证明了￡机理论的客观性和普遍性。我们的工作主要体现在以下一些方面。：异常检测算法包含一个重要假设：系统的特性演变非常缓慢，且体现在时问序列非平稳变化中。它包含两个重要步骤：时问序列的符号化；建立结构向量模型。CSSR算法只适用用于符号序列，但多数时间序列都是实数的，因此，符号化处理是必需的。统计复杂性是基于￡机的全新的信息测度，可以作为符号化方法的判断标准。本文从多个不同领域选择了8组时间序列作为研究对象，用不同的方法作符号化处理，计算并比较它们的统计复杂性，得到了一系列经验结论。把系统响应的时间

4、序列做符号化处理，用CSSR算法重构出系统的因果态集浙江大学博士论文；复杂系统的模式发现合，把它们写成结构向量的形式，每个因果态对应向量的一维。结构向量是系统特性的表达式，它可以刻画系统内部两种不同性质的演变：一是因果态内部的变化：二是因果态的出现或消失。前者是一种量的变化，后者更倾向于质变。在结构向量的基础上定义异常测度，描绘系统的异常演变曲线，因果态的出现或消失会导致曲线的大幅跳跃。这种跃变可以作为系统出现危险的预警信号，它可以在一定程度上取代人为定义的阈值。3个实例：Duffing振子、疲劳断裂、

5、振动时效从不同侧面证明了算法的有效性。半观测马尔可夫决策过程(POMDP)是一个经典的强化学习问题。如果从￡机的角度来分析它，把POMDP问题转变成全观测MDP问题的过程就是一个模式发现的过程。POMDP中的隐含状态同￡机理论中的因果态具有对应关系。为此，在CSSR算法的基础上，提出了隐含状态分割重构(HSSR)算法。在HSSR算法中，观测字符串的变体定义为它周围的观测，并用自定义的齐次性检验取代了Ks检验。从Agent走迷宫的实验来看，HSSR算法能帮助Agent有效辨识它在迷宫中所处的位置。HSSR

6、算法纠正了状态扭曲的问题，把它同Q学习相结合就组成了完整的强化学习算法HSSR—Q。两者的融合存在关键障碍：如何保存并使用Q值。在HSSR-Q算法中，由字符串负责保存并更新Q值，字符串的Q值加权平均得到隐含态的Q值，Agent根据隐含态的9值来做出决策。HSSR—Q算法实现了隐含状态揭示和动作策略学习的同步进行，并收到了较好的效果。本文全面而系统的介绍了￡机理论，并把这项复杂系统的研究成果同工程实践紧密结合，做了多方面的研究，得到了全新的算法和结论，同时也体现了￡机理论的工程价值。关键词：复杂系统；模式

7、发现：￡机；异常检测；强化学习。ll摘要AbstractComputationalmechanicsisanewtheoryflametoanalyzehowgeometricstatespacestructuressupportcomputationindynamicssystems．ProfessorCrutchfieldofSantaFeInstitutehasdevelopedthisframesince1980s．Epsilonmachineisatheorytoolofcomputation

8、almechanics，anditsgoalistodiscoverpatternsintrinsictoaprocessaboutprocess’Sstructurewithlittleprioriassumptions．SointhispaperEpsilonmachineiscalledatheoryofpatterndiscovery．Discoveringhiddenpatternsorstructuresisaveryimpor