【作者】 向馗；

【导师】 蒋静坪；

【作者基本信息】 浙江大学 ， 控制理论与控制工程， 2006， 博士

【摘要】 计算力学是一个全新的理论框架，主要研究动力学系统中的几何状态空间如何支持符号推理计算。Santa Fe研究所的Crutchfield教授从80年代开始从事这方面的工作。ε机是计算力学体系中的主要理论工具，它的目标在于用尽可能少的人为假设，去揭示系统隐含的固有模式。因此，本文称ε机是一个模式发现的理论。 揭示系统隐含的模式或结构是复杂性研究的重要途径，在ε机理论中，称之为因果态重构。目前，最重要的ε机重构算法是Shalizi在2004年给出的因果态分割重构(CSSR)算法。CSSR算法分为3步：初始化、齐次化、确定化，它以概率统计(如条件概率、KS检验)为工具，能够从平稳的符号序列中推理出系统的因果态。每个因果态都由一系列字符串组成，它们具有相同的变体——条件概率分布。 ε机是复杂性研究中一个颇有价值但十分晦涩的理论，把它引入到工程研究中，是一项有意义的挑战。本文首先从ε机理论抽象出模式发现的思想，并把它同两个不同的问题——异常检测和强化学习相结合，给出了一系列新颖的算法和有意义的结论。其中，异常检测算法更多的表达了“模式”的思想，而强化学习算法更多的体现了“发现”的过程。多个实例分析证明了算法的有效性，同时也证明了ε机理论的客观性和普遍性。 异常检测算法包含一个重要假设：系统的特性演变非常缓慢，且体现在时间序列非平稳变化中。它包含两个重要步骤：时间序列的符号化；建立结构向量模型。 CSSR算法只适用用于符号序列，但多数时间序列都是实数的，因此，符号化处理是必需的。统计复杂性是基于ε机的全新的信息测度，可以作为符号化方法的判断标准。本文从多个不同领域选择了8组时间序列作为研究对象，用不同的方法作符号化处理，计算并比较它们的统计复杂性，得到了一系列经验结论。 把系统响应的时间序列做符号化处理，用CSSR算法重构出系统的因果态集合，把它们写成结构向量的形式，每个因果态对应向量的一维。结构向量是系更多还原

【Abstract】 Computational mechanics is a new theory frame to analyze how geometric state space structures support computation in dynamics systems. Professor Crutchfield of Santa Fe Institute has developed this frame since 1980s. Epsilon machine is a theory tool of computational mechanics, and its goal is to discover patterns intrinsic to a process about process’s structure with little priori assumptions. So in this paper Epsilon machine is called a theory of pattern discovery.Discovering hidden patterns or structures is a very important method to study complex systems. Actually, the process of discovery is to reconstruct causal states for the system. A new reconstruction algorithm, causal state splitting reconstruction (CSSR) was presented by Shalizi in 2004, which is fit for any stationary symbol time serials. There are three procedures in CSSR: initialize, homogenize and determinize, and probability statistics is its main tools, i.e. conditional probability and KS test. Every causal state comprises many strings, which have the same morphs.Epsilon machine is strange and mysterious to most people, and applying it to engineering problem is an instructive challenge. Two different problems, anomaly detection and reinforcement learning are studied based on epsilon machine. Several examples demonstrate that epsilon machine is effective and universal.The new anomaly detection algorithm includes a primary assumption and two important steps. The assumption is that the behavior of the system changes slowly and it can be detected from time series. The first step is time series symbolization and the second is structure vector (SV) model.Causal state can only be reconstructed using symbol series, but most time series is real, not symbol. So symbolization is necessary. Statistical complexity comes from epsilon machine, and it’s a good choice to evaluate kinds of symbolization ways. Eight groups of time series are symbolized by several ways and many empirical results are presented.Geometry structures can be inferred from symbol series by CSSR, which reflect更多还原