Large Margin Methods for Structured and Interdependent Output.pdf

Journal of Machine Learning Research 6 (2005) 1453–1484 Submitted 11/04; Published 9/05 Large Margin Methods for Structured and Interdependent Output Variables Ioannis Tsochantaridis IOANNIS @GOOGLE .COM Google, Inc. Mountain View, CA 94043, USA Thorsten Joachims TJ @CS .CORNELL .EDU Department of Computer Science Cornell University Ithaca, NY 14853, USA Thomas Hofmann HOFMANN @INT.TU -DARMSTADT.DE Darmstadt University of Technology Fraunhofer IPSI Darmstadt, Germany Yasemin Altun ALTUN @TTI -C .ORG Toyota Technological Institute Chicago, IL 60637, USA Editor: Yoram Singer Abstract Learning general functional dependencies between arbitrary input and output spaces is one of the key challenges in computational intelligence. While recent progress in machine learning has mainly focused on designing flexible and powerful input representations, this paper addresses the comple- mentary issue of designing classification algorithms that can deal with more complex outputs, such as trees, sequences, or sets. More generally, we consider problems involving multiple dependent output variables, structured output spaces, and classification problems with class attributes. In order to accomplish this, we propose to appropriately generalize the well-known notion of a separation margin and derive a corresponding maximum-margin formulation. While this leads to a quadratic program with a potentially prohibitive, i.e. exponential, number of constraints, we present a cut- ting