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

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

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

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

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

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

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