Fuzzy operator trees for modeling utility functions [Elektronische Ressource] / vorgelegt von Yu Yi

Yu Yi

Sujets

• Informatik
• Mathematics

Informations

• Publié par: philipps-universitat_marburg
• Publié le: 01 janvier 2008
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Fuzzy Operator Trees for Modeling Utility
Functions
Dissertation
zur
Erlangung des Doktorgrades
der Naturwissenschaften
(Dr. rer. nat.)
dem
FachbereichMathematikundInformatik
derPhilipps UniversitätMarburg
vorgelegtvon
YuYi
ausChangsha,China
Marburg/Lahn2008VomFachbereichMathematikundInformatik
derPhilipps UniversitätMarburg
alsDissertationam08.12.2008angenommen.
Erstgutachter: Prof. Dr. EykeHüllermeier
Zweitgutachter: Prof. Dr. BerndFreisleben
TagdermündlichenPrüfungam12.12.2008Abstract
In this thesis, we propose a method for modeling utility (rating) functions based on
a novel concept called Fuzzy Operator Tree (FOT for short). As the notion sug
gests, this method makes use of techniques from fuzzy set theory and implements a
fuzzy rating function, that is, a utility function that maps to the unit interval, where
0 corresponds to the lowest and 1 to the highest evaluation. Even though the origi
nal motivation comes from quality control, FOTs are completely general and widely
applicable.
Our approach allows a human expert to specify a model in the form of an FOT in
a quite convenient and intuitive way. To this end, he simply has to split evaluation
criteria into sub criteria in a recursive manner, and to determine in which way these
sub criteria ought to be combined: conjunctively, disjunctively, or by means of an
averagingoperator. Theresultofthisprocessisthequalitativestructureofthemodel.
A second step, then, it is to parameterize the model. To support or even free the
expert form this step, we develop a method for calibrating the model on the basis of
exemplary ratings, that is, in a purely data driven way. This method, which makes
use of optimization techniques from the field of evolutionary algorithms, constitutes
thesecondmajorcontributionofthethesis.
The third contribution of the thesis is a method for evaluating an FOT in a cost
efficientway. Roughlyspeaking,anFOTcanbeseenasanaggregationfunctionthat
combines the evaluations of a number of basic criteria into an overall rating of an
object. Essentially, the cost of computing this rating is hence given by sum of the
evaluation costs of the basic criteria. In practice, however, the precise utility degree
is often not needed. Instead, it is enough to know whether it lies above or below
an important threshold value. In such cases, the evaluation process, understood as a
sequentialevaluationofbasiccriteria,canbestoppedassoonasthisquestioncanbe
answered in a unique way. Of course, the (expected) number of basic criteria and,
therefore,the(expected)evaluationcostwillthenstronglydependontheorderofthe
evaluations,andthisiswhatisoptimizedbythemethodsthatwehavedeveloped.
Keywords : utility function, rating function, quality assessment, fuzzy set, fuzzy
operator,evolutionstrategies,regression,ordinalclassification,costminimization.
Page: iZusammenfassung
In dieser Arbeit stellen wir eine Methode vor, um Bewertungsfunktionen zu mod
ellieren, die auf einem neuartigen Konzept der Fuzzy Operator Bäume (kurz FOT)
basieren. Wie der Name andeutet, nutzt diese Methode die Techniken aus Fuzzy Set
Theorie und implementiert eine Fuzzy Bewertungsfunktion, nämlich eine Funktion,
die das Einheitsinterval abbildet, wobei 0 der niedrigsten und 1 der höchsten Be
wertung entsprecht. Obwohl die erste Motivation von Qualitätsbewertung aus dem
Bereich der Produktsteuerung kommt, ist unser Modell völlig generell und deshalb
überalleinsetzbar.
UnsereMethodemachtesmöglich,dasseinmenschlicherExperteeinModelinForm
eines FOT in einem sehr intuitiven und attraktiven Weg spezifiziert. Schließlich
braucht er nur ein Hauptkriterium in mehrere Unterkriterien rekursiv zu zerlegen,
und entscheidet, in welche Art und Weise die zu kombinieren sind:
Konjunktion,DisjunktionoderimSinneeinesDurchschnitt Operators. DasResultat
ist die qualitative Struktur des FOT Models. In einem zweiten Schnitt wird dann das
Model parametrisiert. Um den menschlichen Experten dabei zu unterstützen, oder
ihn sogar abkömmlich zu machen, haben wir eine Methode zur Kalibrierung eines
Models entwickelt, die auf exemplarischenBewertungen basiert, inanderen Worten,
rein daten basiert ist. Diese Methode, die die Optimierungstechnik der Evolutions
strategieverwendet,bildetdenzweitenHauptbeitragdieserArbeit.
Der dritte Hauptbeitrag dieser Arbeit ist eine Methode zur Evaluierung eines FOTs
unter Berücksichtigung der Evaluierungskosten. Allgemein gesehen ist ein FOT
eine Aggregation, die die Evaluierungen mehrerer fundamentaler Kriterien zu einer
gesamt Bewertung eines Objektes kombiniert. Die Kosten für dieser gesamt Bew
ertung ist im Wesentlichen die Summe allen Evaluierungskosten der fundamentalen
Kriterien. Aber, eine präzise Bewertung ist nicht immer notwendig, stattdessen, re
ichtesoftaus,inmanchenSituationensicherzustellen,dassdieBewertungüberoder
unter einem wichtigen Schwellenwert liegt. Darüber hinaus kann ein Evaluierungs
prozess (sequentielle Evaluierung der fundamentalen Kriterien) gestoppt werden, so
lange diese Frage eindeutig beantwortet werden kann. Natürlich sind die erwarteten
Evaluierungskosten und Anzahl der Kriterien stark abhängig von der
OrdnungderEvaluierung,diedurchunsereneueMethodeauchoptimiertwird.
Schlüsselwörter: Bewertungsfunktion, Qualitätsmessung, Fuzzy Set, Fuzzy Opera
toren,Gradientenabstieg,Evolutionsstrategie.
Page: iiContents
Abstract i
Zusammenfassung ii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 FromSensingtoAutomaticQualityAssessment . . . . . . 1
1.1.2 TraditionalQualityAssessmentanditsDisadvantages . . . 2
1.1.3 ProblemofModelingUtilityFunction . . . . . . . . . . . . 4
1.2 ModelingwithFuzzyOperatorTree . . . . . . . . . . . . . . . . . 5
1.2.1 ASimpleExampleofFuzzyOperatorTree . . . . . . . . . 5
1.2.2 FeaturesofFuzzyOperatorTrees . . . . . . . . . . . . . . 6
1.2.3 HowtoBuildaFuzzyOperatorTree . . . . . . . . . . . . . 9
1.2.4 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 OutlineoftheThesis . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 ModelingUtilityFunctionswithFuzzyOperatorTrees 13
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 UtilityandUtilityFunctions . . . . . . . . . . . . . . . . . 13
2.1.2 ModelingUtility . . . . . . . . . . . . . . . . . . 14
2.2 FuzzySetTheory . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 FuzzySets . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 FuzzyAggregationOperators . . . . . . . . . . . . . . . . 22
2.2.3 LinguisticHedges . . . . . . . . . . . . . . . . . . . . . . 27
2.3 FuzzyOperatorTreeandProperties . . . . . . . . . . . . . . . . . 29
2.3.1 FormalDefinitionandPropertiesofFuzzyOperatorTree . . 30
2.3.2 AnExampleofFuzzyOperatorTree . . . . . . . . . . . . . 32
2.3.3 DiscreteValuesinFuzzyOperatorTree . . . . . . . . . . . 33
Page: iii2.4 FuzzyOperatorTreeElicitation . . . . . . . . . . . . . . . . . . . 33
2.4.1 FuzzySetElicitation . . . . . . . . . . . . . . . . . . . . . 34
2.4.2 InteriorStructureElicitation . . . . . . . . . . . . . . . . . 37
2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 CalibrationofFuzzyOperatorTrees 41
3.1 ProblemStatement . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 IdentifiabilityofFuzzyOperatorTree . . . . . . . . . . . . . . . . 45
3.3 CalibrationTechniques . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.1 GradientDescent . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.2 SimulatedAnnealing . . . . . . . . . . . . . . . . . . . . . 58
3.3.3 EvolutionStrategies . . . . . . . . . . . . . . . . . . . . . 59
3.4 ExperimentalEvaluation . . . . . . . . . . . . . . . . . . . . . . . 68
3.4.1 SyntheticData . . . . . . . . . . . . . . . . . . . . . . . . 68
3.4.2 ParameterDeterminationinEvolutionStrategies . . . . . . 72
3.4.3 NoisyData . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.4.4 DiscreteData . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.4.5 RealData . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
4 MinimizingEvaluationCostsforFuzzyOperatorTrees 89
4.1 ProblemStatement . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1.2 FormalDefinition . . . . . . . . . . . . . . . . . . . . . . . 90
4.1.3 AnIllustrativeExample . . . . . . . . . . . . . . . . . . . 95
4.1.4 BackgroundandConcepts . . . . . . . . . . . . . . . . . . 96
4.2 EstimatingOptimalEvaluationPlan . . . . . . . . . . . . . . . . . 97
4.2.1 TheBasicIdea . . . . . . . . . . . . . . . . . . . . . . . . 97
4.2.2 RoleofNorms . . . . . . . . . . . . . . . . . . . . . . . . 98
4.2.3 OnHierarchicalFuzzyOperatorTrees . . . . . . . . . . . . 103
4.2.4 AStaticAlgorithm . . . . . . . . . . . . . . . . . . . . . . 104
4.2.5 AnOnline . . . . . . . . . . . . . . . . . . . . . 108
4.2.6 OnCorrelatedData . . . . . . . . . . . . . . . . . . . . . . 110
4.2.7 ComplexityAnalysis . . . . . . . . . . . . . . . . . . . . . 110
4.3 ExperimentalEvaluation . . . . . . . . . . .