Computer Science – Learning
Scientific paper
2009-12-22
Computer Science
Learning
PhD thesis, Department of Computer Science, University of Bonn (submitted, December 2009)
Scientific paper
The 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.
No associations
LandOfFree
Learning to Predict Combinatorial Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Learning to Predict Combinatorial Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning to Predict Combinatorial Structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-307726