復雜系統(tǒng)的模式發(fā)現——ε機的理論與應用.pdf

1、計算力學是一個全新的理論框架，主要研究動力學系統(tǒng)中的幾何狀態(tài)空間如何支持符號推理計算。Santa Fe研究所的Crutchfield教授從80年代開始從事這方面的工作。ε機是計算力學體系中的主要理論工具，它的目標在于用盡可能少的人為假設，去揭示系統(tǒng)隱含的固有模式。因此，本文稱ε機是一個模式發(fā)現的理論。 揭示系統(tǒng)隱含的模式或結構是復雜性研究的重要途徑，在ε機理論中，稱之為因果態(tài)重構。目前，最重要的ε機重構算法是Shalizi在20

2、04年給出的因果態(tài)分割重構(CSSR)算法。CSSR算法分為3步：初始化、齊次化、確定化，它以概率統(tǒng)計(如條件概率、KS檢驗)為工具，能夠從平穩(wěn)的符號序列中推理出系統(tǒng)的因果態(tài)。每個因果態(tài)都由一系列字符串組成，它們具有相同的變體——條件概率分布。 ε機是復雜性研究中一個頗有價值但十分晦澀的理論，把它引入到工程研究中，是一項有意義的挑戰(zhàn)。本文首先從ε機理論抽象出模式發(fā)現的思想，并把它同兩個不同的問題--異常檢測和強化學習相結合，給出

3、了一系列新穎的算法和有意義的結論。其中，異常檢測算法更多的表達了“模式”的思想，而強化學習算法更多的體現了“發(fā)現”的過程。多個實例分析證明了算法的有效性，同時也證明了ε機理論的客觀性和普遍件。我們的工作主要體現在以下一些方面。 異常檢測算法包含一個重要假設：系統(tǒng)的特性演變非常緩慢，且體現在時間序列非平穩(wěn)變化中。它包含兩個重要步驟：時間序列的符號化；建立結構向量模型。 CSSR算法只適用用于符號序列，但多數時間序列都是實數

4、的，因此，符號化處理是必需的。統(tǒng)計復雜性是基于ε機的全新的信息測度，可以作為符號化方法的判斷標準。本文從多個不同領域選擇了8組時間序列作為研究對象，用不同的方法作符號化處理，計算并比較它們的統(tǒng)計復雜性，得到了一系列經驗結論。 把系統(tǒng)響應的時間序列做符號化處理，用CSSR算法重構出系統(tǒng)的因果態(tài)集合，把它們寫成結構向量的形式，每個因果態(tài)對應向量的一維。結構向量是系統(tǒng)特性的表達式，它可以刻畫系統(tǒng)內部兩種不同性質的演變：一是因果態(tài)內部的

5、變化；二是因果態(tài)的出現或消失。前者是一種量的變化，后者更傾向于質變。在結構向量的基礎上定義異常測度，描繪系統(tǒng)的異常演變曲線，因果態(tài)的出現或消失會導致曲線的大幅跳躍。這種躍變可以作為系統(tǒng)出現危險的預警信號，它可以在一定程度上取代人為定義的閾值。3個實例：Duffing振子、疲勞斷裂、振動時效從不同側面證明了算法的有效性。半觀測馬爾可夫決策過程(POMDP)是一個經典的強化學習問題。如果從ε機的角度來分析它，把POMDP問題轉變成全觀測Ml

6、DP問題的過程就是一個模式發(fā)現的過程。POMDP中的隱含狀態(tài)同￡機理論中的因果態(tài)具有對應關系。為此，在CSSR算法的基礎上，提出了隱含狀態(tài)分割重構(HSSR)算法。在HSSR算法中，觀測字符串的變體定義為它周圍的觀測，并用自定義的齊次性檢驗取代了KS檢驗。從Agent走迷宮的實驗來看，HSSR算法能幫助Agent有效辨識它在迷宮中所處的位置。 HSSR算法糾正了狀態(tài)扭曲的問題，把它同Q學習相結合就組成了完整的強化學習算法HSSR