Faculté informatique et communications IC, Département de systèmes de communication, Laboratoire de systèmes non linéaires LANOS (Laboratoire de systèmes non linéaires LANOS)

Modeling diversity by strange attractors with application to temporal pattern recognition

De Feo, Oscar ; Hasler, Martin (Dir.)

Thèse sciences techniques Ecole polytechnique fédérale de Lausanne EPFL : 2001 ; no 2344.

Ajouter à la liste personnelle
    Summary
    This thesis belongs to the general discipline of establishing black-box models from real-word data, more precisely, from measured time-series. This is an old subject and a large amount of papers and books has been written about it. The main difficulty is to express the diversity of data that has essentially the same origin without creating confusion with data that has a different origin. Normally, the diversity of time-series is modeled by a stochastic process, such as filtered white noise. Often, it is reasonable to assume that the time series is generated by a deterministic dynamical system rather than a stochastic process. In this case, the diversity of the data is expressed by the variability of the parameters of the dynamical system. The parameter variability itself is then, once again, modeled by a stochastic process. In both cases the diversity is generated by some form of exogenous noise. In this thesis a further step has been taken. A single chaotic dynamical system is used to model the data and their diversity. Indeed, a chaotic system produces a whole family of trajectories that are different but nonetheless very similar. It is believed that chaotic dynamics not only are a convenient means to represent diversity but that in many cases the origin of diversity stems actually from chaotic dynamic. Since the approach of this thesis explores completely new grounds the most suitable kind of data is considered, namely approximately periodic signals. In nature such time-series are rather common, in particular the physiological signal of living beings, such as the electrocardiograms (ECG), parts of speech signals, electroencephalograms (EEG), etc. Since there are strong arguments in favor of the chaotic nature of these signals, they appear to be the best candidates for modeling diversity by chaos. It should be stressed however, that the modeling approach pursued in this thesis is thought to be quite general and not limited to signals produced by chaotic dynamics in nature. The intended application of the modeling effort in this thesis is temporal signal classification. The reason for this is twofold. Firstly, classification is one of the basic building block of any cognitive system. Secondly, the recently studied phenomenon of synchronization of chaotic systems suggests a way to test a signal against its chaotic model. The essential content of this work can now be formulated as follows. Thesis: The diversity of approximately periodic signals found in nature can be modeled by means of chaotic dynamics. This kind of modeling technique, together with selective properties of the synchronization of chaotic systems, can be exploited for pattern recognition purposes. This Thesis is advocated by means of the following five points. Models of randomness (Chapter 2) It is argued that the randomness observed in nature is not necessarily the result of exogenous noise, but it could be endogenally generated by deterministic chaotic dynamics. The diversity of real signals is compared with signals produced by the most common chaotic systems. Qualitative resonance (Chapter 3) The behavior of chaotic systems forced by periodic or approximately periodic input signals is studied theoretically and by numerical simulation. It is observed that the chaotic system "locks" approximately to an input signal that is related to its internal chaotic dynamic. In contrast to this, its chaotic behavior is reinforced when the input signal has nothing to do with its internal dynamics. This new phenomenon is called "qualitative resonance". Modeling and recognizing (Chapter 4) In this chapter qualitative resonance is used for pattern recognition. The core of the method is a chaotic dynamical system that is able to reproduce the class of time-series that is to be recognized. This model is excited in a suitable way by an input signal such that qualitative resonance is realized. This means that if the input signal belongs to the modeled class of time-series, the system approximately "locks" into it. If not, the trajectory of the system and the input signal remain unrelated. Automated design of the recognizer (Chapters 5 and 6) For the kind of signals considered in this thesis a systematic design method of the recognizer is presented. The model used is a system of Lur'e type, i.e. a model where the linear dynamic and nonlinear static part are separated. The identification of the model parameters from the given data proceed iteratively, adapting in turn the linear and the nonlinear part. Thus, the difficult nonlinear dynamical system identification task is decomposed into the easier problems of linear dynamical and nonlinear static system identification. The way to apply the approximately periodic input signal in order to realize qualitative resonance is chosen with the help of periodic control theory. Validation (Chapter 7) The pattern recognition method has been validated on the following examples — A synthetic example — Laboratory measurement from Colpitts oscillator — ECG — EEG — Vowels of a speech signals In the first four cases a binary classification and in the last example a classification with five classes was performed. To the best of the knowledge of the author the recognition method is original. Chaotic systems have been already used to produce pseudo-noise and to model signal diversity. Also, parameter identification of chaotic systems has been already carried out. However, the direct establishment of the model from the given data and its subsequent use for classification based on the phenomenon of qualitative resonance is entirely new.
    Riassunto
    Riassunto Questa tesi si situa nell'ambito di quell'ampia disciplina che ha come scopo il determinare modelli a scatola nera partendo da dati reali, in particolare a partire da serie temporali. Il soggetto è piuttosto datato, di conseguenza una consistente letteratura esiste a proposito di questo argomento. Il problema principale è d'esprimere la diversità di quei dati che hanno sostanzialmente la stessa origine senza così generare confusione con altri dati la cui natura è essenzialmente diversa. Di solito, la diversità delle serie temporali è modellizata a mezzo di processi stocastici come, ad esempio, rumore bianco filtrato. D'altro canto, è spesso ragionevole supporre un'origine deterministica per i dati, considerandoli di conseguenza generati da un sistema dinamico piuttosto che da un processo stocastico. In questi casi, la diversità dei dati è trasferita sui parametri del sistema dinamico la cui variabilità è poi, ancora una volta, modellizata per mezzo di processi stocastici. Comunque sia, in entrambi i casi la diversità tipica delle misure è ricondotta ad un'origine stocastica, vale a dire ad un rumore esogeno. In questa tesi è stato compiuto un ulteriore passo. Un solo sistema dinamico caotico è utilizzato per modellizare ad un sol tempo sia i dati sia la loro diversità. In effetti, un sistema dinamico caotico è in grado di generare un'intera famiglia di traiettorie differenti ma comunque simili tra loro. A tal proposito, non solo si crede che le dinamiche caotiche siano un mezzo conveniente per la modellizzazione della diversità ma anche che, in molti casi, esse siano all'origine stessa di questa. Poiché l'approccio proposto in questa tesi esplora territori inesplorati, sono stati considerati i segnali più promettenti nella direzione proposta, ovvero i segnali approssimativamente periodici. Questo tipo di segnali è piuttosto comune in natura, in particolare sono tali quei segnali fisiologici degli esseri viventi quali gli elettrocardiogrammi (ECG), porzioni dei segnali del parlato, gli elettroencefalogrammi, etc. Siccome vi sono buone ragioni che fanno supporre una natura caotica di questi segnali, la loro diversità appare come buona candidata al fine d'essere modellizata per via caotica. Ciononostante, è necessario far presente che l'approccio modellistico perseguito in questa tesi è supposto essere piuttosto generale e, di conseguenza, si ritiene che esuli dall'effettiva natura caotica dei segnali. Il fine ultimo dello sforzo modellistico di questa tesi è la classificazione di segnali temporali. La ragione è duplice. In primo luogo, la classificazione è uno tra gli elementi di base di ogni sistema cognitivo. Secondariamente, il fenomeno della sincronizzazione dei sistemi caotici, recentemente studiato, si offre come possibile modalità pratica per confrontare un segnale al suo modello caotico. L'essenza di questo lavoro può essere espressa come segue. Tesi: La diversità dei segnali approssimativamente periodici che si osservano in natura può essere modellizata da sistemi dinamici caotici. Questa tecnica di modellizzazione, insieme alle le proprietà selettive della sincronizzazione dei sistemi caotici, può essere sfruttata per il riconoscimento di patterns. Questa Tesi è sostenuta a mezzo dei cinque punti seguenti. Modelli dei fenomeni aleatori (Capitolo 2) Si sostiene che l'aleatorietá osservata in natura non è necessariamente il risultato di perturbazioni rumorose esogene ma che, al contrario, può essere generata in maniera endogena da dinamiche caotiche deterministiche. La diversità caratteristica di segnali reali è confrontata con quella che può essere prodotta dai più comuni sistemi caotici. Risonanza qualitativa (Capitolo 3) Il comportamento dei sistemi caotici sotto forzante periodica, o approssimativamente periodica, è studiato sia teoreticamente che con il supporto di simulazioni numeriche. Si osserva che un particolare tipo di sistemi caotici si "aggancia" approssimativamente ai segnali d'ingresso che sono correlati con la dinamica caotica interna di questi sistemi. Al contrario, il comportamento caotico di questi sistemi e rinforzato da segnali d'ingresso che non hanno nulla a che fare con la loro dinamica interna. Questo nuovo fenomeno dinamico è stato chiamato "risonanza qualitativa". Modellizare e riconoscere (Capitolo 4) In questo capitolo la risonanza qualitativa è utilizzata per il riconoscimento di patterns. Il cuore del metodo è un sistema dinamico caotico che può riprodurre la classe di serie temporali che si vuole riconoscere. Un segnale esterno è applicato al sistema in modo tale da realizzare un filtro a risonanza qualitativa. Dunque, se il segnale d'ingresso appartiene alla classe di serie temporali modellizzate allora il sistema vi si "aggancia" approssimativamente. In caso contrario, la traiettoria del sistema ed il segnale d'ingresso rimangono incorrelati. Realizzazione automatica del classificatore (Capitoli 5 e 6) presentato, specificatamente per il tipo di segnali considerato in questa tesi, un metodo per la realizzazione sistematica del classificatore. Il modello di riferimento usato è un sistema di Lur'e, ovvero un sistema dinamico non lineare in cui vi è una netta separazione tra la parte lineare, che è dinamica, e la parte non lineare, che è statica. L'identificazione dei parametri del modello a partire dai dati avviene in maniera iterativa, adattando alternativamente la parte lineare e quella non lineare. Di conseguenza, il difficile compito di identificazione non lineare è decomposto nei due più semplici compiti di identificazione dinamica lineare e statica non lineare. Infine, la maniera in cui l'ingresso deve agire sul sistema cosicché la risonanza qualitativa sia garantita è determinata con l'aiuto della teoria del controllo periodico lineare. Validazione (Capitolo 7) Il metodo di riconoscimento di patterns proposto è stato validato sui seguenti esempi — Un esempio sintetizzato al calcolatore — Misure di laboratorio di un oscillatore di Colpitts — ECG — EEG — Vocali del segnale parlato Nei primi quattro casi si tratta di classificazione binaria mentre l'ultimo riguarda una classificazione su cinque classi. Sulla base di quanto noto all'autore il metodo di riconoscimento proposto è originale. I sistemi caotici sono già stati utilizzati per produrre sequenze pseudo aleatorie e per modellizare la diversità di alcuni segnali. Anche l'identificazione parametrica di sistemi caotici non è nuova. Ciononostante, la costituzione del modello a partire dai dati ed il suo conseguente utilizzo in problemi di classificazione per mezzo del fenomeno della risonanza qualitativa e completamente nuovo.
    Zusammenfassung
    Diese Dissertation gehört zur allgemeinen Disziplin der Black-Box-Modellierung basierend auf realen Daten, genauer gesagt, von gemessenen Zeit-Reihen. Dies ist ein altes Thema und eine große Menge von Artikeln und Büchern wurde schon darüber geschrieben. Die Hauptschwierigkeit liegt darin, die Vielfalt von Daten, die im Grunde den gleichen Ursprung haben, zu erfassen; ohne Verwirrung mit Daten zu schaffen, die einen anderen Ursprung haben. Normalerweise wird die Vielfalt von Zeit-Reihen durch einen stochastischen Prozeß, wie gefiltertes weißes Rauschen, modelliert. Oft ist es vernünftig anzunehmen, daß die Zeitreihe statt durch einen stochastischen Prozeß von einem deterministischen dynamischen System erzeugt wird. In diesem Fall wird die Vielfalt der Daten durch die Variabilität der Parameter des dynamischen Systems ausgedrückt. Die Parameter- Variabilität wird dann, einmal mehr durch einen stochastischen Prozeß modelliert. In beiden Fällen wird die Vielfalt durch eine Art exogenen Rauschens erzeugt. Diese Dissertation geht einen Schritt weiter. Ein einziges chaotisches dynamisches System wird benutzt, um die Daten und ihre Vielfalt zu modellieren. Ein chaotisches System produziert tatsächlich eine ganze Familie von Trajektorien, die sich voneinander unterscheiden, aber sich trotzdem sehr ähneln. Man nimmt an, daß chaotische Dynamik nicht nur ein zweckmäßiges Mittel ist, um Vielfalt darzustellen, sondern daß in vielen Fällen der Ursprung von Vielfalt tatsächlich von chaotischer Dynamik herrührt. Da der Ansatz dieser Dissertation vollkommen neue Grundlagen erforscht, wird die geeigneteste Art von Daten betrachtet, nämlich ungefähr periodische Signale. In der Natur sind solche Zeitreihen relativ häufig anzutreffen, besonders bei physiologischen Signalen von Lebewesen, wie Elektrokardiogramme (EKG), Teile von Sprach-Signalen, Elektroenzephalogramme (EEG) etc. Dort gibt es starke Argumente zugunsten der chaotischen Natur dieser Signale; sie scheinen die besten Kandidaten für eine Modellieren von Vielfalt durch Chaos zu sein. Es sollte aber betont werden, daß der Modellierungsansatz, der in dieser Dissertation verfolgt wird, für ziemlich allgemein angesehen wird und wird nicht auf Signale beschränkt ist, die durch chaotische Dynamik in der Natur produziert werden. Die vorgesehene Anwendung des Modellierungsansatzes in dieser Dissertation ist die Klassifikation von zeitlichen Signalen. Dafür gibt es zwei Gründe. Erstens ist Klassifikation ein wichtiger Baustein jedes kognitiven Systems. Zweitens schlägt das in der letzten Zeit studierte Phänomen der Synchronisation chaotischer Systeme einen Weg vor, ein Signal in Bezug zu seinem chaotischen Modell zu prüfen. Der wesentliche Inhalt dieser Arbeit kann nunmehr wie folgt formuliert werden. These: Die Vielfalt in der Natur vorkommender annähernd periodischer Signale kann mittels chaotischer Dynamik modelliert werden. Diese Art von Modellierungs-Technik, zusammen mit der selektiven Eigenschaft der Synchronisation chaotischer Systeme, kann für Mustererkennungs-Zwecke genutzt werden. Diese These wird mittels der folgenden fünf Punkte gerechtfertigt. Modell der Zufälligkeit (Kapitel 2) Es wird argumentiert, daß der in der Natur beobachtete Zufall nicht notwendigerweise das Ergebnis exogenen Rauschens ist, sondern endogen erzeugt worden sein könnte, durch deterministische chaotische Dynamik. Die Vielfalt realer Signale wird verglichen mit den Signalen, die von den bekanntesten chaotischen Systemen produziert werden. Qualitative Resonanz (Kapitel 3) Das Verhalten chaotischer Systeme, getrieben durch annähernd periodische Eingangssignale, wird theoretisch und durch numerische Simulation studiert. Es wird beobachtet, daß das chaotische System annähernd auf einem Eingangssignal "einrastet", das mit seiner internen chaotischen Dynamik verwandt ist. Im Gegensatz dazu wird sein chaotisches Verhalten verstärkt, wenn das Eingangssignal nichts mit seiner internen Dynamik zu tun hat. Dieses neue Phänomen wird "qualitative Resonanz" genannt. Modellierung und Erkennung (Chapter 4) In diesem Kapitel wird qualitative Resonanz zur Mustererkennung benutzt. Der Kern der Methode ist ein chaotisches dynamisches System, das fähig ist, die Klasse von Zeitreihen zu reproduzieren, die erkannt werden sollen. Dieses Modell wird auf eine geeignete Weise von einem Eingangssignal angeregt, damit qualitative Resonanz auftritt. Dies bedeutet, daß, wenn das Eingangssignal zur modellierten Klasse von Zeitreihen gehört, "rastet" das System annähernd darauf ein. Wenn nicht, bleiben die Trajektorie des Systems und das Eingangssignal ohne Beziehung. Automatisierter Entwurf des Erkenners (Kapitel 5 und 6) Für die Art von Signalen, die in dieser Dissertation betrachtet werden, wird eine systematische Entwurfsmethode des Erkenners vorgestellt. Das benutzte Modell ist ein System vom Typ Lur'e, d.h. ein Modell, bei dem der lineare dynamische und nichtlineare statische Teil getrennt sind. Die Identifikationen der Modellparameter von den gegebenen Daten wird iterativ fortgesetzt, indem abwechselnd der lineare und der nichtlineare Teil verbessert wird. Dadurch wird das schwierige nichtlineare dynamische Systemidentifikationsproblem in die leichteren Probleme linearer dynamischer und nichtlinearer statischer Systemidentifikation aufgeteilt. Die Art und Weise, in der das ungefähr periodischen Eingangssignal eingespeist wird, um sicherzustellen, daß qualitative Resonanz auftritt, wird mit der Hilfe periodischen Steuerungstheorie gewählt. Validierung (Kapitel 7) Die Mustererkennungsmethode ist für die folgenden Beispielen bestätigt worden — Ein synthetisches Beispiel — Labor-Messungen vom Colpitts-Oszillator — EKG — EEG — Vokale eines Sprachsignals In den ersten vier Fällen wurde eine binäre Einteilung getroffen. Im letzten Beispiel wurde eine Einteilung in fünf Klassen durchgeführt. Nach bestem Wissen des Autors ist diese Erkennungsmethode neu. Chaotische Systeme wurden schon benutzt, um Pseudo-Rauschen zu produzieren und Signal-Vielfalt zu modellieren. Auch ist Parameter- Identifikation chaotischer Systeme schon ausgeführt worden. Aber die direkte Ableitung des Modells basierend auf den gegebenen Daten und seine nachfolgende Verwendung zur Klassifikation, basierend auf dem Phänomen der qualitativen Resonanz, ist völlig neu.
    Résumé
    Cette thèse se situe dans le cadre de la vaste discipline qui a comme but d'établir des modèles de type boîte-noire à partir de données réelles, plus précisément, à partir de séries temporelles mesurées. C'est un thème plutôt ancien et donc une grande quantité de papiers et livres existe à ce sujet. La difficulté principale est d'exprimer la diversité des données qui sont de la même origine sans créer de confusion avec les données qui ont essentiellement une origine différente. Normalement, la diversité des séries temporelles est modélisée par un processus stochastique, comme, par exemple, le bruit blanc filtré. Souvent, il est raisonnable de supposer que la série temporelle est produite par un système dynamique déterministe plutôt qu'un processus stochastique. Dans ce cas, la diversité des données est exprimée par la variabilité des paramètres du système dynamique. La variabilité des paramètres elle-même est alors, encore une fois, modélisée par un processus stochastique. Dans les deux cas la diversité est supposée être produite par une forme de bruit exogène. Dans cette thèse, un pas supplémentaire a été fait. Un seul système dynamique chaotique est utilisé pour modéliser à la fois les données et leur diversité. En effet, un système chaotique peut produire une famille entière de trajectoires qui sont différentes mais néanmoins semblables. A ce propos, il est admis non seulement que les dynamiques chaotiques sont un moyen convenable pour la modélisation de la diversité mais que, aussi, en beaucoup de cas, elles sont à l'origine même de celle-ci. Puisque l'approche proposée dans cette thèse explore des territoires inexplorés, les signaux les plus prometteurs, dans la direction proposée, ont été considérés, soit les signaux approximativement périodiques. Ces types de signaux sont plutôt communs dans les phénomènes naturels, notamment les signaux physiologiques des êtres vivants tels que les électrocardiogrammes (ECG), les signaux de parole en partie, les électroencéphalogrammes, etc. Comme il y a des bonnes raisons pour supposer une nature chaotique de ces signaux, leur diversité apparaît comme une bonne candidate pour être modélisée de façon chaotique. Pourtant, il faut préciser que l'approche de modélisation poursuivie dans cette thèse est supposée être plutôt générale donc pas limitée à des signaux produits par des systèmes chaotiques par nature. Le but ultime de l'effort de modélisation de cette thèse est la classification de signaux temporels. La raison en est double: premièrement, la classification est un des éléments de base de tous les systèmes cognitifs; deuxièmement, le phénomène de la synchronisation des systèmes chaotiques, récemment étudié, se prête comme une possibilité pratique de comparer un signal à son modèle chaotique. L'essentiel du contenu de ce travail peut être formulé comme suit. Thèse : La diversité des signaux approximativement périodiques qui s'observent dans la nature peut être modélisée au moyen de dynamiques chaotiques. Cette technique de modélisation, avec les propriétés sélectives de la synchronisation des systèmes chaotiques, peut être exploitée pour la reconnaissance de patterns. Cette Thèse est soutenue par les cinq points suivants. Modèles des phénomènes aléatoires (Chapitre 2) On soutient que le caractère aléatoire observé dans la nature n'est pas nécessairement le résultat de perturbations bruyantes exogènes mais que, au contraire, il peut être engendré de manière endogène par des dynamiques chaotiques déterministes. La diversité caractéristique de signaux réels est comparée avec celle qui peut être produite par les systèmes chaotiques les plus simples. Résonance qualitative (Chapitre 3) Le comportement de systèmes chaotiques forcés périodiquement, ou approximativement périodiquement, est étudié soit en théorie soit à l'aide de simulations numériques. On observe qu'un type particulier de systèmes chaotiques "s'accroche" approximativement aux signaux d'entrée quand ils sont corrélés avec leur propre dynamique chaotique interne. Au contraire, le comportement chaotique de ces systèmes est renforcé par des signaux d'entrée qui n'ont rien à faire avec leur dynamique interne. Ce nouveau phénomène dynamique a été appelé "résonance qualitative". Modéliser et reconnaître (Chapitre 4) Dans ce chapitre la résonance qualitative est utilisée pour la reconnaissance de patterns. Le noyau de la méthode est un système dynamique chaotique qui peut reproduire la classe de séries temporelles à reconnaître. Un signal extérieur est appliqué au système de manière à réaliser un filtre à résonance qualitative. Donc, si le signal d'entrée appartient à la classe de séries temporelles modélisée alors le système "s'accroche" approximativement. Dans le cas contraire, la trajectoire du système et le signal d'entrée restent non corrélés. La conception automatisée du classificateur (Chapitres 5 et 6) Il est présenté, spécifiquement pour le type de signaux considéré dans cette thèse, une méthode pour la réalisation systématique du classificateur. Le modèle de référence utilisée est un système de Lur'e, c'est-à-dire un système dynamique dans lequel il y a une séparation nette entre la partie linéaire, qui est dynamique, et la partie non linéaire, qui est statique. L'identification des paramètres du modèle à partir des données procède itérativement en adaptant alternativement la partie linéaire et la partie non linéaire. Donc, la tâche difficile de l'identification du système dynamique non linéaire est décomposée dans les taches plus faciles d'identification du système linéaire dynamique et d'identification du système non linéaire statique. Finalement, la manière avec laquelle l'entrée doit agir sur le système de façon que la résonance qualitative soit garantie est déterminée à l'aide de la théorie du contrôle périodique linéaire. Validation (Chapitre 7) La méthode de la reconnaissance de patterns a été validée sur les exemples suivants — Un exemple synthétisé à l'ordinateur — Mesures de laboratoire d'un oscillateur de Colpitts — ECG — EEG — Voyelles de signaux de parole Dans les quatre premier cas il s'agit de classement binaire tandis que le dernier concerne un classement en cinq classes. A connaissance de l'auteur, la méthode de reconnaissance proposée est originale. Les systèmes chaotiques ont déjà été utilisés pour produire des séquences pseudo-aléatoires et pour modéliser la diversité de quelques signaux. L'identification paramétrique de systèmes chaotiques n'est pas nouvelle non plus. Par contre, l'établissement direct du modèle à partir des données et son usage pour des problèmes de classement utilisant le phénomène de la résonance qualitative est complètement nouveau.