La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Learning to predict combinatorial structures [Elektronische Ressource] / vorgelegt von Shankar Vembu

De
122 pages
Learning to Predict CombinatorialStructuresDissertationzurErlangung des Doktorgrades (Dr. rer. nat.)derMathematisch-Naturwissenschaftlichen Fakult¨atderRheinischen Friedrich-Wilhelms-Universit¨at Bonnvorgelegt vonShankar VembuausVizag, IndienUrbana, IL, USA, 2010iiAngefertigt mit Genehmigung der Mathematisch-NaturwissenschaftlichenFakult¨at der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn1. Referent: Prof. Dr. Stefan Wrobel2. Referent: Prof. Dr. Michael ClausenTag der Promotion: 18.05.2010ZusammenfassungDie gr¨oßte Herausforderung bei der Entwicklung von diskriminativen Ler-nalgorithmen fu¨r die Vorhersage von strukturierte Ausgaben stellt die An-zahl der m¨oglichen Ausgaben dar. Diese kann n¨amlich exponentiell mit derEingabegr¨oße wachsen, so dass ersch¨opfendes Testen nicht in hinreichendkurzer Zeit m¨oglich ist. Um dennoch effiziente Lernalgorithmen zu erhal-ten, hatmanbishergewisse Annahmengetroffen. Fu¨rviele kombinatorischeStrukturen, wie z.B. Kreise in Graphen, sind diese Annahmen jedoch nichtzutreffend. In dieser Arbeit entwicklen wir Lernalgorithmen fu¨r strukturi-erte Ausgaben unter zwei neuen Annahmen, die von viele kombinatorischenStrukturen erfu¨llt werden:(i) DieersteAnnahmeist,dasseinbestimmtesZ¨ahlproblemeffizientgelo¨stwerden kann. Unter dieser Annahme entwickeln wir eine Verallge-meinerung der klassischen Kleinste-Quadrate Methode fu¨r strukturteAusgaben.
Voir plus Voir moins

