Non-convex and multi-objective optimization in data mining [Elektronische Ressource] : non-convex and multi-objective optimization for statistical learning and numerical feature engineering / von Ingo Mierswa

Description

Non-Convex and Multi-ObjectiveOptimization in Data MiningNon-Convex and Multi-Objective Optimization forStatistical Learning and Numerical Feature EngineeringDissertationzur Erlangung des Grades einesDoktors der Naturwissenschaftender Technischen Universit¨at Dortmundan der Fakult¨at f¨ur InformatikvonIngo MierswaDortmund20092Tag der mu¨ndlichen Pru¨fung: 27.04.2009Dekan: Prof. Dr. Peter BuchholzGutachter: Prof. Dr. Katharina MorikProf. Dr. Claus Weihs34AcknowledgmentsI would like to express my gratitude to my supervisor, Prof. Dr. Katharina Morik,whose expertise, understanding, patience, and personality added considerably to thisthesis and the last years of my life. I appreciate her vast knowledge and skill and thatshe always gave me the freedom to work on topics of my preference and – maybe evenmore important – to develop my own style of work. During the last years, she becamemore of a mentor and friend than a professor to me.I would like to thank Prof. Dr. Claus Weihs for the assistance he provided and hisvaluablehintshowIcouldimprovemythesis. Itwasreallyhelpfultogetthosecommentson all levels of detail and especially to get these comments from a statistician’s point ofview.I would like to thank the members of the Artificial Intelligence Group, past and present.I find it quite interesting that the time we played soccer almost every day on a parkinglot was also the time everyone of us published most of his work.

Sujets

• Informatik
• Mathematics

Informations

• Publié par: technischen_universitat_dortmund
• Publié le: 01 janvier 2009
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

Non-ConvexandMulti-Objective
OptimizationinDataMining

Non-ConvexandMulti-ObjectiveOptimizationfor
StatisticalLearningandNumericalFeatureEngineering

Dissertation

zurErlangungdesGradeseines

DoktorsderNaturwissenschaften

derTechnischenUniversita¨tDortmund
anderFakulta¨tfu¨rInformatik
nov

IngoMierswa

Dortmund
2900

2

gaT

red

mu¨ndlichen

Pru¨fung:

Dekan:

Gutachter:

27.04.2009

Prof.Dr.Peter

Buchholz

Prof.Dr.KatharinaMorik
Prof.Dr.ClausWeihs

3

4

Acknowledgments

Iwouldliketoexpressmygratitudetomysupervisor,Prof.Dr.KatharinaMorik,
whoseexpertise,understanding,patience,andpersonalityaddedconsiderablytothis
thesisandthelastyearsofmylife.Iappreciatehervastknowledgeandskillandthat
shealwaysgavemethefreedomtoworkontopicsofmypreferenceand–maybeeven
moreimportant–todevelopmyownstyleofwork.Duringthelastyears,shebecame
moreofamentorandfriendthanaprofessortome.
IwouldliketothankProf.Dr.ClausWeihsfortheassistanceheprovidedandhis
valuablehintshowIcouldimprovemythesis.Itwasreallyhelpfultogetthosecomments
onalllevelsofdetailandespeciallytogetthesecommentsfromastatistician’spointof
.weivIwouldliketothankthemembersoftheArticialIntelligenceGroup,pastandpresent.
Inditquiteinterestingthatthetimeweplayedsocceralmosteverydayonaparking
lotwasalsothetimeeveryoneofuspublishedmostofhiswork.Butasweallknow:
correlationdoesnotnecessarilymeanscausality.
Irecognizethatthisresearchwouldnothavebeenpossiblewithoutthenancialas-
sistanceoftheGermanResearchFoundation(DeutscheForschungsgemeinschaft,DFG)
whosupportedthisworkwithintwocollaborativeresearchcenters(Sonderforschungs-
bereiche,SFB),namelytheSFB531“DesignandManagementofComplexTechnical
ProcessesandSystemsbyMeansofComputationalIntelligenceMethods”andtheSFB
475“ReductionofComplexityinMultivariateDataStructures”.
LastbutnotleastIwouldliketothankmyfamilyforthesupporttheyprovidedme
throughmyentirelifeandinparticular,Imustacknowledgemywifeandbestfriend,
Nadja.

