Data-driven system identification via evolutionary retrieval of Takagi-Sugeno fuzzy models  [Elektronische Ressource] / von: Ingo Renners
183 pages
Deutsch

Data-driven system identification via evolutionary retrieval of Takagi-Sugeno fuzzy models [Elektronische Ressource] / von: Ingo Renners

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Data Driven System IdentificationviaEvolutionary Retrieval of Takagi Sugeno Fuzzy ModelsDissertationzur Erlangung des akademischen GradesDoktoringenieur (Dr. Ing.)vorgelegt der Fakultat¨ fur¨ Informatikder Otto von Guericke Universit at¨ Magdeburgvon: Dipl. Inf. Ingo Rennersgeb. am 16. August 1969 in OpladenSoest, den 9. Marz¨ 2004ZusammenfassungSystemidentifikation hat die Aufgabe, eine Anzahl von zusammengehorenden¨ Kom ponenten der realen Welt in einem Modell abzubilden. Wenn diese Abbildung durchden Transfer von menschlichem Expertenwissen in ein Modell geschieht, wird dies alswissensbasierte Modellierung bezeichnet. Wenn die Informationen uber¨ das Systemallerdings nur implizit und formlos in Datenbestanden¨ vorliegen, wird die Abbildungdieses Wissens mit Hilfe von Algorithmen als datengetriebene Modellierung bezeich net.In dieser Arbeit wird vorgeschlagen, fur¨ die datengetriebene Systemidenti fizierung die Klasse der sogenannten Takai Sugeno Fuzzy Modelle zu benutzen.Dies wird durch das Vorhandensein effektiver Lernalgorithmen fur¨ diese Klasse vonModellen begrundet.¨ Des weiteren ist es oft vorteilhaft, die bei der Systemidenti fizierung gefundenen Modelle auch interpretieren zu konnen.¨ Daher wird auf dieFormulierung verschiedener Interpretierbarkeitsfaktoren, welche zu einem objektivenund leicht zu implementierendeneitsmaß fur¨ Takagi Sugeno Modellezusammengefuhrt¨ werden konnen,¨ besonderer Wert gelegt.

Sujets

Informations

Publié par
Publié le 01 janvier 2004
Nombre de lectures 27
Langue Deutsch
Poids de l'ouvrage 4 Mo

Exrait

