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

-

English
174 Pages
Read an excerpt
Gain access to the library to view online
Learn more

Description

Fuzzy Operator Trees for Modeling UtilityFunctionsDissertationzurErlangung des Doktorgradesder Naturwissenschaften(Dr. rer. nat.)demFachbereichMathematikundInformatikderPhilipps UniversitätMarburgvorgelegtvonYuYiausChangsha,ChinaMarburg/Lahn2008VomFachbereichMathematikundInformatikderPhilipps UniversitätMarburgalsDissertationam08.12.2008angenommen.Erstgutachter: Prof. Dr. EykeHüllermeierZweitgutachter: Prof. Dr. BerndFreislebenTagdermündlichenPrüfungam12.12.2008AbstractIn this thesis, we propose a method for modeling utility (rating) functions based ona 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 afuzzy rating function, that is, a utility function that maps to the unit interval, where0 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 widelyapplicable.Our approach allows a human expert to specify a model in the form of an FOT ina quite convenient and intuitive way. To this end, he simply has to split evaluationcriteria into sub criteria in a recursive manner, and to determine in which way thesesub criteria ought to be combined: conjunctively, disjunctively, or by means of anaveragingoperator. Theresultofthisprocessisthequalitativestructureofthemodel.A second step, then, it is to parameterize the model.

Subjects

Informations

Published by
Published 01 January 2008
Reads 14
Language English
Document size 2 MB
Report a problem

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 . . . . . . . . . . . . . . . . . . . . . . . 111
4.3.1 ExperimentSetup . . . . . . . . . . . . . . . . . . . . . . . 111
4.3.2 ExperimentalResults . . . . . . . . . . . . . . . . . . . . . 112
4.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5 RelatedWork 117
Page: ivChapter0: Contents
5.1 UtilityTheoryandUtilityModeling . . . . . . . . . . . . . . . . . 117
5.2 HierarchicalModeling . . . . . . . . . . . . . . . . . . . . . . . . 119
5.3 FuzzyLogic basedOperatorsinDecisionMaking . . . . . . . . . 120
5.4 CalibrationofaNetwork likeStructure . . . . . . . . . . . . . . . 121
6 ConclusionsandFutureWork 123
6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
A Appendix: Listoft normsandt conorms 127
B Appendix: AJavaImplementation 129
B.1 TheClassStructure . . . . . . . . . . . . . . . . . . . . . . . . . . 129
B.2 TheMainFunctionalities . . . . . . . . . . . . . . . . . . . . . . . 132
B.2.1 GraphicalModule . . . . . . . . . . . . . . . . . . . . . . 132
B.2.2 CommandModule . . . . . . . . . . . . . . . . . . . . . . 136
ListofFigures 139
ListofTables 143
ListofAlgorithms 145
Index 147
Bibliography 151
Acknowledgements 163
CurriculumVitae 165
Page: vPage: viIntroduction
1
Inthischapter, wegiveanintroductiontothemaintopicofthisthesis,namelymod
elingutilityfunctionsusingfuzzyoperatortree(FOTforshort). Afterthemotivation
in Section 1.1, we give the basic idea of FOT and the main techniques used in this
thesisinSection1.2. Finallywegiveanoverviewoftheorganizationofthisthesisin
Section1.3.
1.1Motivation
The objective of this section is to introduce the main motivation of this thesis. We
begin with the idea to apply automatic quality assessment instead of human experts.
Thentheproblembytraditionalqualityassessmentisdemonstratedandsummarized.
To this end we generalize the expectations of a new method for modeling utility
functions.
1.1.1 FromSensingtoAutomaticQualityAssessment
The original idea of modeling with FOT is motivated by quality assessment in prod
uct control, where the evaluation and assessment of products become a fundamental
task. Duetothegrowingglobalcompetition,companiesarecontinuouslyseekingfor
efficient and short developmental periods. At the same time, the demand on prod
uct quality and consequently customer satisfaction arises recently, so that systems to
ensureproductsorservicesandassessqualityofproductshavegainedincreasingim
portance. Inthisregard,qualitycontrolandqualityengineering[Pyz03]hasbecome
anattractiveresearchareainlastdecades. Wewillfocusononeofitscurrentresearch
activities,namelyautomaticqualityassessment(orqualityevaluation),inthisthesis.
Untilnow,manyqualityassessmentsareusuallycarriedoutbyahumanexpertmanu
ally. Bydefinition,anexpertisapersonwhoiswellknowledgeableabouttheobject,
e.g. a food expert of quality control is a person who can identify quality of food
well, etc. An expert is also called decision maker in the decision making problems
[Saa94], since the knowledge of experts is expressed in the form of decisions in this
case. Thisisnotalwaysaconvenientwaybecauseoffollowingdifficulties:
1. Firstofall,thereareusuallyonlylimitedhumanresourcesavailableinpractice,
butmanyproblemshavetobesolved. Fromfinancialaspectitisnotfavorable,
because human experts are not always available and maintaining human ex
pertsisinmostcasemoreexpensivethanusingmeasuringinstruments.
Page: 1Section1.1: Motivation
2. The assessment is relatively subjective, since human experts may give differ-
ent judgments even under identical conditions, and variable outcomes can be
drawnbythesameexpertfromtimetotime.
However in a globalized world, the objective, efficient quality assessment schema
has played an essential role for quality control independent of place of production,
especiallywhenproductsorcomponentsofproductscomefromdifferentregions.
One trend to overcome the aforementioned difficulties is to apply electronic mea
suring instruments to take the place of human experts. For example, the company
1“BattenbergRobotic” developsroboticsashigh precisionsensorymeasuringinstru
ments(seeFigure1.1),whicharespeciallyadaptedforconstraint dependentmeasur-
ingtasksinautomaticproductionandcontrolprocessesforthepurposeofguarantee
inganobjectiveprovableproductassessmentforproducerandcomponentsupplier.
Whiletheautomaticacquisitionofqualitymeasurementshasalreadybeenprogressed
in many industrial fields, the development of automatic quality assessment based on
acquired measurements is still not satisfied, since the automatic quality evaluations
are mostly strongly deflected from those empirical evaluations from human experts.
Weshallreviewtraditionalqualityassessmentanditsdisadvantagesinnextsection.
Figure 1.1: From sensing
to automatic assessment
1.1.2 TraditionalQualityAssessmentanditsDisadvantages
Traditionalqualityassessmentusuallyreliesonpredefined“tolerance”domains,which
indicate the desired intervals for measured criteria. A product is then labeled as “in
order”(abbreviated,IO),ifallcriterialiewithingivenintervals, otherwise
itis“notinorder”(or“outoforder”,abbreviatedNIO),nomatterhowmanycriterion
failed.
Let’sconsideraconcreteexample,inwhichthegoalistoevaluateatechnicaldevice
such as the control panel of car radios, see Figure 1.2, where the quality depends on
the operability of functional components: The switch button A, the adjusting knob B
and several functional buttons C, D, E, and so on. To assess the quality of control
panel automatically, a robot might be applied to test the operability of components,
in which a robot pushes buttons to predefined pressure, and drives back afterward,
so that the buttons return their starting positions. At the same time, several measure
ments are recorded, for example, the maximal position or strength of robot to reach
predefinedpressure.
For adjusting knobs like B here, a robot rotates the adjusting knob into a predefined
position, and again rotates it back into the starting position, at the same time similar
measurements are recorded. For the sake of clearness, let us assume the operability
1 www.battenberg.biz
Page: 2