Large Margin Methods for Structured and Interdependent Output Variables

摘要

Learning general functional dependencies between arbitrary input andoutput spaces is one of the key challenges in computationalintelligence. While recent progress in machine learning has mainlyfocused on designing flexible and powerful input representations, thispaper addresses the complementary issue of designing classificationalgorithms that can deal with more complex outputs, such as trees,sequences, or sets. More generally, we consider problems involvingmultiple dependent output variables, structured output spaces, andclassification problems with class attributes. In order to accomplishthis, we propose to appropriately generalize the well-known notion ofa separation margin and derive a corresponding maximum-marginformulation. While this leads to a quadratic program with apotentially prohibitive, i.e. exponential, number of constraints, wepresent a cutting plane algorithm that solves the optimization problemin polynomial time for a large class of problems. The proposed methodhas important applications in areas such as computational biology,natural language processing, information retrieval/extraction, andoptical character recognition. Experiments from various domainsinvolving different types of output spaces emphasize the breadth andgenerality of our approach. color="gray">