Data Driven System Identification
via
Evolutionary Retrieval of Takagi Sugeno Fuzzy Models
Dissertation
zur Erlangung des akademischen Grades
Doktoringenieur (Dr. Ing.)
vorgelegt der Fakultat¨ fur¨ Informatik
der Otto von Guericke Universit at¨ Magdeburg
von: Dipl. Inf. Ingo Renners
geb. am 16. August 1969 in Opladen
Soest, den 9. Marz¨ 2004Zusammenfassung
Systemidentifikation hat die Aufgabe, eine Anzahl von zusammengehorenden¨ Kom
ponenten der realen Welt in einem Modell abzubilden. Wenn diese Abbildung durch
den Transfer von menschlichem Expertenwissen in ein Modell geschieht, wird dies als
wissensbasierte Modellierung bezeichnet. Wenn die Informationen uber¨ das System
allerdings nur implizit und formlos in Datenbestanden¨ vorliegen, wird die Abbildung
dieses Wissens mit Hilfe von Algorithmen als datengetriebene Modellierung bezeich
net.
In dieser Arbeit wird vorgeschlagen, fur¨ die datengetriebene Systemidenti
fizierung die Klasse der sogenannten Takai Sugeno Fuzzy Modelle zu benutzen.
Dies wird durch das Vorhandensein effektiver Lernalgorithmen fur¨ diese Klasse von
Modellen begrundet.¨ Des weiteren ist es oft vorteilhaft, die bei der Systemidenti
fizierung gefundenen Modelle auch interpretieren zu konnen.¨ Daher wird auf die
Formulierung verschiedener Interpretierbarkeitsfaktoren, welche zu einem objektiven
und leicht zu implementierendeneitsmaß fur¨ Takagi Sugeno Modelle
zusammengefuhrt¨ werden konnen,¨ besonderer Wert gelegt.
Um optimale Strukturen der Modelle zu identifizieren, werden neue Konzepte
¨aus dem Bereich der Heuristik, speziell der evolutionaren Berechnungsmethoden,
als generell nutzbare Suchmethode angewendet. Optimale und schlanke Modell
strukturen sind in Hinsicht auf Genauigkeit, aber insbesondere im Hinblick auf die
Generalisierungfahigk¨ eit von Modellen sehr wunschenswert.¨ Allerdings spielt die
notwendige Kodierung von potentiellen Modellen innerhalb einer kunstlichen¨ Evolu
tion eine bedeutende, wenn nicht sogar die entscheidende Rolle. Aus diesem Grunde
wird in dieser Arbeit eine in diesem Zusammenhang neuartige Methode der Kodierung
vorgeschlagen. Dabei wird der Suchraum eines evolutionaren¨ Algorithmus durch
sogenannte Genotyp Schablonen aufgespannt, welche mit Hilfe einer kontextfreien
Grammatik formuliert werden.
iiiiv
Die vorgeschlagene Methode zur Systemidentifizierung mittels Takagi Sugeno
Modellen wird dann an einem kunstlichen¨ und einem komplexen realen Problem
getestet. In der realen Problemstellung geht es um die Identifikation von Modellen,
welche die Toxizitat¨ von Molekulen¨ vorhersagen. Diese Modelle sollen also einen
Zusammenhang von einfach zu messenden oder zu berechnenden Eigenschaften von
Molekulen,¨ sogenannten molekularen Deskriptoren, zu deren Giftigkeit aufdecken
und herstellen.Abstract
System identification is the task to map several related components of a real world
system into a model. If this is done by transferring human expertise into a model, the
process is called knowledge driven modeling. If the system information is embedded
in data bases and the implicit existent expertise is mapped by algorithms into a model,
the process is called data driven modeling.
This thesis suggests for data driven system identification the class of Takagi
Sugeno fuzzy models as target. This class of models provides the possibility to make
use of powerful learning algorithms. On the other hand the human interpretability of
the resulting models can be assured.
Because of this, necessary interpretability factors are worked out and an objective
interpretability measure for Takagi Sugeno fuzzy models is formulated.
Evolutionary computation, as a general search method, is used to identify an
optimal model structure. Optimal and sparse model structures are desirable for reasons
of accuracy and generalization capability. The way in which candidate solutions (i.e.
models), are encoded in evolutionary algorithms is a central factor in population based
search methods. The author proposes a novel grammar based method to formulate
genotype templates. These templates will be used to define the genotype search space.
The presented approach of data driven system identification via evolutionary re
trieval of Takagi Sugeno fuzzy models is tested with artificial data and with a complex
real world dataset considering the prediction of molecular toxicity.
vAcknowledgments
First of all I want to thank my wife. The possibility to get the impression that my real
love is a computer was always existent but never true nor accused.
I also want to thank Prof. Grauel, one of the most reliable men I know, for steady
support, motivating discussions and holding off much of the bureaucracy many people
have to fight with. I consider the granted scientific freedom during my research as a
valuable present.
This scientific freedom also was supported by the Ministry of Sciences and Re
search, North Rhine Westphalia, through financial support and especially within the
European Union project COMET. Concerning this project my special thanks go to
Dr. Benfenati who provided me with the newest toxicity dataset used in the successor
project IMAGETOX.
I also want to thank Prof. Kruse who recommended this doctorate. Furthermore
he and his colleague Dr. Borgelt provided some very helpful suggestions which ac
counts for the completion of this thesis.
Finally I want to honor the idea of open source software, allowing me and mil
lions of other people to use thousands of algorithms and applications for free.
viContents
1 Introduction 1
1.1 Problem Statement and Motivation . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.1 Organization of the Content . . . . . . . . . . . . . . . . . . 3
1.3.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 System Identification 6
2.1 Model Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Scaled Models . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Flowcharts . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Look Up Tables . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.4 Mathematical Models . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Application Areas of System Identification . . . . . . . . . . . . . . . 9
2.2.1 System Identification with Computational Intelligence . . . . 10
2.2.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.4 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.5 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.6 Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Tasks in System Identification . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Selecting a Model Class . . . . . . . . . . . . . . . . . . . . 14
2.3.2 the Model Structure . . . . . . . . . . . . . . . . . 14
2.3.3 Parameter Optimization of the Model . . . . . . . . . . . . . 15
2.4 Parameter Optimization with Different Error Measures . . . . . . . . 15
viiviii Contents
2.4.1 Loss Functions and Cost Functions . . . . . . . . . . . . . . 15
2.4.2 Linear Parameter Optimization . . . . . . . . . . . . . . . . . 18
2.4.3 Polynomial Models . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Model Complexity and Regularization . . . . . . . . . . . . . . . . . 23
2.5.1 Model Complexity and Model Flexibility . . . . . . . . . . . 24
2.5.2 Bias Error and Variance Error . . . . . . . . . . . . . . . . . 25
2.5.3 Bias/Variance Tradeoff . . . . . . . . . . . . . . . . . . . . . 26
2.5.4 Implicit Structure Optimization . . . . . . . . . . . . . . . . 27
2.5.5 Explicit . . . . . . . . . . . . . . . . 27
2.6 Model Generalization Estimation . . . . . . . . . . . . . . . . . . . . 29
2.6.1 Good and Best Feature Subset . . . . . . . . . . . . . . . . . 29
2.6.2 Training , Validation and Test Dataset . . . . . . . . . . . . 30
2.6.3 Cross Validation . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6.4 Information Criteria . . . . . . . . . . . . . . . . . . . . . . 33
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3 Takagi Sugeno Fuzzy Models 35
3.1 Fuzzy Logic and Fuzzy Models . . . . . . . . . . . . . . . . . . . . . 35
3.2 Fuzzy Inference Systems . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 Membership Function Types . . . . . . . . . . . . . . . . . . 38
3.2.2 Fuzzy Operators . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.3 Reasoning Mechanism . . . . . . . . . . . . . . . . . . . . . 42
3.2.4 Defuzzification Method . . . . . . . . . . . . . . . . . . . . 42
3.2.5 The Output Evaluation of a Takagi Sugeno Fuzzy Model . . . 43
3.3 Interpretability Conditions of Fuzzy Models . . . . . . . . . . . . . . 44
3.3.1 Fuzzy Set Configurations Causing Semantic Inconsistency . . 46
3.3.2 Interpretability Factors . . . . . . . . . . . . . . . . . . . . . 47
3.3.3 An Exemplary Interpretability Measure . . . . . . . . . . . . 49
3.3.4 Avoiding the Curse of Dimensionality . . . . . . . . . . . . . 52
3.4 Takagi Sugeno Fuzzy Models . . . . . . . . . . . . . . . . . . . . . 53
3.4.1 Takagi Sugeno Fuzzy Models for System Identification . . . . 55
3.4.2 Parameter Estimation of Takagi Sugeno Fuzzy Models . . . . 55
3.4.3 Global Parameter Estimation of Takagi Sugeno FMs . . . . . 56
3.5 Structure Identification of Takagi Sugeno FMs. . . . . . . . . . . . . 58Contents ix
3.5.1 Feature Selection . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5.2 Input Space Partitioning . . . . . . . . . . . . . . . . . . . . 58
3.5.3 Fuzzy Set Shape Selection . . . . . . . . . . . . . . . . . . . 59
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4 Evolutionary Computation 60
4.1 Nomenclature of Evolutionary Computation . . . . . . . . . . . . . . 62
4.2 Genotype Representation . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2.1 The Biological Genotype . . . . . . . . . . . . . . . . . . . . 64
4.2.2 Non Coding Segments . . . . . . . . . . . . . . . 66
4.2.3 Artificial Genotypes . . . . . . . . . . . . . . . . . . . . . . 67
4.2.4 Fixed versus Variable Length Representation . . . . . . . . . 67
4.3 Solution Representation and Evaluation . . . . . . . . . . . . . . . . 68
4.3.1 Objective Function . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.2 Fitness Function . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.3 Search Space . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.4 Infeasible Solution Handling . . . . . . . . . . . . . . . . . . 73
4.3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4 Evolutionary Operators . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4.1 Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4.2 Recombination . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.3 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.5 Tree Based Genotype Representation . . . . . . . . . . . . . . . . . . 84
4.5.1 Tree Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.5.2 Tree Structures for Genotype Encoding . . . . . . . . . . . . 86
4.5.3 Example of a Tree Based Genotype Representation . . . . . . 87
4.5.4 Grammars as Framework for Genotype Templates . . . . . . 88
4.5.5 Constraint Handling in Tree Based Genotypes . . . . . . . . . 90
4.5.6 Evolutionary Operations on Tree Based Genotypes . . . . . . 90
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5 Evolutionary Optimization of Descriptive Takagi Sugeno FMs 92
5.1 Michigan vs. Pittsburgh Approach . . . . . . . . . . . . . . . . . . . 92
5.2 Acquiring the Genotype Tree Structure . . . . . . . . . . . . . . . . . 93x Contents
5.2.1 Rule Base and Knowledge Base . . . . . . . . . . . . . . . . 93
5.2.2 Genotype to Phenotype Mapping . . . . . . . . . . . . . . . . 94
5.2.3 B spline Specific Implementation Considerations . . . . . . . 94
5.2.4 Feature Set Selection . . . . . 95
5.2.5 Fuzzy Set Implementation Considerations . . . . . 96
5.3 The Used Genotype Template . . . . . . . . . . . . . . . . . . . . . 97
5.4 The Implemented Evolutionary Algorithm . . . . . . . . . . . . . . . 98
5.4.1 Implementation Environment . . . . . . . . . . . . . . . . . 98
5.4.2 Implemented Crossover . . . . . . . . . . . . . . . . . . . . 99
5.4.3 Structure Information Mutation . . . . . . . . . 100
5.4.4 Implemented Variable . . . . . . . . . 101
5.4.5 Evolutionary Loop . . . . . . . . . . . . . . . . 103
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Data Analysis 107
6.1 Artificial Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2 Real World Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2.1 Quantitative Structure Activity Relationships . . . . . . . . . 111
6.2.2 Data Description . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2.3 Molecular Descriptors . . . . . . . . . . . . . . . . . . . . . 112
6.2.4 Toxicity Prediction With Multi Linear Regression. . . . . . . 114
6.2.5 Toxicity With DTSFMs . . . . . . . . . . . . . . . 114
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7 Conclusions 127
7.1 Brief Summary of Work and Discussion . . . . . . . . . . . . . . . . 127
7.1.1 Inherently Fulfilling the Leveling Interpretability Condition . 129
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2.1 Incorporation of Process Knowledge . . . . . . . . . . . . . . 130
7.2.2 Hierarchical Modeling . . . . . . . . . . . . . . . . . . . . . 131
7.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
A List of Molecules 133
B List of Descriptors 140