Show simple item record

Learning to Predict Combinatorial Structures

dc.contributor.advisorWrobel, Stefan
dc.contributor.authorVembu, Shankar
dc.description.abstractThe major challenge in designing a discriminative learning algorithm for predicting structured data is to address the computational issues arising from the exponential size of the output space. Existing algorithms make different 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 algorithms 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 hierarchical classification, and label ranking.
dc.rightsIn Copyright
dc.subjectMachine learning
dc.subjectStructured prediction
dc.subjectKernel methods
dc.subjectGraph theory
dc.subjectMarkov chain
dc.subjectMonte Carlo Theory
dc.subject.ddc004 Informatik
dc.titleLearning to Predict Combinatorial Structures
dc.typeDissertation oder Habilitation
dc.publisher.nameUniversitäts- und Landesbibliothek Bonn
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeClausen, Michael

Files in this item


This item appears in the following Collection(s)

Show simple item record

The following license files are associated with this item: