Računski zasnovano modeliranje dinamičkih sustava : doktorski rad - Logožar, Robert; Budin, Leo (Zagreb, R. Logožar ; Fakultet elektrotehnike i računarstva, 2012)
SAŽETAK: U ovom multidisciplinarnom radu opisano je, implementirano i primijenjeno modeliranje jednodimenzionalnih dinamičkih sustava u kojem se isključivo na temelju primljenog binarnog vremenskog niza gradi računski model s pridodanim stohastičkim svojstvima. U teorijskom uvodu pokazana je korektnost takvog pristupa. Simbolička dinamika povezana je s kodiranjem u mjerno-modelirajućem kanalu i aproksimirana podnizovima konačne duljine. Između nekoliko računarskih metodologija Crutchfieldova teorija ε-strojeva odabrana je kao najprikladnija za modeliranje iz vremenskog niza. U njoj je temeljni ε-stroj predstavljen stohastičkim konačnim automatom (SFA), koji je ovdje izveden iz konačnih automata (FA). Ilustrirana je podudarnost stohastičkih nedeterminističkih konačnih automata (SNFA) sa skrivenim Markovljevim modelima temeljenim na granama grafa (EOHMM). Dan je i pregled složenijih automata koji su kandidati za ε-strojeve viših razina. Uvedene su operativne inačice osnovnih pojmova teorije ε-strojeva: (L, δ)-ekvivalentna uzročna stanja i njihova praktična zamjena ─ (L, δ)-morfovi (nadalje, morfovi), te pripadni razredi ekvivalencije. Poznata stanja i njihove vjerojatnosti prijelaza određuju prijelazni tenzor te ε-stroj i SFA. Uvedeni su broj morfovima koreliranih simbola i duljina tako istražene korelacije, te duljina korelacije SFA-modela i njegova rekurentnog ciklusa. Opisan je hijerarhijski proces gradbe ε-strojeva. Iz vremenskog niza kreira se raščlambeno stablo visine D, u kojem se morfovi nalaze kao (L,δ)-jedinstvena podstabla. Ta (pod)stabla ─ s listovima na konstantnoj razini (L) D ─ teorijski su razrađena i nazvana ε-(pod)stabla. Njihova se statistika temelji na prosječnom broju bl djece iz čvora na l-toj razini. Glavni računarski doprinos ovog rada izvorni su FM i TFM algoritmi. Oni nalaze morfove (stanja) i njihove međusobne prijelaze i vjerojatnosti, te time definiraju SFA-model sustava. Uz parametre modela L i δ FM algoritam nalazi najdublji morf na razini lDM i općenito staje prije provjere svih podstabla. Stoga kažemo da je on potencijalno površan. Uvjet regularnosti dobivenog SFA jest ldm + L + 1 ≤ D. Uveden je koncept sveobuhvatnog modeliranja u kojem se varijacijom parametara L i δ ─ uz odabranu minimalnu rezoluciju potonjeg ─ na zadanom glavnom stablu istražuje cijeli prostor rješenja FM algoritma. Temeljiti (punoprolazni), TFM algoritam provjerava sva podstabla raščlambenog stabla, a potom uklanja ona koja su (L, δ)-ekvivalentna nekom ranijem podstablu (morfu). On načelno potvrđuje korektnost rezultata FM algoritma. Oba algoritma garantiraju minimalnost i determinističnost svojih regularnih SFA-modela, što im je glavna prednost pred drugim algoritmima iste namjene. Iznijeta je cjelovita informacijsko-teorijska analiza primljenog vremenskog niza i SFA-modela. Definirane su njihove stope entropija i različite složenosti, uključujući i statističku složenost. Na izvoran je način ekspliciran rastav ukupne entropije SFA-modela na sumu statističke složenosti i stope entropije modela. Dokazano je da se stopa entropije modela dalje rastavlja na sumu stope entropije niza odaslanog iz modela i nedeterminiranosti prijelaza, ili na sumu stope entropije Markovljevog izvora i novouvedene stope entropije simbola po prijelazu. Definirani teorijsko-informacijski pokazatelji izračunani su za raznovrsne sustave, a za periodične su i dokazani. Modeliranje do razine SFA ostvareno je u našem programskom alatu DSA. Opisana je implementacija podatkovnih struktura i algoritama korištenih u njegova tri glavna programska modula: za simulaciju dinamičkih sustava, za hranidbu binarnog raščlambenog (glavnog) stabla i za nalaženje SFA. Pregledavanje vremenskog niza, glavnog stabla, morfova i dobivenih modela omogućeno je u grafičkim sučeljima. Za ostvarenje statistički relevantnog glavnog stabla, vremensko-prostorna složenost procesa hranidbe eksponencijalna je u njegovoj visini D. Dokazana je korektnost izvornih algoritama za nerekurzivni prolazak kroz stabla te napravljena njihova usporedba s rekurzivnim algoritmima. FM algoritam unaprijeđen je u odnosu na prvobitnu inačicu. Za njega je implementacija pomno obrazložena, a za vrlo opsežan TFM algoritam u bitnim crtama. Napravljena je iscrpna analiza vremenske složenosti FM algoritma za slučajeve različitih glavnih stabala i različitih načina njegova rada. Općenito je ta složenost eksponencijalna u raznim linearnim kombinacijama parametara L i D, a u najgorem slučaju u njihovoj razlici 2D − L. DSA program primijenjen je za modeliranje brojnih sustava. Za njihova su raščlambena ε-stabla utvrđene krajnje razine statističke konzistentnosti, odnosno maksimalne visine korektnih glavnih stabala u kojima će se nalaziti morfovi. Te su razine teorijski povezane s točnosti numeričkog izračuna i s Lyapunovljevim eksponentom sustava. Za periodične i sustave zadane pravilom te za potpuno kvazistohastičke sustave dobivaju se točni SFA-modeli i uz uporabu FM i TFM algoritama. To vrijedi i za logističko preslikavanje u nastupu kaosa na kraju puta udvostručavanjem perioda, za koje porastom duljine L morfa broj stanja SFA divergira. Tu su dobiveni SFA-modeli plauzibilniji od prethodno poznatih, a na višoj je razini potvrđen konačan registarski stroj. Logistička preslikavanja u kaosu na mahove, za Misiurewiczev parametar i nadomak potpunog kaosa pokazuju strukturu izmiješanu s kvazistohastičnosti. Sveobuhvatno modeliranje ovih sustava za zadani L i sve manji δ daje niz sve preciznijih SFA-modela, sa sve većim brojem stanja. Na temelju njihovih grafova i izračunanih informacijsko-teorijskih pokazatelja odabrani su oni najreprezentativniji. Neki su od njih potvrđeni i TFM algoritmom. Takav složen postupak modeliranja učinkovito obavlja humani modelar s pomoću DSA programa. Time je ustanovljena funkcionalna modelirajuća platforma, pogodna za daljnju nadogradnju i poopćenja. - KLJUČNE RIJEČI: modeliranje, (nelinearni) dinamički sustavi, binarni vremenski niz, teorija ε-strojeva, stohastički konačni automati, mjere složenosti sustava, FM i TFM algoritmi, prostorno-vremenska kompleksnost algoritama, DSA program, logističko preslikavanje
ABSTRACT: In this multidisciplinary work we describe, implement, and apply the modeling of one-dimensional dynamical systems in which the computational model with added stochastic properties is built solely from the received binary time series. The introductory theoretical chapters show the correctness of such an approach. Symbolic dynamics is connected to the encoding in the measuring-modeling channel and approximated by the finite-length substrings. Among a few presented methodologies, the Crutchfield theory of ε-machines is selected as the best for the modeling from a time series. The basic ε-machine is presented by a stochastic finite automaton (SFA), which is here derived from the class of finite automata (FA). The equality of the stochastic nondeterministic finite automata (SNFFA) to the edge-output hidden Markov models (EOHMM) is illustrated. The more complex automata suitable for the higher-level ε-machines are also presented. The basic concepts of the theory of ε-machines are given their operational versions: (L, δ)-equivalent causal states and their practical substitutions ─ (L, δ)-morphs (further, morphs), which define the classes of equivalence. Known states and their transitions' probabilities define the transition tensor, and thus an ε-machine and its SFA. The num-ber of the morph-correlated symbols and the morph-investigated correlation length are introduced, as well as the correlation length of the SFA-model and the length of its re-current cycle. The reconstruction of ε-machines is a hierarchical process. From the time series, the parse tree of height D is created, wherefrom morphs are found as (L, δ)-unique subtrees. These ε-(sub)trees ─ with leaves at the constant level (L) D ─ are theo-retically described. Their statistics is based on the average number bl of children from an l-level node. The main computational contributions of this work are original FM and TFM algorithms. They find morphs (states), their mutual transitions and probabilities, and thus define the SFA-model of a system. For given L and δ, FM algorithm finds the deepest morph on level lDM and generally stops before having checked all the subtrees. This is called (potential) superficiality. The condition for a regular SFA is ldm + L + 1 ≤ D. The concept of comprehensive modeling is introduced. By the variation of L and δ ─ with a chosen resolution for the latter ─ the whole space of the FM algorithm solutions for a parse tree of height D is being explored. The thorough, TFM algorithm first investi-gates all the subtrees in the parse tree and then removes those which are (L, δ)-equivalent to earlier subtrees. It confirms the correctness of the FM algorithm results. Both algorithms guarantee the minimality and determinism of their regular SFA-models, which is their main advantage over other algorithms of the same purpose. A complete information-theoretical analysis of the time series and the SFA-model is given. The corresponding entropy rates and various complexities are defined. An original expansion of the SFA total entropy to the sum of statistical complexity and the model entropy rate is presented. It is proved that the latter can be resolved as the sum of the entropy rate of the time series emitted from the model and the transition indeterminacy, or the sum of the entropy rate of the Markov source and the newly introduced symbol-per-transition entropy rate. All defined quantities are calculated for various dynamical systems and proven for the periodic ones. The modeling up to the SFA level is realized by our original DSA programming tool. The implementation of data structures and algorithms used in its three main programming modules is presented. Inspection of the time series, main (parse) tree, morphs and the created models is possible via graphical user interfaces. The time-space complexity of the tree-feed process for a statistically relevant main tree is generally exponential in the tree height D. Correctness of the original nonrecursive tree-traversal algorithms was proven, and they were compared to the recursive versions. FM algorithm is upgraded from its first version. Its implementation is described in detail, and the implementation of the extensive TFM algorithm in its essential parts. The exhaustive analysis of FM algorithm time complexity is made for the cases of different parse trees and different ways of its operation. For general systems, this complexity is exponential in different linear combinations of parameters L and D and in the worst case in their difference 2D − L. DSA program was applied for the modeling of numerous systems. For their parse ε-trees, the utmost levels of statistical consistency had been determined, so that their morphs were being found from the consistent main trees. Those levels were theoretically connected to the accuracy of numerical calculation and Lyapunov exponent of the system. For periodical, rule-defined, and fully quasi-stochastic systems, both, FM and TFM algorithms give the exact SFA-models. The same is true for the logistic map at the onset of chaos by the end of the period-doubling route, for which the number of SFA states diverge with increasing morph height L. Here, more plausible SFA-models were obtained than previously known. Also, on a higher level, a finite reg-ister machine is confirmed. Logistic maps at the intermittency chaos, Misiurewicz parameter, and near the climax of chaos show structure mixed with quasi-stochasticity. The comprehensive modeling of these systems for a given range of L and decreasing δ gives more and more precise SFA-models, with increasing number of states. Based on their graphs and the calculated information-theoretic indicators, the best representative models are chosen among them. Some of them were confirmed by the TFM algorithm. Such a complex modeling task can be effectively accomplished by a human modeler with the aid of the DSA program. By this, we have provided a functional modeling plat-form that is suitable for further upgrades and generalizations. - KEYWORDS: modeling, (nonlinear) dynamical systems, time series, theory of ε-machines, stochastic finite automata, complexity measures, algorithms, data structures, algorithm space-time complexity, DSA program, logistic map
Na spor. nasl. str. naslov na eng. jeziku: Computationally Based Modeling of Dynamical Systems : doctoral thesis
Bibliografija: 333 - 338 str. - Sažetak na eng. i hrv. jeziku. - Životopis [uključuje i popis objavljenih radova autora]