5

6

According

%34

fo

lal

ot

eht

latest

statistics

era

ocial

totally

gures,

worthless.

7

Contents
ListofTables15
ListofFigures19
ListofNotations25
1.Introduction31
1.1.ThreeThesesaboutDataMining.......................31
1.2.RelatedWork..................................36
1.3.Outline.....................................39
2.Basics41
2.1.MachineLearning................................41
2.1.1.SupervisedLearning..........................42
2.1.1.1.ClassicationLearning...................43
2.1.1.2.RegressionLearning.....................43
2.1.2.UnsupervisedLearning.........................43
2.2.StatisticalLearning...............................44
2.2.1.RegularizedRiskMinimization....................44
2.2.1.1.BoundontheGeneralizationPerformance........46
2.2.2.LargeMarginMethods.........................47
2.2.2.1.SupportVectorMachines..................47
2.2.2.2.Non-SeparableData.....................50
2.2.2.3.Non-LinearLearningwithKernels.............51
2.3.Optimization..................................53
2.3.1.LinearProgramming..........................54
2.3.2.QuadraticandNon-LinearProgramming..............55
2.3.2.1.Nelder-MeadOptimization.................55
2.3.2.2.NewtonOptimization....................55
2.3.3.Non-ConvexProgramming.......................57
9

Contents

2.3.3.1.EvolutionaryAlgorithms..................57
2.4.Multi-ObjectiveOptimization.........................59
2.4.1.Multi-ObjectiveEvolutionaryOptimization.............60
2.4.1.1.GuidedMulti-ObjectiveOptimization...........61

I.Learning63
3.Multi-ObjectiveLearning65
3.1.Single-ObjectiveEvolutionarySupportVectorMachines..........65
3.1.1.MotivationforEvolutionarySupportVectorMachines.......66
3.1.2.EvolutionaryComputationforLargeMarginOptimization....68
3.1.2.1.SolvingtheDualProblemandOtherSimplications...68
3.1.2.2.EvoSVMandPsoSVM...................69
3.1.3.ExperimentsandResults.......................71
3.1.3.1.DataSets...........................71
3.1.3.2.ComparisonfortheObjectiveFunction..........71
3.1.3.3.ComparisonforPositiveKernels..............72
3.2.Multi-ObjectiveStatisticalLearning.....................77
3.2.1.TheRegularizedRiskConsistsofMultipleObjectives.......77
3.2.2.ExplicitTrade-obetweenErrorandComplexity..........79
3.2.3.FirstObjective:MaximizingtheMargin...............80
3.2.4.SecondObjective:MinimizingtheNumberofTrainingErrors...82
3.2.5.Multi-ObjectiveEvolutionaryAlgorithmsforLargeMarginLearning83
3.2.5.1.DenitionoftheObjectives.................83
3.2.5.2.TheMulti-ObjectiveEvoSVM...............84
3.2.6.SelectingaSolutionfromtheParetoSet...............84
3.2.7.ExperimentsandResults.......................86
3.2.7.1.InterpretationoftheParetoFronts.............86
3.2.7.2.Multi-ObjectiveOptimizationvs.MultipleSingle-Objective
Runs.............................91
4.Non-ConvexOptimizationforStatisticalLearning93
4.1.Non-PositiveSemideniteKernelFunctions.................93
4.1.1.TheRelevanceVectorMachine:AKernelMethodforIndenite
KernelFunctions............................95
4.2.ExperimentsandResults............................99
4.2.1.EvolutionaryComputationforNon-ConvexOptimization.....99
4.2.2.DataSets................................99
4.2.3.ComparisonforNon-positiveKernels.................100

01

Contents

5.TransductiveLearning:Non-ConvexandMulti-Objective103
5.1.MotivationofTransductiveLearning.....................103
5.1.1.ProblemDe