Learning to Predict Combinatorial
Structures
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakult¨at
der
Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
vorgelegt von
Shankar Vembu
aus
Vizag, Indien
Urbana, IL, USA, 2010ii
Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen
Fakult¨at der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
1. Referent: Prof. Dr. Stefan Wrobel
2. Referent: Prof. Dr. Michael Clausen
Tag der Promotion: 18.05.2010Zusammenfassung
Die gr¨oßte Herausforderung bei der Entwicklung von diskriminativen Ler-
nalgorithmen fu¨r die Vorhersage von strukturierte Ausgaben stellt die An-
zahl der m¨oglichen Ausgaben dar. Diese kann n¨amlich exponentiell mit der
Eingabegr¨oße wachsen, so dass ersch¨opfendes Testen nicht in hinreichend
kurzer Zeit m¨oglich ist. Um dennoch effiziente Lernalgorithmen zu erhal-
ten, hatmanbishergewisse Annahmengetroffen. Fu¨rviele kombinatorische
Strukturen, wie z.B. Kreise in Graphen, sind diese Annahmen jedoch nicht
zutreffend. In dieser Arbeit entwicklen wir Lernalgorithmen fu¨r strukturi-
erte Ausgaben unter zwei neuen Annahmen, die von viele kombinatorischen
Strukturen erfu¨llt werden:
(i) DieersteAnnahmeist,dasseinbestimmtesZ¨ahlproblemeffizientgelo¨st
werden kann. Unter dieser Annahme entwickeln wir eine Verallge-
meinerung der klassischen Kleinste-Quadrate Methode fu¨r strukturte
Ausgaben.
(ii) Die zweite Annahme ist, dass ein bestimmtes Probenentnahmepro-
lem effizient gelo¨st werden kann. Unter dieser Annahme entwickeln
wir einen neuen, wahrscheinlichkeitstheoretischen Lernalgorithmus fu¨r
strukturierte Ausgaben.
Diese Algorithmen lo¨sen als Spezialf¨alle viele klassische Lernprobleme, wie
zum Beispiel die Mehrfachkennzeichen-Klassifikation, Kennzeichenordnen
und hierarchische Mehrfachkategorien-Klassifikation.Abstract
Themajorchallengeindesigningadiscriminativelearningalgorithmforpre-
dicting structured data is to address the computational issues arising from
the exponential size of the output space. Existing algorithms make differ-
ent assumptions to ensure efficient, polynomial time estimation of model
parameters. For several combinatorial structures, including cycles, partially
ordered sets, permutations and other graph classes, these assumptions do
not hold. In this thesis, we address the problem of designing learning al-
gorithms for predicting combinatorial structures by introducing two new
assumptions:
(i) The first assumption is that a particular counting problem can be
solved efficiently. The consequence is a generalisation of the classical
ridge regression for structured prediction.
(ii) The second assumption is that a particular sampling problem can be
solved efficiently. The consequence is a new technique for designing
and analysing probabilistic structured prediction models.
These results can be applied to solve several complex learning problems
including but not limited to multi-label classification, multi-category hier-
archical classification, and label ranking.Acknowledgements
To Stefan Wrobel, for giving me the opportunity to pursue doctoral studies
atFraunhoferIAIS,andforreadingdraftsofthismanuscriptandsuggesting
improvements.
To Michael May, for giving me the opportunity to pursue doctoral stud-
ies at the Knowledge Discovery lab.
To Michael Clausen, Peter K¨opke, and Andreas Weber, for serving on my
thesis committee.
To Thomas G¨artner, for continual advice, for introducing me to graph the-
ory and kernel methods, for teaching me how to write technical papers, for
numerousdiscussionsontopicsrelatedtomachinelearning,andforcarefully
reading drafts of this manuscript and suggesting improvements.
To Tamas Horv´ath and Kristian Kersting, for numerous discussions on re-
search in general.
To Mario Boley, for discussions on topics related to theoretical computer
science, and for being a wonderful colleague.
To J¨org Kindermann, for providing me with computing resources needed
to run the experiments described in Chapter 5.
To Daniela B¨orner, Renate Henkeler, and Myriam Jourdan, for helping me
with administrative issues.
To Jens Humrich and Katrin Ullrich, for being wonderful colleagues.
To all the members of the IAIS.KD lab, for creating a conducive atmo-
sphere that allowed me to work towards a doctorate in machine learning.
To family and friends.viii
And lastly, to David Baldacci’s novels, for inspiring me to acknowledge in
this way!Contents
Zusammenfassung iii
Abstract v
Acknowledgments vii
Notational Conventions xi
1 Introduction 1
1.1 Structured Prediction . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Why Predict Combinatorial Structures? . . . . . . . . . . . . 5
1.3 Goals and Contributions . . . . . . . . . . . . . . . . . . . . . 7
1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Bibliographical Notes. . . . . . . . . . . . . . . . . . . . . . . 9
2 Structured Prediction 11
2.1 Loss Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Predicting Permutations 23
3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Learning Reductions . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Boosting Methods . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Label Ranking SVM . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 Structured Prediction . . . . . . . . . . . . . . . . . . . . . . 29
3.6 Online Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.7 Instance-based Learning . . . . . . . . . . . . . . . . . . . . . 32
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Complexity of Learning 35
4.1 Efficient Learning . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Hardness Results . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Two New Assumptions . . . . . . . . . . . . . . . . . . . . . . 43x CONTENTS
4.3.1 The Counting Assumption . . . . . . . . . . . . . . . . 43
4.3.2 The Sampling Assumption. . . . . . . . . . . . . . . . 46
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5 Structured Ridge Regression 49
5.1 Ridge Regression . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.2 Training Combinatorial Structures . . . . . . . . . . . . . . . 50
5.3 Scalability Issues . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.1 Linear models . . . . . . . . . . . . . . . . . . . . . . . 54
5.3.2 Online Optimisation . . . . . . . . . . . . . . . . . . . 55
5.4 Approximate Inference . . . . . . . . . . . . . . . . . . . . . . 57
5.4.1 Approximate Decoding. . . . . . . . . . . . . . . . . . 58
5.4.2 Approximate Enumeration . . . . . . . . . . . . . . . 59
5.5 Empirical Results . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 Probabilistic Structured Prediction 67
6.1 Probabilistic Models and Exponential Families . . . . . . . . 67
6.2 Hardness of Computing the Partition Function . . . . . . . . 69
6.3 Approximating the Partition Function Using Uniform Samplers 70
6.4 Approximating the Partition Function Using Counting For-
mulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.5 Approximating the Gradient of the Log Partition Function . 75
6.6 Sampling Techniques . . . . . . . . . . . . . . . . . . . . . . . 76
6.6.1 Basics of Markov Chains . . . . . . . . . . . . . . . . . 76
6.6.2 A Meta Markov chain . . . . . . . . . . . . . . . . . . 80
6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7 Conclusions 85
A Kernels and Low-dimensional Mappings 89
B Counting Dicyclic Permutations 91
C Appendix for Chapter 6 93
C.1 ApproximatingthePartitionFunctionusingApproximateSam-
ples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
C.2 Approximating the Gradient of the Log Partition Function
using a Reduction from Counting to Sampling . . . . . . . . . 95
C.3 Mixing Time Analysis of MC using Path Coupling . . . . 96cube
References 99