复杂系统的模式发现 ——ε机的理论与应用

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 致谢
• 目录
• 表格目录
• 插图目录
• 第1章 绪论
• 1.1 复杂系统
• 1.1.1 复杂性研究的流派
• 1.1.2 SFI的研究
• 1.1.3 Crutchfield与新的计算力学
• 1.2 论文结构
• 第2章 模式发现
• 2.1 模式发现与ε机
• 2.1.1 模式
• 2.1.2 ε机
• 2.1.3 ε机重构
• 2.1.4 结构测度
• 2.1.5 推广及应用
• 2.2 重构算法
• 2.2.1 因果态分割重构算法
• 2.2.2 子树合并算法
• 2.2.3 统计复杂性的计算
• 2.2.4 算法性能评价
• 第3章 基于结构向量的异常检测算法
• 3.1 非平稳时间序列与处理方法
• 3.1.1 非平稳时间序列
• 3.1.2 常见的处理方法
• 3.2 时间序列的符号化处理
• 3.2.1 符号化与评价标准
• 3.2.2 符号化方法
• 3.2.3 性能分析
• 3.3 异常检测算法
• 3.3.1 算法的核心思想
• 3.3.2 提取结构向量
• 3.3.3 定义异常测度
• 3.3.4 D-Markov机
• 3.4 实例分析
• 3.4.1 Duffing振子的分叉
• 3.4.2 曲轴的疲劳断裂试验
• 3.4.3 振动时效试验
• 3.4.4 SV模型的性能分析
• 第4章 基于隐含状态的强化学习算法
• 4.1 POMDP模型
• 4.1.1 模型介绍
• 4.1.2 算法介绍
• 4.1.3 应用介绍
• 4.2 隐含状态的分割重构
• 4.2.1 用ε机理论分析POMDP问题
• 4.2.2 HSSR算法
• 4.2.3 实例分析
• 4.3 基于隐含状态的Q学习
• 4.3.1 在线的HSSR算法
• 4.3.2 HSSR-Q算法
• 4.3.3 实例分析
• 4.4 动作不确定性的研究
• 4.4.1 改进的HSSR算法
• 4.4.2 算法性能分析
• 第5章 总结与展望
• 5.1 全文总结
• 5.2 未来工作的展望
• 附录
• 附录A Occam剃刀
• 附录B 概率自动机
• 附录C KS检验
• 附录D 矩阵理论
• 附录E Finite-type Shift and Sofic Shift
• 参考文献
• 攻读博士学位期间完成的论文