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

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

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

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

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

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

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