La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | technische_universitat_munchen |
Publié le | 01 janvier 2008 |
Nombre de lectures | 44 |
Poids de l'ouvrage | 1 Mo |
Extrait
A
Statistical
hApproac
Ulrich
to
ertkuc¨R
elRu
Learning
Institutf¨urInformatik,Lehrstuhlf¨urBioinformatik
AStatisticalApproachtoRule
Learning
¨tuckerRUlrich
Vollst¨andigerAbdruckdervonderFakult¨atf¨urInformatikderTechnischen
Universit¨atM¨unchenzurErlangungdesakademischenGradeseines
haftenNaturwissenscderDoktors
Dissertation.genehmigten
Vorsitzender:Univ.-Prof.Dr.H.J.Schmidhuber
Pr¨uferderDissertation:
KramerSt.Dr.Univ.-Prof.1.
2.TecUniv.-Prof.hnischeUniDr.vJ.ersit¨F¨aturnkranz,Darmstadt
DieeingereichtDissertationunddurcwurdehdieamFakult¨30.8.2007atf¨urbeiderInformatikTechniscamhen20.2.2008Universit¨atangenommen.M¨unchen
tstenCon
ductiontroIn11.1Motivation............................
1.1.1ATypicalLearningScenario..............
1.1.2TheTrade-OffBetweenComprehensibilityandPre-
dictiveAccuracy.....................
1.1.3StatisticalAnalysisofRuleLearning..........
1.2Applications............................
1.3OutlineoftheThesis.......................
LearningRule22.1Introduction............................
2.2RuleSetRepresentations....................
2.2.1DNFRuleSets......................
2.2.2DecisionLists.......................
2.2.3WeightedRuleSets....................
2.3RuleConditionRepresentations.................
2.4ChallengesinRuleLearning...................
2.4.1CombinatorialComplexity................
2.4.2OverfittingAvoidance..................
2.5AlgorithmicApproachestoRuleLearning...........
2.5.1Separate-and-Conquer..................
2.5.2OtherApproaches....................
LearninghineMacStatistical33.1Introduction............................
3.2AStatisticalFrameworkforClassification...........
3.3BasicResults...........................
3.3.1TheTestSetBound...................
3.3.2BayesClassifierandConsistency............
3.3.3NoFreeLunch......................
3.3.4ApproximationandEstimationError.........
3.4CapacityControl.........................
3.4.1EmpiricalRiskMinimization..............
i
1112456
991010111213151518202022
27272931323335384141
3.4.2StructuralRiskMinimization..............43
3.4.3Regularization......................45
3.5EnsembleTheory.........................47
3.5.1Bagging..........................47
3.5.2Boosting..........................49
3.6BayesianLearning........................52
57SetsRuleDNF44.1Trade-OffsinRuleLearning...................57
4.2EmpiricalRiskMinimizationforDNFRuleSets.......59
4.2.1ARandomizedAlgorithmfork-termDNFConsistency61
4.2.2StochasticLocalSearchfork-termDNFMaximum
Agreement........................68
4.3StructuralRiskMinimizationforDNFRuleSets.......73
24.3.1TheSLRuleLearner..................74
4.3.2Experiments.......................76
4.4EnsembleBasedCapacityControl...............83
4.4.1TheLearningSetting..................84
4.4.2LearningEnsemblesofRuleSets............85
4.4.3BoundsforRuleLearning................86
4.4.4Experiments.......................91
4.5SummaryandRelatedWork...................95
5WeightedRuleSets99
5.1Motivation............................99
5.2EmpiricalRiskMinimizationforWeightedRuleSets.....101
5.2.1Soft-MarginLoss.....................102
5.2.2EmpiricalMargin.....................103
5.2.3MarginMinusVariance.................105
5.3StructuralRiskMinimizationforWeightedRuleSets.....108
5.3.1RademacherBoundsforMMV.............109
5.3.2PAC-BayesianBoundsforMMV............115
5.3.3RepositorySizeBounds.................119
5.4TheRumbleSystem.......................125
5.5Experiments............................128
5.6SummaryandRelatedWork...................132
135LearningRuleFirst-Order66.1Motivation............................135
6.2ExtendingRumbletoFirst-OrderData............138
6.3AFrameworkforRelationalLearning.............141
6.3.1High-LevelView.....................142
6.3.2Low-LevelView......................146
6.3.3InstantiationsoftheFramework............148
ii
6.4Dispersion-BasedRuleGenerationforStructuredData....150
6.4.1FindingExpressiveRuleSets..............151
6.4.2StochasticLocalSearchforOptimalDispersionFeatures155
6.5Experiments............................162
6.5.1ExperimentswithRumbleonFirst-OrderData...162
6.5.2AnEmpiricalInvestigationofRuleLearninginthe
Framework........................164
6.5.3ExperimentsWithDispersion-BasedRuleGeneration169
6.6SummaryandRelatedWork...................171
7SummaryandOutlook175
7.1Summary.............................175
7.2Outlook..............................177
yBibliograph
Index
iii
179
198
iv
T
he
golden
rule
is
that
there
are
no
golden
rules.
georGe
dBernar
Shaw
Abstract
Thisdissertationinvestigatesrulelearningasastatisticalclassificationprob-
lem.Rulelearninghasalonghistoryinmachinelearningandisknownfor
inducinginterpretableandcomprehensibleclassifiers.Methodsfromsta-
tisticalmachinelearning,ontheotherhand,havetraditionallyfocusedon
predictiveaccuracy,oftenattheexpenseofinterpretability.Thegoalof
thisworkistocombinetheapproachestoobtainhighlypredictive,yetin-
terpretableclassifiers.Unlikemanyoftheheuristicsappliedintraditional
tionruleoflearning,rulelearningstatisticalsystems,princpiplesossiblyallowleadinforgatobvetteraluabletheoreticalinsights.invToestiga-this
end,weinvestigatetwotypesofrulesets,propositionallogicformulaein
formdisjunctivulae,eweinnormalvestigateformthe(DNFNP-hardformulae),problemandwofeightedempiricalrulerissets.kForminimiza-DNF
tionofDNFformulaeofatmostkterms.Weproposeastochasticlocal
search(SLS)algorithmtosolvethisproblemefficiently.Then,weapply
theSLSalgorithminastructuralriskminimizationproceduretogainsmall
yetpredictiverulesets.Alternatively,wecombineSLSwithanensem-
bleapproachtoreducetheestimationpartofthepredictionerrorandto
upper-bounditanalytically.Forweightedrulesets,wedeviseanovelconvex
optimizationcriterion,MarginMinusVariance(MMV),afeasiblerelaxation
oftheinfeasibleempiricalriskminimizationproblem.Forcapacitycontrol
wederiveanovelconcentrationinequality.Animplementationofthese
ideas,theRumblesystem,yieldsfavorableresultsinexperimentsdealing
withstructure-activityrelationshipsofsmallmolecules.Finally,formulti-
learningrelationalsystemslearning,weaccordingproptoosetheandflowuseofaframewinformationork.toWeassessevaluateanddifferencomparet
strategiesanalyticallyandexperimentallyandpresentanovelrulegenera-
tioncriterionthataimsathighlydiverserulesets.
ZusammenfassungDieseDissertationuntersuchtRegellernenalseinstatistischesKlassifikati-
onsproblem.RegellernenistseitlangemTeildesmaschinellenLernensund
bekanntdaf¨ur,einfachinterpretierbareundverst¨andlicheKlassifiziererzu
erzeugen.MethodendesstatistischenmaschinellenLernens,aufderande-
renSeite,konzentrierensich¨ublicherweiseaufdieVorhersagegenauigkeit,
des¨ofterenauchaufKostenderInterpretierbarkeit.DasZieldieserAr-
beitistes,diebeidenAns¨atzemiteinanderzukombinieren,umKlassifi-
ziermithoherVorhersagegenauigkeitundInterpretierbarkeitzuerstellen.
AußerdemerlaubenstatistischePrinzipien,andersalsdieHeuristiken,die
oftinherk¨ommlichenRegellernernverwendetwerden,einebesseretheore-
tischeAnalyse,diem¨oglicherweisezuwertvollenEinsichtenf¨uhrenk¨onnte.
WiruntersuchenzudiesemZweckezweiArtenvonRegelmengen,n¨amlich
aussagenlogischeFormelnindisjunktiverNormalform(DNF-Formeln)und
gewichteteRegelmengen.ImFallederDNF-Formelnuntersuchenwirdas
NP-harteProblem,denempirischenFehlervonDNF-Formelnmitmaxi-
malkKonjunktionenzuminimieren.WirschlageneinenAlgorithmusba-
sierendaufstochastischerlokalerSuche(SLS)vor,umdasProblemeffizient
zul¨osen.DanachwendenwirSLSinnerhalbeinerMethodezurstruktu-
rellenFehler-Minimierungan,umkleineRegelmengenmithoherVorhersa-
gegenauigkeitzugenerieren.AlseinenalternativenAnsatzverbindenwir
SLSmitEnsembles,umdenAbsch¨atzungsanteildesVorhersagefehlerszu
minimierenundaufanalytischeWeiseabzusch¨atzen.ImFalledergewich-
tetenRegelmengenentwerfenwirdasneuekonvexeOptimierungskriterium
“AbstandminusVarianz”(engl.MarginMinusVariance,MMV),einerea-
lisierbareVereinfachungdespraktischnichtrealisierbarenProblems,den
empirischenFehlerzuminimieren.F¨urdieKapazit¨ats¨uberwachungleiten
wireineneueUngleichungzurDichteabsch¨atzungher.EineImplementation
dervorgestelltenIdeen,dasRumble-System,erzieltpositiveErgebnissein
ExperimentenmitStruktur-Aktivit¨ats-BeziehungenvonkleinenMolek¨ulen.
F¨urmulti-relationalesLernen,schließlich,entwerfenundverwendenwirein
theoretischesSystem,indemverschiedeneLernsystemeanhanddesInfor-
mationsflussesbewertetundverglichenwerdenk¨onnen.Wirbewertenver-
schiedeneStrategienaufanalytischeundexperimentelleArtundWeiseund
stelleneinneuesRegel-Generierungskriteriumvor,dasaufhoheDiversit¨at
abzielt.Regelmengenin
tswledgemenknoAc
Manypeoplethinkthatwritingadissertationisadaunting,time-consuming,
anddifficulttask,whichneedstobewell-plannedanddemandsahighdegree
ofdisciplineanddiligence.Thisisnotconsistentwithmyexperience.I
foundthatwritingadissertationisadaunting,time-consuming,anddifficult
advtask,enturewhichandnevergenerallyprocee