Record Details

Efficient Algorithms for Structured Output Learning

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Efficient Algorithms for Structured Output Learning
 
Creator Balamurugan, P
 
Subject Structured Output Learning
Structured Output Learning Algorithms
Machine learning
Structural Support Vector Machines
Sparse Structured Output Learning
Sequential Dual Methods
Structural Comditional Random Fields (CRFs)
Semi-supervised Structural SVMs
Structural SVMs
Sparse Structural SVMs
Computer Science
 
Description Structured output learning is the machine learning task of building a classifier to predict structured outputs. Structured outputs arise in several contexts in diverse applications like natural language processing, computer vision, bioinformatics and social networks. Unlike the simple two(or multi)-class outputs which belong to a set of distinct or univariate categories, structured outputs are composed of multiple components with complex interdependencies amongst them. As an illustrative example ,consider the natural language processing task of tagging a sentence with its corresponding part-of-speech tags. The part-of-speech tag sequence is an example of a structured output as it is made up of multiple components, the interactions among them being governed by the underlying properties of the language. This thesis provides efficient solutions for different problems pertaining to structured output learning. The classifier for structured outputs is generally built by learning a suitable model from a set of training examples labeled with their associated structured outputs. Discriminative techniques like Structural Support Vector Machines(Structural SVMs) and Conditional Random Fields(CRFs) are popular alternatives developed for structured output learning. The thesis contributes towards developing efficient training strategies for structural SVMs. In particular, an efficient sequential optimization method is proposed for structural SVMs, which is faster than several competing methods. An extension of the sequential method to CRFs is also developed. The sequential method is adapted to a variant of structural SVM with linear cumulative loss. The thesis also presents a systematic empirical evaluation of various training methods available for structured output learning, which will be useful to the practitioner. To train structural SVMs in the presence of a vast number of training examples without labels, the thesis develops a simple semi-supervised technique based on switching the labels of the components of the structured output. The proposed technique is general and its efficacy is demonstrated using experiments on different benchmark applications. Another contribution of the thesis is towards the design of fast algorithms for sparse structured output learning. Efficient alternating optimization algorithms are developed for sparse classifier design. These algorithms are shown to achieve sparse models faster, when compared to existing methods.
 
Contributor Shevade, Shirish K
 
Date 2018-05-08T06:45:39Z
2018-05-08T06:45:39Z
2018-05-08
2014
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/2005/3488
http://etd.iisc.ernet.in/abstracts/4355/G26588-Abs.pdf
 
Language en_US
 
Relation G26588