2018/09/14 by Heejin Choi, Choi, Heejin
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.1809.05550
openalex publication_date 2018/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this dissertation, we focus on several important problems in structured\nprediction. In structured prediction, the label has a rich intrinsic\nsubstructure, and the loss varies with respect to the predicted label and the\ntrue label pair. Structured SVM is an extension of binary SVM to adapt to such\nstructured tasks.\n In the first part of the dissertation, we study the surrogate losses and its\nefficient methods. To minimize the empirical risk, a surrogate loss which upper\nbounds the loss, is used as a proxy to minimize the actual loss. Since the\nobjective function is written in terms of the surrogate loss, the choice of the\nsurrogate loss is important, and the performance depends on it. Another issue\nregarding the surrogate loss is the efficiency of the argmax label inference\nfor the surrogate loss. Efficient inference is necessary for the optimization\nsince it is often the most time-consuming step. We present a new class of\nsurrogate losses named bi-criteria surrogate loss, which is a generalization of\nthe popular surrogate losses. We first investigate an efficient method for a\nslack rescaling formulation as a starting point utilizing decomposability of\nthe model. Then, we extend the algorithm to the bi-criteria surrogate loss,\nwhich is very efficient and also shows performance improvements.\n In the second part of the dissertation, another important issue of\nregularization is studied. Specifically, we investigate a problem of\nregularization in hierarchical classification when a structural imbalance\nexists in the label structure. We present a method to normalize the structure,\nas well as a new norm, namely shared Frobenius norm. It is suitable for\nhierarchical classification that adapts to the data in addition to the label\nstructure.\n